第二章 线性规划 运筹学讲义

A B
E
C
D
顶点:设C是凸集, X∈C;若X不能用不同的两点 X1∈C和 X2∈C的线性组合表示为X= αX1＋(1- α) X2 (其中0<α<1),则称X为C的一个顶点
定理1：若线性规划问题存在可行解,则问题的可行域是凸集。 定理2: 可行域有有限个顶点。
➢ 重要结论：
如果线性规划有最优解，则一定有一个可行域的顶点对 应一个最优解；最优解可在顶点达到,但不一定都是顶点
§2 图解法 画出可行域 满足约束的区域
(1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。 在直角坐标系里，图上任意一点的坐标代表了决策变量的 一组值，例1的每个约束条件都代表一个半平面。
x2 x2≥0
x2 x1≥0
x2=0
x1=0
x1
x1
（2）对每个不等式(约束条件)，先取其等式在坐标系中作 直线，然后确定不等式所决定的半平面。
第二章 线性规划问题与计算机求解
§1 问题的提出 §2 图解法 §3 单纯形法 §4 计算机求解
§1 问题的提出
例1(生产计划问题) 某工厂生产A、B两种产品，其成本决定于所用的材 料。已知单位产品所需材料量、材料日供应量及单价如表1-1所示。若 每生产A或B产品一个单位，所费工资同为30元，又A、B的每单位销售 价分别为120元和150元。问：工厂应如何安排生产，才能使所获总利 润最大？
得最优解：x1=50, x2=250, 这时z =27500。点A，B，C，D，O是可行 域的顶点，对有限个约束条件则其可行域的顶点也是有限
x2
AB C
z=27500=50x1+100x2
D E
x1
可行域的性质
1、凸集的概念： 定义:如果集合C中任意两个点X1, X2其连线上的所有点也都
是集合C中的点,称C为凸集. 由于X1, X2的连线可表示为: α X1+(1- α) X2(其中0<α<1) 因此,凸集用数学表示为:对任何X1 ∈C, X2 ∈C, 有α X1 ＋(1- α) X2 ∈C (其中0<α<1),则称道C为凸集。 规定：单点集 {x} 为凸集，空集为凸集。
x2=0
x2 2x1+x2=400
x2=250
x1+x2=300
x1=0
x1
图2-1
§2 图 解 法 确定等值线与梯度
（4）目标函数z =50x1+100x2，当z取某一固定值时得到一条直线，直线上 的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值 线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是 可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。
产品Ⅰ 产品Ⅱ 设备使用成本和单价 资源限制
设备
1
1
10元 / 时
300台时
原料A
2
1
12元 / kg
400kg
原料B
0
1
18元 / kg
250kg
销售单价(元)
84
140
单位产品利润(元) 50
100
问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？
设工厂生产产品A、B分别为x1，x2单位， 则线性规划模型：
线性规划可行域为一个凸集 （有界或无界）
进 一 步 讨 论 求极小化问题
例4 某公司由于生产需要，共需要A，B两种原料至少350 吨（A，B两种材料有一定替代性），其中A原料至少购进125 吨。但由于A，B两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需 要1小时，而公司总共有600个加工小时。又知道每吨A原料的 价格为2万元，每吨B原料的价格为3万元，试问在满足生产需 要的前提下，在公司加工能力的范围内，如何购买A，B两种 原料，使得购进成本最低？
解：目标函数： Min f = 2x1 + 3 x2 约束条件： s.t. x1 + x2 ≥ 350
x1 ≥ 125 2x1 + x2 ≤ 600 x1 , x2 ≥ 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。
x2
x1 =125
600
500
2x1+3x2 =1200
400
2x1+x2 =600
设目标函数为 Min f = c1x1 + c2x2 + … + cnxn
(可以)令 z ＝ -f ， 则该极小化问题与下面的极大化问题有相同的最优解，
即 Max z =－c1x1－c2x2 － …－cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们
最优解的目标函数值却相差一个符号，即 Min f ＝－Max z
数学模型
设工厂日产A、B产品分别为x1,x2单位 （决策变量）
产品A利润：120 –(1.00×6 + 2.30×4 + 14.60×3)(材料) – 30（工资） = 31 (元)
产品A利润：150 –(1.00×2 + 2.30×10 +14.60×5 )(材料) – 30（工资） = 22 (元)
相关数据
原料a 原料b 原料c
销售单价(元) 单位产品利润(元)
产品生产所需原材料
产品A
产品B
6
2
4
10
3
5
120
150
31
22
材料单价
1元 / kg 2.30元 / kg 14.60元 / kg
资源限制 日供给给量kg
180kg 400kg 210kg
产品A利润：120 – 1.00×6 + 2.30×4 + 14.60×3 （材料） – 30（工资） = 31 (元)
数约束称为确定需求的约束，它们表示了一定数量的确定 的需求，提供的数量等于要求的数量。网络配送问题的共 性就是它们的主要函数约束为一种特定形式的确定需求的 约束。
• 混合问题（mixed Problem）除以上三类以外的问题
• 建模过程
1.理解要解决的问题，了解解题的目标和条件；
2.定义决策变量（ x1 ，x2 ，… ，xn ），每一组值表示一个方 案； Decision variables 决策变量
300
200
x1+x2=300
100
100 200 300
x1+x2≤300
400
300
200
2x1+x2=400
100
2x1+x2≤400 100 200 300
（3）把五个图合并成一个图，取各约束条件的公共部分，如 图2-1所示。
x2=250
300
200
100
x2≤250
100 200 300
x2
z=10000=50x1+100x2
AB
250
C
z=27500=50x1+100x2 z=20000=50x1+100x2
z =0=50x1+100x2
D
E
200
x1
图2-2
z
§2 图解法 确定最优解
平行移动等值线，当移动到B点时，z在可行域内实现了最大化,B的坐
标为最优解。解方程组
x2= 250 x1+ x2=300
s =bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，s≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+s = bi 2） 当约束条件为： ai1 x1+ai2 x2+ … +ain xn ≥ bi 时 类似地令剩余变量 s =(ai1 x1+ai2 x2+ … +ain xn)－ bi ； s≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn－s = bi
无穷多个最优解。若将例1中的目标函数变为
max z=50x1+50x2，则线段BC上的所有点都代表了最优解； 无界解。即可行域的范围延伸到无穷远，目标函数值可
以无穷大或无穷小。一般来说，这说明模型有错，忽略 了一些必要的约束条件；
无可行解。若在例1的数学模型中再增加一个约束条件 4x1+3x2≥1200，则可行域为空域，不存在满足约束条件 的解，当然也就不存在最优解了。
8 x1 + 4x2 ≥ 20
3x1 + 6 x2 ≥18
x1 + 5x2 ≥ 16
x1 , x2 ≥ 0
线性规划问题主要类型
• 资源分配问题（resource-allocation）以符号表示的函数
约束称为资源约束，这些限制要求使用的资源必须小于等 于所能提供的资源的数量。资源分配问题的共性就是它们 的函数约束全部为资源约束。例1、2
3.用决策变量的函数形式写出目标函数，确定最大化或最小 化目标； Objective function 目标函数
4.用一组决策变量的线性等式或线性不等式表示解决问题过 程中必须遵循的约束条件; Constraints 约束
• 一般形式
目标函数： 约束条件：
Max （Min） z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1
a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0