运筹学第2章对偶理论习题自然科学

1/1运筹学-第2章-对偶理论习题-自然科学

其次章线性规划的对偶理论

2.1写出下列线性规划问题的对偶问题

maxz=2x1+2x2－4x3

x1+3x2+3x3≤304x1+2x2+4x3≤80x1、x2，x3≥0

解：其对偶问题为

minw=30y1+80y2y1+4y2≥23y1+2y2≥23y1+4y2≥－4y1、y2≥0

2.2写出下列线性规划问题的对偶问题

minz=2x1+8x2－4x3

x1+3x2－3x3≥30－x1+5x2+4x3=804x1+2x2－4x3≤50

x1≤0、x2≥0，x3无限制

解：其对偶问题为

maxw=30y1+80y2+50y3y1－y2+4y3≥23y1+5y2+2y3≤8－3y1+4y2－4y3=－4

y1≥0，y2无限制，y3≤0

2.3已知线性规划问题

maxz=x1+2x2+3x3+4x4

x1+2x2+2x3+3x4≤202x1+x2+3x3+2x4≤20x1、x2，x3，x4≥0

其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。

解：其对偶问题为

minw=20y1+20y2

y1+2y2≥1（1）2y1+y2≥2（2）2y1+3y2≥3（3）3y1+2y2≥4（4）y1、y2≥0

将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以

2x3*+3x4*=203x3*+2x4*=20

解得x3*=x4*=4。故原问题的最优解为X*=（0，0，4，4）T

2.4用对偶单纯形法求解下列线性规划

minz=4x1+2x2+6x3

2x1+4x2+8x3≥244x1+x2+4x3≥8x1、x2，x3≥0

解将问题改写成如下形式

max（－z）=－4x1－2x2－6x3

－2x1－4x2－8x3+x4=－24－4x1－x2－4x3+x5=－8x1、x2，x3，x4，x5≥0

明显，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表2—7中。

表2—7CjCB00θ-20θx2x5－zXBx4x5－z－4x1-2-4-4-4/-21/2-7/2-3-3/(-7/2)－2x2[-4]-1-2-2/-41000－6x3-8-4-6-6/-102[-2]-2-2/-20x41000-1/4-1/4-1/2(-1/2)/(-1/4)0x501000100b-24-806-2-120-2-6x2x3－z-37/4-1/2100010-1/21/8-1/41-1/2-144-32最终一个单纯形表中，已得到一个可行的正侧解，因而得到问题的最优解为X*=（0，4，4）T最优值为z*=32

2.5设某线性规划问题的初始单纯形表和最优单纯形表分别为表2—9（初始单纯形表）CjCB00XBx4x5－z5x11254x21143x31430x41000x5010b60800

表2—10（最优单纯形表）CjCB45XBx2x1－z5x10104x21003x3-23-40x42-1-30x5-11-1b4020-260现在要问：

（1）c3在什么范围内变化，表中最优解不变？（2）c3从3变为8，求新的最优解

解（1）由于在最优单纯形表中，c3为非基变量的价格系数，因此其变化仅会影响到检验数σ3=－4，因此当Δc3≤－σ3=4时，表中最优解不变。

（2）当c3从3变为8时，则表中的检验数σ3从—4变为1，即表中的最优解将发生变化，用单纯形法求解得到如表2—11中所示的新的最优解。

表2—11CjCB4545XBx2x1－zx2x35x10102/31/34x2100108x3-2[3]1010x42-1-34/3-1/30x5-11-1-1/31/3b4020-260160/320/3－z00-4-3-1-740/3即新的最优解为X*=（0，160/3，20/3）T。2.6某工厂在方案期内要支配甲、乙两种产品，已知生产一件产品所消耗的A、B、C三种原材料的数量以及单位产品的利润如下表所示：表2—12单位原材料消耗产品甲1215乙3114资源限量（kg）908045ABC单位产品利润（千元/件）若x1、x2分别表示工厂生产甲、乙产品的数量，则使工厂获得最大利润的生产方案数学模型为：

maxz=5x1+4x2

x1+3x2≤902x1+x2≤80x1+x2≤45x1、x2，x3≥0

用单纯形法求解该问题时，其初始单纯形表和最优单纯形表分别如表2—13和3—14所示，试分析使最优基不变的b3的变化范围。

表2—13（初始单纯形表）CjCB000XBx3x4x5－z5x112154x231140x310000x401000x50010b9080450

表2—14（最优单纯形表）CjCB054XBx3x1x2－z5x101004x200100x310000x421-1-10x5-5-12-3b253510-215解由表2—13和表2—14可知，当B=（p3，p1，p2）时，有

?1B?1???0?0?21?1?5???1?2??

?25??1Bb??35?10??????当下式成立时，最优基不变。

?25??1?1Bb?B?b??35?10???1?????0??0??21?1?5??0???1??0?2????b3??25?5?b3?????35??b3??10??b3??????0??

即25－5Δb3≥0，35－Δb3≥0，10+Δb3≥0解不等式有

－5≤Δb3≤5此外，以B-1的第三列各元素去除最优单纯形表中右端常数项对应各列，用公式可直接求出Δb3，即

25??10??35max??,????b?min???

?5??2???1同样可得－5≤Δb3≤5

因此，不影响最优基的b3的变化范围是[40，50]。

2.7在例2.11的生产方案问题中：（1）若生产产品甲的工艺结构发生了改进，

‘

这时关于它的技术向量变为p1=（1，2，1/2）T，试分析对原最优方案有什么影响；（2）若该厂除了生产前两种产品外，拟开发新产品丙，已知产品丙每件消耗A、B、C原材料各为2、4、1kg，每件可获利润8千元。问该厂是否应当生产该产品和生产多少？

解（1）由于产品甲生产工艺的改进，这样原最优单纯形表中的第1列将会发生转变，