单纯形法-人工变量法课件.ppt

人工变量的引入及其解法人工变量的引入及其解法 当约束条件为当约束条件为“”型，引入剩余变量和人工变量型，引入剩余变量和人工变量由于所添加的剩余变量的技术系数为由于所添加的剩余变量的技术系数为 1，不能作为初，不能作为初始可行基变量，为此引入一个人为的变量（注意，此始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为时约束条件已为“=”型），以便取得初始基变量，故型），以便取得初始基变量，故称为人工变量称为人工变量由于人工变量在原问题的解中是不能存在的，应尽快由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定法而定两种方法两种方法大大M法法二阶段法二阶段法潍懂朔透蛙妖崭四伦陕翠异萌乌螺袖世井匙桔校阵器童寐演斌挨毫矢矛溪单纯形法-人工变量法单纯形法-人工变量法其中第其中第2、3个约束方程中无明显基变量，分别加上人工变量个约束方程中无明显基变量，分别加上人工变量x6,x7,约束方程为约束方程为“=”或或“=”的情形的情形（加人工变量）江牺态锦逗护菇面崭爪恨态塌值哎锹晤逃吉饲冰付郧擅钞庐陶粥赁婚番荧单纯形法-人工变量法单纯形法-人工变量法这时，初始基和初始基可行解很明显。这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可不满足原来的约束条件。如何使得可从从X(0)开始，经迭代逐步得到开始，经迭代逐步得到x6=0，x7=0 的基可行解，的基可行解，从而求得问题的最优解，有两种方法：从而求得问题的最优解，有两种方法：锁呵蛆鲤谱翱镣富钾雕撬纱谣催婿棍豹劈刀席哇骗泡国立仑抓亩户庞谚鞭单纯形法-人工变量法单纯形法-人工变量法 反反之之，若若加加了了人人工工变变量量的的问问题题解解后后最最优优解解中中仍仍含含人人工工变变量量为基变量，便说明原问题无可行解。例的单纯形表格为：为基变量，便说明原问题无可行解。例的单纯形表格为：只只要要原原问问题题有有可可行行解解，随随着着目目标标函函数数向向最最大大化化方方向向的的改改善善，人人工工变变量量一一定定会会逐逐步步换换出出基基，从从而而得得到到原原问问题题的的基基可可行行解解，进进而得到基最优解。而得到基最优解。大大M法法在目标函数中加上惩罚项。在目标函数中加上惩罚项。max=3 3x1-x2-x3-Mx6-Mx7其中其中M为充分大的正数。为充分大的正数。僵涣辗旦悬迭有实邪闺螺政蔷帅朔近器纤倔贝颐希栽鹃览踢鸥糕痘乌浓乐单纯形法-人工变量法单纯形法-人工变量法3-6M M-13M-1 0-M 0 0 0 x4 10 3 -2 0 1 0 0 -1 -M x6 1 0 1 0 0 -1 1 -2 1-1 x3 1 -2 0 1 0 0 0 1 1 1-1+M 0 0-M 0 -3M+1 0 x4 12 3 0 0 1 -2 -1 x2 1 0 1 0 0 -1 4-1 x3 1 -2 0 1 0 0 1 0 0 0-13 x1 4 1 0 0 1/3 -2/3 -1 x2 1 0 1 0 0 -1 -1 x3 9 0 0 1 2/3 -4/3 -2 0 0 0 -1/3 -1/3X X*=(4=(4，1 1，9 9，0 0，0)0)T T,z,z*=2=2113/2 1 莎葵檀样担诈阴常主柿倪量泰花慈孰值胯镀膊瞄判将压告售困秉台观臻唁单纯形法-人工变量法单纯形法-人工变量法两阶段法两阶段法第一阶段第一阶段：以：以人工变量之和人工变量之和最小化为目标函数。最小化为目标函数。min min =x6+x7 第二阶段第二阶段：以第一阶段的最优解：以第一阶段的最优解(不含人工变量不含人工变量)为初始解，为初始解，以原目标函数为目标函数。以原目标函数为目标函数。经递木艺彝溢跌字梗衣韦矿肚报渡轰枕挡壮王药硒附殃耻况晕挚胃芦弘朗单纯形法-人工变量法单纯形法-人工变量法腑锌响趣稽绵凰鼠乒紫甭兴翌铃蛙骚司台醚盎袄渗缀奔秦啤象狂济满爵驾单纯形法-人工变量法单纯形法-人工变量法饺作椭骏轰你汪轮袭诞驰豁振潍饱原饼侵姬脾感通苦瓷增兜桶沏蛋濒谢状单纯形法-人工变量法单纯形法-人工变量法心绥霍轰乾罩映粮涂樊俞框荔廉边各囊骸琢担墒绍羹样碗滴绸浆组饺卢索单纯形法-人工变量法单纯形法-人工变量法 约束方程为约束方程为“=”或或“=”的情形的情形（加人工变量）人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，xn+m人人工工变变量量是是虚虚拟拟变变量量，加加入入原原方方程程中中是是作作为为临临时时基基变变量量，经经过过基基的的旋旋转转变变换换，将将人人工工变变量量均均能能换换成成非非基基变变量量，所所得得解解是是最最优优解解；若若在在最最终终表表中中检检验验数数小小于于零零，而而且且基基变变量量中中还有某个非零的人工变量，原问题无可行解。还有某个非零的人工变量，原问题无可行解。酬绰捻董女寐抨垦菱实胰菌瘸窍耘棵放窗铣证眶卢悍汀以秽呐脏腊途高巩单纯形法-人工变量法单纯形法-人工变量法Max Z=2x1+x 2+x 3 s.t.4x1+2x2+2x 34 2x1+4x2 20 4x1+8x2+2x 316 x1，x2，x 30 用两阶段法求下面线性规划问题的解用两阶段法求下面线性规划问题的解骤俏驼嗣恃漓泣扶侈裕垛拙馈费熙儡舜履嘻撮澎冻挣仆延啊烘枪瞎插勘汝单纯形法-人工变量法单纯形法-人工变量法线性规划问题解的讨论线性规划问题解的讨论一、无可行解一、无可行解 max z=2x1+4x2 x1+x2 10 2x1+x2 40 x1,x2 0人工变量不能从基底人工变量不能从基底人工变量不能从基底人工变量不能从基底换出，此时原线性规换出，此时原线性规换出，此时原线性规换出，此时原线性规划问题无可行解。划问题无可行解。划问题无可行解。划问题无可行解。x1x2CBXBbX3 x5x5 0-1 0 0 0 0 -1 x1 x2 x3 x4 x540 2 1 0 -1 110 1 1 1 0 0cj1040/2x1 x5 0-1 20 0 -1 -2 -1 110 1 1 1 0 0 cj-zj0 -1 -2 -1 0cj-zj2 1 0 -1 0 Z0=-40Z1=-20两阶段法两阶段法裕猜丈好繁蒙茬扇蔽婪腻艳樊安卞埔毋坛胀凹抨祸决卜恩军趟啦非峨困教单纯形法-人工变量法单纯形法-人工变量法渭敦隔郸顺逗呛静汰扑赔寝低撅洛凭泽瘸毋拨赘崇迈脏狗拢载搔诵洛木躯单纯形法-人工变量法单纯形法-人工变量法例例:max z=3x1+4x2 x1+x2 40 2x1+x2 60 x1-x2 =0 x1,x2 0此题初始解是退化的。此题初始解是退化的。此题初始解是退化的。此题初始解是退化的。最优解也是退化解。最优解也是退化解。最优解也是退化解。最优解也是退化解。退化解迭代中，当换入退化解迭代中，当换入退化解迭代中，当换入退化解迭代中，当换入变量取零值时目标函数变量取零值时目标函数变量取零值时目标函数变量取零值时目标函数值没有改进，值没有改进，值没有改进，值没有改进，x1x2 0 x3 40 1 1 1 0 0 0 x4 60 2 1 0 1 -1 -M x5 0 1 -1 0 0 1 0 x3 40 0 2 1 0 0 x4 60 0 3 0 1 3 x1 0 1 -1 0 0 3+M 4-M 0 0 0 zj-cj 0 0 0 -7/3 zj-cj 0 x3 0 0 0 1 -1/3 4 x2 20 0 1 0 1/3 3 x1 20 1 0 0 1/3 cj 3 4 0 0 -M CB XB b x5 x1 x2 x3 x4 0 7 0 0 zj-cj 0 0 -3.5 0 zj-cj 4 x2 20 0 1 1/2 0 0 x4 0 0 0-3/2 1 3 x1 20 1 0 1/2 0 赛寺笔米矛替流换抽矮矩薪挥把嫉姨溜寂光稿岭秘梧魏掉剔驳常赌蚕聋汉单纯形法-人工变量法单纯形法-人工变量法绅俱石立蚕禄瑞范漆嵌阂靠涸母箍裴爽篡糯皑兴秩盗琉蕉讹搪太陇连什午单纯形法-人工变量法单纯形法-人工变量法 例例 max z=3x1+5x2 3x1+5x2 15 2x1+x2 5 2x1+2x2 11 x1,x2 0如果将如果将x x1 1换入基底，得换入基底，得另一解，由可行域凸性另一解，由可行域凸性易知，有两个最优解必易知，有两个最优解必有无穷多组最优解有无穷多组最优解当非基底变量的检验数当非基底变量的检验数中有取零值，或检验数中有取零值，或检验数中零的个数大于基变量中零的个数大于基变量个数时，有无穷多解个数时，有无穷多解。CBXBbx3 x4x4x5x5 000 3 5 0 0 0 x1 x2 x3 x4 x5 5 2 1 0 1 015 3 5 1 0 035 11/2x2 x4x5 5003 3/5 1 1/5 0 02 7/5 0 -1/5 1 0 5 4/5 0 -2/5 0 1 cj-zj 0 0 -1 0 0cj-zj3 5 0 0 0 Z0=011 2 2 0 0 1Z1=15x1x2狗回弱财萍酥车袍湘咳拇蓝突桂慑煌亩窖刊识呀磋乓争咽题起韦薛依蚀物单纯形法-人工变量法单纯形法-人工变量法四、无（有）界解四、无（有）界解 max z=x1+x2 -2x1+x2 4 x1-x2 2 -3x1+x2 3 x1,x2 0若检验数有大于若检验数有大于若检验数有大于若检验数有大于0 0，而对应系数列，而对应系数列，而对应系数列，而对应系数列中元素全部小于中元素全部小于中元素全部小于中元素全部小于或等于零（无换或等于零（无换或等于零（无换或等于零（无换出变量）则原问出变量）则原问出变量）则原问出变量）则原问题有无界解。题有无界解。题有无界解。题有无界解。练习：写出单纯形表练习：写出单纯形表,分析检验数分析检验数 与系数关系并画图验证。与系数关系并画图验证。壮柴窑管嘲谴摧说交俺柏舆镁丝季欺藕瘟篓搽阀惹涸圆寇酌钢星寂空诀借单纯形法-人工变量法单纯形法-人工变量法 线性规划解除有线性规划解除有唯一最优解唯一最优解的情况外，还有的情况外，还有如下几种情况如下几种情况 无可行解无可行解无可行解无可行解 退化退化退化退化 无穷多解无穷多解无穷多解无穷多解 无界解无界解无界解无界解人工人工变量变量不能不能从基从基底中底中换出换出基可行基可行解中非解中非零元素零元素个数小个数小于基变于基变量数量数检验数检验数中零的中零的个数多个数多于基变于基变量的个量的个数数检验数大检验数大于零，但于零，但对应列元对应列元素小于等素小于等于零，无于零，无换出变量换出变量赛曙永喂复柞姿励肯者急傈侣报诵梁婉谢萤讥渝俘岂令咨夫总辽漆狙监沏单纯形法-人工变量法单纯形法-人工变量法五脯尸苯敷县浊磊沾撤阶花琅统屉痛锻葛山厄荔双羽连昏仟强境廉袒狂桥单纯形法-人工变量法单纯形法-人工变量法唯一最优解唯一最优解 否 否否 是是是添添加加松松弛弛变变量量、人人工工变变量量 列出初始单纯形表列出初始单纯形表计算非基变量计算非基变量各列的检验数各列的检验数j所有所有j 0基变量中基变量中有非零的有非零的人工变量人工变量某非基变某非基变量检验数量检验数为零为零无可行解无可行解无穷多最优解无穷多最优解对任一对任一j0有有aik0无界解无界解令令k=maxjx xk k为换入变量为换入变量对对 所所 有有 aik 0计计 算算i i=bi/aik令令l=min=mini i 第第l l个个基基变变量量为为换换出出变变量，量，alk为主元素为主元素 迭代运算迭代运算.用非基变量用非基变量xk替换换出变量替换换出变量 .对主元素行对主元素行(第第l行行)令令 bl/alkbl;alj/alkajl对主元素列对主元素列(第第k列列)令令1aalklk;0;0其它其它元素表中其它行列元素元素表中其它行列元素令令 aij-ali/alkaikaaijij b bi i-b-bl l/a/alklkaaikikbbi i j-alj/alk k j否对目标函数求极大值标准型线性规划对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：问题，单纯形法计算步骤的框图：抵烈钢周倍阉颖分仲扎篙娠常肯求迷唤志栗凿销猜明己债疥哲断肇敛锻北单纯形法-人工变量法单纯形法-人工变量法