《线性规划习题(附答案)》由会员分享，可在线阅读，更多相关《线性规划习题(附答案)（23页珍藏版）》请在金锄头文库上搜索。
1、习题习题2-1 判断下列说法是否正确： （1）任何线性规划问题存在并具有惟一的对偶问题； （2）对偶问题的对偶问题一定是原问题； （3）根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之， 当对偶问题无可行解时，其原问题具有无界解； （4）若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最 优解； （5）若线性规划问题中的 bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；（6）应用对偶单纯形法计算时，若单纯形表中某一基变量 xi0，说明在最优生产计划中 第 i 种资源已经完全耗尽；若 yi=0，说明在最优生产计划中的第 i
2、 种资源一 定有剩余。 2-2 将下述线性规划问题化成标准形式。 无约束43214321432143214321, 0,232142224.5243max) 1 (xxxxxxxxxxxxxxxxstxxxxz 无约束321321321321, 0, 0624.322min2xxxxxxxxxstxxxz解：(1)令，增加松弛变量，剩余变量，则该问题的标准形式如 444xxx5x6x下所示： 12344 12344 123445 123446 1234456max34255422 2214. .232 ,0zxxxxxxxxxx xxxxxxstxxxxxx x x x x x x x (2)
3、令，增加松弛变量，则该问题的标zz 11xx 333xxx4x准形式如下所示： 1233 1233 12334 12334max22334 . . 26 ,0zxxxxxxxx stxxxxx x x x x x 2-3 分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各 基可行解对应图解法中可行域的哪一顶点。 0,825943.510max121212121xxxxxxstxxz 0,24261553.2max221212121xxxxxxstxxz解：(1)图解法最优点为 B 点，最优解为 x1=1,x2=3/2，最优值为 35/2。单纯形表计算过程： 初始单纯形表（对应
4、 O 点）zx1x2x3x4RHSz1-10-5000x30341099/3x40520188/5第一次迭代（对应 A 点）zx1x2x3x4RHSz10-10216x30014/51-3/521/521/5/14/5x11012/501/58/58/5/4/5第二次迭代（对应 B 点，即最优解）5x1+2x2=8x2x1O(0,0)A(8/5,0)B(1,3/2)3x1+4x2=9zx1x2x3x4RHSz1005/14 25/14 35/2x25015/14 -3/143/2x11010-1/72/71(2)图解法最优点为 B 点，最优解为 x1=15/4,x2=3/4，最优值为 33/4
5、。单纯形表计算过程： 初始单纯形表（对应 O 点）zx1x2x3x4RHSz1-2-1000x3035101515/3x4062012424/6第一次迭代（对应 A 点）zx1x2x3x4RHSz10-1/301/38x30041-1/233/4x1211/301/644/1/3第二次迭代（对应 B 点，即最优解）zx1x2x3x4RHSz1001/127/2433/4x21011/4-1/83/4x1210-1/12 5/2415/42-4 已知线性规划问题，写出其对偶问题：543212520202410maxxxxxxz6x1+2x2=24x2x1O(0,0)A (4,0)B(15/4,3
6、/4)3x1+5x2=15057234219532. .5432154321jxxxxxxxxxxxts0226332. .31434321421jxxxxxxxxxxxxts无约束321321321, 0, 064. .xxxkxxxxxxts（1）(2)解：(1)原问题的对偶问题为：12121212121212min19572104242320. .3220525,0yyyyyyyystyyyyy y (2)原问题的对偶问题为：1234124122341231234max36223826. .36,0yyyyyyyyystyyyyyyy yyy 2-5 运用对偶理论求解以下各问题： （1）
7、已知线性规划问题：)5 , 4 , 3 , 2 , 1( j43216368minxxxxz)4 , 3 , 2 , 1( j32122minxxxz其最优解为 （a）求 k 的值； （b）写出并求出其对偶问题的最优解。 解：原问题的对偶问题为：1212121212max4621. .20yyyyyystykyyy 无约束，设该对偶问题的三个人工变量为，由于原问题的最优解中的123,sssyyy，则根据互补松弛性，所增加的人工变量，则：13,0x x 130,0ssyy，。122yy122yky另外，原问题的最优值，也* 123222 ( 5)02 ( 1)12zxxx 为对偶问题的最优值，即
8、：。* 124612yy 结合上述三式可得：* 1 * 2021yyk （2）已知线性规划问题：其对偶问题的最优解为， 。 试根据对偶理论求出原问题的最优解。1235,0,1xxx 4321432maxxxxxz0,2023220322. .432143214321xxxxxxxxxxxxts2 . 11y2 . 02y解：首先写出原问题的对偶问题如下：121212121212min202021 22 . . 233324 ,0yyyy yy styyyy y y 由于该对偶问题的最优解为，代入对偶问题的约束条件中可* 121.2,0.2yy得，即对偶问题中的松弛变量。则根据互121.612.
9、62 . . 3344,0sty y 1234,0,0ssssyyyy补松弛性可知，原问题中的决策变量必为 0。12,x x将=0 代入原问题中的约束条件，可得：12,x x。又因为均不为 0，则同样根据互补松1 34 2 342320 3220ssxxx xxx * 121.2,0.2yy弛性可知，。则有：。求解该方程组可得：12,0ssx x 34342320 3220xx xx 。344,4xx（3）已知线性规划问题:0,12.max32132132121xxxxxxxxxstxxz试根据对偶问题性质证明上述线性规划问题目标函数值无界。 解：首先写出原问题的对偶问题如下：12121212
10、12min21 1. .0 0yyyy yystyy yy ，由于该对偶问题中前两个约束条件所确定的可行域为空集，可知该对偶问题无 解。则根据对偶性质可知，原问题无解可无界。另外，必为原问题的解之一，则可证原问题无界。(0,0,0)x 2-6 已知某求极大值线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形 表如表 2-44 所示，求表中各括弧内未知数的值。 表 2-44 初始单纯形表及最终单纯形表zx1x2x3x4x5x6RHSz1-3-2-20000x40111100（b ）x50(a)1201015x602(c)100120：zx1x2x3x4x5x6RHSz1 0（k ）（g ）0
11、5/4（j ）95/4x4000（d ）(l)-1/4-1/45/4x1310（e ）03/4（i ）25/4x2201（f ）0（h ）1/25/2解：由初始单纯形表中的基变量为可知，为最终单纯形表中456,x x x1B所对应的消耗系数矩阵，即：456,x x x111/ 41/ 4 03/ 4 01/ 2Bi h 则有：，可求得：11110012102101dBaecf 2,3,1/ 4,5/ 4,acde。1/ 2,1/ 2,1/ 4fhi 另外：，可求得。15/ 4 1525/ 4 205/ 2b B 10b 再由检验数计算公式可求得；而基变1 jBjjC B pc363/ 4,1/
12、 4量的检验数必为零，所以。即。200,3/ 4,1/ 4kgj2-7 用对偶单纯形法求解下列线性规划问题。 0,52233.18124min13213231321xxxxxxxstxxxz 0,10536423.325min2321321321321xxxxxxxxxstxxxz解：(1) 令 z，=- z 引进松弛变量 x4，x50，标准化12313423512345max 4121832. 225,0zxxxxxxstxxxx x x x x 列出初始单纯形表z，x1x2x3x4x5RHSz，141218000x40-10-310-3x500-2-201-5-12/-2-18/-2选取
13、x2进基。即选取 a22=-2 为主元，进行旋转运算，得到以下单纯形表。z，x1x2x3x4x5RHSz，140606-30x40-10-310-3x2-120110-1/25/2-4/-1-6/-3选取 x4出基，a13=-3 为主元进行旋转运算。z，x1x2x3x4x5RHSz，120026-36x3-181/301-1/301x2-12-1/3101/3-1/23/2当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为x1=0，x2=3/2，x3=1，max z，=-36，即 min z=36(2) 令 z，=- z 引进松弛变量 x4，x50，标准化12312341235123
14、45max 523324. 63510,0zxxxxxxxstxxxxx x x x x 列出初始单纯形表z，x1x2x3x4x5RHSz，1523000x40-3-1-210-4x50-6-3-501-10-2/-3-3/-5选取 x3 进基。即选取 a23=-5 为主元，进行旋转运算，得到以下单纯形表。z，x1x2x3x4x5RHSz，17/51/5003/5-6x40-3/51/501-2/50x3-36/53/510-1/52当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为x1=0，x2=0，x3=2，max z，=-6，即 min z=62-8 已知 2-45 表为求解某线性规划问题的最终单纯形表，表中 x4 , x5为松弛变量， 问题的约束为形式。 表 2-45 最终单纯形表zx1x2x3x4x5
