x1 x2 x3 x4 x5 x6 x7 x8 x9 f? -3 -2 -11 0 0 -1 0 -10 0 -220 x5 1 2 1 0 1 1 0 0 0 x7 1/2 -1 -1 0 0 1 1 -3/2 0 10 5/2 1/2 10 x4 -1/2 -1 0 1 0 -1 0 1/2 0 x9 3 2 1 2 1 0 0 0 1 B*?(a5,a7,a4,a9)为对偶可行基

对偶单纯形法

x1 x2 x3 x4 x5 x6 x7 x8 x9 f? -33 -22 -11 0 0 -11 0 0 -10 -210 x5 1 2 1 0 1 1 0 0 0 10 x7 -4 -4 -1 0 0 -1/2 1 0 -3/2 4 x4 1 0 0 1 0 -1/2 0 0 1/2 0 x8 -3 -2 0 0 0 -1 0 1 -1 T1 所以最优解x??0000100410?，即改变为只生产E为10万件。

3.求解下列线性规划问题的对偶问题：

（2） minf?2x1?x2?x3?3x4 （3） minf?3x1?2x2?3x3?4x4

?x1?2x2?3x3?4x4?3?x1?2x2?4x4?1???x2?3x3?4x4??5?2x2?3x3?4x4?2s.t.? s.t.?

2x?3x?7x?4x?2x?3x?33234?1?1???x1,x2?0?x1?0,x4?0,x2,x3无约束解

(1) 对偶问题：

maxg?y1?2y2?3y3 ?y3?2?y1???1?2y1?2y2?s.t.??3y2?3y3?1 ?4y?4y??32?1??y1无约束,y2?0,y3?0

(2) 对偶问题：

maxg?3y1?5y2?2y3 ?2y3?3?y1???2y1?y2?2y3?2?s.t.?3y1?3y2?7y3??3?4y?4y?4y?423?1?,,?y1?0,y2?0,y3无约束3.判断下列说法是否正确，为什么？

（1） 如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解. （2） 如果线性规划的对偶问题无可行解，则其原问题也一定无可行解.

（3） 如果线性规划的原问题和对偶问题都具有可行解，则其原问题和对偶问题一定具有有限最优

解.

（4） 已知线性规划问题maxf?cx,Ax?b,x?0，若x是它的一个基解，y是其对偶问题的基

解，则恒有cx?yb.

解：

1. ×。如原问题是无界解，则对偶问题无可行解。P167 Th3。 2. ×。（1）的逆否命题。 3. √。P167 Thm4 4. ×。

原问题 对偶问题 若x,y为可行解

maxf?cx ming?yb 则有cx?yAx?yb

s.t.?

6.已知线性规划问题

?yA?c?Ax?b s.t.? 但若x,y为基解，则不一定

?y?0?x?0minf?3x1?2x2,

??x1?2x2?4??3x1?2x2?14s.t.? ?x1?x2?3??x1,x2?0（1） 写出它的对偶问题；

（2） 应用对偶理论证明原问题和对偶问题都存在最优解.

解：对偶问题

maxg?4y1?14y2?3y3

??y1?3y2?y3?3? s.t.?2y1?2y2?y3?2

?y,y,y?0?123（1） 原问题显然有可行解x??0,12?

T对偶问题可行解y??0,0,1?

T则由Thm4（P167）得 原问题和对偶问题都有最优解

8.某文具用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每月白坯纸供应量为3万公斤。已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或生产日记本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸103公斤，每打日记本用白坯纸403公斤，每箱练习本用白坯纸803公斤。又知每生产一捆原稿纸可获利润2元，生产一打日记本获利3元，生产一箱练习本获利1元，试确定：

（1） 现有生产条件下获利最大的方案；

（2） 如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为

每人每月40元，则该工厂要不要招收临时工，招收多少临时工合适？

解：设每月生产原稿纸x1捆，日记本x2打，练习本x3箱 标准形minf???2x1?3x2?x3

?3000?x1?x2?x3?x4?s.t.?103x1?403x2?803x3?x5?30000 ?x,??,x?05?1以B??a4a5?为基的初始单纯形表

0 2 3 1 0 0 3000 1 1 1 1 0 30000 103 403 803 0 1 变为

-9000 -1 0 -2 -3 0 3000 1 1 1 1 0 -10000 -10 0 403 ?403 1 对偶单纯形法

-8000 0 0 ?103 ?53 ?110 2000 0 1 73 ?13 1110 1000 1 0 ?43 43 ?110 所以最优解为x??100020000?，最优值f?8000，最优基B?(a2Ta1)

原问题的对偶问题的最优解y??53,110? 对偶问题ming?100y1?30000y2

?130y1?103y2?2??130y1?403y2?3s.t.? ?130y1?803y2?1??y1,,y2?0其最优解为y??50,110?，则临时工的影子价格为50元/月?市场价40元/月 所以应招收临时工。

对b1作灵敏度分析b1?b1??

?1000??40?110?????1000??40???1000?40??xB?B?1b???2000??????10110????0?????2000??????10??????2000?10???

?????????????1000?40??0则要保持最优基不变，需要?，则?25???200

?2000?10??0所以75?b1?300内最优基不变

则招工的最大人数为300?100?200，f?8000?2000?(50?40)?10000