线性规划大M法或两阶段法PPT.ppt

1第八节 单纯形法的进一步讨论人工变量人工变量法人工变量法l 考虑考虑标准型标准型(M)：l 分别给每个约束方程分别给每个约束方程硬性加入硬性加入硬性加入硬性加入一个非负变量一个非负变量l a11x1+a12x2+a1nxn +xn+1n+1 =b1(0)l a12x1+a22x2+a2nxn +xn+2n+2 =b2(0)l l am1x1+am2x2+amnxn +xn+mn+m =bm(0)n个个 xn+1,xn+2,xn+m 称为称为人工变量人工变量。初始基本可行解：初始基本可行解：(人造基本解人造基本解人造基本解人造基本解)X X0 0=(0,0,0,b1,b2,bm)T(2 2.1 1)l l 基本思想：基本思想：基本思想：基本思想：l 人造解人造解 X0 不是原不是原LPLP问题的基本可行解。问题的基本可行解。l 但若能通过单纯形法的迭代步骤，将虚拟但若能通过单纯形法的迭代步骤，将虚拟l 的人工变量都替换出去，都变为非基变量（即的人工变量都替换出去，都变为非基变量（即l 人工变量人工变量xn+1=xn+2=xn+m=0），则），则X0的的l 前前n个分量就构成原个分量就构成原LPLP问题的一个基本可行解。问题的一个基本可行解。l 反之，若经过迭代，不能把人工变量都变反之，若经过迭代，不能把人工变量都变l 为非基变量，则表明原为非基变量，则表明原LPLP问题无可行解。问题无可行解。人工变量法人工变量法大大MM法或两阶段法法或两阶段法4一、大M法 若迭代最终得到若迭代最终得到最优解最优解最优解最优解X*X*，而且，而且基变量基变量基变量基变量中中不含有人工变量不含有人工变量不含有人工变量不含有人工变量，则，则X*X*的的前前n个分量就构成原问题的一个个分量就构成原问题的一个最优基本解最优基本解最优基本解最优基本解；否则，原问题；否则，原问题无可行解无可行解无可行解无可行解。若迭代结果是若迭代结果是解无界解无界解无界解无界，而且，而且基变量基变量基变量基变量中中不含有人工变量不含有人工变量不含有人工变量不含有人工变量，则原问题也则原问题也解无界解无界解无界解无界；否则，原问题；否则，原问题无可行解无可行解无可行解无可行解。一、大M法例：例：用大用大M法解下列法解下列线性性规划划解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。一、大M法故人故人为添加两个添加两个单位向量，得到人工位向量，得到人工变量量单纯形法数学模型：形法数学模型：其其中中：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/3一、大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.(2.1)(2.1)因为人工变量因为人工变量 xn+1,xn+2,xn+m 0 所以所以 max w 0l(1)若若w*0，说明人工变量中至少有一个为正（针对，说明人工变量中至少有一个为正（针对max w来说），表示原问题来说），表示原问题无可行解无可行解，停止计算；，停止计算；l(2)若若若若ww*=0*=0，且人工变量都变换为非基变量，说明原问题，且人工变量都变换为非基变量，说明原问题得到了初始基本可行解，转入得到了初始基本可行解，转入阶段阶段：l 求解原问题；求解原问题；人工变量的系数人工变量的系数均为均为1 1或或-1-1两阶段法两阶段法l(3)若若若若ww*=0 0，但，但“基列基列基列基列”存在人工变量，例如该列第存在人工变量，例如该列第l l 行的基变行的基变量量xBl l是人工变量，同时该行的前是人工变量，同时该行的前n个系数个系数al l j全都是全都是0，这说明，这说明l 原问题的该约束方程式多余的，那么删去第原问题的该约束方程式多余的，那么删去第l l 行及行及xBl l列，类列，类l 似情况全都这样删去相应行、列；转入似情况全都这样删去相应行、列；转入阶段阶段；l(4)若若若若ww*=0 0，且存在人工变量，且存在人工变量xBl l是基变量，但该行的前是基变量，但该行的前n个系个系数数l 中存在中存在al l k0，则以，则以al l k为主元进行一次换基运算，可使原变为主元进行一次换基运算，可使原变l 量量xk取代人工变量取代人工变量xBl l作为基变量，类似可将这类人工变量作为基变量，类似可将这类人工变量全全l 部都由基变量变为非基变量；转入部都由基变量变为非基变量；转入阶段阶段。l 阶段阶段 求解求解原问题原问题原问题原问题l l 将第一阶段求得的基本可行解对原问题的目标函数进行优将第一阶段求得的基本可行解对原问题的目标函数进行优将第一阶段求得的基本可行解对原问题的目标函数进行优将第一阶段求得的基本可行解对原问题的目标函数进行优化，将目标函数换成原目标函数，化，将目标函数换成原目标函数，化，将目标函数换成原目标函数，化，将目标函数换成原目标函数，建立建立原问题原问题原问题原问题的的初始单纯形表初始单纯形表。只需把只需把阶段阶段的的最末单纯形表最末单纯形表最末单纯形表最末单纯形表修改如下：修改如下：l (1)人工变量人工变量 xn+1，xn+2，xn+m诸列去掉；诸列去掉；l (2)把把cj行与行与cj列的数字换成原问题目标函数的相应系数列的数字换成原问题目标函数的相应系数;l (3)重新计算重新计算z0和和j，用以取代原检验行中相应数字。，用以取代原检验行中相应数字。l 然后用单纯形法进行迭代，直到运算结束。然后用单纯形法进行迭代，直到运算结束。两阶段法两阶段法两阶段两阶段法 例例 用用两阶段两阶段法求解下述法求解下述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 -7 7 0 0 -5/3 5/3 0 0 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-MA 线性规划模型的应用一般而言，一个一般而言，一个经济、管理、管理问题凡凡是是满足以下条件足以下条件时，才能建立，才能建立线性性规划模型。划模型。要求解问题的目标函数能用数值指标来反映，且要求解问题的目标函数能用数值指标来反映，且为线性函数为线性函数 存在着多种方案存在着多种方案 要求达到的目标是在一定条件下实现的，这些约要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述束可用线性等式或不等式描述21