线性规划练习题.doc

8. 表1.15是一个求极大值线性规划的单纯形表，其中x4，x5，x6是松弛变量。表1.15cj22CBXBbx1x2x3x4x5x602x5x2x12141-12a21-1-1-2-a+8j-1（1）把表中缺少的项目填上适当的数或式子。（2）要使上表成为最优表，a应满足什么条件？（3）何时有无穷多最优解？（4）何时无最优解？（5）何时应以x3替换x1？8. 答案（1）把表中缺少的项目填上适当的数或式子。cj122000CBXBbx1x2x3x4x5x6021x5x2x12140010101-12a21-1100-1-2-a+8j004-2a-10a-4（2）要使上表成为最优表，a应满足 2a4 （3）当a=2或a=4时有无穷多最优解（4）当a8时无最优解（5）当1a2时应以x3替换x19. 已知某线性规划的初始单纯形表和最终单纯形表如表1.16，请把表中空白处的数字填上，并指出最优基B及B1。表1.16C2-11000CBXBbx1x2x3x4x5x6000x4x5x63111-1112-1100010001j2-1100002-1x4x1x210155-11/2-1/2-21/21/2j9答案 第一表的右端常数向量为，第二表前四列构成矩阵最优基， 10. 已知某线性规划问题，用单纯形法计算时得到的中间某两步的计算见表1.17，试将空白处填上数字。表1.17C354000CBXBbx1x2x3x4x5x6x2x5x68/314/320/32/3-4/35/31000541/3-2/3-2/3010001j-1/304-5/300x2x3x115/41-6/41-2/418/415/41-12/41-10/414/4115/41j10答案 所以表中的数字填写如下表。C354000CBXBbx1x2x3x4x5x6500x2x5x68/314/320/32/3-4/35/31000541/3-2/3-2/3010001j-1/304-5/300543x2x3x180/4150/4144/4100110001015/41-6/41-2/418/415/41-12/41-10/414/4115/41j000-45/41-24/41-11/411某个线性规划的最终表是表1.18。表1.18cj01-200CBXBbx1x2x3x4x501-2x1x2x313/25/21/2100010001-1/2-1/2-1/25/23/21/2j000-1/2-1/2初始基变量是x1，x4，x5。（1）求最优基B=（P1，P2，P3）；（2）求初始表。11答案 初始基变量是x1，x4，x5。（1）最优基，（2）初始表为：C01-200CBXBbx1x2x3x4x5000x1x4x5212100-2111-3-1010001j01-2003. 写出下列线性规划的对偶问题： 3答案（1） ； （2）（3） （4） 一、 下面是某公司关于三个产品生产组合问题的线性规划，其中（2，5，8）为产品的价格，（96，40，60）为三个生产车间的能力，其目标函数、约束条件及最优单纯形表如下：max Z=2x1+5x2+8x3 6x1+8x2+4x3962x1+ x2 +2x3405x1+3x2+2x360xi, I=1,2,3基变量 x1 x2 x3 x4 x5 x6解 f x2 x3 x6 1/6 -1/3 -1/12 2/3 -1/3 -1/3（1） 填完上表，指出原问题与对偶问题最优解。（2） 评论每个车间的追加能力对公司的价值。（3） 若设计部门又提出一个新产品，其预测价格为7，生产单位产品消耗三个车间工时数据为（10，2，2），试问公司是否该考虑其投产，为什么？（答案）：（1）基变量 x1 x2 x3 x4 x5 x6解 f 19/3 0 0 1/6 11/3 0 x2 x3 x6 1/3 1 0 1/6 -1/3 0 5/6 0 1 -1/12 2/3 0 7/3 0 0 -1/3 -1/3 18/356/344/3x*=(0,8/3,56/3,0,0,44/3), y*=(1/6,11/3,0)(2) 1/6,11/3,0(3)40,不投产。二、 有一工厂，由三个车间生产四种产品，三个车间的生产能力分别为（4，3，3）（百小时），四种产品价格分别为（2，4，1，1/2）（千元），其产品组合的线性规划为max Z=2x1+4x2+x3+1/2x4 x1+3x2 +x442x1+x2 3x2+4x3+x43xi, i=1,2,3,4设x5,x6,x7依次为以上三个不等式的松弛变量，以下是该问题的不完全表：基变量 x1 x2 x3 x4 x5 x6 x7解 f x2 x1 x3 2/5 -1/5 0 -1/5 3/5 0 -1/10 -1/20 1/4(1) 完成上表；(2) 在保持最优基不变的情况下，产品1的价格可以增加多少？(3) 从外厂调剂给而车间2百小时的生产能力，但每百小时需支付0.4千元，这种调剂可以接受吗？若可以接受，能净增加多少收入？（答案）：（1）基变量 x1 x2 x3 x4 x5 x6 x7解 f 0 0 0 17/20 11/10 9/20 1/4 x2 x1 x3 0 1 0 2/5 2/5 -1/5 0 1 0 0 -1/5 -1/5 3/5 0 0 0 1 3/20 -1/10 1/20 1/4(2) 5/4c115/2；(3)可以接受，净增0.1千元。八、已知线性规划问题为min Z=8x1+6x2+3x3+6x4 （1）写出其对偶问题x1+2x2 +x43 （2）已知原问题的最优解为x*=(1,1,2,0)试根据对偶3x1 +x2 + x3+x46 理论直接求出对偶问题的最优解。 x3+x42x1 + x3 2 xi0, i=1,2,3,4解：(1)对偶问题为 (2)根据互补松弛定理，由x1 ，x2 ， x30有 max W=3y1+6y2+2y3+2y4 y1+3y2 +y4=8 y1+3y2 +y48 2y1+y2 =6 2y1+y2 6 y2 + y3 + y4=3 y2 + y3 + y43 解得Y=(2,2,1,0),此解也满足对偶约束条件4，因此 y1 +y2 +y3 6 为对偶问题可行解其对应的目标函数为 yi0, i=1,2,3,4 w=32+62+2=20=Z * 所以Y=(2,2,1,0)为对偶问题的最优解。九、已知线性规划问题为max Z=2x1+4x2+x3+x4 （1）写出其对偶问题x1+3x2 + x48 （2）已知原问题的最优解为x*=(2,2,4,0)试根据对偶2x1 +x2 6 理论直接求出对偶问题的最优解。 x2 + x3 + x46x1 + x2 + x3 9 xi0, i=1,2,3,4解：(1)对偶问题为 (2)根据互补松弛定理，由x1 ，x2 ， x30有 min W=8y1+6y2+6y3+9y4 y1+ 2y2 +y4=2 y1+2y2 +y48 3y1+y2 + y3 + y4=4 3y1+y2 +y3 + y46 y3 + y4=1 y3 + y4