教案線性規(guī)劃

第1章線性規(guī)劃第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型第2節(jié)線性規(guī)劃問題的幾何意義第3節(jié)單純形法第4節(jié)單純形法的計(jì)算步驟第5節(jié)單純形法的進(jìn)一步討論第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型1.1問題的提出1.2圖解法1.3線性規(guī)劃問題的標(biāo)準(zhǔn)形式1.4線性規(guī)劃問題的解的概念1.1問題的提出1.1問題的提出

例1

某工廠在計(jì)劃期內(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)如何安排計(jì)劃使該工廠獲利最多?

1.1問題的提出用數(shù)學(xué)關(guān)系式描述這個問題1.1問題的提出得到本問題的數(shù)學(xué)模型為:這就是一個簡單的線性規(guī)劃模型。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)最大化或最小化。上述問題具有的特征：1.1問題的提出決策變量及各類系數(shù)之間的對應(yīng)關(guān)系1.1問題的提出線性規(guī)劃模型的一般形式1.2圖解法1.2圖解法例1是一個二維線性規(guī)劃問題，因而可用作圖法直觀地進(jìn)行求解。1.2圖解法目標(biāo)值在（4，2）點(diǎn)，達(dá)到最大值141.2圖解法（1）無窮多最優(yōu)解(多重最優(yōu)解)，見圖1-4。（2）無界解，見圖1-5-1。（3）無可行解，見圖1-5-2。通過圖解法，可觀察到線性規(guī)劃的解可能出現(xiàn)的幾種情況：1.2圖解法目標(biāo)函數(shù)maxz=2x1+4x2

圖1-4無窮多最優(yōu)解（多重最優(yōu)解）1.2圖解法圖1-5-1無界解

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

則該問題的可行域即為空集，即無可行解，無可行解的情形1.2圖解法增加的約束條件圖1-5-2不存在可行域1.2圖解法1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式用向量形式表示的標(biāo)準(zhǔn)形式線性規(guī)劃線性規(guī)劃問題的幾種表示形式1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式用矩陣形式表示的標(biāo)準(zhǔn)形式線性規(guī)劃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ī)劃1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式例3

將例1的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式的線性規(guī)劃。例1的數(shù)學(xué)模型在加入了松馳變量后變?yōu)?.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)型。1.3線性規(guī)劃問題的標(biāo)準(zhǔn)型式例4的標(biāo)準(zhǔn)型1.4線性規(guī)劃問題的解概念1.可行解2.基3.基可行解4.可行基1.4線性規(guī)劃問題的解的概念定義滿足約束條件(1-5)、(1-6)式的解X=(x1,x2，…，xn)T，稱為線性規(guī)劃問題的可行解，其中使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解。1.可行解1.4線性規(guī)劃問題的解的概念2.基，基向量，基變量1.4線性規(guī)劃問題的解的概念對應(yīng)每一個基B,令所有非基變量為零，由(1-5)約束方程組求得的解X稱為基解；滿足非負(fù)條件（1-6）的基3基可行解解，稱為基可行解.基可行解的非零分量的數(shù)目不大于m，并且都是非負(fù)的。1.4線性規(guī)劃問題的解的概念對應(yīng)于基可行解的基，稱為可行基。約束方程組(1-5)具有的基解的數(shù)目最多是個，一般基可行解的數(shù)目要小于基解的數(shù)目。以上提到了幾種解的概念，它們之間的關(guān)系可用圖1-6表明。說明：當(dāng)基解中的非零分量的個數(shù)小于m時，該基解是退化解。在以下討論時，假設(shè)不出現(xiàn)退化的情況。4可行基1.4線性規(guī)劃問題的解的概念不同解之間的關(guān)系第2節(jié)線性規(guī)劃問題的幾何意義2.1基本概念2.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.凸集2.1基本概念實(shí)心圓，實(shí)心球體，實(shí)心立方體等都是凸集，圓環(huán)不是凸集。從直觀上講，凸集沒有凹入部分，其內(nèi)部沒有空洞。圖1-7中的(a)(b)是凸集，(c)不是凸集。圖1-2中的陰影部分是凸集。任何兩個凸集的交集是凸集，見圖1-7(d)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.凸組合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,2,3,4都是頂點(diǎn)。3.頂點(diǎn)2.2幾個定理定理1

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

是凸集。2.2幾個定理定理1的證明：只需證明D中任意兩點(diǎn)連線上的點(diǎn)必然在D內(nèi)即可。設(shè)是D內(nèi)的任意兩點(diǎn)；且X(1)≠X(2)。2.2幾個定理2.2幾個定理引理1

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

線性規(guī)劃問題的基可行解X對應(yīng)于可行域D的頂點(diǎn)。（充要條件）證：不失一般性，假設(shè)基可行解X的前m個分量為正。故現(xiàn)分兩步來討論，分別用反證法。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

402.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不是基可行解。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)的凸組合表示X(見圖1-8)圖1-82.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＜12.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)型是maxz=CX

)。因X(0)不是頂點(diǎn)，