OR-chapter1线性规划及单纯形法(到单纯形法)

解:（１）因为x3无符号要求 ，即x3取正值也可取负值，标准 型中要求变量非负，所以
x3 ，且 x 用 x 3 , x3 0 3 x 3 替换
线性规划问题的数学模型
(2) 第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4， x4≥0,化为等式； (3) 第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5， x5≥0； (4) 第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右 端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令z′=-z,得到max z′=-z，即当z达到最小值时z′达到最大值，反之亦然;
其中： C ( c1 c 2 c n )
x1 X xn
a1 j Pj a mj
b1 B bm
线性规划问题的数学模型
6. 线性规划问题的标准形式
max Z c j x j
简写为： max (min) Z
c
j 1
n
j
xj (i 1 2 m ) (j 1 2 n)
a
j 1
n
ij
题的数学模型
矩阵形式：
max (min) Z CX AX ( ) B X 0
2.目标函数：设总利润为z，则有： max z = 2 x1 + x2
3.约束条件： 5x2 ≤ 15 6x1+ 2x2 ≤ 24 x1+ x2 ≤ 5
x1， x2≥0
问：应如何安排生产计划，才 能使总利润最大？
线性规划问题的数学模型
例1.3 已知资料如下表所示， 问如何安排生产才能使利润 最大？或如何考虑利润大， 产品好销。
线性规划问题的数学模型
第一章 线性规划 及单纯形法
主要内容：
LP的数学模型
图解法 单纯形法
单纯形法的进一步讨论－人工变量法
LP模型的应用
线性规划问题的数学模型
1. 规划问题 生产和经营管理中经常提出如何合理安排，使人力、 物力等各种资源得到充分利用，获得最大的效益， 这就是规划问题。 线性规划通常解决下列两类问题：
（1）当任务或目标确定后，如何统筹兼顾，合理安排，用 最少的资源 （如资金、设备、原标材料、人工、时间等） 去完成确定的任务或目标
线性规划问题的数学模型
例1.7 将下列线性规划问题化为标准形式
min Z 2 x1 x 2 3 x 3 5 x1 x 2 x 3 7 x1 x 2 4 x 3 2 3 x1 x 2 2 x 3 5 x1 , x 2 0, x 3 为无约束（无非负限制）
解： Max z = 3x1–5x2’+5x2”–8x3 +7x4 s.t. 2x1–3x2’+3x2”+5x3+6x4+x5= 28 4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0
线性规划问题的数学模型
例1.6 将下列线性规划问题化为标准形式
min Z 2 x 1 x 2 3 x 3 5 x1 x 2 x 3 7 x1 x 2 4 x 3 2 3 x 1 x 2 2 x 3 5 x1 , x 2 0, x 3 无约束
设备
产 品
解：
1.决策变量：设产品I、II的产量 分别为 x1、x2
2.目标函数：设总利润为z，则 有： max z = 2 x1 + x2 3.约束条件：
2x1 + 2x2 ≤ 12 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1 ≥ 0 , x2 ≥ 0
A 2 2
B 1 2
C 4 0
航线号 船队 类型 1 1 2 1 编队形式 拖轮 1 A型 驳船 2 — B型 驳船 — 4 货运成本 （千元／队） 36 36 货运量 （千吨） 25 20
3
2 4
2
1
2
—
4
4
72
27
40
20
船只种类 拖 轮
船只数
30 34 52
航线号
1 2
合同货运量
200 400
A型驳船 B型驳船
问：应如何编队，才能既完成合同任务，又使总货运成本为最小？
线性规划问题的数学模型
（2）如何化标准形式 目标函数的转换 (-1)，可化为求极大值问题。 即
max z z c j x j
如果是求极小值即min z c j x j ，则可将目标函数乘以
也就是：令 z z ，可得到上式。
变量的变换 若存在取值无约束的变量 x j，可令 x j xj xj 其中：xj , xj 0
线性规划问题的数学模型
标准形式如下：
x3 ) 0 x4 0 x5 max Z 2 x1 x2 3( x3 x3 ) x4 7 5 x1 x2 ( x3 x x ( x x) x5 2 1 2 3 3 x3 ) 5 3 x1 x2 2( x3 , x3 , x4 , x5 0 x1 , x2 , x3
j 1
n
n a ij x j bi s . t j 1 i 1,2, , m x j 0, j 1,2, , n
特点： (1) 目标函数求最大值（有时求最小值） (2) 约束条件都为等式方程，且右端常数项bi都大于或等于零 (3) 决策变量xj为非负。
目标函数：
max (min) z c 1 x 1 c 2 x 2 c n x n a 1 1 x 1 a 1 2 x 2 a 1 n x n ( ) b1
约束条件：
a m 1 x 1 a m 2 x 2 a m n x n ( ) bm x 1 0 x n 0
线性规划问题的数学模型
4. 建模步骤
(1) 确定决策变量：即需要我们作出决策或选择的量。一般 情况下，题目问什么就设什么为决策变量；
(2) 找出所有限定条件：即决策变量受到的所有的约束； (3) 写出目标函数：即问题所要达到的目标，并明确是max 还是 min。
线性规划问题的数学模型
5. 线性规划数学模型的一般形式
线性规划问题的数学模型
例1.8 将线性规划问题化为标准型
minZ -x1 2 x2 3 x1 8 x2 5 x1 3 x2 4 x 0, x 无约束 2 1
解：
m ax Z x1 2(x 3 x4 ) 3 x1 8(x 3 x4 ) x5 5 x1 3(x 3 x4 ) x6 4 x ,x ,x ,x ,x 0 1 3 4 5 6
线性规划问题的数学模型
例1.9 将线性规划问题化为标准型
Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4 s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 ≤ 28 4 x1 + 2 x2 + 3 x3 - 9 x4 ≥ 39 6 x2 + 2 x3 + 3 x4 ≤ - 58 x1 , x3 , x4 ≥ 0； x2无约束
线性规划问题的数学模型
2. 线性规划的数学模型由三个要素构成 决策变量 目标函数 约束条件 Decision variables Objective function Constraints
怎样辨别一个模型是线性规划模型？
其特征是：
（1）问题的目标函数是多个决策变量的线性函数， 通常是求最大值或最小值；
线性规划问题的数学模型
解：
设：xj为第j号类型船队的队数（j = 1，2，3，4）， z 为总货运成本 则： min z = 36x1 + 36x2 + 72x3 + 27x4
x1 + x2 + 2x3 + x4 ≤ 30
2x1 + 2x3 ≤ 34 4x2 + 4x3 + 4x4 ≤ 52 25x1+20x2 ＝200 40x3+20x4 ＝400 xj ≥ 0 （ j = 1,2,3,4）
线性规划问题的数学模型
解:
x4 x5 替换 x3 ，且 x4 , x5 ， 0 引入变量 x6 , x7
用
将第3个约束方程两边乘以（－1） 将极小值问题反号，变为求极大值
标准形式如下：
max Z 2 x1 x2 3( x4 x5 ) 0 x6 0 x7 7 5 x1 x2 ( x4 x5 ) x6 x x (x x ) x7 2 1 2 4 5 5 3 x1 x2 2( x4 x5 ) x1 , x2 , x4 , x5 , x6 , x7 0
（2）在一定的资源条件限制下，如何组织安排生产获得最 好的经济效益（如产品量最多 、利润最大.）
线性规划问题的数学模型
例1.1 如图所示，如何截取x使铁皮所围成的容积最 大？ x
v a 2 x x
2
a
dv 0 dx
2(a 2 x ) x ( 2) (a 2 x )2 0
（2）问题的约束条件是一组多个决策变量的线性不 等式或等式。
线性规划问题的数学模型
3. 建模条件 (1) 优化条件：问题所要达到的目标能用线型函数描述，且 能够用极值（max 或 min）来表示； (2) 限定条件：达到目标受到一定的限制，且这些限制能够 用决策变量的线性等式或线性不等式表示； (3) 选择条件：有多种可选择的方案供决策者选择，以便找 出最优方案。