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
补充线性规划问题练习题解答
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)