运筹学

97二.求解线性规划问题时可能出现哪几种结果？哪些结果反映建模时有错误？如何改正这些错误？1.唯一最优解、2.无穷多最优解3.无界解4.无可行解；在应用上，当线性规划问题出现无界解和无可行解两种情形时，说明线性规划问题的模型有问题。a、出现无界解，是由于线性规划模型中缺乏必要的约束条件，因此，增加恰当的约束条件，使出现有界的可行域，即可解决问题；b、出现无可行解，是因为线性规划模型中的约束条件相互冲突，需要修改模型后再进行求解。二、在确定初始可行解时,什么情况下要在约束条件中增添人工变量?在目标函数中人工变量前的系数为（-M）的经济意义是什么？如果线性规划的标准形式中无现成的的初始可解B=I时，可采用人工变量法获得的初始可行解；（-M）称为“罚因子”，既只要人工变量取值大于零，目标函数就不能实现最优。三.什么事线性规划问题的标准形式？如何讲一个非标准型的线性规划问题转化为标准形式？a)约束条件都是等式；b)等式约束的右端项为非负的常数；c)每个变量都要求取非负数值。目标函数的转化（最大值）约束条件的转化（等式约束）变量约束的转化（全正）资源常量的转化（b）=0）定义可行解基解基可行解最优解关系？可行解：凡满足约束条件的解，均可称为可行解。基解：当X1=0，X2=0时K1=80，K2=60，这也是个特解，（0，0，80，60）,因所有的非基变量都等于0，又叫基解。基可行解：基解满足非负极为基可行解。最优解：使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称为该线性规划的一个最优解。五、试述线性规划的数学模型的结构及各要素的特征？答:结构包括决策变量，约束条件和目标函数。特征:（1）方案都用一组决策变量表示，具体方案由决策变量的一组取值决定，且决策变量一般是非负连续的。（2）模型都用一个决策变量的线性函数衡量决策方案的优略，该函数称为目标函数。对于不同的问题，要求目标函数实现最大化或最小化。（3）存在一些约束条件，这些约束条件可以用一组决策变量的线性等式或不等式表示右端项是一个给定的常数。六、如果线性规划的标准型变换为求目标函数的极小化minz,则用单纯法计算时如何判别问题已得到最优解？答:将最优性判别的条件改为所有检验数∝j=0即可，相应的进基变量条件为∝j0，其他不变。但用大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），试将此问题建立动态规划的模型。用xki表示从产地i分配给销地k，k+1，…，n的物资的总数，则采用逆推法时，动态规划的基本方程为fk（xk1，…，xkm）＝ikxmin﹛miikikxh1)(＋fk＋1（xk1－x1k，…，xkm－xmk）﹜式中0≤xik≤xkimiikx1＝bk，（k＝1，2，…，n）fn+1=0并且有x1i＝ai，（i＝1，2，…，m）2-3：工业污染问题：在一条主干河流沿岸分布甲乙企业，一只支流在甲乙之间汇入主干河流，Minz=1200x1+850x2x1=1.53x1+4x2=9x1=3x2=2Xj=02-4:运输问题：某公祠将A1,A2,A3三个工厂生产一种新产品，运到B1,B2,B3,B4四个销售点，详情见表，公司管理在平衡产销下，以最小成本运送所需的产品。答：设Xij（i=1,2,3,j=1,2,3,4）分别为产地Ai到销售处Bj的运输量，Cij(i=1,2,3,j=1,2,3,4)分别为Ai到Bj的运输费，目标函数为总运费最少：Minz=∑∑CijXijI=1j=1表示在满足供销平衡系列约束条件下，确定从产地到销售地运输量，使总运费最少，其约束条件为：x11+x12+x13+x14=70产量约束：x21+x22+x23+x24=45x31+x32+x33+x34=55x11+x21+x31=30x12+x22+x32=60销量约束:x13+x23+x33=35x14+x24+x34=4决策变量非负：Xij》=02-5;用一批长度为7.4米的圆钢做100钢架，每套由2。9米，2.1米，1.5米圆钢各一根组成求如何使材料最省：答：确定决策变量，设Xj表示按第j种方案所用的圆钢数。（j=1，2，3，4，5，6，7，8）确定目标函数，使用量最省，用料为：Minz=x1+x2+x3+x4+x5+x6+x7+x8确定约束条件：2.9米圆钢的数量限制x1+x2+x3+2x4=1002.1米圆钢的数量限制2x1+x2+x5+2x6+3x7=1001.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=2000y1-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，ij）Maxz=（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=30008x13+6x23+5x33=150010x11+5x21+7x31=4000舱位容积限制10x12+5x21+7x32=540010x12+5x23+7x33=1500x11+x12+x13=600商品数量限制x21+x33+x23=1000x31+x32+x33=8002/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为运费收入，其目标函数要求最大值：Maxz=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=0x2=0MinZ=250X1+350X22-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个月内需租用仓库对存货物。一直各个月所需的仓库面积Minz=2800∑Xi1+4500∑Xi2+6000∑Xi3+7300x14X11+x12+x13+x14=15X12+x13+x14+x21+x22+x23=10X13+x14+x22+x23+x31+x32=20X14+x23+x32+x41=12X1j=0j=1.2.3.4X2j=0j=1.2.3X31=0x32=0x41=02-11投资计划问题某企业今后三年内有四种机会Maxz=1.6x23+1.2x31+1.4x34X11+x12=3X12=2X21+x23=1.2x11X23=1.5X31+x34=1.5x12+1.2x21X34=1Xij=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≥202月初贷款额约束：x12+x13+x14+x21+x22+x23≥303月初贷款额约束：x13+x14+x22+x23+x31+x32≥154月贷初款额约束：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)+10%x142-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(x2