Ling Xueling
第二章 线性规划线性规划在数学上比较简单,但应用面极广
1,L.P.干什么问题 约束 目标生产 /库存计划 满足需求,资源有限 成本 最 小或产量 最 大股票 /证券选择 有限资金 收益 最 大广告媒体选择 有限预算 共知度 最 大配送中心,运输 满足需求,储能有限 成本 最 小
2,L.P,的两个特征目标 ＋ 约束 （ constrained optimization,maximization or
minimization）
Ling Xueling
第一节 一个最大值问题一,Par 公司问题提出
1,两种产品：中档,高档 golf 球袋
2,四工序：切割 （ C） 缝制 （ S） 装配 （ F） 检验和包装 （ I& P）
3,问题,如何组织生产？ 中,高档产品各应计划生产多少？
二,调研与数据
1,生产部门－－工序,工时分析
2,财务部门－－成本,售价分析,高档－ 9.00,中档－ 10.0
3,管理部门－－可用工时分析需用工时 C & D S F I & P
标准 7 / 1 0 1/2 1 1/10
高档 1 5/6 2/3 1/4
工序 C & D S F I & P
可用工时 630 600 708 135
Ling Xueling
第一节 一个最大值问题三,问题归纳
1,假设产品全部可以销售出去
2,要求：在已有的工时 约束 条件下,使利润 最大 化的两种产品之生产量各应是?
四、目标函数
1、建立决策变量 x1,x2
2、建立 o.f.
3、解（任意）、可行解（满足约束）、最优解五、（资源）约束
1、各工序可用工时约束
2、非负约束－－ L.P,一般特征,可使求解大大简化。
Ling Xueling
第一节 一个最大值问题六,完整的数学表达
1,模型
Max Z ＝ Max 10x1 ＋ 9x2
s.t.
7/10x１ ＋ x２ ≤ 630 ―― C & D
1/2x１ ＋ 5/6x２ ≤ 600 ―― S
x１ ＋ 2/3x２ ≤ 708 ―― F
1/10x１ ＋ 1/4x２ ≤ 135 ―― I & P
x 1,x 2 ≥ 0
2,说明
1） 因为只考虑了主要因素,模型只是现实世界的简化,近似
2） 本模型之数学 特征 是：所有的表达式都是 线性 式 。
Ling Xueling
第二节 线性规划图解法适用,仅有两个决策变量的 L.P,问题一,解点－－ 解的点坐标二,L.P,模型的几何表达
1,非负约束的表达
2,不等式约束的表达
(900,630),(1200,700),(708,1062),(1350,540)
3,定义
1） 可行域 2） 可行解
4,o.f,之几何表达 (180,200),(360,400),(540,600)
三,最优解几何表达及其求出 (540,252)
1,确定最优解触及的端点
2,解联立方程得最优解坐标,即为最优解点 。
Ling Xueling
第二节 线性规划图解法
Ling Xueling
第二节 线性规划图解法四,松弛变量和标准型
1,松弛变量－－ 能 提供资源 （ 工时 ） 使用信息 的变量
1） 四个约束的剩余,0 120 0 18
2） 定义 （ slack）
L.P,模型中对应,?,约束的 闲置 能力称为该约束的 松弛,对应的 非负 变量就称为松弛变量本例中,最优解受到第一,三约束界限,故一,三约束无松弛
2,L.P,模型标准型 （ standard form）
1） 定义 （ 除非负约束 外 ） 所有约束式都是 等式 的 L.P,模型
2） 意义 为将线性代数引入求解 多元 线性规划的方法作准备
3,多余约束不影响可行域 （ 或：可有可无 ） 的约束,称为多余约束如上例中的 S（ 第二 ） 约束 。
Ling Xueling
第二节 线性规划图解法五,端点与最优解
1,当 z = 5x1+9x2 时,最优解也是 端点,(300,420)
2,定理若可行域有界,则 L.P,问题最优解总在 可行域端点 处
3,定理的意义 （ 单形法的依据 ） －－提供了求解
L.P,问题的一般思路 （ 迭代方法 ）,
将一般 L.P,模型化成标准型
利用初等变换求解约束之线性方程组：得到解交点
将解代入目标函数,比较它们的大小
（ 通过迭代 ） 直至求得最优的解 。
Ling Xueling
第三节 线性规划图解法：最小值例子一,问题及其数学模型
1,有关数据两种产品,A 或 B 两种成本,2 或 3 / 每单位两种所需工时,2 或 1 / 每单位
2,有关约束
1） 为了追求规模效应,生产总数不得少于 350 单位
2） 销售部门报告,A 产品已经获得 125 单位的订货
3） 共有 600 可用工时
3,问题：最小成本时两种产品的生产量？
（ 课堂练习建立模型 ）
Ling Xueling
第三节 线性规划图解法：最小值例子一,问题及其数学模型
4,数学模型
min z = min 2x1 + 3x2
s.t.
x1 + x2? 350
x1? 125
2x1 + x2? 600
x1,x2? 0
Ling Xueling
第三节 线性规划图解法：最小值例子二,图解法
1,可行域三交点分别是,( 250,350 ) ( 125,225 ) ( 250,100 )
2,o.f,图形表达分别令 z = 600,1200 得 ( 300,200 ) ( 600,400 )
3,最优解
x1 = 250 (>125) x2 = 100 o.f,= 800 。
Ling Xueling
第三节 线性规划图解法：最小值例子三,剩余变量和标准型注意：最优解中 x1 = 250 超过最小需求 125 单位
1,定义 (surplus)
L.P,问题中对应,?” 约束的过剩量称为 剩余,其所对应的变量成为剩余变量
2,标准型
min z = min 2x1 + 3x2 + 0s1 + 0s2 + 0s3
s.t.
x1 + x2 － s1 = 0
x1 － s2 = 0
2x1 + x2 ＋ s3 = 0
xi,si? 0
Ling Xueling
第四节 线性规划图解法中的特殊情况一,无穷多解
1,问题特征
o.f,直线与可行域某边界直线重合
2,例子设 Par,公司问题中,中档高尔夫球袋的单位利润降为 6.3
则 z = 6.3 x1 + 9 x2 与 C&D 直线重合
3,评价好事,多重组合－－多种生产方案,皆可作为决策方案,
认为：此时有条件追求其他的,满意,目标 。
Ling Xueling
第四节 线性规划图解法中的特殊情况二,无解
1,问题特征不可能同时满足所有约束
2,例子在原 Par,公司问题中,加上约束,x1 > 500,x2 > 360
3,处理
1） 既要指出现有资源的不可行性
2） 也要给出正确的行动方案,如：如何增加资源可以使得预订目标得以实现？ 本例中,各工序如果分别至少补充
（ 80,0,32,5）,即可使得最大化利润的目标得到实现 。
Ling Xueling
第四节 线性规划图解法中的特殊情况三,无限界解
1,问题特征在 求最大化问题时,遭遇 o.f,可以无限制地增加
2,例子
max 20x1 + 10x2
s.t.
x1 > 2
x2 < 5
x1,x2? 0
3,评价模型有问题 ！ 很可能是有些 约束 被冒险地删去或忽略了 。
Ling Xueling
The End of Chapter 2
第二章 线性规划线性规划在数学上比较简单,但应用面极广
1,L.P.干什么问题 约束 目标生产 /库存计划 满足需求,资源有限 成本 最 小或产量 最 大股票 /证券选择 有限资金 收益 最 大广告媒体选择 有限预算 共知度 最 大配送中心,运输 满足需求,储能有限 成本 最 小
2,L.P,的两个特征目标 ＋ 约束 （ constrained optimization,maximization or
minimization）
Ling Xueling
第一节 一个最大值问题一,Par 公司问题提出
1,两种产品：中档,高档 golf 球袋
2,四工序：切割 （ C） 缝制 （ S） 装配 （ F） 检验和包装 （ I& P）
3,问题,如何组织生产？ 中,高档产品各应计划生产多少？
二,调研与数据
1,生产部门－－工序,工时分析
2,财务部门－－成本,售价分析,高档－ 9.00,中档－ 10.0
3,管理部门－－可用工时分析需用工时 C & D S F I & P
标准 7 / 1 0 1/2 1 1/10
高档 1 5/6 2/3 1/4
工序 C & D S F I & P
可用工时 630 600 708 135
Ling Xueling
第一节 一个最大值问题三,问题归纳
1,假设产品全部可以销售出去
2,要求：在已有的工时 约束 条件下,使利润 最大 化的两种产品之生产量各应是?
四、目标函数
1、建立决策变量 x1,x2
2、建立 o.f.
3、解（任意）、可行解（满足约束）、最优解五、（资源）约束
1、各工序可用工时约束
2、非负约束－－ L.P,一般特征,可使求解大大简化。
Ling Xueling
第一节 一个最大值问题六,完整的数学表达
1,模型
Max Z ＝ Max 10x1 ＋ 9x2
s.t.
7/10x１ ＋ x２ ≤ 630 ―― C & D
1/2x１ ＋ 5/6x２ ≤ 600 ―― S
x１ ＋ 2/3x２ ≤ 708 ―― F
1/10x１ ＋ 1/4x２ ≤ 135 ―― I & P
x 1,x 2 ≥ 0
2,说明
1） 因为只考虑了主要因素,模型只是现实世界的简化,近似
2） 本模型之数学 特征 是：所有的表达式都是 线性 式 。
Ling Xueling
第二节 线性规划图解法适用,仅有两个决策变量的 L.P,问题一,解点－－ 解的点坐标二,L.P,模型的几何表达
1,非负约束的表达
2,不等式约束的表达
(900,630),(1200,700),(708,1062),(1350,540)
3,定义
1） 可行域 2） 可行解
4,o.f,之几何表达 (180,200),(360,400),(540,600)
三,最优解几何表达及其求出 (540,252)
1,确定最优解触及的端点
2,解联立方程得最优解坐标,即为最优解点 。
Ling Xueling
第二节 线性规划图解法
Ling Xueling
第二节 线性规划图解法四,松弛变量和标准型
1,松弛变量－－ 能 提供资源 （ 工时 ） 使用信息 的变量
1） 四个约束的剩余,0 120 0 18
2） 定义 （ slack）
L.P,模型中对应,?,约束的 闲置 能力称为该约束的 松弛,对应的 非负 变量就称为松弛变量本例中,最优解受到第一,三约束界限,故一,三约束无松弛
2,L.P,模型标准型 （ standard form）
1） 定义 （ 除非负约束 外 ） 所有约束式都是 等式 的 L.P,模型
2） 意义 为将线性代数引入求解 多元 线性规划的方法作准备
3,多余约束不影响可行域 （ 或：可有可无 ） 的约束,称为多余约束如上例中的 S（ 第二 ） 约束 。
Ling Xueling
第二节 线性规划图解法五,端点与最优解
1,当 z = 5x1+9x2 时,最优解也是 端点,(300,420)
2,定理若可行域有界,则 L.P,问题最优解总在 可行域端点 处
3,定理的意义 （ 单形法的依据 ） －－提供了求解
L.P,问题的一般思路 （ 迭代方法 ）,
将一般 L.P,模型化成标准型
利用初等变换求解约束之线性方程组：得到解交点
将解代入目标函数,比较它们的大小
（ 通过迭代 ） 直至求得最优的解 。
Ling Xueling
第三节 线性规划图解法：最小值例子一,问题及其数学模型
1,有关数据两种产品,A 或 B 两种成本,2 或 3 / 每单位两种所需工时,2 或 1 / 每单位
2,有关约束
1） 为了追求规模效应,生产总数不得少于 350 单位
2） 销售部门报告,A 产品已经获得 125 单位的订货
3） 共有 600 可用工时
3,问题：最小成本时两种产品的生产量？
（ 课堂练习建立模型 ）
Ling Xueling
第三节 线性规划图解法：最小值例子一,问题及其数学模型
4,数学模型
min z = min 2x1 + 3x2
s.t.
x1 + x2? 350
x1? 125
2x1 + x2? 600
x1,x2? 0
Ling Xueling
第三节 线性规划图解法：最小值例子二,图解法
1,可行域三交点分别是,( 250,350 ) ( 125,225 ) ( 250,100 )
2,o.f,图形表达分别令 z = 600,1200 得 ( 300,200 ) ( 600,400 )
3,最优解
x1 = 250 (>125) x2 = 100 o.f,= 800 。
Ling Xueling
第三节 线性规划图解法：最小值例子三,剩余变量和标准型注意：最优解中 x1 = 250 超过最小需求 125 单位
1,定义 (surplus)
L.P,问题中对应,?” 约束的过剩量称为 剩余,其所对应的变量成为剩余变量
2,标准型
min z = min 2x1 + 3x2 + 0s1 + 0s2 + 0s3
s.t.
x1 + x2 － s1 = 0
x1 － s2 = 0
2x1 + x2 ＋ s3 = 0
xi,si? 0
Ling Xueling
第四节 线性规划图解法中的特殊情况一,无穷多解
1,问题特征
o.f,直线与可行域某边界直线重合
2,例子设 Par,公司问题中,中档高尔夫球袋的单位利润降为 6.3
则 z = 6.3 x1 + 9 x2 与 C&D 直线重合
3,评价好事,多重组合－－多种生产方案,皆可作为决策方案,
认为：此时有条件追求其他的,满意,目标 。
Ling Xueling
第四节 线性规划图解法中的特殊情况二,无解
1,问题特征不可能同时满足所有约束
2,例子在原 Par,公司问题中,加上约束,x1 > 500,x2 > 360
3,处理
1） 既要指出现有资源的不可行性
2） 也要给出正确的行动方案,如：如何增加资源可以使得预订目标得以实现？ 本例中,各工序如果分别至少补充
（ 80,0,32,5）,即可使得最大化利润的目标得到实现 。
Ling Xueling
第四节 线性规划图解法中的特殊情况三,无限界解
1,问题特征在 求最大化问题时,遭遇 o.f,可以无限制地增加
2,例子
max 20x1 + 10x2
s.t.
x1 > 2
x2 < 5
x1,x2? 0
3,评价模型有问题 ！ 很可能是有些 约束 被冒险地删去或忽略了 。
Ling Xueling
The End of Chapter 2
