第1章 线性规划与单纯形法 第6节ppt课件

1、第第6 6节节 应应 用用 举举 例例 普通讲，一个经济、管理问题凡满足以下条件时，才干建立线性规划的模型。 (1) 要求解问题的目的函数能用数值目的来表示，且Z=f(x)为线性函数； (2) 存在着多种方案； (3) 要求到达的目的是在一定约束条件下实现的；这些约束条件可用线性等式或不等式来描画。 合理利用线材问题合理利用线材问题现要做现要做100100套钢架，每套需用长为套钢架，每套需用长为2.9m2.9m，2.1m2.1m和和1.5m1.5m的元钢各一根。知原料长的元钢各一根。知原料长7.4m7.4m，问应如何下，问应如何下料，运用的原资料最省。料，运用的原资料最省。解：一切合理的下料方

2、式列举如下解：一切合理的下料方式列举如下 8种方式运用的原料根数即为决策变量，按余料从小到大给各变量编号，问题归结为如下线性规划 0,)3(1004323)2(100322)1(10024 . 11 . 19 . 08 . 03 . 02 . 01 . 00minmin876543218653217654364218765432187654321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzxxxxxxxxz或或 假设仅选取余料长小于0.9m的套裁方案 设按方案下料的原资料根数为x1,方案为x2，方案为x3，方案为x4,方案为x5。可列出以下数学模型： 0,100323100

3、2210028 . 03 . 02 . 01 . 00min54321532154342154321xxxxxxxxxxxxxxxxxxxxz 最优下料方案：按方案下料30根，方案下料10根，方案下料50根， 需90根原资料可以制造100套钢架。其他最优方案：方案下料40根，III方案下料30根，按IV方案下料20根， 需90根原资料可以制造100套钢架。 配料问题 某工厂要用三种原资料C、P、H混合调配出三种不同规格的产品A、B、D。知产品的规格要求，产品单价，每天能供应的原资料数量及原资料单价，分别见表格。该厂应如何安排消费，使利润收入为最大? 解 以AC表示产品A中C的成分，AP表示产品

4、A中P的成分，依次类推，根据原资料比例限制)391(21,41,41,21 BBBBAAAAPCPC)401(, BBBBAAAAHPCHPC将(1-40)逐个代入(1-39)并整理得到0214121041414304143410212121 HPCHPCHPCHPCBBBBBBAAAAAA 根据原资料供应数量的限额100100100 HHHPPPCCCDBADBADBA9个变量分别用x1,x9表示，那么约束条件可表示为： 0,60100100021212104141430414341021212191963852741654654321321xxxxxxxxxxxxxxxxxxxxxxx 目

5、的函数为产品收入减去原资料本钱产品收入为：50A+35B+25D，即 50(x1+x2+x3)产品A 35(x4+x5+x6)产品B 25(x7+x8+x9)产品D 原资料本钱为：65C+25P+35H ，即 65(x1+x4+x7)原资料C 25(x2+x5+x8)原资料P 35(x3+x6+x9)原资料H所以，目的函数为975432110401030152515maxxxxxxxxz 产品方案问题 某厂消费I，II，III三种产品，都分别经A，B两道工序加工。设A工序可分别在设备A1或A2上完成， B工序可在B1，B2，B3三种设备上完成。知产品I可在A，B任何一种设备上加工；产品II可在

6、任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工，产品III只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据如表格所示，试安排最优消费方案，使该厂获利最大。 解 设产品I，II，III的产量分别为x1，x2，x3件。 产品I六种加工方案(A1, B1), (A1, B2), (A1, B3), (A2, B1), (A2, B2), (A2, B3)加工的产品I的数量分别用x11, x12, x13, x14, x15, x16表示；产品II两种加工方案(A1, B1), (A2, B1)加工的产品II的数量分别用x21, x22表示；产品III只需1种加工方案(

7、A2, B2)加工产品III的数量等于x3。 x1= x11+x12+x13+x14+x15+x16 x2= x21+x22 工厂的盈利为产品售价减去相应的原料费和设备加工费，产品加工量只受设备有效台时的限制。LP模型为 0400077700011444000886610000129777600010555)77(05. 0)1144(11. 0)8866(06. 0)129777(03. 0)10555(05. 0)50. 080. 2()()35. 00 . 2()(25. 025. 0(max161331512222114113221615142113121116133151222211

8、4113221615142113121132221161514131211ijxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz 消费与库存的优化安排 某工厂消费五种产品(i =1,5)，上半年各月对每种产品的最大市场需求量为dij(i =1, ,5; j =1, ,6)。知每件产品的单件售价为Si元，消费每件产品所需求工时为ai，单件本钱为Ci元；该工厂上半年各月正常消费工时为rj(j =1, ,6)，各月内允许的最大加班工时为rj ; Ci为加班单件本钱。又每月消费的各种产品如当月销售不完，可以库存。库存费用为Hi(元/件月)。假设1月初一切产品

9、的库存为零，要求6月底各产品库存量分别为ki件。现要求为该工厂制定一个消费方案，在尽能够利用消费才干的条件下，获取最大利润。 解 设xij, xij/分别为该工厂第i种产品在 第j个月在正常时间和加班时间内的消费量；yij为i种产品在第j月的销售量，ij为第i种产品第j月末的库存量。(1) 各种产品每月的消费量不能超越允许的消费才干，表示为： 51/516 , 1,6 , 1,iiiiijiijrxajrxa(2) 各种产品每月销售量不超越市场最大需求量)6,1, 6,1(, jidyijij(3) 每月末库存量等于上月末库存量加上该月产量减掉当月的销售量 iiiijijijjiijkjiyx

10、x 60/1, 06 , 1; 5 , 1 其中其中(4) 满足各变量的非负约束)6,1, 5,1(, 0, 0, 0, 0/ jiyxxijijijij (5) 该工厂上半年总盈利最大可表示为： 51615151/maxijijijiijiijiijiHxCxCySz 延续投资问题 某部门在今后五年内思索给以下工程投资，知： 工程A，从第一年到第四年每年年初需求投资，并于次年末回收本利115%； 工程B，第三年初需求投资，到第五年末能回收本利125%，但规定最大投资额不超越4万元； 工程C，第二年初需求投资，到第五年末能回收本利140%，但规定最大投资额不超越3万元； 工程D，五年内每年初可

11、购买公债，于当年末归还，并加利息6%。 该部门现有资金10万元，问它应如何确定给这些工程每年的投资额，使到第五年末拥有的资金的本利总额为最大?解： (1) 确定决策变量,以xiA,xiB,xiC,xiD (i=1,2,，5)分别表示第i年年初给工程A，B，C，D的投资额 (2) 投资额应等于手中拥有的资金额由于工程D每年都可以投资，并且当年末即能回收本息。所以该部门每年应把资金全部投出去，手中不该当有剩余的凝滞资金。因此 第一年：该部门年初拥有100000元，所以有 x1A+x1D=100000 第二年：因第一年给工程A的投资要到第二年末才干回收。所以该部门在第二年初拥有资金额仅为工程D在第一

12、年回收的本息x1D(1+6%)。于是第二年的投资分配是 x2A+x2C+x2D=1.06x1D第三年：第三年初的资金额是从工程A第一年投资及工程D第二年投资中回收的本利总和：x1A(1+15%)及x2D(1+6%)。于是第三年的资金分配为x3A+x3B+x3D=1.15x1A+1.06x2D第四年：与以上分析一样，可得x4A+x4D=1.15x2A+1.06x3D第五年：x5D=1.15x3A+1.06x4D 此外，由于对工程B、C的投资有限额的规定，即： x3B40000 x2C30000 (3) 目的函数问题是要求在第五年末该部门手中拥有的资金额到达 最 大 ， 与 五 年 末 资 金 有 关 的 变 量 是 ：x4A,x3B,x2C,x5D;因此这个目的函数可表示为 max z=1.15x4A+1.40 x2C+1.25x3B+1.06x5D (4) 数学模型 经过以上分析，这个与时间有关的投资问题可以