运筹学
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
97二.求解线性规划问题时可能出现哪几种结果？哪些结品，运到B1,B2,B3,B4四个销售点，详情见表，公司管理在果反映建模时有错误？ 如何改正这些错误？ 平衡产销下，以最小成本运送所需的产品。 1.唯一最优解 、2.无穷多最优解3.无界解4.无可行解；在答：设Xij（i=1,2,3,j=1,2,3,4）分别为产地Ai到销售处Bj应用上，当线性规划问题出现无界解和无可行解两种情形的运输量，Cij(i=1,2,3,j=1,2,3,4)分别为Ai到Bj的运输费，时，说明线性规划问题的模型有问题。 目标函数为总运费最少： a、出现无界解，是由于线性规划模型中缺乏必要的约束条 Min z=∑∑CijXij 件，因此，增加恰当的约束条件，使出现有界的可行域， I=1 j=1表示在满足供销平衡系列约束条件下，确定即可解决问题； 从产地到销售地运输量，使总运费最少，其约束条件为： b、出现无可行解，是因为线性规划模型中的约束条件相互 x11+x12+x13+x14=70 冲突， 需要修改模型后再进行求解。 产量约束：x21+x22+x23+x24=45 二、在确定初始可行解时,什么情况下要在约束条件中增添 x31+x32+x33+x34=55 人工变量?在目标函数中人工变量前的系数为（-M）的经济 x11+x21+x31=30 意义是什么？ x12+x22+x32=60 如果线性规划的标准形式中无现成的的初始可解B=I销量约束:x13+x23+x33=35 时，可采用人工变量法获得的初始可行解 ；（-M）称为“罚 x14+x24+x34=4 决策变量非负：Xij》=0 因子”，既只要人工变量取值大于零，目标函数就不能实现2-5;用一批长度为7.4米的圆钢做100钢架，每套由2。9最优。 米， 2.1 米， 1.5 米圆钢各一根组成求如何使材料最省： X31>=0 x32>=0 x41>=0 2-11 投资计划问题 某企业今后三年内有四种机会 Max z= 1.6x23+1.2x31+1.4x34 X11+x12=3 X12<=2 X21+x23=1.2x11 X23<=1.5 X31+x34=1.5x12+1.2x21 X34<=1 Xij>=0 (i=1.2.3;j=1.2.3.4) 2-12贷款问题 某公司拟在下一年度的1-4月份的四个月内， 解：设决策变量xij表示该公司在第i(i=1234)月份签订的借期为j(j=1234)个月份的贷款合同。因五月份起该公司不需要向财务公司贷款。故x24,x33,x34,x42,x43,x44均为零，且 1月初贷款额约束：x11+x12+x13+x14≥20 2月初贷款额约束：x12+x13+x14+x21+x22+x23≥30 3月初贷款额约束：x13+x14+x22+x23+x31+x32≥15 4月贷初款额约束：x14+x23+x32+x41≥10 贷款额非负约束：xij≥0(i=1,2,3,4;j=1,2,3,4) 假设z为贷款费用，则z=5%(x11+x21+x31+x41)+6.5%(x12+x22+x32)+8%(x13+x23三.什么事线性规划问题的标准形式？如何讲一个非标准型的线性规划问题转化为标准形式？ a) 约束条件都是等式； b) 等式约束的右端项为非负的常数； c) 每个变量都要求取非负数值。 目标函数的转化（最大值） 约束条件的转化（等式约束）变量约束的转化（全正）资源常量的转化（b）=0） 定义可行解 基解 基可行解 最优解 关系？ 可行解：凡满足约束条件的解，均可称为可行解。 基解：当X1=0，X2=0时K1=80，K2=60，这也是个特解，（0，0，80，60）,因所有的非基变量都等于0，又叫基解。 基可行解：基解满足非负极为基可行解。 最优解：使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称为该线性规划的一个最优解。 五、试述线性规划的数学模型的结构及各要素的特征？ 答:结构包括决策变量，约束条件和目标函数。 特征:（1）方案都用一组决策变量表示，具体方案由决策变量的一组取值决定，且决策变量一般是非负连续的。（2）模型都用一个决策变量的线性函数衡量决策方案的优略，该函数称为目标函数。对于不同的问题，要求目标函数实现最大化或最小化。（3）存在一些约束条件，这些约束条件可以用一组决策变量的线性等式或不等式表示右端项是一个给定的常数。 六、如果线性规划的标准型变换为求目标函数的极小化min z,则用单纯法计算时如何判别问题已得到最优解？ 答:将最优性判别的条件改为所有检验数∝j>=0即可，相应的进基变量条件为 ∝j>0，其他不变。但用大M法求初始基可行解时，人工变量在目标函数中的系数取+M。 2.试述对偶单纯形法的计算步骤，它的优点及应用上的局限性。答：（1）初始化。将约束条件均转化为<=形式，并引入松弛变量将规划问题转化成标准型。 （2）可行性检验：检验所有基变量的取值是否达到非负。（3）迭代。1）确定出基变量2)确定进基变量3）确定新的基解（4）旋转变换 优点：引入的人工变量不多，换基迭代步骤较少，且无须使太多的人工变量为0的情形，使用对偶单纯形法更容易。当灵敏度分析时，对偶单纯形法向最优解的收敛速度，通常要比该问题重新使用单纯形法快得多。 局限性：资源系数全部为正，约束条件不能为等式。 3试从经济上解释对偶问题及对偶变量的含义： 答：线性规划对偶问题的经济解释是直接建立在原问题经济解释的基础上的，从对偶问题的基本性质可以看出，在单纯形法的每次迭代中有目标函数Z=函数其中b是线性规划原问题的右端项，它代表第i中资源的可用量。 对偶变量y的含义是当前最优解中对应一个单位第i中资源的估价（或对目标函数的利润贡献）。 4根据原问题同对偶问题之间的对应关系，分别找出两个问题变量之间，基解以及检验数之间的关系。 答：原问题变量个数为对偶问题约束个数，分别找出约束个数是对偶问题变量个数。 原问题松弛变量的检验数的相反数为对偶问题的最优解。 6什么是资源的影子价格?它与相应的市场价格之间有何区别？说明影子价格意义？ 答：单位资源在生产中所做出的贡献的估价称为影子价格。 资源的市场价格是已知数；相对比较稳定，而它的影子价格则有赖于资源的利用情况是未知数。系统内任何资源数量和价格的变化都会影响影子价格的变化，是一种动态价格。从市场角度看，资源的影子价格实际上是一种机会成本。 考虑一个有m个产地和n个销地的运输问题。设ai（i＝1，2，„，m）为产地i可发运的物资数，bj（j＝1，2，„，n）为销地j所需要的物资数。又从产地i到销地j发运xij单位物资所需的费用为hij（xij），试将此问题建立动态规划的模型。 minm用xki表示从产地i分配给销地xk，k+1资的总数，则采用逆推法时，动态规划的基本方程为hik，„，(xikn)的物f k（xk1，„，mxkm）＝ik﹛i1 ＋f k＋1（xk1－x1k，„，式中 0≤xikx≤ikxkm－xmk）﹜ xki i1＝bk，（ k＝1，2，„，n） f n+1 =0 并且有 x1i＝ai，（i＝1，2，„，m） 2-3：工业污染问题：在一条主干河流沿岸分布甲乙企业，一只支流在甲乙之间汇入主干河流，Min z=1200x1+850x2 x1>=1.5 3x1+4x2>=9 x1<=3 x2<=2 Xj>=0 2-4:运输问题：某公祠将A1,A2,A3三个工厂生产一种新产答：确定决策变量，设Xj表示按第j种方案所用的圆钢数。（j=1，2，3，4，5，6，7，8） 确定目标函数，使用量最省，用料为： Min z=x1+x2+x3+x4+x5+x6+x7+x8 确定约束条件： 2.9米圆钢的数量限制 x1+x2+x3+2x4>=100 2.1米圆钢的数量限制 2x1+x2+x5+2x6+3x7>=100 1.5米圆钢的数量限制 3x1+x3+x4+3x5+2x6+4x8>=100 非负限制 Xj>=0且为整数 2-6木材库存问题 答：设Yi分别表示冬春夏秋四个季度的采购木材量，Xij表示第i季度采购用于第j季度的销售木材量，则： 冬季储量 Y1<=2000 仓库储量约束 春季储量 x12+x13+x14+y2<=2000 夏季储量 x13+x14+x23+x24+y3<=\2000 秋季储量 x14+x24+x34+y4<=2000 y1-x11-x12-x13-x14=0y2--x22-x23-x24=0 购销平衡约束 y3-x33-x34=0y4-x44=0 冬季销售 x11<=1000 销售量约束 春季销售 x12+x22<=1400 夏季销售 x13+x24+x33<=2000 秋季销售 x14+x24+x34+x44<=1600 购销量非负约束：Yi>=0,Xij>=0，（i,j=1，2，3，4） 其中第i季度购入第j季度出售的木材价格为： Pij=PIij-[70+100（j-i）]*0.1万元每立方米） （j=1，2，3，4，i） Max z=（425x11+423x12+438x13+418x14-410y1）+(440x22+448x23+428x24-430y2) +(465x33+438x34-460y3)+(355x44-450y4) 2-7:货轮装优化问题：答：设Xij>=0为装于第j舱位的第i种商品的数量（i,j=1，2，3）则： 8x11+6x21+5x31<=2000 舱位载重限制 8x12+6x22+5x32<=3000 8x13+6x23+5x33<=1500 10x11+5x21+7x31<=4000 舱位容积限制 10x12+5x21+7x32<=5400 10x12+5x23+7x33<=1500 x11+x12+x13<=600 商品数量限制 x21+x33+x23<=1000 x31+x32+x33<=800 2/3(1-0.15)<=(8x11+6x21+5x31)/(8x12+6x22+5x32)<=2/3(1+0.15) 货轮平衡条件 1/2(1-0.15)<=(8x13+6x23+4x33)/(8x12+6x22+5x32)<=1/2(1+0.15) 4/3(1-0.10)<=(8x11+6x21+5x31) /(8x13+6x23+5x33)<=4/3(1+0.10) 设z为运费收入，其目标函数要求最大值： Max z=1000（x11+x12+x13）+700(x21+x22+x23)+600(x31+x31+x33) 2-8机械租赁问题试问应租赁甲乙各多少天，才能完成任务且费用最少？ 解： 设租赁甲X1，乙X2。必须满足以下条件： 甲乙安装构件A数量约束： 5X1+6X2>=250 甲乙安装构件B数量约束：8X1+6X2>=300 甲乙安装构件C数量约束：10X1+20X2>=700 此外X1X2非负:x1>=0 x2>=0 Min Z =250X1+350X2 2-9项目投资优化问题 某公司有一批资金用于ABCDE5个工程项目的投资，解： 设X1X2X3X4X5分别表示项目ABCDE的投资百分比，所以X1+X2+X3+x4+x5=1
设z表示该公司最大收益，则
Z=0.10X1+0.08X2+0.06X3+0.05X4+0.09X5
项目A的投资不大与其他各项投资之和：
X1-X2-X3-X4-X5<=0
项目B和E的投资之和不小于项目C的投资：X2-X3+X5>=0
投资百分比约束： Xj>=0（J=1/2/3/4/5）
2-10仓库租赁合同某厂在今后4个月内需租用仓库对存货物。一直各个月所需的仓库面积 Min z=2800∑Xi1+4500∑Xi2+6000∑Xi3+7300x14 X11+x12+x13+x14>=15 X12+x13+x14+x21+x22+x23>=10 X13+x14+x22+x23+x31+x32>=20 X14+x23+x32+x41>=12 X1j>=0 j=1.2.3.4 X2j>=0 j=1.2.3
)+10%x14
2-13厂址选择问题 甲乙丙三地，每地都生产一定数量的原料， 解：设xij为由i地运到j地的原料数量，yij为由i地运到j地的产品数量，ij=1，2，3分别对应甲乙丙
设Qi为第i处设厂的规模，即年产品的数量根据题意有Q1=y11+y12,Q2=y21+y22,Q3=y31+y32(产品全消耗) 假设总费用为z，则要取得最小费用的厂址选择规划模型为 Minz=75(x12+x21)+50(x13+x31)+100(x23+x32)=150y11+240y12+210y21+120y22+160y31+220y32 3(y11+y12)-x21-x31+x12+x13≤20 X21+3(y21+y22)-x12-x32+x23≤16
X31+x32+3(y31+y32)-x13-x23≤24 y11+y21+y31=7 y12+y22+y32=13 y21+y22≤5
xij≥0(i,j=1,2,3;i≠j yij≥0(i=1,2,3;j=1,2)
2-14飞行器能源优化问题：某飞行器需要使用电源的设备，三组电池可选择三种电池单元解：设优化后第一种电池单元数为x1,第二种为x2,第三种为x3三设备所需的总能量分别为b1≥200(A.h)b2≥220(A.h)b3≥580(A.h) 数学模型为
Minz=2x1+1.5x2+x3 5.5x1+8x2+9.1x3≥200
5.6x1+8.2x2+9.2x3≥200 5.47x1+7.9x2+8.7x3≥580 x1,x2,x3≤30 x1,x2,x3≥0
通过计算得，第一组电池使用第一类单元30个，第二组使用第二类30个，第三组电池使用第三类15个，三组电池的最小总质量为105千克
2-15：种植计划问题：某农场拥有土地230亩，除100亩坡地和80亩旱地外
答：按每份预计获100元净收入计算，设Xi（i=1，2，3，4，5，6）为计划需要种植第i种作物的份数 坡地旱地水田面积分别为b1=100,b2=80.b3=50
据经验没在坡地或一百元收入，第1，3，4种植物所需分别为0.4亩，0.2亩，0.18亩，则0.4x1+0.2x3+0.18x4<=100 在旱地种植或100元收入，第1，2，3，4分别需要0.3，0.25，0.15，0.1，则0.3x1+0.25x2+0.15x3+0.1x4<=80
在水田种植100元收入，第3，5，6种作物所需面积分别为0.4，0.15，0.1，则0.4x3+0.15x5+0.1x6<=50 设种植收入为在z，由于x1到x6表示的是种植6类作物没100元收入分别使用的耕地面积，则
Z=100x1+100x2+100x3+100x4+100x5+100x6 决策量非负： Xi（i=1，2，3，4，5，6）>=0
结果：水田种50亩的第六作物，旱地种24.5的第二作物和55.5的第四作物，100亩坡地全种第四作物，最大收入为115333.3元
2-16生产计划问题某公司在山东地区的工厂生产扳手和钳子， 1该公司为使盈利的贡献最大化，应该计划每天生产多少件扳手和钳子 2根据这个计划对盈利的总贡献是多少 3这个计划中，哪些资源将是最关键的
解：该公司必须对每天生产扳手和钳子的数量做出决定，定义如下
W=每天生产扳手的数量，以千件为单位 P=每天生产钳子的数量，以千件为单位
则生产计划对盈利的贡献z为 贡献z=130w+100p 数学规划模型为 minz=130w+100p
1.5w+p≤27 W +p ≤ 21 0.3w+0.5p≤9 w≤15 p≤16 w≥0,p≥0
对盈利的贡献最大化生产计划 w=12.0,p=9.0 对盈利的贡献z的最大值为2460白天/天
（1） 该公司应该计划每天生产12000件扳手和9000件钳子 （2） 最盈利的总贡献是：贡献=130w+100p=2460(白天/天)（3） 必须查看哪种资源将用尽它们的资源限量
钢铁：1.5w+1.0p=1.5*12.0+1.0*9.0=27 浇铸机：1.0w+1.0p=1.0*12.0+1.0*9.0=21 这个结果正好等于每天浇铸机的生产能力 装配机：0.3w+0.5p=0.3*12.0+0.5*9.0=8.1
2-17：炼焦煤供应问题：某公司需100万吨到150万吨的炼焦煤，问题1.卫视供应炼焦煤的成本最小化，该公司与选定的供应商签订多少煤炭供应量的协议？ 问题2.该公司的采购成本是多少？
问题3.该公司的平均采购成本是多少？
答：设与供应商签订供煤协议的煤供应量为：
Xj=与供应商j签订的供煤量（i=1，2，3，4，5，6，7，8） 则该公司供应成本为：=495x1+500x2+610x3+635x4+665x5+710x6+725x7+800x8 使成本最小化的Xi的数值为求出这些数值，其约束条件为如下：
8
购没煤总量约束：∑Xi=1225 i=1
必须从联合会的公司购买至少50%的煤：x1+x2+x4+x6>=x3+x5+x7+x8
卡车运输约束：x2+x4+x5+x6<=720 铁路运输约束：x1+x3+x7+x8<=650 挥发性约束：(15x1+16x2+18x3+20x4+21x5+22x6+23x7+25x8)/(x1+x2+x3+x4+x5+x6+x7+x8)>=19 生产能力约束：x1<=300,x2<=600,x3<=510,x4<=655,x5<=575, x6<=680,x7<=450,x8<=490
可的炼焦煤供应的线性规划：Minz=495x1+500x2+610x3+635x4+665x5+710x6+725x7+800x8 可得问题1：
x1=55,x2=600,x3=0,x4=20,x5=100,x6=0,x7=450,x8=0 问题2：总成本为=495x1+500x2+610x3+635x4+665x5+710x6+725x7+800x8=732675
问题3：平均称为为：732675/1225=598.1（元每吨） 例6-1 设有一纺织厂可生产衣料和窗帘布共两种产品
尽可能避免开工不足 尽可能限制每周加班时间不超过10小时 尽可能满足市场需求 尽可能减少加班时间
解：为了建设该问题的数学模型，作如下分析：
（1） 设该厂每周生产衣料和窗帘各为X1，X2千米 纺纱的约束：500X1+800X2≤9000即为资源约束。
X1+X2+d-1-d+1=80 d+1+d-2-d+2=10 x1+d-3-d+3=70 x2+d-4-d+4=45
（3） 在此问题中的4个有序目标分别为：
P1: min z1 = d-1 P2:min z2 = d+2 P3: min z3 =5d-3 + 3d-4 P4: min z4 =d+1 6-2加权目标规划模型：
解：min z=5d1-+8d2++9(5 d3-+3 d4-)+2 d1+
500x+800x≤9000 x1+x2+ d1-- d1++80 d1+ + d2- - d2+=100 x1+ d3-- d3 +=70
x2+ d4-- d4+=45 xj≥0, di-, di+≥0 例7-1
下料问题：设有某种型号的圆钢下零件A1,的毛坯，试建立模型。 解设用Bj方式下料的圆钢有Xi根，则该问题的数学模型为 N Min z=∑Xj J=1 S.T﹛ N
∑Cij≥ai(i=1,2’’’’’’’.m) Xi≥0且为整数 } J=1
其中目标函数minZ=∑Xj，表示所有圆钢树最少，约束条件∑CijXj≥Ai表示各种零件实际数量必须满足数量。这是一个纯整数规划问题。
本文来源：https://www.wddqw.com/doc/7219c498be23482fb5da4c86.html