第1講線性規(guī)劃與單純形法-資料課件

線性規(guī)劃與單純形法線性規(guī)劃模型（1.1)單純形法(1.4)

重點：線性規(guī)劃的模型，單純形法難點：解的概念，單純形法基本要求：掌握線性規(guī)劃的標準化，理解解的概念、解的性質(zhì)，掌握單純形法1Chapter1

例1-1某工廠在計劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時和原料A、B的消耗量如下表。該工廠每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問應(yīng)如何安排生產(chǎn)計劃能使該廠獲利最多？

1問題的提出1.1線性規(guī)劃模型2Chapter1建立模型明確問題，確定決策變量

設(shè)計劃期內(nèi)產(chǎn)品Ⅰ、Ⅱ的產(chǎn)量分別為x1，x2

MaxZ=2x1+3x2x1+2x2≤804x1

≤1604x2≤120（非負值約束）x1,x2≥0確定約束條件：設(shè)備條件：確定目標函數(shù)：確定決策變量的約束：原材料A：原材料B：3Chapter1整理得：目標函數(shù)：MaxZ=2x1+3x2

約束條件：s.t.：x1+2x2

≤804x1

≤1604x2

≤120

x1,x2

≥04Chapter15Chapter1一般形式目標函數(shù)：Max（Min）z=c1x1+c2x2+…+cn

xn

（1-1）

約束條件：s.t.a11x1+a12x2+…+a1n

xn

≤（=,≥）b1

a21x1+a22x2+…+a2n

xn

≤（=,≥）b2…………

am1x1+am2x2+…+amn

xn

≤（=,≥）bm

（1-2）

x1，x2，…，xn≥0（1-3）技術(shù)系數(shù)Subjectto非負約束價值系數(shù)資源限制系數(shù)2線性規(guī)劃模型6Chapter1maxz=c1x1+c2x2++cnxna11x1+a12x2++a1nxn=b1a21x1+a22x2++a2nxn=b2am1x1+am2x2++amnxn=bmx1,x2,,xn≥0其中，bi≥0(i=1,2,,m)標準型7Chapter1標準型的表達形式Maxz=CXAX=bX>=0要求b的各個分量非負資源向量價值系數(shù)決策變量系數(shù)矩陣8Chapter1化標準型的步驟：（1）目標函數(shù)為最小：

minz=c1x1+c2x2++cnxn令z=-z,變?yōu)閙axz=-c1x1-c2x2--cnxn（2）決策變量xj無非負約束。（i）xj≤0，令xj=-xj，xj

≥0（ii）xj無約束，令xj=xj-xj，xjxj

≥0（3）bi

<0,不等式或等式兩端同時乘–19Chapter1

x1+2x2+x3

=80

4x1+x4

=160

4x2+x5

=120maxz=2x1

+3x2

+0x3+0x4

+0x5

x1,…,x5

≥0將例1-1的線性規(guī)劃問題化為標準型10Chapter111Chapter1則該問題的標準型為：12Chapter11.3線性規(guī)劃問題的解的概念1-41-51-61.3線性規(guī)劃問題解的概念及性質(zhì)13Chapter1即，對于標準的LP問題來說滿足這兩個條件的x是可行解或者可行點三者皆滿足是最優(yōu)解14Chapter1定義1-1基：

設(shè)A是約束方程組m×n維的系數(shù)矩陣，其秩為m，B是矩陣A中m×m階非奇異子矩陣（B的行列式│B│≠0），則稱B是線性規(guī)劃問題的一個基。最多有個基1.3.1基本概念

15maxz=2x1+3x2+0x3+0x4+0x5

x1+2x2+x3=80

4x1+x4=160

4x2+x5=120

x1,x2≥0基有：B1，B2，B3B4不是基

100010001B1=系數(shù)矩陣:121004001004001A=121400040B2=120401040B3=210000401B4=16Chapter1基基向量17Chapter1若令方程組中的非基變量x1=x2=0，可以求出一個解：X=（0，0，80，160，120）T稱X為基解。18Chapter1一個基本解的非零分量個數(shù)不超過m個?；A(chǔ)可行解的非零分量個數(shù)<

m

時，稱為退化解滿足非負約束條件的基解稱為基可行解。對應(yīng)于基可行解的基，稱為可行基。當基可行解為最優(yōu)解時,對應(yīng)的基稱最優(yōu)基。19Chapter1約束方程可改寫為：向量的形式表示為：

矩陣的形式表示為：

20Chapter1線性規(guī)劃標準型問題解的關(guān)系約束方程的解空間基解可行解非可行解基可行解退化解21Chapter1線性規(guī)劃問題解的狀況無可行解有可行解無最優(yōu)解有最優(yōu)解唯一最優(yōu)解無窮多最優(yōu)解線性規(guī)劃問題22Chapter11.3.2線性規(guī)劃解的性質(zhì)定理23Chapter1

要找到線性規(guī)劃問題的最優(yōu)解，只要在基本可行解中尋找就可以了。雖然基本可行解的數(shù)目是有限個（不超過Cnm個），但當m,n較大時，要用“窮舉法”求出所有基本可行解也是行不通的。因此，必須尋求一種更有效的方法。1.4單純形法24Chapter1主要有三個問題：一是尋找初始解，二是判別最優(yōu)解，三是迭代。

單純形法的基本思路是：從線性規(guī)劃問題的一個基本可行解開始，轉(zhuǎn)換到另一個使目標函數(shù)值增大的基本可行解。反復(fù)迭代，直到目標函數(shù)值達到最大時，就得到了最優(yōu)解。25Chapter1單純形法基本思路是否最優(yōu)解求最優(yōu)目標函數(shù)值是基變換,迭代否確定初始可行解否是26Chapter1

考慮：bi>0i=1,…,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn

≤b1

a21x1+a22x2+…+a2nxn

≤b2…………

am1x1+am2x2+…+amnxn

≤bm

x1，x2，…，xn≥0加入松弛變量：

Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2…………

am1x1+am2x2+…+amnxn+xn+m=bm

x1，x2，…，xn，xn+1，…，xn+m≥027Chapter1

顯然，xj=0j=1,…,n;

xn+i=bii=1,…,m

是基本可行解對應(yīng)的基是單位矩陣。以下是初始單純形表：

m其中：j=cj-∑cn+iaij為檢驗數(shù)cn+i

=0i=1,…,m

i=1an+i,i=1,an+i,j=0(j≠i)i,j=1,…,m單純形表28Chapter11確定初始基可行解：令xj=0j=1,…,n;

則xn+i=bii=1,…,m

是基本可行解。2解的最優(yōu)性檢驗：計算非基變量檢驗數(shù)

m

j=cj-∑cn+iaij，j=1,…,ni=1基變量檢驗數(shù)為0，即n+i

=0i=1,…,m若，則該基可行解為最優(yōu)解，否則轉(zhuǎn)下面若，則該問題為無界解（無最優(yōu)解）。否則轉(zhuǎn)第3步。3解的改進：確定換入變量為換入變量確定換出變量為換出變量

換基迭代以為主元，將