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

運籌學

OPERATIONAL

RESEARCH--運籌學

OPERATIONALRESEARCH--1第一章線性規(guī)劃及單純形法--2第一章--2第四節(jié)單純形法計算步驟第二節(jié)圖解法第三節(jié)單純形法原理第一節(jié)線性規(guī)劃問題及其數(shù)學模型第五節(jié)單純形法的進一步討論第六節(jié)數(shù)據(jù)包絡分析第七節(jié)其他應用例子--第四節(jié)單純形法計算步驟第二節(jié)圖解法第三節(jié)單3第一節(jié)線性規(guī)劃問題及其數(shù)學模型一、問題的提出二、線性規(guī)劃問題的與模型三、線性規(guī)劃的數(shù)學模型四、線性規(guī)劃模型的應用五、線性規(guī)劃問題的標準形式--第一節(jié)線性規(guī)劃問題及其數(shù)學模型一、問題的提出--4Ⅰ

Ⅱ每天可用能力設備A0515

設備B6224

調(diào)試工序115

利潤21一、問題提出例1生產(chǎn)計劃問題兩種家電各生產(chǎn)多少,可獲最大利潤?--一、問題提出例1生產(chǎn)計劃問題兩種家電各生產(chǎn)多少,可獲最5

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0maxZ=2x1+x2解:設兩種家電產(chǎn)量分別為變量x1

，x2--maxZ=2x1+x2解:設兩種家電產(chǎn)量分別為變量x16

5x2

153、約束條件

6x1+2x2

24

x1+x2

5

x1，x2

02、目標函數(shù)maxZ=2x1+x2LP問題的三要素1、決策變量x1

，x2--2、目標函數(shù)maxZ=2x1+x2LP問題的三要素-7例2--例2--8例2解：設表示捷運公司在第i(i=1,2,3,4)月初簽訂的租期為j(j=1,2,3,4)個月的倉庫面積的合同（單位為100m2)。--例2解：設表示捷運公司在第i(i=1,2,3,49ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12--ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12--10經(jīng)過上面的討論，得到下面的LP模型：目標函數(shù)約束條件--經(jīng)過上面的討論，得到下面的LP模型：目標函數(shù)約束條件--11二、線性規(guī)劃模型特點決策變量：向量(x1…

xn)T決策人要考慮和控制的因素非負約束條件：線性等式或不等式目標函數(shù)：Z=?(x1

…

xn)線性式，求Z極大或極小--二、線性規(guī)劃模型特點決策變量：向量(x1…xn)T12（一）一般式Max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn

(=,)b2………am1X1+am2X2+…+amnXn

(=,)bmXj0(j=1,…,n)--（一）一般式Max(min)Z=C1X1+C2X2+…+C13目標函數(shù)價值系數(shù)技術系數(shù)右端項常數(shù)決策變量--目標函數(shù)價值系數(shù)技術系數(shù)右端項常數(shù)決策變量--14（二）隱含的假設比例性：決策變量變化引起目標的改變量與決策變量改變量成正比可加性：每個決策變量對目標和約束的影響獨立于其它變量連續(xù)性：每個決策變量取連續(xù)值確定性：線性規(guī)劃中的參數(shù)aij

,bi,ci為確定值--（二）隱含的假設比例性：決策變量變化引起目標的改變量與決策變15線性規(guī)劃的標準化一般形式目標函數(shù)：Max（Min）z=c1x1+c2x2+…+cnxn

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

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0標準形式目標函數(shù)：Maxz=c1x1+c2x2+…+cnxn

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

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0，bi≥0三、線性規(guī)劃問題的標準形式--線性規(guī)劃的標準化三、線性規(guī)劃問題的標準形式--16

可以看出，線性規(guī)劃的標準形式有如下四個特點：目標最大化；約束為等式；決策變量均非負；右端項非負。對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉化為標準形式:三、線性規(guī)劃問題的標準形式--可以看出，線性規(guī)劃的標準形式有如下四個特三、線性規(guī)劃171.極小化目標函數(shù)的問題：設目標函數(shù)為

Minf=c1x1

+c2x2

+…+cnxn

(可以)令z

＝-f

，則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即Maxz=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個問題的最優(yōu)解相同，但它們最優(yōu)解的目標函數(shù)值卻相差一個符號，即

Minf

＝-Maxz三、線性規(guī)劃問題的標準形式--1.極小化目標函數(shù)的問題：三、線性規(guī)劃問題的標準形式--182、約束條件不是等式的問題：設約束條件為

ai1x1+ai2x2+…+ainxn

≤bi

可以引進一個新的變量s

，使它等于約束右邊與左邊之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)顯然，s

也具有非負約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn+s=bi三、線性規(guī)劃問題的標準形式--2、約束條件不是等式的問題：三、線性規(guī)劃問題的標準形式--19當約束條件為

ai1x1+ai2x2+…+ainxn

≥bi

時，類似地令

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

顯然，s

也具有非負約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn-s=bi三、線性規(guī)劃問題的標準形式--當約束條件為三、線性規(guī)劃問題的標準形式--20為了使約束由不等式成為等式而引進的變量s,當不等式為“小于等于”時稱為“松弛變量”；當不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉化為標準形式時，必須對各個約束引進不同的松弛變量。

3.右端項有負值的問題：

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

=-bi。三、線性規(guī)劃問題的標準形式--為了使約束由不等式成為等式而引進的變量s,當3.右端21例：將以下線性規(guī)劃問題轉化為標準形式

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

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

x1+x2+x3=-9

x1,x2,x3

≥0

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

其次考慮約束，有2個不等式約束，引進變量x4，x5

≥0。第三個約束條件的右端值為負，在等式兩邊同時乘-1。三、線性規(guī)劃問題的標準形式--例：將以下線性規(guī)劃問題轉化為標準形式

三、線性規(guī)劃問題的標準22通過以上變換，可以得到以下標準形式的線性規(guī)劃問題：

Maxz=-2x1

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

x1,x2,x3,x4,x5

≥0***變量無符號限制的問題***：

在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj’和xj”的大小。三、線性規(guī)劃問題的標準形式--通過以上變換，可以得到以下標準形式的線性規(guī)劃問題：三、線性23課堂練習

某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的A、B、C、D四種養(yǎng)分。有關數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的M、N兩種飼料中選擇，試決定總花費最小的購買方案。（列出模型）ABCD價格M0.50.20.30300N0.10.30.40.2200每頭日需10587養(yǎng)分飼料--課堂練習某蓄場每日要為每頭牲畜購買飼料，以使其獲取所24課堂練習

某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的A、B、C、D四種養(yǎng)分。有關數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的M、N兩種飼料中選擇，試決定總花費最小的購買方案。（列出模型）ABCD價格M0.50.20.30300N0.10.30.40.2200每頭日需10587養(yǎng)分飼料答案：設購買M飼料x1，N飼料x20.5x1+0.1x2≥100.2x1+0.3x2≥50.3x1+0.4x2≥80.2x2≥7x1,x2≥0s.t.MinZ=300x1+200x2--課堂練習某蓄場每日要為每頭牲畜購買飼料，以使其獲取所25第二節(jié)圖解法

對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關概念，并求解。--第二節(jié)圖解法對于只有兩個決策變量的線性26第二節(jié)圖解法一、圖解法的目的和步驟--第二節(jié)圖解法一、圖解法的目的和步驟--27

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0maxZ=2x1+x2例1模型的圖解法第二節(jié)圖解法--maxZ=2x1+x2例1模型的圖解法第二節(jié)圖解28第二節(jié)圖解法例2.目標函數(shù)：

Maxz=50x1+100x2約束條件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)--第二節(jié)圖解法例2.目標函數(shù)：--29第二節(jié)圖解法x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2--第二節(jié)圖解法x1x2x2=0x1=0x2=250x1+30第二節(jié)圖解法目標函數(shù)z=50x1+100x2，當z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數(shù)值，稱之為“等值線”。平行移動等值線，當移動到B點時，z在可行域內(nèi)實現(xiàn)了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE--第二節(jié)圖解法目標函數(shù)z=50x31第二節(jié)圖解法例2.目標函數(shù)：

Maxz=50x1+100x2約束條件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最優(yōu)解：

x1=50，x2=250

最優(yōu)目標值z=27500--第二節(jié)圖解法例2.目標函數(shù)：--32第二節(jié)圖解法最優(yōu)解：x1=0，x2=1

最優(yōu)目標值z=3課堂練習圖解法求解線性規(guī)劃012341234x1x2O-1-2(1)(2)(3)--第二節(jié)圖解法最優(yōu)解：x1=0，x2=33第二節(jié)圖解法（1）唯一解（2）多重最優(yōu)解（3）無可行解注：出現(xiàn)（3）、（4）情況時，建模有問題（4）無有限最優(yōu)解二、圖解法的求解結果分類--第二節(jié)圖解法（1）唯一解（2）多重最優(yōu)解（3）無可行解34第二節(jié)圖解法三、圖解法的幾點啟示從圖解法中我們了解到以下事實：①若LP問題的可行域存在，則可行域一定是凸集。②若LP問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（如果有無窮多最優(yōu)解的話）一定是可行域凸集的某個極點（頂點）。思路：①最優(yōu)解先在可行域中找。（可行域為空集，則無可行解，故無最優(yōu)解。）②最優(yōu)解在可行域的極點中找。③極點是有限個，若兩個極點都是最優(yōu)解，則兩個極點所連線段上的所有點均是最優(yōu)解）定義：LP問題的可行域的極點（頂點）稱為基本可行解。--第二節(jié)圖解法三、圖解法的幾點啟示從圖解法中我們了解到以35第三節(jié)單純形法凸集凸集：在點集中任取兩點，則其連線仍在其中。即沒有凹入的部分；沒有空洞。⑴⑵⑶⑷⑸⑹在凸集⑵中，點A，B，C，D稱為極點（或頂點）。ABCD--第三節(jié)單純形法凸集凸集：在點集中任取兩點，則其連線仍在36第四節(jié)單純形法--37第四節(jié)單純形法--3738第四節(jié)單純形法單純形法的基本思路：根據(jù)線性規(guī)劃問題的標準，從可行域中某個基可行解（一個頂點）開始，轉換到另一個基可行解（頂點），并且使目標函數(shù)達到最大值時，線性規(guī)劃問題就得到了最優(yōu)解。(1)確定初始基可行解(2)最優(yōu)性檢驗和解的判別(3)由一個基可行解→另一個基可行解。--38第四節(jié)單純形法單純形法的基本思路：根據(jù)線性規(guī)劃問題3839第四節(jié)單純形法理論基礎--39第四節(jié)單純形法理論基礎--3940第四節(jié)單純形法單純形法的步驟及解法--40第四節(jié)單純形法單純形法的步驟及解法--40(1)確定初始基可行解(2)最優(yōu)性檢驗和解的判別(3)由一個基可行解→另一個基可行解。一、單純形法的基本思路第四節(jié)單純形法--41(1)確定初始基可行解(2)最優(yōu)性檢驗和解的判別(3)x1+a1m+1xm+1+……+a1nxn=b1x2+a2m+1xm+1+……+a2nxn=b2xm+amm+1xm+1+……+amnxn=bn10…0a1m+1…a1n01…0a2m+1…a2n………00…1amm+1…amnA=第四節(jié)單純形法標準化模型，確定初始基可行解--42x143單純形表X1X2…XmXm+1…

Xm+k…XnCBXBbC1C2…

CmCm+1…

Cm+k…CnC1X1b110…0a1m+1…a1m+k…a1nC2X2b201…0a2m+1…a2m+k…

a2nCrXrbr00…0arm+1…arm+k…

arnCmXmbm00…1amm+1…amm+k…

ann……………………………………z00

…0σm+1…σm+k…

σn--43單純形表4344例1第四節(jié)單純形法

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0maxZ=2x1+x2--44例1第四節(jié)單純形法maxZ=2x1+x2--4445第一步：標準化第四節(jié)單純形法

5x2+x3

=

156x1+2x2

+x4

=

24

x1+x2

+x5

=5

x1，x2

，x3，x4，x5

0maxZ=2x1+x2+0x3

+0x4+0x5--45第一步：標準化第四節(jié)單純形法maxZ=2x14546第二步：根據(jù)增廣矩陣找一個初始基可行解第四節(jié)單純形法--46第二步：根據(jù)增廣矩陣找一個初始基可行解第四節(jié)單純形法4647第三步：列出初始單純形表第四節(jié)單純形法--47第三步：列出初始單純形表第四節(jié)單純形法--4748第四步：判斷是否最優(yōu)，否則找出下一個基可行解，并寫出新單純形表第四節(jié)單純形法--48第四步：判斷是否最優(yōu)，否則找出下一個基可行解，并寫出新單4849第四步：判斷是否最優(yōu)，否則找出下一個基可行解，并寫出新單純形表第四節(jié)單純形法--49第四步：判斷是否最優(yōu)，否則找出下一個基可行解，并寫出新單4950第五步：再寫出新單純形表第四節(jié)單純形法--50第五步：再寫出新單純形表第四節(jié)單純形法--5051習題第四節(jié)單純形法--51習題第四節(jié)單純形法--5152習題第四節(jié)單純形法--52習題第四節(jié)單純形法--5253習題第四節(jié)單純形法--53習題第四節(jié)單純形法--5354習題第四節(jié)單純形法--54習題第四節(jié)單純形法--5455習題第四節(jié)單純形法--55習題第四節(jié)單純形法--5556習題第四節(jié)單純形法--56習題第四節(jié)單純形法--5657一、人工變量法（大M法）第五節(jié)單純形法的進一步討論沒有初始基可行解時怎么辦？借助人工變量求初始的基本可行解

--57一、人工變量法（大M法）第五節(jié)單純形法的進一步討論5758一、人工變量法（大M法）第五節(jié)單純形法的進一步討論--58一、人工變量法（大M法）第五節(jié)單純形法的進一步討論5859一、人工變量法（大M法）第五節(jié)單純形法的進一步討論--59一、人工變量法（大M法）第五節(jié)單純形法的進一步討論5960一、人工變量法（大M法）第五節(jié)單純形法的進一步討論--60一、人工變量法（大M法）第五節(jié)單純形法的進一步討論6061一、人工變量法（大M法）第五節(jié)單純形法的進一步討論--61一、人工變量法（大M法）第五節(jié)單純形法的進一步討論6162一、人工變量法（大M法）第五節(jié)單純形法的進一步討論--62一、人工變量法（大M法）第五節(jié)單純形法的進一步討論6263一、人工變量法（大M法）第五節(jié)單純形法的進一步討論--63一、人工變量法（大M法）第五節(jié)單純形法的進一步討論6364二、兩階段法（大M法）第五節(jié)單純形法的進一步討論--64二、兩階段法（大M法）第五節(jié)單純形法的進一步討論-6465二、兩階段法（大M法）第五節(jié)單純形法的進一步討論--65二、兩階段法（大M法）第五節(jié)單純形法的進一步討論-6566二、兩階段法（大M法）第五節(jié)單純形法的進一步討論--66二、兩階段法（大M法）第五節(jié)單純形法的進一步討論-6667二、兩階段法（大M法）第五節(jié)單純形法的進一步討論--67二、兩階段法（大M法）第五節(jié)單純形法的進一步討論-6768二、兩階段法（大M法）第五節(jié)單純形法的進一步討論--68二、兩階段法（大M法）第五節(jié)單純形法的進一步討論-6869二、兩階段法（大M法）第五節(jié)單純形法的進一步討論--69二、兩階段法（大M法）第五節(jié)單純形法的進一步討論-6970二、兩階段法（大M法）第五節(jié)單純形法的進一步討論--70二、兩階段法（大M法）第五節(jié)單純形法的進一步討論-7071二、兩階段法（大M法）第五節(jié)單純形法的進一步討論--71二、兩階段法（大M法）第五節(jié)單純形法的進一步討論-7172三、關于解的判斷第五節(jié)單純形法的進一步討論--72三、關于解的判斷第五節(jié)單純形法的進一步討論--7273三、關于解的判斷第五節(jié)單純形法的進一步討論--73三、關于解的判斷第五節(jié)單純形法的進一步討論--7374三、關于解的判斷第五節(jié)單純形法的進一步討論--74三、關于解的判斷第五節(jié)單純形法的進一步討論--7475三、關于解的判斷第五節(jié)單純形法的進一步討論--75三、關于解的判斷第五節(jié)單純形法的進一步討論--7576三、關于解的判斷第五節(jié)單純形法的進一步討論--76三、關于解的判斷第五節(jié)單純形法的進一步討論--7677三、關于解的判斷第五節(jié)單純形法的進一步討論--77三、關于解的判斷第五節(jié)單純形法的進一步討論--7778三、關于解的判斷第五節(jié)單純形法的進一步討論--78三、關于解的判斷第五節(jié)單純形法的進一步討論--7879應用--79應用--7980一、人工變量法（大M法）第五節(jié)單純形法的進一步討論--80一、人工變量法（大M法）第五節(jié)單純形法的進一步討論8081--81--8182--82--8283本章內(nèi)容結束--83本章內(nèi)容結束--83運籌學

OPERATIONAL

RESEARCH--運籌學

OPERATIONALRESEARCH--84第一章線性規(guī)劃及單純形法--85第一章--2第四節(jié)單純形法計算步驟第二節(jié)圖解法第三節(jié)單純形法原理第一節(jié)線性規(guī)劃問題及其數(shù)學模型第五節(jié)單純形法的進一步討論第六節(jié)數(shù)據(jù)包絡分析第七節(jié)其他應用例子--第四節(jié)單純形法計算步驟第二節(jié)圖解法第三節(jié)單86第一節(jié)線性規(guī)劃問題及其數(shù)學模型一、問題的提出二、線性規(guī)劃問題的與模型三、線性規(guī)劃的數(shù)學模型四、線性規(guī)劃模型的應用五、線性規(guī)劃問題的標準形式--第一節(jié)線性規(guī)劃問題及其數(shù)學模型一、問題的提出--87Ⅰ

Ⅱ每天可用能力設備A0515

設備B6224

調(diào)試工序115

利潤21一、問題提出例1生產(chǎn)計劃問題兩種家電各生產(chǎn)多少,可獲最大利潤?--一、問題提出例1生產(chǎn)計劃問題兩種家電各生產(chǎn)多少,可獲最88

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0maxZ=2x1+x2解:設兩種家電產(chǎn)量分別為變量x1

，x2--maxZ=2x1+x2解:設兩種家電產(chǎn)量分別為變量x189

5x2

153、約束條件

6x1+2x2

24

x1+x2

5

x1，x2

02、目標函數(shù)maxZ=2x1+x2LP問題的三要素1、決策變量x1

，x2--2、目標函數(shù)maxZ=2x1+x2LP問題的三要素-90例2--例2--91例2解：設表示捷運公司在第i(i=1,2,3,4)月初簽訂的租期為j(j=1,2,3,4)個月的倉庫面積的合同（單位為100m2)。--例2解：設表示捷運公司在第i(i=1,2,3,492ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12--ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12--93經(jīng)過上面的討論，得到下面的LP模型：目標函數(shù)約束條件--經(jīng)過上面的討論，得到下面的LP模型：目標函數(shù)約束條件--94二、線性規(guī)劃模型特點決策變量：向量(x1…

xn)T決策人要考慮和控制的因素非負約束條件：線性等式或不等式目標函數(shù)：Z=?(x1

…

xn)線性式，求Z極大或極小--二、線性規(guī)劃模型特點決策變量：向量(x1…xn)T95（一）一般式Max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn

(=,)b2………am1X1+am2X2+…+amnXn

(=,)bmXj0(j=1,…,n)--（一）一般式Max(min)Z=C1X1+C2X2+…+C96目標函數(shù)價值系數(shù)技術系數(shù)右端項常數(shù)決策變量--目標函數(shù)價值系數(shù)技術系數(shù)右端項常數(shù)決策變量--97（二）隱含的假設比例性：決策變量變化引起目標的改變量與決策變量改變量成正比可加性：每個決策變量對目標和約束的影響獨立于其它變量連續(xù)性：每個決策變量取連續(xù)值確定性：線性規(guī)劃中的參數(shù)aij

,bi,ci為確定值--（二）隱含的假設比例性：決策變量變化引起目標的改變量與決策變98線性規(guī)劃的標準化一般形式目標函數(shù)：Max（Min）z=c1x1+c2x2+…+cnxn

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

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0標準形式目標函數(shù)：Maxz=c1x1+c2x2+…+cnxn

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

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0，bi≥0三、線性規(guī)劃問題的標準形式--線性規(guī)劃的標準化三、線性規(guī)劃問題的標準形式--99

可以看出，線性規(guī)劃的標準形式有如下四個特點：目標最大化；約束為等式；決策變量均非負；右端項非負。對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉化為標準形式:三、線性規(guī)劃問題的標準形式--可以看出，線性規(guī)劃的標準形式有如下四個特三、線性規(guī)劃1001.極小化目標函數(shù)的問題：設目標函數(shù)為

Minf=c1x1

+c2x2

+…+cnxn

(可以)令z

＝-f

，則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即Maxz=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個問題的最優(yōu)解相同，但它們最優(yōu)解的目標函數(shù)值卻相差一個符號，即

Minf

＝-Maxz三、線性規(guī)劃問題的標準形式--1.極小化目標函數(shù)的問題：三、線性規(guī)劃問題的標準形式--1012、約束條件不是等式的問題：設約束條件為

ai1x1+ai2x2+…+ainxn

≤bi

可以引進一個新的變量s

，使它等于約束右邊與左邊之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)顯然，s

也具有非負約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn+s=bi三、線性規(guī)劃問題的標準形式--2、約束條件不是等式的問題：三、線性規(guī)劃問題的標準形式--102當約束條件為

ai1x1+ai2x2+…+ainxn

≥bi

時，類似地令

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

顯然，s

也具有非負約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn-s=bi三、線性規(guī)劃問題的標準形式--當約束條件為三、線性規(guī)劃問題的標準形式--103為了使約束由不等式成為等式而引進的變量s,當不等式為“小于等于”時稱為“松弛變量”；當不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉化為標準形式時，必須對各個約束引進不同的松弛變量。

3.右端項有負值的問題：

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

=-bi。三、線性規(guī)劃問題的標準形式--為了使約束由不等式成為等式而引進的變量s,當3.右端104例：將以下線性規(guī)劃問題轉化為標準形式

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

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

x1+x2+x3=-9

x1,x2,x3

≥0

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

其次考慮約束，有2個不等式約束，引進變量x4，x5

≥0。第三個約束條件的右端值為負，在等式兩邊同時乘-1。三、線性規(guī)劃問題的標準形式--例：將以下線性規(guī)劃問題轉化為標準形式

三、線性規(guī)劃問題的標準105通過以上變換，可以得到以下標準形式的線性規(guī)劃問題：

Maxz=-2x1

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

x1,x2,x3,x4,x5

≥0***變量無符號限制的問題***：

在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj’和xj”的大小。三、線性規(guī)劃問題的標準形式--通過以上變換，可以得到以下標準形式的線性規(guī)劃問題：三、線性106課堂練習

某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的A、B、C、D四種養(yǎng)分。有關數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的M、N兩種飼料中選擇，試決定總花費最小的購買方案。（列出模型）ABCD價格M0.50.20.30300N0.10.30.40.2200每頭日需10587養(yǎng)分飼料--課堂練習某蓄場每日要為每頭牲畜購買飼料，以使其獲取所107課堂練習

某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的A、B、C、D四種養(yǎng)分。有關數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的M、N兩種飼料中選擇，試決定總花費最小的購買方案。（列出模型）ABCD價格M0.50.20.30300N0.10.30.40.2200每頭日需10587養(yǎng)分飼料答案：設購買M飼料x1，N飼料x20.5x1+0.1x2≥100.2x1+0.3x2≥50.3x1+0.4x2≥80.2x2≥7x1,x2≥0s.t.MinZ=300x1+200x2--課堂練習某蓄場每日要為每頭牲畜購買飼料，以使其獲取所108第二節(jié)圖解法

對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關概念，并求解。--第二節(jié)圖解法對于只有兩個決策變量的線性109第二節(jié)圖解法一、圖解法的目的和步驟--第二節(jié)圖解法一、圖解法的目的和步驟--110

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0maxZ=2x1+x2例1模型的圖解法第二節(jié)圖解法--maxZ=2x1+x2例1模型的圖解法第二節(jié)圖解111第二節(jié)圖解法例2.目標函數(shù)：

Maxz=50x1+100x2約束條件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)--第二節(jié)圖解法例2.目標函數(shù)：--112第二節(jié)圖解法x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2--第二節(jié)圖解法x1x2x2=0x1=0x2=250x1+113第二節(jié)圖解法目標函數(shù)z=50x1+100x2，當z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數(shù)值，稱之為“等值線”。平行移動等值線，當移動到B點時，z在可行域內(nèi)實現(xiàn)了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE--第二節(jié)圖解法目標函數(shù)z=50x114第二節(jié)圖解法例2.目標函數(shù)：

Maxz=50x1+100x2約束條件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最優(yōu)解：

x1=50，x2=250

最優(yōu)目標值z=27500--第二節(jié)圖解法例2.目標函數(shù)：--115第二節(jié)圖解法最優(yōu)解：x1=0，x2=1

最優(yōu)目標值z=3課堂練習圖解法求解線性規(guī)劃012341234x1x2O-1-2(1)(2)(3)--第二節(jié)圖解法最優(yōu)解：x1=0，x2=116第二節(jié)圖解法（1）唯一解（2）多重最優(yōu)解（3）無可行解注：出現(xiàn)（3）、（4）情況時，建模有問題（4）無有限最優(yōu)解二、圖解法的求解結果分類--第二節(jié)圖解法（1）唯一解（2）多重最優(yōu)解（3）無可行解117第二節(jié)圖解法三、圖解法的幾點啟示從圖解法中我們了解到以下事實：①若LP問題的可行域存在，則可行域一定是凸集。②若LP問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（如果有無窮多最優(yōu)解的話）一定是可行域凸集的某個極點（頂點）。思路：①最優(yōu)解先在可行域中找。（可行域為空集，則無可行解，故無最優(yōu)解。）②最優(yōu)解在可行域的極點中找。③極點是有限個，若兩個極點都是最優(yōu)解，則兩個極點所連線段上的所有點均是最優(yōu)解）定義：LP問題的可行域的極點（頂點）稱為基本可行解。--第二節(jié)圖解法三、圖解法的幾點啟示從圖解法中我們了解到以118第三節(jié)單純形法凸集凸集：在點集中任取兩點，則其連線仍在其中。即沒有凹入的部分；沒有空洞。⑴⑵⑶⑷⑸⑹在凸集⑵中，點A，B，C，D稱為極點（或頂點）。ABCD--第三節(jié)單純形法凸集凸集：在點集中任取兩點，則其連線仍在119第四節(jié)單純形法--120第四節(jié)單純形法--37121第四節(jié)單純形法單純形法的基本思路：根據(jù)線性規(guī)劃問題的標準，從可行域中某個基可行解（一個頂點）開始，轉換到另一個基可行解（頂點），并且使目標函數(shù)達到最大值時，線性規(guī)劃問題就得到了最優(yōu)解。(1)確定初始基可行解(2)最優(yōu)性檢驗和解的判別(3)由一個基可行解→另一個基可行解。--38第四節(jié)單純形法單純形法的基本思路：根據(jù)線性規(guī)劃問題121122第四節(jié)單純形法理論基礎--39第四節(jié)單純形法理論基礎--122123第四節(jié)單純形法單純形法的步驟及解法--40第四節(jié)單純形法單純形法的步驟及解法--123(1)確定初始基可行解(2)最優(yōu)性檢驗和解的判別(3)由一個基可行解→另一個基可行解。一、單純形法的基本思路第四節(jié)單純形法--124(1)確定初始基可行解(2)最優(yōu)性檢驗和解的判別(3)x1+a1m+1xm+1+……+a1nxn=b1x2+a2m+1xm+1+……+a2nxn=b2xm+amm+1xm+1+……+amnxn=bn10…0a1m+1…a1n01…0a2m+1…a2n………00…1amm+1…amnA=第四節(jié)單純形法標準化模型，確定初始基可行解--125x1126單純形表X1X2…XmXm+1…

Xm+k…XnCBXBbC1C2…

CmCm+1…

Cm+k…CnC1X1b110…0a1m+1…a1m+k…a1nC2X2b201…0a2m+1…a2m+k…

a2nCrXrbr00…0arm+1…arm+k…

arnCmXmbm00…1amm+1…amm+k…

ann……………………………………z00

…0σm+1…σm+k…

σn--43單純形表126127例1第四節(jié)單純形法

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0maxZ=2x1+x2--44例1第四節(jié)單純形法maxZ=2x1+x2--127128第一步：標準化第四節(jié)單純形法

5x2+x3

=

156x1+2x2

+x4

=

24

x1+x2