第2章 线性规划图解法2008

1、第1节 问题的提出1、线性规划的概念 由用线性变量所构建的线性目标函数和线性约束组成的数学模型，我们称之为线性规划。即所有变量都是一次的，目标函数和约束条件（方程或不等式）也是线性的。2、具体应用例子。例2.1 某工厂计划用现有的铜、铅两种资源生产甲、乙电缆，生产甲、乙两种电缆的单位售价及资源消耗如下表所示：甲电缆乙电缆资源量铜（吨）2110铅（吨）118价格（万元）64另外，市场对乙电缆的最大需求量为7单位，而对甲乙电缆的需求量无限制。问该工厂应如何安排生产才能使工厂的总收入最大？一、线性数学模型的建立：2146maxxxz101221 xx821 xx0,21xxs.t.72xObject

2、：解：设x1，x2分别代表甲乙两种电缆的生产量，z代表工厂的总收入，则上述问题可用如下数学模型来表示：LP的基本概念的基本概念目标函数中的变量系数用目标函数中的变量系数用Cj表示表示,Cj称为价称为价值系数值系数;约束条件的变量系数用约束条件的变量系数用aij表示表示,aij称称为工艺系数为工艺系数;约束条件右端的常数用约束条件右端的常数用bi表表示示,bj称为资源限量称为资源限量(系数系数)2146maxxxz101221 xx821 xx0,21xx约束条件(subject to)72x目标Object：指出模型中的可行解基本概念基本概念:1、什么是可行解、什么是可行解?2、什么是最优解、

3、什么是最优解?二、线性规划模型的求解二、线性规划模型的求解(方法方法)：1、图解法；、图解法；2、单纯形法（时代标志）；、单纯形法（时代标志）；3、计算机软件求解。、计算机软件求解。第2节 图解法 条件：只有两个变量的线性规划问题 理解: X1,x2代表两个数轴： 目标函数：是一条直线（视Z为常量） 约束条件：是等式或不等式，代表直线或直线的上方或下方；x1x207条件约束图示条件约束图示: :x1x25100788图示图示: :101221 xx821 xx0,21xxs.t.72x可行域x1x25100788可行域最优解101221 xx821 xx0,21xxs.t.72xx1x2目标函

4、数等值线可行域最优解66-84图解法例3：x1x22004000250300最优解300（z=27500=50 x1+100 x2) X1=50,x2=25050练习题：教材P24 第1题Global optimal solution found. Objective value: 9.857143 Total solver iterations: 2 Variable Value Reduced Cost X1 1.714286 0.000000 X2 2.142857 0.000000 Row Slack or Surplus Dual Price 1 9.857143 1.000000

5、2 0.000000 1.285714 3 0.000000 0.1428571LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 9.857142 VARIABLE VALUE REDUCED COST X1 1.714286 0.000000 X2 2.142857 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1.285714 3) 0.000000 0.142857 NO. ITERATIONS= 2 RANGES IN WHICH THE BASIS IS UNCH

6、ANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 2.000000 3.000000 0.500000 X2 3.000000 1.000000 1.800000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 6.000000 4.000000 3.000000 3 15.000000 14.999999 6.000000约束条件资源量使用量剩余数量铜

7、（吨）10100铅（吨）880市场量761 在线性规划中，对于一个约束条件中没有使用的资源或能力的大小称之为松驰量。在不等式中添加一个变量Si ，则原约束条件变为：求解结果：X1=2，X2=6，1012121sxx8221sxx0,21xxs.t.732sx3212100046maxsssxxz目标函数：1012121sxx8221sxx0,21xxs.t.732sx3212100046maxsssxxz目标函数：于是，重新得到一个数学模型：上述过程，称为线性规划的标准化过程，其模型被称为线性规划的标准模型。线性规划的标准型规定为：0;, 2 , 1, 0max2211222221211121

8、21112211iimnmnmmnnnnnnbnixbxaxaxabxaxaxabxaxaxaxcxcxcz目标函数：目标函数：约束条件约束条件线性规划标准型 1.目标函数求最大值(也有的教材规定为求最小) 2.约束条件均为等式方程; 3.变量Xi为非负; 4.常数bj都大于或等于零. 原模型：标准化模型： 线性规划的标准化过程中还有没有其它问题要处理？101221 xx821 xx0,21xxs.t.72x1、若碰到0的约束条件该如何标准化？2、Min问题。 在第i个约束条件为型，在不等式的左边减去一个非负的变量Si,称为剩余变量；同时令相应的Ci,=0。结果如下：1012121sxx822

9、1sxx0,32121sssxxs.t.732sx对于对于Min问题，问题，只需要将系数由正号（+）变为负（-）即要。转化过程 对约束条件进行处理： 1、对=的减去一个非负变量sJ 使之左右相等； 减去的变量称为剩余量(surplus variable ) 加上的变量称为松弛量(slack variable ) 3、对目标函数:加系数0处理Si量101221 xx821 xx0,21xxs.t.72x2134minxxz目标函数：2134maxxxz101221 xx821 xx0,21xxs.t.72x之前之后2134maxxxz101221 xx821 xx0,21xxs.t.72x之后2

10、134maxxxz1011221sxx8221sxx03, 2, 10,21sssxxs.t.732sx练习：线性规划模型的标准化 P25 第3题，极点凸集不是凸集凸集 x2 50403020101020 3040 x1 x2 50403020101020 3040 x1 Q1（25，0） Q2（15，20） x2 50403020101020 3040 x1 (d)可行域无界可行域无界 (e)可行域无界可行域无界 (f)可行域为空集可行域为空集 多个最优解多个最优解 目标函数无界目标函数无界 无可行解无可行解 (a)可行域有界可行域有界 (b)可行域有界可行域有界 (c)可行域无界可行域无界

11、 唯一最优解唯一最优解 多个最优解多个最优解 唯一最优解唯一最优解第3节 图解法的灵敏度分析 一、线性规划的标准化0;,2, 1,0),(),(),(minmax2211222221211121211122112211iimnmnmmnnnnnnnnbnixbxaxaxabxaxaxabxaxaxaxcxcxczxcxcxcz或目标函数：目标函数：约束条件约束条件线性规划的标准型规定为：0;, 2 , 1, 0max221122222121112121112211iimnmnmmnnnnnnbnixbxaxaxabxaxaxabxaxaxaxcxcxcz目标函数：目标函数：约束条件约束条件二、

12、灵敏度分析1、什么是灵敏度分析？先看例子:2、如何进行灵敏度分析？例2.1 某工厂计划用现有的铜、铅两种资源生产甲、乙电缆，生产甲、乙两种电缆的单位售价及资源消耗如下表所示：甲电缆甲电缆乙电缆乙电缆资源量资源量铜（吨）铜（吨）2110铅（吨）铅（吨）118价格（价格（万元万元）64另外，市场对乙电缆的最大需求量为7单位，而对甲乙电缆的需求量无限制。问该工厂应如何安排生产才能使工厂的总收入最大？求解结果:X1=2 ,X2=6,Z=36:X1=2 ,X2=6,Z=36万元万元 生产甲生产甲, ,乙电缆乙电缆2 2个单位个单位,6,6个单位个单位, ,获最大收入获最大收入3636万元万元. .问题问

13、题: :甲的价格由甲的价格由6 6万元降为万元降为5 5万元万元, ,生产方案还是最优吗生产方案还是最优吗? ?怎么解决?(1)重新计算;(2)另想简单办法?二、灵敏度分析1、什么是灵敏度分析？ 在实际工作中，我们往往已经求得了最优解，可是有时，模型中的某个系数或若干个系会发生变化，如原材料的购买单价由原来的50元上涨到为60元，那么，生产安排的最优方案是否还是最优？值得重新考虑？ 线性规划模型中系数的变化，引起最优解的变化，属于灵敏度分析的研究范围。 定义：在建立数学模型和求得最优解之后，研究线性规划的一引起系数 变化时，对最优解产生什么影响？（最优解是否会改变？）2、如何进行灵敏度分析？j

14、ijibac,2、如何进行灵敏度分析？（1）目标函数中的系数 的灵敏度分析 当 改变时， Z会如何改变？ 先看例子：二、灵敏度分析icicAB资源限制设备11300台时原料A21400千克原料B01250千克获利（元）50100问该工厂应如何安排生产才能使工厂的总收入最大？图解法例3：x1x22004000200300最优解(50,250)300当X1=50,x2=250时, MAX Z=50 x1+100 x2=27500 当产品A或B的价格系数发生变化时，增加或减少时，是大利润将发生变化，也就将改变最优解。我们现在就要求出系数的最大变化范围。Ci改变时，Z不变。图解法例3：x1x22004

15、000200300300直线F：直线E 从图中可知，直线F的斜率K=0 直线E的斜率K=-1 而目标函数: z=C1x1+c2x2 的斜率k=-C1/C2 那么，当 -1 -c1/c2 0时顶点B仍然是最优解图解法例3：x1x22004000200300最优解300（z=27500=50 x1+100 x2) X1=50,x2=250图解法例3：x1x22004000200300300目标函数斜率:K=-c1/c221cck0121cck条件条件: :图解法例3：1005050221ccck0121cck条件条件: :x1x2先来固定C2=100,让C1变化,讨论C1的变化范围,使得Z不变.0

16、10011ck10001 c05012ck只要C2=100, C1在0和100之间变化,那么工厂生产获取最大利润的方案将不变.即仍然是X1=50,X2=250,即生产量不变，但获取的利润可能会变（因为产品的单价变了）。假设C2=100不变，C1=70上涨20元，则当生产方案不变时，工厂获利变为：50X70+100X250=3500+25000=28500，比原来多1000250c 当C1和C2同时变化时，则可通过不等式：0121cck来判断原最优解是否仍然最优。如：C1=60，C2=55，-C1/C2=-60/55=-1.09要重新求解.三、约束条件中右边系数bj的灵敏度分析 讨论bj的变化范围，使得Z最优解不变。 由于bj的变化，使得可行域发生变化，变大或缩小；生产设备台时增加10小时x1x2ABCDOBCB点（点（60，250）最大利润为：最大利润为：Z=50X60+100X250=28000 由于新增10台时，增加了500元利润，故在300台时的基础上，每增加1台时可增加500/10=50元的利润，这个增加量被称为该约束条件的对偶价格（简称为对偶价格）。 现修改另一个右边系数B2：x1