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