a 11 a 12
A
a 21
am
1
a 22 am2
为系数矩阵。
a 1 n
a 2n
a mn
第12页
规范形式
min c x
Ax b
s .t .
x
0
第13页
标准形 式
min c x
Ax b
s
.t
.
x
0
第14页
概
念
可行解（或可行点）：满足所有约束条件的向量x (x1, x2, xn) 可行集（或可行域）：所有的可行解的全体
第17页
不等式变等 式
a i1 x 1 a i 2 x 2 a in x n b i
a i1 x 1 a i 2 x 2 a in x n s i b i , s i 0
或
a i1 x 1 a i 2 x 2 a in x n b i
松弛变量
a i1 x 1 a i 2 x 2 a in x n s i b i , s i 0
❖目标转换
求最大可以等价成求负的最小
maxcx mi ncx
❖ 约束转换 ❖ 实例
第16页
约束转换 ❖等式变不等式
ai1 x1 ai2 x2 ainxn bi
ai1 x1 ai2 x2 ainxn bi ai1 x1 ai2 x2 ainxn bi
❖ 不等式变等式
❖ 不等式变不等式
可控因素：每天生产三种产品的数量，分别设为 x1 , x2 , x3 目标：每天的生产利润最大
利润函数 3x1 5x2 4x3 受制条件：
每天原料的需求量不超过可用量： 原料P1 ： 2x1 3x2 1500 原料P2 ：2 x2 4x3 800 原料P3 ： 3 x1 2 x2 5 x3 2000
蕴含约束：数量非负xij 0;i 1,2, j 1,2,3,4
第9页
模 型
24
min
cij xij
i1 j1
xi1 xi2 xi3 xi4 ai ;i 1,2
s.t. x1j x2 j bj ; j 1,2,3,4
xij 0;i 1,2, j 1,2,3,4
第10页
一般形 式
注
释
x j ; j 1 , 2 ,..., n 为 待 定 的 决 策 变 量 ， c (c1 ,c 2 , ,c n ) 为 价 值 向 量 ， c j ; j 1 , 2 ,..., n 为 价 值 系 数 ， b ( b 1 , b 2 ,..., b m ) 为 右 端 向 量 ， 矩阵
蕴含约束：产量为非负数
x1 , x2 , x3 0
第5页
模 型
max 3 x1 5 x 2 4 x 3 2x1 3x2 1500
s.t. 2 x2 4 x3 800
3x1 2x2 5x3 2000 x1, x2 , x3 0
第6页
计算结 果
OBJECTIVE FUNCTION VALUE
2675.000
VARIABLE VALUE
REDUCED COST
X1
375.000000
0.000000
X2
250.000000
0.000000
X3
75.000000
0.000000
ROW SLACK OR SURPLUS DUAL PRICES
1)
0.000000
1.050000
2)
0.000000
第3页
生产计划问题
某工厂用三种原料生产三种产品，已知的条件如表 2.1.1所示，试制订总利润最大的生产计划
单位产品所需原 产品Q1 产品
料数量（公斤）
Q2
原料P1
23
原料P2
02
原料P3
32
单位产品的利润 3
5
（千元）
产品 Q3
原料可用量 （公斤/日）
0 1500
4
800
5 2000
4
第4页
问题分 析
剩余变量
x 1 a i 2 x 2 a in x n b i
a i1 x 1 a i 2 x 2 a in x n b i
或
a i1 x 1 a i 2 x 2 a in x n b i
a i1 x 1 a i 2 x 2 a in x n b i
目标函数
minz c1 x1 c2 x2 cn xn
ai1 x1 ai2 x2 ainxn bi ;i 1,2,...,p
s.t.axij1
x1
0;
ai2 x2 ainxn j 1,2,...,q
bi ;i
p 1,...,m
xj无 限 制; j 1,2,...,q
约束条件
第11页
运筹学课 件
运
决
筹
胜
帷
线性规划
千
幄
里
之
之
中
Linear
外
Programming
第1页
线性规 划
线性规划问题 可行区域与基本可行解 单纯形算法 初始可行解 对偶理论 灵敏度分析 计算软件 案例分析
第2页
线性规划问 题
线性规划实例
生产计划问题 运输问题
线性规划模型
一般形式 规范形式 标准形式 形式转换 概念
第19页
例2.1.3 把问题转化为标准形
0.625000
3)
0.000000
0.300000
第7页
运 输问 题
一个制造厂要把若干单位的产品从两个仓库Ai;i 1,2 发送到零售点Bj;j 1,2,3,4，仓库 Ai 能供应的产品数量为 ai;i 1,2，零售点Bj 所需的产品的数量为bj;j 1,2,3,4。 假设供给总量和需求总量相等，且已知从仓库 Ai 运一个单 位产品往Bj 的运价为cij 。问应如何组织运输才能使总运费 最Ai 小？
D {x Ax b, x 0}
最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体 称为最优解集合 O {x Dc x c y,y D }
最优值：最优解的目标函数值
v c x, x O
第15页
模型转换
❖变量转换
令 自 由 变 量 xjx j x j ， 其 中 x j,x j为 非 负 变 量
第8页
问题分析
可控因素：从仓库Ai 运往Bj 的产品数量 设为xij;i 1,2, j 1,2,3,4 目标：总运费最小
24
费用函数ci j xi j i1 j1
受控条件： 从仓库运出总量不超过可用总量，运入零售点的数量不低于需求量。 由于总供给量等于总需求量，所以都是等号。即
xi1 xi2 xi3 xi4 ai ;i 1,2 x1j x2j bj ; j 1,2,3,4