第四章、线性规划在工商管理中的应用 已经掌握： 1. 线性规划的图解法，对线性规划的求解及灵敏度分析的基本概念、基本原理；

Presentation on theme: "第四章、线性规划在工商管理中的应用 已经掌握： 1. 线性规划的图解法，对线性规划的求解及灵敏度分析的基本概念、基本原理；"— Presentation transcript:

1 第四章、线性规划在工商管理中的应用 已经掌握： 1. 线性规划的图解法，对线性规划的求解及灵敏度分析的基本概念、基本原理；
2. 掌握了用计算机软件求解线性规划问题及其灵敏度分析的方法。 马上学习： 研究线性规划在工商管理中的应用，解决工商管理中的实际问题。

2 主要内容 §4.1、人力资源分配的问题 §4.2、生产计划的问题 §4.3、套裁下料问题 §4.4、配料问题 §4.5、投资问题

3 某昼夜服务的公交线路每天各时间段内所 需司机和乘务人员数如下：
§4.1、人力资源分配的问题 某昼夜服务的公交线路每天各时间段内所 需司机和乘务人员数如下： 例1 班次 时间 所需人数 1 6:00-10:00 60 2 10:00-14:00 70 3 14:00-18:00 4 18:00-22:00 50 5 22:00-2:00 20 6 2:00-6:00 30 第i班 次需 要的 工作 人数 分析：应该设第 i班次开始工作的人数 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?

4 设xi表示第i班次时开始上班的人员数，在第i班需要的工作人数应包括：
解： 设xi表示第i班次时开始上班的人员数，在第i班需要的工作人数应包括： 第 i-1班次时开始上班的人员数 第i班次时开始上班的人员数 又要求这六个班次时开始上班的所有人员最少，即要求x1+x2+x3+x4+x5+x6最小，这样我们建立如下的数学模型。 目标函数： min x1+x2+x3+x4+x5+x6 约束条件： x1+x2≥70， x2+x3≥60， x3+x4≥50， x4+x5≥20，x5+x6≥30， x1+x6≥60， x1, x2, x3, x4, x5, x6≥0

5 重点： 学会建模 约束条件为何不取等号？ 将最优解带入第二个约束条件 20+50>60，取不到等号
用“管理运筹学”软件可以求得此问题的解：x1=50， x2=20，x3=50， x4=0， x5=20， x6=10， 24小时内一共需要司机和乘务人员150人。 约束条件为何不取等号？ 将最优解带入第二个约束条件 20+50>60，取不到等号 重点： 学会建模

6 福安商场是个中型的百货商场，它对售货 人员的需求经过统计分析如下所示：
§4.1、人力资源分配的问题 福安商场是个中型的百货商场，它对售货 人员的需求经过统计分析如下所示： 例2 星期一：15人；星期二：24人； 星期三：25人；星期四：19人； 星期五：31人；星期六：28人； 星期日：28人。 要求： 售货人员每周工作五天，休息两天， 要求休息的两天是连续的 问应该如何安排售货人员的作息，既满足了工作需要，又使配备的售货人员的人数最少?

7 法一 解：设x1为星期一开始休息的人数，x2为星期二开始休息的人数，…，x7为星期日开始休息的人数。目标是要求售货人员的总数最少。因为每个售货员都工作五天，休息两天，所以只要计算出连续休息两天的售货员人数，也就计算出了售货员的总数。把连续休息两天的售货员按照开始休息的时间分成7类，各类的人数分别为X1，X2，…X7，即有目标函数: min X1+X2+X3+X4+X5+X6+X7

8 模型： 喂！请问数学模型？

9 约束条件 x2 + x3 + x4 + x5 + x6 ≥ 15 （除去周日开始休息的和周一开始休息的人数）
（除去周一开始休息的和周二开始休息的人数） x4 + x5 + x6 + x7 + x1 ≥ 25 （除去周二开始休息的和周三开始休息的人数） x5 + x6 + x7 + x1 + x2 ≥ 19 （除去周三开始休息的和周四开始休息的人数） x6 + x7 + x1 + x2 + x3 ≥ 31 （除去周四开始休息的和周五开始休息的人数） x7 + x1 + x2 + x3 + x4 ≥ 28 （除去周五开始休息的和周六开始休息的人数） x1 + x2 + x3 + x4 + x5 ≥ 28 （除去周六开始休息的和周日开始休息的人数）

10 上机求解得：x1=12,x2=0,x3=11,x4=5,x5=0,x6=8,x7=0, 目标函数最小值=36
也就是说配备36个售货员，并安排 12人休息周一、二； 0人休息周二、三； 11 人休息周三、四； 5人休息周四、五； 0人休息周五、六； 8人休息周六、日； 0人休息周日、一。

11 设x1为星期一开始上班的人数，x2为星期二开始上班 的人数，…，x7为星期日开始上班的人数。目标是要 求售货人员的总数最少。
目标函数: min X1+X2+X3+X4+X5+X6+X7 约束条件：分析 星期一 上班人数： 一定不包含星期二开始上班的和星期三开始上班的人数， 则： X1+X4+X5+X6+X7 ≥15 星期二 ： X1+X2+X5+X6+X7 ≥24 星期三 ：X1+X2+X3+X6+X7 ≥25 星期四： X1+X2+X3+X4+X7 ≥19 星期五： X1+X2+X3+X4+X5≥31 星期六： X2+X3+X4+X5+X6≥28，星期日：X3+X4+X5+X6+X7 ≥28 法二 周日，周一休息 周一，周二休息

12 最优解： 函数值=36 x1=3,x2=5,x3=12,x4=0,x5=11,x6=0，X7=5, 周一开始上班的人数为8人
周二开始上班的人数为0人 周三开始上班的人数为12人 周四开始上班的人数为0人 周五开始上班的人数为11人 周六开始上班的人数为5人 周日开始上班的人数为0人

13 周1开始休息人数=周3开始上班人数 周2开始休息人数=周4开始上班人数 周3开始休息人数=周5开始上班人数 周4开始休息人数=周6开始上班人数 周5开始休息人数=周日开始上班人数 周6开始休息人数=周1开始上班人数 周日开始休息人数=周2开始上班人数

14 思考 服务业对人力资源的需求实际情况是：一周内像例 4-2所描述的那样变化，而每天的各时间段的需求又往往像例 4-1 描述的那样变化，在保证工作人员每天工作 8 h，每周休息两天的情况下，该如何安排使人员的编制最小呢？ 答案：先用例1方法，分别求出每天所需的人数(每个时段开始上班的人数加起来就是每天总共需要的人数)，再按例2方法求出公司的最小编制

15 §4.2、生产计划的问题 例3 ．某公司面临一个问题：是外包协作还是自行生产。该公司生产甲、乙、丙三种产品，这三种产品都要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。有关情况见表4—3；公司中可利用的总工时为：铸造8000小时，机加工12000小时和装配10000小时。公司为了获得最大利润，甲、乙、丙三种产品各生产多少件?甲、乙两种产品的铸造应多少由本公司铸造? 多少由外包协作？

16 表4-3 解：设 x1、x2、x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，
工时与成本 甲 乙 丙 每件铸造工时(小时) 5 10 7 每件机加工工时(小时) 6 4 8 每件装配工时（小时) 3 2 自产铸件每件成本(元) 外协铸件每件成本(元) 机加工每件成本(元) 1 装配每件成本(元) 每件产品售价(元) 23 18 16 解：设 x1、x2、x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数， 设x4、x5分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。

17 产品甲全部自制的利润=23-(3+2+3)=15(元) 产品甲铸造外协，其余自制的利润=23-(5+2+3)=13(元)
工时与成本 甲 乙 丙 每件铸造工时(小时) 5 10 7 每件机加工工时(小时) 6 4 8 每件装配工时（小时) 3 2 自产铸件每件成本(元) 外协铸件每件成本(元) 机加工每件成本(元) 1 装配每件成本(元) 每件产品售价(元) 23 18 16 ① 先计算每件产品的利润（目标函数的系数） ② ③ ④ ⑤ ⑥ ⑦ ④ ⑥ ⑦ 产品甲全部自制的利润=23-(3+2+3)=15(元) 产品甲铸造外协，其余自制的利润=23-(5+2+3)=13(元) 产品乙全部自制的利润=18-(5+1+2)=10(元) 产品乙铸造外协，其余自制的利润=18-(6+1+2)=9(元) 产品丙的利润 =16-(4+3+2)=7(元) ⑤ ⑥ ⑦ ④ ⑥ ⑦ ⑤ ⑥ ⑦ ④ ⑥ ⑦

18 5X1+10X2+7X3≤8000(这里没包括外协铸造时间)， 6X1+4X2+8X3+6X4+4X5≤12000(机加工)，
工时与成本 甲 乙 丙 每件铸造工时(小时) 5 10 7 每件机加工工时(小时) 6 4 8 每件装配工时（小时) 3 2 建立数学模型如下： 目标函数： max 15X1+10X2+7X3+13X4+9X5 约束条件： 5X1+10X2+7X3≤8000(这里没包括外协铸造时间)， 6X1+4X2+8X3+6X4+4X5≤12000(机加工)， 3X1+2X2+2X3+3X4+2X5≤10000(装配)， X1，X2，X3，X4，X5≥0 用“管理运筹学”软件进行计算，计算机计算结果显示在图4-1中。详见上机计算……。

19 1 目标函数最优值为：29400 变量 最优解 相差值 x1 1600 0 x2 0 2 x3 0 13.1
变量 最优解 相差值 x x x x x 1 相应的决策变量的目标系数（单位利润）需要改进的数量 10 7 13 结果分析： 1. 最大的利润为29400元，其最优的生产计划为全部由自己生产的甲产品1600件，铸造外协、其余自制生产乙产品600件，而丙产品不生产。 2. 由相差值可知， —如果全部由自己生产的乙产品的利润再增加2元达到每件12元利润，那么全部自制的乙产品才有可能上马生产，否则乙产品还是铸造外协、其余自制的利润更大； —丙产品的利润要达到每件利润20.1元，丙产品才有可能上马生产； —铸造外协、其余自制的甲产品利润达到13.5元，才有可能上马生产。

20 2 约束 松驰/剩余变量 对偶价格 1 0 0.3 2 0 2.25 3 4000 0 由对偶价格可知：
约束 松驰/剩余变量 对偶价格 2 增加一个工时，付出少于对偶价格，但利润可以增加对偶价格 由对偶价格可知： 铸造每工时的对偶价格为0.3元，机加工每工时的对偶价格为2.25元，装配每工时的对偶价格为0元。 如果有人以低于铸造和机加工的对偶价格来提供铸造及机加工的工时则可以购入来获取差价（例如外协铸造工时价格低于0.3元，则外协铸造合算)。（你买别人的工时） 如果有人要购买该公司的铸造与机加工的工时，则出价必须扣除成本外，还必须高于其对偶价格，否则就不宜出售。至于装配每工时的对偶价格为0，这是由于在此生产计划下还有4000个装配工时没有完。（你卖自己的工时）

21 注意啊！ 对偶价格不是市场价格。 在作市场决策时： 某种资源市场价格低于对偶价格时， 可适量 这种资源，组织和增加生产。
可适量 这种资源，组织和增加生产。 2. 当市场价格高于对偶价格时， 可以 资源而不安排生产或提高产品的价格。 注意啊！ 买进 卖出

22 目标函数系数范围： 变量 下限 当前值 上限 X1 14 15 无上限 X2 无下限 10 12 X3 无下限 7 20
目标函数系数范围： 变量 下限 当前值 上限 X 无上限 X 无下限 X 无下限 X 无下限 X 3 从目标函数决策变量系数一栏中知道，当全部自己生产的每件甲产品的利润在14到+∞内变化时，其最优解不变；全部自己生产的每件乙产品的利润只要不超过12元，则其最优解不变；当每件丙产品的利润不超过20.1元时，则其最优解不变；当铸造外协其余自制的每件甲产品的利润不超过13.5元时，其最优解不变；当铸造外协，其余自制的每件乙产品的利润在8.667到10元内变化时，则其最优解不变。在这里当某产品利润变化时都假设其余产品的利润是不变的。

23 常数项范围 约束 下限 当前值 上限 无上限 从约束条件右边常数变化范围栏可知，当铸造工时在0到10000小时间变化时其对偶价格都为0.3元；当机加工工时在9600到20000小时内变化时，其对偶价格都为2.25元；当装配工时在6000到+∞内变化时，其对偶价格都为零。 注意：当常数项超出上面的范围时其对偶价格可能已变。 4

24 例4 永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品。每种产品均要经过A、B两道工序加工。设该厂有两种规格的设备能完成A工序，它们以A1、A2表示；有三种规格的设备能完成B工序，它们以B1，B2，B3表示。产品Ⅰ可在A、B的任何规格的设备上加工。产品Ⅱ可在任何一种规格的A设备上加工，但完成B工序时，只能在B1设备上加工。产品Ⅲ只能在A2与B2设备上加工。已知在各种设备上加工的单件工时、原料单价、产品销售单价、各种设备的有效台时以及满负荷操作时的设备费用如表4 —4示，要求制定最优的产品加工方案，使该厂利润最大。

25 3个产品 2道工序 5个设备 表4-4 设 备 产品单件工时 设备的有效台时 满负荷时的设备费用 Ⅰ Ⅱ Ⅲ A1 5 10 6000
设 备 产品单件工时 设备的有效台时 满负荷时的设备费用 Ⅰ Ⅱ Ⅲ A1 5 10 6000 300 A2 7 9 12 10000 321 B1 6 8 4000 250 B2 4 11 7000 783 B3 200 原料单价(元／件) 0.25 0.35 0.5 销售单价(元／件) 1.25 2 2.8 3个产品 2道工序 5个设备

26 设 备 产品单件工时 设备的有效台时 满负荷时的设备费用 A1 5,X111 10,X211 6000 300 A2 7,X112
设 备 产品单件工时 设备的有效台时 满负荷时的设备费用 Ⅰ Ⅱ Ⅲ A1 5,X111 10,X211 6000 300 A2 7,X112 9,X212 12,X312 10000 321 B1 6,X121 8,X221 4000 250 B2 4,X122 11,X322 7000 783 B3 7,X123 200 解：设Xijk表示第i种产品在第j种工序上(A工序用1表示，B工序用2表示)的第k种设备上加工的数量。如x123表示第Ⅰ种产品在B道工序上用B3设备加工的数量。则约束 5x111+10x211≤6000， (设备A1) 7x112+9x212+12x312≤10000， (设备A2) 6x121+8x221≤4000， (设备B1)， 4x122+11x322≤ (设备B2) , 7x123≤4000 (设备B3)

27 设 备 产品单件工时 设备的有效台时 满负荷时的设备费用 A1 5,X111 10,X211 6000 300 A2 7,X112
设 备 产品单件工时 设备的有效台时 满负荷时的设备费用 Ⅰ Ⅱ Ⅲ A1 5,X111 10,X211 6000 300 A2 7,X112 9,X212 12,X312 10000 321 B1 6,X121 8,X221 4000 250 B2 4,X122 11,X322 7000 783 B3 7,X123 200 设Xijk表示第i种产品在第j种工序上(A工序用1表示，B工序用2表示)的第k种设备上加工的数量。恒等约束（隐含约束）： X111+X112-X121-X122 –X123=0，(Ⅰ产品在A、B工序上加工的数量相等) X211+X212-X221=0, (Ⅱ产品在A、B工序上加工的数量相等) X312-X322=0, (Ⅲ产品在A、B工序上加工的数量相等)

28 设 备 产品单件工时 设备的有效台时 满负荷时的设备费用 Ⅰ Ⅱ Ⅲ A1 5,X111 10,X211 6000 300 A2 7,X112 9,X212 12,X312 10000 321 B1 6,X121 8,X221 4000 250 B2 4,X122 11,X322 7000 783 B3 7,X123 200 原料单价(元／件) 0.25 0.35 0.5 销售单价(元／件) 1.25 2 2.8

29 设 备 产品单件工时 设备的有效台时 满负荷时的设备费用 Ⅰ Ⅱ Ⅲ A1 5,X111 10,X211 6000 300 A2
设 备 产品单件工时 设备的有效台时 满负荷时的设备费用 Ⅰ Ⅱ Ⅲ A1 5,X111 10,X211 6000 300 A2 7,X112 9,X212 12,X312 10000 321 B1 6,X121 8,X221 4000 250 B2 4,X122 11,X322 7000 783 B3 7,X123 200 一台机器设备的有效台时都用光了所发生的费用

30 5x111+10x211≤6000， (设备A1) 7x112+9x212+12x312≤10000， (设备A2) 6x121+8x221≤4000， (设备B1)， 4x122+11x322≤ (设备B2) , 7x123≤4000 (设备B3) X111+X112-X121-X122 –X123=0，(Ⅰ产品在A、B工序上加工的数量相等) X211+X212-X221=0, (Ⅱ产品在A、B工序上加工的数量相等) X312-X322=0, (Ⅲ产品在A、B工序上加工的数量相等)

31 再将最优解四舍五入 模型 将模型输入计算机 x111=1200，x112=230.0492，X211=0， X212 =500，
X312 = ， X121 =0，X221 =500，X122 = ，X322 = ，X123 = , 最优值为 。 再将最优解四舍五入 模型 将模型输入计算机

32 由于本题要求的决策变量的单位是件，所以答案应该是整数。本题与例1、例2、例3实质上都是整数规划的问题，但是这类问题可以作为线性规划的问题来解，有些如例1，例2，例3的答案都是整数，而有些如本题答案是非整数，可以将答案舍入成整数也可能得到满意的结果。如本题如果用软件的整数规划的来解，得到的答案为x111=1200，x112=230，X211=0，X212 =500，X312 =324， X121 =0，X221 =500，X122 =859，X322 =324，X123 =571..最优值为 。其最优解正好与四舍五入线性规划结果一样的。两种方法的最优值也相差无几，只差0.3元。

33 另一种建模方法 第1种产品的加工方法有几种？ 2*3=6 第2种产品的加工方法有几种？ 2*1=2 第3种产品的加工方法有几种？ 1*1=1 共有9种加工方法 产品Ⅰ可在A、B的任何规格的设备上加工。产品Ⅱ可在任何一种规格的A设备上加工，但完成B工序时，只能在B1设备上加工。产品Ⅲ只能在A2与B2设备上加工。

34 另一种建模方法 x1表示第1种产品A工序在设备A1、 B工序在设备B1生产的件数； x2表示第1种产品A工序在设备A1、B工序在设备B2生产的件数； x3表示第1种产品A工序在设备A1、B工序在设备B3生产的件数； x4表示第1种产品A工序在设备A2、B工序在设备B1生产的件数； x5表示第1种产品A工序在设备A2、B工序在设备B2生产的件数； x6表示第1种产品A工序在设备A2、B工序在设备B3生产的件数； x7表示第2种产品A工序在设备A1生产的件数； x8表示第2种产品A工序在设备A2生产的件数； x9表示第3种产品的件数。 B1 A2 B2

35 目标函数： max f=(1.25−0.25)(x1+x2+x3+x4+x5+x6) +(2−0.35)(x7+x8)+(2.80−0.5)x9– 300/6000(5(x1+x2+x3)+10x7)-321/10000(7(x4+x5+x6)+9x8+12x9)-250/4000(6(x1+x4)+8(x7+x8)) -783/7000(4(x2+x5) +11x9 ) -200/4000(7(x3+x6)) 决策变量非负说明 xi ≥ 0 , i = 1，2，…，9 设备A1 设备A2 设备B1 设备B2 设备B3

36 约束条件 s.t. 5(x1 +x2+x3)+10x7≤6000（设备 A1） 7(x4+x5+x6)+9x8+12x9≤10000（设备A2） 6(x1+x4) +8(x7+x8)≤4000（设备 B1） 4(x2+x5) +11x9 ≤ 7000 （设备 B2） 7 (x3+x6) ≤ 4000 （设备 B3）

37 §4.3、套裁下料问题 例5 某工厂要做100套钢架，每套需要长为2.9m，2.1 m 和1.5 m的圆钢各一根。已知原料每根长7.4m，
问应如何下料，可使所用原料最省。 解：最简单的做法是： 在每根原材料上截取2.9m、2.1m和1.5m的圆钢各一根组成一套，每根原材料省下料头0.9m。为了做100套钢架，需要原材料100根，共有90m的料头。 若改用套裁可以节约不少原材料，为了找到一个省料的套裁方案，先设计出较好的几个下料方案，所谓较好，第一要求每个方案下料后的料头较短，第二要求这些方案的总体能裁下所有各种规格的圆钢，并且不同方案有着不同的各种所需圆钢的比。这样套裁才能满足对各种不同规格圆钢的需要并达到省料的目的。为此设计出以下5种下料方案以供套裁用。见表4—5。

38 表4—5。 下料数 方案 （根） 长度 Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ 2.9 1 2 2.1 1.5 3 合计 7.4 7.3 7.2 7.1 6.6
下料数 方案 （根） 长度 Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ 2.9 1 2 2.1 1.5 3 合计 7.4 7.3 7.2 7.1 6.6 料头 0.1 0.2 0.3 0.8 其它方案的料头较多，不考虑，如1根2.9,1根2.1,1根1.5,料头为0.9m

39 目标函数：min X1+X2+X3+X4+ X5 约束条件：X1+2X2+ X4 ≥100（2.9m的圆钢）
解：为了用最少的原材料得到100套钢架，需要混合使用上述五种下料方案，设按I，Ⅱ，Ⅲ，Ⅳ，V方案下料的原材料根数分别为x1，x2，x3，x4，x5，可列出下面的数学模型。 目标函数：min X1+X2+X3+X4+ X5 约束条件：X1+2X2+ X4 ≥100（2.9m的圆钢） 2X3+ 2X4+X5 ≥100 （2.1m的圆钢） 3X1+X2+2X3+3X5 ≥100 （1.5m的圆钢） X1， X2， X3， X4， X5 ≥0． 上机计算得到如下最优下料方案：按Ⅰ方案下料30根；按Ⅱ方案下料10根，按Ⅳ方案下料50根(即x1=30，x2=10，x3=0，x4=50，x5=0)，只需90根原材料(即目标函数最小值为90)即可制造100套钢架。

40 思考如果只取方案前四个或前三个或再增加其它方案，结果如何？

41 其它方案列表（不是所有）(P46-5b) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2.9 2.1 1.5 合计 7.4 7.3 7.2 7.1 6.6 6.5 5.9 6.3 5.7 5.1 4.5 料头 0.1 0.2 0.3 0.8 0.9 1.1 1.7 2.3 1.4 4.4 min X1+X2+X3+X4+ X5+X6+X7+X8+X9+X10+X11+X12+X13+X14 约束条件： X1+2X2+ X4 +X6+X7≥100， 2X3+ 2X4+X5 +X6+3X8+2X9+X10≥100， 3X1+X2+2X3+3X5 +X6+2X7+X9+2X10+4X11+3X12+2X13+X14≥100

42 解为：目标函数值=90, x1=0,x2=40,x3=30,x4=20,其它x为0。从这里看出模型有多个解。料头多的方案一般为0。
将模型输入计算机

43 注意！ 在建立此数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这个套用方案就不是可行解了。

44 引申 在一个给定长度的原料上裁出不同长度的产品，是一个线裁问题 如果在一个一给定形状的面积上，裁出不同形状的产品，这是一个面裁问题
类似地还有体裁问题。 解决该类问题的方法都和例5类似，都是先设计出一些较好的下料方案，然后用类似的线性规划模型解决。

45 现在讲第四个问题 ：§4.4配料问题 例6 某工厂要用三种原料1，2，3混合调配出三种不同规格的产品甲、乙、丙，已知产品的规格要求、产品的单价、每天能供应的原材料数量及原材料单价，分别见表4-6和表4-7。该厂应如何安排生产，使利润收入为最大? 表4-6 产品名称 规格要求 单价(元／千克)  甲 原材料1不少于50％，原材料2不超过25％ 50 乙 原材料1不少于25％， 原材料2不超过50％ 35 丙  不限 25

46 3种产品，3种原料 原材料名称 每天最多供应量 单价（元/千克） 1 100 65 2 25 3 60 35
解：设xij表示第i种产品中原材料j的含量(分别用 产品1，2，3表示产品甲、乙、丙)。例如x23就表 示乙产品中第3种原材料的含量，目标是使利润 最大，利润的计算公式如下：

47 利润 = 总收入 − 总原料支出 收入 支出 设xij表示第 i 种（甲、乙、丙）产品中原料 j 的含量
利润 = 总收入 − 总原料支出 甲的数量：x11，x12，x13之和（各种原料生产的甲产品的数量）； 乙的数量：x21，x22，x23之和； 丙的数量：x31，x32，x33之和； 原料 1数量：x11，x21，x31之和（每种产品所用到的原料1的数量）； 原料 2数量：x12，x22，x32之和； 原料 3数量：x13，x23，x33之和； 收入 支出

48 由表4-6得到约束条件： 规格要求4个；供应量限制3个
X11≥0.5(X11+X12+X13)，(甲产品中原料1的数量不少于50%) X12≤0.25(X11+X12+X13) X21≥0.25(X21+X22+X23) X22≥0.5(X21+X22+X23) 规格要求 由表4-7得到： X11+X21+X31≤100 X12+X22+X32≤100 X13+X23+X33≤60 原材料1的供应量 供应量

49 得问题模型如下(必须整理后上机求解）：

50 解为：x11=100，x12=50,x13=50，其余的xij=0，也就是说每天只生产甲产品200千克，分别需要用1原料100千克，2原料50千克，3原料50千克。其它乙、丙产品不生产。目标函数值=500元 模型 将模型输入计算机

51 例7 汽油混合问题 一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1，2，3，4种标准汽油，其特性和库存量列于表4—8中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种飞机汽油的性能指标及产量需求列于表4—9中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号飞机汽油满足需求，并使得1号飞机汽油产量最高。

52 表4-9 4种标准汽油 2种飞机汽油 设Xij为飞机汽油i 中所用标准汽油j的数量，这样可知：
辛烷数 蒸汽压力(g／cm2) 产量需求(L) 1 不小于91 不大于9.96×10-2 越多越好 2 不小于100 不少于250000 设Xij为飞机汽油i 中所用标准汽油j的数量，这样可知： X11+X12+X13+X14为飞机汽油1总产量，总产量越多越好，所以有目标函数为 max X11+X12+X13+X14 约束条件之一：X21+X22+X23+X24≥250000

53 表4-8: 得到有关库存量和产量指标的约束条件： X11+X21≤380000, X12+X22≤265200,
标准汽油 辛烷数 蒸汽压力(s／cm2) 库存量(L) 1 107.5 7.11×10-2 380000 2 93 11.38×10-2 265200 3 87 5.69×10-2 408100 4 108 28.45×10-2 130100 得到有关库存量和产量指标的约束条件： X11+X21≤380000, X12+X22≤265200, X13+X23≤408100, X14+X24≤130100, Xij≥0.

54 下面再列出有关辛烷数和蒸汽压力的约束条件:
物理中的“分压定律”可叙述如下：“设有一种混合气体，由n种气体组成。设混合气体的压力为P，所占总容积为V，各组成成分的压力及其所占容积分别为p1…,pn，及v1,…,vn,，则PV=∑pj vj”。用此分压定律可写出有关蒸汽压力的约束条件。 飞机汽油1的蒸汽压力不能大于9.96×10-2,，即有:

55 同样，可以得到有关飞机汽油2的蒸汽压力的约束条件为：
2.85x x x x24≥0.

56 同样可以写有关辛烷数的约束条件，对于飞机汽油1有：
标准汽油 辛烷数 蒸汽压力(s／cm2) 1 107.5 7.11×10-2 2 93 11.38×10-2 3 87 5.69×10-2 4 108 28.45×10-2 同样可以写有关辛烷数的约束条件，对于飞机汽油1有： (107.5x11+93x12+87x13+108x14)/(x11+x12+x13+x14) ≥91. 经整理得： 16.5x11+2x12-4x13+17x14≥0. 对于飞机汽油2有： 7.5x21-7x22-13x23+8x24≥0. 综上所述得到此问题的数学模型 :

57 数学模型： 目标函数：max X11+X12+X13+X14 约束条件：X21+X22+X23+X24≥250000,
　　　　　　Xij≥0 产量需求 库存量 蒸汽压力约束条件 辛烷数约束条件

58 X11= ，X12=265200，x13= ，X 14 = ，X 21 = ，X 22 =0， X 23 = ， X 24 = ， 最优值= 。 模型 将模型输入计算机

59 结论： 表明用1号标准汽油 升，2号标准汽油265200升，3号标准汽油 升，4号标准汽油 升，混合成 升1号飞机汽油；用1号标准汽油 升，2号标准汽油零升，3号标准汽油 升，4号标准汽油 升混合成250000升2号飞机汽油，这是既满足需求，又使1号汽油的产量为最高的最优方案。

60 §4.5投资问题 例8 某部门现有资金200万元，今后五年内考虑给以下的项目投资，已知项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110％。项目B：从第一年到第三年每年年初都可以投资，次年末回收本利125％，但规定每年最大投资额不能超过30万元。项目C：第三年初需要投资，到第五年末能回收本利140％，但规定最大投资额不能超过80万元。项目D：第二年初需要投资，到第五年未能回收本利155％，但规定最大投资额不能超过100万元。

61 据测定每万元每次投资的风险指数如下所示：
项目 风险指数（每万元每次） A 1 B 3 C 4 D 5.5 问： （1） 应如何确定这些项目的每年投资额，使得第五年末拥有资金的本利金额为最大? （2） 应如何确定这些项目的每年投资额，使得第五年末拥有资金的本利在330万的基础上使得其投资总的风险系数为最小?

62 解： 第一 确定变量： 项目有4个，年数有5年 （1）这是一个连续投资的问题，设xij为第i年初投资于j项目的金额(单位万元)，根据给定条件，将变量列于下表： 年份 项目 1 2 3 4 5 A x1A x2A x3A x4A x5A B x1B x2B x3B x4B C x3C D x2D 第二 确定约束条件 因为项目A每年都可以投资，并且当年末都能收回本息，所以该部门每年都应把资金都投出去，手中不应当有剩余的呆滞资金，因此第一年：该部门年初有资金200万元，故有 X1A+X1B=200

63 1 2 3 4 5 x1A x2A x3A x4A x5A x1B x2B x3B x4B x3C x2D
年份 项目 1 2 3 4 5 A x1A x2A x3A x4A x5A B x1B x2B x3B x4B C x3C D x2D 第二年：因第一年给项目B的投资要到第二年末才能回收，所以该部门在第二年初拥有资金仅为项目A在第一年投资额所回收的本息110％X1A， 故有 X2A+X2B+X2D =1.1X1A 第三年：第三年初的资金额是从项目A第二年投资和项目B第一年投资所回收的本息总和 1.1X2A+1.25X1B 故有 X3A+X3B+X3C =1.1X2A+1.25X1B

64 1 2 3 4 5 x1A x2A x3A x4A x5A x1B x2B x3B x4B x3C x2D
年份 项目 1 2 3 4 5 A x1A x2A x3A x4A x5A B x1B x2B x3B x4B C x3C D x2D 第四年：同以上分析，可得 X4A+X4B =1.1X3A+1.25X2B 第五年： X5A =1.1X4A+1.25X3B 另外，由于对项目B，C，D的投资额的限制有 xiB≤30, ( i=1,2,3,4) x3c≤80, x2D≤100. 考察的是第5年年初拥有的资金

65 第三、目标函数和模型 该问题要求在第五年末该部门手拥有的资金额达到最大，这个目标函数可以表示为:
max (1.1X5A+1.25X4B+1.4X3C+1.55X2D) 模型为： 目标函数：max z=1.1X5A+1.25X4B+1.4X3C+1.55X2D S.t X1A+X1B=200 X2A+X2B+X2D =1.1X1A X3A+X3B+X3C =1.1X2A+1.25X1B X4A+X4B =1.1X3A+1.25X2B X5A =1.1X4A+1.25X3B XiB≤30, ( i=1,2,3,4) X3c≤80, X2D≤ Xij≥0.

66 共11个约束条件 化简后得到： 化简才能上机 max 1.1x5A+1.25x4B+1.4x3C+1.55x2D
St x1A+x1B=200 x2A+x2B+x2D-1.1x1A=0 x3A+x3B+x3C-1.1x2A-1.25x1B=0 x4A+x4B-1.1x3A-1.25x2B=0 x5A-1.1x4A-1.25x3B=0 X1B≤30 x2B≤ 30 x3B ≤ 30 x4B ≤ 30 x3C ≤ 80 x2D ≤100 共11个约束条件

67 x1A=170, x2A=57, x3A=0, x4A=7. 5, x5A=33. 5 ，x1B=30, x2B=30, x3B=20
x1A=170, x2A=57, x3A=0, x4A=7.5, x5A=33.5 ，x1B=30, x2B=30, x3B=20.2, x4B=30 x3C=80 ，x2D=100 第五年末拥有的资金的本利 （即目标函数最大值） 为341.35万元 模型 将模型输入计算机

68 从对偶价格栏可知： 约束 松驰/剩余变量 对偶价格 0 1.664 0 1.513 0 1.375 0 1.21 0 1.1
约束 松驰/剩余变量 对偶价格 从对偶价格栏可知： 第一年初增加投资1万元，将导致第五年末拥有资金的本利增加1.664万元；目前第一年投资额为200万； 第二年初增加投资1万元，将导致第五年末拥有资金的本利增加1.513万元，目前第二年的投资金额来自第一年投资于项目A而回收的110％的本利； 第三年初、第四年初、第五年初增加或减少投资1万元，将导致第五年末拥有资金的本利分别增加或减少1.375万元、1.210万元、1.1万元；

69 约束 松驰/剩余变量 对偶价格 从第6个至第9个约束方程对偶价格栏中可知：如果第一年、第二年、第三年、第四年B项目的投资额的限制放松或收缩1万元指标(对应于XiB≤30，I=1,2,3,4），将导致第五年末拥有的资金的本利分别增加或减少0.055万元、0万元、0万元、0.040万元；

70 约束 松驰/剩余变量 对偶价格 从第10个和第11个约束方程对偶价格栏可知： 项目C（对应于X3C≤80)、项目D （对应于X2D≤100)的投资额的限制放松或收缩1万元的指标，将导致第五年末拥有的资金的本利分别增加或减少0.025万元、0.037万元

71 常数项范围： 约束 下限 当前值 上限 上表是关于保持对偶价格不变的约束条件右边值的变化范围的，当某一个的右边值在此范围内变化而其他右边值不变时，对偶价格不变，例如如果第一年初现有资金为190万元，从表上可知，190万元属于保持对偶价格不变的右边值的变化范围内，故可以从其对偶价格计算出第五年末所拥有的资金的本利总数为： ( ) ×1.664=324.71(万元) 但如第一年初现有资金低于下限 万元时，则需要重新建模求解。当几个右边值同时变化时则可用百分之一百法则判断原来的对偶价格是否保持不变。

72 部分目标系数变动范围：（目标函数中只包含这几个变量）
变量 下限 当前值 上限 X5A X4B 无上限 X3C 无上限 X2D 无上限 上表中列出了目标函数中部分变量系数的变化范围，当X5A、X4B、X3C和X2D中的一个变量的系数在此范围内变化时，即项目A的第五年、项目B的第四年、项目C的第三年、项目D的第二年投资在第五年末的回收本利的百分比中的一个在此范围变化时，最优解保持不变。超出这个范围，要重新建模求解，当几个系数同时变化时要用百分之百法则判断。

73 x1~x11分别代表： x1A,x2A,x3A,x4A,x5A, x1B,x2B,x3B,x4B, x3C,x2D

74

75 注意 在这里要说明的是在目标函数中变量X1A、X1B、X2A、X2B、X3A、X3B、X4A的系数都为零，这主要是我们把这些变量的投资回收本利的百分比对第五年的贡献都体现在约束条件里，而没体现在目标函数中，所以没法用其目标函数的系数对其进行回收本利百分比的灵敏度分析。

76 （2）．所设变量与(1)相同，可知其目标函数为最小风险，有:
Min f =X1A+X2A+X3A+X4A+X5A +3(X1B+X2B+X3B+X4B)+4X3C+5.5X2D 在问题(1)的约束条件中加上要求第五年末拥有资金本利在330万元的条件就得到问题(2)的约束条件： S.t X1A+X1B=200, X2A+X2B+X2D-1.1X1A=0, X3A+X3B+X3C-1.1X2A-1.25X1B =0, X4A+X4B+X3A-1.25X2B=0, X5A-1.1X4A-1.21X3B=0, XiB≤30，（i=1,2,3,4) X3C≤80， X2D≤100， 1.1X5A+1.25X4B+1.4X3C+1.55X2D≥330, Xij≥0，

77 此问题的最优解为: X1A=200, X2A=192.317, X3A=131.549, X4A=144.704, X5A=159.174,
X3C=80, X2D=27.683, X1B=X2B=X3B=X4B=0, 此时其投资的风险系数最小为1300。

78 变量 最优解 相差值 X1A X2A X3A X4A X5A X1B X2B X3B X4B 目标函数中系数需要改进的数量 在上图相差值中可知如果XiB(i=1,2,3,4)的风险系数至少减少0.5即降为2.5或2.5以下，则可以考虑对项目B的第i年的投资，否则就不对其投资.

79 约束 松驰/剩余变量 对偶价格 …… …… …… 提高1万元回收，相当于增加约束条件常数项1个单位，则目标函数值变坏 在第二栏的第12个约束方程的剩余变量栏中的数值为零，而其对偶价格为-10，表明用此方案第五年末的本利的回收正好为330万，如果要提高(或减少)一万元回收，则要增加(或减少)10个风险系数值。而1，2，3，4，5的约束方程中的对偶价格都为10，表明在第一，二，三，四，五年都增加(或减少)投资1万元，就会减少(或增加)投资10个风险系数值。

80 在第三栏的目标函数系数变化范围栏中表明了当某个项目的风险系数在此范围内变化,而其它风险系数不变时,最优解不变。
在第四栏中指出了当某个右边值在此范围内变化,而其它右边值不变时,所有对偶价格值都不变.

81 本章作业 2（人力资源） 3、8、9（生产计划） 1（套裁下料） 6（配料问题） 不要偷懒啊！