?zj?zj?1?(aj?zj)?y?y?kz?jj?1j?1st.??x1?x2???xj?yj?xj,yj,zj?0?(j?1,?,n)(j?1,?,n)(j?1,?,n)(j?1,?,n)
20.某公司有三项工作需分别招收技工和力工来完成。第一项工作可由一个技工单独完成，或由一个技工和两个力工组成的小组来完成。第二项工作可由一个技工或一个力工单独去完成。第三项工作可由五个力工组成的小组完成，或由一个技工领着三个力工来完成。已知技工和力工每周工资分别为100元和80元，他们每周都工作48H，但他们每人实际的有效工作时间分别为42和36H。为完成这三项工作任务，该公司需要每周总有效工作时间为：第一项工作10000H，第二项工作20000H，第三项工作30000H，能招收到的工人数为技工不超过400人，力工不超过800人。试建立数学模型，确定招收技工和力工各多少人。使总的工资支出为最小。
答：设ij为用j(j?1,2)种方式完成第i（i?1,2,3)项工作时招收的工人组数（第一项工作用第一种方式完成时，每个工人组内含技工1人，如用第二种方式完成时，每个组含技工1人，力工2个等）。则问题的线性规划模型可写为：
x?10000?42x11?(42?2?36)x12?42x21?36x22?20000???30000?(5?36)x31?(42?3?36)x32st.?x11?x12?x21?x32?400??2x12?x22?5x31?3x32?800?xij?0(i?1,2,3;j?1,2)??
(x?x12?x21?x32)人，力工人数为(2x12?x22?5x31?3x32)注：实际招收的技工数为11人。
minz?100(x11?x12?x21?x32)?80(2x12?x22?5x31?3x32)
第二章.对偶理论与灵敏度分析
1. 已知线性规划问题：
maxz?c1x1?c2x2?c3x3
用单纯形法求解得最终单纯形表如下表所示： （a） 求（b） 求 ??a11??a13??a12??b1??1??0???x1??a?x2??a?x3??0?x4??1?x5??b?st.??a?????21??22??2??23??xj?0(j?1,?,5)?
a11,a12,a13,a21,a22,a23和b1,b2
c1,c2,c3 x1x2x3x4x5x3 3/2 x2 2 1 1/2 0 1 1 0 1/2 －1 -1/2 2 cj?zj-3 0 0 0 -4 ：答
a11?9/2,a21?5/2,a12?1,a22?1,a13?4,a23?2,b1?8,b2?5,c1?7,c2?4,c3?8
?12. 已知矩阵A及其逆矩阵A如下：
?210??1/2?1/40???0??1A??020A?1/20??????11??401?? ??2?
试根据改进单纯形法中求逆矩阵的方法原理求下述矩阵B的逆矩阵B?1，已知
?251??B??0?12????441??
?250??5??11/4???1????1/2???1C??0?10A??????????4?????7?? ?441?? ? 答：先设
?111/20??1/25/20???A?1??0?C?1??0?20?10???????61??0?141???2? ?
?251??1??11/2???2????2??1?B??0?12C??????????441?? 有 ?1?????13??
B?1?1011/26???9/26?1/2611/26???C?1??8/26?2/26?4/26???01?2/13???????00?1/13???4/2612/26?2/26??
3. 已知线性规划的原问题与对偶问题分别为：
?
（P）原问题：maxz?CX (D)对偶问题：minw?Yb
?AX?b?YA?Cst.?st??X?0 ?Y?0
?
若Y为对偶问题最优解，又原问题约束条件右端项用b替换之后其最优解为X，试证明
?CX?Yb 有
证明：原问题右端项b用b替换后，新的原问题P及对偶问题D为：
''
maxz'?CZminw'?Yb?AZ?b?YA?Cst.?st.?P': ?Z?0 D': ?Y?0
*'*'
设D的最优解为Y，因有CZ?Yb，有Y是D的可行解，故有Yb?Yb，由此
CZ?Y*b
x4,x5为松弛变量，问题的约束
4. 已知下表为求解某线性规划问题的最终单纯形表，表中
条件为?形式。 x10 1 0 x2x31 0 0 x4x5x3 5/2 x1 5/2 cj?zj1/2 -1/2 -4 1/2 -1/6 -4 0 1/3 -2 (a)写出原线性规划问题 (b) 直接由表写出对偶问题的最优解。 答：（a）原线形规划问题如下：
maxz?6x1?2x2?10x3?x2?2x3?5?st.?3x1?x2?x3?10?x,x,x?0?123?
(b )对偶问题最优解为
5. 已知线性规划问题：
Y?(4,2)
maxz?5x1?3x2?6x3?x1?2x2?x3?18?2x?x?3x?16?123st.??x1?x2?x3?10?x1,x2?0,x3无约束 ?（a） 写出其对偶问题
（b） 已知原问题用两阶段法求解时得到的最终单纯形表如下 试写出其对偶问题的最优解。 5 3 6 －6 0 x10 x2 1 2 1 x3'x3'' 0 0 1 x4 1 0 0 x4 8 x5 1 14 －6 xs'' 4 0 1 0 0 0 －1 cj?zj0 －1 0 0 0 答： （a） 其对偶问题为
minw?18y1?16y2?10y3(1)?y1?2y2?y3?5?2y?y?y?3(2)?123st.?(3)?y1?3y2?y3?6??y1?0,y2,y3无约束
y第y（b） 设第（1）个约束条件的松弛变量为s1，（2）个约束条件的松弛变量为s2，
由原问题用两阶段法求得之最终单纯形表知
约束条件（1）~(3)有
ys1?0,ys2?1,y1?0，代入
?y1?2y2?y3?5??2y1?y2?y3?1?3?y?3y?y?623?1
(y,y,y)?(0,1,3)
解得：123
6.已知线性规划问题：
minz?2x1?x2?2x3??x1?x2?x3?4?st.??x1?x2?kx3?6?x?0,x?0,x无约束23?1
其最优解为
x1??5,x2?0,x3??1（a）求k的值；
（b）写出并求其对偶问题的最优解。 解：先写出其对偶问题如下：
maxw?4y1?6Y2
?y?y?2?12?y?y??1?12st.??y1?ky2?2??y1无约束,y2?0
