min f?CX约束条件： AX?b X?0 max z?CX约束条件： AX?b X?0

其中：C为非负行向量，列向量b中元素的符号没有要求

其中：C为非正行向量，列向量b中元素的符号没有要求以上两种线性规划时一般可以选取对偶单纯形法。

13.解：

（1）错误。原问题存在可行解，则其对偶问题可能存在可行解，也可能无可行解；

（2）正确；

（3）错误。对偶问题无可行解，则原问题解的情况无法判定，可能无可行解，可能有可行解，甚至为无界解； （4）正确；

14．解：

maxz??x1?2x2?3x3??4??x1?x2?x3?s1??x1?x2?2x3?s2?8??x2?x3?s3??2??xi≥0,i?1,,3;sj≥0,j?1,? ,3用对偶单纯形法解如表6-1所示。 表6-1 迭代次数 基变量 s1 s2 CB x1 x2 x3 s1 s2 s3 ?1 [?1] 1 0 0 ?1 ?2 1 1 ?1 0 ?2 ?1 2 [?1] 1 ?3 ?3 ?1 2 1 0 ?3 1 1 1 ?1 ?2 0 1 0 0 0 0 ?1 1 0 1 ?1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 b ?4 8 ?2 4 4 ?2 0 0 0 0 s3 zj cj?zj x1 s2 ?1 0 0 1 0 0 ?1 0 1 s3 zj cj?zj 续表

迭代次数

基变量 CB x1 x2 x3 s1 s2 s3 b

?1 x1 s2 ?2 0 0 1 ?2 0 ?3 0 3 ?1 2 ?5 0 ?1 1 0 1 ?1 0 0 1 0 0 0 0 ?1 2 ?1 3 ?3 6 0 2 ?1 0 ?2 1 0 0 ?1 0 2 x2 zj cj?zj 最优解为x1=6，x2=2，x3=0，目标函数最优值为10。

15. 解：原问题约束条件可以表示为：AX?b?ta，其中a和b为常数列向量。 令t?0，将问题化为标准型之后求解，过程如下：

其中最优基矩阵的逆矩阵为

?100????1B???11?1?，

?001???则

?100??5??5????????1B*b???11?1??10???2?

?001??3??3????????100??t??1??t?????????B?1*ta???11?1???t??t??3????3t?

?001??t??1??t?????????

?5?t???（b?ta）??2?3t? 则B?1*?3?t???从而， 1)当0?t?迭代 次数 基变量 3时，最优单纯形表为 2cB 1 0 2 x1 1 1 0 0 0 x2 2 0 0 1 0 x3 0 1 -1 0 -1 x4 0 0 1 0 0 x5 0 0 -1 1 -2 b 5?t 2?3t 3?t x1 2 x4 x2 cj?zj 此时5?t?0，线性规划问题的最优解为(x1,x2)?(5?t,3?t)，3?t?0，2?3t?0，目标函数最大值为11?3t；

372）当?t?时，由2?3t?0可知，(x1,x2)?(5?t,3?t)并非最优解，利用对偶

22单纯形法继续迭代求解，过程如下所示， 迭代 次数 基变量 cB 1 0 2 x1 1 1 0 0 0 1 0 0 0 x2 2 0 0 1 0 0 0 1 0 x3 0 1 （-1） 0 -1 0 1 0 0 x4 0 0 1 0 0 1 -1 0 -1 x5 0 0 -1 1 -2 -1 1 1 -1 b 5?t 2?3t x1 2 x4 x2 3?t cj?zj x1 3 1 0 2 7?2t x3 x2 ?2?3t 3?t cj?zj 此时7?2t?0，?2?3t?0，3?t?0，从而线性规划问题的最优解为

(x1,x2)?(7?2t,3?t)，目标函数的最大值为13； 3）当

7，由7?2t?0可知，(x1,x2)?(7?2t,3?t)并非最优解，利用?t?10时，

2

对偶单纯形法继续迭代求解，过程如下所示， 迭代 次数 基变量 cB 1 0 2 x1 1 1 0 0 0 1 0 0 0 1 1 1 -1 x2 2 0 0 1 0 0 0 1 0 0 0 1 0 x3 0 1 （-1） 0 -1 0 1 0 0 0 1 0 0 x4 0 0 1 0 0 1 -1 0 -1 -1 0 1 -2 x5 0 0 -1 1 -2 b 5?t 2?3t 3?t x1 2 x4 x2 cj?zj x1 3 1 0 2 （-1） 7?2t 1 1 -1 1 0 0 0 x3 x2 ?2?3t 3?t cj?zj x5 4 0 0 2 ?7?2t 5?t 10?t x3 x2 cj?zj 此时?7?2t?0，5?t?0，10?t?0，从而线性规划问题的最优解为

(x1,x2)?(0,10?t)，目标函数的最大值为20?2t；

16.解：先写出原问题的对偶问题

min f?20y1?20y2约束条件： y1?4y2?2 (1) 2y1?3y2?2 (2) 3y1?2y2?1 (3) 4y1?y2?1 (4) y1,y2?013将y1?,y2?代入对偶问题的约束条件，得有且只有（2）、（4）式等式成立，

105也就是说，其对应的松弛变量取值均为0，（1）和（3）式对应的松弛变量不为0，

从而由互补松弛定理有x1?x3?0；又因为y1?0,y2?0，从而原问题中的两个约束应该取等式，把x1?x3?0代入其中，得到