2.2将下列线性规划模型化为标准形式并列出初始单纯形表。
min z =x1 ' 2x2 4x3
（°
s.t彳
5为一2x2 —4x3 = -26
人込0,x2亠0,x3无约束
解：（1 ）令Xi' =_Xi,X3 k '_x3”Z =_z ，则得到标准型为（其中
-3x^2x2 +2x^^19 -4% +3x2 +4x3 兰14
M为一个任意大的正
数 ） 3 maxz' - -2x1' 2x2 4x -4x3\4 0x5 -Mx6 -Mx7
‘3捲'+2x2 +2怡'—2x3\4 =19 s.t
4X/+3X2 +4x3'—4x3
\—x5 +疋=14
5x1' 2x2 4x3' - 4x3\7 二 26
X1 ',X2,X3‘,X3“,X4,X5,X6,X7 _0
初始单纯形表如表 2-1所示:
表2-1 -2
c 2 4 -4 0 0 -M -M
CB XB b X1' X2 X3' X3'' X4 X5 X6 X7 0
0 X4 19 3 2 2 -2 1 0 0 0 19/3
-M X6 14 [4 ] 3 4 -4 0 -1 1 0 14/4 -M X7 26 5 2 4 -4 0 0 0 1 26/5
-z -2+9M 2+5M 4+8M -4-8M 0 -M 0 0 2.3用单纯形法求解下列线性规划问题。 maxz =2片 _x2 x3
min z = 5捲 - 2x2 3x3 2x4 _L3x1 x2 x3 _ 60
1x1 2x2 3x3 4x4 _ 7 s.t 《2人
（
）
为—X2 2x3 —10
2+2x2 +x3 +2x4 兰3
（
）
s.t i
X1,X2,X3,兀—0
N +x2 -2x3 兰 20 X1,X2,X3 _0
解: （ 1 ）最优解为 X* =（15,5,0） T
,z* =25。
（2） 最优解为 C =（0,1.5,0,0） K - -3。
2.4分别用大M法和两阶段法求解下列线性规划问题。
max^2x1 3x2—5怡
min z =4为 x2
X1 1 X2 X3 =7 3xX2 =3
s.t <2为—5x2+x3 生10
（2）
4x1 3x2 -x3 = 6 Xs.t ?
1,X2,X3 -0
x1 2 x2 X4 = 4
解：（1 ）最优解为 x=（6.429,0.571,0） T
,z
X,X2,X3,X4 — 0
* * =14.571。*
T *
（2）最优解为 x =（0.4,1.8,1,0） ,z =3.4。
1
2.6已知线性规划问题
min Z = 2为 3x2 5x3 2x4 3x5
X x2 2x3 x4 3x^ _ 4 s.t ￡ 2人一x2 +3x3 十為 +x5 33
Xj KO, j =1,2,山,5
其对偶问题最优解为 y； =4/5, y； =3/5;Z* =5。试用对偶理论找出原问题最优解。
解：先写出它的对偶问题
maxw = 4y； 3y2 ”y； +2y2 兰 2 y； _y2 兰3 |2y；+3y2 兰5 s.t彳 y；竹2兰2 3y； + y2 兰3
y；, y2 -0
* *
将y1 =4/5, y2 =3/5代入约束条件可知，第 2、3、4个约束为严格不等式，因此，由互 补松弛性得x； =x3 =x； =0。又因为y；,y2，所以原问题的两个约束条件应取等式，因 此有
-■ * * > ■ *
x； 3x5 =4
<**=<*
|2x； x5 =3
T
x；=； x5 =；
故原问题最优解为 X* =（；,O,O,O,；）,Z* =5。
2.12现有线性规划问题
maxz - -5x； 5x2 ；3x3 -x； x2 3x3 _20 s.t X；,X2,X3 一0 先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？ （；）约束条件①的右端项系数由 20变为30； （2） 约束条件②的右端项系数由 90变为70； （3） 目标函数中x3的系数由；3变为8； （4） X；的系数列向量由（-；,；2）丁变为（0,5）丁 ； （5） 将原约束条件②改变为 ；0x； 5x2 ；0x3 _；00 ； （6） 增加一个约束条件 2x； 3X2 5x^50。 解：在上述LP问题的第①、②个约束条件中分别加入松弛变量 X4,X5 得 ① ② max z = -5x； 5x2 ；3x3 0x4 0% -X； X2 3X3 X4 s.t =20 E =90 ；2x； 4X2 ；0X3 X；,X2,X3,X4,X5 — 0 2 列出此问题的初始单纯形表并进行迭代运算，过程如表 2-11所示。 由表2-11中的计算结果可知， LP问题的最优解 X*=(0,20,0,0,10) 丁，z*=5*20=100。 (1) 约束条件①的右端项系数由 20变为30,则有 B」bJ0I[30L[30 l 卜 4 1 丄90 H-30 列出单纯形表，并利用对偶单纯形法求解，过程如表 2-12所示。 表 2-11 Cj -5 5 13 0 0 6i CB XB b X1 X2 X3 X4 X5 0 X4 20 -1 1 [3 ] 1 0 20/3 0 X5 90 12 4 10 0 1 9 Cj-Zj -5 5 13 0 0 13 X3 20/3 -1/3 [1/3 ] 1 1/3 0 20 0 X5 70/3 46/3 2/3 0 -10/3 1 35 Cj-Zj -2/3 2/3 0 -13/3 0 5 X2 20 -1 1 3 1 0 0 X5 10 16 0 -2 -4 1 Cj-Zj 0 0 -2 -5 0 表 2-12 Cj -5 5 13 0 0 CB XB b X1 X2 X3 X4 X5 5 X2 30 -1 1 3 1 0 0 X5 -30 16 0 [-2 ] -4 1 Cj-Zj 0 0 -2 -5 0 5 X2 -15 23 1 0 [-5 ] 3/2 13 X3 15 -8 0 1 2 -1/2 Ci-Zj -16 0 0 -1 -1 0 X4 3 -23/5 -1/5 0 1 -3/10 13 X3 9 6/5 2/5 1 0 1/10 Cj-Zj -103/5 -1/5 0 0 -13/10 由表2-12中计算结果可知，LP问题的最优解变为 X* =(0,0,9,3,0) T , z* =13疋9 =117。 (2) 约束条件②的右端常数由 90变为70，则有 B^b = 1 M 0 1 丫20\『II 20\ =1 H 1人70丿「10丿 列出单纯形表，并利用对偶单纯形法求解，结果如表 2-13所示。 3
管理运筹学课后答案
