?a11?am1?????J????a?a?mn??1n?x1??b1????????=??? ?xn??bn??????x1??b1???????????(kaj1,kaj2,?kajn) ?xj?=?kbj?
???????????xn??bn?????从而得出结论 二、（12%）有三个线性规划：
(?)?Min?z?CX(??)?Min?z??C?X(???)?Min?z?CX
约束条件AX＝b 约束条件AX＝b 约束条件AX＝b X ? 0 X?0 X?0是（ ?）的最优解 ，X??是（ ??）的最优解 ，Y?是（?）的对偶问题的最优解已知：X?，
试证：（1）(C??C)(X???X?)?0；（2）C(X??X)?Y?(b?b)。（2000） 解：(1)
因为所以所以(2)
CX'?CX''C(X'?X'')?0C'(X''?X')?0(1)
又因为C'X''?C'X'(2)(2)?(1)得(C''?C')(X''?X')?0设Y是(ΙΙΙ)的对偶问题的最优解C(X??X)?CX??CX?Y?b?Yb?Y?b?Y'b?Y?(b?b)2.在使用单纯形法求解线性规划问题
maxZ?CX?AX?b?
s.t.???X?0?时，设当前基B??P1,?,Pm?.证明：若xk为某非基变量，检验数
?k?ck?CBB?1Pk?0，
由此确定Pk为进基变量，则能保证新的基本可行解的目标值得以改善。(1998)
2.
证明：令 A?(B,N)C?(CB,CN)?XB?有(B,N)???b?BXB?NXN?b?XN??XB?B?1b?B?1NXN?X?令当前X??B? 即XN?(0,0?0)T ?0?带入目标函数??CBXB?CNXN?CBB?1b?(CN?CBB?1N)XN???CBB?1bxk入基后 即xk???0?0??????'?1?1??CBBb??CN?CBBN???????????0???0??????
?1?1?CBBb????cm?ck?cn??CBB?Pm?Pk?Pn?????????????0???CBB?1b??ck?CBB?1Pk??????k???一（14％）
对某线性规划问题 MaxZ?CX?AX?b ?
X?0?已确定一可行基本B,CB为基变量价格系数向量，A?(P1,P2,?,Pn)（1）请用数学方法证明，当所有非基变量检验数?j?cj?CBBPj?0时，当前基本可行解为最优。
（2）请从经济含义的角度出发，说明上述判断的正确性。(1997) 解：
一．
?1
（一）确定换出基的变量
因为总存在<0的bi，令br=min?bi?,其对应变量xr为换出基的变量
iCB C1 基 b x1 1 0 xr 0 1 xm 0 0 xm?1 a1.m?1 xn a1.n x1 b1 Cr xr br ar.m?1 ar.n Cm xm bm 0 0 0 0 1 am.m?1 am.n ?j Cm?1?zm?1 Cs?zs Cn?zn
（二）确定换入基变量
（1）为了使下一个表中第r行基变量为正值，因而只有对应arj<0的非基变量才可以考虑作为换入基的变量
???cj?zj?c?zarj?0??ss （2）为了使下一个表中对偶问题的解仍为可行解，令??min?jars???arj?称ars为主元素，xs为换入基的变量 设下一表中的检验数为cj?zj
??'?cj?zj?'?cj?zjcs?zs???cj?zj????cs?zs??arj??
arsars??arj??arj（a）对arj?0时，因cj?zj?0 故以cj?zjcj?zjarj?0 有因为主元素ars?0 所以
cs?zs?0 所ars???0
'（b）对arj?0 因
cj?zjarj?'cs?zs?0 故?cj?zj??0 ars
解： 解： 解： 解： 解： 解： 解： 解： 解：
二、运输问题
２．将非平衡运输问题化为平衡运输问题，在表上相当于增加一个虚设的 ，在模型中相当于增加若干个 变量。（2007）（2004） 解：2．产地或销地；松弛。
9．运用表上作业法求解运输问题时，计算检验数可以用 b ，确定初始方案可以用 a 。 （a）最小元素法 （b）比回路法
4. 用表上作业法求解m个发点和n个收点的平衡运输问题，其方案表上有数格的个数
为 ，空格的个数为 ；若从检验数为-2的某空格调整，调量为2，则调后可使总运费下降 。(2000) 解：m+n-1, (m-1)(n-1), 4.
3．用表上作业法求解某运输问题，若已计算出某空格的检验数为-2，则其经济意义是 ，若从该空格出发进行调整，该调整量为2，则调后可使总运费下降 。（1999）
解：3、该处每增运一个单位，将使总成本降低2
二、（13%）用表上作业法求解下面的平衡运输问题
minz???cijxij
i?1j?1mn?n??xij?ai,i?1,?,m?j?1?ms..t??xij?bj,j?1,?,n ?i?1?xij?0,i?1,?,m;j?1,?,n??时，计算某方案的空格[i,j]检验数?ij可采用位势法，其主要步骤如下：
（1）建立线形方程组Ui+Vj=Cij,其中Cij为所有有数个的运价，Ui，Vj分别称发地i和收地j的位势。
（2）令U1=0，求解得位势值Ui，Vj，i=1，??，m, j=1,??,n （3）?ij= Cij-(Ui+Vj)
试证明该方法的正确性，即证明空格[i,j]的检验数为
?ij= Cij-(Ui+Vj)
（1999） 解： 解： 解： 解： 解： 解：
三、多目标规划
2．目标规划模型的一个主要特点是引入了______________变量，模型的目标就是这些变量的极_____（大还是小）化，模型的约束中也要包括用这些变量表示的_____________约束。（2005）
解：2、偏差 小 目标（软）
3． 目标规划模型的一个主要特点是引入了偏差变量，模型的目标就是这些变量的极 小
（大还是小化），模型的约束中也要包括用这些变量表示的目标约束。(2002)