線性規(guī)劃及單純形法課件

第二章

線性規(guī)劃及單純形法§1線性規(guī)劃問(wèn)題及模型§2圖解法§3單純形方法及大M法§4線性規(guī)劃應(yīng)用舉例分析1第二章線性規(guī)劃及單純形法§1線性規(guī)劃問(wèn)題及模型1§1問(wèn)題的提出例1.某工廠在計(jì)劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗、資源的限制，如下表：?jiǎn)栴}：工廠應(yīng)分別生產(chǎn)多少單位Ⅰ、Ⅱ產(chǎn)品才能使工廠獲利最多？線性規(guī)劃模型：目標(biāo)函數(shù)：Maxz=50x1+100x2約束條件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥02§1問(wèn)題的提出例1.某工廠在計(jì)劃期內(nèi)要安排Ⅰ、Ⅱ兩線性規(guī)劃的組成要素：目標(biāo)函數(shù)MaxF或MinF約束條件s.t.(subjectto)滿足于決策變量用符號(hào)來(lái)表示可控制的因素建模步驟1.理解要解決的問(wèn)題，了解解題的目標(biāo)和條件；2.定義決策變量（x1，x2，…，xn），每一組值表示一個(gè)方案；3.用決策變量的線性函數(shù)形式寫(xiě)出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；4.用一組決策變量的等式或不等式表示解決問(wèn)題過(guò)程中必須遵循的約束條件3線性規(guī)劃的組成要素：3一般形式目標(biāo)函數(shù)：Max（Min）z=c1x1+c2x2+…+cnxn約束條件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥04一般形式4對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問(wèn)題的有關(guān)概念，并求解。下面通過(guò)例1詳細(xì)講解其方法。例1.目標(biāo)函數(shù)：Maxz=50x1+100x2約束條件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)§2圖解法5對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，可以在平面直角坐標(biāo)系上作（1）畫(huà)出線性規(guī)劃問(wèn)題的可行域，如圖所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖16（1）畫(huà)出線性規(guī)劃問(wèn)題的可行域，如圖所示。x1x2x2=0x（2）目標(biāo)函數(shù)z=50x1+100x2，當(dāng)z取某一固定值時(shí)得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱(chēng)之為“等值線”。平行移動(dòng)等值線，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行域內(nèi)實(shí)現(xiàn)了最大化。得到最優(yōu)解：x1=50，x2=250，最優(yōu)目標(biāo)值z(mì)=27500x1x2z=20000=50x1+100x2圖2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE7（2）目標(biāo)函數(shù)z=50x1+100x2，當(dāng)z取某一固定值時(shí)得例2某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購(gòu)進(jìn)125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同的，加工每噸A原料需要2個(gè)小時(shí)，加工每噸B原料需要1小時(shí)，而公司總共有600個(gè)加工小時(shí)。又知道每噸A原料的價(jià)格為2萬(wàn)元，每噸B原料的價(jià)格為3萬(wàn)元，試問(wèn)在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買(mǎi)A，B兩種原料，使得購(gòu)進(jìn)成本最低？8例2某公司由于生產(chǎn)需要，共需要A，B兩種原料至少3解：目標(biāo)函數(shù)：Minf=2x1+3x2約束條件：s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0采用圖解法。如下圖：得Q點(diǎn)坐標(biāo)（250，100）為最優(yōu)解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q9解：目標(biāo)函數(shù)：Minf=2x1+3x21重要結(jié)論：如果線性規(guī)劃有最優(yōu)解，則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解；無(wú)窮多個(gè)最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)閙axz=50x1+50x2，則線段BC上的所有點(diǎn)都代表了最優(yōu)解；無(wú)界解。即可行域的范圍延伸到無(wú)窮遠(yuǎn)，目標(biāo)函數(shù)值可以無(wú)窮大或無(wú)窮小。一般來(lái)說(shuō)，這說(shuō)明模型有錯(cuò)，忽略了一些必要的約束條件；無(wú)可行解。若在例1的數(shù)學(xué)模型中再增加一個(gè)約束條件4x1+3x2≥1200，則可行域?yàn)榭沼?，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。10重要結(jié)論：10線性規(guī)劃的標(biāo)準(zhǔn)化——引入松馳變量（含義是資源的剩余量）例1中引入s1，s2，s3模型化為目標(biāo)函數(shù)：Maxz=50x1+100x2+0s1+0s2+0s3約束條件：s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=

250x1,x2,s1,s2,s3≥0

對(duì)于最優(yōu)解

x1=50x2=250，s1=0s2=50s3=0說(shuō)明：生產(chǎn)50單位Ⅰ產(chǎn)品和250單位Ⅱ產(chǎn)品將消耗完所有可能的設(shè)備臺(tái)時(shí)數(shù)及原料B，但對(duì)原料A則還剩余50千克。11線性規(guī)劃的標(biāo)準(zhǔn)化——引入松馳變量（含義是資源的剩余量）11線性規(guī)劃的標(biāo)準(zhǔn)化線性規(guī)劃標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：Maxz=c1x1+c2x2+…+cnxn約束條件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0，bi≥012線性規(guī)劃的標(biāo)準(zhǔn)化12

可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)：目標(biāo)最大化；約束為等式；決策變量均非負(fù)；右端項(xiàng)非負(fù)。對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題，我們總可以通過(guò)以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:13可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特131.極小化目標(biāo)函數(shù)的問(wèn)題：設(shè)目標(biāo)函數(shù)為Minf=c1x1

+c2x2

+…+cnxn

(可以)令z＝-f，則該極小化問(wèn)題與下面的極大化問(wèn)題有相同的最優(yōu)解，即Maxz=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即Minf＝-Maxz141.極小化目標(biāo)函數(shù)的問(wèn)題：142、約束條件不是等式的問(wèn)題：設(shè)約束條件為

ai1x1+ai2x2+…+ainxn

≤bi可以引進(jìn)一個(gè)新的變量s，使它等于約束右邊與左邊之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)顯然，s也具有非負(fù)約束，即s≥0，這時(shí)新的約束條件成為

ai1x1+ai2x2+…+ainxn+s=bi152、約束條件不是等式的問(wèn)題：15當(dāng)約束條件為

ai1x1+ai2x2+…+ainxn

≥bi時(shí)，類(lèi)似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

顯然，s也具有非負(fù)約束，即s≥0，這時(shí)新的約束條件成為

ai1x1+ai2x2+…+ainxn-s=bi16當(dāng)約束條件為16為了使約束由不等式成為等式而引進(jìn)的變量s,當(dāng)不等式為“小于等于”時(shí)稱(chēng)為“松弛變量”；當(dāng)不等式為“大于等于”時(shí)稱(chēng)為“剩余變量”。如果原問(wèn)題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。

3.右端項(xiàng)有負(fù)值的問(wèn)題：

在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如bi<0，則把該等式約束兩端同時(shí)乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi。17為了使約束由不等式成為等式而引進(jìn)的變量s,當(dāng)3.右端例：將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

Minf=2x1-3x2+4x3s.t.3x1

+4x2-5x3≤62x1+x3≥8

x1+x2+x3=-9

x1,x2,x3

≥0

解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令z=-f=-2x1+3x2-4x3

其次考慮約束，有2個(gè)不等式約束，引進(jìn)松弛變量x4，x5

≥0。第三個(gè)約束條件的右端值為負(fù)，在等式兩邊同時(shí)乘-1。18例：將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

18通過(guò)以上變換，可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題：Maxz=-2x1

+3x2-4x3s.t.3x1+4x2-5x3+x4=62x1+x3-x5=8-x1-x2-x3=9

x1,x2,x3,x4,x5

≥0

在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。當(dāng)某一個(gè)變量xj沒(méi)有非負(fù)約束時(shí)，可以令

xj=xj’-xj”其中

xj’≥0，xj”≥0即用兩個(gè)非負(fù)變量之差來(lái)表示一個(gè)無(wú)符號(hào)限制的變量，當(dāng)然xj的符號(hào)取決于xj’和xj”的大小。19通過(guò)以上變換，可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題：19§3單純形方法及大M法單純形法的基本思路和原理單純形法的表格形式求目標(biāo)函數(shù)值最小的線性規(guī)劃的問(wèn)題的單純形表解法幾種特殊情況20§3單純形方法及大M法單純形法的基本思路和原理201單純形法的基本思路和原理單純形法的基本思路：從可行域中某一個(gè)頂點(diǎn)開(kāi)始，判斷此頂點(diǎn)是否是最優(yōu)解，如不是,則再找另一個(gè)使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱(chēng)之為迭代，再判斷此點(diǎn)是否是最優(yōu)解。直到找到一個(gè)頂點(diǎn)為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問(wèn)題無(wú)最優(yōu)解為止。通過(guò)第二章例1的求解來(lái)介紹單純形法:在加上松弛變量之后我們可得到標(biāo)準(zhǔn)型如下：目標(biāo)函數(shù)：max50x1+100x2

約束條件：x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250.xj≥0（j=1，2）,sj≥0（j=1，2,3）211單純形法的基本思路和原理單純形法的基本思路：從可它的系數(shù)矩陣,

其中pj為系數(shù)矩陣A第j列的向量。A的秩為3,A的秩m小于此方程組的變量的個(gè)數(shù)n，為了找到一個(gè)初始基本可行解，先介紹以下幾個(gè)線性規(guī)劃的基本概念。

基：已知A是約束條件的m×n系數(shù)矩陣，其秩為m。若B是A中m×m階非奇異子矩陣（即可逆矩陣），則稱(chēng)B是線性規(guī)劃問(wèn)題中的一個(gè)基?；蛄浚夯鵅中的一列即稱(chēng)為一個(gè)基向量?；鵅中共有m個(gè)基向量。非基向量：在A中除了基B之外的一列則稱(chēng)之為基B的非基向量。基變量：與基向量pi相應(yīng)的變量xi叫基變量，基變量有m個(gè)。22它的系數(shù)矩陣,22非基變量：與非基向量pj相應(yīng)的變量xj叫非基變量，非基變量有n－m個(gè)。由線性代數(shù)的知識(shí)知道，如果我們?cè)诩s束方程組系數(shù)矩陣中找到一個(gè)基，令這個(gè)基的非基變量為零，再求解這個(gè)m元線性方程組就可得到唯一的解了，這個(gè)解我們稱(chēng)之為線性規(guī)劃的基本解。在此例中我們不妨找到了

為A的一個(gè)基，令這個(gè)基的

非基變量x１，s2為零。這時(shí)約束方程就變?yōu)榛兞康募s束方程：

23非基變量：與非基向量pj相應(yīng)的變量xj叫非基變量，非基變量有x2+s1＝300，x2=400，x2+s3=250.求解得到此線性規(guī)劃的一個(gè)基本解：x1=0，x2=400，s1=－100，s2=0，s3=－150由于在這個(gè)基本解中s1=－100，s3=－150，不滿足該線性規(guī)劃s1≥0，s3≥0的約束條件，顯然不是此線性規(guī)劃的可行解，一個(gè)基本解可以是可行解，也可以是非可行解，它們之間的主要區(qū)別在于其所有變量的解是否滿足非負(fù)的條件。我們把滿足非負(fù)條件的一個(gè)基本解叫做基本可行解，并把這樣的基叫做可行基。24x2+s1＝300，24一般來(lái)說(shuō)判斷一個(gè)基是否是可行基，只有在求出其基本解以后，當(dāng)其基本解所有變量的解都是大于等于零，才能斷定這個(gè)解是基本可行解，這個(gè)基是可行基。那么我們能否在求解之前，就找到一個(gè)可行基呢？也就是說(shuō)我們找到的一個(gè)基能保證在求解之后得到的解一定是基本可行解呢？由于在線性規(guī)劃的標(biāo)準(zhǔn)型中要求bj都大于等于零，如果我們能找到一個(gè)基是單位矩陣，或者說(shuō)一個(gè)基是由單位矩陣的各列向量所組成（至于各列向量的前后順序是無(wú)關(guān)緊要的事）例如，那么顯然所求得的基本解一定是基本可行解，這個(gè)單位矩陣或由單位矩陣各列向量組成的基一定是可行基。實(shí)際上這個(gè)基本可行解中的各個(gè)變量或等于某個(gè)bj或等于零。

25一般來(lái)說(shuō)判斷一個(gè)基是否是可行基，只有在求出其基本解以在本例題中我們就找到了一個(gè)基是單位矩陣。在第一次找可行基時(shí)，所找到的基或?yàn)閱挝痪仃嚮驗(yàn)橛蓡挝痪仃嚨母髁邢蛄克M成，稱(chēng)之為初始可行基，其相應(yīng)的基本可行解叫初始基本可行解。如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將構(gòu)造初始可行基，具體做法在以后詳細(xì)講述。26在本例題中我們就找到了一個(gè)基是單位矩陣。26二、最優(yōu)性檢驗(yàn)所謂最優(yōu)性檢驗(yàn)就是判斷已求得的基本可行解是否是最優(yōu)解。1.最優(yōu)性檢驗(yàn)的依據(jù)——檢驗(yàn)數(shù)σj一般來(lái)說(shuō)目標(biāo)函數(shù)中既包括基變量，又包括非基變量。現(xiàn)在我們要求只用非基變量來(lái)表示目標(biāo)函數(shù)，這只要在約束等式中通過(guò)移項(xiàng)等處理就可以用非基變量來(lái)表示基變量，然后用非基變量的表示式代替目標(biāo)函數(shù)中基變量，這樣目標(biāo)函數(shù)中只含有非基變量了，或者說(shuō)目標(biāo)函數(shù)中基變量的系數(shù)都為零了。此時(shí)目標(biāo)函數(shù)中所有變量的系數(shù)即為各變量的檢驗(yàn)數(shù)，把變量xi的檢驗(yàn)數(shù)記為σi。顯然所有基變量的檢驗(yàn)數(shù)必為零。在本例題中目標(biāo)函數(shù)為50x1+100x2。由于初始可行解中x1，x2為非基變量，所以此目標(biāo)函數(shù)已經(jīng)用非基變量表示了，不需要再代換出基變量了。這樣我們可知σ1=50，σ2=100，σ3=0，σ4=0，σ5=0。27二、最優(yōu)性檢驗(yàn)272.最優(yōu)解判別定理對(duì)于求最大目標(biāo)函數(shù)的問(wèn)題中，對(duì)于某個(gè)基本可行解，如果所有檢驗(yàn)數(shù)≤0，則這個(gè)基本可行解是最優(yōu)解。下面我們用通俗的說(shuō)法來(lái)解釋最優(yōu)解判別定理。設(shè)用非基變量表示的目標(biāo)函數(shù)為如下形式

由于所有的xj的取值范圍為大于等于零，當(dāng)所有的都小于等于零時(shí)，可知是一個(gè)小于等于零的數(shù)，要使z的值最大，顯然只有為零。我們把這些xj取為非基變量(即令這些xj的值為零)，所求得的基本可行解就使目標(biāo)函數(shù)值最大為z0。**對(duì)于求目標(biāo)函數(shù)最小值的情況，只需把≤0改為≥0282.最優(yōu)解判別定理28三、基變換通過(guò)檢驗(yàn)，我們知道這個(gè)初始基本可行解不是最優(yōu)解。下面介紹如何進(jìn)行基變換找到一個(gè)新的可行基，具體的做法是從可行基中換一個(gè)列向量，得到一個(gè)新的可行基，使得求解得到的新的基本可行解，其目標(biāo)函數(shù)值更優(yōu)。為了換基就要確定換入變量與換出變量。1.入基變量的確定從最優(yōu)解判別定理知道，當(dāng)某個(gè)σj＞0時(shí)，非基變量xj變?yōu)榛兞坎蝗×阒悼梢允鼓繕?biāo)函數(shù)值增大，故我們要選基檢驗(yàn)數(shù)大于0的非基變量換到基變量中去（稱(chēng)之為入基變量）。若有兩個(gè)以上的σj＞0，則為了使目標(biāo)函數(shù)增加得更大些，一般選其中的σj最大者的非基變量為入基變量，在本例題中σ2=100是檢驗(yàn)數(shù)中最大的正數(shù)，故選x2為入基變量。29三、基變換292.出基變量的確定在確定了x2為入基變量之后，我們要在原來(lái)的3個(gè)基變量s1，s2，s3中確定一個(gè)出基變量，也就是確定哪一個(gè)基變量變成非基變量呢？

如果把s3作為出基變量，則新的基變量為x2，s1，s2，因?yàn)榉腔兞縳1=s3=0，我們也可以從下式：x2+s1=300，x2+s2=400，x2=250，求出基本解：x1=0，x2=250，s1=50，s2=150，s3=0。因?yàn)榇私鉂M足非負(fù)條件，是基本可行解，故s3可以確定為出基變量。能否在求出基本解以前來(lái)確定出基變量呢？以下就來(lái)看在找出了初始基本可行解和確定了入基變量之后，怎么樣的基變量可以確定為出基變量呢？或者說(shuō)出基變量要具有什么條件呢？

302.出基變量的確定30我們把確定出基變量的方法概括如下：把已確定的入基變量在各約束方程中的正的系數(shù)除以其所在約束方程中的常數(shù)項(xiàng)的值，把其中最小比值所在的約束方程中的原基變量確定為出基變量。這樣在下一步迭代的矩陣變換中可以確保新得到的bj值都大于等于零。在本例題中約束方程為

在第二步中已經(jīng)知道x2為入基變量，我們把各約束方程中x2的為正的系數(shù)除對(duì)應(yīng)的常量，得

31我們把確定出基變量的方法概括如下：把已確定的入基變量其中的值最小，所以可以知道在原基變量中系數(shù)向量為

的基變量s3為出基變量，這樣可知x2，s1，s2為基變量，x1，s3為非基變量。令非基變量為零，得x2+s1=300,x2+s2=400,x2=250.求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150.這時(shí)目標(biāo)函數(shù)值為50x1+100x2=50×0+100×250=25000。顯然比初始基本可行解x1=0,x2=0,s1=300,s3=250時(shí)的目標(biāo)函數(shù)值為0要好得多。下面我們?cè)龠M(jìn)行檢驗(yàn)其最優(yōu)性，如果不是最優(yōu)解還要繼續(xù)進(jìn)行基變換，直至找到最優(yōu)解，或者能夠判斷出線性規(guī)劃無(wú)最優(yōu)解為止。3232在講解單純形法的表格形式之前，先從一般數(shù)學(xué)模型里推導(dǎo)出檢驗(yàn)數(shù)的表達(dá)式?？尚谢鶠閙階單位矩陣的線性規(guī)劃模型如下（假設(shè)其系數(shù)矩陣的前m列是單位矩陣）：以下用表示基變量，用表示非基變量。33在講解單純形法的表格形式之前，先從一般數(shù)學(xué)模把第i個(gè)約束方程移項(xiàng)，就可以用非基變量來(lái)表示基變量xi，把以上的表達(dá)式帶入目標(biāo)函數(shù)，就有其中：34把第i個(gè)約束方程移項(xiàng)，就可以用非基變量來(lái)表示基變量上面假設(shè)x1,x2,…xm是基變量，即第i行約束方程的基變量正好是xi，而經(jīng)過(guò)迭代后，基將發(fā)生變化，計(jì)算zj的式子也會(huì)發(fā)生變化。如果迭代后的第i行約束方程中的基變量為xBi，與xBi相應(yīng)的目標(biāo)函數(shù)系數(shù)為cBi，系數(shù)列向量為則其中，(cB)是由第1列第m行各約束方程中的基變量相應(yīng)的目標(biāo)函數(shù)依次組成的有序行向量。單純形法的表格形式是把用單純形法求出基本可行解、檢驗(yàn)其最優(yōu)性、迭代某步驟都用表格的方式來(lái)計(jì)算求出，其表格的形式有些像增廣矩陣，而其計(jì)算的方法也大體上使用矩陣的行的初等變換。以下用單純形表格來(lái)求解第二章的例1。max50x1+100x2+0·s1+0·s2+0·s3.x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250，x1,x2,s1,s2,s3≥0.把上面的數(shù)據(jù)填入如下的單純形表格35上面假設(shè)x1,x2,…xm是基變量，即第i行約按照線性規(guī)劃模型在表中填入相對(duì)應(yīng)的值，如上表所示；在上表中有一個(gè)m*m的單位矩陣，對(duì)應(yīng)的基變量為s1,s2,s3；在zj行中填入第j列與cB列中對(duì)應(yīng)的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位數(shù)填入0；在行中填入cj-zj所得的值，如；z表示把初始基本可行解代入目標(biāo)函數(shù)求得的目標(biāo)函數(shù)值，即b列*cB列；初始基本可行解為s1=300,s2=400,s3=250,x1=0,x2=0;由于250/1最小，因此確定s3為出基變量；由于，因此確定x2為入基變量。出基變量所在行，入基變量所在列的交匯處為主元，這里是a32=1，在表中畫(huà)圈以示區(qū)別。迭代次數(shù)基變量cBx1x2s3s4s5b比值Bi/ai2501000000s1s2s3000111002101001001300400250300/1400/1250/150100000z=036迭代次數(shù)基變量cBx1x2以下進(jìn)行第一次迭代，其變量為x2,s1,s2,通過(guò)矩陣行的初等變換，求出一個(gè)新的基本可行解，具體的做法用行的初等變換使得x2的系數(shù)向量p2變換成單位向量，由于主元在p2的第3分量上，所以這個(gè)單位向量是也就是主元素變成1。這樣我們又得到的第1次迭代的單純表如下所示。在上表中第3個(gè)基變量s1已被x2代替，故基變量列中的第3個(gè)基變量應(yīng)變?yōu)閤2。由于第0次迭代表中的主元a32已經(jīng)為1，因此第3行不變。為了使第1行的a12為0，只需把第3行*(-1)加到第1行即可。同樣可以求得第2行。求得第1次迭代的基本可行解為s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.迭代次數(shù)基變量cBx1x2s3s4s5b比值bi/aij501000001s1s2x2001001010-12001-1010015015025050/1150/2—50000-1002500037以下進(jìn)行第一次迭代，其變量為x2,s1,s2,通過(guò)矩陣行的初從上表可以看出，第一次迭代的，因此不是最優(yōu)解。設(shè)x1為入基變量，從此值可知b1/a11=50為最小正數(shù)，因此，s1為出基變量，a11為主元，繼續(xù)迭代如下表所示。從上表中可知第二次迭代得到的基本可行解為x1=50,x2=250,s1=0,s2=50,s3=0,這時(shí)z=27500。由于檢驗(yàn)數(shù)都<0，因此所求得的基本可行解為最優(yōu)解，z=27500為最優(yōu)目標(biāo)函數(shù)值。實(shí)際上，我們可以連續(xù)地使用一個(gè)單純形表，不必一次迭代重畫(huà)一個(gè)表頭。迭代次數(shù)基變量cBx1x2s3s4s5b比值bi/aij501000002x1s2x25001001010-100-211010015050250

00-500-502750038從上表可以看出，第一次迭代的以例2來(lái)講解如何用單純形表的方法求解目標(biāo)函數(shù)值最小的線性規(guī)劃問(wèn)題。目標(biāo)函數(shù)：約束條件：加入松弛變量和剩余變量變?yōu)闃?biāo)準(zhǔn)型，得到新的約束條件如下：

大M法

39以例2來(lái)講解如何用單純形表的方法求解目標(biāo)函數(shù)值最小的線性規(guī)劃

至于目標(biāo)函數(shù)，在標(biāo)準(zhǔn)型中并不一定要求求最大值或最小值，但是為了使單純形表解法有一個(gè)統(tǒng)一的解法，我們把所有求目標(biāo)函數(shù)最小值的問(wèn)題化成求目標(biāo)函數(shù)最大值的問(wèn)題。具體做法只要把目標(biāo)函數(shù)乘以（－1）。

要注意到人工變量是與松弛、剩余變量不同的。松弛變量、剩余變量它們可以取零值，也可以取正值，而人工變量只能取零值。一旦人工變量取正值，那么有人工變量的約束方程和原始的約束方程就不等價(jià)了，這樣所求得的解就不是原線性規(guī)劃的解了。為了竭盡全力地要求人工變量為零，我們規(guī)定人工變量在目標(biāo)函數(shù)中的系數(shù)為－M，這里M為任意大的數(shù)。這樣只要人工變量M＞0，所求的目標(biāo)函數(shù)最大值就是一個(gè)任意小的數(shù)。這樣為了使目標(biāo)函數(shù)實(shí)現(xiàn)最大就必須把人工變量從基變量中換出。如果一直到最后，人工變量仍不能從基變量中換出，也就是說(shuō)人工變量仍不為零，則該問(wèn)題無(wú)可行解。40至于目標(biāo)函數(shù)，在標(biāo)準(zhǔn)型中并不一定要求求最大值或最小此例的數(shù)學(xué)模型如下所示：目標(biāo)函數(shù)：maxz=－2x1－3x2－Ma1－Ma2.

約束條件：x1+x2－s1+a1=350，x1－s2+a2=125，2x1+x2+s3=600，x1，x2，s1，s2，s3，a1，a2≥0.像這樣，為了構(gòu)造初始可行基得到初始可行解，把人工變量“強(qiáng)行”地加到原來(lái)的約束方程中去，又為了盡力地把人工變量從基變量中替換出來(lái)就令人工變量在求最大值的目標(biāo)函數(shù)里的系數(shù)為－M，這個(gè)方法叫做大M法，M叫做罰因子。

41此例的數(shù)學(xué)模型如下所示：41下面我們就用大M法來(lái)求解此題:迭代次數(shù)基變量cBx1x2s1s2s3a1a2b比值-2-3000-M-M0a1a2a3-M-10012100100350125600350/1125/1600/2zj-2M-MMM0-M-M-2+2M-3+M-M-M000-475M1a1x2s3-M-2001-1001-1100-1001010210-2225125350225-----350/2zj

-2-MM-M+20-M-M-20-3+M-MM-2002-2M-225M-2502a1x1s2-M-2001/2-10-1/21011/2001/20001/20111/2300/1/2175/1/2zj

-2-1/2M-1M01/2M-1-M001/2M-2-M0-1/2M+10-M-50M-60042下面我們就用大M法來(lái)求解此題:迭代次數(shù)基變量cBx1從上表中可知檢驗(yàn)數(shù)都小于零。已求得最優(yōu)解為：x1=250,x2=100,s1=0,s2=125,s3=0,a1=0,a2=0，其最優(yōu)值為f=-z=-(-800)=800。迭代次數(shù)基變量cBx1x2s1s2s3a1a2b比值

-2-3000-M-M3x2x1s2-3-2001-20-12010101-1000111-1-1100250125

zj

-2-3401-4000-40-1-M+4-M

-80043迭代次數(shù)基變量cBx1x2二、兩階段法兩階段法是處理人工變量的另一種方法，這種方法是將加入人工變量后的線性規(guī)劃劃分兩階段求解，仍以上面的例題為例，闡述兩階段法的求解過(guò)程。第一階段：要判斷原線性規(guī)劃是否有基可行解，方法是先求解下列線性規(guī)劃問(wèn)題：目標(biāo)函數(shù)：約束條件：44二、兩階段法44

注意：此線性規(guī)劃的約束條件與原線性規(guī)劃一樣，而目標(biāo)函數(shù)是求人工變量的相反數(shù)之和的最大值。如果此值大于零，則不存在使所有人工變量都為零的可行解，停止計(jì)算。如果此值為零，即說(shuō)明存在一個(gè)可行解，使得所有的人工變量都為零。第二階段：將第一階段的最終單純形表中的人工變量取消，將目標(biāo)函數(shù)換成原問(wèn)題的目標(biāo)函數(shù)，把此可行解作為初始可行解進(jìn)行計(jì)算。45注意：此線性規(guī)劃的約束條件與原線性規(guī)迭代次數(shù)基變量cBx1x2s1s2s3a1a2b比值-2-3000-1-10a1a2s3-1-1011-10010100-10012100100350125600350/1125/1600/2zj-2-1110-1-1-21-1-1000-4701a1x1s3-10001-1101-1100-1001010210-2225125350zj

0-11-10-1101-110022252x2x1s300001-11010100-100100111-1-1225125125zj

000000000000-1-1046迭代次數(shù)基變量cBx1x2迭代次數(shù)基變量cBx1x2s1s2s3b比值-2-30000x2x1s3-3-2001-110100-1001021225125125225/1125/2zj-2-33-1000-310-9251x2x1s2-3-2001-20-11010100111100250125zj

-2-340100-40-1-800從表中可知其基本可行解x1=250,x2=100,s1=0,s2=125,s3=0是本例的最優(yōu)解，其最優(yōu)值為z=-(-800)=800。47迭代次數(shù)基變量cBx1x2

一、無(wú)可行解例1、用單純形表求解下列線性規(guī)劃問(wèn)題解：在上述問(wèn)題的約束條件中加入松馳變量、剩余變量、人工變量得到：填入單純形表計(jì)算得：48一、無(wú)可行解解：在上述問(wèn)題的約束條件中加入松馳變量、剩余變迭代次數(shù)基變量CBx1x2s1s2s3a1b比值2030000-M0s1s2a100-M31010001001001100-111503040150/10—40/1zjcj-zj-M-M00M-M20+M30+M00-M0-40M1x2s2a1300-M3/1011/100001001007/100-1/100-1115302515/(3/10)30/125/(7/10)zjcj-zj9-7/10M303+M/100M-M11+7/10M0-3-M/100-M0450-25M2x2x1a13020-M011/10-3/100010010000-1/10-7/10-116304zjcj-zj20303+M/1011+7M/10M-M00-3-M/10-11-7M/10-M0780-4M49迭代次數(shù)基變量CBx1x2

從第二次迭代的檢驗(yàn)數(shù)都小于零來(lái)看，可知第2次迭代所得的基本可行解已經(jīng)是最優(yōu)解了，其最大的目標(biāo)函數(shù)值為780-4M。我們把最優(yōu)解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三個(gè)約束方程得x1+x2-0+4=40,即有：x1+x2=36≤40.并不滿足原來(lái)的約束條件3，可知原線性規(guī)劃問(wèn)題無(wú)可行解，或者說(shuō)其可行解域?yàn)榭占?，?dāng)然更不可能有最優(yōu)解了。像這樣只要求線性規(guī)劃的最優(yōu)解里有人工變量大于零，則此線性規(guī)劃無(wú)可行解。二、無(wú)界解在求目標(biāo)函數(shù)最大值的問(wèn)題中，所謂無(wú)界解是指在約束條件下目標(biāo)函數(shù)值可以取任意的大。下面我們用單純形表來(lái)求第二章中的例子。例2、用單純形表求解下面線性規(guī)劃問(wèn)題。

50從第二次迭代的檢驗(yàn)數(shù)都小于零來(lái)看，可知第2

迭代次數(shù)基變量CBx1x2s1s2b比值11000s1s2001-110-3201161—zjcj-zj0000110001x1s2101-1100-13119zjcj-zj1-11002-101填入單純形表計(jì)算得：解：在上述問(wèn)題的約束條件中加入松馳變量，得標(biāo)準(zhǔn)型如下：51迭代次數(shù)基變量CBx1x2

從單純形表中，從第一次迭代的檢驗(yàn)數(shù)等于2，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最優(yōu)解。同時(shí)我們也知道如果進(jìn)行第2次迭代，那么就選x2為入基變量，但是在選擇出基變量時(shí)遇到了問(wèn)題：=-1,=-1,找不到大于零的來(lái)確定出基變量。事實(shí)上如果我們碰到這種情況就可以斷定這個(gè)線性規(guī)劃問(wèn)題是無(wú)界的，也就是說(shuō)在此線性規(guī)劃的約束條件下，此目標(biāo)函數(shù)值可以取得無(wú)限大。從1次迭代的單純形表中，得到約束方程：移項(xiàng)可得：52從單純形表中，從第一次迭代的檢驗(yàn)數(shù)等于2，

由于M可以是任意大的正數(shù)，可知此目標(biāo)函數(shù)值無(wú)界。上述的例子告訴了我們?cè)趩渭冃伪碇凶R(shí)別線性規(guī)劃問(wèn)題是無(wú)界的方法：在某次迭代的單純形表中，如果存在著一個(gè)大于零的檢驗(yàn)數(shù)，并且該列的系數(shù)向量的每個(gè)元素aij(i=1,2,…,m)都小于或等于零，則此線性規(guī)劃問(wèn)題是無(wú)界的，一般地說(shuō)此類(lèi)問(wèn)題的出現(xiàn)是由于建模的錯(cuò)誤所引起的。三、無(wú)窮多最優(yōu)解例3、用單純形法表求解下面的線性規(guī)劃問(wèn)題。53由于M可以是任意大的正數(shù)，可知此目標(biāo)函數(shù)值

解：此題我們用圖解法已求了解，現(xiàn)在用單純形表來(lái)求解。填入單純形表計(jì)算得：54解：此題我們用圖解法已求了解，現(xiàn)在用單純形表來(lái)求解迭代次數(shù)基變量CBx1x2s1s2s3b比值50500000s1s2s3000111002101001001300400250300/1400/1250/1zjcj-zj00000505000001s1s2x200501010-12001-1010015015025050/1150/2—zjcj-zj0500050500000125002x1s2x2500501010-100-211010015050250—50/1250/1zjcj-zj5050500000-50001500055迭代次數(shù)基變量CBx1x2

這樣我們求得了最優(yōu)解為x1=50,x2=250,s1=0,s2=50,s3=0,此線性規(guī)劃的最優(yōu)值為15000。這個(gè)最優(yōu)解是否是惟一的呢？由于在第2次迭代的檢驗(yàn)數(shù)中除了基變量的檢驗(yàn)數(shù)等于零外，非基變量s3的檢驗(yàn)數(shù)也等于零，這樣我們可以斷定此線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。不妨我們把檢驗(yàn)數(shù)也為零的非基變量選為入基變量進(jìn)行第3次迭代?？汕蟮昧硪粋€(gè)基本可行解，如下表所示：迭代次數(shù)基變量CBx1x2s1s2s3b50500003x1s3x25005010-11000-21101