线性规划课件.pptx

1线性规划Linear programming第1页/共123页21、线性规划的建模一例（例1）例1：在工厂计划期内要安排生产A、B两种产品，已知生产单位产品所需的设备台时及a、b两种原材料的消耗如下表。又该工厂每生产一件A产品可获利2元，每生产一件B产品可获例3元。问：如何安排计划使该工厂获利最大？产品A产品B资源总数设备128台时原材料a4016KG原材料b0412KG单位利润23第2页/共123页3解设A、B两种的产量分别为（决决策策变变量量），该问题的数学模型为：目标函数目标函数约束函数约束函数（SubjectTo：s.t.）产品A产品B资源总数设备128台时原材料a4016KG原材料b0412KG单位利润23第3页/共123页42、线性规划模型第4页/共123页5线性规划模型解析式标准形式第5页/共123页6模型形式简记第6页/共123页7线性规划模型矩阵标准形式线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,unr,0线性规划的标准形式目标函数：max约束条件：=变量符号：0第7页/共123页8线性规划模型练习1 三种产品要经过三种不同的工序加工。各种产品每一件所需时间（分钟），每天各道工序的加工能力（每天多少分钟）和销售每一种产品的单位利润如下。试建立使总利润达到最大的线性规划模型。工序每件时间（分钟）第1种产品第2种产品第3种产品工序加工能力（分钟/天）123121312141430460420利润/件（元）325第8页/共123页9线性规划模型练习2 某厂为进行生产需采购A、B两种原材料，单价分别为70元/公斤和50元/公斤。现要求购买资金不超过5000元，总购买量不少于80公斤，而A原材料不少于20公斤。问如何确定最好的采购方案（即花掉的资金最少并且购买的总量最大）？第9页/共123页103、线性规划的图解解决只有两个决策变量的线性规划问题方法：在直角坐标系中画出所有约束方程的图象，从而得到可行域（满足所有约束方程的解的集合）；可行域（满足所有约束方程的解的集合）；然后画出经过原点的目标函数图象的平行线目标函数等值线；目标函数等值线；寻找经过可行域的使Z Z达到最大的目标函数等值线，该直线与可行域的交集即为最优解最优解集。第10页/共123页图解法例1max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x2064-860 x1x2目标函数等值线最优解可行域第11页/共123页12图解法例2max z=2x1+3x2s.t.x1+2x284 x1 16 4x2 12x1 0,x20 x204843x1最优解（4，2）目标函数等值线可行域0第12页/共123页13四种可能的解的情况四种可能的解的情况唯一最优解无穷多最优解无界解（无穷可行解，但无最优解）无解（无可行解）第13页/共123页14唯一最优解max z=2x1+3x2s.t.x1+2x284 x1 16 4x2 12x1 0,x2004843x1x2最优解（4，2）目标函数等值线可行域第14页/共123页15线性规划的图解无穷多最优解在例2中，maxz=2x1+3x2s.t.x1+2x284x1164x212x10,x20目标函数改为：maxz=2x1+4x204843x1最优解（4，2）目标函数等值线可行域 目标函数等值线与第一条约束直线平行，目标函数等值线与第一条约束直线平行，可以移至重合，与可行域交集为一线段。可以移至重合，与可行域交集为一线段。第15页/共123页16无界解目标函数等值线第16页/共123页17无解第17页/共123页184、模型的标准化一般形式：标准形式：第18页/共123页19模型的标准化第19页/共123页20模型的标准化例题将标准化第20页/共123页21例题答案标准化形式原型第21页/共123页22模型的标准化练习将下列模型标准化第22页/共123页23练习答案原型标准化形式第23页/共123页245、线性规划的基本概念第24页/共123页几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基解可行域的极点基可行解目标函数等值线：一组平行线 目标函数值等于一个常数的解第25页/共123页26可行解与最优解可行解：满足约束条件的解，记为X X=（x1，x2，xn）T最优解：使目标函数值达到最优的可行解。第26页/共123页基矩阵 约束方程系数矩阵A的mm子矩阵B，若B的行列式0，则称B为A的一个基（矩阵）。=目标函数约束条件行列式0基矩阵右边常数第27页/共123页28基变量、基向量 基B对应的m个变量为基变量，其他n-m个变量为非基变量。假定 第28页/共123页29基阵基阵非基阵非基阵基基向向量量非非基基向向量量基变量基变量非基变量非基变量第29页/共123页30基解、基可行解基解基解：令所有非基变量为0，根据约束方程求得的解（不包括非负约束）为对应基的基解。表示为 X=（x1，x2，xm，0，0）T基可行解基可行解：满足非负约束的基解。基的个数最多为 ，故基解的个数最多为 。第30页/共123页31总结几个概念基矩阵、非基矩阵基变量、非基变量基向量、非基向量基解、可行解、基可行解、最优解第31页/共123页32几种解的关系第32页/共123页可行域的性质线性规划的可行域是凸集线性规划的最优解在极点上凸集凸集不是凸集极点第33页/共123页基解例1第34页/共123页基变量x1、x2、x3，非基变量x4、x5、x6基解为（x1，x2，x3，x4，x5，x6）T=（5，3，1，0，0，0）T是基可行解，表示可行域的一个极点。目标函数值为：z=20第35页/共123页基变量x1、x2、x4，非基变量x3、x5、x6基解为（x1，x2，x3，x4，x5，x6）T=（27/5，12/5，0，2/5，0，0）T是基可行解，表示可行域的一个极点。目标函数值为：z=18第36页/共123页基变量x1、x2、x5，非基变量x3、x4、x6基解为（x1，x2，x3，x4，x5，x6）T=（6，3，0，0，-3，0）T是基解，但不是可行解，不是一个极点。第37页/共123页基变量x1、x2、x6，非基变量x3、x4、x5基解为（x1，x2，x3，x4，x5，x6）T=（3，4，0，0，0，4）T是基可行解，表示可行域的一个极点。目标函数值为：z=18第38页/共123页基变量x2、x3、x4，非基变量x1、x5、x6基解为（x1，x2，x3，x4，x5，x6）T=（0，21/2，27/2，-30，0，0）T是基解，但不是可行解。第39页/共123页基变量x1、x2、x3，非基变量x4、x5、x6基解为（x1，x2，x3，x4，x5，x6）T=（0，3，6，0，15，0）T是基可行解，表示可行域的一个极点。目标函数值为：z=15第40页/共123页基变量x1、x2、x3，非基变量x4、x5、x6基解为（x1，x2，x3，x4，x5，x6）T=（0，11/2，-3/2，0，0，10）T是基解但不是可行解。第41页/共123页基解例2max z=x1+3x2Ds.t.x1+x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0 x1,x2,x3,x40 x1=0E O x2=0 A第42页/共123页43基解课堂练习max z=3x1+x2s.t.3x1+5x2+x3=15 5x1+2x2 +x4=10 x1,x2,x3,x40 试求其所有的基解,并判断哪些基解为基可行解.第43页/共123页44练习答案第44页/共123页45解题过程A=3 5 1 0 B1=3 5 B0为A的一个基 5 2 0 1 5 2 B1对应的基变量为x1,x2,令非基变量x3=x4=0,则求得基变量x1=20/19,x2=45/19，从而X1=（20/19，45/19，0，0）T为基解，满足非负，也为基可行解。同理求得B2=3 1 ,X2=(2,0,9,0)T 5 0 B3=3 0 ,X3=(5,0,0,-15)T 5 1 B4=5 1 ,X4=(0,5,-10,0)T 2 0 B5=5 0 ,X5=(0,3,0,4)T 2 1 B6=1 0 ,X6=(0,0,15,10)T 0 1显然X3、X4是基解，但不是基可行解，X1、X2、X3、X4是基可行解。maxz=3x1+x2s.t.3x1+5x2+x3 =155x1+2x2 +x4=10 x1,x2,x3,x40第45页/共123页46基解课后练习在下列线性规划问题中，找出所有基解、基可行解和最优解。maxZ=10 x1+5x2s.t 3x1+4x29 5x1+2x28 x1,x20第46页/共123页476、线性规划的求解寻找最优解的过程进基变量、离基变量、基变换单纯形法第47页/共123页48寻找最优解的过程根据问题的标准，从可行域中某个基可行解（一个极点）开始，转换到另一个更优的基可行解（另一个极点），直到使目标函数达到最大、得到最优解为止。第48页/共123页49以例1为例MaxZ=2x1+3x2 x1+2x2 8 4x1 16 4x212 x1，x20 第49页/共123页50第一步 化标准型MaxZ=2x1+3x2+0 x3+0 x4+0 x5 x1+2x2+x3 =8 4x1 +x4 =16 4x2+x5=12 x1,x2,x3 0第50页/共123页51第二步 寻找第一个基，求第一个基可行解 A=(P1,P2,P3,P4,P5)B=(P3,P4,P5)=1 0 0 0 1 0 0 0 1 令x1=x2=0,得第一个基可行解 x(1)=(0,0,8,16,12)T此时z=0，由于z=2x1+3x2有正系数的非基变量x1和x2，选择将x2换入。第51页/共123页52第三步 将x2换入，选择一个基变量换出 x1依然为非基变量，令x1=0，则 x3=8-2x2 0 x4=16 0 x5=12-4x2 0 因而x2=min(8/2,-,12/4)=3当x2=3时,x5=0,，由此选择x2替换x5。第52页/共123页53经过替换得 x3=2-x1+1/2x5 x4=16-4x1 x2=3-1/4x5 z=9+2x1-3/4x5令 x1=x5=0 ，得z=9和另一个基可行解x(2)=(0,3,2,16,0)T 此时有正系数的非基变量 x1，因而选择x1换入，用相同的方法选择换出的基变量第53页/共123页54同理可得其他的基可行解x(3)=(2,3,0,8,0)Tx(4)=(4,2,0,0,4)T当解为x(4)时，z=14-1.5x3-0.125x4此时再无正系数的非基变量，所以 max=14，唯一最优解为x(4)第54页/共123页=目标函数约束条件基矩阵右边常数进基变量、离基变量、基变换=基变量第55页/共123页=进基变量离基变量目标函数约束条件右边常数=第56页/共123页=目标函数约束条件新的基矩阵右边常数=第57页/共123页=进基变量离基变量目标函数约束条件基矩阵=第58页/共123页=目标函数约束条件新的基矩阵右边常数=第59页/共123页60单纯形法第60页/共123页61单纯形法的基本思想 根据问题的标准，从可行域中某个基可行解（一个极点）开始，转换到另一个更优的基可行解（另一个极点），直到使目标函数达到最大、得到最优解为止。第61页/共123页线性规划的矩阵表示=第62页/共123页=典则形式（典式）典则形式（典式）第63页/共123页64可以证明：检验数检验数典则形式（典式）典则形式（典式）第64页/共123页65证明 检验数检验数 -所有变量的系数所有变量的系数非基变量的系数非基变量的系数注意注意1 1：基变：基变量检验数为量检验数为0 0注意注意2 2：所：所有检验数有检验数=0=0时得到时得到最优解最优解第65页/共123页66由上面证明得检验数检验数令xN=0,得xB=B-1b,此即为基解x*=(xB,xN)T=(B-1b,0)当所有0时，基解x*=(B-1b,0)为最优基解当所有B-1b0时，最优基解x*=(B-1b,0)为最优 基可行解，即为最优的 极点，即为 最优解。第66页/共123页67令令则则定义定义 在约束方程组在约束方程组(2)中，对于中，对于一个选定的基一个选定的基B，令所有的非基变，令所有的非基变量为零得到的解，称为相应于基量为零得到的解，称为相应于基B的的基本解基本解。再看一次再看一次整个过程整个过程第67页/共123页68基本定理1 对于一个线性规划问题，若存在基B，使 则对应于基B的基可行解 就是最优解，B为最优基。可行性可行性最优性最优性第68页/共123页69基本定理2 线性规划问题如果存在最优解，则一定存在一个基本可行解是最优解。第69页/共123页70矩阵与单纯形表的对应关系第70页/共123页XbCBXBAb-ZXBXNbCBXBBNb-ZXBXNbCBXBIB-1NB-1b-ZCT-CBB-1A-CBTB-1b模型矩阵形式模型矩阵形式单纯形表单纯形表第71页/共123页72单纯形表的基本格式（1）CbXCBXBB-1AB-1b-ZC-CBB-1A-CBB-1bXbCBXBAb-Z第72页/共123页73单纯形表的基本格式（2）典式：典式：CBCNbXBXNCBXBIB-1NB-1b-ZC-CBB-1A-CBB-1b单纯形法单纯形法基本格式：基本格式：第73页/共123页74单纯形表的基本格式（3）00(右端项)（松弛变量）（原始决策变量）(右端项)（松弛变量）（原始决策变量）对于迭代过程中的任意可行基对于迭代过程中的任意可行基B所形成的单纯形表，初始表所形成的单纯形表，初始表中单位子矩阵的位置（即松弛变量对应的系数）必为中单位子矩阵的位置（即松弛变量对应的系数）必为B-1 留意松弛变量留意松弛变量xs的检验数的检验数-CBB-1，在下一章有用。，在下一章有用。第74页/共123页75单纯形表的基本格式（3）00(右端项)（松弛变量）（原始决策变量）(右端项)（松弛变量）（原始决策变量）研究此时的系数矩阵研究此时的系数矩阵由此可见，此时xj 的系数为B-1Pj。第75页/共123页76单纯形法例 1第76页/共123页77初始可行基初始基可行解 第77页/共123页78000-210-Z2210-110 x501101-310 x402001-21x10 x5x4x3x2x1XBCBB-1b00-210C初始单纯形表第78页/共123页79-10-1100-Z1/211-1200 x50101-310 x21402-501x10000-210-Z2210-110 x501101-310 x402001-21x10 x5x4x3x2x1XBCBB-1b00-210C表 1表 2第79页/共123页80-3/2-1/2-1/2000-Z1/21/2-1/2100 x3-25/23/2-1/2010 x2113/25/2-1/2001x10-10-1100-Z1/211-1200 x50101-310 x21402-501x10 x5x4x3x2x1XBCBB-1b00-210C表 2表 3最优解第80页/共123页81例 2第81页/共123页第82页/共123页第83页/共123页第84页/共123页第85页/共123页86单纯形法的求解步骤1、标准化2、求出初始基可行解3、列出单纯形表，并求出检验数的值4、对检验数进行判断:（1）若所有检验数=0，则已求出最优解；（2）若至少有一个检验数为正，则选取绝对值最大的那个，对应的非基变量为入基变量。计算 的值：若对应非基变量 xk 的系数B-1pk 0（即0，则选择最小的，其对应的变量为出基变量。进行初等变换。转3 第86页/共123页87人工变量法1、两阶段法2、大M法第87页/共123页88对于约束条件为=或=的情形第88页/共123页89假定已经标准化的原问题为第89页/共123页90 对于已经标准化的形式，每个约束等式加上一个人工变量第90页/共123页91两阶段法：将求解过程分成两个阶段第一阶段、构造辅助线性规划问题求解，若求得辅助线性规划问题的目标函数值为0，则原问题存在可行解，进入第二阶段，否则原问题无解。第二阶段、以第一阶段求得的最优解为初始可行解，求解原问题。第91页/共123页92所加入的人工变量只有满足全为0时才能保证原等式成立。建立新目标。所有人工变量全为0时，新目标函数达到最优值0。第92页/共123页93第一阶段 求解辅助线性规划问题第93页/共123页94若第一阶段求得的最优解使目标函数值达到最大值0，则进入第二阶段。假定求得的最优解为X=()。第94页/共123页95第二阶段、以X为初始可行解求解原问题第95页/共123页96两阶段法例1第96页/共123页97第一阶段，构造辅助线性规划问题原问题辅助规划问题人工变量第97页/共123页98对辅助规划问题的求解00010001x5-1-9/5-1/51/5-3/50010 x6-1-901016/52/5-W10/361109/53/5x7-12040011/52/5x3015/730007/5-1/5x5-1-4501954-W101011121x7-142000512x6-151500321x5-1x7x4x3x2x1XBCBB-1b-10000C表1表2第98页/共123页99-1-9/7-1/75/7-16/7-9/7-1/75/7x5-1-17/42/7-3/7-3/77/42/7-3/7x6-10-10000-W15/711006/7x4025/700103/7x3015/70001-1/7x20-15/701006/7-W15/715/711006/7x7-125/700103/7x3015/70001-1/7x20 x7x4x3x2x1XBCBB-1b-10000C表3表4最优解第99页/共123页100第二阶段，求解原问题15-1000-Z5/27/6001x115/2-1/2100 x335/21/6010 x220006/7-Z5/215/71006/7x4-125/325/70103/7x3315/7001-1/7x22x4x3x2x1XBCBB-1b-1321C以为初始基可行解求解原问题表1表2最优解为第100页/共123页101两阶段法例2第101页/共123页102求解辅助规划问题-7/8-1/41/8-5/81010 x5000010001x6-1-15/8-1/41/8-5/80010 x7-1380-1-140-3/8-Z1010-60-1/4x8-1400115/8x20280-1-80-1/8x6-1-980-11159-Z91810-421x8-143200885x7-148/5480-1-353x6-1x8x4x3x2x1XBCBB-1b-10000C表1表2 由于辅助线性规划问题最优解为由于辅助线性规划问题最优解为-38-38，不为，不为0 0，所以原问题不存在可行解（无解）。，所以原问题不存在可行解（无解）。第102页/共123页103大大M法法原理：在进行迭代时，只有所有的人工变量均迭代为非基变量（即为0）时，才能消除大M对目标函数的影响，使目标函数达到最优。例：P64 例3 第103页/共123页104添加松弛变量、人工变量列出初始单纯形表计算非基变量各列的检验数j所有j0有aik0计算i=bi/aik令i=minixi为换出变量aik为主元素基变量中有非零的人工变量某非基变量检验数为零唯一唯一最优解最优解无可行解无可行解无界解无界解无穷多最优解无穷多最优解迭代运算是否否否是是是单纯形法一般步骤第104页/共123页105无穷多个最优解 若存在一个非基变量的检验数为0，则最优解不止一个且为无穷多个。第105页/共123页106无穷多最优解例题141-1/204x4-160-100-Z31/43/810 x2-160-100-Z11/4-1/801x1-3201/21-1x2-110002-2-Z661013x4-124012-2x3-1x4x3x2x1XBCBB-1b-1-1-1-3C表1表2表3第106页/共123页107由表2得最优解由表3得最优解所以，最优解为第107页/共123页108x1x2第108页/共123页109无穷多个最优解练习第109页/共123页110练习答案第110页/共123页111111011x111/211120 x30-1-1000-Z-1-1000-Z1/21/2-1/201x111/21/21/210 x2100011-Z111011x400011-1x30X4x3x2x1XBCBB-1b0011C表1表2表3第111页/共123页112由表2得最优解由表3得最优解所以，最优解为第112页/共123页113无界解例题第113页/共123页114作出其初始单纯形表如下0003/2-5/27/2100-1/25/213/2010-1/23/25/2001-1/21/21/2x1x2x3x4x5RHS(右端向量)zx1x2x3x4进基无离基变量x x4 4可无限增大，可无限增大，目标函数值随之目标函数值随之无限增大，所以无限增大，所以为无界解为无界解第114页/共123页115单纯形法的进一步讨论退化 对于基可行解XB=B-1b、XN=0，若存在基变量的值为0，则称该可行解是退化的可行解是退化的，否则为非退化的非退化的，即XB=B-1b0。若某线性规划问题的所以基可行解都是非退化的，则该问题为非退化的，否则该问题为退化的。第115页/共123页116退化引起死循环 从某个基开始，经过若干次迭代以后又回到原来的基，也就是单纯形法出现了死循环。出现死循环的原因主要是因为退化的问题中，基变量取值可以为0，即经过迭代以后，目标函数值可能不会增加。第116页/共123页117死循环的避免一种有效的方法是Bland方法P67第117页/共123页118单纯形法的进一步讨论最小化目标函数 最小化目标函数问题 只须在判断检验数时取相反符号即可。即迭代终止条件为：第118页/共123页119最小化目标函数例题第119页/共123页120以MIN求解-60100-Z41-1/204x41201/21-1x21-1000-22-Z661013x4124012-2x31x4x3x2x1XBCBB-1b1113C表1表2第120页/共123页121以MAX求解60-100-Z141-1/204x4-1201-1x2-110002-2-Z661013x4-124012-2x3-1X4x3x2X1XBCBB-1b-1-1-1-3C表1表2第121页/共123页122本章结束！第122页/共123页123感谢您的观看！第123页/共123页