第二章 线性规划习题(附答案)
- 格式：doc
- 大小：938.50 KB
- 文档页数：23
习题2-1 判断下列说法是否正确：（1） 任何线性规划问题存在并具有惟一的对偶问题； （2） 对偶问题的对偶问题一定是原问题；（3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；（4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；（5） 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况； （6） 应用对偶单纯形法计算时，若单纯形表中某一基变量x i <0，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解。
（7） 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；（8） 已知y i 为线性规划的对偶问题的最优解，若y i >0，说明在最优生产计划中第i 种资源已经完全耗尽；若y i =0，说明在最优生产计划中的第i 种资源一定有剩余。
2-2将下述线性规划问题化成标准形式。
⎪⎪⎩⎪⎪⎨⎧≥≥-++-≤+-+-=-+-+-+-=无约束43214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z ()⎪⎩⎪⎨⎧≥≤≤-+-=++-+-=无约束321321321321,0,0624.322min 2x x x x x x x x x st x x x z 解：(1)令'''444x x x =-，增加松弛变量5x ，剩余变量6x ，则该问题的标准形式如下所示：'''12344'''12344'''123445'''123446'''1234456max 342554222214..232,,,,,,0z x x x x x x x x x x x x x x x x s t x x x x x x x x x x x x x =-+-+-⎧-+-+-=⎪+-+-+=⎪⎨-++-+-=⎪⎪≥⎩ (2)令'z z =-，'11x x =-，'''333x x x =-，增加松弛变量4x ，则该问题的标准形式如下所示：'''''1233''''1233''''12334''''12334max 22334..26,,,,0z x x x x x x x x s t x x x x x x x x x x =+-+⎧++-=⎪+-++=⎨⎪≥⎩ 2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。
()⎪⎩⎪⎨⎧≥≤+≤++=0,825943.510max 121212121x x x x x x st x x z ()⎪⎩⎪⎨⎧≥≤+≤++=0,24261553.2max 221212121x x x x x x st x x z 解：(1)图解法最优点为B 点，最优解为x1=1,x2=3/2，最优值为35/2。
单纯形表计算过程：初始单纯形表（对应O 点）z ’ x 1 x 2 x 3 x 4 RHS z ’x 3 9/3 x 4 8/5 第一次迭代（对应A 点）z ’ xx x x RHS z ’x 3 /14/5x 18/5/4/5●第二次迭代（对应B点，即最优解）z’x1x2x3x4RHSz’x2x1(2)图解法初始单纯形表（对应O点）z’x1x2x3x4RHSz’x315/3x424/6第一次迭代（对应A点）z’x1x2x3x4RHSz’x33/4x14/1/3 ●第二次迭代（对应B点，即最优解）z’x1x2x3x4RHSx2x1⎪⎩⎪⎨⎧≥≤++++≤++++057234219532..5432154321j x x x x x x x x x x x t s ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥+≥+≥+++≥++0226332..31434321421j x x x x x x x x x x x x t s 2-4已知线性规划问题，写出其对偶问题：（1）(2)解：(1)原问题的对偶问题为：12121212121212min 19572104242320..3220525,0y y y y y y y y s t y y y y y y ω=++≥⎧⎪+≥⎪⎪+≥⎪⎨+≥⎪⎪+≥⎪≥⎪⎩(2)原问题的对偶问题为：1234124122341231234max 36223826..36,,,0y y y y y y y y y s t y y y y y y y y y y ω=+++++≤⎧⎪+≤⎪⎪++≤⎨⎪++≤⎪≥⎪⎩2-5运用对偶理论求解以下各问题： （1）已知线性规划问题： 543212*********max x x x x x z ++++=)5,4,3,2,1(=j 43216368min x x x x z +++=)4,3,2,1(=j 32122min xx x z +-=⎪⎩⎪⎨⎧≥≤≤-+-=++-无约束321321321,0,064..x x x kx x x x x x t s其最优解为 （a ）求k 的值；（b ）写出并求出其对偶问题的最优解。
解：原问题的对偶问题为：1212121212max 4621..20y y y y y y s t y ky y y ω=+--≥⎧⎪+≤-⎪⎨-=⎪⎪≤⎩无约束，设该对偶问题的三个人工变量为123,,s s s y y y ，由于原问题的最优解中的13,0x x ≠，则根据互补松弛性，所增加的人工变量130,0s s y y ==，则：122y y --=，122y ky -=。
另外，原问题的最优值*123222(5)02(1)12z x x x =-+=⨯--+⨯-=-，也为对偶问题的最优值，即：*124612y y ω=+=-。
结合上述三式可得：*1*2021y y k ⎧=⎪=-⎨⎪=⎩（2）已知线性规划问题：其对偶问题的最优解为， 。
1235,0,1x x x =-==-4321432max x x x x z +++=⎪⎩⎪⎨⎧≥≤+++≤+++0,,,2023220322..432143214321x x x x x x x x x x x x t s 2.11=y 2.02=y试根据对偶理论求出原问题的最优解。
解：首先写出原问题的对偶问题如下：121212121212min 20202122..233324,0y y y y y y s t y y y y y y ω=++≥⎧⎪+≥⎪⎪+≥⎨⎪+≥⎪≥⎪⎩由于该对偶问题的最优解为**121.2,0.2y y ==，代入对偶问题的约束条件中可得121.612.62..3344,0s t y y >⎧⎪>⎪⎪=⎨⎪=⎪≥⎪⎩，即对偶问题中的松弛变量1234,0,,0s s s s y y y y ≠=。
则根据互补松弛性可知，原问题中的决策变量12,x x 必为0。
将12,x x =0代入原问题中的约束条件，可得：13423423203220s s x x x x x x ⎧++=⎨++=⎩。
又因为**121.2,0.2y y ==均不为0，则同样根据互补松弛性可知，12,0s s x x =。
则有：343423203220x x x x +=⎧⎨+=⎩。
求解该方程组可得：344,4x x ==。
（3）已知线性规划问题:⎪⎩⎪⎨⎧≥≤-+-≤++-+=0,,12.max 32132132121x x x x x x x x x st x x z 试根据对偶问题性质证明上述线性规划问题目标函数值无界。
解：首先写出原问题的对偶问题如下：1212121212min 211..00y y y y y y s t y y y y ω=+--≥⎧⎪+≥⎪⎨-≥⎪⎪≥⎩， 由于该对偶问题中前两个约束条件所确定的可行域为空集，可知该对偶问题无解。
则根据对偶性质可知，原问题无解可无界。
另外，(0,0,0)x =必为原问题的解之一，则可证原问题无界。
2-6已知某求极大值线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表2-44所示，求表中各括弧内未知数的值。
表2-44 初始单纯形表及最终单纯形表z x 4 x 5 x 6 ：：z x 4 x 1 x 2解：由初始单纯形表中的基变量为456,,x x x 可知，1B -为最终单纯形表中456,,x x x 所对应的消耗系数矩阵，即：111/41/403/401/2B i h ---⎛⎫⎪= ⎪ ⎪⎝⎭则有：11110012102101d B a e c f -⎛⎫⎛⎫⎪ ⎪= ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭，可求得：2,3,1/4,5/4,a c d e ====1/2,1/2,1/4f h i =-=-=-。
另外：15/41525/4205/2b B -⎛⎫⎛⎫⎪ ⎪= ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭，可求得10b =。
再由检验数计算公式1j B j j C B p c σ-=-可求得363/4,1/4σσ==；而基变量的检验数必为零，所以20σ=。
即0,3/4,1/4k g j ===。
2-7用对偶单纯形法求解下列线性规划问题。
()⎪⎩⎪⎨⎧≥≥+≥+++=0,,52233.18124min 13213231321x x x x x x x st x x x z ()⎪⎩⎪⎨⎧≥≥++≥++++=0,,10536423.325min 2321321321321x x x x x x x x x st x x x z解：(1) 令z ，=- z 引进松弛变量x 4，x 5≥0，标准化123134********max '4121832.225,,,,0z x x x x x x st x x x x x x x x =---+-=⎧⎪++=⎨⎪≥⎩列出初始单纯形表，z ，x 4x 5-12/-2-18/-2 选取x 2进基。
即选取a 22=-2为主元，进行旋转运算，得到以下单纯形表。
，z ，x 4x 2-4/-1-6/-3选取x 4出基，a 13=-3为主元进行旋转运算。
，z ，x 3x 2当前基既是原始可行基，又是对偶可行基，因而是最优基。
