运筹学第二章

1、第2次课2 学时本次课教学重点：线型规划模型有关概念、图解法求解线型规划模型本次课教学难点：线型规划模型有关概念、各种解的情况分析本次课教学内容：第二章 线性规划的图解法第一节问题的提出 一、引例例1.某工厂在计划期内要安排i、n两种产品的生产，已知生产单位产品所需的设备台时及a、b两种原材料的消耗、资源的限制，如下表：in资源限制设备11300台时原料a2:1400千克原料b01250千克单位产品获利50元100元问题：工厂应分别生产多少单位i、n产品才能使工厂获利最多?解：分析问题后可得数学模型：目标函数：maxz =50x1 100x2约束条件：stxi x2 3002x1 x2 400

2、x2 250x1 - 0, x2 - 0这是一个 线性规划模型，因为：目标函数是线性函数，约束条件是一些线性的等式或不等式。若目标函数是非线性函数，或约束条件中有非线性的等式或不等式，则这样的问题称为非线性规划。2、 一般建模过程1 .理解要解决的问题，了解解题的目标和条件；2 .定义决策变量(x1,x2,xn),每一组值表示一个方案；3 .用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4 .用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件3、 线性规划模型的一般形式目标函数：max (min )z =c1x1 c2x2 0nxn约束条件：staiixi ai2

3、x2 ainxn _(=,_)b1a2ixi a22x2a2nxn (=, _)b2 amixi - am2x2 - amnxn (二, )bm xi _ 0,x2 3 0, xn _ 0第二节图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法1、 有关概念1、可行解：满足约束条件的解2、可行域：全体可行解的集合。3、最优解：使得目标函数值达到最优的可行解。4、凸集5、松弛变量2、 图解法求解线性规划例 1. 目标函数： max z =50x1 +100x2约束条件：stx1 x2 - 3002xi x2 400

4、x2 250 xi - 0, x2 - 0 解：(1)分别取决策变量xi,x2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标 代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。面。(3)把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。xi+x2=300图2-1(4)目标函数z =50xi +100x2,当z取某一固定值时得到一条直线， 直线上的每一点都具有 相同的目标函数值，称之为 等值线”。平行移动等值线，当移动到 b点时，z在可行域内实现 了最大化。a, b, c, d, e是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。图2-2综上得到最

5、优解：x1 =50,x2 = 250最优目标值 z=27500三、线性规划问题解的情况1、如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；2、无穷多个最优解。若将例1中的目标函数变为 max z =50x1 +50x2，则线段bc上的所有点都代表了最优 解；3、无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；4、无可行解。若在例1的数学模型中再增加一个约束条件4x1 +3x2之1200,则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。例2.某公司由于生产需要，共需要a, b两种原料至少350吨（

6、a, b两种材料有一定替代性），其中a原料至少购进125吨。但由于a, b两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨 a原料需要2个小时，加工每吨 b原料需要1小时，而公司总共有 600 个加工小时。又知道每吨 a原料的价格为2万元，每吨b原料的价格为3万元，试问在满足生 产需要的前提下，在公司加工能力的范围内，如何购买a, b两种原料，使得购进成本最低？解:目标函数:约束条件:minst=2x1 3x2x1 x2 _ 3502x1x1x2 600_125x1_ 0,x2 _0采用图解法。如下图:x1二1256005002x1+3x2=12004002x1 +x2 =6003

7、002x1+3x2=9002001000 500600qj_1002003x1+x2=3502x1+3x2=800 lx1得q点坐标（250, 100）为最优解。教学组织1、课堂讲授2、多媒体图形演示作业布置：1、p23.2 （1,2）第3次课2 学时本次课教学重点：化标准型、灵敏度分析本次课教学难点：灵敏度分析本次课教学内容：第三节图解法的灵敏度分析、线性规划模型的标准形式目标函数：max（min ）z = gx c2x2 cnxn约束条件：s.taiixi - ai2x2 - anxn _（二,_）6a2ixi a22x2 a2nxn - （二,）b2amixi - am2x2 - amn

8、xn 0,这时新的约束条件成为aix+x/.（2）当约束条件为aiixi 钙2类似地令si = aiixiai2x2 ainxn -匕显然，si也具有非负约束，即si 0,这时新的约束条件成为ax+a2&+.士an%s = b3.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时， 如bw0,则把该等式约束两端同时乘以-1,得到：一 ai 一 a24 一.二.国片=-b为了使约束由不等式成为等式而引进的变量si，当不等式为“小于等于”时称为松弛变量”;当不等式为“大于等于”时称为剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个

9、约束引进不同的松弛变量。例：将以下线性规划问题转化为标准形式m i n f =2x1 -3x2 4x3约束条件：st3x1 4x2 -5x3 0解：首先，将目标函数转换成极大化：令 z = f = -2x1 +3x2 -4x3次考虑约束，有2个不等式约束，引进松弛变量 x4,x5 0o三个约束条件的右端值为负，在等式两边同时乘-1。通过以上变换，可以得到以下标准形式的线性规划问题：max z = -2x1 3x2 -4x3约束条件：st3xi 4x2 -5x3 x4=62x1x3- x5 = 8-x1 - x2 - x3=94.变量无符号限制的问题在标准形式中，必须每一个变量均有非负约束。当某

10、一个变量xj没有非负约束时，可以令xj= xj-为其中xj0,为0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于 不，和为”的大小。灵敏度分析灵敏度分析：建立数学模型和求得最优解后， 研究线性规划的一个或多个参数 （系数）cicu,变化时，对最优解产生的影响。1 .目标函数中的系数ci的灵敏度分析ci的变化只影响目标函数等值线的斜率，不影响可行域。考虑例1的情况，目标函数 z =50x1 +100x2在 z =x2 （x2=z斜率为0）到z=x1+x2（x1+x2=z斜率为 一1 ）之间时,原最优解xi =50,x2 =250仍是最优解。一般情况：z =c1x1 +c2x

11、2；写成斜截式x2 = 1x1 + c2c2目标函数等值线的斜率为，当 1m-色w0（*）时，原最优解仍是最优解。c2c2*）并整理得*）并整理得= 100, x2 = 200。（1假设产品n的利润100元不变，即c2 =100,代到式（ 0 c1 100假设产品i的利润 50元不变，即c1 =50，代到式（ 50 _ c2 二假若产品i、n的利润均改变，则可直接用式（*）来判断。假设产品i、n白利润分别为60元、55元，则6055那么，最优解为z -x1+ x2 和 z =2x1 +x2 的交点 x12 .约束条件中右边系数 bj的灵敏度分析当约束条件中右边系数 bj变化时，线性规划的可行域

12、发生变化，可能引起最优解的变化。考虑例1的情况：（1）假设设备台时增加10个台时，即b1变化为310,这时可行域扩大，最优解为x2 =250 和 x1 + x2=310 的交点 x1 =60,x2 = 250变化后的总利润 一变化前的总利润 =增加的利润（50x60+ 100 x250） （50 x 50+100 x 250） = 500 ,500/10 = 50 元说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。（2）假设原料 a增加10千克时，即 b2变化为410,这时可行域扩大，但最优解仍 为 x2 =250 和x1 +x2 =310的交点 x1 =60,x2 =250。此变化对总利润无影响， 该约束条件的禺价格为 0。解释：原最优解没有把原料a用尽，有50千克的剩余，因此增加