二、線性規(guī)劃與目標(biāo)規(guī)劃第2章線性規(guī)劃與單純形法第3章對偶理論與靈敏度分析第4章運(yùn)輸問題第5章線性目標(biāo)規(guī)劃1.二、線性規(guī)劃與目標(biāo)規(guī)劃第2章線性規(guī)劃與單純形法1.第2章線性規(guī)劃與單純形法

第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型第2節(jié)線性規(guī)劃問題的幾何意義第3節(jié)單純形法第4節(jié)單純形法的計算步驟第5節(jié)單純形法的進(jìn)一步討論第6節(jié)應(yīng)用舉例2.第2章線性規(guī)劃與單純形法

第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型2.1.1問題的提出2.1.2圖解法2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)形式2.1.4線性規(guī)劃問題的解的概念3.第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型2.1.1問題的提出3.第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型

線性規(guī)劃是運(yùn)籌學(xué)的一個重要分支。線性規(guī)劃在理論上比較成熟，在實(shí)用中的應(yīng)用日益廣泛與深入。特別是在電子計算機(jī)能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了。從解決技術(shù)問題的最優(yōu)化設(shè)計到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)、軍事、經(jīng)濟(jì)計劃和管理決策等領(lǐng)域都可以發(fā)揮作用。它已是現(xiàn)代科學(xué)管理的重要手段之一。解線性規(guī)劃問題的方法有多種，以下僅介紹單純形法。4.第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃是2.1.1問題的提出2.1.1問題的提出

例1

某工廠在計劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗，如表1-1所示。資源產(chǎn)品ⅠⅡ

擁有量設(shè)備128臺時原材料A4016kg原材料B0412kg每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問應(yīng)如何安排計劃使該工廠獲利最多?

5.2.1.1問題的提出2.1.1問題的提出資源2.1.1問題的提出用數(shù)學(xué)關(guān)系式描述這個問題6.2.1.1問題的提出用數(shù)學(xué)關(guān)系式描述這個問題6.2.1.1問題的提出得到本問題的數(shù)學(xué)模型為:這就是一個最簡單的線性規(guī)劃模型。7.2.1.1問題的提出得到本問題的數(shù)學(xué)模型為:這就是一個最2.1.1問題的提出

例2

靠近某河流有兩個化工廠(見圖1-1)，流經(jīng)第一化工廠的河流流量為每天500萬立方米，在兩個工廠之間有一條流量為每天200萬立方米的支流。

圖1-1化工廠1每天排放含有某種有害物質(zhì)的工業(yè)污水2萬立方米，化工廠2每天排放的工業(yè)污水為1.4萬立方米。從化工廠1排出的污水流到化工廠2前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%。因此兩個工廠都需處理一部分工業(yè)污水?；S1處理污水的成本是1000元/萬立方米,化工廠2處理污水的成本是800元/萬立方米。問:在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使兩個工廠處理工業(yè)污水的總費(fèi)用最小。8.2.1.1問題的提出例2靠近某河流有兩個2.1.1問題的提出設(shè)：化工廠1每天處理的污水量為x1萬立方米；化工廠2每天處理的污水量為x2萬立方米建模型之前的分析和計算9.2.1.1問題的提出設(shè)：建模型之前的分析和計算9.2.1.1問題的提出得到本問題的數(shù)學(xué)模型為：10.2.1.1問題的提出得到本問題的數(shù)學(xué)模型為：10.2.1.1問題的提出每一個線性規(guī)劃問題都用一組決策變量表示某一方案，這組決策變量的值代表一個具體方案。一般這些變量的取值是非負(fù)且連續(xù)的；都有關(guān)于各種資源和資源使用情況的技術(shù)數(shù)據(jù)，創(chuàng)造新價值的數(shù)據(jù)；存在可以量化的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示;都有一個達(dá)到某一目標(biāo)的要求，可用決策變量的線性函數(shù)(稱為目標(biāo)函數(shù))來表示。按問題的要求不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。上述兩個問題具有的共同特征：11.2.1.1問題的提出每一個線性規(guī)劃問題都用一組決策變量上2.1.1問題的提出決策變量及各類系數(shù)之間的對應(yīng)關(guān)系12.2.1.1問題的提出決策變量及各類系數(shù)之間的對應(yīng)關(guān)系122.1.1問題的提出線性規(guī)劃模型的一般形式13.2.1.1問題的提出線性規(guī)劃模型的一般形式13.2.1.2圖解法1.2圖解法例1是一個二維線性規(guī)劃問題，因而可用作圖法直觀地進(jìn)行求解。14.2.1.2圖解法1.2圖解法14.2.1.2圖解法目標(biāo)值在（4，2）點(diǎn)，達(dá)到最大值1415.2.1.2圖解法目標(biāo)值在（4，2）點(diǎn)，達(dá)到最大值14152.1.2圖解法（1）無窮多最優(yōu)解(多重最優(yōu)解)，見圖1-4。（2）無界解，見圖1-5-1。（3）無可行解，見圖1-5-2。通過圖解法，可觀察到線性規(guī)劃的解可能出現(xiàn)的幾種情況：16.2.1.2圖解法（1）無窮多最優(yōu)解(多重最優(yōu)解)，見圖12.1.2圖解法目標(biāo)函數(shù)maxz=2x1+4x2

圖1-4無窮多最優(yōu)解（多重最優(yōu)解）17.2.1.2圖解法目標(biāo)函數(shù)maxz=2x1+4x2.1.2圖解法圖1-5-1無界解18.2.1.2圖解法圖1-5-1無界解18.

當(dāng)存在相互矛盾的約束條件時，線性規(guī)劃問題的可行域?yàn)榭占?。例如，如果在?的數(shù)學(xué)模型中增加一個約束條件:

則該問題的可行域即為空集，即無可行解，無可行解的情形2.1.2圖解法19.當(dāng)存在相互矛盾的約束條件時，線性規(guī)劃問題的可行域?yàn)榭赵黾拥募s束條件圖1-5-2不存在可行域2.1.2圖解法20.增加的約束條件圖1-5-2不存在可行域2.1.2圖解2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式21.2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式2.1.3線性規(guī)劃問2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式用向量形式表示的標(biāo)準(zhǔn)形式線性規(guī)劃線性規(guī)劃問題的幾種表示形式22.2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式用向量形式表示的標(biāo)準(zhǔn)形式2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式用矩陣形式表示的標(biāo)準(zhǔn)形式線性規(guī)劃23.2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式用矩陣形式表示的標(biāo)準(zhǔn)形式2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式(1)若要求目標(biāo)函數(shù)實(shí)現(xiàn)最小化，即minz=CX，則只需將目標(biāo)函數(shù)最小化變換求目標(biāo)函數(shù)最大化，即令z′=?z，于是得到maxz′=?CX。(2)約束條件為不等式。分兩種情況討論：若約束條件為“≤”型不等式，則可在不等式左端加入非負(fù)松弛變量，把原“≤”型不等式變?yōu)榈仁郊s束；若約束條件為“≥”型不等式，則可在不等式左端減去一個非負(fù)剩余變量(也稱松弛變量)，把不等式約束條件變?yōu)榈仁郊s束。(3)若存在取值無約束的變量xk,可令如何將一般線性規(guī)劃轉(zhuǎn)化為標(biāo)準(zhǔn)形式的線性規(guī)劃24.2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式(1)若要求目標(biāo)函數(shù)實(shí)2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式例3

將例1的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式的線性規(guī)劃。例1的數(shù)學(xué)模型在加入了松馳變量后變?yōu)?5.2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式例3將例1的數(shù)學(xué)模型2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式例4

將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)形式線性規(guī)劃(1)用x4?x5替換x3，其中x4，x5≥0；(2)在第一個約束不等式左端加入松弛變量x6；(3)在第二個約束不等式左端減去剩余變量x7；(4)令z′=?z，將求minz

改為求maxz′即可得到該問題的標(biāo)準(zhǔn)型。26.2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式例4將下述線性規(guī)劃問2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式例4

例4的標(biāo)準(zhǔn)型27.2.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式例4例4的標(biāo)準(zhǔn)型272.1.4線性規(guī)劃問題的解概念1.可行解2.基3.基可行解4.可行基28.2.1.4線性規(guī)劃問題的解概念1.可行解28.2.1.4線性規(guī)劃問題的解的概念定義滿足約束條件(1-5)、(1-6)式的解X=(x1,x2，…，xn)T，稱為線性規(guī)劃問題的可行解，其中使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解。1.可行解29.2.1.4線性規(guī)劃問題的解的概念定義1.可行解29.2.1.4線性規(guī)劃問題的解的概念2.基，基向量，基變量30.2.1.4線性規(guī)劃問題的解的概念2.基，基向量，基變2.1.4線性規(guī)劃問題的解的概念滿足非負(fù)條件（1-6）的基解，稱為基可行解.基可行解的非零分量的數(shù)目不大于m，并且都是非負(fù)的。3基可行解31.2.1.4線性規(guī)劃問題的解的概念滿足非負(fù)條件（1-6）的2.1.4線性規(guī)劃問題的解的概念對應(yīng)于基可行解的基，稱為可行基。約束方程組(1-5)具有的基解的數(shù)目最多是個，一般基可行解的數(shù)目要小于基解的數(shù)目。以上提到了幾種解的概念，它們之間的關(guān)系可用圖1-6表明。說明：當(dāng)基解中的非零分量的個數(shù)小于m時，該基解是退化解。在以下討論時，假設(shè)不出現(xiàn)退化的情況。4可行基32.2.1.4線性規(guī)劃問題的解的概念對應(yīng)于基可行解的基，稱為2.1.4線性規(guī)劃問題的解的概念不同解之間的關(guān)系33.2.1.4線性規(guī)劃問題的解的概念不同解之間的關(guān)系33.P552.1（1），2.2（1）(無需列初始單純形表）作業(yè)34.P55作業(yè)34.第2節(jié)線性規(guī)劃問題的幾何意義2.2.1基本概念2.2.2幾個定理35.第2節(jié)線性規(guī)劃問題的幾何意義2.2.1基本概念35.2.2.1基本概念凸集凸組合頂點(diǎn)36.2.2.1基本概念凸集36.2.2.1基本概念定義設(shè)K是n維歐氏空間的一點(diǎn)集，若任意兩點(diǎn)X(1)∈K，X(2)∈K的連線上的所有點(diǎn)αX(1)+(1?α)X(2)∈K，(0≤α≤1)，則稱K為凸集。圖1-71.凸集37.2.2.1基本概念定義圖1-71.凸集37.2.2.1基本概念實(shí)心圓，實(shí)心球體，實(shí)心立方體等都是凸集，圓環(huán)不是凸集。從直觀上講，凸集沒有凹入部分，其內(nèi)部沒有空洞。圖1-7中的(a)(b)是凸集，(c)不是凸集。圖1-2中的陰影部分是凸集。任何兩個凸集的交集是凸集，見圖1-7(d)38.2.2.1基本概念實(shí)心圓，實(shí)心球體，實(shí)心立方體等都是凸集，2.2.1基本概念設(shè)X(1)，X(2)，…，X(k)是n維歐氏空間En中的k個點(diǎn)。若存在μ1，μ2，…，μk，且0≤μi≤1,i=1,2,…，k

使X=μ1X(1)+μ2X(2)+…+μkX(k)

則稱X為X(1)，X(2)，…，X(k)的一個凸組合（當(dāng)0＜μi＜1時，稱為嚴(yán)格凸組合）。2.凸組合39.2.2.1基本概念設(shè)X(1)，X(2)，…，X(k)是n維2.2.1基本概念設(shè)K是凸集，X∈K；若X不能用不同的兩點(diǎn)X(1)∈K和X(2)∈K的線性組合表示為

X=αX(1)+(1?α)X(2)，(0＜α＜1)

則稱X為K的一個頂點(diǎn)(或極點(diǎn))。圖中的0，Q1,Q2,Q3,Q4都是頂點(diǎn)。3.頂點(diǎn)40.2.2.1基本概念設(shè)K是凸集，X∈K；若X不能用不同的兩點(diǎn)2.2.2幾個定理定理1

若線性規(guī)劃問題存在可行域，則其可行域

是凸集。41.2.2.2幾個定理定理1若線性規(guī)劃問題存在可行域，則其2.2.2幾個定理定理1的證明：只需證明D中任意兩點(diǎn)連線上的點(diǎn)必然在D內(nèi)即可。設(shè)是D內(nèi)的任意兩點(diǎn)；且X(1)≠X(2)。42.2.2.2幾個定理定理1的證明：只需證明D中任意兩點(diǎn)連線2.2.2幾個定理43.2.2.2幾個定理43.2.2.2幾個定理引理1

線性規(guī)劃問題的可行解X=(x1,x2,…，xn)T為基可行解的充要條件是：X的正分量所對應(yīng)的系數(shù)列向量是線性獨(dú)立的。44.2.2.2幾個定理引理1線性規(guī)劃問題的可行解X=(2.2.2幾個定理定理2

線性規(guī)劃問題的基可行解X對應(yīng)于可行域D的頂點(diǎn)。證：不失一般性，假設(shè)基可行解X的前m個分量為正。故現(xiàn)分兩步來討論，分別用反證法。45.2.2.2幾個定理定理2線性規(guī)劃問題的基可行解X對應(yīng)2.2.2幾個定理(1)若X不是基可行解，則它一定不是可行域D的頂點(diǎn)。根據(jù)引理1，若X不是基可行解，則其正分量所對應(yīng)的系數(shù)列向量P1，P2，…，Pm線性相關(guān)，即存在一組不全為零的數(shù)αi,i=1,2,…,m，使得

α1P1+α2P2+…+αmPm=0(1-9)用一個數(shù)μ＞0乘(1-9)式再分別與(1-8)式相加和相減，得

(x1?μα1)P1+(x2?μα2)P2+…+(xm?μαm)Pm=b

(x1+μα1)P1+(x2+μα2)P2+…+(xm+μαm)Pm=b

46.2.2.2幾個定理(1)若X不是基可行解，則2.2.2幾個定理

因X不是可行域D的頂點(diǎn)，故在可行域D中可找到不同的兩點(diǎn)

X(1)=(x1(1),x2(1),…,xn(1))T

X(2)=(x1(2),x2(2),…,xn(2))T

使得X=αX(1)+(1?α)X(2)

，

0＜α＜1

設(shè)X是基可行解，對應(yīng)的向量組P1…Pm線性獨(dú)立，故當(dāng)j＞m時，有xj=xj(1)=xj(2)=0。由于X(1)，X(2)是可行域的兩點(diǎn)，因而滿足

（2）若X不是可行域D的頂點(diǎn)，則它一定不是基可行解。將兩式相減，得

因X(1)≠X(2)，所以上式中的系數(shù)不全為零，故向量組P1,P2,…，Pm線性相關(guān)，與假設(shè)矛盾，即X不是基可行解。47.2.2.2幾個定理因X不是可行域D的頂點(diǎn)，故在可行2.2.2幾個定理引理2

若K是有界凸集，則任何一點(diǎn)X∈K可表示為K的頂點(diǎn)的凸組合。

本引理的證明從略，用以下例子說明本引理的結(jié)論。例5

設(shè)X是三角形中任意一點(diǎn)，X(1)，X(2)和X(3)是三角形的三個頂點(diǎn)，試用三個頂點(diǎn)的坐標(biāo)表示X(見圖1-8)圖1-848.2.2.2幾個定理引理2若K是有界凸集，則任何一點(diǎn)2.2.2幾個定理

解：任選一頂點(diǎn)X(2)，做一條連線XX(2)，并延長交于X(1)、X(3)連接線上一點(diǎn)X′。因?yàn)閄′是X(1)、X(3)連線上一點(diǎn)，故可用X(1)、X(3)線性組合表示為X′=αX(1)+(1?α)X(3)0＜α＜1

又因X是X′與X(2)連線上的一個點(diǎn)，故X=λX′+(1?λ)X(2)0＜λ＜1

將X′的表達(dá)式代入上式得到X=λ［αX(1)+(1?α)X(3)］+(1?λ)X(2)=λαX(1)+λ(1?α)X(3)+(1?λ)X(2)

令μ1=αλ,μ2=(1?λ),μ3=λ(1?α)，得到X=μ1X(1)+μ2X(2)+μ3X(3)∑iμi=1,0＜μi＜149.2.2.2幾個定理解：任選一頂點(diǎn)X(2)，做2.2.2幾個定理定理3

若可行域有界，則線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)。證：設(shè)X(1),X(2)，…，X(k)是可行域的頂點(diǎn)，若X(0)不是頂點(diǎn)，且目標(biāo)函數(shù)在X(0)處達(dá)到最優(yōu)z*=CX(0)(標(biāo)準(zhǔn)型是z=maxz)。因X(0)不是頂點(diǎn)，所以它可以用D的頂點(diǎn)線性表示為代入目標(biāo)函數(shù)得50.2.2.2幾個定理定理3若可行域有界，則線性規(guī)劃2.2.2幾個定理在所有的頂點(diǎn)中必然能找到某一個頂點(diǎn)X(m)，使CX(m)是所有CX(i)中最大者。并且將X(m)代替(1-10)式中的所有X(i)，得到由此得到CX(0)≤CX(m)根據(jù)假設(shè)CX(0)是最大值，所以只能有CX(0)=CX(m)即目標(biāo)函數(shù)在頂點(diǎn)X(m)處也達(dá)到最大值。

51.2.2.2幾個定理在所有的頂點(diǎn)中必然能找到某一個頂點(diǎn)X(2.2.2幾個定理有時，目標(biāo)函數(shù)可能在多個頂點(diǎn)處達(dá)到最大，這時在這些頂點(diǎn)的凸組合上也達(dá)到最大值，這時線性規(guī)劃問題有無限多個最優(yōu)解。假設(shè)是目標(biāo)函數(shù)達(dá)到最大值的頂點(diǎn)，則對這些頂點(diǎn)的凸組合，有52.2.2.2幾個定理有時，目標(biāo)函數(shù)可能在多個頂點(diǎn)處達(dá)到最大2.2.2幾個定理設(shè)：于是：另外，若可行域?yàn)闊o界，則可能無最優(yōu)解，也可能有最優(yōu)解，若有最優(yōu)解，也必定在某頂點(diǎn)上得到。53.2.2.2幾個定理設(shè)：53.基本結(jié)論線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，也可能為無界域，它們有有限個頂點(diǎn)，線性規(guī)劃問題的每個基可行解對應(yīng)可行域的一個頂點(diǎn)。若線性規(guī)劃問題有最優(yōu)解，必在某頂點(diǎn)上得到。雖然頂點(diǎn)數(shù)目是有限的，若采用“枚舉法”找所有基可行解，然后一一比較，最終必然能找到最優(yōu)解。但當(dāng)n,m較大時，這種辦法是行不通的，所以要繼續(xù)討論如何有效尋找最優(yōu)解的方法。本課程將主要介紹單純形法。54.基本結(jié)論線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，也可能為無第3節(jié)單純形法2.3.1舉例2.3.2初始基可行解的確定2.3.3最優(yōu)性檢驗(yàn)與解的判斷2.3.4基變換2.3.5迭代（旋轉(zhuǎn)運(yùn)算）55.第3節(jié)單純形法2.3.1舉例55.單純形法求解線性規(guī)劃的思路：

一般線性規(guī)劃問題具有線性方程組的變量數(shù)大于方程個數(shù)，這時有不定的解。但可以從線性方程組中找出一個個的單純形，每一個單純形可以求得一組解，然后再判斷該解使目標(biāo)函數(shù)值是增大還是變小，決定下一步選擇的單純形。這就是迭代，直到目標(biāo)函數(shù)實(shí)現(xiàn)最大值或最小值為止。這樣，問題就得到了最優(yōu)解，先舉一例來說明。56.單純形法求解線性規(guī)劃的思路：一般線性規(guī)劃問題具2.3.1舉例例6

試以例1來討論如何用單純形法求解。解：已知本例的標(biāo)準(zhǔn)型為：57.2.3.1舉例例6試以例1來討論如何用單純形法求解2.3.1舉例約束條件(1-12)式的系數(shù)矩陣為從(1-12)式可看到x3,x4,x5的系數(shù)構(gòu)成的列向量58.2.3.1舉例約束條件(1-12)式的系數(shù)矩陣為58.2.3.1舉例P3

,P4,P5是線性獨(dú)立的，這些向量構(gòu)成一個基B

。對應(yīng)于B的變量x3,x4,x5為基變量.從(1-12)式中可以得到（1-13）59.2.3.1舉例P3,P4,P5是線性獨(dú)立的，這些向量構(gòu)2.3.1舉例將(1-13)式代入目標(biāo)函數(shù)(1-11)：得到當(dāng)令非基變量x1=x2=0，便得到z=0。這時得到一個基可行解X(0)

X(0)=(0,0,8,16,12)T

本基可行解的經(jīng)濟(jì)含義是：工廠沒有安排生產(chǎn)產(chǎn)品Ⅰ、Ⅱ，資源都沒有被利用，所以工廠的利潤為z=0。60.2.3.1舉例將(1-13)式代入目標(biāo)函數(shù)(1-11)：2.3.1舉例

從分析目標(biāo)函數(shù)的表達(dá)式(1-14)可以看到：

非基變量x1,x2(即沒有安排生產(chǎn)產(chǎn)品Ⅰ，Ⅱ)的系數(shù)都是正數(shù)，因此將非基變量變換為基變量，目標(biāo)函數(shù)的值就可能增大。從經(jīng)濟(jì)意義上講，安排生產(chǎn)產(chǎn)品Ⅰ或Ⅱ，就可以使工廠的利潤指標(biāo)增加。所以只要在目標(biāo)函數(shù)(1-14)的表達(dá)式中還存在有正系數(shù)的非基變量，這表示目標(biāo)函數(shù)值還有增加的可能，就需要將非基變量與基變量進(jìn)行對換。61.2.3.1舉例從分析目標(biāo)函數(shù)的表達(dá)式(1-12.3.1舉例如何確定換入、換出變量一般選擇正系數(shù)最大的那個非基變量x2為換入變量，將它換到基變量中，同時還要確定基變量中哪一個換出來成為非基變量?？砂匆韵路椒▉泶_定換出變量：分析(1-13)式，當(dāng)將x2定為換入變量后，必須從x3,x4,x5中確定一個換出變量，并保證其余的變量仍然非負(fù)，即x3,x4,x5≥0。62.2.3.1舉例如何確定換入、換出變量62.2.3.1舉例如何確定換入、換出變量當(dāng)x1=0時，由(1-13)式得到63.2.3.1舉例如何確定換入、換出變量63.2.3.1舉例如何確定換入、換出變量當(dāng)x2取何值時，才能滿足非負(fù)要求呢？從(1-15)式可看出，只有選擇

x2=min(8/2,-,12/4)=3時，才能使(1-15)式成立。因當(dāng)x2=3時，基變量x5=0，這就決定用x2去替換x5。以上數(shù)學(xué)描述說明，每生產(chǎn)一件產(chǎn)品Ⅱ，需要用掉的各種資源數(shù)為(2，0，4)。由這些資源中的薄弱環(huán)節(jié)，就確定了產(chǎn)品Ⅱ的產(chǎn)量。這里就是由原材料B的數(shù)量確定了產(chǎn)品Ⅱ的產(chǎn)量x2=12/4=3件。64.2.3.1舉例如何確定換入、換出變量64.2.3.1舉例如何確定換入、換出變量為了求得以x3,x4,x2為基變量的一個基可行解和進(jìn)一步分析問題，需將(1-13)中x2的位置與x5的位置對換，得到65.2.3.1舉例如何確定換入、換出變量65.2.3.1舉例將(1-16)式中x2的系數(shù)列向量變換為單位列向量。其運(yùn)算步驟是：③′=③/4；①′=①-2×③′;②′=②,并將結(jié)果仍按原順序排列有：高斯消去法66.2.3.1舉例將(1-16)式中x2的系數(shù)列向量變換為單2.3.1舉例再將(1-17)式代入目標(biāo)函數(shù)(1-11)式得到67.2.3.1舉例再將(1-17)式代入目標(biāo)函數(shù)(1-11)2.3.1舉例

從目標(biāo)函數(shù)的表達(dá)式(1-18)可看到，非基變量x1的系數(shù)是正的，說明目標(biāo)函數(shù)值還可以增大，即X(1)還不是最優(yōu)解。于是，再用上述方法確定換入、換出變量，繼續(xù)迭代，得到另一個基可行解X(2)X(2)=(2,3,0,8,0)T

再經(jīng)過一次迭代，又得到一個基可行解X(3)X(3)=(4,2,0,0,4)T

而這時得到目標(biāo)函數(shù)的表達(dá)式是：

z=14?1.5x3?0.125x4(1-19)

再檢查(1-19)式，可見所有非基變量x3,x4的系數(shù)都是負(fù)數(shù)，這說明若要用剩余資源x3,x4，就必須支付附加費(fèi)用。所以當(dāng)x3=x4=0時，即不再利用這些資源時，目標(biāo)函數(shù)達(dá)到最大值。所以X(3)是最優(yōu)解。即當(dāng)產(chǎn)品Ⅰ生產(chǎn)4件，產(chǎn)品Ⅱ生產(chǎn)2件時，工廠可以得到最大利潤。68.2.3.1舉例從目標(biāo)函數(shù)的表達(dá)式(1-18小結(jié)通過上例，可將每步迭代得到的結(jié)果與圖解法做一對比。例1的線性規(guī)劃問題是二維的，即有兩個變量x1,x2。當(dāng)加入松弛變量x3,x4,x5后，變換為高維的。這時可以想象，滿足所有約束條件的可行域是高維空間中的凸多面體(凸集)。該凸多面體上的頂點(diǎn)，就是基可行解。初始基可行解為X(0)=(0,0,8,16,12)T，對應(yīng)于圖1-2中的原點(diǎn)(0，0)；X(1)=(0,3,2,16,0)T對應(yīng)于圖中的Q4點(diǎn)(0，3)；X(2)=(2，3，0，8，0)T對應(yīng)于Q3點(diǎn)(2，3)；最優(yōu)解X(3)=(4，2，0，0，4)T相當(dāng)于圖中的Q2點(diǎn)(4，2)。從初始基可行解X(0)開始迭代，依次得到X(1)，X(2)，X(3)，相當(dāng)于圖中的目標(biāo)函數(shù)平移時，從0點(diǎn)開始，首先碰到Q4，然后碰到Q3，最后達(dá)到Q2。69.小結(jié)通過上例，可將每步迭代得到的結(jié)果與圖解法做一對比。從初始2.3.2初始基可行解的確定為了確定初始基可行解，要首先找出初始可行基，其方法如下。(1)直接觀察(2)加松弛變量(3)加非負(fù)的人工變量70.2.3.2初始基可行解的確定為了確定初始基可行解，要首先2.3.2初始基可行解的確定從線性規(guī)劃問題的系數(shù)構(gòu)成的列向量Pj(j=1,2,…,n)中，通過直接觀察，找出一個初始可行基(1)直接觀察71.2.3.2初始基可行解的確定從線性規(guī)劃問題(1)直接觀察2.3.2初始基可行解的確定

對所有約束條件為“≤”形式的不等式，利用化標(biāo)準(zhǔn)型的方法，在每個約束條件的左端加上一個松弛變量。經(jīng)過整理，重新對xj及aij

(i=1,2,…,m;j=1,2,…,n)進(jìn)行編號，則可得下列方程組（x1,x2,…,xm

為松弛變量）：(2)加松弛變量72.2.3.2初始基可行解的確定對所有約束條件2.3.2初始基可行解的確定于是，(1-22)中含有一個m×m階單位矩陣，初始可行基B即可取該單位矩陣。將(1-22)式每個等式移項得

73.2.3.2初始基可行解的確定于是，(1-22)中含有一個2.3.2初始基可行解的確定令xm+1=xm+2=…=xn=0，由(1-23)式可得xi=bi(i=1,2,…,m)得到一個初始基可行解。又因bi≥0(在1-3節(jié)中已做過規(guī)定)，所以得到一個初始基可行解

X=(x1,x2,…,xm,0，…，0)T

n?m個

=(b1,b2,…,bm,0，…，0)T

n?m個74.2.3.2初始基可行解的確定令xm+1=xm+2=…=x2.3.2初始基可行解的確定對所有約束條件為“≥”形式的不等式及等式約束情況，若不存在單位矩陣時，可采用人造基方法。即對不等式約束，減去一個非負(fù)的剩余變量，再加上一個非負(fù)的人工變量；對于等式約束，再加上一個非負(fù)的人工變量這樣，總能在新的約束條件系數(shù)構(gòu)成的矩陣中得到一個單位矩陣。(3)加非負(fù)的人工變量75.2.3.2初始基可行解的確定對所有約束條件為“≥”形式的2.3.3最優(yōu)性檢驗(yàn)與解的判別由于線性規(guī)劃問題的求解可能出現(xiàn)唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解等四種情況，因此，需要建立解的判別準(zhǔn)則。一般情況下，經(jīng)過迭代后(1-23)式變成

76.2.3.3最優(yōu)性檢驗(yàn)與解的判別由于線性規(guī)劃問題的求解可能出2.3.3最優(yōu)性檢驗(yàn)與解的判別將代入目標(biāo)函數(shù)(1-20)式，整理后得77.2.3.3最優(yōu)性檢驗(yàn)與解的判別將2.3.3最優(yōu)性檢驗(yàn)與解的判別令78.2.3.3最優(yōu)性檢驗(yàn)與解的判別令78.2.3.3最優(yōu)性檢驗(yàn)與解的判別

若為對應(yīng)于基B的一個基可行解，且對于一切j=m+1,…,n，有σj≤0，則X(0)為最優(yōu)解。稱σj為檢驗(yàn)數(shù)。1.最優(yōu)解的判別定理79.2.3.3最優(yōu)性檢驗(yàn)與解的判別若2.3.3最優(yōu)性檢驗(yàn)與解的判別

若為一個基可行解，對于一切j=m+1，…,n，有σj≤0，又存在某個非基變量的檢驗(yàn)數(shù)σm+k=0，則線性規(guī)劃問題有無窮多最優(yōu)解。

證:

只需將非基變量xm+k換入基變量中，找到一個新基可行解X(1)。因σm+k=0，由(1-27)知z=z0，故X(1)也是最優(yōu)解。由2.2節(jié)的定理3可知，X(0)和X(1)連線上所有點(diǎn)都是最優(yōu)解。2.無窮多最優(yōu)解判別定理80.2.3.3最優(yōu)性檢驗(yàn)與解的判別若2.3.3最優(yōu)性檢驗(yàn)與解的判別

若為一基可行解，有一個σm+k＞0，并且對i=1,2,…，m，有a‘i,m+k≤0，那么該線性規(guī)劃問題具有無界解(或稱無最優(yōu)解)。證:

構(gòu)造一個新的解X(1)，它的分量為3．無界解判別定理81.2.3.3最優(yōu)性檢驗(yàn)與解的判別若2.3.3最優(yōu)性檢驗(yàn)與解的判別

因，所以對任意的λ＞0都是可行解，把x(1)代入目標(biāo)函數(shù)內(nèi)，得到z=z0+λσm+k

因σm+k＞0，故當(dāng)λ→+∞，則z→+∞，故該問題目標(biāo)函數(shù)無界。82.2.3.3最優(yōu)性檢驗(yàn)與解的判別因2.3.3最優(yōu)性檢驗(yàn)與解的判別其它情形以上討論都是針對標(biāo)準(zhǔn)型的，即求目標(biāo)函數(shù)極大化時的情況。當(dāng)要求目標(biāo)函數(shù)極小化時，一種情況是將其化為標(biāo)準(zhǔn)型。如果不化為標(biāo)準(zhǔn)型，只需在上述1，2點(diǎn)中把σj≤0改為σj≥0，第3點(diǎn)中將σm+k＞0改寫為σm+k＜0即可。83.2.3.3最優(yōu)性檢驗(yàn)與解的判別其它情形83.2.3.4基變換若初始基可行解X(0)不是最優(yōu)解及不能判別無界時，需要找一個新的基可行解。具體做法是從原可行解基中換一個列向量(當(dāng)然要保證線性獨(dú)立)，得到一個新的可行基，稱為基變換。為了換基，先要確定換入變量，再確定換出變量，讓它們相應(yīng)的系數(shù)列向量進(jìn)行對換，就得到一個新的基可行解。84.2.3.4基變換若初始基可行解X(0)不是最優(yōu)解及不能判別1.換入變量的確定由(1-27)式可知，當(dāng)某些σj＞0時，若xj增大，則目標(biāo)函數(shù)值還可以增大。這時需要將某個非基變量xj換到基變量中去(稱為換入變量)。若有兩個以上的σj＞0，那么選哪個非基變量作為換入變量呢?為了使目標(biāo)函數(shù)值增加得快，從直觀上看應(yīng)選σj＞0中的較大者，即由應(yīng)選擇xk為換入變量。85.1.換入變量的確定由(1-27)式可知，當(dāng)某些σj＞0時，若2.換出變量的確定設(shè)P1，P2，…，Pm是一組線性獨(dú)立的向量組，它們對應(yīng)的基可行解是X(0)，將它代入約束方程組(1-21)得到其他的向量Pm+1,Pm+2,…,Pm+t,…,Pn都可以用P1，P2，…，Pm線性表示。若確定非基變量xm+t為換入變量，必然可以找到一組不全為0的數(shù)(i=1,2,…,m)使得86.2.換出變量的確定設(shè)P1，P2，…，Pm是一組線性獨(dú)立的向量2.換出變量的確定在(1-29)式兩邊同乘一個正數(shù)θ，然后將它加到(1-28)式上，得到

87.2.換出變量的確定在(1-29)式兩邊同乘一個正數(shù)θ，然后將2.換出變量的確定88.2.換出變量的確定88.2.換出變量的確定89.2.換出變量的確定89.2.換出變量的確定新的基可行解為90.2.換出變量的確定新的基可行解為90.2.換出變量的確定由此得到由X(0)轉(zhuǎn)換到X(1)的各分量的轉(zhuǎn)換公式91.2.換出變量的確定由此得到由X(0)轉(zhuǎn)換到X(1)的各分量的2.換出變量的確定這里是原基可行解X(0)的分量；是新基可行解X(1)的各分量；βi,m+t是換入向量Pm+t對應(yīng)原來一組基向量的坐標(biāo)?，F(xiàn)在的問題是，這個新解X(1)的m個非零分量對應(yīng)的列向量是否獨(dú)立?事實(shí)上，因?yàn)閄(0)的第一個分量對應(yīng)于X(1)的相應(yīng)分量是零，即92.2.換出變量的確定這里是原基可行解X(0)的2.換出變量的確定成立。又因?qū)?1-32)式減(1-31)式得到93.2.換出變量的確定成立。又因93.2.換出變量的確定由于上式中至少有βl,m+t≠0，所以上式表明P1，P2，…，Pm是線性相關(guān)，這與假設(shè)相矛盾。由此可見，X(1)的m個非零分量對應(yīng)的列向量Pj(j=1,2,…,m,j≠l)與Pm+t是線性獨(dú)立的，即經(jīng)過基變換得到的解是基可行解。

實(shí)際上，從一個基可行解到另一個基可行解的變換，就是進(jìn)行一次基變換。從幾何意義上講，就是從可行域的一個頂點(diǎn)轉(zhuǎn)向另一個頂點(diǎn)。94.2.換出變量的確定由于上式中至少有βl,m+t≠0，所以上式2.3.5迭代(旋轉(zhuǎn)運(yùn)算)上述討論的基可行解的轉(zhuǎn)換方法是用向量方程描述的，在實(shí)際計算時不太方便，因此下面介紹系數(shù)矩陣法。

考慮以下形式的約束方程組一般線性規(guī)劃問題的約束方程組中加入松弛變量或人工變量后，很容易得到上述形式95.2.3.5迭代(旋轉(zhuǎn)運(yùn)算)上述討論的基可行解的轉(zhuǎn)換方法是2.3.5迭代(旋轉(zhuǎn)運(yùn)算)設(shè)x1,x2,…,xm為基變量，對應(yīng)的系數(shù)矩陣是m×m單位陣I，它是可行基。令非基變量xm+1,xm+2,…,xn為零，即可得到一個基可行解。

若它不是最優(yōu)解，則要另找一個使目標(biāo)函數(shù)值增大的基可行解。這時從非基變量中確定xk為換入變量。顯然這時θ為

在迭代過程中θ可表示為

其中是經(jīng)過迭代后對應(yīng)于的元素值。96.2.3.5迭代(旋轉(zhuǎn)運(yùn)算)設(shè)x1,x2,…,xm為基變量2.3.5迭代(旋轉(zhuǎn)運(yùn)算)按θ規(guī)則確定xl為換出變量，xk,xl的系數(shù)列向量分別為97.2.3.5迭代(旋轉(zhuǎn)運(yùn)算)按θ規(guī)則確定xl為換出變量，x2.3.5迭代(旋轉(zhuǎn)運(yùn)算)為了使xk與xl進(jìn)行對換，須把Pk變?yōu)閱挝幌蛄?，這可以通過(1-33)式系數(shù)矩陣的增廣矩陣進(jìn)行初等變換來實(shí)現(xiàn)。98.2.3.5迭代(旋轉(zhuǎn)運(yùn)算)為了使xk與xl進(jìn)行對換，須把2.3.5迭代(旋轉(zhuǎn)運(yùn)算)變換的步驟是：

(1)將增廣矩陣(1-34)式中的第l行除以alk，得到(2)將(1-34)式中xk列的各元素，除alk變換為1以外，其他都應(yīng)變換為零。其他行的變換是將(1-35)式乘以aik(i≠l)后，從(1-34)式的第i行減去，得到新的第i行。99.2.3.5迭代(旋轉(zhuǎn)運(yùn)算)變換的步驟是：

(1)將增廣2.3.5迭代(旋轉(zhuǎn)運(yùn)算)由此可得到變換后系數(shù)矩陣各元素的變換關(guān)系式

是變換后的新元素。

100.2.3.5迭代(旋轉(zhuǎn)運(yùn)算)由此可得到變換后系數(shù)矩陣各元素2.3.5迭代(旋轉(zhuǎn)運(yùn)算)(3)經(jīng)過初等變換后的新增廣矩陣是101.2.3.5迭代(旋轉(zhuǎn)運(yùn)算)(3)經(jīng)過初等變換后的新增廣2.3.5迭代(旋轉(zhuǎn)運(yùn)算)(4)由(1-36)式中可以看到x1,x2,…,xk,…，xm的系數(shù)列向量構(gòu)成m×m單位矩陣;它是可行基。當(dāng)非基變量xm+1,…，xl,…,xn為零時，就得到一個基可行解X(1)在上述系數(shù)矩陣的變換中，元素alk稱為主元素，它所在列稱為主元列，它所在行稱為主元行，元素alk位置變換后為1。102.2.3.5迭代(旋轉(zhuǎn)運(yùn)算)(4)由(1-36)式中可2.3.5迭代(旋轉(zhuǎn)運(yùn)算)例7

試用上述方法計算例6的兩個基變換。

解：例6的約束方程組的系數(shù)矩陣寫成增廣矩陣當(dāng)以x3,x4,x5為基變量，x1,x2為非基變量，令x1,x2=0，可得到一個基可行解X(0)=(0,0,8,16,12)T103.2.3.5迭代(旋轉(zhuǎn)運(yùn)算)例7試用上述方法計算例6的兩2.3.5迭代(旋轉(zhuǎn)運(yùn)算)現(xiàn)用x2去替換x5，于是將x3,,x4,x2的系數(shù)矩陣變換為單位矩陣，經(jīng)變換后為

令非基變量x1,x5=0，得到新的基可行解X(1)=(0,3,2,16,0)T104.2.3.5迭代(旋轉(zhuǎn)運(yùn)算)現(xiàn)用x2去替換x5，于是將x3P562.4，2.5作業(yè)105.P56作業(yè)105.第4節(jié)單純型法的計算步驟2.4.1單純型表2.4.2計算步驟106.第4節(jié)單純型法的計算步驟2.4.1單純型表106.2.4.1單純型表為了便于理解計算關(guān)系，現(xiàn)設(shè)計一種計算表，稱為單純形表，其功能與增廣矩陣相似。將(1-22)式與目標(biāo)函數(shù)組成n+1個變量，m+1個方程的方程組。107.2.4.1單純型表為了便于理解計算關(guān)系，現(xiàn)設(shè)計一種計算表線性規(guī)劃的方程組108.線性規(guī)劃的方程組108.線性規(guī)劃的方程組為了便于迭代運(yùn)算，可將上述方程組寫成增廣矩陣形式109.線性規(guī)劃的方程組為了便于迭代運(yùn)算，可將上述方程組寫成增廣矩陣線性規(guī)劃的方程組若將z看作不參與基變換的基變量，它與x1,x2,…,xm的系數(shù)構(gòu)成一個基，這時可采用行初等變換將c1,c2,…,cm變換為零，使其對應(yīng)的系數(shù)矩陣為單位矩陣。得到表1-2110.線性規(guī)劃的方程組若將z看作不參與基變換的基變量，它與x1,x線性規(guī)劃的方程組表1-2的說明XB列中填入基變量，這里是x1，x2,…，xm；CB列中填入基變量的價值系數(shù)，這里是c1,c2,…,cm；它們是與基變量相對應(yīng)的；b列中填入約束方程組右端的常數(shù)；cj行中填入基變量的價值系數(shù)c1,c2,…,cn；θi列的數(shù)字是在確定換入變量后，按θ規(guī)則計算后填入；最后一行稱為檢驗(yàn)數(shù)行，對應(yīng)各非基變量xj的檢驗(yàn)數(shù)是111.線性規(guī)劃的方程組表1-2的說明111.2.4.2計算步驟表1-2稱為初始單純形表，每迭代一步構(gòu)造一個新單純形表。計算步驟：(1)按數(shù)學(xué)模型確定初始可行基和初始基可行解，建立初始單純形表。(2)計算各非基變量xj的檢驗(yàn)數(shù)，檢查檢驗(yàn)數(shù)，若所有檢驗(yàn)數(shù)則已得到最優(yōu)解，可停止計算。否則轉(zhuǎn)入下一步。112.2.4.2計算步驟表1-2稱為初始單純形表，每迭代一步構(gòu)2.4.2計算步驟(3)在σj＞0,j=m+1,…,n中，若有某個σk對應(yīng)xk的系數(shù)列向量Pk≤0，則此問題是無界，停止計算。

否則，轉(zhuǎn)入下一步。(4)根據(jù)max(σj＞0)=σk，確定xk為換入變量，按θ規(guī)則計算可確定xl為換出變量，轉(zhuǎn)入下一步113.2.4.2計算步驟(3)在σj＞0,j=m+1,…,n中2.4.2計算步驟(5)以alk為主元素進(jìn)行迭代(即用高斯消去法或稱為旋轉(zhuǎn)運(yùn)算)，把xk所對應(yīng)的列向量將XB列中的xl換為xk，得到新的單純形表。重復(fù)(2)～(5)，直到終止。114.2.4.2計算步驟(5)以alk為主元素進(jìn)行迭代(即用2.4.2計算步驟現(xiàn)用例1的標(biāo)準(zhǔn)型來說明上述計算步驟(1)取松弛變量x3,x4,x5為基變量，它對應(yīng)的單位矩陣為基。這就得到初始基可行解X(0)=(0,0,8,16,12)T將有關(guān)數(shù)字填入表中，得到初始單純形表，見表1-3。表中左上角的cj是表示目標(biāo)函數(shù)中各變量的價值系數(shù)。在CB列填入初始基變量的價值系數(shù)，它們都為零。115.2.4.2計算步驟現(xiàn)用例1的標(biāo)準(zhǔn)型來說明上述計算步驟112.4.2計算步驟表1-3116.2.4.2計算步驟表1-3116.2.4.2計算步驟計算非基變量的檢驗(yàn)數(shù)各非基變量的檢驗(yàn)數(shù)為σ1=c1?z1=2?(0×1+0×4+0×0)=2σ2=c2?z2=3?(0×2+0×0+0×4)=3

填入表1-3的底行對應(yīng)非基變量處。117.2.4.2計算步驟計算非基變量的檢驗(yàn)數(shù)117.2.4.2計算步驟

它所在行對應(yīng)的x5為換出變量，x2所在列和x5所在行的交叉處

[4]稱為主元素或樞元素(pivotelement)118.2.4.2計算步驟它所在行對應(yīng)的x5為換出變量，x2.4.2計算步驟(4)以[4]為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算或迭代運(yùn)算，即初等行變換，使P2變換為(0,0,1)T,在XB

列中將x2

替換x5,于是得到新表1-4.

換人變量換出變量主元素119.2.4.2計算步驟(4)以[4]為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算2.4.2計算步驟(5)檢查表1-4的所有cj?zj,這時有c1?z1=2；說明x1應(yīng)為換入變量。重復(fù)(2)～(4)的計算步驟，得表1-5。換人變量換出變量主元素因?yàn)檫€存在檢驗(yàn)數(shù)>0，繼續(xù)進(jìn)行迭代。120.2.4.2計算步驟(5)檢查表1-4的所有cj?zj2.4.2計算步驟

(6)表1-6最后一行的所有檢驗(yàn)數(shù)都已為負(fù)或零。這表示目標(biāo)函數(shù)值已不可能再增大，于是得到最優(yōu)解X*=X(3)=(4,2,0,0,4)T

目標(biāo)函數(shù)的最大值z*=14

121.2.4.2計算步驟(6)表1-6最后一行的所有檢驗(yàn)數(shù)第5節(jié)單純形法的進(jìn)一步討論2.5.1人工變量法2.5.2退化2.5.3檢驗(yàn)數(shù)的幾種表示形式122.第5節(jié)單純形法的進(jìn)一步討論2.5.1人工變量法122.5.1人工變量法設(shè)線性規(guī)劃問題的約束條件其中沒有可作為初始基的單位矩陣，則分別給每一個約束方程加入人工變量xn+1,…,xn+m，得到123.2.5.1人工變量法設(shè)線性規(guī)劃問題的約束條件123.2.5.1人工變量法以xn+1,…，xn+m為基變量，并可得到一個m×m單位矩陣。令非基變量x1,…,xn為零，便可得到一個初始基可行解X(0)=(0,0,…,0,b1,b2,…,bm)T因?yàn)槿斯ぷ兞渴呛蠹尤氲皆s束條件中的虛擬變量，要求經(jīng)過基的變換將它們從基變量中逐個替換出來。基變量中不再含有非零的人工變量，這表示原問題有解。若在最終表中當(dāng)所有cj?zj≤0，而在其中還有某個非零人工變量，這表示原問題無可行解。以下討論如何解含有人工變量的線性規(guī)劃問題。124.2.5.1人工變量法以xn+1,…，xn+m為基變量，并可2.5.1人工變量法

例8

現(xiàn)有線性規(guī)劃問題，試用大M法求解。1.大M法125.2.5.1人工變量法例8現(xiàn)有線性規(guī)劃問題，試用大2.5.1人工變量法解在上述問題的約束條件中加入松弛變量x4，剩余變量x5，人工變量x6,x7，得到

這里M是一個任意大的正數(shù)。

126.2.5.1人工變量法解在上述問題的約束條件中加入松弛變2.5.1人工變量法

因本例的目標(biāo)函數(shù)是要求min，所以用所有cj?zj≥0來判別目標(biāo)函數(shù)是否實(shí)現(xiàn)了最小化.用單純形法進(jìn)行計算時，見表1-6。127.2.5.1人工變量法因本例的目標(biāo)函數(shù)是要求m2.5.1人工變量法在表1-6的最終計算結(jié)果可看出，已得到最優(yōu)解：

x1=4,x2=1,x3=9，x4=x5=x6=x7=0；目標(biāo)函數(shù)z=?2128.2.5.1人工變量法在表1-6的最終計算結(jié)果可看出，已得到2.5.1人工變量法以下介紹求解含有人工變量線性規(guī)劃問題的兩階段法。第一階段：不考慮原問題是否存在基可行解；給原線性規(guī)劃問題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)和要求實(shí)現(xiàn)最小化。2.兩階段法129.2.5.1人工變量法以下介紹求解含有人工變量線性規(guī)劃問題的2.5.1人工變量法第一階段：

不考慮原問題是否存在基可行解；給原線性規(guī)劃問題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)和要求實(shí)現(xiàn)最小化。如

130.2.5.1人工變量法第一階段：

不考慮原問題是否存在基可行2.5.1人工變量法第一階段求解用單純形法求解上述模型。若得到的最小值w=0，說明原問題存在基可行解，可以進(jìn)行第二段計算。否則原問題無可行解，應(yīng)停止計算。第二階段求解從第一階段計算得到的最終表中除去人工變量，將目標(biāo)函數(shù)行的系數(shù)，換為原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計算的初始表。各階段的計算方法及步驟與第3節(jié)介紹的單純形法相同。131.2.5.1人工變量法第一階段求解131.2.5.1人工變量法例9

試用兩階段法求解如下線性規(guī)劃問題：132.2.5.1人工變量法例9試用兩階段法求解如下線性規(guī)劃問2.5.1人工變量法解:

先在上述線性規(guī)劃問題的約束方程中加入人工變量，給出第一階段的數(shù)學(xué)模型為：133.2.5.1人工變量法解:先在上述線性規(guī)劃問題的約束方程中2.5.1人工變量法第一階段用單純形法求解，見表1-7。求得的結(jié)果是w=0，最優(yōu)解是x1=0,x2=1,x3=1,x4=12,x5=x6=x7=0因?yàn)槿斯ぷ兞縳6=x7=0，所以(0，1，1，12，0)T是原線性規(guī)劃問題的基可行解。于是可以進(jìn)行第二階段運(yùn)算。將第一階段的最終表中的人工變量取消，填入原問題的目標(biāo)函數(shù)系數(shù)，進(jìn)行第二階段計算，見表1-8。134.2.5.1人工變量法第一階段用單純形法求解，見表1-7。求2.5.1人工變量法表1-7135.2.5.1人工變量法表1-7135.2.5.1人工變量法表1-8從表1-8得到最優(yōu)解：x1=4,x2=1,x3=9,目標(biāo)函數(shù)值z=?2136.2.5.1人工變量法表1-8從表1-8得到最優(yōu)解：x1=2.5.2退化在單純形法計算中用θ規(guī)則確定換出變量時，有時存在兩個以上相同的最小比值，這樣在下一次迭代中就有一個或幾個基變量等于零，這就出現(xiàn)了退化解。這時換出變量xl=0，迭代后目標(biāo)函數(shù)值不變。這時不同基表示為同一頂點(diǎn)。有人構(gòu)造了一個特例，當(dāng)出現(xiàn)退化時，進(jìn)行多次迭代，而基從B1,B2，…又返回到B1，即出現(xiàn)計算過程的循環(huán)，便永遠(yuǎn)達(dá)不到最優(yōu)解。137.2.5.2退化在單純形法計算中用θ規(guī)則確定換出變量時，有2.5.2退化盡管實(shí)際計算過程中循環(huán)現(xiàn)象極少出現(xiàn)，但還是有可能發(fā)生的。如何解決這問題?先后有人提出了“攝動法”，“字典序法”。1974年由勃蘭特(Bland)提出一種簡便的規(guī)則，簡稱勃蘭特規(guī)則：(1)選取cj?zj＞0中下標(biāo)最小的非基變量xk為換入變量，即k=min(j｜c(diǎn)j?zj＞0)(2)當(dāng)按θ規(guī)則計算存在兩個和兩個以上最小比值時，選取下標(biāo)最小的基變量為換出變量。按勃蘭特規(guī)則計算時，一定能避免出現(xiàn)循環(huán)。138.2.5.2退化盡管實(shí)際計算過程中循環(huán)現(xiàn)象極少出現(xiàn)，但還是2.5.3檢驗(yàn)數(shù)的幾種表示形式本書以maxz=CX；AX=b，X≥0為標(biāo)準(zhǔn)型，以cj?zj≤0，（j=1,2,…,n）作為最優(yōu)解的判別準(zhǔn)則。由于還有其他形式的問題，為了避免混淆，將有關(guān)情況歸納如下：設(shè)x1,x2,…,xm為約束方程的基變量，于是可得139.2.5.3檢驗(yàn)數(shù)的幾種表示形式本書以maxz=CX；A2.5.3檢驗(yàn)數(shù)的幾種表示形式將它們代入目標(biāo)函數(shù)后，可有兩種表達(dá)形式140.2.5.3檢驗(yàn)數(shù)的幾種表示形式將它們代入目標(biāo)函數(shù)后，可有判別準(zhǔn)則的選擇當(dāng)要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化時，若用(1-37)式來分析，就需要用cj?zj≤0,（j=1,2，…,n）作為判別準(zhǔn)則；若用(1-38)式來分析，就需要用zj?cj≥0,（j=1,2,…,n）作為判別準(zhǔn)則。當(dāng)要求目標(biāo)函數(shù)實(shí)現(xiàn)最小化時，可用(1-37)式或(1-38)式來分析，這時可分別用cj?zj≥0或zj?cj≤0，（j=1,2,…,n）來判別目標(biāo)函數(shù)是否已達(dá)到最小。141.判別準(zhǔn)則的選擇當(dāng)要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化時，若用(1-37)式幾種判別準(zhǔn)則的匯總142.幾種判別準(zhǔn)則的匯總142.2.5.4單純形法小結(jié)(1)

根據(jù)實(shí)際問題給出數(shù)學(xué)模型，列出初始單純形表。進(jìn)行標(biāo)準(zhǔn)化，見表1-10。分別以每個約束條件中的松弛變量或人工變量為基變量，列出初始單純形表。表1-10143.2.5.4單純形法小結(jié)(1)

根據(jù)實(shí)際問題給出數(shù)學(xué)模型，列第6節(jié)

應(yīng)用舉例一般講，一個經(jīng)濟(jì)、管理問題凡滿足以下條件時，才能建立線性規(guī)劃模型。

(1)要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來表示，且為線性函數(shù)；

(2)存在著多種方案及有關(guān)數(shù)據(jù)；

(3)要求達(dá)到的目標(biāo)是在一定約束條件下實(shí)現(xiàn)的，這些約束條件可用線性等式或不等式來描述。144.第6節(jié)

應(yīng)用舉例一般講，一個經(jīng)濟(jì)、管理問題凡滿足以下條件時，第6節(jié)

應(yīng)用舉例例10

合理利用線材問題?，F(xiàn)要做100套鋼架，每套需用長為2.9m，2.1m和1.5m的元鋼各一根。已知原料長7.4m，問應(yīng)如何下料，使用的原材料最省。解：最簡單做法是，在每一根原材料上截取2.9m，2.1m和1.5m的元鋼各一根組成一套，每根原材料剩下料頭0.9m（7.4-2.9-2.1-1.5=0.9)。為了做100套鋼架，需用原材料100根，共有90m料頭。若改為用套裁，這可以節(jié)約原材料。下面有幾種套裁方案，都可以考慮采用。見表1-11。表1-11145.第6節(jié)

應(yīng)用舉例例10合理利用線材問題?，F(xiàn)要做100套鋼架第6節(jié)

應(yīng)用舉例為了得到100套鋼架，需要混合使用各種下料方案。設(shè)按Ⅰ方案下料的原材料根數(shù)為x1,Ⅱ方案為x2，Ⅲ方案為x3，Ⅳ方案為x4,Ⅴ方案為x5。根據(jù)表1-11的方案，可列出以下數(shù)學(xué)模型：146.第6節(jié)

應(yīng)用舉例為了得到100套鋼架，需要混合使用各種下料方第6節(jié)

應(yīng)用舉例在以上約束條件中加入人工變量x6,x7,x8；然后用表1-12進(jìn)行計算。表1-12147.第6節(jié)

應(yīng)用舉例在以上約束條件中加入人工變量x6,x7,x8第6節(jié)

應(yīng)用舉例第1次計算148.第6節(jié)

應(yīng)用舉例第1次計算148.第6節(jié)

應(yīng)用舉例第2次計算149.第6節(jié)

應(yīng)用舉例第2次計算149.第6節(jié)

應(yīng)用舉例最終計算表（第3次計算）由計算得到最優(yōu)下料方案是：按Ⅰ方案下料30根；Ⅱ方案下料10根；Ⅳ方案下料50根。即需90根原材料可以制造100套鋼架。有非基變量的檢驗(yàn)數(shù)為零，所以存在多重最優(yōu)解。150.第6節(jié)

應(yīng)用舉例最終計算表（第3次計算）由計算得到最優(yōu)下料方第6節(jié)

應(yīng)用舉例例11

（配料問題）某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、D。已知產(chǎn)品的規(guī)格要求，產(chǎn)品單價，每天能供應(yīng)的原材料數(shù)量及原材料單價，分別見表1-13和表1-14。該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大?

解：如以AC表示產(chǎn)品A中C的成分，AP表示產(chǎn)品A中P的成分，依次類推。表1-13151.第6節(jié)

應(yīng)用舉例例11（配料問題）某工廠要用三種原材料C第6節(jié)

應(yīng)用舉例根據(jù)表1-13有：這里AC+AP+AH=A；BC+BP+BH=B(1-40)將(1-40)逐個代入(1-39)并整理得到152.第6節(jié)

應(yīng)用舉例根據(jù)表1-13有：這里AC+AP+AH=第6節(jié)

應(yīng)用舉例表1-14表明這些原材料供應(yīng)數(shù)量的限額。加入到產(chǎn)品A、B、D的原材料C總量每天不超過100kg，P的總量不超過100kg，H總量不超過60kg。表1-14153.第6節(jié)

應(yīng)用舉例表1-14表明這些原材料供應(yīng)數(shù)量的限額。加入第6節(jié)

應(yīng)用舉例由此得約束條件AC+BC+DC≤100AP+BP+DP≤100AH+BH+DH≤60在約束條件中共有9個變量，為計算和敘述方便，分別用x1,…,x9表示。令x1=Ac,x2=Ap,x3=AH,x4=BC,x5=BP,x6=BH,x7=DC,x8=DP,x9=DH.154.第6節(jié)

應(yīng)用舉例由此得約束條件AC+BC+DC≤100154第6節(jié)

應(yīng)用舉例約束條件可表示為：155.第6節(jié)

應(yīng)用舉例約束條件可表示為：155.第6節(jié)

應(yīng)用舉例目標(biāo)函數(shù)目的是使利潤最大，即產(chǎn)品價格減去原材料的價格為最大。產(chǎn)品價格為：50(x1+x2+x3)——產(chǎn)品A

35(x4+x5+x6)——產(chǎn)品B25(x7+x8+x9)——產(chǎn)品D原材料價格為：65(x1+x4+x7)——原材料C

25(x2+x5+x8)——原材料P35(x3+x6+x9)——原材料H為了得到初始解，在約束條件中加入松弛變量x10～x16，得到數(shù)學(xué)模型：156.第6節(jié)

應(yīng)用舉例目標(biāo)函數(shù)156.第6節(jié)

應(yīng)用舉例例11的線性規(guī)劃模型157.第6節(jié)

應(yīng)用舉例例11的線性規(guī)劃模型157.第6節(jié)

應(yīng)用舉例最優(yōu)解用單純形法計算，經(jīng)過四次迭代，得最優(yōu)解為：

x1=100,x2=50,x3=50這表示：需要用原料C為100kg，P為50kg，H為50kg，構(gòu)成產(chǎn)品A。即每天只生產(chǎn)產(chǎn)品A為200kg，分別需要用原料C為100kg，P為50kg，H為50kg。從最終計算表中得到，總利潤是z=500元/天。158.第6節(jié)

應(yīng)用舉例最優(yōu)解158.第6節(jié)

應(yīng)用舉例例12

生產(chǎn)與庫存的優(yōu)化安排問題某工廠生產(chǎn)五種產(chǎn)品(i=1,…,5)，上半年各月對每種產(chǎn)品的最大市場需求量為dij(i=1,…,5;j=1,…,6)。已知每件產(chǎn)品的單件售價為Si元，生產(chǎn)每件產(chǎn)品所需要工時為ai，單件成本為Ci元；該工廠上半年各月正常生產(chǎn)工時為rj(j=1,…,6)，各月內(nèi)允許的最大加班工時為rj′;Ci′為加班單件成本。又每月生產(chǎn)的各種產(chǎn)品如當(dāng)月銷售不完，可以庫存。庫存費(fèi)用為Hi(元/件·月)。假設(shè)1月初所有產(chǎn)品的庫存為零，要求6月底各產(chǎn)品庫存量分別為ki件?，F(xiàn)要求為該工廠制定一個生產(chǎn)計劃，在盡可能利用生產(chǎn)能力的條件下，獲取最大利潤。159.第6節(jié)

應(yīng)用舉例例12生產(chǎn)與庫存的優(yōu)化安排問題159.第6節(jié)

應(yīng)用舉例

解：設(shè)xij和xij′分別為該工廠第i種產(chǎn)品的第j個月在正常時間和加班時間內(nèi)的生產(chǎn)量；yij為i種產(chǎn)品在第j月的銷售量，wij為第i種產(chǎn)品第j月末的庫存量。根據(jù)題意，可用以下模型描述：

(1)各種產(chǎn)品每月的生產(chǎn)量不能超過允許的生產(chǎn)能力，表示為：160.第6節(jié)

應(yīng)用舉例解：設(shè)xij和xij′分別為該工廠第6節(jié)

應(yīng)用舉例(2)各種產(chǎn)品每月銷售量不超過市場最大需求量

yij≤dij

(i=1,…,5;j=1,…,6)(3)每月末庫存量等于上月末庫存量加上該月產(chǎn)量減掉當(dāng)月的銷售量(4)滿足各變量的非負(fù)約束

xij≥0,xij′≥0,yij≥0,(i=1,…,5；j=1,…,6)wij≥0(i=1,…,5；j=1,…,5)161.第6節(jié)

應(yīng)用舉例(2)各種產(chǎn)品每月銷售量不超過市場最大需求第6節(jié)

應(yīng)用舉例(5)該工廠上半年總盈利最大可表示為：

162.第6節(jié)

應(yīng)用舉例(5)該工廠上半年總盈利最大可表示為：1第6節(jié)

應(yīng)用舉例例13

連續(xù)投資問題

某部門在今后五年內(nèi)考慮給下列項目投資