第一章线性规划 1．1将下述线性规划问题化成标准形式 1)min z＝－3x1＋4x2－2x3＋5 x4 －x2＋2x3－x4＝－2 4x st. x1＋x2－x3＋2 x4 ≤14 －2x1＋3x2＋x3－x4 ≥ 2 x1，x2，x3≥0，x4无约束 2)min z ＝2x1－2x2＋3x3 ＋x2＋x3＝4 －x st. －2x1＋x2－x3≤6 x1≤0 ，x2≥0，x3无约束 1．2用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。 1)min z＝2x1＋3x2 4x1＋6x2≥6 st2x1＋2x2≥4 x1，x2≥0 2)max z＝3x1＋2x2 2x1＋x2≤2 st3x1＋4x2≥12 x1，x2≥0 3)max z＝3x1＋5x2 6x1＋10x2≤120 st5≤x1≤10 3≤x2≤8 4)max z＝5x1＋6x2 2x1－x2≥2 st－2x1＋3x2≤2 x1，x2≥0 1．3找出下述LP问题所有基解，指出哪些是基可行解，并确定最优解 （1）min z＝5x1－2x2＋3x3＋2x4 x1＋2x2＋3x3＋4x4＝7 st2x1＋2x2＋x3 ＋2x4＝3 x1，x2，x3，x4≥0
1．4 分别用图解法与单纯形法求解下列LP 问题，并对照指出最优解所对应的顶点。 1) maxz ＝10x 1＋5x 2 3x 1＋4x 2≤9 st 5x 1＋2x 2≤8 x 1，x 2≥0 2) maxz ＝2x 1＋x 2 3x 1＋5x 2≤15 st 6x 1＋2x 2≤24 x 1，x 2≥0 1．5 分别用大M 法与两阶段法求解下列LP 问题。 1) minz ＝2x 1＋3x 2＋x 3 x 1＋4x 2＋2x 3≥8 st 3x 1＋2x 2 ≥6 x 1，x 2 ，x 3≥0 2) max z ＝4x 1＋5x 2＋ x 3 . 3x 1＋2x 2＋ x 3≥18 St. 2x 1＋ x 2 ≤4 x 1＋ x 2－ x 3＝5 3) maxz ＝ 5x 1＋3x 2 +6x 3 x 1＋2x 2 －x 3 ≤ 18 st 2x 1＋x 2 －3 x 3 ≤ 16 x 1＋x 2 －x 3＝10 x 1，x 2 ，x 3≥0 123123 123123123 4)max 101512539561515.25,,0z x x x x x x x x x st x x x x x x =++++≤??-++≤?? ++ ≥??≥? 1．6
运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题 a） 12 12 12 12 min z=23 466 ..424 ,0 x x x x s t x x x x + +≥ ? ? +≥ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为 最优解，即该问题有无穷多最优解，这时的最优值为 min 3 z=2303 2 ?+?= P47 1.3 用图解法和单纯形法求解线性规划问题 a） 12 12 12 12 max z=10x5x 349 ..528 ,0 x x s t x x x x + +≤ ? ? +≤ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点， 即 1 12 122 1 349 3 528 2 x x x x x x = ? += ?? ? ?? +== ?? ? ，即最优解为* 3 1, 2 T x ?? = ? ?? 这时的最优值为 max 335 z=1015 22 ?+?=
单纯形法： 原问题化成标准型为 121231241234 max z=10x 5x 349 ..528,,,0x x x s t x x x x x x x +++=?? ++=??≥? j c → 10 5 B C B X b 1x 2x 3x 4x 0 3x 9 3 4 1 0 0 4x 8 [5] 2 0 1 j j C Z - 10 5 0 0 0 3x 21/5 0 [14/5] 1 -3/5 10 1x 8/5 1 2/5 0 1/5 j j C Z - 1 0 - 2 5 2x 3/2 0 1 5/14 -3/14 10 1x 1 1 0 -1/7 2/7 j j C Z - -5/14 -25/14
运筹学习题答案 第一章（39页） 1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。 （1）max 12z x x =+ 51x +102x ≤50 1x +2x ≥1 2x ≤4 1x ，2x ≥0 （2）min z=1x +1.52x 1x +32x ≥3 1x +2x ≥2 1x ，2x ≥0 （3）max z=21x +22x 1x -2x ≥-1 -0.51x +2x ≤2 1x ，2x ≥0 （4）max z=1x +2x 1x -2x ≥0 31x -2x ≤-3 1x ，2x ≥0 解： （1）（图略）有唯一可行解，max z=14 （2）（图略）有唯一可行解，min z=9/4 （3）（图略）无界解 （4）（图略）无可行解 1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。
（1）min z=-31x +42x -23x +54x 41x -2x +23x -4x =-2 1x +2x +33x -4x ≤14 -21x +32x -3x +24x ≥2 1x ，2x ，3x ≥0，4x 无约束 （2）max k k z s p = 11 n m k ik ik i k z a x ===∑∑ 1 1(1,...,)m ik k x i n =-=-=∑ ik x ≥0 (i=1…n; k=1,…,m) （1）解：设z=-z ',4x =5x -6x , 5x ,6x ≥0 标准型： Max z '=31x -42x +23x -5(5x -6x )+07x +08x -M 9x -M 10x s. t . -41x +2x -23x +5x -6x +10x =2 1x +2x +33x -5x +6x +7x =14 -21x +32x -3x +25x -26x -8x +9x =2 1x ,2x ,3x ,5x ,6x ,7x ,8x ,9x ,10x ≥0