厦门大学运筹学OR 习题讲解.ppt

《运筹学》课程小结与答疑
厦门大学管理学院

是非判断题:(1) 线性规划问题的每一个基可行解对应
可行域的一个顶点,如果线性规划问题存在最优解,则最
优解一定对应可行域边界上的一个点;
(2)单纯形法求解标准型式的线性规划问题时,检验数 0 对应的非基变量xj 都可以被选作为换入变量;
(3)在单纯形法计算中,选取最大正检验数k 对应的
变量xk 作为换入变量,将使目标函数值得到最快的增长;
(3)一旦一个人工变量在迭代中变为非基变量后,该
变量及相应列的数字可以从单纯形表中删除,而不影响计
算结果;
(4) 一旦一个人工变量在迭代中变为非基变量后,该变
量及相应列的数字可以从单纯形表中删除,而不影响计算
结果;
(5)线性规划问题的任一可行解都可以用全部基可行解
的非负凸组合来表示;即:假设 X1、X2、…、Xn 是某线
性规划问题的所有基可行解,1、2、…、n是一组非负
实数且1 + 2 + …+ n = 1,则对于任何一个可行解 X
都有:X = 1X1 + 2X2 + …+ nXn ;
(6)在运输问题中,只要给出一组含(m + n –1)个非
负的变量{xij},满足:
,就可以作为运输问题的一个初始基可行解;
(7)有产地产量和销地的销量均为整数时,用表上作业
法求得的运输问题的最优解也为整数解;
(8)在目标规划问题中,正偏差变量应取正值,负偏差
变量应取负值;
(9)若将指派问题的效率矩阵的每个元素都乘上同一个
常数k(>0),将不影响最优指派方案;
(10)解决传统库存问题的三个步骤是:画存贮状态图,
建立费用函数,求经济订购批量。
问题1:如何将一般的线性规划问题化成标准型并根
据实际问题的需要列出初始单纯形表。
(1)首先将原问题化成标准型,具体就是:
把目标最小的化成目标为最大的形式;
约束条件右端的常数项均化成 0 的常数;
对于取值可正可负的变量,通过令其为两个正变量
的相减,将其所有变量均化成 0 (即非负)形式;
通过加入非负的松弛变量或非负的剩余变量把“”
或“”形式的不等式化成等式;
(2)在完成上述步骤后,根据问题的需要,适当加
入人工变量,利用大M法列出初始单纯形表。
举例如下:
解:原目标变成新目标:
Max Z= 3x1 – 4x2 + 2x3 – 5x4
将第一个约束条件两边同乘以(-1)变成:
-4x1 + x2 – 2x3 + x4 = 2
令 x4 = x4- x4, 在第二个约束条件中加入非负松弛
变量 x5 ,在第三个约束条件中加入非负剩余变量
x6 ,就可将原线性规划问题化成如下标准型:
在这个标准型中,只有变量 x5 可以作为初始的基
变量,为得到一组初始的基变量,我们必须在第一个
与第三个约束条件中分别加入人工变量 x7 、x8 可得:
由此,我们就可以列出初始单纯形表如下:
cj 
3
-4
2
-5
5
0
0
-M
-M
CB
XB
b*
x1
x2
x3
x4
x4
x5
x6
x7
x8
-M
x7
2
-4
1
-2
1
-1
0
0
1
0
0
x5
14
1
1
3
-1
1
1
0
0
0
-M
x8
2
-2
3
-1
2
-2
0
-1
0
1
检验数j
3 -6M
-4+
4M
2-3M
-5+
3M
5-3M
0
-M
0
0