GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 数学规划模型（6课时） §1、生产安排问题及基本概念 §2、 奶制品的生产与销售 §3、自来水输送与货机装运 数学建模 Mathematical Models 广东工贸职业技术学院 1 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 生产安排问题及基本概念 ［问题的提出］某工厂生产甲、乙两种产品,生产每件产品需要原材料、能源消耗、劳动力及所获利润如下表所示：现有库存原材料1400千克；能源消耗总额不超过2400百元；全厂劳动力满员为2000人.试安排生产任务（生产甲、乙产品各多少件）,使获得利润最大,并求出最大利润. 品种 原材料（千克) 能源消耗（百元) 劳动力(人) 利润(千元) 甲 2 1 4 5 乙 3 6 数学建模 Mathematical Models 广东工贸职业技术学院 2 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE ［模型的建立］(整数线性规划问题) 设安排生产甲产品件,乙产品件,相应的利润为,则此问题的数学模型为: . 数学建模 Mathematical Models 广东工贸职业技术学院 3 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE ［模型的求解］ 方法一：图解法 可行域为：由直线 组成的凸五边形区域. 直线 在此凸五边形区域内平行移动. 易知：当过 与 的交点时, 取最大值. 数学建模 Mathematical Models 广东工贸职业技术学院 4 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE ［模型的求解］ 方法二：用Lindo软件或Maple软件求解. 数学建模 Mathematical Models 广东工贸职业技术学院 5 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE ［数学规划的若干基本概念］ 数学规划问题 数学规划问题由目标函数、约束条件、决策变量构成； 线性规划，非线性规划 可行解，可行域；最优解，最优值. 结论一： 线性规划若存在可行域,则可行域为凸集； 结论二：若可行域有界,则最优解在可行域的顶点达到. 数学建模 Mathematical Models 广东工贸职业技术学院 6 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 例2 彩电生产问题 设安排生产甲型彩电 件,乙型彩电 件，相应的利润为S.则此问题的数学模型为： max S=3x +2y 解法一: 用图解法进行求解 解法二：用Lindo软件 、 Maple软件 求解. 数学建模 Mathematical Models 广东工贸职业技术学院 8 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 作业： 某厂生产甲、乙两种产品,一件甲产品用原料1千克, 原料5千克；一件乙产品用原料2千克, 原料4千克.现有原料20千克, 原料70千克.甲、乙产品每件售价分别为20元和30元.问如何安排生产使收入最大？ 数学建模 Mathematical Models 广东工贸职业技术学院 9 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE §2、加工奶制品的生产计划(例1) 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 每天： 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到 30元/公斤，应否改变生产计划？ 数学建模 Mathematical Models 广东工贸职业技术学院 10 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 50桶牛奶 每天 时间480小时 至多加工100公斤A1 决策变量 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 24×3x1 获利 16×4 x2 目标函数 每天获利 线性规划模型(LP) 原料供应 劳动时间 约束条件 加工能力 非负约束 数学建模 Mathematical Models 广东工贸职业技术学院 11 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 模型求解 图解法 x1 x2 A B C D 约束条件 l1 l2 l3 l4 l5 Z=3600 Z=2400 c Z=0 目标函数 z=c (常数) ~等值线 在B(20,30)点得到最优解 目标函数和约束条件是线性函数 最优解一定在凸多边形的某个顶点取得。 可行域为直线段围成的凸多边形 目标函数的等值线为直线 数学建模 Mathematical Models 广东工贸职业技术学院 12 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 模型求解 软件实现 LINDO 6.1 max 72x1+64x2 st 2）x1+x2<50 3）12x1+8x2<480 4）3x1<100 end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2 DO RANGE (SENSITIVITY) ANALYSIS? No 20桶牛奶生产A1, 30桶生产A2，利润3360元。 数学建模 Mathematical Models 广东工贸职业技术学院 13 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 结果解释 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2 max 72x1+64x2 st 2）x1+x2<50 3）12x1+8x2<480 4）3x1<100 end 三种资源 原料无剩余 时间无剩余 加工能力剩余40 “资源” 剩余为零的约束为紧约束（有效约束） 数学建模 Mathematical Models 广东工贸职业技术学院 14 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

结果解释 影子价格 35元可买到1桶牛奶，要买吗？ 35 <48, 应该买！ 聘用临时工人付出的工资最多每小时几元？ 2元！ OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2 结果解释 最优解下“资源”增加1单位时“效益”的增量 影子价格 原料增加1单位, 利润增长48 时间增加1单位, 利润增长2 加工能力增长不影响利润 35元可买到1桶牛奶，要买吗？ 35 <48, 应该买！ 聘用临时工人付出的工资最多每小时几元？ 2元！ 数学建模 Mathematical Models 广东工贸职业技术学院 15 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE DO RANGE(SENSITIVITY) ANALYSIS? Yes 最优解不变时目标函数系数允许变化范围 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000 (约束条件不变) x1系数范围(64,96) x2系数范围(48,72) x1系数由24 3=72增加为303=90，在允许范围内 A1获利增加到 30元/千克，应否改变生产计划 不变！ 数学建模 Mathematical Models 广东工贸职业技术学院 16 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 结果解释 影子价格有意义时约束右端的允许变化范围 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000 (目标函数不变) 原料最多增加10 时间最多增加53 35元可买到1桶牛奶，每天最多买多少？ 最多买10桶! 数学建模 Mathematical Models 广东工贸职业技术学院 17 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 例2 奶制品的生产销售计划 在例1基础上深加工 1桶牛奶 3千克A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 0.8千克B1 2小时,3元 1千克 获利44元/千克 0.75千克B2 2小时,3元 1千克 获利32元/千克 50桶牛奶, 480小时 至多100公斤A1 制订生产计划，使每天净利润最大 30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？ B1，B2的获利经常有10%的波动，对计划有无影响？ 数学建模 Mathematical Models 广东工贸职业技术学院 18 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 1桶牛奶 3千克 A1 12小时 8小时 4千克 A2 或 获利24元/千克 获利16元/kg 0.8千克 B1 2小时,3元 1千克 获利44元/千克 0.75千克 B2 获利32元/千克 决策变量 出售x1 千克 A1, x2 千克 A2， X3千克 B1, x4千克 B2 x5千克 A1加工B1， x6千克 A2加工B2 目标函数 利润 原料供应 加工能力 约束条件 附加约束 劳动时间 非负约束 数学建模 Mathematical Models 广东工贸职业技术学院 19 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 模型求解 OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2 软件实现 LINDO 6.1 DO RANGE (SENSITIVITY) ANALYSIS? No 数学建模 Mathematical Models 广东工贸职业技术学院 20 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2 结果解释 每天销售168 千克A2和19.2 千克B1， 利润3460.8（元） 8桶牛奶加工成A1，42桶牛奶加工成A2， 将得到的24千克A1全部加工成B1 除加工能力外均为紧约束 数学建模 Mathematical Models 广东工贸职业技术学院 21 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？ 结果解释 OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 增加1桶牛奶使利润增长3.16×12=37.92 增加1小时时间使利润增长3.26 投资150元增加5桶牛奶，可赚回189.6元。（大于增加时间的利润增长） 数学建模 Mathematical Models 广东工贸职业技术学院 22 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

结果解释 B1,B2的获利有10%的波动，对计划有无影响 波动对计划有影响 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY …… …… DO RANGE (SENSITIVITY) ANALYSIS? Yes B1获利下降10%，超出 X3 系数允许范围 B2获利上升10%，超出 系数允许范围 波动对计划有影响 生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化。 数学建模 Mathematical Models 广东工贸职业技术学院 23 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE §3、 自来水输送与货机装运 运输问题 生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大； 各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。 数学建模 Mathematical Models 广东工贸职业技术学院 24 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 例1 自来水输送 【问题】 A：50 B：60 C：50 甲：30；50 乙：70；70 丙：10；20 丁：10；40 水库供水量(千吨) 小区基本用水量(千吨) 小区额外用水量(千吨) （以天计） 元/千吨 甲 乙 丙 丁 A 160 130 220 170 B 140 190 150 C 200 230 / 其他费用:450元/千吨 支出： 引水管理费 收入：900元/千吨 应如何分配水库供水量，公司才能获利最多？ 若水库供水量都提高一倍，公司利润可增加到多少？ 数学建模 Mathematical Models 广东工贸职业技术学院 25 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 【问题分析】 A：50 B：60 C：50 甲：30；50 乙：70；70 丙：10；20 丁：10；40 总供水量：160 < 总需求量：120+180=300 总收入900160=144,000(元) 收入：900元/千吨 其他费用:450元/千吨 支出∶ 引水管理费 其他支出450160=72,000(元) 确定送水方案使利润最大 使引水管理费最小 数学建模 Mathematical Models 广东工贸职业技术学院 26 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 【模型构成】 确定3个水库向4个小区的供水量 决策变量 水库i 向j 区的日供水量为 xij（x34=0） 目标函数 供应限制 线性规划模型(LP) 约束条件 需求限制 数学建模 Mathematical Models 广东工贸职业技术学院 27 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 【模型求解】 OBJECTIVE FUNCTION VALUE 1) 24400.00 VARIABLE VALUE REDUCED COST X11 0.000000 30.000000 X12 50.000000 0.000000 X13 0.000000 50.000000 X14 0.000000 20.000000 X21 0.000000 10.000000 X22 50.000000 0.000000 X23 0.000000 20.000000 X24 10.000000 0.000000 X31 40.000000 0.000000 X32 0.000000 10.000000 X33 10.000000 0.000000 A(50) B(60) C(50) 甲(30;50) 乙(70;70) 丙(10;20) 丁(10;40) 50 40 10 引水管理费 24400(元) 利润=总收入-其它费用-引水管理费=144000-72000-24400 = 47600（元） 数学建模 Mathematical Models 广东工贸职业技术学院 28 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 【问题讨论】 每个水库最大供水量都提高一倍 总供水量(320) > 总需求量(300) 确定送水方案使利润最大 利润 = 收入(900) –其它费用(450) –引水管理费 利润(元/千吨) 甲 乙 丙 丁 A 290 320 230 280 B 310 260 300 C 250 220 / 目标函数 供应限制 需求约束可以不变 B, C 类似处理 数学建模 Mathematical Models 广东工贸职业技术学院 29 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

这类问题一般称为“运输问题” (Transportation Problem) 【问题求解】 OBJECTIVE FUNCTION VALUE 1) 88700.00 VARIABLE VALUE REDUCED COST X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000 A(100) B(120) C(100) 甲(30;50) 乙(70;70) 丙(10;20) 丁(10;40) 40 100 50 30 总利润 88700（元） 这类问题一般称为“运输问题” (Transportation Problem) 数学建模 Mathematical Models 广东工贸职业技术学院 30 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 例2 货机装运 三个货舱最大载重(吨),最大容积(米3) 【问题】 前仓： 10；6800 中仓： 16；8700 后仓： 8；5300 三个货舱中实际载重必须与其最大载重成比例   重量（吨） 空间( 米3/吨） 利润（元/吨） 货物1 18 480 3100 货物2 15 650 3800 货物3 23 580 3500 货物4 12 390 2850 如何装运，使本次飞行获利最大？ 数学建模 Mathematical Models 广东工贸职业技术学院 31 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 【模型假设 】 每种货物可以分割到任意小； 每种货物可以在一个或多个货舱中任意分布； 多种货物可以混装，并保证不留空隙； 【模型建立】 xij--第i 种货物装入第j 个货舱的重量(吨） i=1,2,3,4, j=1,2,3 (分别代表前、中、后仓) 决策变量 xij--第i 种货物装入第j 个货舱的重量 目标函数(利润) 数学建模 Mathematical Models 广东工贸职业技术学院 32 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 【模型建立】 货舱重量 10；6800 16；8700 8；5300 约束条件 货舱容积 数学建模 Mathematical Models 广东工贸职业技术学院 33 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 【模型建立】 xij--第i 种货物装入第j 个货舱的重量 10；6800 16；8700 8；5300 平衡要求 约束条件 货物供应 数学建模 Mathematical Models 广东工贸职业技术学院 34 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE

GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE 【模型求解 】 货物2：前仓10,后仓5； 货物3: 中仓13, 后仓3；货物4: 中仓3。 OBJECTIVE FUNCTION VALUE 1) 121515.8 VARIABLE VALUE REDUCED COST X11 0.000000 400.000000 X12 0.000000 57.894737 X13 0.000000 400.000000 X21 10.000000 0.000000 X22 0.000000 239.473679 X23 5.000000 0.000000 X31 0.000000 0.000000 X32 12.947369 0.000000 X33 3.000000 0.000000 X41 0.000000 650.000000 X42 3.052632 0.000000 X43 0.000000 650.000000 最大利润约121516元 货物~供应点 货舱~需求点 运输问题 平衡要求 运输问题的扩展 数学建模 Mathematical Models 广东工贸职业技术学院 35 GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE