matlab常用算法-106人工變量

信息系劉康澤人工變量法人工變量法（無初始可行基求最優(yōu)解）

前面所介紹的單純形方法是：當(dāng)線性規(guī)劃問題有一個現(xiàn)成的可行基時(shí)，如何去求解線性規(guī)劃問題的最優(yōu)解。然而，當(dāng)一個線性規(guī)劃問題不存在現(xiàn)成的初始可行基，甚至連判斷約束方程組的系數(shù)矩陣A是否滿秩、有無可行解都很困難時(shí)，就要采用下面的人工變量先求原線性規(guī)劃問題的第一個可行基，然后再用上述的單純形方法，去求最優(yōu)解或判定無最優(yōu)解。一、大M

法基本思想:

在約束條件中添加人工變量yi

，將yi

作為基變量，迅速得到一組初始可行基，使得單純形算法能夠順利實(shí)施。

注意到人工變量是后加入到原約束方程中的變量，它破壞了原有的約束條件，同時(shí)還要求它對目標(biāo)函數(shù)的取值不造成影響。因此必須讓人工變量

yi

盡快出基，成為非基變量，因?yàn)榉腔兞康娜≈禐?，從而達(dá)到不破壞原有約束且對目標(biāo)函數(shù)的取值不造成影響的目的。

具體的說：若經(jīng)過換基迭代．基變量中無人工變量，則原問題有可行解。若基變量中還有人工變量，并且檢驗(yàn)數(shù)已經(jīng)全部是非正數(shù)，則原問題元可行解。

為此我們修改目標(biāo)函數(shù)，在目標(biāo)函數(shù)中加一個懲罰項(xiàng)M

yi

，其中M

是一個可以任意大的正數(shù)，只要目標(biāo)函數(shù)中還存在大M，則問題將達(dá)不到最小值，這樣在實(shí)現(xiàn)目標(biāo)函數(shù)最小化的過程中，將迫使人工變量逐逐個替換出基。最終得到一組完全由原問題中的變量構(gòu)成的初始可行基。繼續(xù)使用單純形算法，便可以得到問題的最優(yōu)解或判定問題無解。

注意：在換基迭代中，一旦人工變量全部化成非基變量，就可將人工變量所在的列從單純形表中刪除。若此時(shí)尚未得到原問題的最優(yōu)解，則繼續(xù)換基迭代，直至求出最優(yōu)解或判定無最優(yōu)為止。

例、用大M方法求解線性規(guī)劃問題：解：引入松弛變量x3,

x4及剩余變量x5

，(松弛變量與剩余變量不是人工變量)將最大化改為最小化，問題化成標(biāo)準(zhǔn)型：

因無現(xiàn)行的初始可行基，故引入人工變量y1,y2

，使原問題進(jìn)一步化成如下形式：64000－M－Mx32310000100x43201000120y1100001014y20100－10122

列出原始數(shù)據(jù)表:（不是單純形表，因?yàn)榛兞康臋z驗(yàn)數(shù)不是0）6＋M4＋M00－M00x32310000100x43201000120y1100001014y20100－10122將第3行及第4行的－M倍加到檢驗(yàn)數(shù)行，便得到初始單純形表:x1

換基迭代：得下一張單純形表04＋M00－M－5－M0－84＋22Mx303100－2072x402010－4054x1100001014y20100－101220000－4－6－M－4－M－172x300103－2－372x400012－4－254x1100001014x20100－10122x2

此時(shí)人工變量已全部出基,劃去人工變量,得原問題的初始可行基原問題中的變量0000－4－172x30010372x40001254x11000014x20100－122這已經(jīng)是原問題的最優(yōu)表，最優(yōu)解為:

x1=14,

x2=22。

最優(yōu)值為:f

=172。例：用大M方法求解線性規(guī)劃問題標(biāo)準(zhǔn)化:

添加人工變量y

有：得原始數(shù)據(jù)表：1100－M0x3－111000y－310－1131－3M1+M0－M03Mx3－111000y－310－113x2

2－2M0－1－M－M03Mx2－111000y－20－1－113

因?yàn)闄z驗(yàn)數(shù)都≤0，所以此表對應(yīng)的基為最優(yōu)基，

其中人工變量y

＝3M

≠0，人工變量y

仍留在基中，于是原線性規(guī)劃問題無可行解。一般地，設(shè)問題為：對每一個約束方程分別加入人工變量<2>問題（2）達(dá)到最優(yōu)解，但有些人工變量的取值不為0，即人工變量沒有完全出基，此時(shí)原問題（1）無可行解。<3>問題（2）的某張單純形表中的檢驗(yàn)數(shù)λk≥0，且λk下方的系數(shù)列≤0，又人工變量全部取0，此時(shí)原問題（1）無界。<4>問題（2）的某張單純形表中的檢驗(yàn)數(shù)λk≥0，且λk下方的系數(shù)列≤0，，但有些人工變量不等于0，此時(shí)原問題（1）無可行解。<1>問題（2）達(dá)到最優(yōu)解,且人工變量全部取0，此時(shí)在最優(yōu)表中劃去人工變量所在的列，余下的就是原問題的最優(yōu)單純形表，由此得到原問題（1）的最優(yōu)解。對問題（2）使用單純形方法，可能出現(xiàn)如下幾種情況：二、兩階段法基本思想:

兩階段方法是在原線性規(guī)劃問題引入人工變量以后用兩個階段來求解問題的一種方法。

設(shè)原問題為：

第二階段：如果第一階段表明原問題存在可行基，則在第一階段得到可行基對應(yīng)的單純形表上，去掉人工變量所在的行與列，再從這個原問題的可行基出發(fā)，用單純形方法去求解原問題的最優(yōu)解。

第一階段：引入人工變量，構(gòu)造一個輔助問題，用單純形方法求解輔助問題，其目的是為了判斷原問題是否存在可行基；構(gòu)造輔助問題如下：引入人工變量稱基為人造基，

顯然輔助問題（2）有現(xiàn)成的初始可行基：對應(yīng)的基解是：

問題（2）是一個標(biāo)準(zhǔn)的具有m+n個變量的線性規(guī)劃問題，目標(biāo)函數(shù)有一個明顯的下界Z＝0，因此問題（2）必定有最優(yōu)解。于是可用單純形法去求解它。稱這個求解過程為第一階段。在該階段中逐步將人工變量迭代出基，而使原問題中的變量成為基變量。【注1】問題（2）的約束中增加條件

其目的在于：在第一階段的迭代中記錄原問題目標(biāo)函數(shù)的非基變量表示，從而在第一階段結(jié)束時(shí)直接得到原問題初始單純形表中的檢驗(yàn)數(shù)。

【注2】

為得到第一階段的初始單純形表，往往先寫出問題（2）的原始數(shù)據(jù)表，然后將原始數(shù)據(jù)表中對應(yīng)人工變量的行加到首行（檢驗(yàn)數(shù)行）即可。問題（2）的原始數(shù)據(jù)表：00…0－1－1…－10－c1

－c2

…－cn

0a11a12…a1n10…0b1a21a22…a2n010b2

………………………am1am2…amn00…1bm將原始數(shù)據(jù)表中對應(yīng)人工變量的行加到首行（目標(biāo)行）得：…00…0－c1

－c2

…－cn

0a11a12…a1n10…0b1a21a22…a2n01…0b2

………………………am1am2…amn00…1bm第一階段的初始單純形表：

值得注意的是：用單純形方法求出的第一階段（輔助問題）的最優(yōu)基不是原線性規(guī)劃問題的最優(yōu)基。這個最優(yōu)基與原線性規(guī)劃問題的最優(yōu)基有什么關(guān)系？事實(shí)上，求解輔助問題可能出現(xiàn)如下三種情況：

（1）若在輔助問題的最優(yōu)基中最小值取到下界0,且人工變量全部出基，即人工變量全部成為非基變量，而對應(yīng)的m個基變量全部為原問題中的x變量。則這m個基變量就是原問題的初始可行基。

此時(shí)只要在輔助問題最優(yōu)單純形表中劃去人工變量對應(yīng)的列以及首行，便得到原問題初始可行基和所對應(yīng)的單純形表。然后開始對原問題的求解，這就是第二階段。

（2）若在輔助問題的最優(yōu)基中還含有人工變量

y

，但最小值取到下界0,這時(shí)人工變量

y

的取值一定為0（屬于退化情況），

因此輔助問題的這個最優(yōu)基還不是原問題的基（因?yàn)樵兞窟€未能完全進(jìn)基），更談不上是原問題的可行基。

這時(shí)可用主元消去法把原問題中某些非基變量引進(jìn)基，而替換出基變量中的人工變量。再開始第二階段的單純形法。

【注3】：由于人工變量的取值為0，在替換該人工變量出基迭代中，不影響其它變量的取值及目標(biāo)函數(shù)值，也就是說迭代后仍然保持最優(yōu)解和最優(yōu)值。因此在選擇主元時(shí)不必遵循單純形法所規(guī)定的進(jìn)出基原則。只要保證人工變量出基，而原變量進(jìn)基就可以了。

（3）若輔助問題對應(yīng)于最優(yōu)基的目標(biāo)函數(shù)值大于零，即最優(yōu)解minZ＞0，這說明基變量中有人工變量（人工變量的取值大于0），此時(shí)原問題無可行解。

例、某產(chǎn)品重量150克，要用A、B兩種原料制戊，每單位原料成本A種為2元，B種為8元。該產(chǎn)品至少需要含14單位的B種原料，最多需要含20單位的A種原料。每單位原料的重量：A種5克，B種為10克。為使成本最小，該產(chǎn)品中A、B兩種原料應(yīng)各占多少?

解：設(shè)x1,x2

分別為A、B兩種原料的使用量，則問題的數(shù)學(xué)模型為

引入松弛變量x3及剩余變量x4

，使問題化成標(biāo)準(zhǔn)型:

因無現(xiàn)行的初始可行基，引入人工變量y1,y2，構(gòu)造輔助問題：0000－1－10－2－8000y1

5100010150x310100020y3

010－101145110－100164－2－8000y1

5100010150x310100020y3

010－10114第一階段開始第一階段的初始單純形表為：原始數(shù)據(jù)表為：011－5－100640－82040y1

010－501050x110100020y3

010－10114001／2－1－11／100900－2080x2

01－1／201／1005x110100020y3

001／2－1－1／101900000－10000－4116x2

010－10114x110021／502x3001－2－1／5218

因?yàn)榈谝浑A段的檢驗(yàn)數(shù)都≤0，所以此時(shí)的基為最優(yōu)基，

且最優(yōu)解Z＝0，

由于人工變量都巳出基，故可進(jìn)入第二階段：

劃去輔助問題目標(biāo)行（Z

所在的行），

劃去人工變量所在的列，

得原問題相對應(yīng)的單純形表：

又因?yàn)闄z驗(yàn)數(shù)已全部非正，所以此時(shí)的基已是原問題的最優(yōu)基，且最優(yōu)解為

x1＝2，x2

＝14，最優(yōu)值為f

＝116。也就是使用2單位的A種原料和14單位的B種原料時(shí)，可使所需的產(chǎn)品成本達(dá)到最小，最小值為116元。000－4116x2

010－114x110022x3001－218

解：無現(xiàn)行初始可行基，引入人工變量y1,

y2

，得輔助問題：例、第一階段開始原始數(shù)據(jù)表為：00000－1－1013－1000y1

01210104x5

－12111004y2

303100143152000813－1000y1

01210104x5

－12111004y2

30310014第一階段的初始單純形表為：－2101／300－5／34／32301／304／3y1

－2101／301－2／34／3x5

－2202／310－1／38／3x31011／3001／34／3－1000－1／20－3／20500－2／3－3／2－8／3y1

－1000－1／21－1／20x2－1101／31／20－1／64／3x31011／3001／34／3

因第一階段的檢驗(yàn)數(shù)都≤0，所以此時(shí)的基為最優(yōu)基，但人工變量y1

還在基中，選擇－1作為主元，作換基迭代（此時(shí)不必遵循單純形法所的進(jìn)出基