第五章 线性规划
5-1 线性规划的标准形式与基本性质 5-2 基本可行解的转换 5-3 单纯形方法及应用举例
*
整体概述
概述一
点击此处输入
相关文本内容
概述二
点击此处输入
相关文本内容
概述三
点击此处输入
相关文本内容
Page 2
*
第五章 线性规划
目标函数和约束条件都是线性的，像这类约束 函数和目标函数都是为线性函数的优化问题，称作 线性规划问题。它的解法在理论和方法上都很成熟， 实际应用也很广泛。虽然大多数工程设计是非线性 的，但是也有采用线性逼近方法求解非线性问题的。 此外，线性规划方法还常被用作解决非线性问题的 子问题的工具，如在可行方向法中可行方向的寻求 就是采用线性规划方法。当然，对于真正的线性优 化问题，线性规划方法就更有用了。
值1万元；需占用一车间工作日5天， 二车间工作日2天。现一车间可用于
s .t . 3 x1 5 x 2 15
生产A、B产品的时间15天，二车间 可用于生产A、B产品的时间24天。 试求出生产组织者安排A、B两种产
6 x1 2 x 2 24 x1 0
品的合理投资产数，以获得最大的总 产值。
a i1x1ai2x2 ainxn xni bi 约束条件为“ ”时：
如 :6x12x224 6x12x2x324
x3为松弛变量
Page 8
*
• 如果有不等式约束： ai1x 1ai2x2ainxn bi 则可减去x新 ni 的 0(此 变时 量x称 ni为剩余)变 ，量 把它们全 等式约束，即 ai1x 1ai2x2ainxnxni bi
3 x1' -3 x1 " +2x2 +x3 = 8 x1' - x1 " - 4x2 +x 4= 14 x1' , x1" ,x2 ,x3 ,x4 0
Page 10
*
（3）x两边有约束的情况。
x1+x2 5 -6 x1 10 x20
-6+6 x1+6 10+6 令x1' = x1 +6 0 x1' 16
分析：每天生产的甲、乙两种产品分别为 x 1 , x 2 件
f(x 1 ,x 2 ) 6 0 x 1 1 2 0 x 2 m a x (利润最大) g 1(X )9x 14x23 6 0（材料约束）
g 2(X ) 3 x 1 1 0 x2 3 0 0 （工时约束）
g 3(X )4x15 x22 0 0 （电力约束）

Page 7
*
将一般形式的线性规划化为标准形式的方法
约束条件包括两部分：一是等式约束条件，二是变量 (2)的 非在负约 要求束，条 它是件标中准， 形式中出现的唯一不等式形式
• 如果有不等式约束： a i1x1ai2x2 ainxn bi 则可加上新x的 ni 变 0(此 量时称 xni为松弛变)，量把它们全变 等式约束，即
约束条件为“ ”时：如 :1 0 x 1 1 2 x2 1 8
1 0x 1 1 2x2x3 1 8 x3为剩余变量
Page 9
*
(2) 变量
1、x 0，令x’＝- x。
例如：
3x1+2x2 8 x1 -4x2 14
x20
2、x取值无约束，令x= x'- x"
3 x1' -3 x1 " +2x2 8 x1' - x1 " - 4x2 14 x1' , x1" , x2 0
Page 5
*
例5-3：某厂生产甲、乙两种产品，已知：①两种产品分别由两 条生产线生产。第一条生产甲，每天最多生产9件，第二条生产 乙，每天最多生产7件；②该厂仅有工人24名，生产甲每件用2工 日，生产乙每件用3工日；③产品甲、乙的单件利润分别为40元 和80元。问工厂如何组织生产才能获得最大利润？
m a x F ( X ) 4 0 x1 8 0 x 2 日利润最大
s.t. x1 9
x2 7
2 x1 3 x2 2 4
x1, x2 0
生产能力限制 劳动力限制 变量非负
Page 6
*
二、线性规划的标准形式
线性规划数学模型的一般形式：求 x[x1x2 xn]T
使 且满足
说明： 1）m=n,唯一解 2）m>n,无解 3）m<n,无穷解
Page 3
*
§5-1 线性规划的标准形式与基本性质
一、线性规划实例
解：设生产A、B两产品分别
例每生5-1产：一某台工产厂品要A生可产获A产、值B2两万种元产；品，为数学x1,模x型2台为，：则该问题的优化
需占用一车间工作日3天，二车间工 作日6天；每生产一台产品B 可获产
max z 2 x1 x 2
p1 3,6Ｔ， p2 5,2Ｔ， p3 1,0Ｔ， p4 0,1Ｔ Ap1, p2, p3, p4
Page 12
x1' +x2 11 x1' 16 x1' , x2 0
(4) 右端常数
右端项b＜0时，只需将等式或不等式两 端同乘(一1)，则等式右端项必大于零。
Page 11
*
例5 1的数学模型可化为如下标准形式：
max z 2x1 x2 s.t. 3 x1 5x2 15 6 x1 2x2 24
min z 2 x1 x2 s.t. 3x1 5x2 x3 15
x1 0
6 x1 2 x2 x4 24
x2 0
x j 0( j 1,2,3,4)
用 矩 阵 和 向 量有 表： 示 ， 则
A63
5 2
1 0
10, b15,24Ｔ， c2,1,0,0，
x2 0
Page 4
*
例5-2：生产甲种产品每件需使用材料9kg、3个工时、4kw电，获 利润60元。生产乙种产品每件需用材料4kg、10个工时、5kw电， 可获利120元。若每天能供应材料360kg，有300个工时，能供 200kw电。试确定两种产品每天的产量，使每天可能获得的利润最 大？
f( x ) c 1 x 1 c 2 x 2 c n x n m i n
a11x1 a12x2 a1n xn b1 a21x1 a22x2 a2n xn b2 am1x1 am2x2 amn xn bm
xi0(i1,2, ,n) bj 0(j1,2, ,m )