运筹学基础及应用

1、运筹学根底及应用习题解答习题一 P461.1|X2 +4x1 2x2 4 4 4xi 6x262的所有X1,X2该问题有无穷多最优解，即满足4xi 6X2 6且 0 X2此时目标函数值z 3。(b)所以该问题无可用图解法找不到满足所有约束条件的公共范围， 行解。1.2(a)约束方程组的系数矩阵12 3 6 3 0 0A 814 0 20最优解 x 0,10,0,7,0,0 T3 0 0 0 01基基解是否基可行解目标函数值X1X2X3X4X5X6P1P2 P3167否000036P1P2P40100700是10P1P2P57是3030002P1P2 P6721否400044P1P3 P45否0

2、08002P1P3P53是3000802P1P3P61否100032P1P4P5000350是0P1P4P6515否002044o(b) 约束方程组的系数矩阵基基解是否基可行解目标函数值X1X2X3X4P1P211否4002P1P3211是4300555P1P4111否0036P2P31是50202P2P41否0022P3P40011是5最优解(1)图解法最优解即为的解，最大值z 35(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式max z 10x1 5x2 0x3 0x43x1 4x2 x39st.5x1 2x2 x48那么F3，P4组成一个基。令XiX2 0得基可行解x

3、0,0,9,8，由此列出初始单纯形表Cj10500Cb基bX1X2X3X40X3934100X485201CjZj10500Cj10500Cb基bX1X2X3X4c210X3582110 一10一1555CjZj0102新的单纯形表为1, 2 0，说明已找到问题最优解z*352(b)x1 1- x2 2 ' X3 0, x4 0。最大值Cj10500cB基bX1X2X3X43535X 2012 2141410X11121077525CjZj001414(1)图解法Xi(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式max z 2x1 x2 0x3 0x4 0x5st.

4、5x2 x3156x1 2x2 x424XiX2X55那么P3， F4， P5组成一个基。令xi X2 0得基可行解x 0,0,15,24,5，由此列出初始单纯形表Cj21000CB基bX1X2X3X4X50X315051000X42420100X5511001cjZj21000Cj21000Cb基bX1X2X3X4X5051000X315111002X4436210X510013611CjZj03030min15 3320，,24,-522新的单纯形表为Cj21000Cb基bX1X2X3X4X5155150X30012422X47100112423130X501024211CjZj00042

5、1,2 0，说明已找到问题最优解X1在约束条件中添加松弛变X21x2 x2 x20,x20 x3x3, z' z5X40 , X50。最大值X5量或剩余变量，且令max z'3x1 x2 x2 2x3 0x4 0x5ini2x1 3x2 3x2 4x3 x4 12II II4x1 x2 x2 2x3 x5 8 st.3x1 x2 x2 3x36iniX1,X2, X2, X3,X4, X50其约束系数矩阵为2 33410A 4112013 11300在A中人为地添1加两列单位向量P7,F82334100 04112011 03113000 1令 max z'3x11X2

6、IIX212x3 0x4 0x5Mx6 Mx7得初始单纯形表Cj311200MMCb基bX11X2nX21X3X4X5X6X70X41223341000M x68411-20-110M x76311-30001CjZj37M1 125M0M 00(b)在约束条件中添加松弛变量或剩余变量，且令IHIHX3X3X3X30,X30 z' zmax z'3x1 5x2 x3 x3 0x4 0x5IIIx12x2 x3x<5x46III2xiX23x33x3X516st.，”Xi X2 5X3 5X310IIIXi, X2, X3,X3, X4, X50其约束系数矩阵为121110

7、A213301115500在A中人为地】添:加两列单位向量P7,F81211101 02133010 01155000 1令maxz'3为5x2X3x30 X40X5 Mx6 Mx7得初始单纯形表Cj3-51-100-MMCb基bX1X2X3X3X4X5X6X7MX66121-1-10100X516213-30 100MX710115-50 001CjZj32M 53M1+6M-1-6M-M000解1 :大M法在上述线性规划问题中分别减去剩余变量X4,X6,X8,再加上人工变量 X5,X7,X9,得max z2x1 x2 2x3 0x4 Mx5 0x6 Mx7 0x8 Mx9XiX2X

8、3X4X56s,t,2x-iX3X6X722x2X3X8X90Xi,X2,X3,X4,X5,X6,X7,X8,X9其中M是一个任意大的正数。据此可列出单纯形表Cj2120M0M0MiCb基 bXiX2X3X4X5X6X7X8X91 1 1 1 1 0 0 0 02 0 1 0 0 1 1 0 00 2 1 0 0 0 0 1 160CjZj2 M 3M 12 MM0M0M0103/211001/21/22010011 00011/200001/ 21/ 242CjZjc-c5M 3_门-cM 1 1 3M2M0-M0M02 2 2 2 2 2400113/23/21/21/ 22 0 1 0

9、0 1 1 0 01 1 0 0 0 1/ 2 1/ 2 1/2 1/ 23/4CjZj3M 3 5M 3 M 1 1 3M4M 500IVI02 2 2 21001/ 41/ 43/83/81/81/ 80011/ 21/21/41/ 41/ 41/ 40101/ 41/41/81/83/83/8CjZj0005/4 M 53/8- M - M4888由单纯形表计算结果可以看出，4 0且ai4 0(i 1,2,3)，所以该线性规划问题有无界解解2：两阶段法。现在上述线性规划问题的约束条件中分别减去剩余变量x4, x6, x8再加上人工变量X5, x, X9,得第一阶段的数学模型据此可列出单纯

10、形表50 0 0 0 1 0 1 0 1iCb 基 bXiX2X3X4X5X6X7X8X91 1 1 1 1 0 0 0 02 0 1 0 0 1 1 0 00 2 1 0 0 0 0 1 160CjZj131101010103/211001/21/22010011 00011/200001/ 21/ 242CjZj1 3105/21010-2 2400113/23/21/21/ 22 0 1 0 0 1 1 0 01 1 0 0 0 1/ 2 1/ 2 1/2 1/ 23/4CjZj0 0 0 0 1 0 1 0 11001/ 41/ 43/83/81/81/ 80011/ 21/21/41

11、/ 41/ 41/ 40101/ 41/41/81/83/83/8CjZj0 0 0 0 1 0 1 0 1第一阶段求得的最优解X*(3,7,7,O,O,O,O,O,O)T ,目标函数的最优值4 4 2*O。因人工变量X5 x7X9O，所以X* (3,7,7,O,O,O,O,O,O) T是原线性规4 4 2划问题的基可行解。于是可以进展第二阶段运算。 将第一阶段的 最终表中的人工变量取消， 并填入原问题的目标函数的系数， 进 展第二阶段的运算，见下表。CjZj212000 0iCb基bX1X2X3X4X6X81001/43/81/80011/21/ 41/40101/41/83/8CjZj00

12、05/43/89/8由表中计算结果可以看出，4 O且ai4 O(i 1,2,3)，所以原线性规划问题有无界解。(b)解1 :大M法在上述线性规划问题中分别减去剩余变量x4,x6,x8,再加上人工变量 X5,X7,X9,得min z2x1 3x2 x3 0x4 0x5 Mx6 Mx7x1 4x2 2x3 X4 x68s,t,3% 2x2 x5 x76其中M是一个任意大的正数。据此可列出单纯形表Cj2120M0M0MCb基bXiX2X3X4X5X6X7i1421010232001013CjZj2 4M3 6M1 2MMM001/411/21/401/4085/2011/211/214/555 一一

13、 13 1M3M 3CjZj-M0MM04 224224013/53/101 /103/101/10102/51/52/51/52/5CjZj0001/21/2M 1/2M 1 /2由单纯形表计算结果可以看出，最优解，目标函数的最优解值X存在非基变量检验数 3 0，故该线性规划问题有无穷多最优解。解2:两阶段法。现在上述线性规划问题的约束条件中分别减去剩余变量X4 , X5,再加上人工变量X6,X7,得第一阶段的数学模型 minX6 X7x1 4x2 2x3X4X683% 2x2 x5 x76s,t,Xi,X2,X3,X4,X5,X6,X7,X8,X90据此可列出单纯形表Cj0 0 0 0 0

14、 1 1iCb基 bX1X2X3X4X5X6X71342201001100123CjZj46211001/411 /21/401/4085/2011/211/214/5CjZj5/2011/213/20013/53/101/103/101 /10102/51/52/51/52/5CjZj0000011第一阶段求得的最优解，目标函数的最优值* 0。因人工变量X6 X7 0，所以是原线性规划问题的基可行解。于是 可以进展第二阶段运算。将第一阶段的最终表中的人工变量取 消，并填入原问题的目标函数的系数，进展第二阶段的运算，见 下表。CjZj23100iCb基bX1X2X3X4X5013/53/101

15、/10102/51/52/5CjZj0001/21/2由单纯形表计算结果可以看出， 最优解，目标函数的最优解值由 于存在非基变量检验数 3 0，故该线性规划问题有无穷多最优解。1.8表 1-23X1X2X3X4X5x4624-210X5113201CjZj31200表 1-24X1X2X3X4X5X13121120X510511/21CjZj075320354000X1X2X3X4X5X65X2&'32/31013000x5 143430523100X629/353042301CjZj13045300XiX2X3X4X5X65X28,32/31013004X3141541501

16、2/151500X689154115002/154 51CjZj11/150017154 505X250/4i0i0i54i84ii04i4X362/4i00i64i54i44i3Xi89/4ii0024ii24ii5'4iCjzj00045 4i24 4iii4i最后一个表为所求。习题二P76写出对偶问题对偶问题为:min z 2x-i 2x2 4x3x1 3x2 4x322xi X2 3X3 y43st.x1 4x2 3x35Xi ,X20, X3无约束max w 2yi 3y2 5y3yi 2y2 y323yi y2 4y32s.t.4y1 3y2 3y34yi 0, y20,

17、y3无约束(b)maxz 5xi6X23X3Xi2X22x35st.Xi5x2X334xi7x23x38Xi无约束,X20,X30min w 5yi3y28y3yiy24y35对偶问题为：+2yist.2yi5y27y36y23y33yi无约束,y20, y3 0(a) 错误。原问题存在可行解，对偶问题可能存在可行解，也可 能无可行解。(b) 错误。线性规划的对偶问题无可行解，那么原问题可能无可 行解，也可能为无界解。(c) 错误。(d) 正确。对偶单纯形法解：先将问题改写为求目标函数极大化，并化为标准形式max z' 4x112x218x3 0x4 0x5x13x3 x43st.2x

18、2 2x3x55Xi 0 i 1,5列单纯形表，用对偶单纯形法求解，步骤如下Cj4121800CB基bX1X2X3X4X50X43103100X5502201CjZj41218000X43103105112X2011022CjZj4060618X31101103331101112X22332CjZj20026最优解为，目标值z 39(b)解：先将问题改写为求目标函数极大化，并化为标准形式maxz'5x1 2x2 4X3 0X40x53x1X22X3 X44st.6x13x25X3X510xi0i 1,5列单纯形表，用对偶单纯形法求解Cj52400CB基bX1X2X3X4X50X4431

19、2100X51063501CjZj524000X421011133310512X2210333Cj22Zj100334X32301312X2031052CjZj10020最优解为x 0,0,2 T ,目标值z 8 将该问题化为标准形式：max z2x1x2x30x40x5x1x2x3x46St.X1 2X2 X5 4xi0i 1, 5用单纯形表求解Cj21100CB基bX1X2X3X4X50X46111100X5412001CjZj211006CB基bX1X2X3X4X52X6111100X51003111CjZj03-120由于j 0，所以已找到最优解X* 6,0,0,0,10，目标函数值z

20、*12 令目标函数max z (2 J 咅(-1+ 2) x2(1+ 3 X3(1)令23 0 ,将1反映到最终单纯形表中Cj211100Cb基 bX1X2X3X4X521X461 1 1 10x51003111CjZj0-3- 1 -1- 1 2- 1 0表中解为最优的条件：-3-1 0，-1- 1 0，2- 1 0，从而1(2)令13 0，将2反映到最终单纯形表中Cj212100CB基bX1X2X3X4X52X16111100X51003111CjZj02 - 3-120表中解为最优的条件：2-3 0，从而2 3Cj211300Cb基bX1X2X3X4X52X1611 1100x51003

21、111CjZj0-33-1203 -1表中解为最优的条件:0，从而3(b) 令线性规划问题为max z 2x1 x2 x3x x2 x364兀 2x2450 i 1,3st.(1)先分析的变化b B1 b 1 011 1 0使问题最优基不变的条件是6100，从而16同理有，从而210(C) 由于 x (6,0,0,0,10)代入 X12x36 2,所以将约束条件减去Cj2-11000CB基bX1X2X3X4X5X62X161111000X5100311100X6-210-2001cjZj0-3-1-200剩余变量后的方程x1 2x3 x62直接反映到最终单纯形表中对表中系数矩阵进展初等变换，得

22、Cj2-11000Cb 基bXiX2X3X4X5X62x161111000x5 100311100X6-80-1-3-101CjZj0-3-1-200Cj2-11000Cb基bX1X2X3X4X5X62X1%1%0%0%0X52%0%0%1%0X6830%1%013CjZj851030303因此增加约束条件后，新的最优解为,最优值为282.12线性规划问题单纯形法求解Cb基bXiX2X3X4X50X445635100X53034501CjZj314000X415310114X3634101555cjZj31100455535111Xi103334X330111255cjZj1302055最优解为Xi，X2 氐 5,0,3，目标值z 27。 设产品A的利润为3，线性规划问题变为max z 3x1 x2 4x36x1 3x2 5x345st. 3x1 4x2 5x330X1 , X2 , X30单纯形法求解基bX1X2X3X4X5X44563510X53034501Cjzj31400X4