第一部分线性规划问题的求解
――重要算法：图解法、单纯形迭代、大M法单纯形迭代、对偶问题、表上作业法（找初始可行解： 西北角法， 最小元素法；最优性检验：
闭回路法，位势法；）、目标规划：图解法、整数规划：分支定界法（次重点），匈牙利法（重 点）、 第二部分动态规划问题的求解
――重要算法：图上标号法 第三部分 网络分析问题的求解 ――重要算法：破圈法、
TP标号法、寻求网络最大流的标号法
第一部分线性规划问题的求解
一、两个变量的线性规划问题的图解法：
㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。 定义：达到目标的可行解为最优解。 ㈡图解法：
图解法采用直角坐标求解： X1——横轴；X2——竖轴。1、将约束条件（取等号）用直线绘出；
2、 确定可行解域；
3、 绘出目标函数的图形（等值线），确定它向最优解的移动方向；
注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。
4、 确定最优解及目标函数值。
㈢参考例题：（只要求下面这些有唯一最优解的类型） 例1:某厂生产甲、乙两种产品，这两种产品均需在
A、B、C三种不同的设备上加工，每种产品在不同设备上加工
所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下 表所示：
消 \\ 设 产'品? 口仃 A B C 利润 （万兀） 、、\\ 备 ■■耗\\ 甲 3 9 5 5 450 9 3 70 30 乙 有效总工时 540 720 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大? （此题也可用“单纯形法”或化“对偶问题”用大M法求解） 解：设Xi、X2为生产甲、乙产品的数量。
max z = 70x 1+30x2
3x1 9x2 540 5x1 5x2 450 9x1 3x2 720
⑵ ⑶ ⑷
⑸、
X1, x2 0
可行解域为oabcdO,最优解为b点。 由方程组
5xi 5x2 9xi 3x2 720 Xi
二 X*=
450
解出 Xi=75, X2=15
X2
= (75, i5) T
--max z =Z = 70 X5+30 15=5700
例2: 用图解法求解
max z = 6x i+4x2
s.t.
2x1 X2 10
X2 X2
Xi, X2
可行解域为 oabcdO, 最优解为b点。
由方程组
X2 10
Xi X2
Xi
X*=
=(2, 6)
X2
/? max z = 6 1+4X6=36
例3:用图解法求解 min z = — 3xi+x2
s.t.
X
i
4
X2
3 2xi 5X2
i2 Xi 2X2
8
Xi, x2 0
解：
可行解域为bcdefb，最优解为b点。
由方程组
c
xi 4
厂
2xi 5x2 i2 Xi
X2
=(4,
⑴
⑸、⑹解出 xi=2, X2=6
⑵
⑶ ⑷ ⑸ ⑹、⑺
解出 X4 i=4 , X2=—
5
4 5
1 5
??? min z = — 3X4+ = — 11 -
二、标准型线性规划问题的单纯形解法： ㈠一般思路：
1、 用简单易行的方法获得初始基本可行解；
2、 对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入 3、 根据0 L规则确定改进解的方向；
4、 根据可能改进的方向进行迭代得到新的解；
5、 根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入
况）：
设已知
3;
3,直至最优解。 ㈡具体做法（可化归标准型的情
max z = C1X1+ C2X2+…+ CnXn
s.t.
对第i个方程加入松弛变量 Xn+i, i =1 , 2,…，m,得到 列表计算，格式、算法如下：
CB cn+1 c n+2 XB xn+1 xn+2 b b1 b2 c1 x1 a11 a21 c2 x2 a12 a22 - - - - cn+m xn+m 0 L a1 n+m a2 n+m cn+m xn+m bn am1 z1 am2 z2 - - am n+m zn+m d 1
d 2 m c
d n+m 注①： zj =cn+1 a1j+ cn+2 a2j + …+ cn+m amj=
n i aij , （j=1 , 2,…，n+m）
i 1
d j =cj — zj ,当c j w 0时，当前解最优。
注②：由max｛厂｝确定所对应的行的变量为“入基变量”；
由0 =
L
min —aik 0确定所对应的行的变量为“出基变量”，行、列交叉处为主兀素，迭代时要求将主兀
be
一、 一^ 、一
i
a
、一
ik
素变为1，此列其余元素变为 0。
例1:用单纯形法求解（本题即是本资料P2 “图解法”例1的单纯形解法；也可化“对偶问题”求解）
max z =70x1+30x2
s.t.
解：加入松弛变量 X3, X4, X5,得到等效的标准模型：
max z =70x 1+30x2+0 X3+0 X4+0 X5
s.t.
列表计算如下: 70 b 540 450 720 x1 3 5 30 x2 9 5 3 0 30 0 x3 1 0 0 0 0 0 x4 0 1 0 0 0 0 x5 0 0 1 CB 0 0 0 XB x3 x4 x5 0 540/3 L =180 450/5 =90 720/9 =80 (9) 0 0 70 f 0
0 0 70
x3 x4 x1
300 50 80
0 0 1 70
8 1 0 0 0 0 1 0 0 0 0 1 0 0 0
-12/5
-1/3 -5/9 1/9
300/8 =37.5 50/10/3 =15 80/1/3
(10/3 )
1/3 70/3 20/3 f 0 1 0 30 =240
70/9
0
0 30 70
-70/9
x3 x2 x1
180 15 75 0 0 1 70 1
3/10 -1/10 2 -1/6
1/6 20/3
5700
二 X*= (75, 15, 180, 0, 0) T
/? max z =70 X 75+30 X 15=5700
0
0
0
-2
-20/3
《运筹学》复习参考资料
