下载文档原格式
运筹学基础及应用习题解答z 3。
(b)用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。
(a)约束方程组的系数矩阵12 3 6 3 0A 8 1 4 0 23 0 0 0 0基基解是否基可行解目标函数值X1 X2 X3 X4 X5 X6P1 P2 P3163 7-60 0 0否P1 P2 P4 0 10 0 7 0 0 是10P1 P2 P50 3 0 0 72是 3习题一P46x i1-的所有X i,X2，此时目标函数值o(b)约束方程组的系数矩阵A 12 3 4A2 2 12⑻(1)图解法基 基解 是否基可行解 目标函数值X 1X 2X 3X 4P 1P 24 11否"2P 1P 3 2 0 110 是435 ~5~5P 1P 4111否—36P 2P 312是52P 2P 41否22P 3P 40 0 1 1是5最优解xT2 11 5吋omax z 10x 1 5x 2 0x 3 0x 4 3x i 4X 2 X 3st. 5x 1 2x 2 x 48 9 8 12。
min—,— — 5 3 5C j 105 0 0 C B基b X 1X 2X 3X 421143 0 X 3— 1—"5"5582110X 11C j 105 0 0 C B 基bX 1 X 2 X 3 X 4 0 X 3 9 341 0 0X 48[5] 20 1 C j Z j105令 X iX 20,0,9,8，由此列出初始单纯形表最优解即为3x1 4x2 9的解x5x 1 2x 2 81,-，最大值z 竺 2 2(2)单纯形法首先在各约束条件上添加松弛变量,将问题转化为标准形式则P 3，P 4组成一个基。
得基可行解xC j Z j0 1221 8320，min14 22新的单纯形表为C j 105 0 0 C B基b X 1X 2X 3X 435 3 5X 2— 01— —2141410X 11121—7525c jZ j14 143*35x i 1, x 2 - , X 3 0, X 4 0。
运筹学基础及应用 习题解答习题一 P46 1.1 (a)该问题有无穷多最优解，即满足210664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。
(b)用图解法找不到满足所有约束条件的公共围，所以该问题无可行解。
1.2(a) 约束方程组的系数矩阵⎪⎪⎪⎭⎫ ⎝⎛--=1000030204180036312A4最优解()T x 0,0,7,0,10,0=。
(b) 约束方程组的系数矩阵⎪⎪⎭⎫⎝⎛=21224321A最优解Tx ⎪⎭⎫⎝⎛=0,511,0,52。
1.3(a)(1) 图解法最优解即为⎩⎨⎧=+=+8259432121x x x x 的解⎪⎭⎫⎝⎛=23,1x ，最大值235=z(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式 ⎩⎨⎧=++=+++++=825943 ..00510 max 4213214321x x x x x x t s x x x x z则43,P P 组成一个基。
令021==x x得基可行解()8,9,0,0=x ，由此列出初始单纯形表 21σσ>。
5839,58min =⎪⎭⎫ ⎝⎛=θ02>σ，2328,1421min =⎪⎭⎫ ⎝⎛=θ0,21<σσ，表明已找到问题最优解0 , 0 , 231,4321====x x x x 。
最大值 235*=z (b)(1) 图解法最优解即为⎩⎨⎧=+=+524262121x x x x 的解⎪⎭⎫⎝⎛=23,27x ，最大值217=z(2) 单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式1234523124125max 2000515.. 62245z x x x x x x x s t x x x x x x =+++++=⎧⎪++=⎨⎪++=⎩21=+x x 2621+x x则3P ，4P ，5P 组成一个基。
令021==x x得基可行解()0,0,15,24,5x =，由此列出初始单纯形表21σσ>。
第一章P43-1.1（1）当取A （6/5,1/5）或B （3/2,0）时，z 取最小值3。
所以该问题有无穷多最优解，所有线段AB 上的点都是最优解。
P43-1.2(1)令''4'44x x x -=，z z -='''4'4321'55243max x x x x x z +-+-=,,,,,,232142222465''4'43216''4'43215''4'4321''4'4321≥=-+-++-=+-+-+=-+-+-x x x x x x x x x x x x x x x x x x x x x x x xP43-1.4(1) 图解法：A(0,9/4)，Z 1=45/4；B(1,3/2)，Z 2=35/2；C(8/5,0)，Z 3=16。
单纯形法：10 5 0 0C b X b b x1x2x3x4θ0 x39 3 4 1 0 30 x48 5 2 0 1 8/5δ10 5 0 00 x321/5 0 14/5 1 -3/5 3/210 x18/5 1 2/5 0 1/5 4δ0 1 0 -25 x23/2 0 1 5/14 -3/1410 x1 1 1 0 -1/7 2/7δ0 0 -5/14 -25/14依次相当于：原点；C；B。
P44-1.7(1)2 -1 2 0 0 0 -M -M -MC b X b b x1x2x3x4x5x6x7x8x9θ无界解。
两阶段法：阶段二：P45-1.10证明：CX (0)>=CX*，C*X*>=C*X (0) CX (0)-CX*+C*X*-C*X (0)>=0，即(C*-C)(X*-X (0))>=0。
P45-1.13设饲料i 使用x i （kg ），则543218.03.04.07.02.0m in x x x x x z ++++=s.t. 7001862354321≥++++x x x x x 305.022.05.054321≥++++x x x x x1008.022.05.054321≥++++x x x x x0,,,,54321≥x x x x x第二章P74-2.1(1)321532m ax y y y w ++=22321≤++y y y 243321≤++y y y 4334321=++y y y 无约束321,0,0y y y ≤≥P75-2.4(1),06353322232max 212121212121≥≥≤-≤+≤-≤++=y y y y y y y y y y y y w(2) (8/5,1/5)(3) 无穷多最优解。
运筹学基础及应用第四版胡运权主编课后练习答案一、线性规划1. 求解下列线性规划问题：max z = 3x1 + 2x2s.t.2x1 + x2 ≤ 8x1 + 2x2 ≤ 6x1, x2 ≥ 0答案：首先将约束条件化为标准形式，得到：max z = 3x1 + 2x2 + 0s1 + 0s2s.t.2x1 + x2 + s1 = 8x1 + 2x2 + s2 = 6x1, x2, s1, s2 ≥ 0通过单纯形法求解，得到最优解为：x1 = 2, x2 = 2，最优值为8。
2. 求解下列线性规划问题的对偶问题：min z = 2x1 + 3x2s.t.x1 + 2x2 ≥ 42x1 + x2 ≥ 6x1, x2 ≥ 0答案：原问题的对偶问题为：max z' = 4y1 + 6y2s.t.y1 + 2y2 ≤ 22y1 + y2 ≤ 3y1, y2 ≥ 0通过单纯形法求解，得到最优解为：y1 = 1, y2 = 1，最优值为10。
二、非线性规划1. 求解下列非线性规划问题：min f(x) = x^2 + 2x + 3s.t.x ∈ [0, 4]答案：首先求导数，得到f'(x) = 2x + 2。
令导数等于0，得到x = -1。
由于x ∈ [0, 4]，所以只需考虑x = 0和x = 4。
计算f(0) = 3，f(4) = 31。
因此，最小值为3，对应的x = 0。
2. 求解下列非线性规划问题：max f(x) = x^3 - 3x^2 + 4s.t.x ∈ [0, 3]答案：首先求导数，得到f'(x) = 3x^2 - 6x。
令导数等于0，得到x = 0或x = 2。
计算f(0) = 4，f(2) = 2，f(3) = 2。
因此，最大值为4，对应的x = 0。
三、整数规划1. 求解下列整数规划问题：max z = 3x1 + 2x2s.t.x1 + 2x2 ≤ 8x1, x2 ∈ Z答案：通过分支定界法求解，得到最优解为：x1 = 2, x2 = 3，最优值为10。
运筹学基础及应用 习题解答习题一 P46 1.1 (a)该问题有无穷多最优解，即满足210664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。
(b)用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。
1.2(a) 约束方程组的系数矩阵⎪⎪⎪⎭⎫ ⎝⎛--=1000030204180036312A4最优解()T x 0,0,7,0,10,0=。
(b) 约束方程组的系数矩阵⎪⎪⎭⎫ ⎝⎛=21224321A最优解Tx ⎪⎭⎫⎝⎛=0,511,0,52。
1.3(a)(1) 图解法最优解即为⎩⎨⎧=+=+8259432121x x x x 的解⎪⎭⎫⎝⎛=23,1x ，最大值235=z(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式⎩⎨⎧=++=+++++=825943 ..00510 max 4213214321x x x x x x t s x x x x z则43,P P 组成一个基。
令021==x x得基可行解()8,9,0,0=x ，由此列出初始单纯形表 21σσ>。
5839,58min =⎪⎭⎫ ⎝⎛=θ02>σ，2328,1421min =⎪⎭⎫⎝⎛=θ0,21<σσ，表明已找到问题最优解0 , 0 , 23 1,4321====x x x x 。
最大值 235*=z(b)(1) 图解法最优解即为⎩⎨⎧=+=+524262121x x x x 的解⎪⎭⎫⎝⎛=23,27x，最大值217=z(2) 单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式1234523124125max 2000515.. 62245z x x x x x x x s t x x x x x x =+++++=⎧⎪++=⎨⎪++=⎩21=+x x 2621+x x则3P ，4P ，5P 组成一个基。
令021==x x得基可行解()0,0,15,24,5x =，由此列出初始单纯形表21σσ>。
运筹学基础及应用 习题解答习题一 P46 1.1 (a)该问题有无穷多最优解，即满足210664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。
(b)用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。
1.2(a) 约束方程组的系数矩阵⎪⎪⎪⎭⎫ ⎝⎛--=1030204180036312A4最优解()Tx 0,0,7,0,10,0=。
(b) 约束方程组的系数矩阵⎪⎪⎭⎫ ⎝⎛=21224321A最优解Tx ⎪⎭⎫ ⎝⎛=0,511,0,52。
1.3(a)(1) 图解法最优解即为⎩⎨⎧=+=+8259432121x x x x 的解⎪⎭⎫ ⎝⎛=23,1x，最大值235=z(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式⎩⎨⎧=++=+++++=825943 ..00510 max 4213214321x x x x x x t s x x x x z则43,P P 组成一个基。
令021==x x得基可行解()8,9,0,0=x ，由此列出初始单纯形表21σσ>。
5839,58min =⎪⎭⎫⎝⎛=θ02>σ，2328,1421min =⎪⎭⎫⎝⎛=θ新的单纯形表为0,21<σσ，表明已找到问题最优解0, 0 , 23 1,4321====x x x x 。
最大值235*=z(b) (1) 图解法最优解即为⎩⎨⎧=+=+524262121x x x x 的解⎪⎭⎫⎝⎛=23,27x，最大值217=z(2) 单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式 1234523124125m ax 2000515.. 62245z x x x x x x x s t x x x x x x =+++++=⎧⎪++=⎨⎪++=⎩21=+x x 2621+x x则3P ，4P ，5P 组成一个基。
令021==x x得基可行解()0,0,15,24,5x =，由此列出初始单纯形表21σσ>。
245min ,,461θ⎛⎫=-= ⎪⎝⎭02>σ，1533min ,24,522θ⎛⎫==⎪⎝⎭ 新的单纯形表为0,21<σσ，表明已找到问题最优解11x =，27 2x =，3152x =，40x =，50x =。
最大值 *172z =1.6(a) 在约束条件中添加松弛变量或剩余变量，且令()0,0 ''2'2''2'22≥≥-=x x x x x ，zz x x -=-=' ,3'3该问题转化为⎪⎪⎩⎪⎪⎨⎧≥=-+-=---+=++-+++-+--=0,,,,,633824124332x ..0023' max 54'3''2'21'3''2'215'3''2'214'3''2'2154'3''2'21x x x x x x x x x x x x x x x x x x x t s x x x x x x z其约束系数矩阵为⎪⎪⎪⎭⎫ ⎝⎛------=003113102114014332A在A 中人为地添加两列单位向量87,P P⎪⎪⎪⎭⎫ ⎝⎛------1031130110211400014332令7654'3''2'210023' max Mx Mx x x x x x x z --++-+--=得初始单纯形表(b) 在约束条件中添加松弛变量或剩余变量，且令()''''''33333 0,0x x x x x =-≥≥，'z z =- 该问题转化为'''123345'''12334'''12335'''1233'''123345m ax '3500x 2623316.. 5510,,,,,0z 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 =--+-++⎧++--=⎪+--+=⎪⎨++-=⎪⎪≥⎩其约束系数矩阵为 12111021330111550A --⎛⎫ ⎪=-- ⎪ ⎪-⎝⎭在A 中人为地添加两列单位向量87,P P 121110102133010011551--⎛⎫ ⎪- ⎪ ⎪-⎝⎭令'''12334567m ax '3500z x x x x x x M x M x =--+-++--1.7(a)解1：大M 法在上述线性规划问题中分别减去剩余变量468,,,x x x 再加上人工变量579,,,x x x 得123456789max 22000z x x x x M x x M x x M x =-++-+-+-1234513672389123456789622,,20,,,,,,,,0x x x x x x x x x s t x x x x x x x x x x x x x ++-+=⎧⎪-+-+=⎪⎨--+=⎪⎪≥⎩其中M 是一个任意大的正数。
据此可列出单纯形表由单纯形表计算结果可以看出，40σ>且40(1,2,3)i a i <=，所以该线性规划问题有无界解 解2：两阶段法。
现在上述线性规划问题的约束条件中分别减去剩余变量468,,,x x x 再加上人工变量579,,,x x x 得第一阶段的数学模型据此可列出单纯形表第一阶段求得的最优解*T377X (,,,0,0,0,0,0,0)442=,目标函数的最优值*0ω=。
因人工变量5790x x x ===，所以*T377(,,,0,0,0,0,0,0)442X=是原线性规划问题的基可行解。
于是可以进行第二阶段运算。
将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。
由表中计算结果可以看出，40σ>且40(1,2,3)i a i <=，所以原线性规划问题有无界解。
(b)解1：大M 法在上述线性规划问题中分别减去剩余变量468,,,x x x 再加上人工变量579,,,x x x 得1234567min 2300z x x x x x M x M x =+++++-123461257123456789428326,,,,,,,,,,0x x x x x x x x x s t x x x x x x x x x ++-+=⎧⎪+-+=⎪⎨⎪⎪≥⎩其中M 是一个任意大的正数。
据此可列出单纯形表由单纯形表计算结果可以看出，最优解*T49(,,0,0,0,0,0)55X=，目标函数的最优解值*4923755z =⨯+⨯=。
X 存在非基变量检验数30σ=，故该线性规划问题有无穷多最优解。
解2：两阶段法。
现在上述线性规划问题的约束条件中分别减去剩余变量45,,x x 再加上人工变量67,,x x 得第一阶段的数学模型67m in x x ω=+ 123461257123456789428326,,,,,,,,,,0x x x x x x x x x s t x x x x x x x x x ++-+=⎧⎪+-+=⎪⎨⎪⎪≥⎩据此可列出单纯形表第一阶段求得的最优解*T 49(,,0,0,0,0,0)55X=,目标函数的最优值*0ω=。
因人工变量670x x ==，所以T49(,,0,0,0,0,0)55是原线性规划问题的基可行解。
于是可以进行第二阶段运算。
将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。
由单纯形表计算结果可以看出，最优解*T49(,,0,0,0,0,0)55X=，目标函数的最优解值*4923755z =⨯+⨯=。
由于存在非基变量检验数30σ=，故该线性规划问题有无穷多最优解。
1.8习题二 P76 2.1 写出对偶问题 (a)⎪⎪⎩⎪⎪⎨⎧≥=++≤+++≥++++=无约束3213214321321321,0,534332243 ..422 min x x x x x x y x x x x x x t s x x x z 对偶问题为：⎪⎪⎩⎪⎪⎨⎧≤≥=++≤++≤++++=无约束321321321321321,0,0433424322 ..532max y y y y y y y y y y y y t s y y y w(b)⎪⎪⎩⎪⎪⎨⎧≤≥≤++≥-+-=++++=0,0,837435522 ..365max 321321321321321x x x x x x x x x x x x t s x x x z 无约束 对偶问题为： ⎪⎪⎩⎪⎪⎨⎧≥≤≤+-≥++=+-++=0,0,332675254 ..835 min 321321321321321y y y y y y y y y y y y t s y y y w 无约束2.2(a)错误。
原问题存在可行解，对偶问题可能存在可行解，也可能无可行解。
(b)错误。
线性规划的对偶问题无可行解，则原问题可能无可行解，也可能为无界解。
(c)错误。
(d)正确。
2.6 对偶单纯形法 (a)⎪⎩⎪⎨⎧≥≥+≥+++=0,,522 33 ..18124 min 3213231321x x x x x x x t s x x x z解：先将问题改写为求目标函数极大化，并化为标准形式()⎪⎩⎪⎨⎧=≥-=+---=+--++---=5,,10522 3 3 ..0018124'max 53243154321 i x x x x x x x t s x x x x x z i列单纯形表，用对偶单纯形法求解，步骤如下最优解为Tx ⎪⎭⎫ ⎝⎛=23,1,0， 目标值39=z。
(b)⎪⎩⎪⎨⎧≥≥++≥++++=0,,1053642 3 ..425 min 321321321321x x x x x x x x x t s x x x z解：先将问题改写为求目标函数极大化，并化为标准形式()⎪⎩⎪⎨⎧=≥-=+----=+---++---=5,,10105364 2 3 ..00425'max 5321432154321 i x x x x x x x x x t s x x x x x z i列单纯形表，用对偶单纯形法求解最优解为()Tx 2,0,0=， 目标值8=z 。
