3.若产品x3值为生产，则x3应为基变量，?在单纯性表中?3?0，即C3至少应为?5????6??1?0?????6???4?????203
4.设新产品为x7，则?7?8???6?10
二（20％）
有一线性规划为 Maxz?c1x1?c2x2 s.t a11x1?a12x2?b1 a21x1 ?a22x2?b2 x1 ,x2 ?0
设 X3,X4 为引入的松弛变量。得到最优单纯形表如上表，要求： （1）利用最优解求c1,c2. （2）利用最优解求b1,b2
XB X1 X1 X2 X3 X4 1 0 3 -1 0 1 -1 1 0 0 -3 -1 解 1 2 -8 X2 ?J （3）C2 能变化多少而不至影响最优解；当 C2?1 时求最优解；
?1? （4）假定用b+λb代替b,其中b????1??(??????),求出使最优基保持不变的λ的范
????围.
（5）求出各资源的剩余量和影子价格。(1997) 解：二
maxz?c1x1?c2x2a11x1?a12x2?a13x3?b1a21x1?a22x2?a23x4?b2x1,x2,x3,x4?0
xB x1 x2 x1 1 0 0 x2 0 1 0 x3 3 -1 -3 x4 -1 1 -1 解 1 2 -8 ?j
（1）?3?C3?CBB?1P3 ?3?0??C1C2???3?? ??1???1?? ?1?
?1 ?1?0??C1C2???4?C4?CBBP4 C1?2,C2?3
3?b???3b1?b2?1?3?1??b1??1??3b1?b2??1??12?1??(2) Bb?? ???? ??????? ??11b2?b?b2?b?b?27???2????12????12?b?2??2(3) C2的变化影响检验数，设C2的变化量为?C
?3?0??2,3??C???3???0 即 6??3??C??0 ??1???1??4?0??2,3??C????0 ?2??3??C??0
?1?
?1??C?3 当C2=1时 CB XB Bb 2 X1 1 1 X2 2 ?1 2 1 0 0 X1 X2 X3 X4 1 0 3 -1 0 1 -1 1 0 0 -5 1 1 1 2 0 0 1 -1 1 0 -1 -4 0 ?J 2 X1 3 0 X4 2
?J
??fk?Sk??minVk?fk?1?Sk?1????? X???3,0,0?, 2 Z?2?3?0?1?6 ?f4?S4??1950?1180??3???3?1???2??1???1*B?b??b?????????????0
??11???7???1????????2????3???3?1???2???????????????0??11???7????????????2??7?91?3?????0?????1?2?2????4?????1
4??3???7???0???1???22（5）X1?1,X2?2 B?1???（4）
?3?1?1?11??1 ?X,XB???12?????X1,X2?
2?13???11? Max?2X1?3X2
13?1X?X??21222?37?1 s.t?X1?X2?
22?2?X1,X2?0?? 第一种资源剩余为0 第二种资源剩余为0
影子价格分别为-3，-1 解： 解：
解： 解：
（五）证明题
三（15分）、考虑下面两个线性规划：
(I)?Min?z?CX(II)?Min?z'?C'X约束条件AX?bX?0约束条件AX?b
X?0?C'?C?X'*?X*?0（2007） 已知X*是(I)的最优解，X'*是(II)的最优解，试证：解：三、
??因为所以所以CX*?CX'*C(X*?X'*)?0C'(X'*?X*)?0(1)
又因为C'X'*?C'X*(2)(2)?(1)得
(C'?C)(X'*?X*)?0maxz?CX三（11%）、考虑线性规划问题（P）?Ax?b??X?0
1．若X1,X2均为（P）的可行解，???0,1?，证明?X1?(1??)X2也是（P）的可行解；
2．写出（P）的对偶模型（仍用矩阵式表示）。（2006）
三、1证明：令?X1?(1??)X2?X3，若X3是（P）的可行解，则应满足
??AX3?b??(1)
?X3?0???(2)因为X1,X2均为(P)的可行解，?AX1?b?AX2?b即?；，?X?0X?0?1?2 所以AX3?A[?X1?(1??)X2]??AX1?(1??)AX2
??b?(1??)b?b即X3满足(1).又因为??[0,1],X1?0,X2?0,故有?X1?0,(1??)X2?0, 所以X3??X1?(1??)X2?0,
即X3满足(2).所以X3??X1?(1??)X2也是(P)的可行解.2．对偶模型
minw?bTY?ATY?CT ??Y无限制三（10%）、证明线性规划中的互补松弛定理：设（P）[max]z=CX,X?{X|AX?b,X?0},(D)[min]u=Yb,Y?{YA?b,Y?0},若X,Y分别是（P）（D）的可行解，Xs,Ys分别是其相应的松弛变量，则X,Y是（P），（D）的最优解的充要条件是：YXs?YsX?0；
并解释互补松弛定理的经济意义。（2004） 解： 三、
互补松弛定理的经济意义是：资源有剩余，则其影子价格为0，反之，影子价格为0说明资源恰好用完。
四、(21%)试证明线性规划原问题中第J个约束扩大K倍,其对偶规划最优解中第J个变量将缩小K倍（2003）
?a11?am1?????解：四、设原问题为maxZ=CX AX=b对偶????a?a?mn??1n?y1??C1????????≥??? ?ym??CN?????