最優(yōu)化教案兩階段法與大M法

§4.2兩階段法與大M法————初始可行基的求法求解線性規(guī)劃的步驟是：已知一個初始基本可行解從初始基本可行解出發(fā)，寫出單純型表，求出進(jìn)基離基變量，做主元消去法，求出一個新的基本可行解且使目標(biāo)函數(shù)值得到改善。判斷當(dāng)前基本可行解是否是最優(yōu)解那末，當(dāng)觀察不出來初始基本可行解時，怎么辦？下面介紹的方法是幾種求初始基本可行解的方法4.2.1≥0其中A是矩陣，≥0。若A中有階單位矩陣，則初始基本可行解立即得到。比如，，那么就是一個基本可行解。若A中不包含階單位矩陣，就需要用某種方法求出一個基本可行解。介紹兩階段法之前，先引入人工變量的概念。設(shè)A中不包含階單位矩陣，為使約束方程的系數(shù)矩陣中含有階單位矩陣，把每個方程增加一個非負(fù)變量，令（4.2.2）≥0，≥0即（4.2.3）≥0，≥0顯然，是（4.2.3）向量≥0是人為引入的，它的每個分量成為人工變量。人變量與前面介紹過的松弛變量是兩個不同的概念。松弛變量的作用是把不等式約束改寫成等式約束，改寫前后的兩個問題是等價的。因此，松弛變量是“合法”的變量。而人工變量的引入，改變了原來的約束條件從這個意義上講，它們是“不合法”的變量。第一階段是用單純形方法消去人工變量（如果可能的話）：（4.2.4）≥0，≥0其中是分量全是1的維列向量，是人工變量構(gòu)成的維列向量。由于是（4.2.4）的一個基本可行解，目標(biāo)函數(shù)值在可行域上有下界，因此問題（4.2.4求解（4.2.4），設(shè)得到的最優(yōu)基本可行解是，此時必有下列三種情形之一：這時（4.2.1）無可行解。因為如果（4.2.1）存在可行解則是（4.2.4）的可行解。在此點(diǎn)，問題（4.2.4＜而是目標(biāo)函數(shù)值的最優(yōu)值，矛盾。2.且的分量都是非基變量。這時，個基變量都是原來的變量，又知是（4.2.4）的基本可行解，因此是（4.2.1）的一個基本可行解。3且的某些分量是基變量。這時，可用主元消去法把原來變量中的某些非基變量引進(jìn)基，替換出基變量中的人工變量，再開始兩階段法的第二階段。應(yīng)指出，為替換出人工變量而采用的主元消去，在主元的選擇上，并不要求遵守單純形法確定離進(jìn)基變量的規(guī)則。第二階段，就是從得到的基本可行解出發(fā)，用單純形方法求（4.2.1例4.2.1≥2≥1≤3≥0先引進(jìn)松弛變量，把問題化成標(biāo)準(zhǔn)形式。由于此標(biāo)準(zhǔn)形式中約束方程的系數(shù)矩陣并不包含3階單位矩陣，因此還引進(jìn)人工變量。下面先求解一階段問題：+=2=1=3≥0仍然用主元消去法，主元用框號標(biāo)出。迭代過程如下：11-1001021-10-100111001100320-1-1000302-1101-111-10-10011010110-1202-1100-2101-0100-1000100000-1-10由于所有判別數(shù)≤0，因此達(dá)到最優(yōu)解。在一階段問題的最優(yōu)解中，人工變量都是非基變量。這樣，我們得到初始基本可行解第一階段結(jié)束后，修改最后的單純形表。去掉人工變量和下面的列（也可保留，但人工變量不能再進(jìn)基），把最后的判別數(shù)行按原來問題進(jìn)行修正。其他不變。然后開始第二階段迭代，即極大化目標(biāo)函數(shù)。迭代過程如下：01010000100002-110111-10020-1101103-20040101121000130-11011010026得到（4.2.5）的最優(yōu)解（，）=（3，0），目標(biāo)函數(shù)最優(yōu)值例4.2.2≤2=4=0≥0引進(jìn)松弛變量，把上述問題化成標(biāo)準(zhǔn)形式，再引進(jìn)人工變量，得到下列一階段問題：=2+=4+=0≥0，…，6先用單純形法解一階段問題，迭代如下：其中是目標(biāo)函數(shù)中基變量的系數(shù)構(gòu)成的維行向量，是上表中的第列，是上表中的右端列。-1211002-44-1010410-10010-34-200041001-20-3-210010-10010-10-4-2000，取主元，經(jīng)元消去得到下表：0100100-5-212010-10010再以為主元，進(jìn)行主元消法，得到0100100101000這樣，基變量均為原來的變量，得到原來的問題的一個基本可行解再把表中人工變量對應(yīng)的列去掉（也可保留，但人工變量不能再進(jìn)基），并把判別數(shù)行增加進(jìn)去。正如前面曾經(jīng)指出過的那樣，初表中的判別數(shù)和目標(biāo)函數(shù)值利用定義來計算，即其中是目標(biāo)函數(shù)中基變量的系數(shù)構(gòu)成的維行向量，是上表中的第列，是上表中的右端列。第二階段的初表如下：010100101000000-1此表已是最優(yōu)表。最優(yōu)解是目標(biāo)函數(shù)值的最優(yōu)值例4.2.3+=2+=10≥0引進(jìn)人工變量。解第一階段問題：+=4+=6+=2++=10≥0下面以表格形式給出迭代過程：2-110100411100106100100023020001106040000200-11-21000011-1010410010002002-30014004-600080-11-210000201-1104100100020201-20140402-40080010201002100100020000-1-1100000-2-200第一階段問題已經(jīng)達(dá)到最優(yōu)解。人工變量均取零值，但人工變量是基變量，應(yīng)從基中替換出去。現(xiàn)在修正表中判別數(shù)行。由于，和是基變量，相對的判別數(shù)均為零，只需計算非基變量對應(yīng)的判別數(shù)：在現(xiàn)行基本可行解處的目標(biāo)函數(shù)值去掉人工變量下面的列，得到第二階段的初始單純形表：00120102100120004此表已是最優(yōu)表。得到最優(yōu)解目標(biāo)函數(shù)的最優(yōu)值在兩階段法的第二階段，可以保留人工變量下面的列，好處在于：最初單位矩陣所在的位置，在以后的每個單純形表中，總是存放現(xiàn)行基的逆。但必須注意，正如前面指出的，人工變量絕不可再進(jìn)基。4.2.2大法大法的基本思想是：在約束中增加人工變量，同時修改目標(biāo)函數(shù)，加上罰項，其中是很大的正數(shù)，這樣，在極小化目標(biāo)函數(shù)的過程中，由于大的存在，將迫使人工變量離基。我們?nèi)钥紤]線性規(guī)劃問題≥0（4.2.6）引進(jìn)人工變量，研究下列問題：（4.2.7）≥0，≥0，用單純形方法求解問題（4.2.71.達(dá)到（4.2.7）的最優(yōu)解，且。此時，得到的即為問題（4.2.6）的最優(yōu)解。2.達(dá)到（4.2.7）的最優(yōu)解，且＞0。這時，原（4.2.6）無可行解。因為如果（4.2.6）有可行解，比如說，則，是（4.2.7）的可行解。問題（4.2.7）在這一點(diǎn)的目標(biāo)函數(shù)值（4.2.8）設(shè)（4.2.7則最優(yōu)值（4.2.9）由于是很大的正數(shù)，＞0，因此可以很大，從而由（4.2.8）和（4.2.9）推知＜，這與為最優(yōu)值矛盾。3.（4.2.7）問題不存在有限最優(yōu)值，在單純形表格中，

＞0≤0，這時，問題（4.2.6）無界。理由是：在此情形下，原來的問題必存在一個可行解。由于（4是無界多面集，根據(jù)定理2.1.1和定理3.2.2，存在方向≥0使得＜0(4.2.10)由于可取任意大的正數(shù)，因此由上式可推知。是原來問題的可行域的方向，根據(jù)定理3.2.2，問題(4.2.6)無界。4.問題(4.2.7)不存在有限最優(yōu)值，在單純形表中，＞0，≤0，有些人工變量不等于零，即。這時，(4.2.6)無可行解。例4.2.4用大法求解下列問題≤11≥3≥0引進(jìn)松弛變量和人工變量，用單純形方法解下列問題：=11=3=1≥0在下面的迭代中，選擇最大判別數(shù)時要注意是很大的正數(shù)，它的數(shù)值可超過每個已知的正數(shù)。迭代過程如下：1-2110001121-40-110310-2000110000-23100-1100100-11-2110-20001101000031-22-5120100-11-2110-2000110010-1200140100-11-211009000-2由于是很大的正數(shù)，因此所有的判別數(shù)≤0達(dá)到最優(yōu)解。人工變量。原來問題的最優(yōu)解目標(biāo)函數(shù)最優(yōu)值例：解：引入剩余變量和人工變量，得到新的LP問題2-1-10104-310-101100-10-1-1115-310-10110-30-3輔助問題最優(yōu)解中人工變量，所以原問題無解。4.2.3單個人工變量技巧這是針對常數(shù)項不是非負(fù)向量時，尋求初始基本可行解的方法。我們考慮線性規(guī)劃（4.2.14）≥0MinSt例≥1≥2≥0標(biāo)準(zhǔn)型=-1=-11）讓進(jìn)基，離基變量選例4.2.5≥1≥2≥0先引進(jìn)松弛變量把約束寫成等式，然后再用（-1）乘每個方程的兩端，使系數(shù)矩陣包含二階段單位矩陣，即確定，再引進(jìn)人工變量，得到（4.2.17）≥0把方程組（4.2.17-1110-1-11-201-1-2以第2行第5列元素（-1）為主元，經(jīng)主元消去，得到-231-101-120-112得到（4.2.17）的一個基本可行解。再用兩階段法或大法求解，現(xiàn)在用兩階段法，求解一階段問題≥0迭代過程如下表：-231-101-120-112-120-10210010001-1-12310-2-1340000-10得到一個原來問題的一個基本可行解由此基本可行解開始，進(jìn)行兩階段法的第二階段，本階段的起始單純形表為01-1-1310-2-1400-4-310判別數(shù)均非正，已達(dá)到原來問題的最優(yōu)解。這個最優(yōu)解是目標(biāo)函數(shù)的最優(yōu)值利用單個人工變量時，關(guān)于原來問題的解的狀況的討論，與前面關(guān)于兩階段法和大法的討論類似，這里不再重復(fù)?！?.3退化情形4.3.1循環(huán)現(xiàn)象我們曾經(jīng)指出，當(dāng)線性規(guī)劃存在最優(yōu)解時，在非退化的情形下，單純形方法經(jīng)有限次迭代必達(dá)最優(yōu)解，然而，對于退化情形，當(dāng)最優(yōu)解存在時，用前面介紹的方法，有可能經(jīng)有限次迭代求不出最優(yōu)解，即出現(xiàn)循環(huán)現(xiàn)象。事實上，已經(jīng)有人給出循環(huán)例子。下面的例題是給出的。例4.3.1用單純形方法解下列問題:≥0下面列出迭代情況：