第三章 线性规划
数据、模型与决策 (第二版)
3.2.1 图解法的过程介绍
• 花瓶问题
• • • • • 目标函数 材料约束 时间约束 储存约束 非负约束 max z =12B+10S 2B+S≤160 （1） 1/3B+1/3S≤40 （2） 3B+2S≤260 （3） B≥0, S≥0
第三章 线性规划
第三章 线性规划 数据、模型与决策 (第二版)
第三章 线性规划
• 3.1 线性规划问题概述 • 3.2 线性规划问题的图解法 • 3.3 单纯形法 • 3.4 对偶问题 • 3.5 敏感性分析
第三章 线性规划
数据、模型与决策 (第二版)
3.1 线性规划问题概述
• 3.1.1 线性规划问题中的主要概念 • 3.1.2 线性规划问题的数学模型
第三章 线性规划
数据、模型与决策 (第二版)
3.1.1 线性规划问题中的主要
概念
• 目标（objective）: 所要达到的最优结果（最大或最 小）。 • 约束条件（constraints）：对所能产生结果的限制。
• 线性规划：一种解决带有约束条件的最优化问题的方 法。 • 解决线性规划问题的步骤
第三章 线性规划 数据、模型与决策 (第二版)
线性规划问题的数学模型
工序 花瓶种类 占用材料 （OZ） 2 1 160 艺术加工 （小时） 1/3 1/3 40 储存空间 （一单位） 3 2 260 利润值 （元） 12 10 ——
大花瓶 小花瓶 每周可用能力
B表示大花瓶每周生产的数量，S表示小花瓶每周生产的数量。
第二篇 规划和优化模型
第三章 线性规划
数据、模型与决策 (第二版)
第三章 线性规划
第三章 线性规划
数据、模型与决策 (第二版)
学习目的
线性规划是运筹学的一个重要分支。通 过对本章的学习要求：
• 能够掌握线性规划问题中的主要概念 • 能够掌握线性规划问题中的线性规划的标准形式 • 能够掌握线性规划问题的求解方法——图解法及单纯 形法 • 理解线性规划问题解的概念和基本定理 • 了解线性规划问题的敏感性分析以及善于建立线性规 划模型来解决一些实际问题。
第三章 线性规划 数据、模型与决策 (第二版)
约束条件 • 2B+S≤160 • 1/3B+1/3S≤40 • 3B+2S≤260 • B≥0, S≥0 目标函数： • max z =12B+10S
第三章 线性规划 数据、模型与决策 (第二版)
数学模型表述如下 • 目标函数 max z =12B+10S • 材料约束 2B+S≤160 • 时间约束 1/3B+1/3S≤40 • 储存约束 3B+2S≤260 • 非负约束 B≥0, S≥0
第三章 线性规划
数据、模型与决策 (第二版)
约束条件：
• 各项目投资总和为1,000,000元 x1 + x2 + x3 + x4+ x5 = 1,000,000 • 所得红利最少为80,000元 0.05 x1 + 0.08 x2 + 0.07 x3 + 0.06 x4+ 0.1 x5≥ 80,000 • 增加额不低于140,000元 1x1 + 0.17 x2 + 0.14 x3 + 0.22 x4+0.7 x5≥140,000 • 平均信用度不低于6 (11 x1 + 8 x2 + 10 x3 + 4 x4+10 x5)/5≥6 • 非负约束 xi ≥ 0 ( i =1,2,3,4,5)
航空业的成本控制
• 那时，联行在其11个航班订票处，有超过4，000名的机场销售代 表和支持人员。在十个最大的机场大约有一千名顾客服务代表， 有些时兼职的，每班2到8个小时不等，大部分是全职的，每班8现 实或10小时，有许多个不同的上班时间。每个订票处都有一天24 小时营业（通过电话订票。然而，每个地点提供所需水平服务的 雇员数量在一天24小时种的变化很大，或许美国半个小时就会有 很大的变化。 • 为了更有效率的满足服务要求，在每个地点为所有工作人员设计 动作排成，是一个组合的梦魇。一旦一名雇员上了班，就会工作 一个班次，只有就餐和每个两个小时的短暂的休息时间，给定24 小时的一天中每半个小时各的服务所需的最小雇员数，在七天一 周中，24小时一天中每个班次需要多少雇员并且合适上班呢？ • 幸运的是，线性规划能解决这些组合梦魇问题。据有形估计，建 立在线性规划基础上的计算机规划系统每年为联合航空公司在直 接薪酬和津贴成本上节省了600万美元，得到的其他好处包括改善 第三章 线性规划 数据、模型与决策 (第二版) 客户服务以及降低雇员的工作负担。
第三章 线性规划 数据、模型与决策 (第二版)
• 实例分析：
• 某石油公司利用三种有生产两种混合原料。每种油的 成本和每天的可用量如下表所示：
油 A B C
燃料1 燃料2 第三章 线性规划 A：最多占25% A：最少占20%
成本（元/升） 8 10 12
B：最少占30% B：最多占50%
可用量（升） 10,000 15,000 20,000
第三章 线性规划
数据、模型与决策 (第二版)
• • • • • • • •
而三种油的成本为： 8×(A1+A2)+10×(B1+ B2)+12×(C1+ C2 ) 利润是销售收入和成本之差，作为目标函数可以表示如下： max z =22×A1+27 A2 +20 B1+25B2+18 C1+23 C2 三种可用的原料油的约束为： A1+A2≤10,000 B1+ B2≤15,000 C1+ C2≤20,000
第三章 线性规划 数据、模型与决策 (第二版)

3.2.2规划问题求解的几种可
能结果
• 无穷多最优解 • 无界解 • 无解或者无可行解
第三章 线性规划
数据、模型与决策 (第二版)
3.2.3图解法延伸
• 图解法的解体方法和几何判断对于求解 一般的线性规划问题有很大启发：
• 1、性规划问题的解的情况有以下几种：唯一最优解；无穷多最优 解；无界解；无可行解。 • 2、线性规划问题有解，那么可行域是凸集。 • 3、规划问题优解存在，那么唯一最优解一定是可行域凸集的某个 顶点；无穷最优解一定是可行域的某个边或某个面。 • 4、规划问题的一般解体思路：先找出凸集的任一顶点，计算该点 处目标函数值，与周围相邻顶点处的目标函数值相比较，如果该 点值最大，那么该点就是最优解或者最优解之一；如果不是，那 么就对目标函数值比该点大的另一点重复此过程，直到找出最优 解。
第三章 线性规划
数据、模型与决策 (第二版)
图解法的步骤：
• 其中一个变量作为横坐标轴，另一个变量作为纵坐标轴，画出平 面直角坐标系，并适当选取单位坐标长度，由于变量是非负的， 因此，画出坐标系的第一象限即可。 • 出各约束条件在坐标轴上对应的直线，找出可行域（常用阴影区 域标识）。 • 图标目标函数，z是一个待求的目标函数值。目标函数常用一组平 行虚线表示，离坐标原点越远的虚线表示的目标函数值越大。 • 确定最优解。因为最优解是可行域中使目标函数值达到最优的点， 当目标函数直线由原点开始向右上方移动时，z值开始增大，一直 移到目标函数直线与可行域相切时为止，切点就是最优解的点。
第三章 线性规划
数据、模型与决策 (第二版)
第三章 线性规划
• • • • • • • • • • • •
各种原料油所占比例的六个约束： A1≤0.25×(A1+B1+C1) B1≥0.3×(A1+B1+C1) C1≤0.4×(A1+B1+C1) A2≥0.2×(A2+B2+C2) B2≤0.5×(A2+B2+C2) C2≥0.3×(A2+B2+C2) 长期供货合同约束： A1+B1+C1≥10,000 A2+B2+C2≥10,000 非负约束： Ai，Bi，Ci≥0 (i=1,2)
数据、模型与决策 (第二版)
直线把图分为两部分，直线上方的点都不符合约束条件， 而直线上和直线下方的点都满足约束条件。
第三章 线性规划 数据、模型与决策 (第二版)
最优解为： • B=20, S=100 将B和S值代入目标函数中得： • Z=12×20+10×100=1240 所以最大利润值是1240。
数据、模型与决策 (第二版)
第三章 线性规划
• 3.1 线性规划问题概述 • 3.2 线性规划问题的图解法 • 3.3 单纯形法 • 3.4 对偶问题 • 3.5 敏感性分析
第三章 线性规划
数据、模型与决策 (第二版)
3.2线性规划问题的图解法
• 3.2.1 图解法的过程介绍 • 3.2.2 规划问题求解的几种可能结果 • 3.2.3 图解法延伸
3
4
18
12
7
6
14
22
10
4
5
第三章 线性规划
4
10
数据、模型与决策 (第二版)
7
10
• A集团的目标为：投资风险最小，每年红 利至少是80,000元，最低平均增长率14%， 最低平均信用度为6，请用线性规划方法 描述该问题。
第三章 线性规划
数据、模型与决策 (第二版)
• 决策变量为个项目的投资数额，设为xi ( i =1,2,3,4,5) • 目标函数： min z = ( 0.1x1 + 0.06x2 +0.18x3 + 0.12x4+ 0.04x5 )