《数据模型与决策》第八章 线性优化

Chapter 8 Linear Optimization 线性优化 College of Management

College of Management Linear Optimization 线性优化 Chapter 8

8.1建模初步 例两 一 品 单位利润: 2个单位3个单位 生产约束: 总量限制 单位消耗能源I: 8 单位消耗能源I:4 204 16 单位消耗能源I:0 College of Management

College of Management 例： 两产品： 甲 乙 单位利润： 2个单位 3个单位 生产约束： 总量限制 单位消耗能源I: 1 2 8 单位消耗能源II: 4 0 16 单位消耗能源III: 0 4 12 8.1 建模初步

建模如下: max z= 2X, +3x st.x1+2x2≤8 4x <16 4x2≤12 x1x2≥0(非负约束) College of Management

College of Management 建模如下： max z = 2x1+3x2 s.t. x1+2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1 , x2 ≥ 0 (非负约束)

82基本概念 日标函数:z(x1,x2)=2x+3x2 决策变量:x12x2 约束条件 资源约束:x1+2x2≤8 4x2≤12 变量非负约束 0 College of management

College of Management 8.2 基本概念 ◆ 目标函数： z(x1 , x2 ) = 2x1+3x2 ◆ 决策变量： x1 , x2 ◆ 约束条件： ◆资源约束： x1+2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 ◆变量非负约束： x1 , x2 ≥ 0

模型的一般表示法: min CX C:价值向量(目标函数系数向量) maX Ⅹ:决策变量(列向量),n维 opt S.t. AX0 A:m行n列矩阵表示m个约束条件 b:常数(右端)列向量 College of Management

College of Management ◆模型的一般表示法： min CX C: 价值向量(目标函数系数向量) X: 决策变量(列向量)，n维 s.t. AX≤ b X≥ 0 A：m行n列矩阵 表示m个约束条件 b：常数(右端)列向量         opt max

Feasible Solution 任一满足AX≤b的解Ⅹ X>0 Optimal Solution 使目标函数取最优值的可行解 有不等号:用图解法,仅限两维 处理方法:将不等式化为等式,再结合线性方 程组处理,求解 College of Management

College of Management ◆ Feasible Solution 任一满足 AX ≤ b 的解 X X≥ 0 ◆ Optimal Solution 使目标函数取最优值的可行解 ◆ 有不等号：用图解法，仅限两维 ◆ 处理方法：将不等式化为等式，再结合线性方 程组处理，求解

max Z=2X+3x 从等值线看变化 S.t. x1+2x2 +X3 4 16 4x 12 X1,X2,x32X4,Xs>0 松弛变量x3,X4,x5≥0表达不等式方向 College of Management

College of Management max z = 2x1+3x2 从等值线看变化 s.t. x1+2x2 ＋x3 ＝ 8 4x1 ＋x4 ＝ 16 4x2 ＋x5 ＝ 12 x1 , x2 , x3 , x4 , x5 ≥ 0 松弛变量x3 , x4 , x5 ≥ 0表达不等式方向

图解法的启示: 可行解:无穷点集 最优解必在边界上(常在顶点处) 顶点=某线性方程组的解 常用的算法有单纯形法(简单的几何图形) AX-b X>0 College of management

College of Management 图解法的启示： ◆ 可行解：无穷点集 ◆ 最优解必在边界上(常在顶点处) ◆ 顶点＝ 某线性方程组的解 ◆ 常用的算法有单纯形法(简单的几何图形) AX＝b X≥0

83建模的有关讨论 运输问题举例:三个供应源A,三个需求源S人《 B B 2 B 3 量 A X X 12 13 8 2 21 22 A 2 3 6 18 求 9 4 18 量 College of Management

College of Management 8.3 建模的有关讨论 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

供需平衡的问题 如何安排运量可使总费用最小? 单位运价(C B B B 3 A13 4 A 2 4 5 2 A368 College of Management

College of Management 供需平衡的问题： 如何安排运量可使总费用最小？ 单位运价(Cij) B1 B2 B3 A1 A2 A3 3 2 4 4 5 2 6 8 1