运筹学作业答案（线性规划整数规划）

1、1 用对偶单纯形法求解解答：先将问题化为构建单纯型表之后，迭代次CbXbbX1X2X3X4X5X6-9X12100-4/911/9-12X220101-10-15X320011/90-2/9Z*72000-1/3-3-7/32 用大M法求解下面问题解答：先将问题化为构建单纯型表之后，迭代次CbXbbX1X2S1S2S3A1A2-3X210001-20-120-2X125010101-100S212500111-1-1Z*-80000-40-1-M+4-M3 某造船厂根据合同从当年起连续三年年末分别提供5条规格、型号相同的大型客货轮。已知该厂这3年内生产大型客货轮的能力和每艘客货轮的成本如下：年

2、度正常生产时间可完成的客货轮数量加班生产时间可完成的客货轮数量正常生产时每艘得成本（万元）133600242700323650已知加班生产时，每艘客货轮的成本要比正常高出10%，又知道造出来的客货轮如果当年不交货，每艘每积压一年要造成积压损失60万元。在签合同的时候，该厂已经积压了2艘未交货得客货轮，而该厂希望在第3年年末完成合同时，还能储存一艘备用。问该厂应如何安排每年的客货轮生产量，使得在满足上述要求的情况下，总的生产费用最小？解答：建立的运输模型如下：最优解如下（不唯一）：4 对于下面的线性规划问题 在求解该问题最优解的基础上回答(1) b1由20变为45时的新的最优解。(2) b2由9

3、0变为95时的新的最优解。(3) c3由13变为8时，是否影响最优解？若有影响，求出新的最优解。(4) c2由5变为6时，是否影响最优解？若有影响，求出新的最优解。(5) 增加一个变量x6，c6=10，a16=3，a26=5，是否影响最优解？若有影响，求出新的最优解。(6) 增加一个约束条件，是否影响最优解？若有影响，求出新的最优解。解答：最优单纯型表如下：-551300XbbX1X2X3X4X5X220-11310X510160-2-41-10000-2-50(1) b1由20变为45，-551300XbbX1X2X3X4X55X245-113100X5-90160-2-4100-2-505

4、X2-902310-53/213X345-8012-1/2-1600-1-10X418-23/5-1/501-0.313X396/52/5100.1117-103/5-0.200-1.3(2) b2由90变为95时,同（）类似带入，所以最优基保持不变，最优解为限x2=20、x5=15（）因为c3是非基变量对应的系数。-2-5=-7<0，不影响最优解。（）c是基变量对应的目标函数的系数，所以会对非基变量的检验数产生影响。带入后发现x的检验数c1-cBTB-1p1=0-1*(-1)=1>0,其他非基变量的检验数<0。所以对最优解有影响。-551300XbbX1X2X3X4X5X2

5、20-113100X510160-2-4110-5-606X2165/80123/83/41/16-5X15/810-1/8-1/41/1600-39/8-23/4-1/16(5)p6=(3,5)T，检验数：，不影响最优解。（）增加一个约束-5513000XbbX1X2X3X4X5X5X220-1131000X510160-2-4100X502350015X220-1131000X510160-2-4100X-1050-4-30100-2-5005X212.511/410-5/403/40X51527/200-5/21-1/213X32.5-5/2013/40-1/495-5/200-7/20

6、-1/25 分别用分枝定界法和割平面法求解下面的问题解答：最优解为（0,5）T,最优值等于40。6 安排4个人做4种不同的工作。每个工人完成各项工作消耗的时间如下（单位：分钟）A工作B工作C工作D工作甲20192028乙18242720丙26161518丁17202419(1) 如何指派，可使总的消耗时间最少？(2) 如果把上图中的消耗时间数据看作是创造效益数据，如何指派，可使总的效益最大？(3) 如果在上图中再增加一个工作E，甲、乙、丙、丁四个人完成这个工作E的时间分别为17、20、15、16。那么应该指派甲、乙、丙、丁分别干那4项工作（意味着有一项没有人做），可使总的消耗时间最少？解答：目标函数最优解为安排甲做B 项工作，乙做A 项工作，丙C 项工作，丁D 项工作，或者是安排甲做B 项工作，乙做D 项工作，丙C 项工作，丁A 项工作，最少时间为71分钟（）b.为使总收益最大的目标函数的数学模型为：将a 中的目标函数改为求最大值即可。目标函数最优解为安排甲做D 项工作，乙做C 项工作，丙A 项工作，丁B 项工作，最大收益为102。（）由于工作多人少，我们假设有一个工人戊，他做各