运筹学2

15
第二步：确定目标函数取最优值的 方向。确定取极值方向的方法：令s 取不同值，作出n条（至少两条）等 值线，即可判断出方向。 第三步：求最优解。（使目标函数 取最大或最小值的解）
16
例2
max z=x1+x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0
x2
最优解
6
可行域
令x3 = x3 =x3/ – x3// x3 无符号限制, xj 无非负约束，令 xj =xj/ – xj//
9
Max z/= – x1/ + x2 +4 x3/ –4 x3// s.t. – 3x2+4 x3/ –4 x3// +x4 =9 – x1/+ 2x2 –x5 = 6 5x2+2 x3/ –2 x3// +x6 =16 x1/, x2 , x3/ , x3// , x4 , x5 , x6 ≥ 0
x1
-1 0 -1 -1 1
x1+ x2≤5
18
线性规划的图解法 例4
max s.t. z=2x1+x2 x1+ x2 ≥3 x1 - x2≤3 x1 ≥0, x2≥0
x2
3
g
x1 0
3
19
min s.t.
z=2x1+x2 x1+ x2 ≥3 x1 - x2≤3 x1 ≥0, x2≥0
x2
3
g
x1 0
1 1 2 2 n 11 1 12 2 1n n
n
st .
b ≥0
i

a x +a x +...+ a x =b a x + a x +...+ a x =b ⋮ a x + a x +...+ a x =b x , x ,..., x ≥0
4
-8 0
6
x1
x1+ x2 =4 x1+ x2 =0
17
线性规划的图解法 例3
min s.t. z=-x1+x2 -2x1+ x2≤2 x1 - 2x2≤2 x1+ x2≤5 x1 ≥0, x2≥0
D g 2 1 1 2 A 3 4
x2
-2x1+ x2≤2
C 可行域
B 最优解 5
x1 - 2x2≤2
10
补充几个名词：
可行解：满足所有约束条件的决策变量 可行域：全体可行解组成的集合 最优解：使目标函数达到最大或最小的 可行解。 最优值：最优解的目标函数值。
11
第二节 线性规划问题的图解法
一、图解法的步骤（适应于求解两个 决策变量的线性规划问题）
12
例1
max s.t. z=x1+3x2 x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0
4
C = (c , c ,⋯, c );X=
1 2 n
（三）标准型的矩阵形式
max st . z =CX

AX =b X ≥0
a11a12 ...a1n a a ...a A = ( P1, P2 , ⋯ , Pn ) = 21 22 2 n ......... am1am 2 ...amn
,
3
（二）标准型的向量形式
max z = ∑c x
n j =1 j n j =1 j
∑
st .
p x =b
j j
x≥0
其中，C为价值向量；X 为决策变量向量；Pj为xj 的系数列向量；b为资源 向量
a1 j x1 b1 0 x b 0 a2 j 2 ; P = ;b = 2 ; 0 = ⋮ ⋮ ⋮ ⋮ xn bm anj 0
回顾（ 回顾（第二章线性规划及单纯形法 第一节 线性规划问题及数学模型 ）
总结： 总结、 线性规划的三大要素：决策变量、 约束条件、 约束条件、目标函数 二、线性规划模型及其建立的步骤
1
三、线性规划模型的标准型
标准型为：
max
z =cx +c x +...+c x
1 21 1 22 2 2n n 2 m1 1 1 m2 2 mn n 2 n
m
2
（一）标准型的简写形式
max st .
z = ∑c x
n
j =1
j
j
n ∑ j =1 j
a x =b (i =1,2, ⋯, m) x ≥0 ( j =1,2, ⋯, n)
ij j i
8
目标函数令z=-z/
-3x2 + 4x3 ≤9 – x1 + 2x2 ≥ 6
Max z / =x1 -x2+-4 x3 -3x2 + 4x3+x4=9
约束条件“≤”，加上一非负松弛变量
– x1 + 2x2-x5=6 5x2+2 x3+x6=16
约束条件“≥”，减去一非负剩余变量
5x2+2 x3≤16 x1 ≤ 0, 令x1= -x1/ ≥0,
3
20
二、线性规划求解结果
唯 唯一最优解 一
无穷多最优解 无界解 无可行解
21
三、图解法的启示
可行域为有界或无界凸多边形 若有最优解则一定在顶点上达到
22
5
（四）标准型的集合形式
max z = {CX AX = b, X ≥ 0
}
6
四、线性规划模型的标准化步骤
（一）目标函数最大化 （二）约束条件等式化 （三）决策变量非负化
7
例 将下列LP标准化
min z =-x1 +x2 -4 x3 3x2 – 4x3 ≥ –9 s.t. – x1 + 2x2 ≥6 5x2+2 x3≤16 x1 ≤ 0, x2≥0, x3 无符号限制
x2 6
4
-8 0
目标函数等值线
6
x1
x1+3x2 =6 x1+ 3x2 =0
13
步骤 第一步：确定满足约束条件 的点的集合（其中每个点都 是可行解，所有可行解组成 的集合，为可行解集）每个 约束条件所限定的点集为一 个半平面，各半平面的交集 即为可行解集。
14
各半平面的判定方法（1）将各s、t 令为等式，作出直线 （2）在两个半平面内任选一点，检 验是否满足s·t