线性规划课后题答案(张干宗).doc

1、P11.3（1）将下列线性规划模型化成标准形式：解：令，代入上面的线性规划，得标准形式P14:1、用图解法求解下列线性规划问题：利用图解法：于是得最优解为(4,1),最优值为-10。P15：2解：利用图解法于是最优解为（6，0），最优值为36。P15.3解：利用图解法求得有无穷多最优解，都落在一个线段上，该线段的两个端点是：于是全部的最优解可以表示成与的凸组合，即最优值都是-21。P16:1、 解：设表示第台机床加工第类产品的产量，于是可得数学模型 P16:2、 解：设表示第食品的采购量，于是可得数学模型P18:9(2)将下列线性规划问题变换成标准形式：解：令，则得 P18:9(4) 将下列线

2、性规划问题变换成标准形式：解：此题关键是将目标函数中的绝对值去掉。令则有因此都是非负变量。于是原规划可以化成标准形式：P1913、某养鸡场有一万只鸡，用动物饲料和谷物饲料混合喂养，每天每只鸡平均吃混合饲料0.5公斤，其中动物饲料占的比例不得少于1/5。动物饲料每公斤0.2元，谷物饲料每公斤0.16元。饲料公司每周只保证供应谷物饲料21000公斤。问饲料应怎样混合，才能使每天的总成本最低？试建立问题的数学模型并求解（图解法）。解：设养鸡场每天用动物饲料和谷物饲料分别为公斤，则问题模型为 用图解法:求得其最优解为 。P19:14解: 设甲乙厂各处理万立方米/天；总费用 元/天；考虑 工厂1与工厂2

3、所在的两点：工厂1：工厂2：于是建立数学模型为：目标函数 利用图解法，画图求得其最优解为：最优值为： P37:1解：线性规划问题由第一个约束的3倍减去第二个约束的2倍，得 即 （1）根据上式得到，再带回第一个约束，整理得 （2）由（1）、（2）表示出，带入目标函数，整理得 于是整理得基对应的典式为：根据典式，得基的基可行解是 同样根据典式，得基可行解的非基变量的检验数是 由于，因此不是最优解。P37:3证明：先化成标准形式这个显然是可行基对应的典式，注意到， 因此该线性规划目标值趋于负无穷，原线性规划目标函数趋于正无穷，即没有最优解。证毕。P46:1、 用单纯形法求解下列线性规划问题：（1）解

4、：先转化成标准形式选为初始的基变量组，得单纯形表X1X2X3X4X5X6f0-11-100 0X4X5X623412-1110-211100010001f-2-201 -10 0X2X5X621411-1100-2311-10010001f-7/3-7/300-2/3-1/3 0X2X3X68/31/311/35/31/3-4/31000101/3-1/31/32/31/3-1/3001最后一个单纯形表的检验数全部非正，得最优解为 最优值为（2）解：选为初始的基变量组，化为典式：得单纯形表X1X2X3X4f303-10X1X41/27101/21-1/2301f0-6020X2X4162-21

5、0-1401f-3-500-1/2X2X35/23/23/2-1/210011/41/4最后一个单纯形表的检验数全部非正，得最优解为 最优值为P63：1.用两阶段法解下列线性规划问题：解：首先化成标准形式由于上面的规划的系数矩阵中存在一个单位向量，因此只需要在添加一个人工变量，构造辅助问题：选为初始基变量组，化成典式：于是初始单纯形表为：X1X2X3X4z42-100X3X434122-11001X1X2X3X4z0000-1X3X112015/2-1/210-1/21/2得辅助问题的最优解，且此时人工变量已经出基，因此得原问题的一个初始可行基及其不完全形式的典式（去掉上表中的人工变量列及检验

6、数行）：根据约束条件得，带入目标函数中，得典式：由于检验数，因此应用得到原问题的一个最优解原问题的最优值为 P63：3.用两阶段法解下列线性规划问题：解：先转化成标准形式然后加入人工变量，构造辅助问题：选为初始的基变量组，化成典式：得单纯形表:X1X2X3X4X5X6z51-2-1-10 0X5X6232-1-31-100-11001z40-1/2-1/2-1-3/2 0X1X61410-3/2-1/2-1/2-1/20-11/21/201于是得到辅助问题的最优解为：最优值为由于，因此原问题无可行解。P75：1. 对线性规划问题验证是否为可行基？如果是，求出其典式。解：对于来说，为基变量，为非

7、基变量。令，代入问题的约束中，得，于是得基解 由于0，因此是一个可行基。 下面将问题化成基的典式。约束条件 转换成。 转换成，即。 转换成。 目标函数。于是，基的典式为：P76：5（1）用单纯形法求解下列线性规划问题：解：将模型化为选为初始的基变量组，化成典式：单纯形表为： X1X2X3X4X5z23002-4-3X1X225100112-100-1z19-200-2-3X3X22 11-2 0110-1201最后一个单纯形表的检验数全部非正，得最优解为x(0,1,2)；最优值为f19。P76：5（2）用单纯形法求解下列线性规划问题：解：选作为初始的基变量组，根据第二个约束求出，带入目标函数，

8、整理得标准形式：于是，得单纯形表：X1X2X3X4X5f15069/207100X4X5231/23/4-2/301/23/21001X1X2X3X4X5f8-1000-142/3X4X3121/41/2-2/300110-1/32/3最后一个单纯形表的检验数全部非正，得最优解为最优值为P7919对线性规划问题： 不经单纯形迭代，证明 为其最优基，并求出最优解。解：先标准化：令，则 于是 因此对应的基可行解为 检验数为： 因此为其最优基，即为最优解。P99第4题：判断下列关于对偶问题的说法是否正确：（1） 若原问题存在可行解，则其对偶问题必定存在可行解；（错误，因为对偶问题也可能无可行解）（2

9、） 若对偶问题无可行解，则原问题必定无可行解；（错误，因为对偶问题也可能无界解，当然此时对偶问题一定无最优解）（3） 若原问题和对偶问题都有可行解，则两者必都有最优解。（正确）P99第5题：设LP有最优解，并设(LP)：有可行解。试利用对偶理论证明：(LP)必有最优解。证：首先根据LP有最优解及对偶理论知：一定存在最优解，因此一定有可行解。又(LP)的对偶问题是其约束与LP对偶规划的约束一样，因此根据LP的对偶存在可行解推知，其也存在可行解。结合对偶理论和(LP)存在可行解知，(LP)必有最优解。证毕。P99第6题：解：所给线性规划问题的对偶规划是：由于对偶规划只有两个决策变量，因此可以利用比

10、单纯形法更简单的图解法来求解。利用图解法求得：对偶问题的最优解为：下面利用互补松弛性求解原问题的最优解。由于 因此它们的互补约束均为紧约束，即 （1）又由于 于是其对偶约束也是紧约束，即 （2）将（2）带入（1），得求解该方程得： 于是原问题的最优解为： P99：7、解：设分别表示A型，B型产品的产量，则所给问题的数学模型为：其对偶规划为：先将原问题化成标准形式：选为初始的基变量组，做表如下：x1x2x3x4x5f0540 0 0x39013100x48021010x54511001f-20003/20-5/20x35005/21/2-1/20x14011/20 1/20x5501/20-1/

11、21f-215000-1-3x325001/22-5x135100 1-1x210010-12于是所求问题的最优解为： 对偶问题的最优解为： 最优值都是： P105:1、用对偶单纯形法求解下列线性规划问题：解：先将所给线性规划问题转化成：选作为初始基变量，作出如下初始单纯形表：x1x2x3x4x5f0-5-2-4 0 0x4-4-3-1-210x5-10-6-3-501x1x2x3x4x5f20/3-10-2/3 0 -2/3x4-2/3-10-1/31-1/3x210/3215/30-1/3x1x2x3x4x5f22/300-1/3 -1 -1/3X12/3101/3-11/3X220112

12、-1于是所求问题的最优解为： 最优值为： P105:2、用对偶单纯形法求解下列线性规划问题：解：先将所给线性规划问题转化成：选作为初始基变量，作出如下初始单纯形表：x1x2x3x4x5x6f0-3-2-1 0 0 0x46111100x5-4-101010X6-30-11001x1x2x3x4x5x6f120-2-4 0 -3 0x42012110x1410-10-10X6-30-11001x1x2x3x4x5x6f1800-6 0 -3 -2x4-1003111x1410-10-10X2301-100-1由上面最后一个表格的第一行得方程：显然上式与非负约束矛盾，因此该线性规划没有可行解。P1

13、05:3、用对偶单纯形法求解下列线性规划问题：解：先将所给线性规划问题转化成：选作为初始基变量，作出如下初始单纯形表：x1x2x3x4x5x6f0-1-2-3 0 0 0x4-4-21-1100x58112010X6-20-11001f20-5/2-5/2 -1/2 00x121-1/21/2-1/200x5603/23/21/210x6-20-11001f700-5 -1/2 0-5/2x1310-1-1/20-1/2x530031/213/2X2201-100-1于是所求问题的最优解为： 最优值为： P111:1、 解：先化成标准形式选做为初始基，建立扩充问题：得如下单纯形表：x1x2x3

14、x4x5x6f0012 0 0 0x141-1-1000x48012100X5-20-11010X6M011001让x3进基，x6离基，得x1x2x3x4x5x6f-2M0-10 0 0 -2x1M+4100001x48-2M0-1010-2X5-2-M0-2001-1X3M011001得到扩充问题的一个正则解，继续用对偶单纯形法迭代，得：x1x2x3x4x5x6f-2M0-10 0 0 -2x1M+4100001x48-2M0-1010-2X5-2-M0-2001-1X3M011001f-8000 -1 0 0X1M+4100001X2-8+2M010-102X5-18+3M000-213X

15、38-M00110-1f-8000 -1 0 0X112101100X2801210 0X46003110X6M-800-1-101于是得最优解：最优值： 该问题最优解不惟一，继续迭代得：x1x2x3x4x5x6f-8000 -1 0 0X112101100X2801210 0X46003110X6M-800-1-101f-8000 -1 0 0X1101002/3-1/30X240101/3-2/3 0X320011/31/30X6M-6000-2/31/31于是得课后答案所给的最优解：上面计算的Matlab程序为：syms MA=0 0 1 2 0 0 04 1 -1 -1 0 0 08

16、0 1 2 1 0 0-2 0 -1 1 0 1 0M 0 1 1 0 0 1;for i=1:4A(i,:)=A(i,:)+A(5,:)*(-A(i,4);endA(3,:)=-A(3,:);for i=1 2 4 5A(i,:)=A(i,:)+A(3,:)*(-A(i,3);endA(5,:)=-A(5,:);for i=1 2 3 4A(i,:)=A(i,:)+A(5,:)*(-A(i,7);endA(4,:)=A(4,:)/3;for i=1 2 3 5A(i,:)=A(i,:)+A(4,:)*(-A(i,4);endP1112、解：添加人工约束，得到如下扩充问题得如下单纯形表：x1x

17、2x3x4x5x6x7x8f0000 1 -2 -3 0 0x1171005-1510x2-22010-12-110X3-3300111-110X8M00011111让x4进基，x8离基，得x1x2x3x4x5x6x7x8f-M000 0 -3 -4 -1 -1x117 - 5*M1000-60-4-5x2M - 2201003021X3- M - 3300100-20-1X4M00011111f-17/5-1/5000-9/5-4-1/50x8M - 17/5-1/50006/504/51x2-93/51/51009/506/50X3-182/5-1/50106/5,24/50X417/51

18、/5001-1/511/50于是根据x2行知，扩充问题没有可行解，于是原问题也没有可行解。程序：syms MA=0 0 0 0 1 -2 -3 0 017 1 0 0 5 -1 5 1 0-22 0 1 0 -1 2 -1 1 0-33 0 0 1 1 1 -1 1 0M 0 0 0 1 1 1 1 1;for i=1:4A(i,:)=A(i,:)+A(5,:)*(-A(i,5);endk1=2;k2=9;A(k1,:)=A(k1,:)/A(k1,k2);for i=1 3 4 5A(i,:)=A(i,:)+A(k1,:)*(-A(i,k2);endP1123、解：添加人工约束，得到如下扩充问题得如下表格：x1x2x3x4x5f0-120 0 0x3-1-41100x