第1章+线性规划与单纯形法-第6节.pdf
第6节应 用 举 例第6节应 用 举 例一般讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划的模型：(1)要求解问题的目标函数能用数值指标来表示，且Z=f(x)为线性函数；(2)存在着多种方案；(3)要求达到的目标是在一定约束条件下实现的；这些约束条件可用线性等式或不等式来描述。举例说明线性规划在经济管理等方面的应用例10 合理利用线材问题现要做100套钢架，每套需用长为2.9m，2.1m和1.5m的元钢各一根。已知原料长7.4m，问应如何下料，使所用的原材料最省。解解 最简单做法是，在每一根原材料上截取2.9m，2.1m和1.5m的元钢各一根组成一套，每根原材料剩下料头0.9m（7.4-2.9-2.1-1.5=0.9)。为了做100套钢架，需用原材料100根，共有90m料头 若改为用套裁，这可以节约原材料。下面有几种套裁方案，都可以考虑采用表1-11 套裁方案方 案 下料根数 长度(m)2.9 2.1 1.5 1 0 3 2 1 2 2 1 2 1 3 合计 料头 7.40 7.30.17.20.27.10.36.60.8 为了得到100套钢架，需要混合使用各种下料方案。设按方案下料的原材料根数为x1,方案为x2，方案为x3，方案为x4,方案为x5。根据表1-11的方案，可列出以下数学模型：=+=+=+=0,1003231002210028.03.02.01.00min54321532154342154321xxxxxxxxxxxxxxxxxxxxz2.9m的数量2.1m的数量1.5m的数量余料数量在以上约束条件中加入人工变量x6,x7,x8；然后用表1-12进行计算。cj 0 -0.1-0.2-0.3 -0.8-M-M-M i CB XBb x1 x2 x3 x4 x5 x6x7x8 -M-M-M x6 x7 x8 100 100 100 1 0 32 0 1 0 2 2 1 2 0 0 1 0 1 0 0 0 1 0 0 0 1 100/1 100/1 cj-zj 4M-0.1+3M-0.2+4M-0.3+3M-0.8+4M0 0 0 Max第1次计算cj 0-0.1-0.2-0.3-0.8-M-M-M i CB XBb x1x2 x3 x4 x5 x6x7x8 -M-M 0 x6x7x1200/3 100 100/3 0015/3 0 1/3-2/3 2 2/3 1 2 0-1 1 1 1 0 0 0 1 0-1/3 0 1/3 200/3 100/2 cj-zj 0-0.1+5/3M-0.2+4/3M-0.3+3M-0.80 0-4/3M cj 0-0.1-0.2-0.3-0.8-M-M-M CB XBb x1 x2 x3 x4 x5 x6 x7 x8 i -M-0.3 0 x6 x4 x1 50/3 50 100/3 0 0 1 5/3 1 1/3-5/3 1 2/3 0 1 0-3/2 1/2 1 100-1/2 1/2 0-5-2 1 150/15 100/1 cj-zj 0-0.1+5/3M0.1-5/3M0-0.65-3/2M00.15-3/2M-4/3M 第2次计算cj 00.1 0.2 0.30.8-M-M-M CB XB b x1x2x3x4x5 x6 x7 x8 0.1-0.3 0 x2 x4 x1 10 50 30 0011 0 0-11 1 0 1 0-9/101/3 13/103/5 0-1/5-3/101/3 1/10-1/5 0 2/5 cj-zj 00 0 0-0.74-M+0.06-M+0.12-M-0.02 有非基变量的检验数为零，所以存在有非基变量的检验数为零，所以存在多重多重最优解最优解例1-11的 最终计算表（第3次计算）由计算得到最优下料方案是：按方案下料30根；方案下料10根；方案下料50根。即需90根原材料可以制造100套钢架。例11 配料问题 某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表1-13和表1-14。该厂应如何安排生产，使利润收入为最大?解如以AC表示产品A中C的成分，AP表示产品A中P的成分，依次类推。产品名称 规 格 要 求 单价（元/kg）A 原材料 C 不少于 50%原材料 P 不超过 25%50 B 原材料 C 不少于 25%原材料 P 不超过 50%35 D 不限 25 表1-13根据表1-13有：)391(21,41,41,21BBBBAAAAPCPC这里AC+AP+AH=A；BC+BP+BH=B (1-40)将(1-40)逐个代入(1-39)并整理得到0214121041414304143410212121+HPCHPCHPCHPCBBBBBBAAAAAA表 1-14 原材料供应数量的限额 表1-14表明这些原材料供应数量的限额。加入到产品A、B、D的原材料C总量每天不超过100kg，P的总量不超过100kg，H总量不超过60kg原材料名称 每天最多供应量（kg）单价/(元/kg)C 100 65 P 100 25 H 60 35 约束条件：AC+BC+DC100AP+BP+DP100AH+BH+DH60 在约束条件中共有9个变量，为计算和叙述方便，分别用x1,x9表示。令x1=Ac,x2=Ap,x3=AH,x4=BC,x5=BP,x6=BH,x7=DC,x8=DP,x9=DH.约束条件可表示为：+0,60100100021212104141430414341021212191963852741654654321321xxxxxxxxxxxxxxxxxxxxxxx?目标函数 目的是使利润最大，即产品价格减去原材料的价格为最大。产品价格为：50(x1+x2+x3)产品A35(x4+x5+x6)产品B25(x7+x8+x9)产品D 原材料价格为：65(x1+x4+x7)原材料C25(x2+x5+x8)原材料P35(x3+x6+x9)原材料H 为了得到初始解，在约束条件中加入松弛变量x10 x16，得到数学模型：例11的线性规划模型()=+=+=+=+=+=+=+=0,601001000212121041414304143410212121010401030152515max18109116963158521474113654126541132110321161514131211109754321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz?约束条件目标函数最优解：每天只生产产品A为200kg，分别需要用原料C为100kg；P为50kg;H为50kg 总利润是z=500元/天例12 生产与库存的优化安排 某工厂生产五种产品(i=1,5)，上半年各月对每种产品的最大市场需求量为di j(i=1,5;j=1,6)。已知每件产品的单件售价为Si元，生产每件产品所需要工时为ai，单件成本为Ci元；该工厂上半年各月正常生产工时为rj(j=1,6)，各月内允许的最大加班工时为rj;Ci为加班单件成本。又每月生产的各种产品如当月销售不完，可以库存。库存费用为Hi(元/件月)。假设1月初所有产品的库存为零，要求6月底各产品库存量分别为ki件。现要求为该工厂制定一个生产计划，在尽可能利用生产能力的条件下，获取最大利润。解：决策变量 设xi j,xij分别为该工厂第i种产品的第j个月在正常时间和加班时间内的生产量 yi j为i种产品在第j月的销售量 i j为第i种产品第j月末的库存量线性规划模型(1)各种产品每月的生产量不能超过允许的生产能力，表示为：=51516,1,6,1,ijijiijijijrxajrxa?(2)各种产品每月销售量不超过市场最大需求量yi jdi j (i=1,5;j=1,6)(3)每月末库存量等于上月末库存量加上该月产量减掉当月的销售量iiiijijijjiijkjiyxx=+=601,06,1;5,1其中?(4)满足各变量的非负约束xi j0,xij0,yij0,(i=1,5；j=1,6)i j0(i=1,5；j=1,5)(5)该工厂上半年总盈利最大可表示为：目标函数=51615161maxijijijiijiijiijiHxCxCySz例13 连续投资问题某部门在今后五年内考虑给下列项目投资，已知：项目A，从第一年到第四年每年年初需要投资，并于次年末回收本利115%；项目B，第三年初需要投资，到第五年末能回收本利125%，但规定最大投资额不超过4万元；项目C，第二年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过3万元；项目D，五年内每年初可购买公债，于当年末归还，并加利息6%该部门现有资金10万元，问它应如何确定给这些项目每年的投资额，使到第五年末拥有的资金的本利总额为最大?解：(1)确定决策变量这是一个连续投资问题，与时间有关但这里设法用线性规划方法，静态地处理以xiA,xiB,xiC,xiD(i=1,2,，5)分别表示第i年年初给项目A，B，C，D的投资额，它们都是待定的未知变量。根据给定的条件，将变量列于表1-15中表 1-15项目 第一年 第二年 第三年 第四年 第五年 A x1A x2A x3A x4A/B/x3B/C/x2C/D x1D x2D x3D x4D x5D 投资周期投资周期(2)投资额应等于手中拥有的资金额 由于项目D每年都可以投资，并且当年末即能回收本息。所以该部门每年应把资金全部投出去，手中不应当有剩余的呆滞资金。因此 第一年：该部门年初拥有100000元，所以有x1A+x1D=100000 第二年：因第一年给项目A的投资要到第二年末才能回收。所以该部门在第二年初拥有资金额仅为项目D在第一年回收的本息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)数学模型 这个与时间有关的投资问题可以用以下线性规划模型来描述：=+=+=+=+=5,2,1,0,3000040000006.115.1006.115.1006.115.1006.110000006.14.125.115.1max234353244213331222115224?ixxxxxxxxxxxxxxxxxxxxxxxxxxxxziDiCiBiACBDADDADADADBADDCADADCBA约束条件：目标函数：(5)用两阶段单纯形法计算结果得到 第一年：x1A=34783元，x1D=65217元 第二年：x2A=39130元，x2C=30000元，x2D=0 第三年：x3A=0，x3B=40000元，x3D=0 第四年：x4A=45000元，x4D=0 第五年：x5D=0 到第五年末该部门拥有资金总额为143,750元，即盈利43.75%。第一章 作业 习题1.6 习题1.10（老版1.8）习题1.11（老版1.9）上机（1）习题1.6分别用单纯形法中的大 M 法和两阶段法求解下述线性规划问题，并指出属哪一类解。（1）max z=2x1+3x2-5x3x1+x2+x3=72x1-5x2+x310 x1，x2，x30（2）min z=2x1+3x2+x3x1+4x2+2x383x1+2x26 x1，x2，x30（3）max z=10 x1+15x2+12x35x1+3x2+x3 9-5x1+6x2+15x3152x1+x2+x3 5 x1，x2，x30（4）max z=2x1-x2+2x3x1+x2+x36-2x1+x322x2-x3 0 x1，x2，x30习题1.10 某糖果厂用原料 A、B、C 加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中 A、B、C 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如表 1-17 表示。问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立这个问题的线性规划的数学模型。表1-17原 料甲乙丙原料成本（元/千克）每月限制用量（千克）ABC60%20%15%60%50%2.001.501.00200025001200加工费（元/千克）0.500.400.30售 价3.402.852.25习题1.11 某厂生产三种产品，。每种产品要经过 A，B 两道工序加工。设该厂有两种规格的设备能完成 A 工序，它们以 A1，A2表示；有三种规格的设备能完成 B 工序，它们以 B1，B2，B3表示。产品可在 A，B 任何一种规格设备上加工。产品可在任何规格的 A 设备上加工，但完成 B 工序时，只能在 B1设备上加工；产品只能在 A2与 B2设备上加工。已知在各种机床设备的单件工时，原材料费，产品销售价格，各种设备有效台时以及满负荷操作时机床设备的费用如下表（表 1-18），要求安排最优的生产计划，使该厂利润最大。表 1-18产 品设备设备有效台时满负荷时的设备费用（元）A1A2B1B2B35764710981211600010000400070004000300321250783200原料费（元/件）0.250.350.50单价（元/件）1.252.002.80
