管理运筹学第二章 线性规划的图解法

B、约束条件不是等式的问题：
若约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量si ，使它等于约束右 边与左边之差 si=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，si 也具有非负约束，即si≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+si = bi
第二章 线性规划 的图解法
一、线性规划的概念 二、线性规划问题的提出 三、线性规划的数学模型 四、线性规划的图解法 五、线性规划解的情况 六、LP图解法的灵敏度分析
一、线性规划的概念
线性规划Linear Programming 简称LP，是一 种解决在线性约束条件下追求最大或最小的 线性目标函数的方法。 线性规划的目标和约束条件都可以表示成线 性的式子。
max z 3 x1 2 x2
2 x1 x2 ≤ 10 设备B台时占用 s.t. x1 x2 ≤ 8 x , x ≥ 0 产量非负 1 2
决策变量 （decision variable） 目标函数 （objective function） 约束条件 （subject to）

-ai1
x1-ai2 x2- … -ain xn = -bi 。
例1.3：将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 ≤15.7 4.1 x1 + 3.3 x3 ≥8.9 x1 + x2 + x3 = 38 x 1 , x 2 , x3 ≥ 0


解：首先，将目标函数转换成极大化：


令 z= -f = -3.6 x1+5.2 x2-1.8 x3
其次考虑约束，有2个不等式约束，引进松弛变量 x4 ， x5≥0。 于是，我们可以得到以下标准形式的线性规划问 题：
Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 s.t. 2.3 x1 +5.2 x2 -6.1 x3 + x4 = 15.7 4.1 x1 +3.3 x3 – x5 = 8.9 x1 + x2 + x3 = 38 x1 , x2, x3 , x4 ,x5 ≥ 0

数学模型： Max s = 3x1＋5x2＋4x3



s.t. 2x1＋3x2＋0x3≤ 1500
0x1＋2x2＋4x3≤800 3x1＋2x2＋5x3≤2000 x1 ，x2 ，x3 ≥0


从前面两个例子中可以看出一般线性规划问题 的建模过程： A、理解要解决的问题，明确在什么条件下， 要追求什么目标； B、定义决策变量； C、用决策变量的线性函数形式写出所要追求 的目标，即目标函数,按问题的不同，要求目 标函数实现最大化和最小化； D、用一组决策变量的等式或不等式来表示在 解决问题过程中所必须遵循的约束条件。
对最优解x1＝50，x2＝250来说，各松弛变量 的值如下表所示：
约束条件 设备台时数 原料A 松弛变量的值 S1=0 S2=50
原料B
S3=0

X2 400
松弛变量的值也可以从图 解法中获得一些信息： S1=0 S2>0 S3=0

最优解： x1＝50 x2＝250
x2＝250
300
200

2、线性规划模型的标准型：
max z = c1 x1 + c2 x2 + + cn xn
a11 x1 + a12 x2 + + a1n xn = b1 ( 0)

s.t.
am1 x1 + am2 x2 + + amn xn = bm ( 0)
x1 ≥0， x2 ≥0，…， xn ≥0

（注：其中z＝-f， x2 ’ =- x2 ， x3’－ x3’ ’ ＝ x3 ）
四、线性规划的图解法

对于只有两个决策变量的线性规划问题，可 以在二维直角坐标平面上作图表示线性规划 问题的有关概念，并求解。

例1.5 某工厂在计划期内要安排Ⅰ，Ⅱ两种产品的 生产，生产单位产品所需的设备台时及A、B两种原 材料的消耗以及资源的限制如表所示： 产品 设备 原料A 原料B Ⅰ 1 2 0 Ⅱ 1 1 1 资源限制 300台时 400kg 250kg
当约束条件为
ai1 x1+ai2 x2+ … +ain xn ≥ bi时，类似地令 si= (ai1 x1 + ai2 x2 + … + ain xn ) –bi 显然，si也满足非负约束，即si≥0，这时新 的约束条件成为 ai1 x1+ai2 x2+ … +ain xn-s = bi
注意： 不同的约束不等式引入的变量也不同； 一般称≤不等式中引入的变量为松弛变量，称 ≥不等式中引入的变量为剩余变量。
100
O
100
200
300 x1+x2＝300
X1
2x1+x2＝400
剩余变量的值和意义

请大家下去后阅读教材15－17页例2
课堂练习：图解法求解以下LP问题
目标函数 Max z = 2500x1 + 1500x2
约束条件 s.t. 3x1+2x2≤ 65 2x1+x2≤ 40 3x2≤ 75 x1 ,x2 ≥0
等值线
100 200 300 X1
O
故原问题最优解为： x1＝50，x2＝250 最优值为27500。

图解法求解线性规划问题的步骤：
1、建立直角坐标系。 2、画出可行域。 3、作目标函数的等值线 4、找出最优解（切点即为最优解，找出切 点坐标，并代入目标函数求得最优值）。

X2 400

4、变量非负限制
x1 ,x2 ≥0

线性规划模型：

Max s =50x1+30x2 s.t. 4x1+3x2≤ 120 2x1+x2≤ 50 x1 ,x2 ≥0

承导入案例
产品甲 产品乙 生产能力 2 1 10 设备A 1 1 8 设备B 3 2 单位利润
设两种产品产量为x1,x2,则有: 最大化 设备A台时占用 三要素 总利润表达式 生产能力,不 允许超过
标准形式的特点： A、目标函数为Max形式 B、约束全为＝式 C、所有决策变量xj ≥0，j＝ 1，2，3，… n D、所有bi≥0，i＝1，2，3，…… m

3、如何将一般LP问题化为标准形
式
A、极小化目标函数问题转化为极大化目标 函数问题： 若目标函数为： Min f = c1x1 + c2x2 + … + cnxn 则可令z ＝ -f ，原目标等同于： Max z = -c1x1 - c2x2 - … - cnxn 但须注意, f* ＝ – z*
三、线性规划的数学模型

1、LP模型的一形式 目标函数： Max(Min)z = c1x1 + c2x2 + … + cnxn
•约束条件： a11x1+a12x2+…+a1nxn≤( =, ≥ )b1 a21x1+a22x2+…+a2nxn≤( =, ≥ )b2 . . . am1x1+am2x2 +…+amnxn≤( =, ≥ )bm x1 ，x2 ，… ，xn ≥ ( ≤) 0 或无约束

例1.4 将以下线性规划问题转化为标准形式 min f = x1 +2 x2 + 3 x3 s. t. x1 - x2 + x3 ≤4 x1 +2 x3 ≥8 x1 + x 2 + x 3 ≥ 2 x1 ≥ 0, x2 ≤0

答案：标准型为 maxz = -x1 +2 x2’- 3 x3’+ 3 x3’ ’ s. t. x1 + x2’ + x3’－ x3’ ’ +s1=4 x1 +2 x3’－2 x3’ ’ –s2＝8 x1 - x2 ’ + x3’－ x3’ ’ –s3 ＝ 2 x1 ， x2’ ， x3’， x3’ ’ ， s1 ，s2 ，s3 ≥ 0

工厂每生产一单位产品Ⅰ可以获利50元，每生产一 单位产品Ⅱ可获利100元，问工厂应分别生产多少 单位产品Ⅰ和产品Ⅱ才能使获利最多？
问题的线性规划模型： 目标函数：max z= 50x1+100 x2 约束条件：x1+x2≤300 2x1+x2≤400 x2≤250 x1 ≥0， x2 ≥0


C、变量符号限制的问题：
当某一个变量xj ≤0时，可以令 xj = -xj’ 则xj’≥0

当某一个变量xj没有非负约束时，可以令 xj = xj’- xj” 其中 xj’≥0，xj”≥0

D、右端项有负值的问题： 如 bi<0，则把该等式约束两端同时乘以-1， 得到：

二、线性规划问题的提出
例1.1、胜利家具厂生产桌子和椅子两种家具，桌子售价50 元/张，椅子售价30元/张。生产一张桌子需要木工4h，油漆 工2h，生产一张椅子需要木工3h，油漆工1h。该厂每月可用 木工工时120h，油漆工工时50h。问该厂每月生产多少张桌 子和椅子才能使每月的销售收入最大？ 解： 1、确定决策变量 x1、x2——每月生产桌子、椅子的数量； 2、确定目标函数——销售收入最大 Max s =50x1+30x2 3、确定约束条件 s.t. 4x1+3x2≤ 120 2x1+x2≤ 50
线性规划中解的概念
最优解： x1＝50 x2＝250
300
非可行解： x1＝200 x2＝300
x2＝250
200
可行域
100
可行解： x1＝100 x2＝100
O
100
200
300 x1+x2＝300
X1
2x1+x2＝400
线性规划中几个的概念



1、解：决策变量的任意一组取值； 2、可行解：满足约束条件（包括非负条件）的一 组决策变量值，称可行解； 3、可行域：所有可行解的集合； 4、最优解：使目标函数值最优（即使最大化目标 函数值最大，使最小化目标函数最小）的可行解； 5、最优值：最优解对应的目标函数值。
原料可用量 （公斤/日）
2 0
3 2
0 4
1500 800
原料P3
单位产品的利润（千元）
3
3
2
5
5
4
2000
决策变量：每天生产三种产品的数量，分别 设为x1，x2，x3； 目标：每天的生产利润最大 目标函数为Max s ＝3x1＋5x2＋4x3 约束条件：每天原料的需求量不超过可用量 原料P1 ： 2x1＋3x2＋0x3≤ 1500 原料P2 ： 0x1＋2x2＋4x3≤800 原料P3 ： 3x1＋2x2＋5x3≤2000 隐含约束：产量为非负数x1 ，x2 ，x3 ≥0
松弛变量的值和意义
例1.5的线性规划模型化为标准型： 目标函数：max z= 50x1+100 x2 约束条件：x1+x2+s1＝300 2x1+x2+s2＝400 x2+s3＝250 x1,x2,s1,s2,s3≥0

引入的松弛变量常常表示未被充分利用的资 源条件。
松弛变量的值和意义


X2 400
第一步：确定可行域
可行域
300 x2＝250 200
100
O
100
200
300 x1+x2＝300
X1
2x1+x2＝400

X2
第二步：作目标函数等值线， 确定使目标函数最优的点
等值线法线
最优值
400 Z＝27500 300 (50,250) 200 Z＝10000
最优解
z＝0
100
xj为待定的决策变量； cj为目标函数系数，或价值系数、费用系数； aij为技术系数； bj为资源常数，简称右端项； 其中i＝1，2，…m； j＝1，2，…n

可以看出，一般LP模型的特点： A、决策变量x1，x2，x3，……xn表示要寻求 的方案，每一组值就是一个方案； B、约束条件是用等式或不等式表述的限制 条件； C、一定有一个追求目标，或希望最大或希 望最小； D、所有函数都是线性的。
当目标函数与约束条件均为决策变 量的线性函数，且变量取连续值时， 称为线性规划LP；变量取整称为整 数线性规划ILP；变量取二进制为 0-1规划BLP。
例1.2 某工厂用三种原料生产三种产品，已知的条件 如下表所示，试制订总利润最大的生产计划
单位产品所需原料数量 （公斤） 原料P1 原料P2 产品Q1 产品Q2 产品Q3