第2章 运筹学课件图解法

向量Pj 对应的决策变量是x j
T
用矩阵表述：
max z CX ( LP4 ) s.t AX b X 0
其中
A (aij )mn ( p1, p2 pn )
0 (0,0,0)
T
max z CX s.t AX b X 0
剩余变量
ai1x1 ai 2 x2 ain xn si bi , si 0
2)
不等式变不等式
ai1 x1 ai 2 x2 ain xn bi
ai1 x1 ai 2 x2 ain xn bi ,
3)
等式变不等式
ai1 x1 ai 2 x2 ain xn bi
其中 bi 0
决策变量大于等于0
右端常数项大于0
或者 ( LP2 )
max z c j x j
j 1
n
s.t ij x j b j , i 1, 2 m j 1 x 0, j 1, 2 n j
n
（向量和矩阵符号表述） ( LP3 )
第一节
问题的提出
1.1、问题的提出
例1: 某工厂用三种原料生产三种产品，已知
的条件如下表所示，试制订总利润最大的生 产计划
单位产品所需原 料数量（公斤） 产品 Q1 产品 Q2 产品 Q3
原料可用量 （公斤/日）
原料P1
原料P2 原料P3 单位产品的利润 （千元）
2
0 3 3
3
2 2 5
0
4 5 4
4x2 12
x2
A
可行域
B
max z 2 x1 3x2 s.t x1 2 x2 8 x1 16 4 x 12 2 x , x 0 1 2
最优解（4，2）
x1
x1 16
综上，本问题可用如下模型描述： 目标函数： max z 3x1 5x2 4x3 约束条件： 2 x1 3x2 1500
2x1 4 x3 800 3x1 2x2 5x3 2000
x1 ,x2 ,x3 0
从以上例可以看出，其特征是：
1) 问题用一组决策变量 ( x1 , x2 xn ) 表示某一方案；决策变量的值就代表 一个具体的方案，一般这些变量是非 负的。
1500
800 2000
可控因素：每天生产三种产品的数量，
分别设为：x1 ,x2 ,x3
目标：每天的利润最大
3 利润函数： x1 5x2 4 x3
受制条件：每天原料的需求量不超过可用量
单位产品所需原料 数量（公斤） 原料P1 原料P2 原料P3 单位产品的利润 （千元）
产品 Q1
产品 Q2
max(min) z c1x1 c2 x2 cn xn
x1 x2 2 n xn (, )b2 m1 x1 m 2 x2 mn xn (, )bm x1 , x2 xn 0
线 性 规 划
Chapter 2 Linear Programming
Linear Programming
在人们的生产实践中，经常会遇到
如何利用现有资源来安排生产，以取得 最大经济效益的问题。此类问题构成了 运筹学的一个重要分支—数学规划，而 线性规划(Linear Programming 简记LP) 则是数学规划的一个重要分支。
j
j
min z CX max f z CX
III.
约束转换（实例）
1)
不等式变等式
i1x1 i 2 x2 in xn bi
松弛变量
i1x1 i 2 x2 in xn si bi si 0
或者：
ai1 x1 ai 2 x2 ain xn bi
1.3、线性规各种形式都统一变为如下的
标准形式：
( LP ) 1
目标函数为最大
约束为 等式
max z c1 x1 c2 x2 cn xn s.t x1 x2 1n xn b1 m1 x1 m 2 x2 mn xn bm x1 , x2 xn 0
2. 存在一定的约束条件，这些约束都可 以用一组线性等式或线性不等式表示。
3. 都有一个要达到的目标，它可以用决 策变量的线性函数来表示。按问题的 不同要求，目标函数实现最大化或最
小化。
满足以上三个条件的数 学模型称为线性规划的数 学模型，其一般形式为:
目标函数
s.t x1 x2 1n xn (, )b1
A
-----称为系数矩阵 -----称为资源向量 -----称为价值向量
b
C
X
-----称为决策变量向量
将一般形式转换为标准形式
I.
变量转换(若出现自由变量 令自由变量
j
x
j
)
xj x x ,
其中
x , x 0.
II. 目标转换 求最小可以等价的转换为求最大
2、无界解
对下述问题用图解法求解结果见下图：
max z x1 x2 s.t x1 x2 4 x1 x2 2 x , x 0 1 2
x2
2x1 x2 4
max z x1 x2 s.t x1 x2 4 x1 x2 2 x , x 0 1 2
注意：
在不引起混淆的情况下，松弛变量、
剩余变量与决策变量的符号不加区
分,均用 xi 表示。 在将求最小问题化为标准型时，一
定注意所求的最优值互为相反数。
松弛变量和剩余变量的解释
例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种 产品的生产，已知生产单位产品所需的设 备台时及A、B两种原材料的消耗、资源的 限制，如下表：
ai1 x1 ai 2 x2 ain xn bi ai1 x1 ai 2 x2 ain xn bi
例1:将下列数学模型变为标准型：
max z x1 x2 s.t x1 x2 4 (1) x1 x2 2 x , x 0 1 2
2.2、图解法
变量用直角坐标系中的点表示 约束条件用坐标系中的半空间或直线的 交表示
要点：
目标函数用一组等值线表示，沿着增加 或减少的方向移动
等值线
例1:
max z 2 x1 3x2 s.t x1 2 x2 8 x1 16 4 x 12 2 x , x2 0 1 2
自从1947年G. B. Dantzig 提出求解线
性规划的单纯形方法以来，线性规划在理论
上趋向成熟，在实用中日益广泛与深入。特 别是在计算机能处理成千上万个约束条件和 决策变量的线性规划问题之后，线性规划的 适用领域更为广泛了，已成为现代管理中经 常采用的基本方法之一。
§2.1 问题的提出 §2.2 线性规划的图解法 §2.3 图解法的灵敏度分析
min z x1 x2 s.t x1 x2 4 (2) x1 x2 2 x 0 1
解： (1)、原式的标准型为：
max z x1 x2 s.t x1 x2 s1 4 x1 x2 s2 2 x , x 0, s , s 0. 1 2 1 2
总之，可能出现的情况：
可行域是空集
可行域无界无最优解 最优解存在且唯一，则一定在顶点上达到 最优解存在且不唯一，一定存在顶点是 最优解
注：图解法简便、直观，有助于了解
线性规划问题求解的基本原理，但是当 变量的个数多于三个时，它就无能为力 了，因此我们将介绍单纯形法。为了便 于讨论，我们先规定线性规划问题的数
x1 2x2 8
结论： 可行域一定是凸集 若最优解存在，则最优解一定 在凸集的顶点达到
上例中求得 问题的解是唯一的， 但对一般线性规划问题，求解结果还 可能出现以下几种情况： 1、无穷多最优解（多重解）
若将上例中的目标函数 max z 2x1 4x2 改为则表示目标函数中以参数的等值线 与约束条件的边界平行，当值由小变大 时，将与此边界重合，线段AB上的所有 点都是最优解。
(2)、令 x2 x3 x4 ,
规划的标准型为：
则可得原
max f z x1 ( x3 x4 ) s.t x1 ( x3 x4 ) s1 4 x1 ( x3 x4 ) s2 2 x 0, x , x 0, s , s 0 1 2 1 3 4
max z CX s.t p j x j b j 1 x 0, j 1, 2 n j
n
其中：
C (c1, c2 cn ),X ( x1, x2 xn )
T
T
Pj (a1 j , a2 j amj ) ,b (b1, b2 bm )
约束条件
注解：
o
x1 , x2 xn称为决策变量。
o 上述规划中的决策变量也可以是无约束的。 o 满足所有约束条件的一组决策变量称为可行解
o 使目标函数达到最大的一组决策变量称为最优解
o 最优解所对应的目标函数值称为最优值 o 所有可行解组成的集合称为可行域
第二节
线性规划的图解法
图解法
缺点： 只能求解两个决策变 量的线性规划 优点：简单、直观、帮助我 们了解求解线性规划的原理
学模型的标准形式。
线性规划问题的标准形式
线性规划的一般形式
s.t x1 x2 1n xn (, )b1
max(min) z c1x1 c2 x2 cn xn