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

1第八节单纯形法的进一步讨论——人工变量人工变量法考虑标准型(M)：分别给每个约束方程硬性加入一个非负变量a11x1+a12x2+…+a1nxn+xn+1=b1(≥0)a12x1+a22x2+…+a2nxn+xn+2=b2(≥0)……………am1x1+am2x2+…+amnxn+xn+m=bm(≥0)n个xn+1,xn+2,…,xn+m称为人工变量。初始基本可行解：(人造基本解)X0=(0,0,…,0,b1,b2,…,bm)T(2.1)基本思想：人造解X0不是原LP问题的基本可行解。但若能通过单纯形法的迭代步骤，将虚拟的人工变量都替换出去，都变为非基变量（即人工变量xn+1=xn+2=…=xn+m=0），则X0的前n个分量就构成原LP问题的一个基本可行解。反之，若经过迭代，不能把人工变量都变为非基变量，则表明原LP问题无可行解。人工变量法大M法或两阶段法4一、大M法若迭代最终得到最优解X*，而且基变量中不含有人工变量，则X*的前n个分量就构成原问题的一个最优基本解；否则，原问题无可行解。若迭代结果是解无界，而且基变量中不含有人工变量，则原问题也解无界；否则，原问题无可行解。一、大M法例：用大M法解下列线性规划012210243423max321321321321321xxxxxxxxxxxxxxxZ、、解：首先将数学模型化为标准形式5,,2,1,012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在单位矩阵，无法建立初始单纯形表。一、大M法故人为添加两个单位向量，得到人工变量单纯形法数学模型：7,,2,1,012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj－其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。一、大M法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi-Mx64-431-101040x5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M-Mx63-650-1013/50x58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——0x531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→jj→jj一、大M法例用大M法求解下述LP问题maxz=3x1–x2–2x33x1+2x2–3x3=6x1–2x2+x3=4x1，x2，x3≥0maxz=3x1–x2–2x33x1+2x2–3x3+x4=6–Mx4x1–2x2+x3+x5=4–Mx5x1，x2，x3，x4，x5≥0s.t.解s.t.一、大M法cj基解x1x2x3x4x53-1-2-M-M比值32-310x4x5641-2101-M-M10M3+4M-1-2+2M00243212/3-11/30x1x53-M20-8/32-1/31-6+2M0-3-8M/31+2M-4M/3-1023-2x1x310-4/31-1/61/231-2/301/61/2-70-5/30-M-5/6-M-1/2minX*=(3,0,1)T,z*=7单纯形法的进一步讨论－人工变量法解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个σk0且aik≤０（i=1，2,…,m）则线性规划具有无界解。4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在人工变量时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。11二、两阶段法两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划问题分两段来求解。第一阶段：要判断原线性规划问题是否存在基本可行解。第二阶段：将第一阶段的最终计算表中的人工变量取消，并将第一阶段最终计算表中的目标函数行的数字换成原问题的目标函数的数字，继续求解，直到得到最优解。两阶段法阶段Ⅰ求解人造极大问题（先将线性规划问题化标准型，并将其约束条件中加入人工变量，得第一阶段的数学模型）maxw=-xn+1-xn+2-…-xn+m或者minw=xn+1+xn+2+…+xn+ms.t.(2.1)因为人工变量xn+1,xn+2,…,xn+m≥0所以maxw≤0(1)若w*0，说明人工变量中至少有一个为正（针对maxw来说），表示原问题无可行解，停止计算；(2)若w*=0，且人工变量都变换为非基变量，说明原问题得到了初始基本可行解，转入阶段Ⅱ：求解原问题；人工变量的系数均为1或-1两阶段法(3)若w*=0，但“基列”存在人工变量，例如该列第l行的基变量xBl是人工变量，同时该行的前n个系数alj全都是0，这说明原问题的该约束方程式多余的，那么删去第l行及xBl列，类似情况全都这样删去相应行、列；转入阶段Ⅱ；(4)若w*=0，且存在人工变量xBl是基变量，但该行的前n个系数中存在alk≠0，则以alk为主元进行一次换基运算，可使原变量xk取代人工变量xBl作为基变量，类似可将这类人工变量全部都由基变量变为非基变量；转入阶段Ⅱ。阶段Ⅱ求解原问题将第一阶段求得的基本可行解对原问题的目标函数进行优化，将目标函数换成原目标函数，建立原问题的初始单纯形表。只需把阶段Ⅰ的最末单纯形表修改如下：(1)人工变量xn+1，xn+2，…，xn+m诸列去掉；(2)把cj行与cj列的数字换成原问题目标函数的相应系数;(3)重新计算z0和σj，用以取代原检验行中相应数字。然后用单纯形法进行迭代，直到运算结束。两阶段法两阶段法例用两阶段法求解下述LP问题maxz=3x1–x2–2x33x1+2x2–3x3=6x1–2x2+x3=4x1，x2，x3≥0解s.t.s.t.3x1+2x2–3x3+x4=6x1–2x2+x3+x5=4x1，x2，x3，x4，x5≥0maxw=–x4–x5第一阶段：先将线性规划问题化标准型，并将其约束条件中加入人工变量，得第一阶段的数学模型两阶段法cj基解x1x2x3x4x5000-1-1比值32-310x4x5641-2101-1-11040-200243212/3-11/30x1x50-120-8/32-1/3120-8/32-4/302min00x1x310-4/31-1/61/231-2/301/61/20000-1-1第一阶段得最优解X*=(3,0,1,0,0)T,w*=0因人工变量x4=x5=0，所以(3,0,1,0,0)T是原线性规划问题的基可行解。两阶段法阶段Ⅱ：求解原问题将阶段一最终表中的人工变量去掉，并填入原问题的目标函数，作单纯形表10-4/3131-2/30x1x3X*=(3,0,1)T,z*=73-1-23-2-70-5/30x1x2x3cj基解单纯形法的进一步讨论－人工变量法单纯性法小结:建立模型个数取值右端项等式或不等式极大或极小新加变量系数两个三个以上xj≥0xj无约束xj≤0bi≥0bi0≤=≥maxZminZxsxa求解图解法、单纯形法单纯形法不处理令xj=xj′-xj″xj′≥0xj″≥0令xj’=-xj不处理约束条件两端同乘以-1加松弛变量xs加入人工变量xa减去xs加入xa不处理令z′=-ZminZ=－maxz′0-M停止Ajjjzc:求0j所有kj即找出max)()0(0jika对任一)0(lklkiiaab计算lkxx替换基变量用非基变量新单纯形表列出下一个ax含有量中是否基变0j非基变量的有某个最优解一唯无可行解最优解无穷多是否环循否否否是是是循环无界解线性规划模型的应用一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。要求解问题的目标函数能用数值指标来反映，且为线性函数存在着多种方案要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述21