(MBA课程)管理运筹学第四章线性规划在工商管理中的应用合集课件.ppt

1、1第四章、线性规划在工商第四章、线性规划在工商管理中的应用管理中的应用 通过线性规划的图解法，我们对线性规通过线性规划的图解法，我们对线性规划的求解及灵敏度分析的基本概念、基本原理划的求解及灵敏度分析的基本概念、基本原理已有所了解，又通过线性规划问题的计算机求已有所了解，又通过线性规划问题的计算机求解的学习，我们掌握了用计算机软件这一有用解的学习，我们掌握了用计算机软件这一有用工具去求解线性规划问题及其灵敏度分析。在工具去求解线性规划问题及其灵敏度分析。在这一章我们来研究线性规划在工商管理中的应这一章我们来研究线性规划在工商管理中的应用，解决工商管理中的实际问题。用，解决工商管理中的实际问题。

2、广西大学广西大学王中昭王中昭制作制作 4.1、人力资源分配的问题、人力资源分配的问题 4.2、生产计划的问题、生产计划的问题 4.3、套裁下料问题、套裁下料问题 4.4、配料问题、配料问题 4.5、投资问题、投资问题广西大学广西大学王中昭王中昭制作制作 某昼夜服务的公交线路每天各时间段内所某昼夜服务的公交线路每天各时间段内所 需司机和乘务人员数如下：需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和

3、乘务人员人员，既能满足工作需要，又配备最少司机和乘务人员?班次班次时间时间所需人数所需人数16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030广西大学广西大学王中昭王中昭制作制作解：解：设设xi表示第表示第i班次时开始上班的司机和乘务人班次时开始上班的司机和乘务人员数，可以知道在第员数，可以知道在第i班工作的人数应包括班工作的人数应包括第第 i-1班次时开始上班的人员数和第班次时开始上班的人员数和第i班次时班次时开始上班的人员数，例如有开始上班的人员数，例如有x1+x270。又要。又要求

4、这六个班次时开始上班的所有人员最少，求这六个班次时开始上班的所有人员最少，即要求即要求x1+x2+x3+x4+x5+x6最小，这样我们建最小，这样我们建立如下的数学模型。立如下的数学模型。广西大学广西大学王中昭王中昭制作制作用用“管理运筹学管理运筹学”软件可以求得此问题的解：软件可以求得此问题的解：x1=50，x2=20，x3=50，x4=0，x5=20，x6=10，24小时内一共需要司机和乘务人员小时内一共需要司机和乘务人员150人。人。此问题的解不唯一，用此问题的解不唯一，用LINDO软件计算软件计算得到：得到：X1=60,X2=10,X3=50,X4=0,X5=30,X6=0 目标函数值

5、目标函数值=150广西大学广西大学王中昭王中昭制作制作 福安商场是个中型的百货商场，它对售货福安商场是个中型的百货商场，它对售货 人员的需求经过统计分析如下所示：人员的需求经过统计分析如下所示：星期一：星期一：15人；星期二：人；星期二：24人；星期三：人；星期三：25人；星期人；星期四：四：19人；星期五：人；星期五：31人；星期六：人；星期六：28人；星期日：人；星期日：28人。人。为了保证售货人员充分休息，售货人员每周工作五为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足

6、了工作需要，又使如何安排售货人员的作息，既满足了工作需要，又使配备的售货人员的人数最少配备的售货人员的人数最少?广西大学广西大学王中昭王中昭制作制作模型：模型：再按照每天所需售货员的人数写出约束条件，例再按照每天所需售货员的人数写出约束条件，例如星期日需要如星期日需要28人，我们知道商场中的全体售货员中人，我们知道商场中的全体售货员中除了星期六开始休息和星期日开始休息的人外都应该除了星期六开始休息和星期日开始休息的人外都应该上班，即有上班，即有x1+x2+x3+x4+x528，0,x 28 x 31 x 19 x 25 x 24 x 15 x 28 x:min x :7654321743217

7、632176521765417654365432543217654321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx约束条件目标函数广西大学广西大学王中昭王中昭制作制作 上机求解得：上机求解得：x1=12,x2=0,x3=11,x4=5,x5=0,x6=8,x7=0,目标函数最小值目标函数最小值=36.也就是说配备也就是说配备36个售货员，并安排个售货员，并安排12人休息星期一、人休息星期一、二；安排二；安排11 人休息星期三、四；安排人休息星期三、四；安排5人休息星期四、人休息星期四、五；安排五；安排8人休息星期六、日。这人休息星期六、日。这 样的安排既满

8、足了工样的安排既满足了工作需要，又使配备的售货员最少。软件对此问题的解如作需要，又使配备的售货员最少。软件对此问题的解如下：下：目标函数最优值为：目标函数最优值为：36 变量变量 最优解最优解 相差值相差值 x1 12 0 x2 0 0.333 x3 11 0 x4 5 0 x5 0 0 x6 8 0 x7 0 0广西大学广西大学王中昭王中昭制作制作 约束约束 松驰松驰/剩余变量剩余变量 对偶价格对偶价格 1 0 -0.333 2 9 0 3 0 -0.333 4 0 -0.333 5 1 0 6 0 -0.333 7 0 0 由于所有约束条件的对偶价格都小于或等于由于所有约束条件的对偶价格都

9、小于或等于0，故增加约束条件的常数项都不会使目标值变小。故增加约束条件的常数项都不会使目标值变小。即增加售货员是不利的。但对于约束即增加售货员是不利的。但对于约束1、3、4、6来讲，减少一售货员会使目标函数值变小，来讲，减少一售货员会使目标函数值变小，是有利的。是有利的。广西大学广西大学王中昭王中昭制作制作 目标函数系数范围：目标函数系数范围：变量变量 下限下限 当前值当前值 上限上限 X1 0 1 1.5X1 0 1 1.5 X2 0.667 1 X2 0.667 1 无上限无上限 X3 0 1 1.5X3 0 1 1.5 X4 1 1 1X4 1 1 1 X5 1 1 X5 1 1 无上限

10、无上限 X6 0 1 1X6 0 1 1 X7 1 1 1.333X7 1 1 1.333 安排星期二开始休息和星期安排星期二开始休息和星期五开始五开始休息的人员可休息的人员可以无限制，此时最优解仍然不变。以无限制，此时最优解仍然不变。广西大学广西大学王中昭王中昭制作制作 常数项范围：常数项范围：约束约束 下限下限 当前值当前值 上限上限 1 19 28 28 2 无下限无下限 15 24 3 15 24 42 4 10 25 41.5 5 无下限无下限 19 20 6 16 31 38.5 7 28 28 36广西大学广西大学王中昭王中昭制作制作法二：设法二：设x1为星期一开始上班的人数，为

11、星期一开始上班的人数，x2为星期二开始上为星期二开始上班的人数，班的人数，x7为星期日开始上班的人数。目标是要为星期日开始上班的人数。目标是要求售货人员的总数最少。求售货人员的总数最少。(P40-2a.ltx)目标函数目标函数:min X1+X2+X3+X4+X5+X6+X7 约束条件：约束条件：星期日星期日 X3+X4+X5+X6+X7 28星期一星期一 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+X531星期六星期六 X

12、2+X3+X4+X5+X628广西大学广西大学王中昭王中昭制作制作 明兴公司面临一个是外包协作还明兴公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、是自行生产的问题。该公司生产甲、乙、丙三种产品，这三种产品都要经过铸造、丙三种产品，这三种产品都要经过铸造、机加工和装配三个车间。甲、乙两种产品机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。有但产品丙必须本厂铸造才能保证质量。有关情况见表关情况见表43；公司中可利用的总工时；公司中可利用的总工时为：铸造为：铸造8000小时，机加工小时，机加工

13、12000小时和装小时和装配配10000小时。公司为了获得最大利润，甲、小时。公司为了获得最大利润，甲、乙、丙三种产品各生产多少件乙、丙三种产品各生产多少件?甲、乙两种甲、乙两种产品的铸造应多少由本公司铸造产品的铸造应多少由本公司铸造?应多少由应多少由外包协作？外包协作？广西大学广西大学王中昭王中昭制作制作表表4-34-3 解：设解：设x1、x2、x3分别为三道工序都由本公司加工分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，设的甲、乙、丙三种产品的件数，设x4、x5分别为由分别为由外协铸造再由本公司机加工和装配的甲、乙两种产外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。品的件

14、数。计算每件产品的利润分别如下：计算每件产品的利润分别如下：工时与成本工时与成本 甲甲乙乙丙丙每件铸造工时每件铸造工时(小时小时)5107每件机加工工时每件机加工工时(小时小时)648 每件装配工时（小时每件装配工时（小时)322 自产铸件每件成本自产铸件每件成本(元元)354外协铸件每件成本外协铸件每件成本(元元)56 机加工每件成本机加工每件成本(元元)213 装配每件成本装配每件成本(元元)322每件产品售价每件产品售价(元元)231816广西大学广西大学王中昭王中昭制作制作 产品甲全部自制的利润产品甲全部自制的利润=23-(3+2+3)=15(元元)产品甲铸造外协，其余自制的利润产品甲

15、铸造外协，其余自制的利润=23-(5+2+3)=13(元元)产品乙全部自制的利润产品乙全部自制的利润=18-(5+1+2)=10(元元)产品乙铸造外协，其余自制的利润产品乙铸造外协，其余自制的利润=18-(6+1+2)=9(元元)产品丙的利润产品丙的利润=16-(4+3+2)=7(元元)工时与成本工时与成本 甲甲乙乙丙丙每件铸造工时每件铸造工时(小时小时)5107每件机加工工时每件机加工工时(小时小时)648 每件装配工时（小时每件装配工时（小时)322 自产铸件每件成本自产铸件每件成本(元元)354外协铸件每件成本外协铸件每件成本(元元)56 机加工每件成本机加工每件成本(元元)213 装配

16、每件成本装配每件成本(元元)322每件产品售价每件产品售价(元元)231816广西大学广西大学王中昭王中昭制作制作 建立数学模型如下：建立数学模型如下：目标函数：目标函数：max 15X1+10X2+7X3+13X4+9X5 约束条件：约束条件：5X1+10X2+7X38000(这里没包括外协铸造时间这里没包括外协铸造时间)，6X1+4X2+8X3+6X4+4X512000(机加工机加工)，3X1+2X2+2X3+3X4+2X510000(装配装配)，X1，X2，X3，X4，X50 用用“管理运筹学管理运筹学”软件进行计算，计算机计算结果显示软件进行计算，计算机计算结果显示在图在图4-1中。详

17、见上机计算中。详见上机计算。工时与成本工时与成本 甲甲乙乙丙丙每件铸造工时每件铸造工时(小时小时)5107每件机加工工时每件机加工工时(小时小时)648 每件装配工时（小时每件装配工时（小时)322广西大学广西大学王中昭王中昭制作制作 目标函数最优值为：目标函数最优值为：29400 变量变量 最优解最优解 相差值相差值 x1 1600 0 x2 0 2 x3 0 13.1 x4 0 0.5 x5 600 0 广西大学广西大学王中昭王中昭制作制作约束约束 松驰松驰/剩余变量剩余变量 对偶价格对偶价格1 0 0.32 0 2.253 4000 0 从对偶价格栏可知铸造每工时的对偶价格为从对偶价格栏

18、可知铸造每工时的对偶价格为0.3元，元，机加工每工时的对偶价格为机加工每工时的对偶价格为2.25元，装配每工时的对偶元，装配每工时的对偶价格为零元。这样如果有人以低于铸造和机加工的对偶价格为零元。这样如果有人以低于铸造和机加工的对偶价格来提供铸造及机加工的工时则可以购入来获取差价价格来提供铸造及机加工的工时则可以购入来获取差价（例如外协铸造工时价格低于（例如外协铸造工时价格低于0.3元，则外协铸造合算元，则外协铸造合算)。同样如果有人要购买该公司的铸造与机加工的工时，则同样如果有人要购买该公司的铸造与机加工的工时，则出价必须扣除成本外，还必须高于其对偶价格，否则就出价必须扣除成本外，还必须高于

19、其对偶价格，否则就不宜出售。至于装配每工时的对偶价格为零，这是由于不宜出售。至于装配每工时的对偶价格为零，这是由于在此生产计划下还有在此生产计划下还有4000个装配工时没有完。个装配工时没有完。注意注意:从计算中可知从计算中可知,如果把如果把松驰或者松驰或者剩余变量看作变量剩余变量看作变量时引入模型时，对偶价格实际上是时引入模型时，对偶价格实际上是松驰或者松驰或者剩余变量剩余变量 的相差值的绝对值。的相差值的绝对值。广西大学广西大学王中昭王中昭制作制作 对偶价格不是市对偶价格不是市场价格，在作市场决场价格，在作市场决策时，某种资源市场策时，某种资源市场价格低于对偶价格时，价格低于对偶价格时，可

20、适量买进这种资源，可适量买进这种资源，组织和增加生产。相组织和增加生产。相反当市场价格高于对反当市场价格高于对偶价格时，可以卖出偶价格时，可以卖出资源而不安排生产或资源而不安排生产或提高产品的价格。提高产品的价格。广西大学广西大学王中昭王中昭制作制作 目标函数系数范围：目标函数系数范围：变量变量 下限下限 当前值当前值 上限上限X1 14 15 无上限无上限X2 无下限无下限 10 12X3 无下限无下限 7 20.1X4 无下限无下限 13 13.5X5 8.667 9 10广西大学广西大学王中昭王中昭制作制作 常数项范围常数项范围约束约束 下限下限 当前值当前值 上限上限1 0 8000

21、100002 9600 12000 200003 6000 10000 无上限无上限 从约束条件右边常数变化范围栏可知，从约束条件右边常数变化范围栏可知，当铸造工时在当铸造工时在0到到10000小时间变化时其小时间变化时其对偶价格都为对偶价格都为0.3元；当机加工工时在元；当机加工工时在9600到到20000小时内变化时，其对偶价格小时内变化时，其对偶价格都为都为2.25元；当装配工时在元；当装配工时在6000到到+内内变化时，其对偶价格都为零。变化时，其对偶价格都为零。也就是说当常数项超出上面的范围时其也就是说当常数项超出上面的范围时其对偶价格可能已变，这时某种资源的市对偶价格可能已变，这时

22、某种资源的市场价格与对偶价格的关系随之发生变化。场价格与对偶价格的关系随之发生变化。广西大学广西大学王中昭王中昭制作制作 永久机械厂生产永久机械厂生产、三种产品。每种三种产品。每种产品均要经过产品均要经过A、B两道工序加工。设该厂有两种两道工序加工。设该厂有两种规格的设备能完成规格的设备能完成A工序，它们以工序，它们以A1、A2表示；有表示；有三种规格的设备能完成三种规格的设备能完成B工序，它们以工序，它们以B1，B2，B3表示。产品表示。产品可在可在A、B的任何规格的设备上加工。的任何规格的设备上加工。产品产品可在任何一种规格的可在任何一种规格的A设备上加工，但完成设备上加工，但完成B工序时

23、，只能在工序时，只能在B1设备上加工。产品设备上加工。产品只能在只能在A2与与B2设备上加工。已知在各种设备上加工的单件设备上加工。已知在各种设备上加工的单件工时、原料单价、产品销售单价、各种设备的有工时、原料单价、产品销售单价、各种设备的有效台时以及满负荷操作时的设备费用如表效台时以及满负荷操作时的设备费用如表4 4示，示，要求制定最优的产品加工方案，使该厂利润最大。要求制定最优的产品加工方案，使该厂利润最大。广西大学广西大学王中昭王中昭制作制作表表4-4设设 备备 产品单件工时产品单件工时设备的设备的有效台有效台时时满负荷时满负荷时的设备费的设备费用用A15106000300A279121

24、0000321B1684000250B24117000783B374000200原料单价原料单价(元件元件)0.250.350.5销售单价销售单价(元件元件)1.2522.8广西大学广西大学王中昭王中昭制作制作 解：设解：设Xijk表示第表示第i种产品在第种产品在第j种工序上种工序上(A工序用工序用1表示，表示，B工序工序用用2表示表示)的第的第k种设备上加工的数量。如种设备上加工的数量。如x123表示第表示第种产品在种产品在B道工序上用道工序上用B3设备加工的数量。则约束设备加工的数量。则约束 5x111+10 x2116000，(设备设备A1)7x112+9x212+12x31210000

25、，(设备设备A2)6x121+8x2214000，(设备设备B1)，4x122+11x3227000 (设备设备B2),7x1234000 (设备设备B3)设设 备备 产品单件工时产品单件工时设备的设备的有效台有效台时时满负荷时满负荷时的设备费的设备费用用A15,X11110,X2116000300A27,X1129,X21212,X31210000321B16,X1218,X2214000250B24,X12211,X3227000783B37,X1234000200广西大学广西大学王中昭王中昭制作制作 设设Xijk表示第表示第i种产品在第种产品在第j种工序上种工序上(A工序用工序用1表示，

26、表示，B工序用工序用2表表示示)的第的第k种设备上加工的数量。恒等约束：种设备上加工的数量。恒等约束：X111+X112-X121-X122 X123=0，(产品在产品在A、B工序上加工的数量工序上加工的数量相等相等)X211+X212-X221=0,(产品在产品在A、B工序上加工的数量相等工序上加工的数量相等)X312-X322=0,(产品在产品在A、B工序上加工的数量相等工序上加工的数量相等)设设 备备 产品单件工时产品单件工时设备的设备的有效台有效台时时满负荷时满负荷时的设备费的设备费用用A15,X11110,X2116000300A27,X1129,X21212,X3121000032

27、1B16,X1218,X2214000250B24,X12211,X3227000783B37,X1234000200应该是应该是0才合理才合理广西大学广西大学王中昭王中昭制作制作设设 备备 产品单件工时产品单件工时设备的有设备的有效台时效台时满负荷时的满负荷时的设备费用设备费用A15,X11110,X2116000300A27,X1129,X21212,X31210000321B16,X1218,X2214000250B24,X12211,X3227000783B37,X1234000200原料单价原料单价(元件元件)0.250.350.5销售单价销售单价(元件元件)1.2522.8总费用则

28、目标函数为时该设备实际使用的总台每台时的设备费用该产品件数原料单价销售单价利润目标函数3122211121115131)5.08.2()35.02()0.25)(x-(1.25Max :xxxji应该是应该是1.25(X121+X122+X123)-0.25(X111+X112)才才合理。合理。广西大学广西大学王中昭王中昭制作制作设设 备备 产品单件工时产品单件工时设备的有设备的有效台时效台时满负荷时的满负荷时的设备费用设备费用A15,X11110,X2116000300A27,X1129,X21212,X31210000321B16,X1218,X2214000250B24,X12211,X

29、3227000783B37,X123400020012332212222112131221211221111131222111211174000200)114(7000783)86(4000250)1297(10000321-)105(6000300)5.08.2()35.02()0.25)(x-(1.25Max xxxxxxxxxxxxx :5131ji时该设备实际使用的总台每台时的设备费用该产品件数原料单价销售单价利润目标函数广西大学广西大学王中昭王中昭制作制作 5x111+10 x2116000，(设备设备A1)7x112+9x212+12x31210000，(设备设备A2)6x121+

30、8x2214000，(设备设备B1)，4x122+11x3227000 (设备设备B2),7x1234000 (设备设备B3)X111+X112-X121-X122 X123=0，(产品在产品在A、B工序上加工工序上加工的数量相等的数量相等)X211+X212-X221=0,(产品在产品在A、B工序上加工的数量工序上加工的数量相等相等)X312-X322=0,(产品在产品在A、B工序上加工的数量相等工序上加工的数量相等)12332212222112131221221111211135.02304.10.4475x-5.00.375x-9148.13611.15x1.17753.00.75x:x

31、xxxxxMax化简后得到广西大学广西大学王中昭王中昭制作制作模型模型 将模型输入计算机x111=1200，x112=230.0492，X211=0，X212 =500，X312=324.138，X121=0，X221=500，X122=858.6206，X322=324.138，X123=571.4286,最优值为最优值为1146.6。广西大学广西大学王中昭王中昭制作制作 由于本题要求的决策变量的单位是件，所以由于本题要求的决策变量的单位是件，所以答案应该是整数。本题与例答案应该是整数。本题与例1、例、例2、例、例3实质上实质上都是整数规划的问题，但是这类问题可以作为线都是整数规划的问题，但

32、是这类问题可以作为线性规划的问题来解，有些如例性规划的问题来解，有些如例1，例，例2，例，例3的答的答案都是整数，而有些如本题答案是非整数，可以案都是整数，而有些如本题答案是非整数，可以将答案舍入成整数也可能得到满意的结果。如本将答案舍入成整数也可能得到满意的结果。如本题如果用软件的整数规划的来解，得到的答案为题如果用软件的整数规划的来解，得到的答案为x111=1200，x112=230，X211=0，X212 =500，X312=324，X121=0，X221=500，X122=859，X322=324，X123=571.最优值为最优值为1146.3622。其最优解。其最优解正好与四舍五入线

33、性规划结果一样的。两种方法正好与四舍五入线性规划结果一样的。两种方法的最优值也相差无几，只差的最优值也相差无几，只差0.3元。元。广西大学广西大学王中昭王中昭制作制作 本问题最优的方案为生产本问题最优的方案为生产产品产品1430件件（X111+X112=1200+230=X121+X122+X123=0+859+571=1430)，产品第产品第A道工序由道工序由A1设备加工设备加工1200件，由件，由A2设备加工设备加工230件。件。产品的第产品的第B道工序由道工序由B2设备加工设备加工859件，由件，由B3设备加工设备加工571件。件。生产生产产品产品500件，它的第件，它的第A道工序全部由

34、道工序全部由A2设备加工，它设备加工，它的第的第B道工序全部由道工序全部由B1设备加工。设备加工。X212=X221=500。生产生产产品产品324件，其第件，其第A道工序全部由道工序全部由A2加工，其第加工，其第B道工道工序全部由序全部由B2设备加工，设备加工，X312=X322=324，这样能使工厂获得最大利，这样能使工厂获得最大利润润1146.3元。元。生产数量生产数量A1X111=1200X211=0A2X112=230X212=500X312=324B1X121=0X221=500B2X122=859X322=324B3X123=571广西大学广西大学王中昭王中昭制作制作如果分别按实

35、际产品和原材料来计算则有：如果分别按实际产品和原材料来计算则有：Max z=-0.5x111-0.6352x112-0.85x211-0.6389x212-0.8852x312+0.875x121+0.8024x122+0.9x123+1.5x221+1.5691x322 5x111+10 x2116000，(设备设备A1)7x112+9x212+12x31210000，(设备设备A2)6x121+8x2214000，(设备设备B1)，4x122+11x3227000 (设备设备B2),7x1234000 (设备设备B3)X111+X112-X121-X122 X1230，(产品在产品在A工序

36、加工的数工序加工的数量大于量大于B加工的数量加工的数量)X211+X212-X2210,(产品在产品在A工序上加工数量天于工序上加工数量天于B的数量的数量)X312-X3220,(产品在产品在A工序上加工的数量大于工序上加工的数量大于B)广西大学广西大学王中昭王中昭制作制作结果如下：结果如下：本问题最优的方案为生产本问题最优的方案为生产产品产品1200件件（X111+X112=1200+0=X121+X122+X123=0+628.572+571.428=1200)，产品第产品第A道工序由道工序由A1设备加工设备加工1200件，由件，由A2设备加工设备加工0件。件。产品的第产品的第B道工序由道

37、工序由B2设备加工设备加工628.572件，由件，由B3设备加工设备加工571.428件。件。生产生产产品产品500件，它的第件，它的第A道工序全部由道工序全部由A2设备设备加工，它的第加工，它的第B道工序全部由道工序全部由B1设备加工。设备加工。X212=X221=500。生产生产产品产品324件，其第件，其第A道工序全部由道工序全部由A2加工，其加工，其第第B道工序全部由道工序全部由B2设备加工，设备加工，X312=X322=407.79，这样，这样能使工厂获得最大利润能使工厂获得最大利润1128.091元。比上方法要少。此元。比上方法要少。此法合理。法合理。广西大学广西大学王中昭王中昭制

38、作制作 某工厂要做某工厂要做100套钢架，每套用长为套钢架，每套用长为2.9m，2.1 m 和和1.5 m的圆钢各一根。已知原料每根长的圆钢各一根。已知原料每根长7.4m，问应如何下料，可使所用原料最省。问应如何下料，可使所用原料最省。广西大学广西大学王中昭王中昭制作制作表表45。下料数下料数 方案方案（根）（根）长度长度2.9120102.1002211.531203合计合计7.47.37.27.16.6料头料头00.10.20.30.8广西大学广西大学王中昭王中昭制作制作 解：解：为了用最少的原材料得到为了用最少的原材料得到100套钢架，需要套钢架，需要混合使用上述五种下料方案，设按混合使

39、用上述五种下料方案，设按I，V方案下料的原材料根数分别为方案下料的原材料根数分别为x1，x2，x3，x4，x5，可列出下面的数学模型。，可列出下面的数学模型。目标函数：目标函数：min X1+X2+X3+X4+X5 约束条件：约束条件：X1+2X2+X4 100，2X3+2X4+X5 100，3X1+X2+2X3+3X5 100，X1，X2，X3，X4，X5 0 上机计算得到如下最优下料方案：按上机计算得到如下最优下料方案：按方案下方案下料料30根；按根；按方案下料方案下料10根，按根，按方案下料方案下料50根根(即即x1=30，x2=10，x3=0，x4=50，x5=0)，只需，只需90根原

40、材料根原材料(即目标函数最小值为即目标函数最小值为90)即可制造即可制造100套钢架。套钢架。广西大学广西大学王中昭王中昭制作制作广西大学广西大学王中昭王中昭制作制作其它方案列表（不是所有）其它方案列表（不是所有）(P46-5b)12345678910111213142.9120101100000002.1002211032100001.531203120124321合计合计7.47.37.27.16.66.55.96.35.75.164.531.5料头料头00.10.20.30.80.91.51.11.72.31.44.44.45.9广西大学广西大学王中昭王中昭制作制作模型模型 将模型输入计

41、算机广西大学广西大学王中昭王中昭制作制作M 注意！注意！在建立此数学模型时，在建立此数学模型时，约束条件用大于等于约束条件用大于等于号比用等于号要好号比用等于号要好。因为有时在套用一些下料方。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这个套用方案就不是最优方案。如果用等于号，这个套用方案就不是可行解了。是可行解了。约束条件用大于等于号时，目标函数本来求约束条件用大于等于号时，目标函数本来求所用原材料最少和求料头最少是一样的，但由于所用原材料最少和求料头最少是一样的，但由于在第一个下料方案中料头为零，无论

42、按第一下料在第一个下料方案中料头为零，无论按第一下料方案下多少根料，料头都为零，也就是说不管第方案下多少根料，料头都为零，也就是说不管第一下料方案下料是一下料方案下料是200根还是根还是150都可使目标函数都可使目标函数值达到最小，这显然不合理。所以目标函数就一值达到最小，这显然不合理。所以目标函数就一定要求原材料最少。如果所有方案料头都不为零，定要求原材料最少。如果所有方案料头都不为零，则可用料头作为最小值函数变量。则可用料头作为最小值函数变量。广西大学广西大学王中昭王中昭制作制作 思考：思考：如果原材不止一种规格，如还有如果原材不止一种规格，如还有10M长的原材，则如何设计模型？长的原材，

43、则如何设计模型？广西大学广西大学王中昭王中昭制作制作 某工厂要用三种原料某工厂要用三种原料1，2，3混合调配出三种不混合调配出三种不同规格的产品甲、乙、丙，已知产品的规格要求、同规格的产品甲、乙、丙，已知产品的规格要求、产品的单价、每天能供应的原材料数量及原材料单产品的单价、每天能供应的原材料数量及原材料单价，分别见表价，分别见表4-6和表和表47。该厂应如何安排生产，。该厂应如何安排生产，使利润收入为最大使利润收入为最大?产品名称产品名称 规格要求规格要求 单价单价(元千克元千克)甲甲 原材料原材料1不少于不少于50，原材料原材料2不超过不超过25 50 乙乙原材料原材料1不少于不少于25，

44、原材料原材料2不超过不超过50 35丙丙 不限不限 25 广西大学广西大学王中昭王中昭制作制作 解：设解：设xij表示第表示第i种产品中原材料种产品中原材料j的含量的含量(分别用分别用 产品产品1，2，3表示产品甲、乙、丙表示产品甲、乙、丙)。例如。例如x23就表就表 示乙产品中第示乙产品中第3种原材料的含量，目标是使利润种原材料的含量，目标是使利润 最大，利润的计算公式如下：最大，利润的计算公式如下：原材料名称原材料名称 每天最多供应量每天最多供应量 单价（元单价（元/千克）千克）11006521002536035333122211312113323133222123121113332312

45、322211312113151x10 x40 x10 x30 x15x25-15x )(x35)(x25)65(x-)(x25)(x35)50(x max:)()(xxxxxxxxxxxxij目标函数为使用原料数量每种原料单价该产品的数量销售单价利润广西大学广西大学王中昭王中昭制作制作由表由表4-6得到：得到：X110.5(X11+X12+X13)，(甲中原料甲中原料1占甲占甲产品数量不少于产品数量不少于50%.)X120.25(X11+X12+X13)X210.25(X21+X22+X23)X220.5(X21+X22+X23)广西大学广西大学王中昭王中昭制作制作得问题模型如下得问题模型如下

46、(必须整理后上机求解）：必须整理后上机求解）：)3,2,1,3,2,1(,0 x ,60 x ,100 x ,100 x ,05.05.00.5x-,025.025.00.75x ,025.075.00.25x-,05.05.00.5x :x10 x40 x10 x30 x15x25-15xz max:ij33231332221231211123222123222113121113121133312221131211jixxxxxxxxxxxxxx约束条件目标函数广西大学广西大学王中昭王中昭制作制作模型模型 将模型输入计算机广西大学广西大学王中昭王中昭制作制作 VARIABLE VALUE R

47、EDUCED COST X11 100.000000 0.000000 X12 50.000000 0.000000 X13 50.000000 0.000000 X21 0.000000 15.000000 X22 0.000000 0.000000 X31 0.000000 45.000000 X33 0.000000 10.000000 X23 0.000000 0.000000 X32 0.000000 0.000000 广西大学广西大学王中昭王中昭制作制作 汽油混合问题。汽油混合问题。一种汽油的特性可用两种指标描述，用一种汽油的特性可用两种指标描述，用“辛烷数辛烷数”来定量描述其点火

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

49、机汽油产量最号飞机汽油产量最高。高。广西大学广西大学王中昭王中昭制作制作 设设Xij为飞机汽油为飞机汽油i 中所用标准汽油中所用标准汽油j的数量，这的数量，这样可知样可知X11+X12+X13+X14为飞机汽油为飞机汽油1总产量，总产量，总产量越多越好，所以有目标函数为总产量越多越好，所以有目标函数为 max X11+X12+X13+X14 约束条件之一：约束条件之一：X21+X22+X23+X24250000飞机汽油飞机汽油 辛烷数辛烷数 蒸汽压力蒸汽压力(gcm2)产量需求产量需求(L)1不小于不小于91不大于不大于9.9610-2越多越好越多越好2不小于不小于100 不大于不大于9.96

50、10-2不少于不少于250000表表4-9广西大学广西大学王中昭王中昭制作制作表表4-8:得到有关库存量和产量指标的约束条件：得到有关库存量和产量指标的约束条件：X11+X21380000,X12+X22265200,X13+X23408100,X14+X24130100,Xij0.标准汽油标准汽油 辛烷数辛烷数 蒸汽压力蒸汽压力(scm2)库存量库存量(L)1107.57.1110-238000029311.3810-22652003875.6910-2408100410828.4510-2130100广西大学广西大学王中昭王中昭制作制作 下面再列出有关辛烷数和蒸汽压力的约束条件下面再列出有