运筹学习题答案(第一章)

page 14 5 May 2014
School of Management
运筹学教程
第一章习题解答
l.6 考虑下述线性规划问题：
max Z c1 x1 c2 x2 a11 x1 a12 x2 b1 st .a21 x1 a22 x2 b2 x1 , x2 0
(4)
该问题有无界解
page 4 5 May 2014
School of Management
运筹学教程
第一章习题解答
1.2 将下述线性规划问题化成标准形式。
min Z 3x1 4 x2 2 x3 5 x4 4 x1 x2 2 x3 x4 2 x x x 2 x 14 2 3 4 st 1 . 2 x1 3x2 x3 x4 2 x1 , x2 , x3 0, x4无约束
max Z 3x1 6 x2 1x1 2 x2 12 st . 2 x1 4 x2 14 x ,x 0 1 2
最优值（上界）为：21
page 16 5 May 2014
School of Management
运筹学教程
第一章习题解答
解：下界对应的模型如下（ c,b取小，a取大）
x1 0 0 0
x2 3 0 0
基可行解 x3 x4 x5 0 0 3.5 1.5 0 0 3 8 5
x6 0 0 0
Z 3 3 0
0.75
page 9 5 May 2014
0
0
Байду номын сангаас
0
2
2.25
2.25
School of Management
运筹学教程
第一章习题解答
(2) min Z 5 x1 2 x2 3x3 2 x4 x1 2 x2 3x3 4 x4 7 st 2 x1 2 x2 x3 2 x4 3 x 0, ( j 1, 4) j
page 21 5 May 2014
School of Management
运筹学教程
第一章习题解答
1.8 已知某线性规划问题的初始单纯形表和用单 纯形法迭代后得到下面表格，试求括弧中未知数a∼l值。
(3) max Z x1 x2 6 x1 10x2 120 st. 5 x1 10 5 x 8 2
max Z 5 x1 6 x2 2 x1 x2 2 st. 2 x1 3x2 2 x ,x 0 1 2
唯一最优解， x1 10, x2 6, Z 16
运筹学教程
第一章习题解答
1.3 对下述线性规划问题找出所有基解，指出哪 些是基可行解，并确定最优解。
max Z 3x1 x2 2 x3 12x1 3x2 6 x3 3x4 9 8 x x 4 x 2 x 10 1 2 3 5 st 3x1 x6 0 （ , j 1, ,6） x j 0
max Z 2 x1 2 x2 3x31 3x32 x1 x2 x31 x32 4 st 2 x1 x2 x31 x32 x4 6 x1 , x2 , x31 , x32 , x4 0
page 7 5 May 2014
School of Management
运筹学教程（第二版） 习题解答
运筹学教程
第一章习题解答
1.1 用图解法求解下列线性规划问题。并指出问 题具有惟一最优解、无穷多最优解、无界解还是无可 行解。
min Z 2 x1 3x2 4 x1 6 x2 6 st .2 x1 2 x2 4 x ,x 0 1 2
运筹学教程
第一章习题解答
(1) max Z 3x1 x2 2 x3 12x1 3x2 6 x3 3x4 9 8 x x 4 x 2 x 10 1 2 3 5 st 3x1 x6 0 （ , j 1, ,6） x j 0
第一章习题解答
min Z 3x1 4 x2 2 x3 5 x4 4 x1 x2 2 x3 x4 2 x x x 2 x 14 (1) 4 st 1 2 3 . 2 x1 3x2 x3 x4 2 x1 , x2 , x3 0, x4无约束 max Z 3x1 4 x2 2 x3 5 x41 5 x42 4 x1 x2 2 x3 x41 x42 2 x x x 2 x 2 x x 14 2 3 41 42 5 st 1 2 x1 3x2 x3 x41 x42 x6 2 x1 , x2 , x3 , x41 , x42 , x6 0
max Z x1 4 x2 3 x1 5 x2 8 st .4 x1 6 x2 10 x ,x 0 1 2
最优值（下界）为：6.4
page 17 5 May 2014
School of Management
运筹学教程
第一章习题解答
l.7 分别用单纯形法中的大M法和两阶段法求解 下列线性规划问题，并指出属哪—类解。
无穷多最优解， x1 1, x2
max Z 3x1 2 x2 2 x1 x2 2 (2) st .3x1 4 x2 12 x , x 0 1 2 该问题无解
page 3 5 May 2014
School of Management
运筹学教程
第一章习题解答
min Z 2 x1 2 x2 3 x3 x1 x2 x3 4 st 2 x1 x2 x3 6 x 0, x 0, x 无约束 2 3 1
(1)
(2)
page 5 5 May 2014
School of Management
运筹学教程
(1) max Z 10x1 5 x2 3x1 4 x2 9 st.5 x1 2 x2 8 x ,x 0 1 2
page 11 5 May 2014
School of Management
运筹学教程
第一章习题解答
(2) max Z 2 x1 x2 3 x1 5 x2 15 st .6 x1 2 x2 24 x ,x 0 1 2
运筹学教程
第一章习题解答
min Z 2 x1 3x2 x3 x1 4 x2 2 x3 8 (2) st.3x1 2 x2 6 x , x 0 1 2 该题是无穷多最优解。 9 4 最优解之一：x1 , x2 , x3 0, Z 6 5 5
x1
x2
基可行解 x3
x4
Z
0 0 2/5
page 10 5 May 2014
0.5 0 0
2 1 11/5
0 1 0
5 5 43/5
School of Management
运筹学教程
第一章习题解答
1.4 分别用图解法和单纯形法求解下述线性规划 问题，并对照指出单纯形表中的各基可行解对应图解 法中可行域的哪一顶点。
c
x1
j
1
1 0
0 0
-2/14 10/35 -5/14d+2/14c 3/14d-10/14c
School of Management
page 13 5 May 2014
运筹学教程
第一章习题解答
当c/d在3/10到5/2之间时最优解为图中的 A点；当 c/d大于5/2且c大于等于0时最优解为图中的B点；当c/d 小于 3/10 且 d 大于 0 时最优解为图中的 C 点；当 c/d 大于 5/2且c小于等于0时或当c/d小于3/10且d小于0时最优解 为图中的原点。
(1)
(2)
max Z 3x1 2 x2 2 x1 x2 2 st.3x1 4 x2 12 x , x 0 1 2 max Z 5 x1 6 x2 2 x1 x2 2 st. 2 x1 3x2 2 x ,x 0 1 2
page 19 5 May 2014
School of Management
运筹学教程
第一章习题解答
max Z 4 x1 x2 3 x1 x2 3 4 x 3 x x 6 (3) 1 2 3 st x1 2 x2 x4 4 , j 1, ,4） x j 0（ 该题是唯一最优解： 2 9 17 x1 , x2 , x3 1, x4 0, Z 5 5 5
max Z 3 x1 x2 2 x3 x1 x2 x3 6 2 x x 2 (1) 1 3 st 2 x2 x3 0 , j 1, ,3） x j 0（ 该题是无界解。
page 18 5 May 2014
School of Management
page 6 5 May 2014
School of Management
运筹学教程
第一章习题解答
(2) min Z 2 x1 2 x2 3x3 x1 x2 x3 4 st 2 x1 x2 x3 6 x 0, x 0, x 无约束 2 3 1
(1)
(2)
min Z 5 x1 2 x2 3x3 2 x4 x1 2 x2 3x3 4 x4 7 st 2 x1 2 x2 x3 2 x4 3 x 0, ( j 1, 4) j
School of Management
page 8 5 May 2014
page 12 5 May 2014
School of Management
运筹学教程
第一章习题解答
l.5 上题(1)中，若目标函数变为max Z = cx1 + dx2， 讨论c,d的值如何变化，使该问题可行域的每个顶点依 次使目标函数达到最优。 解：得到最终单纯形表如下： Cj→ CB d 基 x2 b 3/2 c x1 0 d x2 1 0 x3 5/14 0 x4 -3/4
School of Management
(3)
max Z x1 x2 6 x1 10x2 120 st . 5 x1 10 5 x 8 2
(4)
page 2 5 May 2014
运筹学教程
第一章习题解答
(1) min Z 2 x1 3x2 4 x1 6 x2 6 st .2 x1 2 x2 4 x ,x 0 1 2 1 , Z 3是一个最优解 3
page 20 5 May 2014
School of Management
运筹学教程
第一章习题解答
max Z 10x1 15x2 12x3 5 x1 3 x2 x3 9 5 x 6 x 15x 15 ( 4) 1 2 3 st 2 x1 x2 x3 5 , j 1, ,3） x j 0（ 该题无可行解。
式中，1≤c1≤3, 4≤c2≤6, -1≤a11≤3, 2≤a12≤5, 8≤b1≤12, 2≤a21≤5, 4≤a22≤6, 10≤b2≤14,试确定 目标函数最优值的下界和上界。
page 15 5 May 2014
School of Management
运筹学教程
第一章习题解答
解：上界对应的模型如下（c,b取大，a取小）