《5运筹学之单纯型法应用举例》由会员分享，可在线阅读，更多相关《5运筹学之单纯型法应用举例（51页珍藏版）》请在金锄头文库上搜索。
1、第6节 应 用 举 例一般讲，一个经济、管理问题凡满足以下条件 时，才能建立线性规划的模型。n (1) 要求解问题的目标函数能用数值指标来表示， 且Z=f(x)为线性函数；n (2) 存在着多种方案； n (3) 要求达到的目标是在可以量化的，并要有足够 数据的一定约束条件下实现的；这些约束条件可用 线性等式或不等式来描述。n下面举例说明线性规划在经济管理等方面的应用。线性规划建模设立决策变量；明确约束条件并用变量的线性 等式或不等式表示；用变量的线性函数表示目标， 并确定是求极小还是极大；根据变量的物理性质研究变 量是否有非负性 有时根本无法用变量的线性函数来 描述目标函数或约束条件，在这
2、种情况下，可以尝试增加一些变 量或重新设定变量 生产 计划 问题用若干种原材料（资源）生产某几种 产品，原材料（或某种资源）供应 有一定的限制，要求制定一个产品 生产计划，使其在给定资源限制条 件下能得到最大收益。单耗 产品资源A1An资源 可供量 B1a11a1nb1B2a21a2nb2 Bmam1amnbm单件利润C1Cn解 设生产产品Aj的数量为xj例1-18 A，B两种产品，两道工序产品 工序一 工序二 A 加工2小时 加工3小时B 加工3小时 加工4小时可利用工时 15 25每生产一吨B，可得到两吨产品CA每吨盈利400元， B每吨盈利800元销售一吨C盈利300元报废每吨C损失20
3、0元市场预测，C最大销量为5吨决定A，B的产量，使工厂总的盈利最大。例1-18 设A，B产品的生产量分别为x1和x2工序1工时 2x1 3x215工序2工时 3x1 4x225 C产品数量 2x2C产品销量x3 ,报废量x4C产品销售量 x3 5利润总值 Z=400x1 +800x2 +300x3 -200x4-x3- x4=0非负约束 x1，x2，x3，x4例1-18 最优解 x1=3.75，x2=2.5，x3=5, x4=0最优值 =5000例1-19 产品2个零件1+3个零件2车间总工时生产效率（件小时 ） 零件1零件2 1 2 3100 50 758 10 166 15 21车间生产工
4、时数 零件1零件2 1 2 3x11 x21 x31x12 x22 x32例1-19 车间1工时约束 x11x12100车间2工时约束 x21x2250车间3工时约束 x31x3275零件1生产数量 8x11+10x21+16x31零件2生产数量 6x12+15x22+21x32非负约束 x ij 0产品数量:min4x11+5x21+8x31, 2x12+5x22+7x32y2y 8x11+10x21+16x31 3y 6x12+15x22+21x32目标函数 max Z=y例1-19 最优解 x11=100，x12=0x21=0, x22=50x31=25, x32=50最优值 y=600
5、例10 合理利用线材问题。现要做100套钢架，每套 需用长为2.9m，2.1m和1.5m的元钢各一根。已知原料 长7.4m，问应如何下料，使用的原材料最省。n解 最简单做法是，在每一根原材料上截 取2.9m，2.1m和1.5m的元钢各一根组成一 套，每根原材料剩下料头0.9m（7.4-2.9- 2.1-1.5=0.9)。为了做100套钢架，需用原 材料100根，共有90m料头。若改为用套裁 ，这可以节约原材料。下面有几种套裁方 案，都可以考虑采用。n见表1-11。 表1-11 套裁方案为了得到100套钢架，需要混合使用各种下料 方案。设按方案下料的原材料根数为x1,方案为 x2，方案为x3，方
6、案为x4,方案为x5。根据表1 -11的方案，可列出以下数学模型： 在以上约束条件中加入人工变量x6,x7,x8；然后 用表1-12进行计算。第1次计算第2次计算例1-11的 最终计算表（第3次计算）有非基变量的检验数为零，所以存在多重最优解 。由计算得到最优下料方案是：n按方案下料30根；n方案下料10根；n方案下料50根。n即需90根原材料可以制造100套钢 架。例11 配料问题n 某工厂要用三种原材料C、P、H混合调 配出三种不同规格的产品A、B、D。已知产 品的规格要求，产品单价，每天能供应的 原材料数量及原材料单价，分别见表1-13 和表1-14。该厂应如何安排生产，使利润 收入为最
7、大?解 如以AC表示产品A中C的成分，AP表示产品A中P 的成分，依次类推。见表1-13有：根据表1-13有： 这里 AC+AP+AH=A； BC+BP+BH=B (1-40) 将(1-40)逐个代入(1-39)并整理得到表 1-14 原材料供应数量的限额n表1-14表明这些原材料供应数量的限额。加入到 产品A、B、D的原材料C总量每天不超过100kg，P 的总量不超过100kg，H总量不超过60kg。由此约束条件：nAC+BC+DC100nAP+BP+DP100nAH+BH+DH60n在约束条件中共有9个变量，为计算和叙 述方便，分别用x1,x9表示。令nx1=Ac, x2=Ap, x3=A
8、H,nx4=BC, x5=BP, x6=BH,nx7=DC, x8=DP, x9=DH.约束条件可表示为：目标函数n目的是使利润最大，即产品价格减去原材料的价格为 最大。n产品价格为：50(x1+x2+x3)产品A35(x4+x5+x6)产品B25(x7+x8+x9)产品Dn原材料价格为：65(x1+x4+x7)原材料C25(x2+x5+x8)原材料P35(x3+x6+x9)原材料Hn为了得到初始解，在约束条件中加入松弛变量x10x16 ，得到数学模型：例11的线性规划模型最优解：n这数学模型，可用单纯形法计算，经过 四次 迭代，获得最优解为：x1=100,x2=50,x3=50； 这表示需要
9、用原料C为100kg；P为50kg;H为 50kg，构成产品A。n即每天只生产产品A为200kg，分别需要用原 料C为100kg；P为50kg;H为50kg。n从最终计算表中得到，总利润是z=500元/天 。例12 生产与库存的优化安排n某工厂生产五种产品(i=1,5)，上半年各月对每 种产品的最大市场需求量为di j(i=1,5;j=1,6)。已知每件产品的单件售价为Si元，生产每件产品所需要工时为ai，单件成本为 Ci元；该工厂上半年各月正常生产工时为 rj(j=1,6)，各月内允许的最大加班工时为 rj;Ci为加班单件成本。又每月生产的各种产品 如当月销售不完，可以库存。库存费用为Hi(
10、元/件 月)。假设1月初所有产品的库存为零，要求6月底 各产品库存量分别为ki件。现要求为该工厂制定一 个生产计划，在尽可能利用生产能力的条件下，获 取最大利润。n解 设xi j,xij分别为该工厂第i种产品的第j 个月在正常时间和加班时间内的生产量；yi j为i种产品在第j月的销售量，i j为第i种产 品第j月末的库存量。根据题意，可用以下 模型描述线性规划模型n(1) 各种产品每月的生产量不能超过允许的 生产能力，表示为：(2) 各种产品每月销售量不超过市场最大需求量 yi jdi j (i=1,5;j=1,6)(3) 每月末库存量等于上月末库存量加上该月产 量减掉当月的销售量 (4) 满
11、足各变量的非负约束nxi j0, xij0, yij0,(i=1,5；骏=1,6)ni j0(i=1,5；j=1,5)(5) 该工厂上半年总盈利最大可表示为 ：n目标函数例13 连续投资问题某部门在今后五年内考虑给下列项目投资，已知：n项目A，从第一年到第四年每年年初需要投资，并 于次年末回收本利115%；n项目B，第三年初需要投资，到第五年末能回收本 利125%，但规定最大投资额不超过4万元；n项目C，第二年初需要投资，到第五年末能回收本 利140%，但规定最大投资额不超过3万元；n项目D，五年内每年初可购买公债，于当年末归还 ，并加利息6%。n该部门现有资金10万元，问它应如何确定给这些项
12、 目每年的投资额，使到第五年末拥有的资金的本利 总额为最大?解： (1) 确定决策变量n这是一个连续投资问题，与时间有关 。但这里设法用线性规划方法，静态 地处理。以xiA,xiB,xiC,xiD(i=1,2, ，5)n分别表示第i年年初给项目A，B，C， D的投资额，它们都是待定的未知变 量。根据给定的条件，将变量列于表 1-15中。表 1-15(2) 投资额应等于手中拥有的资金额n由于项目D每年都可以投资，并且当年末即 能回收本息。所以该部门每年应把资金全 部投出去，手中不应当有剩余的呆滞资金 。因此n第一年：该部门年初拥有100000元，所以有nx1A+x1D=100000n第二年：因第
13、一年给项目A的投资要到第二年末才 能回收。所以该部门在第二年初拥有资金额仅为 项目D在第一年回收的本息x1D(1+6%)。于是第二年 的投资分配是nx2A+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.06x4Dn此外，由于对项目B、C的投资有限额的规 定，即：nx3B40000nx2C300
14、00(3) 目标函数n问题是要求在第五年末该部门手中拥有 的资金额达到最大，与五年末资金有关 的变量是：x4A,x3B,x2C,x5D;因此这个目标 函数可表示为nmax z=1.15x4A+1.40x2C+1.25x3B+1.06x5D(4) 数学模型n经过以上分析，这个与时间有关的投资问题可 以用以下线性规划模型来描述：(5) 用两阶段单纯形法计算结果得到n第一年： x1A=34783元，x1D=65217元n第二年： x2A=39130元，x2C=30000元，x2D=0n第三年： x3A=0，x3B=40000元，x3D=0n第四年： x4A=45000元，x4D=0n第五年： x5D
15、=0n到第五年末该部门拥有资金总额为143,750元， 即盈利43.75%。另一个的投资方案：n第一年： x1A=71698元，x1D=28300元n第二年： x2A=0元，x2C=30000元，x2D=0n第三年： x3A=42453元，x3B=40000元， x3D=0n第四年： x4A=0元，x4D=0n第五年： x5D=48820元。n还可以有其他的方案。运输问题 某种物资有m个产地Ai， i=1,2,.,m，产量分别为ai个单位 ；有n个销地Bj，销量分别为bj个 单位，j=1,2,n，Ai与Bj之间的 单位运价为Cij，问应如何安排运 输方案，才能使总运费最少？ 产销平衡的运输问题运输问题 设从产地Ai，运往销地Bj的销量为 Xij，则运输问题 某地区有两个煤矿A1 A2 ，所产的 煤要运往三个城市B1 B2 B3，各 产地的产量、销地的销量以及各 产地到各销地的单位运费见下表 ，求使总运费最小的运输方案 B1B2B3产量A1907095200A2806575230销量100150180x11x12x13x21x22x23运输问题B1B2B3产量A1907095200A2806575230销量100150180x11x12x13x21x22x23总运费为 Z=32500元 最大流量问题例123 某油田通过输油管道向港口输送原油，中间 有4个泵站，每段管道上的输送能力如
