minZ???cijxiji?1j?1nmn（2）
s.t.?i?1xij?ai?i?1,2,?,m???j?1?m答: ?ui?vj?cij????xij?bj?j?1,2,?,n??ui,vj不限制?i?1?xij?0?i?1,2,?,m;j?1,2,?,n??(i?1，2，...，m；j???maxw??aiui??bjvjj?1mn?1，2，...，n)8．用对偶单纯形法求解下列线性规划问题:
minZ?x1?x2?2x1?x2?4 ?x?7x?7?12?x,x?0?12（1）
s.t. 解:化成标准形式，列对偶单纯形表
cj -1 -1 0 0 CB XB x1 x2 x3 x4 b 0 x3 0 x4 -2 -1 1 0 -4 -1 -7 0 1 -7 λj=cj-zj -1 -1 0 0 0 采用对偶单纯形迭代规则得最优表： -1 x1 -1 x2 1 0 7/13 1/13 21/13 0 1 1/13 -2/13 10/13 31/13 λj=cj-zj 0 0 -6/13 -1/13 最优解X=(21/13,10/13,0,0) ,最优值minZ= 31/13(maxZ’=-31/13) 。
minZ?4x1?12x2?18x3?x1?3x3?3??2x2?2x3?5?x,x,x?0?123（2）
s.t.解: 化成标准形式，列对偶单纯形表
6
cj -4 -12 -18 0 0 CB XB x1 x2 x3 x4 x5 b 0 X4 0 X5 -1 0 -3 1 0 -3 0 (-2) -2 0 1 -5 λj=cj-zj -4 -12 -18 0 0 0 X4 -1 0 (-3) 1 0 -3 0 1 1 0 -1/2 5/2 -12 X2 λj=cj-zj -4 0 -6 0 -6 -18 X3 -12 X2 1/3 0 1 -1/3 0 1 1/3 1 0 0 -1/2 3/2 λj=cj-zj -2 0 0 -2 -6 最优解X=(0,3/2,1,0,0) ,
最优值minZ=36(maxZ’=0-(3/2)×12-1×18=-36) 。 9．设 min Z?3x?5x?x?2x?4x12345
s.t.?x1?x2?x3?3x4?x5?6???x1?x2?2x3?x4?x5?3?x,x,x,x,x?0?12345（1）写出其对偶问题。 （2）求解对偶问题。
（3）从对偶解中求出原问题的解。 答：（1）对偶模型
7
maxw?6y1?3y2?y1?y2?3?y?y?512??y1?2y2??1s.t.??3y1?y2?2?y1?y2??4??y1?0,y2?0*
（2）求解对偶问题，图解法。得Y=(-3,1) ,w=-15 。
（3）利用互补松弛性求原问题解，由y1,y2异于0，知原约束均为等式；又由对偶约束1，2，4式为严格不等式，故可得x1,x2,x4等于0。代入原约束方程组，解得x3=3，x5=3, 即X=(0,0,3,0,3),最优值z=-1×3-4×3=-15=w。
10．从下面最优单纯形表中（最大化问题，约束条件均为“?”连接）
（1）写出原问题与对偶问题的最优解。 （2）求
?Z?Z，?b1?x6-5
*
*
*
T
，并解释这两个数值的含义。
52（3）如果以代价增添第一种资源一个单位，是否值得？ （4）若有人原向你购买第三种资源，应要价多少才合算？
（5）是否有其它最优解，如果没有，说明为什么？如果有，则求出另
8
一个最优解。
解：(1)原问题最优解X*=(2,0,3/2,0,1,0)T ,对偶问题最优解Y*=(4,0,9,0,0,0)。
(2)在最优表上可以得到最优基的逆B,
-1-1
?201????1B??104??116???根据最优表上Pj’=BPj ,可解得Pj=BPj’,从而得A,
?47?A??27??1?7477?177?12?1?11277100??010?001???47?b?Bb???27??1?7?177?11270??2??1314??????0??32????1114??1??1?1?????7?对偶解---单纯形因子
CBB?1?Y?(4,0,9)?1?1c???CB??c?CBP?0再由检验数 j j B j ,可得 j j B P j
解得C=(1,1,2,0,0,0) ，最优值z*=1×2+0+2×(3/2)=5。
?Z在最优方案时，有?b?y1?4 ,因为b1影子价格大于0,是稀缺资源，故
1在一定范围内每增加一个单位该种资源就会增加4个单位总收入（影子价格或边际收入为4）。
9
?Z对?x?c6 ，x6表示第三种资源剩余数量，该偏导数值表示资源剩余量
6对总收入的影响率。在初始方案时其值为0，在最佳方案时其值为-9，从另外角度说明引入该资源有利于减少短缺造成的损失或增加收入（影子价格为9）。
(3) 如果以代价增添第一种资源一个单位, 会增加4个单位总收入，值得。
(4) 若有人愿向你购买第三种资源，要价不低于其影子价格9才合算。 (5) 在最优表上,非基变量x2的检验数为0，故最优解不唯一。令x2进基，x1出基，换基迭代得新最优解X*=(0,2,3/2,0,5)T ,最优值z*=0+1×2+2(3/2)=5 。
maxZ??5x1?5x2?13x3??x1?x2?3x3?20??12x1?4x2?10x3?90?x,x,x?0?1235211．设
s.t.?1? ?2?先用单纯形法求出最优解，再分析在下列各条件单独变化的情况下最优解的变化。
（1）约束条件（2）右端常数由90变为70。 （2）目标函数中x3的系数由13变为8。 （3）增加一个约束条件：2x1?3x2?5x3?50 解: 先用单纯形法求出最优解
MAX:-5X1 +5X2 +13X3 ST:
1] -1X1 +1X2 +3X3 +1X4 = 20 2] 12X1 +4X2 +10X3 +1X5 = 90 得到了第一个可行基 用最大检验数法
----------------------------------------------------------
10
补充线性规划问题练习题解答
