线性规划在工商管理中应用.pptx

《线性规划在工商管理中应用.pptx》由会员分享，可在线阅读，更多相关《线性规划在工商管理中应用.pptx（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、14.1、人力资源分配的问题4.2、生产计划的问题4.3、套裁下料问题4.4、配料问题4.5、投资问题主要内容第1页/共79页2 某昼夜服务的公交线路每天各时间段内所 需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?班次班次班次班次时间时间时间时间所需人数所需人数所需人数所需人数1 16:00-10:006:00-10:0060602 210:00-14:0010:00-14:0070703 314:00-18:0014:00-18:0060604 418:00-22:0018

2、:00-22:0050505 522:00-2:0022:00-2:0020206 62:00-6:002:00-6:003030例例例例1 14.14.1、人力资源分配的问题、人力资源分配的问题、人力资源分配的问题、人力资源分配的问题第2页/共79页3解：设xi表示第i班次时开始上班的司机和乘务人员数，可以知道在第i班工作的人数应包括第 i-1班次时开始上班的人员数和第i班次时开始上班的人员数，例如有x1+x270。又要求这六个班次时开始上班的所有人员最少，即要求x1+x2+x3+x4+x5+x6最小，这样我们建立如下的数学模型。目标函数：目标函数：min x1+x2+x3+x4+x5+x6

3、 约束条件：约束条件：x1+x660，x1+x270，x2+x360，x3+x450，x4+x520，x5+x630，x1,x2,x3,x4,x5,x60第3页/共79页4用“管理运筹学”软件可以求得此问题的解：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目标函数值=150第4页/共79页5 福安商场是个中型的百货商场，它对售货 人员的需求经过统计分析如下所示：星期一：15人；星期二：24人；星期三：25人；星期四：1

4、9人；星期五：31人；星期六：28人；星期日：28人。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要，又使配备的售货人员的人数最少?解：设解：设解：设解：设x x1 1为星期一开始休息的人数，为星期一开始休息的人数，为星期一开始休息的人数，为星期一开始休息的人数，x x2 2为星期二开始休为星期二开始休为星期二开始休为星期二开始休息的人数，息的人数，息的人数，息的人数，x x7 7为星期日开始休息的人数。目标是要求为星期日开始休息的人数。目标是要求为星期日开始休息的人数。目标是要求为星期日开始休息的人数。目标是

5、要求售货人员的总数最少。因为每个售货员都工作五天，休息售货人员的总数最少。因为每个售货员都工作五天，休息售货人员的总数最少。因为每个售货员都工作五天，休息售货人员的总数最少。因为每个售货员都工作五天，休息两天，所以只要计算出连续休息两天的售货员人数，也就两天，所以只要计算出连续休息两天的售货员人数，也就两天，所以只要计算出连续休息两天的售货员人数，也就两天，所以只要计算出连续休息两天的售货员人数，也就计算出了售货员的总数。把连续休息两天的售货员按照开计算出了售货员的总数。把连续休息两天的售货员按照开计算出了售货员的总数。把连续休息两天的售货员按照开计算出了售货员的总数。把连续休息两天的售货员按

6、照开始休息的时间分成始休息的时间分成始休息的时间分成始休息的时间分成7 7类，各类的人数分别为类，各类的人数分别为类，各类的人数分别为类，各类的人数分别为X X1 1，X X2 2，XX7 7，即有目标函数，即有目标函数，即有目标函数，即有目标函数:min X:min X1 1+X+X2 2+X+X3 3+X+X4 4+X+X5 5+X+X6 6+X+X7 7例例例例2 2第5页/共79页6模型：再按照每天所需售货员的人数写出约束条件，例如星期日需要28人，我们知道商场中的全体售货员中除了星期六开始休息和星期日开始休息的人外都应该上班，即有x1+x2+x3+x4+x528，喂！请问数学模型喂！

7、请问数学模型喂！请问数学模型喂！请问数学模型？第6页/共79页7上机求解得：x1=12,x2=0,x3=11,x4=5,x5=0,x6=8,x7=0,目标函数最小值=36.也就是说配备36个售货员，并安排12人休息星期一、二；安排11 人休息星期三、四；安排5人休息星期四、五；安排8人休息星期六、日。这 样的安排既满足了工作需要，又使配备的售货员最少。软件对此问题的解如下：目标函数最优值为：36 变量 最优解 相差值 x1 12 0 x2 0 0.333 x3 11 0 x4 5 0 x5 0 0 x6 8 0 x7 0 0第7页/共79页8约束 松驰/剩余变量 对偶价格1 0 -0.3332

8、 9 03 0 -0.3334 0 -0.3335 1 06 0 -0.3337 0 0由于所有约束条件的对偶价格都小于或等于0，故增加约束条件的常数项都不会使目标值变小。即增加售货员是不利的。但对于约束1、3、4、6来讲，减少一售货员会使目标函数值变小，是有利的。第8页/共79页9目标函数系数范围：变量 下限 当前值 上限X1 0 1 1.5X2 0.667 1 无上限X3 0 1 1.5X4 1 1 1X5 1 1 无上限X6 0 1 1X7 1 1 1.333安排星期二开始休息和星期五开始休息的人员可以无限制，此时最优解仍然不变。第9页/共79页10常数项范围：约束 下限 当前值 上限1

9、 19 28 282 无下限 15 243 15 24 424 10 25 41.55 无下限 19 206 16 31 38.57 28 28 36第10页/共79页11法二：设x1为星期一开始上班的人数，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星

10、期五 X1+X2+X3+X4+X531星期六 X2+X3+X4+X5+X628解解:函数值函数值=36,=36,X1=3,x2=5,X1=3,x2=5,x3=12,X4=0,x3=12,X4=0,x5=11,x6=0 x5=11,x6=0X7=5,X7=5,则周则周1 1休息人数为休息人数为周周3 3上班的上班的+周周2 2上上班的班的=12+5=17,=12+5=17,与与法一是一样的周法一是一样的周1 1开始休息仍为开始休息仍为17-17-5=125=12人人第11页/共79页12 明兴公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，这三种产品都要经过铸造、机加工和

11、装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。有关情况见表43；公司中可利用的总工时为：铸造8000小时，机加工12000小时和装配10000小时。公司为了获得最大利润，甲、乙、丙三种产品各生产多少件?甲、乙两种产品的铸造应多少由本公司铸造?应多少由外包协作？例例例例3 34.2、生产计划的问题、生产计划的问题第12页/共79页13表4-3解：设x1、x2、x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，设x4、x5分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。计算每件产品的利润分别如下：工时与成本工时与成本工时与

12、成本工时与成本甲甲甲甲乙乙乙乙丙丙丙丙每件铸造工时每件铸造工时每件铸造工时每件铸造工时(小时小时小时小时)5 510107 7每件机加工工时每件机加工工时每件机加工工时每件机加工工时(小时小时小时小时)6 64 48 8 每件装配工时（小时每件装配工时（小时每件装配工时（小时每件装配工时（小时)3 32 22 2 自产铸件每件成本自产铸件每件成本自产铸件每件成本自产铸件每件成本(元元元元)3 35 54 4外协铸件每件成本外协铸件每件成本外协铸件每件成本外协铸件每件成本(元元元元)5 56 6 机加工每件成本机加工每件成本机加工每件成本机加工每件成本(元元元元)2 21 13 3 装配每件成本

13、装配每件成本装配每件成本装配每件成本(元元元元)3 32 22 2每件产品售价每件产品售价每件产品售价每件产品售价(元元元元)232318181616第13页/共79页14产品甲全部自制的利润=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(元)工时与成本工时与成本工时与成本工时与成本甲甲甲甲乙乙乙乙丙丙丙丙每件铸造工时每件铸造工时每件铸造工时每件铸造工时(小时小时小时小时)5 510107

14、7每件机加工工时每件机加工工时每件机加工工时每件机加工工时(小时小时小时小时)6 64 48 8 每件装配工时（小时每件装配工时（小时每件装配工时（小时每件装配工时（小时)3 32 22 2 自产铸件每件成本自产铸件每件成本自产铸件每件成本自产铸件每件成本(元元元元)3 35 54 4外协铸件每件成本外协铸件每件成本外协铸件每件成本外协铸件每件成本(元元元元)5 56 6 机加工每件成本机加工每件成本机加工每件成本机加工每件成本(元元元元)2 21 13 3 装配每件成本装配每件成本装配每件成本装配每件成本(元元元元)3 32 22 2每件产品售价每件产品售价每件产品售价每件产品售价(元元元元

15、)232318181616第14页/共79页15建立数学模型如下：目标函数：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中。详见上机计算。工时与成本工时与成本工时与成本工时与成本甲甲甲甲乙乙乙乙丙丙丙丙每件铸造工时每件铸造工时每件铸造工时每件铸造工时(小时小时小时小时)5 510107 7每件机加工工时每件机加工

16、工时每件机加工工时每件机加工工时(小时小时小时小时)6 64 48 8 每件装配工时（小时每件装配工时（小时每件装配工时（小时每件装配工时（小时)3 32 22 2第15页/共79页16目标函数最优值为：29400 变量 最优解 相差值 x1 1600 0 x2 0 2 x3 0 13.1 x4 0 0.5 x5 600 0 结果分析：最大的利润为结果分析：最大的利润为2940029400元，其最优的生产计划为全部元，其最优的生产计划为全部由自己生产的甲产品由自己生产的甲产品16001600件，铸造外协、其余自制生产乙产品件，铸造外协、其余自制生产乙产品600600件，而丙产品不生产。从相差值

17、一栏中可知，如果全部由自己生产件，而丙产品不生产。从相差值一栏中可知，如果全部由自己生产的乙产品的利润再增加的乙产品的利润再增加2 2元达到每件元达到每件1212元利润，那么全部自制的乙元利润，那么全部自制的乙产品才有可能上马生产，否则乙产品还是铸造外协、其余自制的利产品才有可能上马生产，否则乙产品还是铸造外协、其余自制的利润更大。同样丙产品的利润要再增加润更大。同样丙产品的利润要再增加13.113.1元达到每件利润元达到每件利润20.120.1元，元，丙产品才有可能上马生产；铸造外协、其余自制的甲产品利润再增丙产品才有可能上马生产；铸造外协、其余自制的甲产品利润再增加加0.50.5元达到元达

18、到13.513.5元，才有可能上马生产。元，才有可能上马生产。第16页/共79页17约束 松驰/剩余变量对偶价格100.3202.25340000 从对偶价格栏可知铸造每工时的对偶价格为0.3元，机加工每工时的对偶价格为2.25元，装配每工时的对偶价格为零元。这样如果有人以低于铸造和机加工的对偶价格来提供铸造及机加工的工时则可以购入来获取差价（例如外协铸造工时价格低于0.3元，则外协铸造合算)。同样如果有人要购买该公司的铸造与机加工的工时，则出价必须扣除成本外，还必须高于其对偶价格，否则就不宜出售。至于装配每工时的对偶价格为零，这是由于在此生产计划下还有4000个装配工时没有完。第17页/共7

19、9页18 对偶价格不是市场价格，在作市场决策时，某种资源市场价格低于对偶价格时，可适量买进这种资源，组织和增加生产。相反当市场价格高于对偶价格时，可以卖出资源而不安排生产或提高产品的价格。注意啊！注意啊！注意啊！注意啊！第18页/共79页19目标函数系数范围：变量 下限 当前值 上限X1 14 15 无上限X2 无下限 10 12X3 无下限 7 20.1X4 无下限 13 13.5X5 8.667 9 10 从目标函数决策变量系数一栏中知道，当全部从目标函数决策变量系数一栏中知道，当全部从目标函数决策变量系数一栏中知道，当全部从目标函数决策变量系数一栏中知道，当全部自己生产的每件甲产品的利润

20、在自己生产的每件甲产品的利润在自己生产的每件甲产品的利润在自己生产的每件甲产品的利润在1414到到到到+内变化时，内变化时，内变化时，内变化时，其最优解不变；全部自己生产的每件乙产品的利润其最优解不变；全部自己生产的每件乙产品的利润其最优解不变；全部自己生产的每件乙产品的利润其最优解不变；全部自己生产的每件乙产品的利润只要不超过只要不超过只要不超过只要不超过1212元，则其最优解不变；当每件丙产品元，则其最优解不变；当每件丙产品元，则其最优解不变；当每件丙产品元，则其最优解不变；当每件丙产品的利润不超过的利润不超过的利润不超过的利润不超过20.120.1元时，则其最优解不变；当铸造元时，则其最

21、优解不变；当铸造元时，则其最优解不变；当铸造元时，则其最优解不变；当铸造外协其余自制的每件甲产品的利润不超过外协其余自制的每件甲产品的利润不超过外协其余自制的每件甲产品的利润不超过外协其余自制的每件甲产品的利润不超过13.513.5元时，元时，元时，元时，其最优解不变；当铸造外协，其余自制的每件乙产其最优解不变；当铸造外协，其余自制的每件乙产其最优解不变；当铸造外协，其余自制的每件乙产其最优解不变；当铸造外协，其余自制的每件乙产品的利润在品的利润在品的利润在品的利润在8.6678.667到到到到1010元内变化时，则其最优解不元内变化时，则其最优解不元内变化时，则其最优解不元内变化时，则其最优

22、解不变。在这里当某产品利润变化时都假设其余产品的变。在这里当某产品利润变化时都假设其余产品的变。在这里当某产品利润变化时都假设其余产品的变。在这里当某产品利润变化时都假设其余产品的利润是不变的。利润是不变的。利润是不变的。利润是不变的。第19页/共79页20常数项范围约束 下限 当前值 上限1 0 8000 100002 9600 12000 200003 6000 10000 无上限从约束条件右边常数变化范围栏可知，当铸造工时在0到10000小时间变化时其对偶价格都为0.3元；当机加工工时在9600到20000小时内变化时，其对偶价格都为2.25元；当装配工时在6000到+内变化时，其对偶价

23、格都为零。也就是说当常数项超出上面的范围时其对偶价格可能已变，这时某种资源的市场价格与对偶价格的关系随之发生变化。第20页/共79页21永久机械厂生产、三种产品。每种产品均要经过A、B两道工序加工。设该厂有两种规格的设备能完成A工序，它们以A1、A2表示；有三种规格的设备能完成B工序，它们以B1，B2，B3表示。产品可在A、B的任何规格的设备上加工。产品可在任何一种规格的A设备上加工，但完成B工序时，只能在B1设备上加工。产品只能在A2与B2设备上加工。已知在各种设备上加工的单件工时、原料单价、产品销售单价、各种设备的有效台时以及满负荷操作时的设备费用如表44示，要求制定最优的产品加工方案，使

24、该厂利润最大。例例4第21页/共79页22表4-4设设设设备备备备 产品单件工时产品单件工时产品单件工时产品单件工时设备的设备的设备的设备的有效台有效台有效台有效台时时时时满负荷时满负荷时满负荷时满负荷时的设备费的设备费的设备费的设备费用用用用A A1 15 5101060006000300300A A2 27 79 912121000010000321321B B1 16 68 840004000250250B B2 24 4111170007000783783B B3 37 740004000200200原料单价原料单价原料单价原料单价(元件元件元件元件)0.250.250.350.350

25、.50.5销售单价销售单价销售单价销售单价(元件元件元件元件)1.251.252 22.82.8第22页/共79页23解：设Xijk表示第i种产品在第j种工序上(A工序用1表示，B工序用2表示)的第k种设备上加工的数量。如x123表示第种产品在B道工序上用B3设备加工的数量。则约束 5x111+10 x2116000，(设备A1)7x112+9x212+12x31210000，(设备A2)6x121+8x2214000，(设备B1)，4x122+11x3227000 (设备B2),7x1234000 (设备B3)设设备备产品单件工时产品单件工时产品单件工时产品单件工时设备的设备的设备的设备的有

26、效台有效台有效台有效台时时时时满负荷时满负荷时满负荷时满负荷时的设备费的设备费的设备费的设备费用用用用A A1 15,X5,X11111110,X10,X21121160006000300300A A2 27,X7,X1121129,X9,X21221212,X12,X3123121000010000321321B B1 16,X6,X1211218,X8,X22122140004000250250B B2 24,X4,X12212211,X11,X32232270007000783783B B3 37,X7,X12312340004000200200第23页/共79页24设Xijk表示第i种

27、产品在第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工序上加工的数量相等)设设备备产品单件工时产品单件工时产品单件工时产品单件工时设备的设备的设备的设备的有效台有效台有效台有效台时时时时满负荷时满负荷时满负荷时满负荷时的设备费的设备费的设备费的设备费用用用用A A1 15,X5,X11111110,X10,X21121160006000300300A A2 27,

28、X7,X1121129,X9,X21221212,X12,X3123121000010000321321B B1 16,X6,X1211218,X8,X22122140004000250250B B2 24,X4,X12212211,X11,X32232270007000783783B B3 37,X7,X12312340004000200200应该是0才合理第24页/共79页25设设设设备备备备 产品单件工时产品单件工时产品单件工时产品单件工时设备的有设备的有设备的有设备的有效台时效台时效台时效台时满负荷时的满负荷时的满负荷时的满负荷时的设备费用设备费用设备费用设备费用A A1 15,X5,

29、X11111110,X10,X21121160006000300300A A2 27,X7,X1121129,X9,X21221212,X12,X3123121000010000321321B B1 16,X6,X1211218,X8,X22122140004000250250B B2 24,X4,X12212211,X11,X32232270007000783783B B3 37,X7,X12312340004000200200原料单价原料单价原料单价原料单价(元件元件元件元件)0.250.250.350.350.50.5销售单价销售单价销售单价销售单价(元件元件元件元件)1.251.252

30、 22.82.8应该是1.25(X121+X122+X123)-0.25(X111+X112)才合理。第25页/共79页26设设设设备备备备 产品单件工时产品单件工时产品单件工时产品单件工时设备的有设备的有设备的有设备的有效台时效台时效台时效台时满负荷时的满负荷时的满负荷时的满负荷时的设备费用设备费用设备费用设备费用A A1 15,X5,X11111110,X10,X21121160006000300300A A2 27,X7,X1121129,X9,X21221212,X12,X3123121000010000321321B B1 16,X6,X1211218,X8,X22122140004

31、000250250B B2 24,X4,X12212211,X11,X32232270007000783783B B3 37,X7,X12312340004000200200第26页/共79页27 5x111+10 x2116000，(设备A1)7x112+9x212+12x31210000，(设备A2)6x121+8x2214000，(设备B1)，4x122+11x3227000 (设备B2),7x1234000 (设备B3)X111+X112-X121-X122 X123=0，(产品在A、B工序上加工的数量相等)X211+X212-X221=0,(产品在A、B工序上加工的数量相等)X312

32、-X322=0,(产品在A、B工序上加工的数量相等)第27页/共79页28模型模型 将模型输入计算机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。第28页/共79页29 由于本题要求的决策变量的单位是件，所以答案应该是整数。本题与例1、例2、例3实质上都是整数规划的问题，但是这类问题可以作为线性规划的问题来解，有些如例1，例2，例3的答案都是整数，而有些如本题答案是非整数，可以将答案舍入成整

33、数也可能得到满意的结果。如本题如果用软件的整数规划的来解，得到的答案为x111=1200，x112=230，X211=0，X212 =500，X312=324，X121=0，X221=500，X122=859，X322=324，X123=571.最优值为1146.3622。其最优解正好与四舍五入线性规划结果一样的。两种方法的最优值也相差无几，只差0.3元。第29页/共79页30 本问题最优的方案为生产产品1430件（X111+X112=1200+230=X121+X122+X123=0+859+571=1430)，产品第A道工序由A1设备加工1200件，由A2设备加工230件。产品的第B道工序

34、由B2设备加工859件，由B3设备加工571件。生产产品500件，它的第A道工序全部由A2设备加工，它的第B道工序全部由B1设备加工。X212=X221=500。生产产品324件，其第A道工序全部由A2加工，其第B道工序全部由B2设备加工，X312=X322=324，这样能使工厂获得最大利润1146.3元。生产数量生产数量生产数量生产数量A A1 1X X111111=1200=1200X X211211=0=0A A2 2X X112112=230=230X X212212=500=500X X312312=324=324B B1 1X X121121=0=0X X221221=500=50

35、0B B2 2X X122122=859=859X X322322=324=324B B3 3X X123123=571571第30页/共79页31如果分别按实际产品和原材料来计算则有：Max z=-0.5x111-0.6352x112-0.85x211-0.6389x212-0.8852x312+0.875x121+0.8024x122+0.9x123+1.5x221+1.5691x3225x111+10 x2116000，(设备A1)7x112+9x212+12x31210000，(设备A2)6x121+8x2214000，(设备B1)，4x122+11x3227000 (设备B2),7x

36、1234000 (设备B3)X111+X112-X121-X122 X1230，(产品在A工序加工的数量大于B加工的数量)X211+X212-X2210,(产品在A工序上加工数量天于B的数量)X312-X3220,(产品在A工序上加工的数量大于B)第31页/共79页32结果如下：本问题最优的方案为生产产品1200件（X111+X112=1200+0=X121+X122+X123=0+628.572+571.428=1200)，产品第A道工序由A1设备加工1200件，由A2设备加工0件。产品的第B道工序由B2设备加工628.572件，由B3设备加工571.428件。生产产品500件，它的第A道工

37、序全部由A2设备加工，它的第B道工序全部由B1设备加工。X212=X221=500。生产产品324件，其第A道工序全部由A2加工，其第B道工序全部由B2设备加工，X312=X322=407.79，这样能使工厂获得最大利润1128.091元。比上方法要少。此法合理。第32页/共79页33 某工厂要做100套钢架，每套用长为2.9m，2.1 m 和1.5 m的圆钢各一根。已知原料每根长7.4m，问应如何下料，可使所用原料最省。F 解：最简单的做法是，在每根原材料上截取2.9m、2.1m和1.5m的圆钢各一根组成一套，每根原材料省下料头0.9m。为了做100套钢架，需要原材料100根，共有90m的料

38、头。若改用套裁可以节约不少原材料，为了找到一个省料的套裁方案，先设计出较好的几个下料方案，所谓较好，第一要求每个方案下料后的料头较短，第二要求这些方案的总体能裁下所有各种规格的圆钢，并且不同方案有着不同的各种所需圆钢的比。这样套裁才能满足对各种不同规格圆钢的需要并达到省料的目的。为此设计出以下5种下料方案以供套裁用。见表45。例例例例5 54.34.3、套裁下料问题、套裁下料问题、套裁下料问题、套裁下料问题第33页/共79页34表45。下料数下料数方案方案（根）（根）长度长度2.9120102.1002211.531203合计合计7.47.37.27.16.6料头料头00.10.20.30.8

39、其它方案的料头较多，不考虑，如其它方案的料头较多，不考虑，如1 1根根2.9,12.9,1根根2.1,12.1,1根根1.5,1.5,料头为料头为0.9m0.9m第34页/共79页35 解：为了用最少的原材料得到100套钢架，需要混合使用上述五种下料方案，设按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根，按

40、方案下料50根(即x1=30，x2=10，x3=0，x4=50，x5=0)，只需90根原材料(即目标函数最小值为90)即可制造100套钢架。第35页/共79页36思考如果只取方思考如果只取方思考如果只取方思考如果只取方案前四个或前三案前四个或前三案前四个或前三案前四个或前三个或再增加其它个或再增加其它个或再增加其它个或再增加其它方案，结果如何方案，结果如何方案，结果如何方案，结果如何？第36页/共79页37其它方案列表（不是所有）(P46-5b)12345678910111213142.9120101100000002.1002211032100001.531203120124321合计合计7

41、.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 min Xmin X1 1+X+X2 2+X+X3 3+X+X4 4+X X5 5+X+X6 6+X+X7 7+X+X8 8+X+X9 9+X+X1010+X+X1111+X+X1212+X+X1313+X+X1414 约束条件：约束条件：约束条件：约束条件：X X1 1+2X+2X2 2+X+X4 4 +X+X6 6+X+X7 7100100，2X2X3 3+2X2X4 4+X+X5 5+X+X6 6+3X+3X8 8+2X+2X

42、9 9+X+X1010100100，3X3X1 1+X+X2 2+2X+2X3 3+3X+3X5 5+X+X6 6+2X+2X7 7+X+X9 9+2X+2X1010+4X+4X1111+3X+3X1212+2X+2X1313+X+X1414100100第37页/共79页38模型模型 将模型输入计算机解为：目标函数值解为：目标函数值=90,x1=0,x2=40,x3=30,x4=20,其它其它x为为0。从这里看出模型。从这里看出模型有多个解。料头多的方案一有多个解。料头多的方案一般为般为0。第38页/共79页39M 注意！在建立此数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一

43、些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这个套用方案就不是可行解了。约束条件用大于等于号时，目标函数本来求所用原材料最少和求料头最少是一样的，但由于在第一个下料方案中料头为零，无论按第一下料方案下多少根料，料头都为零，也就是说不管第一下料方案下料是200根还是150都可使目标函数值达到最小，这显然不合理。所以目标函数就一定要求原材料最少。如果所有方案料头都不为零，则可用料头作为最小值函数变量。第39页/共79页40思考：如果原材不止一种规格，如还有10M长的原材，则如何设计模型？第40页/共79页41 某工厂要用三种原料1，2，3混合调配出三种不同规格的产品

44、甲、乙、丙，已知产品的规格要求、产品的单价、每天能供应的原材料数量及原材料单价，分别见表4-6和表47。该厂应如何安排生产，使利润收入为最大?产品名称产品名称产品名称产品名称 规格要求规格要求规格要求规格要求 单价单价单价单价(元千克元千克元千克元千克)甲甲甲甲原材料原材料原材料原材料1 1不少于不少于不少于不少于5050，原材料原材料原材料原材料2 2不超过不超过不超过不超过25255050 乙乙乙乙原材料原材料原材料原材料1 1不少于不少于不少于不少于2525，原材料原材料原材料原材料2 2不超过不超过不超过不超过5050 3535丙丙丙丙 不限不限不限不限2525表表4-64-6 现在讲

45、第四个问题：4.4配料问题例例例例6 6第41页/共79页42 解：设xij表示第i种产品中原材料j的含量(分别用 产品1，2，3表示产品甲、乙、丙)。例如x23就表 示乙产品中第3种原材料的含量，目标是使利润 最大，利润的计算公式如下：原材料名称原材料名称原材料名称原材料名称 每天最多供应量每天最多供应量每天最多供应量每天最多供应量 单价（元单价（元单价（元单价（元/千克）千克）千克）千克）1 110010065652 210010025253 360603535第42页/共79页43由表4-6得到：X110.5(X11+X12+X13)，(甲中原料1占甲产品数量不少于50%.)X120.2

46、5(X11+X12+X13)X210.25(X21+X22+X23)X220.5(X21+X22+X23)由表由表4-5得到：得到：X11+X21+X31100X12+X22+X32100X13+X23+X3360第43页/共79页44得问题模型如下(必须整理后上机求解）：第44页/共79页45模型模型 将模型输入计算机解为：解为：解为：解为：x x1111=100=100，x x1212=50,x=50,x1313=50=50，其余的，其余的，其余的，其余的x xij ij=0=0，也就是说每天只生产甲产品也就是说每天只生产甲产品也就是说每天只生产甲产品也就是说每天只生产甲产品200200千

47、克，分别需要用千克，分别需要用千克，分别需要用千克，分别需要用1 1原料原料原料原料100100千千千千克，克，克，克，2 2原料原料原料原料5050千克，千克，千克，千克，3 3原料原料原料原料5050千千千千克。其它乙、丙产品不生产。克。其它乙、丙产品不生产。克。其它乙、丙产品不生产。克。其它乙、丙产品不生产。目标函数值目标函数值目标函数值目标函数值=500=500元元元元第45页/共79页46 VARIABLE VALUE REDUCED COST X11 100.000000 0.000000 X12 50.000000 0.000000 X13 50.000000 0.000000

48、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 从相差值中可看出：只有当从相差值中可看出：只有当从相差值中可看出：只有当从相差值中可看出：只有当X X2121的系数从的系数从的系数从的系数从-30-30增加增加增加增加1515元元元元则乙产品才生产，只有当则乙产品才生产，只有当则乙产品才生产，只有当则乙产品才生产，只有当X X3131和和和和X X3333的系数分别从的系数分

49、别从的系数分别从的系数分别从-40-40增加增加增加增加4545元和从元和从元和从元和从-10-10增加增加增加增加1010元则丙产品才生产，元则丙产品才生产，元则丙产品才生产，元则丙产品才生产，第46页/共79页47 汽油混合问题。一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1，2，3，4种标准汽油，其特性和库存量列于表48中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种飞机汽油的性能指标及产量需求列于表49中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号飞机汽油满足需求，并使得

50、1号飞机汽油产量最高。例例7第47页/共79页48设Xij为飞机汽油i 中所用标准汽油j的数量，这样可知X11+X12+X13+X14为飞机汽油1总产量，总产量越多越好，所以有目标函数为 max X11+X12+X13+X14 约束条件之一：X21+X22+X23+X24250000飞机汽油飞机汽油飞机汽油飞机汽油 辛烷数辛烷数辛烷数辛烷数 蒸汽压力蒸汽压力蒸汽压力蒸汽压力(g(gcmcm2 2)产量需求产量需求产量需求产量需求(L)(L)1 1不小于不小于不小于不小于9191不大于不大于不大于不大于9.96109.9610-2-2越多越好越多越好越多越好越多越好2 2不小于不小于不小于不小于