可行域
OR课件
LP
例1.4 现有两个变量的LP模型
x2
§4 LP 问 题 图 解 法
Z 10 x 8x 3x 2 x 120 非 30 x 基 本 45 x 解 , x x 0
max 1 1 2 1 2 1 2
2
80 60
(10,45) Z=460
约束条件
非负约束
OR课件
LP
§1 LP 问题 及其 数学 模型
例、某工厂用三种原料生产三种产品，已 知的条件如下表所示，试制订总利润最大 的生产计划。
单位产品所需原 料数量（公斤） 产品 Q1 1
x
2 0 3 3
产品 2 Q2
x
3 2 2 5
产品 Q33
x
原料可用量 （公斤/日）
原料P1
原料P2 原料P3
OR课件
LP
§1 LP 问题 及其 数学 模型
例2 运输问题：甲乙两地分别有货物80t和 100t，要运送到a，b，c三个地方，数量分 别是70，60和50t，它们之间的单位运价 （元/T· km）如下表，现在要制订出最佳运 输方案，使总的运输费用达到最小。
收点 发点
a 5 8 70
b 4 6 60

OR课件
LP
LP问题标准形式
§2 LP 问题 的标 准型 及其 转化
MaxZ c x Ax b s.t. x 0
特征：
目标取极大（MaxZ) 约束条件取等式（＝） 变量取非负（0）（另外：b0)

OR课件
LP问题模型转换

LP
§2 LP 问题 的标 准型 及其 转化
原料 P3 ： 3x1 2 x2 5x3 2000
非负约束：产量为非负数
x1,x2,x3 ≥0
OR课件
LP
§1 LP 问题 及其 数学 模型
max 3 x1 5 x2 4 x3 2 x1 3 x 2 1500 s.t. 2 x 2 4 x 3 800 3 x1 2 x 2 5 x 3 2000 x1 , x 2 , x 3 0
约束条件
OR课件
LP
其中：
§2 LP 问题 的标 准型 及其 转化
x j ; j 1,2,...,n
为待定的决策变量，
c ( c 1 , c 2 , , c n ) 为价值向量，
c j ; j 1,2,...,n 为价值系数，
b ( b1 , b 2 ,...,b m ) 为右端向量，
0 4 5 4
1500 800 2000
单位产品的利润 （千元）
OR课件
LP
解：设
决策变量：每天生产三种产品的数量，分别设为
§1 LP 问题 及其 数学 模型
x1 , x2 , x3
目标函数：每天的生产利润最大
MaxZ 3x1 5x2 4 x3
约束条件： 每天原料的需求量不超过可用量： 原料 P1 ： 2 x1 3x2 1500 原料 P2 ： 2 x2 4 x3 800
例1、某工厂生产A、B两种产品，都需使 用铜和铝两种金属材料，有关资料如下表 所示。问如何确定A,B产品的产量，使工厂 获取的总利润最大？
原 料 铜 铝 单位产品的利润 （万元） A产品单 1 耗（吨）
x
B产品单 2 耗（吨）
x
原料可用量 （吨）
2 x1 + 1 x2 ≤ 1 x1 + 3 x2 ≤ 3 x1 4 x2
剩余变量
பைடு நூலகம்
OR课件
不等式变不等式
§2 LP 问题 的标 准型 及其 转化
a i 1 x 1 a i 2 x 2 a in x n b i
a i 1 x 1 a i 2 x 2 a in x n b i
或
a i 1 x 1 a i 2 x 2 a in x n b i a i 1 x 1 a i 2 x 2 a in x n b i
max 1 2
2 2 1 2 1
最优目标值： Z=120
最优解为AB线段上所有点 －－称为多重解
X = XA + (1-)XB
0
20
40
60
80 x1
OR课件
LP
§4 LP 问 题 图 解 法
例1.6 某LP问题的可行域如下图：
MaxZ
OR课件
LP
LP问题模型转换
§2 LP 问题 的标 准型 及其 转化
例 把问题转化为标准形式
min S x1 x 2 2 x1 x2 2 x 2x 2 1 2 s.t. x1 x2 5 x1 0
MaxZ x1 ( x3 x4 ) 2 x1 ( x3 x4 ) x5 2 x 2( x x ) x 2 1 3 4 6 s.t. x1 ( x3 x4 ) x7 5 xi 0; i 1,3,4,5,6,7
a i 1 x 1 a i 2 x 2 a in x n b i
a i 1 x 1 a i 2 x 2 a in x n s i b i , s i 0
或
a i 1 x 1 a i 2 x 2 a in x n b i
松弛变量
a i 1 x 1 a i 2 x 2 a in x n s i b i , s i 0
OR课件
LP
§3 LP 问 题 解 的 概 念
可行解：满足LP问题所有约束条件的解。 最优解：满足目标函数的可行解。
MaxZ CX AX b X 0
OR课件
LP
§3 LP 问 题 解 的 概 念
基、基变量、非基变量：
X x1 x2 xm xm1 xn a11 a12 a1m a1m1 a1n A am1 am2 amm amm1 amn a11 a12 a1m B a a a mm m1 m2
40 20
不 可 行 解
x
2
= Z/8 － 5/4 x1
0 可行域
20
40
60
80 x1
若Z=160, x2=20－5/4x1 等值线
最优解: x1=10, x2=45, Z=460 (唯一最优解)
OR课件
LP
§4 例1.5 若将上例的目标函数改为： x LP Z 3x 2x 问 约束条件不变，其最优 80 题 解会发生什么变化？ 60 不 可 图 A(10,45) Z=120 行 x = Z/2 － 3/2 x 解 40 解 法 若Z=60, x =30－3/2x 20 B(30,15) Z=120
变量转换
负变量化为正变量
令自由变量 x j x ，其中 x x j j j , x j 为非负变量

目标转换
求最大可以等价成求负的最小
MinS c x MaxZ c x

约束转换
OR课件
LP问题约束转换
等式变不等式
§2 LP 问题 的标 准型 及其 转化
退化基本解：非零基变量的个数小于m的 基本解。
OR课件
LP
LP问题解集
§3 LP 问 题 解 的 概 念
非 基 本 解
基本解
可行解
不 可 行 解
其交集为基本可行解
OR课件
§3 LP 问 题 解 的 概 念
1． 基本可行解不一定都是最优解， 最优解也不一定都是基本解 2． 如果有两个基本可行解是最优解， 则两解的凸组合也都是最优解。 3． 如果最优解不唯一，则会有多个基本可行解是最优解，它们必然在 同一个面上。 4．基本可行解个数有限，可以在基本可行解中寻找最优解。
矩阵
a 11 a 21 A a m1 a 12 a 22 am2 a1n a 2n a mn
为系数矩阵。
OR课件
LP
§2 LP 问题 的标 准型 及其 转化
LP问题规范形式
min c x Ax b s.t. x 0
40 30
利润（Z）=3x1
+ 4x2
OR课件
LP
决策变量
解：设A、B两种产品的产量分别为x1、x2， 则使工厂获取的总利润最大的数学模型如下：
§1 LP 问题 及其 数学 模型
Max z=3x1 + 4x2
2x1＋x2 ≤ 40 （铜） x1＋3x2 ≤ 30（铝） x1, x2 ≥ 0
目标函数
OR课件
运 筹 帷 幄 之 中 Linear Programming-----LP
决 胜
线性规划基础
（第1章）
千 里 之 外
OR课件
导 学
重 点 与 难 点 -----
重点
掌握什么样的问题是线性规划问题，即
线性规划问题的数学模型的特点、标准型
的建立和图解法的基本思想。
难点
线性规划问题解的概念和标准型的转化。
OR课件
导 学
主 要 内 容 -----
§ 1 LP问题及其数学模型
§ 2 LP的标准型及其转化
§ 3 LP解的概念 § 4 LP的图解法
OR课件
LP
§1 LP 问题 及其 数学 模型

线性规划实例
生产计划问题 运输问题 线性规划模型 模型特征 建模步骤

OR课件
LP
§1 LP 问题 及其 数学 模型
（4）每一问题要求目标函数实现最大化（Max） 或者最小化（Min）。