《运筹学》之线性规划 (2)

返回目录
连续性假定
线性规划问题中的决策变量应 取连续值。
返回目录
确定性假定 线性规划问题中的所有参数都 是确定的参数。线性规划问题 不包含随机因素。
返回目录
线形规划的图解法
X2 2X1+X2=50 4X1+3X2=120 Z=50X1+30X2 X1
X2 (15,20) X1
确定可行域 目标函数等值线
其
中
，x
3
,
x
4
,
x
为
5
基
本
变
量
，
x1
,
x
为
2
非
基
本
变
量
。
返回目录
线形规划解的概念：最优基本解
max z 3x1 5x2
x1
x3
8
s.t.
3x1
2x2 4x2
x4 12 x5 wk.baidu.com6
x1, x2 , x3, x4 , x5 0
x1 x2 x3 x4 x5
1 0 1 0 0 8
A 0 2 0 1 0 12
≤8
（1）
2x2 ≤ 12 3x1 + 4x2 ≤ 36
（2） （3）
x1, x2 ≥0
为约束不等式左边分别添加松弛变 量x3、x4、x5, 约束变为等式
x1
+ x3
=8
2x2
+ x4 = 12
3x1 + 4x2
+ x5 = 36
x1, x2 ≥0
返回目录
非标准型LP的标准化:约束函数2
3、约束“≥”的形式
满足目标要求的 可行解称为最优 解，记为X*； 它所对应的目标 函数值称为最优 值，记为z*。有 时称（X*,z*） 为最优解，简称 为解。
X2 X*=(15,20) Z*=1350
X1
返回目录
线形规划解的概念：基本解
max z 3x1 5x2
x1
x3
8
s.t.
3x1
2x2 4x2
x4 12 x5 36
b2 ( ...........
0) .....
.
.
.
.
am1x1 am2 x2 ... amnxn bm ( 0)
x1 0, x2 0, ..., xn 0
n
(M 2 ) : max z c j x j j 1
s.t.
n
aij x j
bi ,
i 1,2,...m
j1
x
返回目录
线性规划问题隐含的假定
•比例性假定 •可加性假定 •连续性假定 •确定性假定
返回目录
比例性假定
决策变量变化引起的目标函数的改 变量和决策变量的改变量成比例， 同样，每个决策变量的变化引起约 束方程左端值的改变量和该变量的 改变量成比例。
返回目录
可加性假定
每个决策变量对目标函数和约 束方程的影响是独立于其他变 量的，目标函数值是每个决策 变量对目标函数贡献的总和。
b1
b
b2
bm
(M 4 ) : max z CT X | AX b, X 0
返回目录
非标准型LP的标准化:目标函数
min z = CTX 易知 -max(-z) = min(z) = CTX 即 max(-z) = - CTX 令 z’ = -z， 得max z’ = - CTX
返回目录
线形规划的一般模型:数学模型
max z=c1x1 + c2x2 + … + cnxn s.t. a11x1 + a12x2 + … + a1n xn ≤b1
a21x1 + a22x2 + … + a2n xn ≤ b2
……………………………………………
am1x1 + am2x2 + … + amnxn ≤ bm xj ≥0 (j = 1,2,…,n)
返回目录
例1.1 生产计划问题（资源利用问题）
胜利家具厂生产桌子和椅子两种家具。桌子售价 50元/张，椅子销售价格30元/把，生产桌子和椅 子要求需要木工和油漆工两种工种。生产一张桌 子需要木工4小时，油漆工2小时。生产一把椅子 需要木工3小时，油漆工1小时。该厂每个月可用 木工工时为120小时，油漆工工时为50小时。问 该厂如何组织生产才能使每月的销售收入最大？
c5
,
x2
6
1 2 c4
x3
4
2 3 c4
1 3 c5
当c4 c5 0,得 方 程 组 特 解x0 (4,6,4,0,0)T
由 目 标 函 数fmax 可 知 目 标 不 能 继 续 改 善
故 称 该 解 为 规 划 问 题 的一 个 最 优 基 本 解
返回目录
线形规划的应用模型
生产计划问题 食谱问题
返回目录
非标准型LP的标准化:约束函数1
1、bi<0: x1 - 2x2 = -1 ⇒ -x1 + 2x2 = 1
2、约束“≤” 的形式： x1 ≤8 ⇒ x1 + x’ = 8 (x’≥0)
称x’为松弛变量，它不影 响目标函数，所以在目标 函数的系数为零
例：max z = 3x1 + 5x2
s.t x1
线性规划问题隐含的假定 比例性假定 可加性假定 连续性假定 确定性假定 线形规划的图解法 线形规划解的可能结果 线形规划的标准形式1 线形规划的标准形式2 非标准型LP的标准化:目标函数 非标准型LP的标准化:约束函数1 非标准型LP的标准化:约束函数2 非标准型LP的标准化:决策变量
线形规划解的概念：可行解 线形规划解的概念：最优解 线形规划解的概念：基本解 线形规划解的概念：最优基本解 线形规划的应用模型 生产计划问题 生产计划问题：表格分析 生产计划问题：模型 产品配套问题 产品配套问题：工时分析 产品配套问题：配套分析 产品配套问题：模型 结束放映
产品配套问题 下料问题 配料问题
返回目录
生产计划问题
某企业使用m种资源生产n种产品，已知 第i种资源的数量是bi，其单价为pi，每生 产一个单位第j种产品所提供的产值是vj， 所消耗第i种资源的数量是aij。第j种产品 的合同与指令性计划的产量指标是ej，最 高需求量为dj。问该企业该如何指定生产 计划？
x1, x2 , x3, x4 , x5 0
x1 x2 x3 x4 x5
1 0 1 0 0 8
A 0 2 0 1 0 12
3
4
0
0
1 36
参考约束函数标准化
易 知 ：R( A) R( A) r 3 m
又 因 ：r 3 5 n
故：方程组有无穷多个解
取A中 单 位 矩 阵 对 应 的 变 量
返回目录
各种食物的营养成分表
序号
食品 名称
热量
（千卡）
蛋白质 钙
（克）
（毫克）
价格
（元）
1 猪肉 1000 50
400 14
2 鸡蛋 800
60
200
6
3 大米 900
20
300
3
4 白菜 200
10
500
2
返回目录
各种食物的营养成分表（转置）
热量（千卡） 蛋白质（克） 钙（毫克） 价格（元） 食品需要量
运筹学
线性规划基本性质
返回目录
线形规划基本性质目录
线性规划（概论） 线性规划问题:生产计划问题 例1.1 生产计划问题（资源利用问题） 例1.1生产计划问题分析 例1.1生产计划问题模型 例1.1生产计划问题表格描述 例1 .2 营养配餐问题 各种食物的营养成分表 各种食物的营养成分表（转置） 例1 .2 营养配餐问题求解 用于成功决策的实例 线形规划的一般模型:特点 线形规划的一般模型:数学模型
50x1+ 60x2 + 20x3+ 10x4 ≥ 55 400x1+200x2 +300x3+500x4 ≥ 800 x1，x2 ， x3 ， x4 ≥ 0
返回目录
用于成功决策的实例
1、美国航空公司关于哪架飞机用于哪一航 班和哪些机组人员被安排于哪架飞机的 决策；
2、美国国防部关于如何从现有的一些基地 向海湾运送海湾战争所需要的人员和物 资的决策；
猪肉 鸡蛋 大米 白菜 营养要求
1000 800 900 200 3000
50 60 20 10
55
400 200 300 500 800
14
6
32
X1
X2
X3 X4
返回目录
例1 .2 营养配餐问题求解
设Xj为第j种食品每天的购入量，则配餐 问题的线性规划模型为：
min S=14x1+6x2 +3x3+2x4 s.t. 1000x1+800x2 +900x3+200x4 ≥ 3000
3、北美长途运输公司关于每周如何调度数 千辆货车的决策。
返回目录
线形规划的一般模型:特点
系统需要求解待定方案，方案必须满足指 定的条件，而且需要实现指定的目标。 1、决策变量：表示待定方案，一组取值代 表一个方案，决策变量需要满足一定条件； 2、约束条件：用等式或不等式表示； 3、期望目标：用确定的数量方法表示。
3
4
0
0
1 36
取x1
,
x
2
,
x
为
3
基
本
变
量
，x
4
,
x
为
5
自 由 变 量 ， 从 约 束 方 程2，3解 出
x1
4
2 3
x4
1 3
x 5，x 2
6
1 2
x4
目 标 函 数 ：z
42
1 2
x4
x5
( fmax )
令x4 c4 , x5 c5得 通 解
x
4
x1
c4 , x5 c5 21
4 3 c4 3
j
0,
j 1,2,...,n
返回目录
线形规划的标准形式2
(M 3) : max z CT X AX b
s.t. X 0
CT (c1, c2 ,...cn )
a11 a12 ... a1n
A
a21
a22
... a2n
am1 am2 ... amn
x1
X
x2
,
xn
x
3
,
x
4
,
x
为
5
基
本
变
量
，x1
,
x
为
2
自 由 变 量 ， 令x1 c1 , x2 c2得 通 解
x1 c1
x x
2 3
c2 8
c1
x
4
12
2c2
x5 36 3c1 4c2
当c1 c2 0, 得 方 程 组 特 解
x0 (0,0,8,12,36)T
称 该 解 为 约 束 方 程 组 的一 个 基 本 解
返回目录
线性规划（概论）
线形规划是研究解决有限资源最佳分 配的运筹学方法，即如何对有限的资 源做出最佳方式的调配和最有利的利 用，以便最充分地发挥资源的效能去 获得最佳经济效益。
返回目录
线性规划问题:生产计划问题
1、如何合理使用有限的人力、物力和资 金，实现最好的经济效益。
2、如何合理使用有限的人力、物力和资 金，以达到最经济的方式，完成生产 计划的要求。
注：s.t. – Subject to
返回目录
例1.1生产计划问题表格描述
桌子 木工 4 漆工 2 单价 50 生产量 X1
椅子 3 1 30 X2
总工时 120 50
返回目录
例1 .2 营养配餐问题
假定一个成年人每天需要从食物中获得 3000千卡的热量、55克蛋白质和800毫克 的钙。如果市场上只有四种食品可供选择， 它们每千克所含的热量和营养成分和市场 价格见各种食物的营养成分表。问如何选 择才能在满足营养的前提下使购买食品的 费用最小？
最优点的确定 最优解在凸多边形的
顶点
返回目录
线形规划解的可能结果
唯一解
多重解
无解
返回目录
线形规划的标准形式1
(M1) :
max z c1x1 c2 x2 ... cn xn
a11x1 a12 x2 ... a1n xn b1( 0)
s.t.
.a.2.1..x.1.
a22 x2 ... a2n xn ..............................
min z = 3x1 + 2x2 s.t. 12x1 + 3x2 ≥ 4 (1)
2x1 + 3x2 ≥ 2 (2) 3x1 + 15x2 ≥ 5 (3) x1 + x2 = 1 (4) x1 ≥0, x2 ≥0
s.t 12x1 + 3x2 – x3 = 4 2x1 + 3x2 – x4 = 2 3x1 + 15x2 – x5 = 5 x1 + x2 = 1 x1 ≥0, x2 ≥0
返回目录
例1.1生产计划问题分析
解：将实际问题转化为线性规划模型有以下几个步骤：
1．确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量
2．确定目标函数：家具厂的目标是销售收入最大
max z=50x1+30x2 3．确定约束条件：
（1）
4x1+3x2≤120（木工工时限制) （2） 2x1+x2 ≤ 50 （油漆工工时限制） （3） 4．变量取值限制：
称x3、x4、x5为剩余变量，它们不影响目标函数。
返回目录
非标准型LP的标准化:决策变量
决策变量xj ≤0 设x’ j = - xj 则x’ j ≥0
返回目录
线形规划解的概念：可行解
满足线形规划
问题所有约束
X2
条件的向量X称
为可行解，所
有可行解的集
X1
合称为可行域，
记为R。
返回目录
线形规划解的概念：最优解
一般情况，决策变量只取正值（非负值）
x1 ≥ 0, x2 ≥ 0
（4）
返回目录
例1.1生产计划问题模型
数学模型 max S=50x1+ 30x2 s.t.4x1 + 3x2 ≤ 120 2x1 + x2 ≤ 50 x1，x2 ≥ 0
（1） （2） （3） （4）
线性规划数学模型三要素： 1、决策变量： X1,X2 2、目标函数：（1） 3、约束条件：（2、3、4）