第四章数学规划方法建模.ppt

第四章数学规划方法建模4.1 4.1 线性规划方法建模线性规划方法建模4.1.1 4.1.1 线性规划方法简介线性规划方法简介2020/12/324.1 4.1 线性规划方法建模线性规划方法建模4.1.2 4.1.2 线性规划方法建模的根本技巧线性规划方法建模的根本技巧 简单上界和下界约束流约束 简单资源约束 物料平衡约束 质量要求约束 2020/12/334.1 4.1 线性规划方法建模线性规划方法建模4.1.3 4.1.3 线性规划的线性规划的LingoLingo实现实现 例1 求解线性规划 2020/12/344.1 4.1 线性规划方法建模线性规划方法建模model:sets:row/1.4/:b;col/1.3/:c,x;matrix(row,col):A;endsets max=sum(col:c*x);for(row(i):sum(col(j):A(i,j)*x(j)=b(i);data:c=60,30,20;b=48,20,8,5;A=8,6,1 4,2,1.5 2,1.5,0.5 0,2,0;enddata end2020/12/354.1 4.1 线性规划方法建模线性规划方法建模4.1.4 4.1.4 线性规划方法建模例如线性规划方法建模例如例如1 棋子问题 有一个木匠作坊制作两种不同大小的黄杨木棋子小型棋子一套需要车床加工3小时，大型棋子一套需要2小时木匠作坊内有4个车床和4名纯熟操作员，每人每周工作40小时小型棋子一套需要1千克黄杨木，大型棋子一套需要3千克黄杨木黄杨木每周只能得到200千克假如售出，每套大型棋子可以得到20元利润，每套小型棋子可以得到5元利润 确定加工两种棋子的数量，使得总利润最大2020/12/364.1 4.1 线性规划方法建模线性规划方法建模问题的最优解及最优值为：2020/12/374.1 4.1 线性规划方法建模线性规划方法建模例如2 连续投资问题 某部们在今后五年内考虑给以下工程投资，并：工程A，从第一年到第四年每年年初需要投资，并于次年末回收本利115%；工程B，第三年初需要投资，到第五年末能回收本利125%，但规定最大投资额不超过4万元；工程C，第二年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过3万元；工程D，五年内每年初可购置公债，于当年末归还，并加利息6%该部们如今有资金10万元，问它应如何确定给这些工程每年的投资额，使得第五年末拥有的资金的本利总额为最大？2020/12/384.1 4.1 线性规划方法建模线性规划方法建模2020/12/394.1 4.1 线性规划方法建模线性规划方法建模问题的最优结果为：第1年投资：A工程34782.61元，D工程65217.39元 第2年投资：A工程39130.43元，C工程30000元，D工程0元 第3年投资：A工程0元，B工程40000元，D工程0元 第4年投资：A工程45000元，D工程0元 第5年投资：D工程0元 第五年末该部们拥有资金总额为143750元，即盈利43.75%2020/12/3104.1 4.1 线性规划方法建模线性规划方法建模例如3 货机装运问题 某运货机有三个机舱：前舱，中舱，后舱三个货舱所能载的货物的最大体积和最大重量如表4-1所示为了保证飞机的平衡，三个货舱中实际装载货物的重量必须与其最大容量成比例 现有四类货物需飞行装运，有关运送数据见表4-2,试建立数学模型，合理安排装运，使货机本次飞行获利最大2020/12/3114.1 4.1 线性规划方法建模线性规划方法建模 表4-1 三个货仓装载货物的最大容许重量和体积 前仓中仓后仓重量限制（吨）10168体积限制（立方米）680087005300表4-2 四类货物的装运数据 重量（吨）空间（立方米/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物41239028502020/12/3124.1 4.1 线性规划方法建模线性规划方法建模2020/12/3134.1 4.1 线性规划方法建模线性规划方法建模问题的最优结果为：第1个货舱装第2种货物10吨；第2个货舱装第3种货物12.79412吨；第3个货舱装第2种货物5吨，第3种货物2.794118吨；最大获利为111558.8元 2020/12/3144.1 4.1 线性规划方法建模线性规划方法建模例如4 动物饲料制造问题 某饲料公司要消费两种类型的动物饲料：粉状饲料和颗粒饲料消费这些饲料需要的原料为：燕麦，玉米和糖渣消费过程中，首先需要将燕麦和玉米磨碎，然后将所有原料混合形成饲料产品，最后将半成品制成颗粒状或粉末状，从而得到最终产品 每种饲料产品都需要满足规定的营养需求，见表4-3每天各种原料的可用量也有限制，其限定值及原料的价格见表4-4加工饲料的各道工序的本钱见表4-5 假如每天需求量为9吨颗粒饲料，12吨粉状饲料，那么各种原材料应分别使用多少，并应怎样混合才能使得总本钱最低2020/12/3154.1 4.1 线性规划方法建模线性规划方法建模表4-3 营养成分含量百分比 原料蛋白质脂肪纤维素燕麦玉米糖渣13.64.157.12.40.373.725要求含量9.52 6表4-4 原材料可用量与价格原料可用量（千克）价格（元/千克）燕麦玉米糖渣11900235007500.130.170.12表4-5 加工本钱元/千克磨碎混合结粒筛粉0.250.050.420.172020/12/3164.1 4.1 线性规划方法建模线性规划方法建模2020/12/3174.1 4.1 线性规划方法建模线性规划方法建模问题的最优结果为：消费9吨颗粒状饲料需要燕麦288.8889千克，玉米8711.1111千克，糖渣0千克；消费12吨粉状饲料需要燕麦11611.11千克，玉米0千克，糖渣388.8889千克 所需的最低本钱为15097.33元2020/12/3184.1 4.1 线性规划方法建模线性规划方法建模例如5 自行车消费规划问题 某公司消费自行车，表4-6给出了明年各月预期的销售量此公司的月消费才能为3千辆，通过工人加班，可以将产量进步50%，但是会将每辆自行车的消费本钱从30元进步到40元 当前自行车的库存量为2千辆，对库存中的每辆自行车，每个月月底都需支出5元的存储费用，假定此公司的库存才能是无限的 如今是1月1日，在下面的12个月里应消费和存储多少辆自行车才可以满足此销售预期，并使得总本钱最少？2020/12/3194.1 4.1 线性规划方法建模线性规划方法建模表4-6：明年的销售预期千辆 1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月30 15 15 25 33 40 45 45 26 14 25 302020/12/3204.1 4.1 线性规划方法建模线性规划方法建模 问题的最优结果见表4-7消费和库存的最小总本钱为1064500元。表4-7 自行车消费规划最优结果表千辆 月份 1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月预期需求 30 15 15 25 33 40 45 45 26 14 25 30正常生产 28 15 15 28 30 30 30 30 26 14 25 30加班生产 0 0 0 0 0 10 15 15 0 0 0 0仓库存储 0 0 0 4 0 0 0 0 0 0 0 02020/12/3214.1 4.1 线性规划方法建模线性规划方法建模例如例如6 6 体育馆建立问题体育馆建立问题 某市政府打算修建一个小型体育馆通过竞标，一家建筑公司获得了此合同表4-8列出了工程的主要任务，需时均以星期计有些任务只有在某些其他任务完成之后才能进展 1试给出各项任务的施工次序，使得这项工程能尽早完成 2市政府希望可以再提早一些时间完工为此，市政府决定工期每缩短一周，便向此公司支付30千元的奖励为缩短工期，建筑公司每周需要支付额外费用，见表4-8第5列问如何施工才能使得建筑公司的利润最大2020/12/3224.1 4.1 线性规划方法建模线性规划方法建模表4-8 体育馆施工数据表任务 描述 耗时 先决任务 最大缩短时间 每周额外开支1 工地布置 2 没有 0 2 场地平整 16 1 3 303 打地基 9 2 1 264 通路及其它道路网络 8 2 2 12 5 底层施工 10 3 2 176 主场地施工 6 4，5 1 157 划分更衣室 2 4 1 8 8 看台电器布置 2 6 0 9 顶部施工 9 4，6 2 42 10 照明系统 5 4 1 21 11 安装阶梯看台 3 6 1 1812 封顶 2 9 0 13 更衣室 1 7 0 14 建造售票处 7 2 2 22 15 第二通路 4 4，14 2 12 16 信号设施 3 8，11，14 1 617 草坪与附属运动设施 9 12 3 16 18 交付使用 1 17 0 2020/12/3234.1 4.1 线性规划方法建模线性规划方法建模问题1的数学模型：2020/12/3244.1 4.1 线性规划方法建模线性规划方法建模 问题的最优解，即各个任务的开工周次为:0，2，18，29，27，37，37，44，43，37，43，52，39，30，37，46，54，63，相应各个任务的完工周次为：2，18，27，37，37，43，39，46，52，42，46，54，40，37，41，49，63，64最优施工时间安排图，见图4.1其中横坐标为施工周次，纵坐标为施工工程，最早完工时间为第64周 图4.1 问题1的最优施工时间安排图 2020/12/3254.1 4.1 线性规划方法建模线性规划方法建模问题2的数学模型：2020/12/3264.1 4.1 线性规划方法建模线性规划方法建模 问题的最优解，即各个任务的开工周次为:0，2，18，18，26，34，26，39，39，26，39，48，28，19，26，42，50，56；相应各个任务的完工周次为：2,18,26,26,34,39,28,41,48,31,42,50,29,26,30,45,56,57；较原先施工方案共计提早了7周；各个任务实际缩短的周次为：0，0，1，0，2，1，0，0，0，0，0，0，0，0，0，0，3，0最优施工时间安排图，见图4.2其中横坐标为施工周次，纵坐标为施工工程，建筑公司最多可获益87千元 图4.2 问题2的最优施工时间安排图 2020/12/3274.1 4.1 线性规划方法建模线性规划方法建模例如7 农作物种植问题 某农场有625亩的土地可以用来种植农作物可以种植的农作物有玉米、小麦和高粱预计有1000亩-尺的灌溉用水可用，农场农民每周可以投入的时间为300小时这三种农作物每亩的收益分别为400元，200元和250元每亩农作物所需的资源见表4-9试确定各种农作物的种植量，使得农场的获益最大进一步讨论以下3个问题：1假设用50元可以买到1亩-尺的灌溉用水，应否做此项投资？假设投资最多每周购置多少亩-尺的灌溉用水？2假设可以购置土地增加种植面积，购置1亩土地的费用最多是多少元？3由于市场需求变化，每亩高粱的获利增加到300元，应否改变消费方案？2020/12/3284.1 4.1 线性规划方法建模线性规划方法建模表4-9 农场每亩农作物所需的资源数据 所需资源（每亩）玉米 小麦 高粱灌溉用水（亩-尺）3.0 1.0 1.5劳动时间（小时/周）0.8 0.2 0.32020/12/3294.1 4.1 线性规划方法建模线性规划方法建模线性规划模型：问题的最优方案为：种植玉米41.6667亩，种植小麦0亩，种植高粱583.3333亩，最大收益为162500元2020/12/3304.1 4.1 线性规划方法建模线性规划方法建模 对Lingo模型进展灵敏度分析可得下面报告：1土地和灌溉用水这两种资源全部用完，而劳动时间这种资源还剩余91.6667；2土地、灌溉用水和劳动时间的影子价格分别为100元、100元和0元，即增加1个单位的土地量、灌溉用水量和劳动时间，总收益会分别增加100元、100元和0元3最优解不变条件下目的函数系数的变化范围分别为250,400、0,200和250,400，即当每亩玉米的收益在250,400，每亩小麦的收益在0,200，每亩高粱的收益在250,400变化时，不需要改变消费方案4土地、灌溉用水和劳动时间这三种资源影子价格有意义条件下约束右端的限制范围分别为333.3333,666.6667、937.5,1275和208.3333,，要保证前面给定的影子价格有意义，土地量、灌溉用水量和劳动时间只能在上述范围内取值2020/12/3314.1 4.1 线性规划方法建模线性规划方法建模 根据上述报告可以答复前面的三个问题：问题1应该做此项投资，假设投资每周最多1275购置亩-尺的灌溉用水；问题2可以购置土地，购置1亩土地的费用最多是100元；问题3每亩高粱的获利为300元时，仍小于其变化上限400元，所以不需要改变消费方案 2020/12/3324.1 4.1 线性规划方法建模线性规划方法建模4.1.5 课后练习 1某公司承诺为某建立工程从2003年起的4年中每年初分别提供以下数额贷款：2003年100万，2004年150万，2005年120万，2006年110万贷款资金需于2002年底前筹集齐为了充分发挥这笔资金的作用，在满足每年贷款额情况下，可将多余资金分别用于以下投资工程：1于2003年初购置A种债券，期限3年，到期后本息合计为投资额的140，但限购60万；2于2003年初购置B种债券，期限2年，到期后本息合计为投资额的125，且限购90万；3于2004年初购置C种债券，期限2年，到期后本息合计为投资额的130，且限购50万；4于每年初将任意数额的资金存放于银行，年息4，于每年底取出问此公司如何运用这笔筹集到的资金满足贷款要求，并使得2002年底筹集到的资金数额最少2020/12/3334.2 4.2 整数规划方法建模整数规划方法建模4.2.1 4.2.1 整数规划方法简介整数规划方法简介线性整数规划、纯整数规划、混合整数规划、0-1规划 2020/12/3344.2 4.2 整数规划方法建模整数规划方法建模整数规划方法建模需要的一些特殊变量：0-1变量：定义变量的取值要么为0，要么为1。部分整数变量：定义变量假如其值小于用户指定的限制L，那么其取值必须为整数值；否那么可取任意值。半连续变量：定义变量的取值要么为0，要么位于某限定范围内。半连续整数变量：定义变量的取值要么为0，要么位于某限定范围内的整数值。2020/12/3354.2 4.2 整数规划方法建模整数规划方法建模4.2.2 4.2.2 整数规划方法建模的根本技巧整数规划方法建模的根本技巧处理是/否逻辑问题 问题只有两种选择，要么做某件事，要么不做某件事对此可以借助0-1变量来处理。处理逻辑条件问题 问题有一组工程，不妨记为A，B，C，D，E，F，G，和H，每个工程都可以选择做还是不做，可借助0-1变量加以处理。详细问题要求不同，处理的方式也不一样，常见的情况如下：1.在多个选项中进展选择 2020/12/3364.2 4.2 整数规划方法建模整数规划方法建模如“这些工程中至多项选择一个：再如，“选且仅能选择二个工程：2020/12/3374.2 4.2 整数规划方法建模整数规划方法建模2.简单蕴含式 比方“假如选择工程A，那么必须也选择工程B：再如“假如选择工程A，那么不能选择工程B：再如“假如不选择工程A，那么必须选择工程B：2020/12/3384.2 4.2 整数规划方法建模整数规划方法建模3.含有三个变量的蕴涵式 如“假如选择工程A，那么必须也选择工程B和工程C:再如“假如选择工程A，那么必须也选择工程B或工程C:“假如同时选择工程B和工程C，那么必须选择工程A:2020/12/3394.2 4.2 整数规划方法建模整数规划方法建模4.一般蕴涵式 比方“假如选择工程B，C,D和E中的两个或两个以上，那么必须也选择A:处理0-1变量乘积问题 对式 ，可用借助下面三个不等式将其线性化 2020/12/3404.2 4.2 整数规划方法建模整数规划方法建模 对乘积等式约束 ,可利用下面四个不等式约束将其线性化 处理“或约束问题 比方下面问题:2020/12/3414.2 4.2 整数规划方法建模整数规划方法建模 定义0-1变量 ,表示采用第1个约束条件，否那么采用第2个约束条件 处理半连续整数变量问题 如某自行车厂采用流水线作业消费某种自行车，对这种自行车，要么不消费，要消费要求至少消费1500辆。2020/12/3424.2 4.2 整数规划方法建模整数规划方法建模处理固定本钱问题 如某手机消费厂打算消费一种新型的手机，假如消费那么需要投资固定本钱10万元，假如不消费，那么此项本钱为0。引入0-1辅助变量 ，表示消费此种手机，否那么为0。2020/12/3434.2 4.2 整数规划方法建模整数规划方法建模处理0-1变量和实数变量的乘积问题 用整数规划方法建模时，有时会遇到实数变量和0-1变量相乘的问题如 ，其中 为0-1变量，可用下面不等式将其线性化 处理“或约束问题 数学规划中的约束条件一般都是必须同时满足，但有时对其中的某两个约束条件只须满足一个即可，比方 2020/12/3444.2 4.2 整数规划方法建模整数规划方法建模 定义0-1变量 ，令 表示采用第1个约束条件，采用第2个条件，那么取值为0 2020/12/3454.2 4.2 整数规划方法建模整数规划方法建模处理半连续整数变量问题 如某自行车厂采用流水线作业消费某种自行车，对这种自行车，要么不消费，要消费要求至少消费1500辆定义变量 表示消费这种自行车的辆数，那么显然 为半连续整数变量.定义0-1变量 ，那么有 处理固定本钱问题 如某手机消费厂打算消费一种新型的手机，假如消费那么需要投资固定本钱10万元，假如不消费，那么此项本钱为0记 表示消费此种新型手机的个数，表示投资固定资产的费用，2020/12/3464.2 4.2 整数规划方法建模整数规划方法建模引入0-1辅助变量 表示消费此种手机，否那么为0，那么 处理0-1变量和实数变量的乘积问题 如 为实数变量，而 为0-1变量，且有 ，那么 2020/12/3474.2 4.2 整数规划方法建模整数规划方法建模4.2.3 4.2.3 整数规划方法的整数规划方法的LingoLingo软件实现软件实现例例 用Lingo软件求解整数规划2020/12/3484.2 4.2 整数规划方法建模整数规划方法建模解：在Lingo指令窗中输入下面指令：model:sets:row/1.2/:b;col/1.2/:c,x;matrix(row,col):A;endsetsmax=sum(col:c*x);for(col:gin(x);for(row(i):sum(col(j):A(i,j)*x(j)=b(i);data:c=1,1;b=1,4;A=-1,1,3,1;enddataend2020/12/3494.2 4.2 整数规划方法建模整数规划方法建模4.2.4 4.2.4 整数规划方法建模例如整数规划方法建模例如例如例如1 1 指派问题指派问题 有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R现有甲、乙、丙、丁、戊五人，他们将中文说明书翻译成不同语种的说明书所需的时间见表4-15请从这五人中指派四人完成这项工作，使得所需的总时间最少2020/12/3504.2 4.2 整数规划方法建模整数规划方法建模表4-15 各人对每项任务所需时间表 语种EJGR甲乙丙丁戊2109751541486131416111241513972020/12/3514.2 4.2 整数规划方法建模整数规划方法建模建立指派问题的数学模型如下：问题的最优解为:，其余变量为0，最优值为24，即甲翻译俄文，乙翻译日文，丁翻译德文，戊翻译英文所需的总时间最少，为24小时 2020/12/3524.2 4.2 整数规划方法建模整数规划方法建模例如2 汽车厂消费方案问题 某汽车厂消费小、中、大三种类型的汽车，各类型每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量如表4-16所示由于条件限制，规定假如消费某一类型的汽车，那么至少要消费80辆，试制定月消费方案，使工厂的利润最大表4-16 汽车厂相关数据表小型 中型 大型现有量钢材（吨）1.5 3 5600劳动时间（小时）280 250 40060000利润（万元）2 3 42020/12/3534.2 4.2 整数规划方法建模整数规划方法建模 问题的最优解为:,即消费小型汽车80辆，中型汽车150辆，大型汽车0辆，工厂获得的最大利润为610万元 2020/12/3544.2 4.2 整数规划方法建模整数规划方法建模例如3 露天采矿问题 某地发现了一个露天铀矿根据探测钻探的结果，发现这个矿可以分为假设干个可开采区矿坑需要挖掘成阶梯形，以方便卡车开到矿坑底部铀矿呈东西方向分布，如图4.3所示铀矿确定有18个可开采区，呈三层分布为挖掘一个可开采区，首先需要掘开它上方的三个区：正上方的区，左上方的区和右上方的区 挖第一层的区块每吨需要消耗100元，挖的第二层每吨需要消耗200元，挖第三层每吨需要消耗300元假如区块是由含有很多石英的石头组成斜线区域，那么每吨需要多消耗1000元只有灰色显示的区才含有铀即1，7，10，12，17，18区其市场价值分别为200，300，500，1000,1200和1400元/吨第18区，尽管也含有大量矿石，但也同时含有大量非常硬的石头为使总收益到达最大，应挖掘哪些矿区?2020/12/3554.2 4.2 整数规划方法建模整数规划方法建模123456789101112131415161718第1层第2层第3层图4.3：露天矿山构造图2020/12/3564.2 4.2 整数规划方法建模整数规划方法建模问题的最优解为:，其余变量为0，最大收益为1400即挖掘矿区1，2，3，4，5，6，7，10，11，12，13，17可使得总收益到达最大2020/12/3574.2 4.2 整数规划方法建模整数规划方法建模例如4 蔗糖消费问题 在澳大利亚，甘蔗的收割已经实现了高度机械化甘蔗在砍下之后将马上通过运行于小型铁路网上的货车运送到蔗糖厂一辆货车的运量可以消费的蔗糖量取决于甘蔗收购的地点以及甘蔗成熟的程度在收割之后，甘蔗中的含糖量由于发酵而迅速下降，一段时间之后，所含糖份将完全流失如今有11辆货车到达了蔗糖厂，每辆货车运载的甘蔗量都一样对每辆货车每小时的损失量以及剩余时间测量的数据见表4-17：表4-17：每车甘蔗属性货车编号 1 2 3 4 5 6 7 8 9 10 11损失率（千克/小时）43 26 37 28 13 54 62 49 19 28 30剩余时间 8 8 2 8 4 8 8 8 8 8 8 2020/12/3584.2 4.2 整数规划方法建模整数规划方法建模 在蔗糖厂有三条消费线，每辆货车都可以选择在哪条消费线上进展加工一车甘蔗的加工时间为两个小时必须在这车甘蔗的质量寿命完毕之前完成加工蔗糖厂的经理希望找出一个消费方案，使总的蔗糖损失降到最低2020/12/3594.2 4.2 整数规划方法建模整数规划方法建模 问题的最优解为:,其余变量为0，各个货车蔗糖的损失量(单位：千克)分别为：172，208，74，168，52，108，124，196，152，168，180，蔗糖的最小总损失量为1602千克于是得问题的最优加工方案见表4-18 表4-18 最优加工方案表 时间段1 时间段2 时间段3 时间段4货车3 货车1 货车4 货车2货车6 货车5 货车10 货车9货车7 货车8 货车11 2020/12/3604.2 4.2 整数规划方法建模整数规划方法建模例如5 文件备份问题 某公司希望将一些重要的文件备份到软盘上每张空白软盘的容量是1.44MB一共需要备份16个文件，其大小(单位：KB)分别为：46，55，62，87，108，114，137，164，253,364,372,388,406,432,461和851 假定无法使用压缩文件，但软盘的数量足够，问如何备份这些文件才能使得使用的软盘数目最少？2020/12/3614.2 4.2 整数规划方法建模整数规划方法建模文件备份问题的数学模型：问题的最优分配方案:软盘 文件大小（KB）使用空间（MB）1 46,62,87,137,364,372,388 1.42192 108,406,432,461 1.37403 55,114,164,253,851 1.40032020/12/3624.2 4.2 整数规划方法建模整数规划方法建模例如6 钢管切割问题 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19m 1现有一客户需要50根4m，20根6m和15根8m的钢管，应如何下料最节省？2零售商假如采用不同切割形式太多，将会导致消费过程的复杂化，从而增加消费和管理本钱，所以该零售商规定采用不同的切割形式不能超过3种此外，该客户除需要1中的三种钢管外，还需要10根5m的钢管，应如何下料最省？2020/12/3634.2 4.2 整数规划方法建模整数规划方法建模表4-20 钢管的合理切割形式表模式1模式2模式3模式4模式5模式6模式74m钢管根数43211006m钢管根数01021308m钢管根数0010102问题1的数学模型：2020/12/3644.2 4.2 整数规划方法建模整数规划方法建模 结果：按照形式1切割5根原料钢管，按照形式2切割5根原料钢管，按照形式5切割15根原料钢管，最少需要切割25根原料钢管 问题2的数学模型：2020/12/3654.2 4.2 整数规划方法建模整数规划方法建模 运行得切割所需的形式分别为：形式1，将原料钢管切割成4m钢管3根，5m钢管0根，6m钢管1根，8m钢管0根；形式2，将原料钢管切割成4m钢管0根，5m钢管0根，6m钢管0根，8m钢管2根；形式3，将原料钢管切割成4m钢管2根，5m钢管1根，6m钢管1根，8m钢管0根最少需要切割19m的原料钢管28根模型结果：2020/12/3664.2 4.2 整数规划方法建模整数规划方法建模例如7 仓库位置设置 某公司希望开设一些新仓库，向销售中心供货每开设一个新仓库都有一些固定费用货物将从仓库运输到附近的销售中心，每次运输的运费取决于运输的间隔 目前有12个位置可以建造新仓库，这些仓库可以向12个销售中心供货表4-21给出了每个仓库完全满足每个客户销售中心需求所需的总本钱单位：元，假如无法进展送货，取对应的本钱为100000 此外，每个仓库的固定建立费用和仓库的容量上限见表4-22仓库在任何时候都要保证满足客户需求，每个客户的需求量见表4-23 问此公司应在哪些位置创办仓库才能使得建立本钱和运输本钱的总费用最低？2020/12/3674.2 4.2 整数规划方法建模整数规划方法建模表4-21 完全满足客户需求所需的运输总本钱客户1 客户2 客户3 客户4 客户5 客户6 客户7 客户8 客户9 客户10 客户11 客户12仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8仓库9仓库10仓库11仓库12100 80 50 50 60 100 120 90 60 70 65 110120 90 60 70 65 110 140 110 80 80 75 130 140 110 80 80 75 130 160 125 100 100 80 150160 125 100 100 80 150 190 150 130 100000 100000 100000190 150 130 100000 100000 100000 200 180 150 100000 100000 100000200 180 150 100000 100000 100000 100 80 50 50 60 100100 80 50 50 60 100 120 90 60 70 65 110120 90 60 70 65 110 140 110 80 80 75 130140 110 80 80 75 130 160 125 100 100 80 150160 125 100 100 80 150 190 150 130 100000 100000 100000190 150 130 100000 100000 100000 200 180 150 100000 100000 100000200 180 150 100000 100000 100000 100 80 50 50 60 1002020/12/3684.2 4.2 整数规划方法建模整数规划方法建模表4-22 仓库的固定建立费用和仓库的容量上限表仓库 1 2 3 4 5 6 7 8 9 10 11 12固定建设费用 3500 9000 10000 4000 3000 9000 9000 3000 4000 10000 9000 35000容量上限 300 250 100 180 275 300 200 220 270 250 230 180表4-23 客户的货物需求量表客户 1 2 3 4 5 6 7 8 9 10 11 12需求量 120 80 75 100 110 100 90 60 30 150 95 1202020/12/3694.2 4.2 整数规划方法建模整数规划方法建模运行得最低总本钱为18713.19元，开设的仓库位置分别为：1，4，5，8，9，开设仓库的总费用为17500元，运输的总费用为1213.194元相应的最优运输方案见表4-242020/12/3704.2 4.2 整数规划方法建模整数规划方法建模表4-24 最优运输方案表 客户1 客户2 客户3 客户4 客户5 客户6 客户7 客户8 客户9 客户10 客户11 客户12仓库1仓库4仓库5仓库8仓库9 0 0 0 5 0 0 85 60 30 0 0 120 0 0 0 70 110 0 0 0 0 0 0 0120 35 0 0 0 0 5 0 0 0 0 0 0 45 75 0 0 100 0 0 0 0 0 0 0 0 0 25 0 0 0 0 0 150 95 02020/12/3714.2 4.2 整数规划方法建模整数规划方法建模例如8 求职面试问题 有4名同学到一家公司参加三个阶段的面试公司要求每个同学都必须首先找公司秘书初试，然后到主管部门复试，最后到经理处参加面试，并且不允许插队即在任何一个阶段4名同学的顺序是一样的由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表4-25所示单位：分钟 4名同学约定他们全部面试完以后一起分开公司假定如今时间是早晨8:00，问他们最早何时能分开公司 2020/12/3724.2 4.2 整数规划方法建模整数规划方法建模表4-25 四名同学各阶段的面试时间表秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁810152020/12/3734.2 4.2 整数规划方法建模整数规划方法建模求职面试问题的数学模型：2020/12/3744.2 4.2 整数规划方法建模整数规划方法建模表4-26 四名同学面试时间表秘书初试主管复试经理面试同学甲8:088:218:218:368:368:56同学乙8:218:318:368:568:569:14同学丙8:318:518:569:129:149:24同学丁8:008:088:118:218:218:362020/12/3754.2 4.2 整数规划方法建模整数规划方法建模2020/12/3764.2 4.2 整数规划方法建模整数规划方法建模2020/12/3774.2 4.2 整数规划方法建模整数规划方法建模2020/12/3784.2 4.2 整数规划方法建模整数规划方法建模2020/12/3794.2 4.2 整数规划方法建模整数规划方法建模2020/12/3804.2 4.2 整数规划方法建模整数规划方法建模2020/12/3814.2 4.2 整数规划方法建模整数规划方法建模2020/12/382模型：2020/12/383课堂练习课堂练习:p某钻井队要从以下十个可供选择的井位：中确定5个钻井探油。十个井位的钻探费用估计分别为 。且井位选择必须满足如下限制条件：p1或选择 和，或选择 ；p2在 三个井位最多只能选择一个；p3在 中最多只能选两个；p试建立数学模型使总的钻探费用为最小。2020/12/384课堂练习课堂练习:p混合泳接力队的选拔问题：某班准备从5名游泳队员中选择4人组成接力队，参加学校的4 100m混合泳接力比赛。5名队员4种泳姿的百米平均成绩如下表所示，问应如何选拔队员组成接力队？p假如最近队员丁的蛙泳成绩有较大退步，只有75.2秒;而队员戊经过艰辛训练自由泳成绩有所进步,到达57.5秒,组成接力队的方案是否应该调整?甲 乙 丙 丁 戊蝶泳（秒）66.8 57.2 78 70 67.4仰泳（秒）75.6 66 67.8 74.2 71蛙泳（秒）87 66.4 84.6 69.6 83.8自由泳（秒）58.6 53 59.4 57.2 62.42020/12/385例如例如4 4 选课策略选课策略p某学校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。这些课程的编号、名称、所属类别和先修课要求如表1所示。那么，毕业时学生最少可以学习这些课程中的哪些中的哪些课程。2020/12/386表 1 运筹学专业的课程属性表课程编号课程名称所属类别先修课要求1微积分数学2线性代数数学3最优化方法数学；运筹学微积分；线性代数4数据结构数学；计算机计算机编程5应用统计数学；运筹学微积分；线性代数6计算机模拟计算机；运筹学计算机编程7计算机编程计算机8预测理论运筹学应用统计9数学实验运筹学；计算机微积分；线性代数2020/12/387模型与结果：2020/12/3882020/12/389例如例如5 5 销售代理的开发与中断模型销售代理的开发与中断模型2020/12/390 某公司正在考虑在某城市开发一些销售代理业务。经过预测，该公司已经确定了该城市将来5年的业务量，分别为400，500，600，700和800。该公司已经初步物色了4家销售公司作为其代理候选企业，下表给出了该公司与每个候选企业建立代理关系的一次性费用万元，以及每个候选企业每年所能承揽的最大业务量和年运行费用万元。该公司应该与哪些候选企业建立代理关系。候选代理1 候选代理2 候选代理3 候选代理4年最大业务量 350 250 300 200一次性费用 100 80 90 70 年运行费用 7.5 4.0 6.5 3.0 2020/12/391模型与结果：，其它变量为0，最优值为313.5万元 2020/12/392假设该公司目前已经与上述4个代理建立了代理关系并且都处于运行状态，但每年初可以决定临时中断或重新恢复代理关系，每次临时中断或重新恢复代理关系的费用万元如下表所示。该公司应如何对这些代理进展业务调整？代理1 代理2 代理3 代理4临时中断费用 5 3 4 2重新恢复费用 5 4 1 92020/12/393模型与结果：，即公司应在第1年初临时中断与代理2和代理3的关系，而在第3年初重新恢复与代理2得代理关系。最小总费用为86.5万元。2020/12/394练习：汽车厂消费方案问题 p一汽车厂消费小、中、大三种类型的汽车，各类型每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量如下表所示。试制定月消费方案，使工厂的利润最大。由于条件限制，只能消费某一类型汽车，且至少要消费80辆，那么最优的消费方案应作如何改变。小型 中型 大型现有量钢材（吨）1.5 3 5600劳动时间（小时）280 250 400600