《第二章 线性规划的图解法》由会员分享，可在线阅读，更多相关《第二章 线性规划的图解法（67页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性规划的图解法,一、线性规划的概念 二、线性规划问题的提出 三、线性规划的数学模型 四、线性规划的图解法 五、线性规划解的情况 六、LP图解法的灵敏度分析,一、线性规划的概念,线性规划Linear Programming 简称LP，是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。 线性规划的目标和约束条件都可以表示成线性的式子。,例1.1、胜利家具厂生产桌子和椅子两种家具，桌子售价50元/张，椅子售价30元/张。生产一张桌子需要木工4h，油漆工2h，生产一张椅子需要木工3h，油漆工1h。该厂每月可用木工工时120h，油漆工工时50h。问该厂每月生产多少张桌子和椅子才能使
2、每月的销售收入最大？ 解： 1、确定决策变量 x1、x2每月生产桌子、椅子的数量； 2、确定目标函数销售收入最大 Max s =50x1+30x2 3、确定约束条件 s.t. 4x1+3x2 120 2x1+x2 50 4、变量非负限制 x1 ,x2 0,二、线性规划问题的提出,线性规划模型： Max s =50x1+30x2 s.t. 4x1+3x2 120 2x1+x2 50 x1 ,x2 0,承导入案例,设两种产品产量为x1,x2,则有:,决策变量 （decision variable）,目标函数 （objective function）,约束条件 （subject to）,当目标函数与
3、约束条件均为决策变量的线性函数，且变量取连续值时，称为线性规划LP；变量取整称为整数线性规划ILP；变量取二进制为0-1规划BLP。,例1.2 某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生产计划,决策变量：每天生产三种产品的数量，分别设为x1，x2，x3； 目标：每天的生产利润最大 目标函数为Max s 3x15x24x3 约束条件：每天原料的需求量不超过可用量 原料P1 ： 2x13x20x3 1500 原料P2 ： 0x12x24x3800 原料P3 ： 3x12x25x32000 隐含约束：产量为非负数x1 ，x2 ，x3 0,数学模型： Max s = 3x
4、15x24x3 s.t. 2x13x20x3 1500 0x12x24x3800 3x12x25x32000 x1 ，x2 ，x3 0,从前面两个例子中可以看出一般线性规划问题的建模过程： A、理解要解决的问题，明确在什么条件下，要追求什么目标； B、定义决策变量； C、用决策变量的线性函数形式写出所要追求的目标，即目标函数,按问题的不同，要求目标函数实现最大化和最小化； D、用一组决策变量的等式或不等式来表示在解决问题过程中所必须遵循的约束条件。,1、LP模型的一般形式,目标函数： Max(Min)z = c1x1 + c2x2 + + cnxn,约束条件： a11x1+a12x2+a1nx
5、n( =, )b1 a21x1+a22x2+a2nxn( =, )b2 . . . am1x1+am2x2 +amnxn( =, )bm x1 ，x2 ， ，xn ( ) 0 或无约束,三、线性规划的数学模型,xj为待定的决策变量； cj为目标函数系数，或价值系数、费用系数； aij为技术系数； bj为资源常数，简称右端项； 其中i1，2，m； j1，2，n,可以看出，一般LP模型的特点： A、决策变量x1，x2，x3，xn表示要寻求的方案，每一组值就是一个方案； B、约束条件是用等式或不等式表述的限制条件； C、一定有一个追求目标，或希望最大或希望最小； D、所有函数都是线性的。,2、线性规
6、划模型的标准型：,x1 0， x2 0， xn 0,s.t.,标准形式的特点： A、目标函数为Max形式 B、约束全为式 C、所有决策变量xj 0，j 1，2，3， n D、所有bi0，i1，2，3， m,3、如何将一般LP问题化为标准形式 A、极小化目标函数问题转化为极大化目标函数问题： 若目标函数为： Min f = c1x1 + c2x2 + + cnxn 则可令z -f ，原目标等同于： Max z = -c1x1 - c2x2 - - cnxn 但须注意, f* z*,B、约束条件不是等式的问题： 若约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量
7、si ，使它等于约束右边与左边之差 si=bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，si 也具有非负约束，即si0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+si = bi,当约束条件为 ai1 x1+ai2 x2+ +ain xn bi时，类似地令 si= (ai1 x1 + ai2 x2 + + ain xn ) bi 显然，si也满足非负约束，即si0，这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi,注意： 不同的约束不等式引入的变量也不同； 一般称不等式中引入的变量为松弛变量，称不等式中引入的变量
8、为剩余变量。,C、变量符号限制的问题： 当某一个变量xj 0时，可以令 xj = -xj 则xj0 当某一个变量xj没有非负约束时，可以令 xj = xj- xj” 其中 xj0，xj”0,D、右端项有负值的问题： 如 bi0，则把该等式约束两端同时乘以-1，得到： -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 x1 ,
9、x2 , x3 0,解：首先，将目标函数转换成极大化： 令 z= -f = -3.6 x1+5.2 x2-1.8 x3 其次考虑约束，有2个不等式约束，引进松弛变量x4 ， x50。 于是，我们可以得到以下标准形式的线性规划问题： 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,例1.4 将以下线性规划问题转化为标准形式 min f = x1 +2 x2 + 3 x
10、3 s. t. x1 - x2 + x3 4 x1 +2 x3 8 x1 + x2 + x3 2 x1 0, x2 0,答案：标准型为 maxz = -x1 +2 x2- 3 x3+ 3 x3 s. t. x1 + x2 + x3 x3 +s1=4 x1 +2 x32 x3 s28 x1 - x2 + x3 x3 s3 2 x1 ， x2 ， x3， x3 ， s1 ，s2 ，s3 0 （注：其中z-f， x2 =- x2 ， x3 x3 x3 ）,对于只有两个决策变量的线性规划问题，可以在二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。,四、线性规划的图解法,例1.5 某工厂在计划
11、期内要安排，两种产品的生产，生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制如表所示：,工厂每生产一单位产品可以获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少单位产品和产品才能使获利最多？,问题的线性规划模型： 目标函数：max z= 50x1+100 x2 约束条件：x1+x2300 2x1+x2400 x2250 x1 0， x2 0,第一步：确定可行域,X1,X2,O,x1+x2300,300,200,100,100,200,300,400,x2250,2x1+x2400,可行域,第二步：作目标函数等值线，确定使目标函数最优的点,X1,X2,O,Z100
12、00,300,200,100,100,200,300,400,等值线法线,z0,(50,250),Z27500,等值线,最优解,最优值,故原问题最优解为： x150，x2250 最优值为27500。,图解法求解线性规划问题的步骤：,1、建立直角坐标系。 2、画出可行域。 3、作目标函数的等值线 4、找出最优解（切点即为最优解，找出切点坐标，并代入目标函数求得最优值）。,X1,X2,O,x1+x2300,300,200,100,100,200,300,400,x2250,2x1+x2400,最优解： x150 x2250,非可行解： x1200 x2300,可行解： x1100 x2100,可行
13、域,线性规划中解的概念,线性规划中几个的概念,1、解：决策变量的任意一组取值； 2、可行解：满足约束条件（包括非负条件）的一组决策变量值，称可行解； 3、可行域：所有可行解的集合； 4、最优解：使目标函数值最优（即使最大化目标函数值最大，使最小化目标函数最小）的可行解； 5、最优值：最优解对应的目标函数值。,松弛变量的值和意义,例1.5的线性规划模型化为标准型： 目标函数：max z= 50x1+100 x2 约束条件：x1+x2+s1300 2x1+x2+s2400 x2+s3250 x1,x2,s1,s2,s30 引入的松弛变量常常表示未被充分利用的资源条件。,松弛变量的值和意义,对最优解
14、x150，x2250来说，各松弛变量的值如下表所示：,松弛变量的值也可以从图解法中获得一些信息：,X1,X2,O,x1+x2300,300,200,100,100,200,300,400,x2250,2x1+x2400,最优解： x150 x2250,S1=0 S20 S3=0,剩余变量的值和意义,请大家下去后阅读教材1517页例2,课堂练习：图解法求解以下LP问题,目标函数 Max z = 2500x1 + 1500x2 约束条件 s.t. 3x1+2x2 65 2x1+x2 40 3x2 75 x1 ,x2 0,X1,X2,O,3x1+2x265,30,20,10,10,20,30,40,
15、3x275,2x1+x240,（15，10）,40,50,答案： 最优解为： x1 15 ，x210 最优值为：z*250015+150010 52500,五、线性规划问题解的情况,例1.5的最优解只有一个，这是线性规划问题最一般的解的情况，但线性规划问题解的情况还存在其它特殊的可能：无穷多最优解、无界解或无可行解。,1、有唯一最优解的情况,例1.5中即是，在此不再赘述。 如果一个线性规划问题有最优解，则一定有一个可行域的顶点对应最优解，唯一最优解一定在可行域的顶点上取得。,在例1. 5的线性规划模型中 目标函数：Max z= 50x1+100 x2 约束条件：x1+x2300 2x1+x2400 x2250 x1 0， x2 0 若目标函数变为： Max z= 50x1+50 x2,2、无穷多最优解的情况,A(0,250),B(50,250),C(100,200),D(200,0),X1,X2
