第1章 线性规划 (2)—03,04,05讲.ppt

手机：手机：13551284516院系：交通与汽车学院，交通运输系院系：交通与汽车学院，交通运输系主讲主讲:罗罗 建建 运筹学运筹学邮箱：邮箱：luo06_luo06_第第1 1章章 线性规划线性规划复习复习1 1、线性规划问题的数学模型包含三个组成要素：线性规划问题的数学模型包含三个组成要素：决策变量决策变量 目标函数目标函数 约束条件约束条件2 2、线性规划数学模型的标准型，以及与非标准线性规划数学模型的标准型，以及与非标准型的转化。型的转化。3 3、图解法的一般步骤。、图解法的一般步骤。本堂课的主要内容本堂课的主要内容1 1、图解法的几何意义；、图解法的几何意义；2 2、单纯形法的概念；、单纯形法的概念；3 3、单纯形法的几何语言；、单纯形法的几何语言；4 4、单纯形法的代数形式、单纯形法的代数形式5 5、单纯型表格。、单纯型表格。重点及难点：单纯形表重点及难点：单纯形表1 1、图解法的几何意义；、图解法的几何意义；凸集凸集（Convex setConvex set）概念：概念：设设K是是n维欧氏空间维欧氏空间的一个点集，的一个点集，若若K中的任意两点中的任意两点x(1),x(2)的连的连线上的一线上的一切点切点x仍在仍在K中，则称中，则称K为凸集。为凸集。即：即：若若K中的任意两点中的任意两点x(1),x(2)K，存，存在在0=1 使得使得x=x(1)+(1-)x(2)K,则称则称K为凸集为凸集例（凸集）例（凸集）例（非凸集）例（非凸集）两个基本概念：两个基本概念：凸组合凸组合(Convex combination)(Convex combination)：设设x(1),x(2).x(k)是是n维欧氏空间维欧氏空间中的中的k个点，若个点，若存在数存在数u1,u2,.uk 且且0ui 1 (i=1,2,k),ui=1,使使得得 x=u1 x(1)+u2 x(2)+.+uk x(k)成立，则称成立，则称x为为x(1),x(2).x(k)的凸组的凸组合合。两个基本概念：两个基本概念：顶点顶点 ：设设K是凸集是凸集,若若K中的点中的点x 不能不能成为成为K中任何线段上的内点，则称中任何线段上的内点，则称x为为凸集凸集K的顶点。的顶点。即：即：若若K中的任意两点中的任意两点x(1),x(2)，不存，不存在数在数 （0 0，转，转3。3.换基迭代（基变换）换基迭代（基变换）（1）进基：取）进基：取对应的对应的Pk进基。进基。（2）出基：取）出基：取对应的对应的Pl进基。进基。得新基，转得新基，转2。注：注：（2）若对一切非基变量有）若对一切非基变量有j 0，且存在，且存在k=0，则有无穷多解。则有无穷多解。的计算的计算:XBCBB-1bx1x2x3x4x5四、单纯形法的实现四、单纯形法的实现单纯形表单纯形表例例：Max Z=7 x1+12x29 x1+4x23604x1+5x2 2003 x1+10 x2 300 x1,x20s.t.Max Z=7 x1+12x29 x1+4x2+x3 =3604x1+5x2 +x4 =2003 x1+10 x2 +x5 =300 x1,x50s.t.化为标准型化为标准型x3x4x5000360200300943451010001000112000单纯形表单纯形表:7x5x4x3x2x1B-1bCBXB四、单纯形法的实现四、单纯形法的实现单纯形表单纯形表例例：煤电油例：煤电油例Max Z=7 x1+12x29 x1+4x23604x1+5x2 2003 x1+10 x2 300 x1,x20s.t.Max Z=7 x1+12x29 x1+4x2+x3 =3604x1+5x2 +x4 =2003 x1+10 x2 +x5 =300 x1,x50s.t.化为标准型化为标准型x3x4x5000360200300943451010001000112000单纯形表单纯形表:790的计算的计算:4030 x5x4x3x2x1B-1bCBXB四、单纯形法的实现四、单纯形法的实现单纯形表单纯形表例例：煤电油例：煤电油例Max Z=7 x1+12x29 x1+4x23604x1+5x2 2003 x1+10 x2 300 x1,x20s.t.Max Z=7 x1+12x29 x1+4x2+x3 =3604x1+5x2 +x4 =2003 x1+10 x2 +x5 =300 x1,x50s.t.化为标准型化为标准型x3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 枢纽枢纽元素元素x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为为主主元元进进行行初初等等行行变变换换502.5001-0.52407.8010-0.43.4000-1.2或或:x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为为主主元元进进行行初初等等行行变变换换502.5001-0.52407.8010-0.43.4000-1.2或或:30.820100 x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1以以10为为主主元元进进行行初初等等行行变变换换502.5001-0.52407.8010-0.43.4000-1.230.820100 x3x1x2071224010-0.12 0.16201000.4-0.284001-3.12 1.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100 以以 为为主主元元进进行行初初等等行行变变换换2.5x3x1x2071224010-0.12 0.16201000.4-0.284001-3.12 1.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100 X*=(20,24,84,0,0)T Z*=428x3x1x2071224010-0.120.16201000.4-0.284001-3.12 1.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1502.5001-0.5240 7.8010-0.43.4000-1.230.820100注：单纯形表中的信息注：单纯形表中的信息每一列的含义：每一列的含义：B-1(bA)=(B-1b,B-1 P1,，B-1 Pn)每个表中的每个表中的B和和B-1的查找：的查找：B从初表中找；从初表中找；B-1从当前表中找，对应于从当前表中找，对应于初表中的初表中的I的位置。的位置。以第以第2个表为例：个表为例：终表分析终表分析最优基最优基B*和和(B*)-1的查找的查找x3x1x2071224010-0.120.16201000.4-0.284001-3.12 1.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表单纯形表:7904030 x3x4x20012300.31000.1502.5001-0.5240 7.8010-0.43.4000-1.230.820100注：单纯形表中的信息注：单纯形表中的信息换入基变量中，得到基可行解换入基变量中，得到基可行解换入基变量中，得到基可行解换入基变量中，得到基可行解定理：定理：定理：定理：若检验数全小于等于零，且某一个非基变量若检验数全小于等于零，且某一个非基变量若检验数全小于等于零，且某一个非基变量若检验数全小于等于零，且某一个非基变量的检验数为的检验数为的检验数为的检验数为0 0，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。（无穷多最优解情况）（无穷多最优解情况）（无穷多最优解情况）（无穷多最优解情况）证明：证明：证明：证明：某个非基变量某个非基变量某个非基变量某个非基变量为最优解。故线性规划问题有无为最优解。故线性规划问题有无为最优解。故线性规划问题有无为最优解。故线性规划问题有无穷多最优解。穷多最优解。穷多最优解。穷多最优解。为一基可行解，有一个变量为一基可行解，有一个变量为一基可行解，有一个变量为一基可行解，有一个变量X Xm+km+k对应对应对应对应因因因因为可行解。为可行解。为可行解。为可行解。定理：定理：若存在检验数大于零，但所对应的换入变量若存在检验数大于零，但所对应的换入变量若存在检验数大于零，但所对应的换入变量若存在检验数大于零，但所对应的换入变量X Xm+km+k的系数向量的系数向量的系数向量的系数向量P Pm+km+k0,0,则原问题无最优解。（则原问题无最优解。（则原问题无最优解。（则原问题无最优解。（无界解的情况）无界解的情况）无界解的情况）无界解的情况）证明：证明：证明：证明：构造一个新的解构造一个新的解构造一个新的解构造一个新的解 ，分量为，分量为，分量为，分量为定理定理：若非基变量检验数严格小于零，则线：若非基变量检验数严格小于零，则线性规划问题有唯一最优解。性规划问题有唯一最优解。定理定理：若检验数全小于等于零，且某一个非基变：若检验数全小于等于零，且某一个非基变：若检验数全小于等于零，且某一个非基变：若检验数全小于等于零，且某一个非基变量的检验数为量的检验数为量的检验数为量的检验数为0 0，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。定理定理：若某一个非基变量的检验数大于若某一个非基变量的检验数大于若某一个非基变量的检验数大于若某一个非基变量的检验数大于0 0，其系数列向，其系数列向，其系数列向，其系数列向量量量量P Pm+km+k0,0,则原问题无最优解。（则原问题无最优解。（则原问题无最优解。（则原问题无最优解。（无界解的情况）无界解的情况）无界解的情况）无界解的情况）线性规划为求最大化的标准型：线性规划为求最大化的标准型：线性规划为求最小化的标准型时，相应的结线性规划为求最小化的标准型时，相应的结果？果？定理（求最小化的最优解判别准则）定理（求最小化的最优解判别准则）（1）若若若若=C-C=C-CB B B B-1-1A 0 A 0，则对应于基则对应于基则对应于基则对应于基B B的基础可行的基础可行的基础可行的基础可行解解解解x x就是就是就是就是基础最优解，此时的可行基就是最优基。基础最优解，此时的可行基就是最优基。基础最优解，此时的可行基就是最优基。基础最优解，此时的可行基就是最优基。（2）若检验数全大于等于零，且某一个非基变量的若检验数全大于等于零，且某一个非基变量的若检验数全大于等于零，且某一个非基变量的若检验数全大于等于零，且某一个非基变量的检验数为检验数为检验数为检验数为0 0，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。（无穷（无穷（无穷（无穷多最优解情况）多最优解情况）多最优解情况）多最优解情况）（3 3）若存在检验数小于零，但所对应的换入变量）若存在检验数小于零，但所对应的换入变量）若存在检验数小于零，但所对应的换入变量）若存在检验数小于零，但所对应的换入变量X Xm+km+k的系数向量的系数向量的系数向量的系数向量P Pm+km+k0,0,则原问题无最优解。（则原问题无最优解。（则原问题无最优解。（则原问题无最优解。（无界解的情况）无界解的情况）无界解的情况）无界解的情况）确定换入变量时，找小于确定换入变量时，找小于0中的最小者。中的最小者。课堂练习课堂练习用单纯形法求解用单纯形法求解Min S=-x1+2x2x1-x2 -2x1+2x2 6x1,x20s.t.化为标准型化为标准型Max S=x1-2x2-x1+x2+x3 =2x1+2x2 +x4=6x1,x40s.t.XBCBB-1bx1x2x3x4x302-1110不考虑不考虑x406120161-2x3080311x11612010-40-1X*=(6,0,8,0)T Z*=-6单纯形法的进一步讨论：人工变量法（大单纯形法的进一步讨论：人工变量法（大M法）法）当原问题求最大化时，假定人工变当原问题求最大化时，假定人工变量在目标函数中的系数为（量在目标函数中的系数为（-M）（）（M为为任意大正数），目标函数求最大化，必任意大正数），目标函数求最大化，必须把须把人工变量从基变量换出人工变量从基变量换出，否则，不，否则，不可能实现最大化。可能实现最大化。当原问题求最小化时，假定人工变量当原问题求最小化时，假定人工变量在目标函数中的系数为在目标函数中的系数为M（M为任意大正为任意大正数），目标函数求最小化，必须把数），目标函数求最小化，必须把人工变人工变量从基变量换出量从基变量换出，否则，不可能实现最小，否则，不可能实现最小化。化。Max Z=CXAX=bX 0s.t.设问题设问题()：，A中不含中不含I增加人工变量增加人工变量 X人人=（xn+1，xn+m）T，X人人在目标函数中的系数为在目标函数中的系数为-M（M为充分大正数）。为充分大正数）。于是原问题化为于是原问题化为()：Max Z=CX-M X人人AX+IX人人=bX,X人人 0s.t.1 问题问题:2 方法方法:单纯形法求解单纯形法求解(),若若最优基变量中不含最优基变量中不含X人人，则所得解的前，则所得解的前n个分量即为个分量即为X*否则，否则，()无解。无解。3 结论结论:例：例：用单纯形法求解用单纯形法求解Max Z=5x1+3x2+2x3+4x45x1+x2+x3+8x4=102x1+4x2+3x3+2x4=10 x1,x2,x3,x4 0s.t.解：解：增加人工变量增加人工变量x5、x6，则模型化为：，则模型化为：Max Z=5x1+3x2+2x3+4x4-Mx5-Mx65x1+x2+x3+8x4+x5 =102x1+4x2+3x3+2x4 +x6=10 x1,x6 0s.t.Max Z=5x1+3x2+2x3+4x4-Mx5-Mx65x1+x2+x3+8x4+x5 =102x1+4x2+3x3+2x4 +x6=10 x1,x6 0s.t.XBCBB-1bx1x2x3x4x5x6511810243201x5x6-M-M10105+7M 3+5M 2+4M 4+10M005/4501x51234208115x6x4x3x2x1B-1bCBXBx5x6-M-M10105+7M 3+5M 2+4M 4+10M005/45x4x64-M5/45/81/81/81015/23/415/411/4015/2+3/4M005/2+15/4M3/2+11/4M10201x51234208115x6x4x3x2x1B-1bCBXBx5x6-M-M10105+7M 3+5M 2+4M 4+10M005/45x4x64-M5/45/81/81/81015/23/415/4 11/4015/2+3/4M005/2+15/4M3/2+11/4M102x4x24313/501/30121/5111/150200-1/35/31001x51234208115x6x4x3x2x1B-1bCBXBx5x6-M-M10105+7M 3+5M 2+4M 4+10M005/45x4x64-M5/45/81/81/81015/23/415/4 11/4015/2+3/4M005/2+15/4M3/2+11/4M102x4x24313/501/30121/5111/150200-1/35/310 x1x2535/3101/185/35/30113/18-1/30-10/30-4/9X*=(5/3,5/3,0,0)T,Z*=40/3单纯形法总结单纯形法总结1、Min型单纯形表与型单纯形表与Max型的区别仅在于：型的区别仅在于：令令 k=minj 0的的xk进基，当进基，当 0时最优。时最优。2、解的几种情况及其在单纯形表上的体现（、解的几种情况及其在单纯形表上的体现（讨论讨论Max型型）唯一唯一最优解最优解j 0,非基非基0无穷多无穷多最优解最优解j 0有非基有非基k=0无界解无界解有有k 0但但B-1Pk 0无可行解无可行解用大用大M法法求解，最求解，最优基中含优基中含有有X人人退化解退化解有两个有两个或两个或两个以上的以上的min 线性规划的对偶问题线性规划的对偶问题（Dual Programming，简称，简称DP）一、对偶问题的提出和模型一、对偶问题的提出和模型1 1、问题的提出、问题的提出产品组合问题 今有另公司要购买三今有另公司要购买三种资源，至少出价多少，种资源，至少出价多少，才能使原公司出让资源才能使原公司出让资源？Max Z=3 x1+5x2 x1 42x2 123 x1+2x2 18x1,x20s.t.设三种资源价格分别为设三种资源价格分别为y1,y2,y3Min W=4y1+12y2+18y3s.t.y1+3y332y2+2y35y1,y2,y3 0y y1 1y y2 2y y3 3收购总价收购总价收购总价收购总价 出让生产某产品的资源出让生产某产品的资源消耗的价值不低于该产品消耗的价值不低于该产品的利润价值的利润价值Max Z=3 x1+5x2 x1 42x2 123 x1+2x2 18x1,x20s.t.Min W=4y1+12y2+18y3s.t.y1+3y332y2+2y35y1,y2,y3 02 2、模型、模型Max Z=CXAXbX 0s.t.原问题（原问题（P P）：）：对偶问题（对偶问题（D D）：）：Min W=bTYATY CTY 0s.t.Max Z=CXAXbX 0s.t.原问题（原问题（P P）：）：对偶问题（对偶问题（D D）：）：Min W=bTYATY CTY 0s.t.原问题原问题原问题原问题 对偶问题对偶问题对偶问题对偶问题目标函数目标函数目标函数目标函数 maxmaxmaxmax min min min min 目标函数目标函数目标函数目标函数约束条件约束条件约束条件约束条件 =变量变量变量变量无约束无约束无约束无约束 变量符号变量符号变量符号变量符号 无约束无约束无约束无约束 约束条件约束条件约束条件约束条件=3 3、如何求、如何求LPLP模型的对偶问题模型的对偶问题（1 1）若）若LPLP为为MaxMax型，则尽量化成型，则尽量化成(P)(P)形式。形式。(等式、自由变量不用转换等式、自由变量不用转换)（2 2）若）若LPLP为为MinMin型，则尽量化成型，则尽量化成(D)(D)形式。形式。(等式、自由变量不用转换等式、自由变量不用转换)例：写出下面例：写出下面LPLP的对偶的对偶解：解：令令1 1、对称性、对称性（P）与（）与（D）互为对偶）互为对偶二、对偶性质与定理二、对偶性质与定理2 2、弱对偶性、弱对偶性设设X、Y 分别为（分别为（P）、（）、（D）的任一可行解，）的任一可行解，则则证：证：X、Y 为（为（P）、（）、（D）的可行解）的可行解5 5、对偶定理、对偶定理若（若（P）有最优解，则（）有最优解，则（D）也有最优解，且二）也有最优解，且二者最优值相等者最优值相等.3 3、解的最优性、解的最优性设设 、分别为（分别为（P）与（）与（D）的可行解，且）的可行解，且则则4 4、无界性、无界性若（若（P）为无界解，则（）为无界解，则（D）无可行解）无可行解若（若（D）为无界解，则（）为无界解，则（P）无可行解）无可行解6 6、松紧定理（互补松弛性）、松紧定理（互补松弛性）设设 分别为（分别为（P）与（）与（D）的可行解）的可行解例例1.4讲解，掌握对偶问题的基本性质。讲解，掌握对偶问题的基本性质。其对偶问题的最优解为其对偶问题的最优解为试找出原问题的最优解？试找出原问题的最优解？线性规划问题最优解为线性规划问题最优解为线性规划问题最优解为线性规划问题最优解为用对偶问题求原问题的最优解。用对偶问题求原问题的最优解。用对偶问题求原问题的最优解。用对偶问题求原问题的最优解。解：标准型为：解：标准型为：解：标准型为：解：标准型为：对偶问题为：对偶问题为：对偶问题为：对偶问题为：标准型为：标准型为：标准型为：标准型为：代入原问题标准型有：代入原问题标准型有：代入原问题标准型有：代入原问题标准型有：三、对偶问题最优解的经济解释三、对偶问题最优解的经济解释影子价格影子价格 设设DP其最优值为其最优值为Z*(注：与注：与LP最优值同），则根据最优值同），则根据Z*=bT y*=b1y1*+b2y2*+bmym*Z/bi=yi*简单推导：Y*=(y1*,y2*,，ym*）为）为DP的最优解，则的最优解，则yi*表示表示 LP某资源某资源bi 变化变化1个单位对目标个单位对目标 产生的影产生的影响，称响，称 yi*为为 bi的的影子价格影子价格。例、煤电油例的对偶问题的最优解为例、煤电油例的对偶问题的最优解为Y*=(0 1.36 0.52),则煤电油三种资源的影子价格分别为则煤电油三种资源的影子价格分别为0、1.36、0.52影子价格在管理决策中的作用：影子价格在管理决策中的作用：（1）影子价格）影子价格市场价格市场价格 若若影子价格市场价格，则应影子价格市场价格，则应影子价格市场价格，则应影子价格市场价格，则应买进该资源买进该资源卖出该资源卖出该资源（2）影子价格反映了资源的稀缺性，影子价格越）影子价格反映了资源的稀缺性，影子价格越高，则越稀缺高，则越稀缺例如：煤的影子价格为例如：煤的影子价格为0，则表明有剩余，则表明有剩余