线性规划的图解法幻灯片.ppt

线性规划的图解法第1页，共65页，编辑于2022年，星期一1第二章第二章线性规划的图解法线性规划的图解法在管理中一些典型的线性规划应用在管理中一些典型的线性规划应用合理利用线材问题：如何在保证生产的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小线性规划模型的组成：线性规划模型的组成：决策变量 用符号来表示可控制的因素目标函数 Max F 或 Min F约束条件 s.t.(subject to)满足于第2页，共65页，编辑于2022年，星期一211问题的提出问题的提出例例1.某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？线性规划模型：线性规划模型：目标函数：Max z=50 x1+100 x2 约束条件：s.t.x1+x2 300 2 x1+x2 400 x2 250 x1,x2 0第3页，共65页，编辑于2022年，星期一3一家工厂制造三种产品，需要三种资源：技术服务、劳动力、行政管理。下表列出了三种单位产品对每种资源的需要量。今有100h的技术服务，600h的劳动力和300h的行政管理时间可供使用。试确定能使总利润最大的产品生产量的线性规划模型。产品资源/h单位利润/元技术服务 劳动力行政管理11102102142631564第4页，共65页，编辑于2022年，星期一4解：设三种产品的生产量分别为x1、x2、x3。线性规划模型为：Max z=10 x1+6x2+4x3S.t.x1+x2+x3100 10 x1+4x2+5x3 600 2x1+2x2+6x3 300 x1,x2,x30第5页，共65页，编辑于2022年，星期一5例例2 M&D公司生产两种产品A和B，基于对现有的存储水平和下一个月的市场潜力的分析，M&D公司管理层决定A和B的总产量至少要达到350千克，此外，公司的一个客户订了125千克的A产品必须首先满足。每千克A、B产品的制造时间分别为2小时和1小时，总工作时间为600小时。每千克A、B产品的原材料成本分别为2$和3$。确定在满足客户要求的前提下，原材料成本最小的生产计划。第6页，共65页，编辑于2022年，星期一6第7页，共65页，编辑于2022年，星期一711问题的提出问题的提出建模过程建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件一般形式一般形式目标函数：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 第8页，共65页，编辑于2022年，星期一8 max（min）z=c1x1+c2x2+cnxn x1，x2，xn 0st.st.a11x1+a12x2+a1nxn (或或=,)b1a21x1+a22x2+a2nxn (或或=,)b2an1x1+a2nx2+annxn (或或=,)bm 目标函数目标函数约束条约束条件件决策变量决策变量xj称为该问题的决策变量。称为该问题的决策变量。资源拥有资源拥有量量价值系数价值系数在目标函数中在目标函数中xj的系数的系数cj称为称为该决策变量的价值系数。该决策变量的价值系数。技术系数技术系数或工艺系或工艺系数数aij 称为该问题的技术称为该问题的技术系数或工艺系数。由所有系数或工艺系数。由所有aij组成的矩阵称为约束组成的矩阵称为约束方程的方程的系数矩阵系数矩阵。在问题中，在问题中，xj的取值受的取值受m项资项资源的约束，源的约束，bi称为第称为第i项资源项资源的拥有量。的拥有量。第9页，共65页，编辑于2022年，星期一9其它表示方式其它表示方式x xj j 0(j=1,2,0(j=1,2,n),n)st.st.max max（minmin）z=z=c cj jx xj ja aijijx xj j (或或=,)b=,)bi i(i=1,2,(i=1,2,m),m)max max（minmin）z=z=X X 0 0st.st.CX C=CX C=（c c1 1,c c2 2,c,cn n ）P Pj jx xj j (或或=,)b=,)b用用向向量量表表达达P Pj j=（a a1j 1j,a a2j 2j,a,anjnj）T Tb=b=（b b1 1,b b2 2,b,bm m）T T简简化化表表示示X=X=（x x1 1,x x2 2,x,xn n）T T其中其中X X 0 0st st.AX AX(或或=,)b=,)b用用矩矩阵阵表表达达A=A=a a11 11 a a12 12 a a1n 1n a a21 21 a a22 22 a a2n 2n a am1 m1 a am2 m2 a amn mn 矩阵矩阵A A称为约束方程组（约束条件）的系数矩阵。称为约束方程组（约束条件）的系数矩阵。max max（minmin）z=z=C CX X C=C=（c c1 1,c c2 2,c,cn n ）第10页，共65页，编辑于2022年，星期一10例例2-1.目标函数：Max z=50 x1+100 x2 约束条件：s.t.x1+x2 300 (A)2 x1+x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)得到最优解：x1=50，x2 =250 最优目标值 z =275002图图 解解 法法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：第11页，共65页，编辑于2022年，星期一11图解线性规划问题步骤第一步，画直角坐标系第二步，根据约束条件画可行域第三步，画过坐标原点的目标函数线，斜率为-c1/c2第四步，确定目标函数值的增大（减小）方向第五步，让目标函数沿着增大（减小）方向平行移动，与可行域相交且有最大（最小）目标函数值的顶点，即为线性规划问题的最优解，然后根据最优解求最优值。第12页，共65页，编辑于2022年，星期一12x1x2z=20000=50 x1+100 x2图z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE第13页，共65页，编辑于2022年，星期一13二元一次不等式（组）表示的平面区域的确定怎样判断二元一次不等式 表示的是直线 哪一侧的平面区域？可以用“选点法”确定具体区域：任选一个不在直线上的点，检验它的坐标是否满足所给的不等式若适合，则该点所在的一侧即为不等式所表示的平面区域；否则，直线的另一侧为所求的平面区域 第14页，共65页，编辑于2022年，星期一14画出下列不等式所表示的平面区域：（1）y-2x+1 （2）x-y+20第15页，共65页，编辑于2022年，星期一15(1)x0 (2)6x+5y22 (3)yx 第16页，共65页，编辑于2022年，星期一162图图 解解 法法 (1)分别取决策变量X1,X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=0第17页，共65页，编辑于2022年，星期一172图图 解解 法法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400第18页，共65页，编辑于2022年，星期一182图图 解解 法法（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1第19页，共65页，编辑于2022年，星期一192图图 解解 法法（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE斜截式第20页，共65页，编辑于2022年，星期一20价值系数的符号与目标函数直线族的平行移动写成斜截式比较容易弄清楚移动方向Z=50 x1+100 x2 （+，+）求最大右上方移动，求最小左下方移动Z=-50 x1-100 x2 （-，-）求最大左下方移动，求最小右上方移动Z=-50 x1+100 x2 （-，+）求最大左上方移动，求最小右下方移动Z=50 x1-100 x2 （+，-）求最大右下方移动，求最小左上方移动关键在C2，C2为正，则往上平移；C2为负，则往下平移第21页，共65页，编辑于2022年，星期一21x1x2O1020304010203040(300,400)(15,10)最优解最优解X=(15,10)最优值最优值Z=8500例例2-2第22页，共65页，编辑于2022年，星期一22246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)min Z=x1+2x2例例2-3(1,2)第23页，共65页，编辑于2022年，星期一23246x1x2246X（2）（3,1）X（1）（1,3）(5,5)min Z=5x1+5x2例例2-4有无穷多个最优解有无穷多个最优解即具有多重解即具有多重解,通解为通解为 01 当当=0.5时时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)第24页，共65页，编辑于2022年，星期一24246x1x2246(1,2)无界解无界解(无最优解无最优解)max Z=x1+2x2例例2-5第25页，共65页，编辑于2022年，星期一25x1x2O10203040102030405050无可行解无可行解即无最优解即无最优解max Z=10 x1+4x2例例2-6第26页，共65页，编辑于2022年，星期一26由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式种形式：1.有唯一最优解有唯一最优解(例例2-2例例2-3)2.有多重最优解有多重最优解(例例2-4)3.有无界解有无界解(例例2-5)4.无可行解无可行解(例例2-6)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解第27页，共65页，编辑于2022年，星期一272图图 解解 法法重要结论：如果线性规划有最优解，则一定可以在可行域的某个顶点上找到最优解；无穷多个最优解，在边界上取得。若将例2-1中的目标函数变为max z=50 x1+50 x2，则线段BC上的所有点都代表了最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例2-1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。第28页，共65页，编辑于2022年，星期一28进进 一一 步步 讨讨 论论 例例2 2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？第29页，共65页，编辑于2022年，星期一29进进 一一 步步 讨讨 论论解：目标函数：Min f=2x1+3 x2 约束条件：s.t.x1+x2 350 x1 125 2 x1+x2 600 x1 ,x2 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。100200300 400 500 600100200300400600500 x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200 x1 x2 Q第30页，共65页，编辑于2022年，星期一303线性规划模型的标准化线性规划模型的标准化标准化便于代数求解，为后面单纯形法求解作准备。标准化便于代数求解，为后面单纯形法求解作准备。一般形式一般形式目标函数：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 标准形式标准形式目标函数：Max 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，bi 0第31页，共65页，编辑于2022年，星期一313线性规划的标准化线性规划的标准化 可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:第32页，共65页，编辑于2022年，星期一323线性规划的标准化线性规划的标准化1、决策变量不是非负 在标准形式中，必须每一个变量均有非负约束。1）当决策变量xk0，则用-xk代替xk，且xk 02）当某一个变量xj无符号要求时，可以令 xj=xj-xj”其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。第33页，共65页，编辑于2022年，星期一333线性规划的标准化线性规划的标准化2、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ain xn bi 可以引进一个新的变量s，使它等于约束右边与左边之差 s=bi(ai1 x1+ai2 x2+ain xn)显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi第34页，共65页，编辑于2022年，星期一343线性规划的标准化线性规划的标准化 当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，类似地令 s=(ai1 x1+ai2 x2+ain xn)-bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-s=bi第35页，共65页，编辑于2022年，星期一353线性规划的标准化线性规划的标准化 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。松弛变量表示未被充分利用的资源，剩余变量表示超过最低限约束的资源多用量。两者在目标函数中的价值系数均为零。只有决策变量影响到目标函数值。第36页，共65页，编辑于2022年，星期一363线性规划的标准化线性规划的标准化3.极小化目标函数的问题：设目标函数为 Min f=c1x1+c2x2+cnxn (可以)令 z -f，则该极小化问题与下面的极大化问题有相同的最优解，即 Max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值（最优值）却相差一个符号，即 Min f -Max z第37页，共65页，编辑于2022年，星期一374.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以-1。如：x1-4x2-5第38页，共65页，编辑于2022年，星期一38线性规划标准化的步骤第39页，共65页，编辑于2022年，星期一39【例】将下列线性规划化为标准型【例】将下列线性规划化为标准型【解】（）因为【解】（）因为x3无符号要求无符号要求，即，即x3取正值也可取取正值也可取负值，标准型中要求变量非负，所以令负值，标准型中要求变量非负，所以令 第40页，共65页，编辑于2022年，星期一40(3)第二个约束条件是第二个约束条件是号，在号，在号号 左左端减去剩余变量端减去剩余变量(Surplus variable)x5，x50。也称松驰变量。也称松驰变量(2)第一个约束条件是第一个约束条件是号，在号，在左端加入左端加入松驰变量松驰变量(slack variable)x4，x40,化为等化为等式；式；(4)第三个约束条件是第三个约束条件是号且常数项为负数，因此在号且常数项为负数，因此在左边加入松左边加入松驰变量驰变量x6，x60，同时两边乘以，同时两边乘以1。（5）目标函数是最小值，为了化为求最大值，令）目标函数是最小值，为了化为求最大值，令Z=Z,得到得到max Z=Z，即当，即当Z达到最小值时达到最小值时Z达到最大值，反之亦然。达到最大值，反之亦然。第41页，共65页，编辑于2022年，星期一41综合起来得到下列标准型综合起来得到下列标准型 第42页，共65页，编辑于2022年，星期一42当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束再化为等式，例如约束 将其化为两个不等式将其化为两个不等式 再加入松驰变量化为等式。再加入松驰变量化为等式。第43页，共65页，编辑于2022年，星期一43对于对于axb(a、b均大于零均大于零)的有界变量化为标准形式有两种方法。的有界变量化为标准形式有两种方法。一种方法是增加两个约束一种方法是增加两个约束xa及及xb 另一种方法是令另一种方法是令x=xa，则，则axb等价于等价于0 xba，增加一个约，增加一个约束束xba并且将原问题所有并且将原问题所有x用用x=x+a替换。替换。化标准型的步骤总结1、决策变量非负2、约束条件为等式3、目标函数极大化4、右端常数非负第44页，共65页，编辑于2022年，星期一444图解法的灵敏度分析图解法的灵敏度分析 灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci,aij,bj 变化时，对最优解产生的影响。4.1 目标函数中的系数目标函数中的系数 ci 的灵敏度分析的灵敏度分析 考虑例1的情况，ci 的变化只影响目标函数等值线的斜率，只会引起目标函数旋转，旋转后再平移，找到最优值。目标函数 z=50 x1+100 x2 第45页，共65页，编辑于2022年，星期一45目标函数线旋转CBD0AC2的符号第46页，共65页，编辑于2022年，星期一46目标函数线旋转CBD0A第47页，共65页，编辑于2022年，星期一47目标函数线旋转CBD0A第48页，共65页，编辑于2022年，星期一48目标函数线旋转CBD0A关键是找出斜率的分界点第49页，共65页，编辑于2022年，星期一49目标函数线旋转CBD0A关键是找出斜率的分界点第50页，共65页，编辑于2022年，星期一50目标函数线旋转CBD0A关键是找出斜率的分界点第51页，共65页，编辑于2022年，星期一51目标函数线旋转CBD0A关键是找出斜率的分界点第52页，共65页，编辑于2022年，星期一524图解法的灵敏度分析图解法的灵敏度分析假设产品的利润100元不变，即 c2=100，代到式（*）并整理得 0 c1 100 假设产品的利润 50 元不变，即 c1=50，代到式（*）并整理得 50 c2 +假若产品、的利润均改变，则可直接用式（*）来判断。假设产品、的利润分别为60元、55元，则 -2 -(60/55)-1 那么，最优解为 z=x1+x2 和 z=2 x1+x2 的交点 x1=100，x2=200。第53页，共65页，编辑于2022年，星期一534图解法的灵敏度分析图解法的灵敏度分析 4.2 约束条件中右边系数 bj 的灵敏度分析 当约束条件中右边系数 bj 变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑例1的情况：假设设备台时增加10个台时，即 b1变化为310，这时可行域扩大，最优解为 x2=250 和 x1+x2=310 的交点 x1=60，x2=250。变化后的总利润-变化前的总利润=增加的利润 (5060+100250)-(50 50+100 250)=500，500/10=50 元 说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。第54页，共65页，编辑于2022年，星期一54约束边界线平移BCDA0第55页，共65页，编辑于2022年，星期一55约束边界线平移BCDA0E第56页，共65页，编辑于2022年，星期一56约束边界线平移BCDA0FE第57页，共65页，编辑于2022年，星期一57某一约束条件的对偶价格仅仅是在某一范围内是有效的。当这种约束条件的资源不断地获得，使得其右端项不断增大时，由于其他约束条件的限制，使得这种约束条件的资源用不完，即其松弛变量不为零，也就是说其不再构成约束，其对偶价格为零。对偶价格为零，即该种资源增加时不会导致最优目标函数值的增加。第58页，共65页，编辑于2022年，星期一58约束边界线平移BCDA0第59页，共65页，编辑于2022年，星期一59约束边界线平移BCDA0第60页，共65页，编辑于2022年，星期一60约束边界线平移BCDA0第61页，共65页，编辑于2022年，星期一61约束边界线平移BCDA0M第62页，共65页，编辑于2022年，星期一62约束边界线平移BCDA0O第63页，共65页，编辑于2022年，星期一63约束边界线平移BCDA0OP第64页，共65页，编辑于2022年，星期一644图解法的灵敏度分析图解法的灵敏度分析 假设原料 A 增加10 千克时，即 b2变化为410，这时可行域扩大，但最优解仍为 x2=250 和 x1+x2=300 的交点 x1=50，x2=250。此变化对总利润无影响，该约束条件的对偶价格为 0。解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。在一定范围内，当约束条件右边常数增加1个单位时 （1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好），即求最大值时增加，求最小值时减小；（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏），即求最大值时减小，求最小值时增加；（3）若约束条件的对偶价格等于0，则最优目标函数值不变。第65页，共65页，编辑于2022年，星期一65