《管理运筹学》(第二版)课后习题参考答案
第 1 章 线性规划(复习思考题)
1.什么是线性规划?线性规划的三要素是什么?
答:线性规划( Linear Programming,LP)是运筹学中最成熟的一个分支,并且是
应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划,是一种重要的优化
工具,能够解决有限资源的最佳分配问题。
建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量是决策问题待定的量值,取值一般为非负;约束条件是指决策变量取值时受到的各种资源条
件的限制,保障决策方案的可行性;目标函数是决策者希望实现的目标,为决策变量的
线性函数表达式,有的目标要实现极大值,有的则要求极小值。
2.求解线性规划问题时可能出现几种结果,哪种结果说明建模时有错误?
答:(1)唯一最优解:只有一个最优点;
(2)多重最优解:无穷多个最优解;
(3)无界解:可行域无界,目标值无限增大;
(4)没有可行解:线性规划问题的可行域是空集。
当无界解和没有可行解时,可能是建模时有错。
3.什么是线性规划的标准型?松弛变量和剩余变量的管理含义是什么? 答:线性规划的标准型是:目标函数极大化,约束条件为等式,右端常数项
bi
决策变量满足非负性。
如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。
4.试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。答:可行解:满足约束条件 AX
b,X 0 的解,称为可行解。
基可行解:满足非负性约束的基解,称为基可行解。 可行基:对应于基可行解的基,称为可行基。
最优解:使目标函数最优的可行解,称为最优解。
最优基:最优解对应的基矩阵,称为最优基。
它们的相互关系如右图所示:
0 ,
5.用表格单纯形法求解如下线性规划。
max Z
4x1 x2 x3 x3 0
2x3 2 8
8x1 3x2
.
6x1 x2 x1 , x2 , x3 解:标准化
max Z 4x1
8x1
3x2
x2 x3
2x3 x4
2 x5 0
.
6x1 x2 x3
x1 , x2 , x3 , x4 , x5
8
列出单纯形表
c j
C B X B x4
4 x1
1 x2
2
0
0
x5
i
b 2 8
x3 x4
0 0
[8] 6 4 1 6 0 8
3 1 1
1 1 2 [1/8] 1/4 3/2 1 0 0
0, x3
1 0 0 1/8 -3/4 -1/2 1 - 1 - 2 0 1 0 0 1 0 0 1 0
2/8 8/6
j
4 0
x1
1/4 13/2
3/8 - 5/4 - 1/2 3
(1/4)/(1/8) (13/2)/(1/4)
j
2 0
x3
2 6
-2 -12
-2 -5
j
故最优解为 X *
(0,0,2,0,6)T ,即 x1 0, x2 2 ,此时最优值为 Z ( X *) 4 .
a1 , a2 ,c1 ,c2 , d 为何值及变 6.表 1— 15 中给出了求极大化问题的单纯形表,问表中
量属于哪一类型时有:( 1)表中解为唯一最优解;(2)表中解为无穷多最优解之一;(3) 下一步迭代将以 x1 代替基变量 x5 ;( 4)该线性规划问题具有无界解; (5)该线性规划问
题无可行解。
表 1—15 某极大化问题的单纯形表
cj
C B
X B x3 x4 x5 j
c1
c2
0
0
x4
0
i
b d 2 3
x1 x2 a1 x3 x5
0 0 0
4 - 1 a2 c1 0 ;
1 0 0 0
0 1 0 0
0 0 1 0
-5 -3
c2
解:(1) d 0, c1 0, c2 (2) d 0, c1 (3) c1
0, c2 0( c1 , c2中至少有一个为零) ;
0, a2 0, d
3 ; a2
4
(4) c2 0, a1 0 ;
(5) x1 为人工变量,且 c1 为包含 M的大于零的数,
d 3 ;或者 x2 为人工变量,
4
a2
且 c2 为包含 M的大于零的数, a1 0, d 0 .
7.用大 M法求解如下线性规划。
max Z 5x1 3x2 6x3
x1 2x2 x3 18 x1 x2 x3 10 x1, x2 , x3 0
.
2x1 x2 3x3 16
解:加入人工变量,进行人造基后的数学模型如下:
max Z 5x1 3x2 6x3 0x4 0x5 Mx 6
.
x1 2x 2 x3 x4 2x1 x2 3x3 x5
18 16 10 ,6)
x1 x2 x3 x6 xi 0 (i 1,2,
列出单纯形表
管理运筹学课后习题参考答案.doc
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)