第四章 数学规划模型 4.1 奶制品的生产与销售4.2 自来水输送与货机装运4.3 汽车生产计划4.7 背包问题4.8 图与网络最短路径问题y数学规划模型 实际问题中 的优化模型x决策变量f(x)目标函数gi(x)0约束条件多元函数 条件极值 决策变量个数n和 约束条件个数m较大 最优解在可行域 的边界上取得 数 学 规 划线性规划 非线性规划 整数规划重点在模型的建立和结果的分析企业生产计划4.1 奶制品的生产与销售 空间层次工厂级：根据外部需求和内部设备、人力、原料等 条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费 用参数等，以最小成本为目标制订生产批量计划。时间层次若短时间内外部需求和内部资源等不随时间变化，可 制订单阶段生产计划，否则应制订多阶段生产计划。本节课题例1 加工奶制品的生产计划1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到 30元/公斤，应否改变生产计划？ 每天：1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利约束条件非负约束 线性 规划 模型 (LP)时间480小时 至多加工100公斤A1 50桶牛奶 每天模型分析与假设 比 例 性 可 加 性 连续性 xi对目标函数的“贡 献”与xi取值成正比 xi对约束条件的“贡 献”与xi取值成正比 xi对目标函数的“贡 献”与xj取值无关 xi对约束条件的“贡 献”与xj取值无关 xi取值连续 A1,A2每公斤的获利是与各 自产量无关的常数每桶牛奶加工出A1,A2的数量和 时间是与各自产量无关的常数A1,A2每公斤的获利是与相 互产量无关的常数每桶牛奶加工出A1,A2的数量和 时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数 线性规划模型模型求解 图解法 x1x20ABCDl1l2l3l4l5约 束 条 件目标 函数 Z=0Z=2400Z=3600z=c (常数) 等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 最优解一定在凸多边 形的某个顶点取得。 模型求解 软件实现 LINDO 6.1 max 72x1+64x2st2）x1+x2 总需求量(300)每个水库最大供水量都提高一倍利润 = 收入(900) 其它费用(450) 引水管理费利润(元/千吨)甲乙丙丁 A290320230280 B310320260300 C260250220/供应 限制B, C 类似处理问题讨论 确定送水方案使利润最大需求约束可以不变求解OBJECTIVE FUNCTION VALUE1) 88700.00VARIABLE VALUE REDUCED COSTX11 0.000000 20.000000X12 100.000000 0.000000X13 0.000000 40.000000X14 0.000000 20.000000X21 30.000000 0.000000X22 40.000000 0.000000X23 0.000000 10.000000X24 50.000000 0.000000X31 50.000000 0.000000X32 0.000000 20.000000X33 30.000000 0.000000 这类问题一般称为 “运输问题” (Transportation Problem)总利润 88700（元） A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030如何装运， 使本次飞行 获利最大？ 三个货舱最大载重(吨),最大容积(米3) 例2 货机装运重量（吨 ）空间( 米3/ 吨）利润（元/ 吨） 货物1184803100货物2156503800货物3235803500货物4123902850三个货舱中实际载重必须与其最大载重成比例 前仓：10；6800中仓：16；8700后仓：8；5300 飞机平衡决策 变量 xij-第i 种货物装入第j 个货舱的重量(吨）i=1,2,3,4, j=1,2,3 (分别代表前、中、后仓)模型假设 每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙； 模型建立 货舱 容积 目标 函数( 利润)约束 条件货机装运模型建立 货舱 重量 10； 680016； 87008； 5300xij-第i 种货物装入第j 个货舱的重量约束 条件平衡 要求 货物 供应 货机装运模型建立 10； 680016； 87008； 5300xij-第i 种货物装入第j 个货舱的重量OBJECTIVE FUNCTION VALUE1) 121515.8VARIABLE VALUE REDUCED COSTX11 0.000000 400.000000X12 0.000000 57.894737X13 0.000000 400.000000X21 10.000000 0.000000X22 0.000000 239.473679X23 5.000000 0.000000X31 0.000000 0.000000X32 12.947369 0.000000X33 3.000000 0.000000X41 0.000000 650.000000X42 3.052632 0.000000X43 0.000000 650.000000 货物2：前仓10,后仓5； 货物3: 中仓13, 后仓3； 货物4: 中仓3。货机装运模型求解 最大利润约121516元货物供应点 货舱需求点平衡要求运输 问题运输问题的扩展 如果生产某一类型汽车，则至少要生产80辆， 那么最优的生产计划应作何改变？例1 汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车对钢 材、劳动时间的需求，利润及工厂每月的现有量。 小型 中型 大型 现有量钢材（吨） 1.5 3 5 600劳动时间（小时） 280 250 400 60000利润（万元） 2 3 4 制订月生产计划，使工厂的利润最大。4.3 汽车生产与原油采购设每月生产小、中、大型 汽车的数量分别为x1, x2, x3汽车厂生产计划 模型建立 小型 中型 大型 现有量钢材 1.5 3 5 600时间 280 250 400 60000利润 2 3 4 线性 规划 模型 (LP)模型 求解 3） 模型中增加条件：x1, x2, x3 均为整数，重新求解。 OBJECTIVE FUNCTION VALUE1) 632.2581 VARIABLE VALUE REDUCED COSTX1 64.516129 0.000000X2 167.741928 0.000000X3 0.000000 0.946237ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 0.7311833) 0.000000 0.003226结果为小数， 怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与 LP最优值632.2581相差不大。 2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数 值z，通过比较可能得到更优的解。 但必须检验它们是否满足约束条件。为什么？IP可用LINDO直接求解整数规划(Integer Programming,简记IP)“gin 3”表示“前3个变量 为整数”，等价于： gin x1 gin x2 gin x3 IP 的最优解x1=64，x2=168，x3=0，最优值z=632 max 2x1+3x2+4x3 st 1.5x1+3x2+5x3600 280x1+250x2+400x360000 end gin 3 OBJECTIVE FUNCTION VALUE1) 632.0000 VARIABLE VALUE REDUCED COSTX1 64.000000 -2.000000X2 168.000000 -3.000000X3 0.000000 -4.000000 模型求解 IP 结果输出其中3个子模型应去掉，然后逐一求解，比较目标函数值， 再加上整数约束，得最优解：方法1：分解为8个LP子模型 汽车厂生产计划 若生产某类汽车，则至少生产80辆，求生产计划。x1,x2, x3=0 或 80x1=80，x2= 150，x3=0，最优值z=610LINDO中对0- 1变量的限定： int y1 int y2 int y3 方法2：引入0-1变量，化为整数规划 M为大的正数 ，可取1000 OBJECTIVE FUNCTION VALUE1) 610.0000 VARIABLE VALUE REDUCED COSTX1 80.000000 -2.000000X2 150.000000 -3.000000X3 0.000000 -4.000000Y1 1.000