《第1章 线性规划与单纯形法-第6节课件》由会员分享，可在线阅读，更多相关《第1章 线性规划与单纯形法-第6节课件（38页珍藏版）》请在金锄头文库上搜索。
1、,运筹学(第三版),运筹学教材编写组 编 清华大学出版社,第一章 线性规划与单纯形型法 第6节 应用举例,钱颂迪 制作,第6节应 用 举 例,一般讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划的模型。 (1) 要求解问题的目标函数能用数值指标来表示，且Z=f(x)为线性函数； (2) 存在着多种方案； (3) 要求达到的目标是在可以量化的，并要有足够数据的一定约束条件下实现的；这些约束条件可用线性等式或不等式来描述。 下面举例说明线性规划在经济管理等方面的应用。,例10 合理利用线材问题。现要做100套钢架，每套需用长为2.9m，2.1m和1.5m的元钢各一根。已知原料长7.4m，问
2、应如何下料，使用的原材料最省。,解 最简单做法是，在每一根原材料上截取2.9m，2.1m和1.5m的元钢各一根组成一套，每根原材料剩下料头0.9m（7.4-2.9-2.1-1.5=0.9)。为了做100套钢架，需用原材料100根，共有90m料头。若改为用套裁，这可以节约原材料。下面有几种套裁方案，都可以考虑采用。 见表1-11。,表1-11 套裁方案,为了得到100套钢架，需要混合使用各种下料方案。设按方案下料的原材料根数为x1,方案为x2，方案为x3，方案为x4,方案为x5。根据表1-11的方案，可列出以下数学模型：,在以上约束条件中加入人工变量x6,x7,x8；然后用表1-12进行计算。,
3、第1次计算,第2次计算,例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的成分，依次类推。见表1-13有：,根据表1-13有：,这里 AC+AP+AH=A； B
4、C+BP+BH=B (1-40) 将(1-40)逐个代入(1-39)并整理得到,表 1-14 原材料供应数量的限额,表1-14表明这些原材料供应数量的限额。加入到产品A、B、D的原材料C总量每天不超过100kg，P的总量不超过100kg，H总量不超过60kg。由此,约束条件：,AC+BC+DC100 AP+BP+DP100 AH+BH+DH60 在约束条件中共有9个变量，为计算和叙述方便，分别用x1,x9表示。令 x1=Ac, x2=Ap, x3=AH, x4=BC, x5=BP, x6=BH, x7=DC, x8=DP, x9=DH.,约束条件可表示为：,目标函数,目的是使利润最大，即产品价
5、格减去原材料的价格为最大。 产品价格为：50(x1+x2+x3)产品A 35(x4+x5+x6)产品B 25(x7+x8+x9)产品D 原材料价格为：65(x1+x4+x7)原材料C 25(x2+x5+x8)原材料P 35(x3+x6+x9)原材料H 为了得到初始解，在约束条件中加入松弛变量x10 x16，得到数学模型：,例11的线性规划模型,最优解：,这数学模型，可用单纯形法计算，经过四次迭代，获得最优解为：x1=100,x2=50,x3=50；这表示需要用原料C为100kg；P为50kg;H为50kg，构成产品A。 即每天只生产产品A为200kg，分别需要用原料C为100kg；P为50kg
6、;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件。现要求为该工厂制定一个生产计划，在尽可能利用生产能力的条件下，获取最大利润
7、。,解 设xi j,xij分别为该工厂第i种产品的第j个月在正常时间和加班时间内的生产量；yi j为i种产品在第j月的销售量，i j为第i种产品第j月末的库存量。根据题意，可用以下模型描述,线性规划模型,(1) 各种产品每月的生产量不能超过允许的生产能力，表示为：,(2) 各种产品每月销售量不超过市场最大需求量yi jdi j (i=1,5;j=1,6),(3) 每月末库存量等于上月末库存量加上该月产量减掉当月的销售量,(4) 满足各变量的非负约束,xi j0, xij0, yij0, (i=1,5；j=1,6) i j0(i=1,5；j=1,5),(5) 该工厂上半年总盈利最大可表示为：,目
8、标函数,例13 连续投资问题,某部门在今后五年内考虑给下列项目投资，已知： 项目A，从第一年到第四年每年年初需要投资，并于次年末回收本利115%； 项目B，第三年初需要投资，到第五年末能回收本利125%，但规定最大投资额不超过4万元； 项目C，第二年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过3万元； 项目D，五年内每年初可购买公债，于当年末归还，并加利息6%。 该部门现有资金10万元，问它应如何确定给这些项目每年的投资额，使到第五年末拥有的资金的本利总额为最大?,解： (1) 确定决策变量,这是一个连续投资问题，与时间有关。但这里设法用线性规划方法，静态地处理。以xiA,
9、xiB,xiC,xiD(i=1,2,，5) 分别表示第i年年初给项目A，B，C，D的投资额，它们都是待定的未知变量。根据给定的条件，将变量列于表1-15中。,表 1-15,(2) 投资额应等于手中拥有的资金额,由于项目D每年都可以投资，并且当年末即能回收本息。所以该部门每年应把资金全部投出去，手中不应当有剩余的呆滞资金。因此,第一年：该部门年初拥有100000元，所以有 x1A+x1D=100000 第二年：因第一年给项目A的投资要到第二年末才能回收。所以该部门在第二年初拥有资金额仅为项目D在第一年回收的本息x1D(1+6%)。于是第二年的投资分配是 x2A+x2C+x2D=1.06x1D,第
10、三年：第三年初的资金额是从项目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
11、 x2C+1.25x3B+1.06x5D,(4) 数学模型,经过以上分析，这个与时间有关的投资问题可以用以下线性规划模型来描述：,(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%。,另一个的投资方案：,第一年： x1A=71698元，x1D=28300元 第二年： x2A=0元，x2C=30000元，x2D=0 第三年： x3A=42453元，x3B=40000元，x3D=0 第四年： x4A=0元，x4D=0 第五年： x5D=48820元。 还可以有其他的方案。,第一章 结束,
