线性规划大M法或两阶段法

1第八节 单纯形法的进一步讨论人工变量人工变量法人工变量法 考虑考虑标准型标准型(M)：分别给每个约束方程分别给每个约束方程一个非负变量一个非负变量 a11x1+a12x2+a1nxn +xn+1n+1 =b1(0)a12x1+a22x2+a2nxn +xn+2n+2 =b2(0)am1x1+am2x2+amnxn +xn+mn+m =bm(0)n个个 xn+1,xn+2,xn+m 称为称为人工变量人工变量。初始基本可行解：初始基本可行解：()=(0,0,0,b1,b2,bm)T 人造解人造解 X0 不是原不是原问题的基本可行解。问题的基本可行解。但若能通过单纯形法的迭代步骤，将虚拟但若能通过单纯形法的迭代步骤，将虚拟 的人工变量都替换出去，都变为非基变量（即的人工变量都替换出去，都变为非基变量（即 人工变量人工变量xn+1=xn+2=xn+m=0），则），则X0的的 前前n个分量就构成原个分量就构成原问题的一个基本可行解。问题的一个基本可行解。反之，若经过迭代，不能把人工变量都变反之，若经过迭代，不能把人工变量都变 为非基变量，则表明原为非基变量，则表明原问题问题无可行解无可行解。人工变量法人工变量法大大MM法或两阶段法法或两阶段法4一、大M法 若迭代最终得到若迭代最终得到，而且，而且中中，则，则的的前前n个分量就构成原问题的一个个分量就构成原问题的一个；否则，原问题；否则，原问题。若迭代结果是若迭代结果是，而且，而且中中，则原问题也则原问题也；否则，原问题；否则，原问题。一、大M法例：例：用大用大M法解下列线性规划法解下列线性规划 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先将数学模型化为标准形式 5,2,1,012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。一、大M法故人为添加两个单位向量，得到人工变量单故人为添加两个单位向量，得到人工变量单纯形法数学模型：纯形法数学模型：7,2,1,012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj其中：其中：M是一个很大的抽象的数，不需要给出具体的数值，是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。一、大M法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-Mx64-431-101040 x5101-1201005-Mx712-21000113-2M2+M-1+2M-M-Mx63-650-1013/50 x58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/500 x531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3j j j j 一、大M法 例例 用大用大M法求解下述法求解下述LPLP问题问题 max z=3x1 x2 2x3 3x1+2x2 3x3 =6 x1 2x2 +x3 =4 x1，x2，x3 0 max z=3x1 x2 2x3 3x1+2x2 3x3+x4 =6 Mx4x1 2x2 +x3 +x5 =4Mx5x1，x2，x3，x4，x5 0s.t.解解s.t.一、大M法cj 基基 解解 x1 x2 x3 x4 x5 3 -1-1 -2-2 -M -M比比 值值 3 2 -3 1 0 x4x5 64 1 -2 1 0 1-M-M 10M 3+4M -1 -2+2M 0 0243 2 1 2/3 -1 1/3 0 x1x5 3-M 2 0 -8/3 2 -1/3 1-6+2M 0 -3-8M/3 1+2M-4M/3-1 02 3-2 x1x3 1 0 -4/3 1 -1/6 1/2 3 1 -2/3 0 1/6 1/2-7 0 -5/3 0 -M-5/6 -M-1/2min X*=(3,0,1)T,z*=7 单纯形法的进一步讨论人工变量法解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零）唯一最优解判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。则线性规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个k 0且且aik（i=1，2,m）则线性）则线性规划具有无界解。规划具有无界解。4）无可行解的判断：当用大）无可行解的判断：当用大M单纯形法计算得到最优解并单纯形法计算得到最优解并且存在人工变量时，则表明原线性规划无可行解。且存在人工变量时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。）退化解的判别：存在某个基变量为零的基本可行解。11二、两阶段法两阶段法是处理人工变量的另一种方法，两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划这种方法是将加入人工变量后的线性规划问题分两段来求解。问题分两段来求解。第一阶段：要判断原线性规划问题是否存在基本可行解。第二阶段：将第一阶段的最终计算表中的人工变量取消，并将第一阶段最终计算表中的目标函数行的数字换成原问题的目标函数的数字，继续求解，直到得到最优解。两阶段法两阶段法阶段阶段 求解求解人造极大问题人造极大问题（先将线性规划问题化标准型，并将其约束条件中加入人工变量，得第一阶段的数学模型）max w=-xn+1-xn+2-xn+m或者 min w=xn+1+xn+2+xn+m s.t.因为人工变量因为人工变量 xn+1,xn+2,xn+m 0 所以所以 max w 0(1)若若w*0，说明人工变量中至少有一个为正（针对，说明人工变量中至少有一个为正（针对max w来说），表示原问题来说），表示原问题无可行解无可行解，停止计算；，停止计算；(2)，且人工变量都变换为非基变量，说明原问题得，且人工变量都变换为非基变量，说明原问题得到了初始基本可行解，转入到了初始基本可行解，转入阶段阶段：求解原问题求解原问题；人工变量的系数人工变量的系数均为均为1 1或或-1-1两阶段法两阶段法(3)，但，但“”存在人工变量，例如该列第存在人工变量，例如该列第 行的基变行的基变量量xB是人工变量，同时该行的前是人工变量，同时该行的前n个系数个系数aj全都是全都是0，这说明，这说明 原问题的该约束方程式多余的，那么删去第原问题的该约束方程式多余的，那么删去第 行及行及xB列，类列，类 似情况全都这样删去相应行、列；转入似情况全都这样删去相应行、列；转入阶段阶段；(4)，且存在人工变量，且存在人工变量xB是基变量，但该行的前是基变量，但该行的前n个系数个系数 中存在中存在ak0，则以，则以ak为主元进行一次换基运算，可使原变为主元进行一次换基运算，可使原变 量量xk取代人工变量取代人工变量xB作为基变量，类似可将这类人工变量全作为基变量，类似可将这类人工变量全 部都由基变量变为非基变量；转入部都由基变量变为非基变量；转入阶段阶段。阶段阶段 求解求解建立建立的的初始单纯形表初始单纯形表。只。只需把需把阶段阶段的的修改如下：修改如下：(1)人工变量人工变量 xn+1，xn+2，xn+m诸列去掉；诸列去掉；(2)把把cj行与行与cj列的数字换成原问题目标函数的相应系数列的数字换成原问题目标函数的相应系数;(3)重新计算重新计算z0和和j，用以取代原检验行中相应数字。，用以取代原检验行中相应数字。然后用单纯形法进行迭代，直到运算结束。然后用单纯形法进行迭代，直到运算结束。两阶段法两阶段法两阶段两阶段法 例例 用用两阶段两阶段法求解下述法求解下述LPLP问题问题 max z=3x1 x2 2x3 3x1+2x2 3x3 =6 x1 2x2 +x3 =4 x1，x2，x3 0 解解s.t.s.t.3x1 +2x2 3x3+x4 =6x1 2x2 +x3 +x5 =4x1，x2，x3，x4，x5 0max w=x4 x5第一阶段：先将线性规划问题化标准型，并将其约束条件中加入人工变量，得第一阶段的数学模型两阶段法两阶段法cj 基基 解解 x1 x2 x3 x4 x5 0 0 0 -1 -1比比 值值 3 2 -3 1 0 x4x5 64 1 -2 1 0 1-1-1 10 4 0 -2 0 0243 2 1 2/3 -1 1/3 0 x1x5 0-1 2 0 -8/3 2 -1/3 1 2 0 -8/3 2 -4/3 02min 00 x1x3 1 0 -4/3 1 -1/6 1/2 3 1 -2/3 0 1/6 1/2 0 0 0 0 -1 -1第一阶段得最优解X*=(3,0,1,0,0)T,w*=0因人工变量因人工变量x4=x5=0，所以，所以(3,0,1,0,0)T是原线性规划问是原线性规划问题的基可行解。题的基可行解。两阶段法两阶段法 阶段阶段：求解原问题：求解原问题将阶段一最终表中的人工变量去掉，并填入原将阶段一最终表中的人工变量去掉，并填入原问题的目标函数，作单纯形表问题的目标函数，作单纯形表 1 0 -4/3 1 3 1 -2/3 0 x1x3 X*=(3,0,1)T,z*=7 3 -1 -2 3-2-x1 x2 x3cj基基解解单纯形法的进一步讨论人工变量法单纯性法小结单纯性法小结:建建立立模模型型个个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极小极大或极小新加变量新加变量系数系数两两个个三个三个以上以上xj0 xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa求求解解图图解解法、法、单单纯纯形形法法单纯单纯形法形法不不处处理理令令xj=xj-xj xj 0 xj 0令令 xj=-xj不不处处理理约束条约束条件两端件两端同乘以同乘以-1加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=-ZminZ=max z0-M停止停止Ajjjzc :求求0 j所所有有kj即即找找出出max)()0(0 jika对对任任一一)0(lklkiiaab 计计算算lkxx替替换换基基变变量量用用非非基基变变量量新新单单纯纯形形表表列列出出下下一一个个ax含有含有量中是否量中是否基变基变 0 j非非基基变变量量的的有有某某个个最最优优解解一一唯唯 无无可可行行解解最优解最优解无穷多无穷多是是否否环环循循否否否否否否是是是是是是循环循环无无界界解解 线性规划模型的应用一般而言，一个经济、管理问题凡一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规是满足以下条件时，才能建立线性规划模型。划模型。要求解问题的目标函数能用数值指标来反映，且要求解问题的目标函数能用数值指标来反映，且为线性函数为线性函数 存在着多种方案存在着多种方案 要求达到的目标是在一定条件下实现的，这些约要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述束可用线性等式或不等式描述21