文档介绍：Linear Optimization
线性优化
Chapter 8
例:
两产品: 甲乙
单位利润: 2个单位 3个单位
生产约束: 总量限制
单位消耗能源I: 1 2 8
单位消耗能源II: 4 0 16
单位消耗能源III: 0 4 12
建模初步
建模如下:
max z = 2x1+3x2
. x1+2x2 ≤ 8
4x1 ≤ 16
4x2 ≤ 12
x1, x2 ≥ 0 (非负约束)
基本概念
目标函数: z(x1, x2) = 2x1+3x2
决策变量: x1, x2
约束条件:
资源约束: x1+2x2 ≤ 8
4x1 ≤ 16
4x2 ≤ 12
变量非负约束: x1, x2 ≥ 0
模型的一般表示法:
min CX C: 价值向量(目标函数系数向量)
X: 决策变量(列向量),n维
. AX≤ b
X≥ 0
A:m行n列矩阵表示m个约束条件
b:常数(右端)列向量
Feasible Solution
任一满足 AX ≤ b 的解 X
X≥ 0
Optimal Solution
使目标函数取最优值的可行解
有不等号:用图解法,仅限两维
处理方法:将不等式化为等式,再结合线性方程组处理,求解
max z = 2x1+3x2 从等值线看变化
. x1+2x2 +x3 = 8
4x1 +x4 = 16
4x2 +x5= 12
x1, x2, x3, x4, x5 ≥ 0
松弛变量x3, x4, x5 ≥ 0表达不等式方向
图解法的启示:
可行解:无穷点集
最优解必在边界上(常在顶点处)
顶点= 某线性方程组的解
常用的算法有单纯形法(简单的几何图形)
AX=b
X≥0
建模的有关讨论
B1 B2 B3
供给量
A1
A2
A3
x11 x12 x13
x21 x22 x23
x31 x32 x33
8
4
6
需
求
量
9 5 4
18
18
运输问题举例:三个供应源Ai, 三个需求源Bj
供需平衡的问题:
如何安排运量可使总费用最小?
单位运价(Cij)
B1 B2 B3
A1
A2
A3
2 4
5 2
6 8 1