第1章LP數(shù)學(xué)模型

運(yùn)籌學(xué)

(OperationsResearch)運(yùn)籌帷幄之中決勝千里之外線性規(guī)劃及單純形法LinearProgramming第一章Chapter1線性規(guī)劃

(LinearProgramming)LP的數(shù)學(xué)模型圖解法單純形法單純形法的進(jìn)一步討論－人工變量法

LP模型的應(yīng)用本章主要內(nèi)容：線性規(guī)劃問題的數(shù)學(xué)模型1.規(guī)劃問題生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題：（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤(rùn)最大.）線性規(guī)劃問題的數(shù)學(xué)模型例1.1某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤(rùn)問：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使總利潤(rùn)最大？解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分別為x1、x22.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z，則有：

maxz=2x1+x23.約束條件：

5x2≤156x1+2x2≤24x1+x2≤5

x1，x2≥0線性規(guī)劃問題的數(shù)學(xué)模型例1.2已知資料如下表所示，問如何安排生產(chǎn)才能使利潤(rùn)最大？或如何考慮利潤(rùn)大，產(chǎn)品好銷。

設(shè)備產(chǎn)品AB

C

D利潤(rùn)（元）

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分別為x1、x22.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z，則有：maxz=2x1+3x23.約束條件：

x1≥0,x2≥0

2x1+2x2≤12

x1+2x2≤84x1≤164x2≤12線性規(guī)劃問題的數(shù)學(xué)模型例1.3

某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量解：要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過180單位，且使原料總成本最小。1.決策變量：設(shè)四種原料的使用量分別為：x1、x2、x3

、x42.目標(biāo)函數(shù)：設(shè)總成本為zmin

z=5x1+6x2+7x3+8x43.約束條件：

x1+2x2+x3+x4≥1602x1+4x3+2x4

＝2003x1

＋x2+x3+2x4

≤180

x1、x2

、x3

、x4≥0

例1.4

某航運(yùn)局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示：航線號(hào)船隊(duì)類型編隊(duì)形式貨運(yùn)成本（千元／隊(duì)）貨運(yùn)量（千噸）拖輪A型駁船B型駁船1112—362521—4362023224724041—42720船只種類船只數(shù)拖輪30A型駁船34B型駁船52航線號(hào)合同貨運(yùn)量12002400問：應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最小？線性規(guī)劃問題的數(shù)學(xué)模型

解：設(shè)：xj為第j號(hào)類型船隊(duì)的隊(duì)數(shù)（j=1，2，3，4），

z為總貨運(yùn)成本數(shù)學(xué)模型：

minz=36x1+36x2+72x3+27x4

x1

+x2

+2x3+x4

≤30

2x1

+2x3

≤34

4x2

+4x3

+4x4≤5225x1+20x2

＝200

40x3+20x4＝400

xj

≥0（j=1,2,3,4）線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型2.線性規(guī)劃的數(shù)學(xué)模型由三個(gè)要素構(gòu)成決策變量Decisionvariables目標(biāo)函數(shù)Objectivefunction約束條件Constraints其特征是：（1）問題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問題的約束條件是一組多個(gè)決策變量的線性不等式或等式。

怎樣辨別一個(gè)模型是線性規(guī)劃模型？

線性規(guī)劃問題的數(shù)學(xué)模型3.建模條件(1)

優(yōu)化條件：?jiǎn)栴}所要達(dá)到的目標(biāo)能用線型函數(shù)描述，且能夠用極值（max或min）來表示；(2)

限定條件：達(dá)到目標(biāo)受到一定的限制，且這些限制能夠用決策變量的線性等式或線性不等式表示；(3)

選擇條件：有多種可選擇的方案供決策者選擇，以便找出最優(yōu)方案。線性規(guī)劃問題的數(shù)學(xué)模型4.建模步驟(1)

確定決策變量：即需要我們作出決策或選擇的量。一般情況下，題目問什么就設(shè)什么為決策變量；(2)

找出所有限定條件：即決策變量受到的所有的約束；(3)

寫出目標(biāo)函數(shù)：即問題所要達(dá)到的目標(biāo)，并明確是max還是min。線性規(guī)劃問題的數(shù)學(xué)模型目標(biāo)函數(shù)：約束條件：5.線性規(guī)劃數(shù)學(xué)模型的一般形式簡(jiǎn)寫為：線性規(guī)劃問題的數(shù)學(xué)模型向量形式：其中：線性規(guī)劃問題的數(shù)學(xué)模型矩陣形式：其中：線性規(guī)劃問題的數(shù)學(xué)模型6.線性規(guī)劃問題的標(biāo)準(zhǔn)形式特點(diǎn)：(1)目標(biāo)函數(shù)求最大值(2)約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零(3)決策變量xj為非負(fù)。線性規(guī)劃問題的數(shù)學(xué)模型（2）如何化標(biāo)準(zhǔn)形式

目標(biāo)函數(shù)的轉(zhuǎn)換

如果是求極小值即，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問題。即

若存在取值無約束的變量，可令其中：

變量的變換若存在取值無約束的變量，則令線性規(guī)劃問題的數(shù)學(xué)模型

約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量

常量bi＜0

的變換:約束方程兩邊乘以（－1）線性規(guī)劃問題的數(shù)學(xué)模型例1.5

將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式用替換，且解:（１）因?yàn)閤3無符號(hào)要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以線性規(guī)劃問題的數(shù)學(xué)模型(2)第一個(gè)約束條件是“≤”號(hào)，在“≤”左端加入松馳變量x4，x4≥0,化為等式；(3)第二個(gè)約束條件是“≥”號(hào)，在“≥”左端減去剩余變量x5，x5≥0；(4)第3個(gè)約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以(-1),將右端常數(shù)項(xiàng)化為正數(shù)；(5)目標(biāo)函數(shù)是最小值，為了化為求最大值，令z′=-z,得到maxz′=-z，即當(dāng)z達(dá)到最小值時(shí)z′達(dá)到最大值，反之亦然;線性規(guī)劃問題的數(shù)學(xué)模型標(biāo)準(zhǔn)形式如下：原問題線性規(guī)劃問題的數(shù)學(xué)模型7.線性規(guī)劃問題的解線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。線性規(guī)劃問題的數(shù)學(xué)模型

可行解：滿足約束條件②、③的解為可行解。所有可行解的集合為可行域。

最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。

基：設(shè)A為約束條件②的m×n階系數(shù)矩陣(m<n)，其秩為m，B是矩陣A中m階滿秩子矩陣（∣B∣≠0），稱B是規(guī)劃問題的一個(gè)基。設(shè)：稱B中每個(gè)列向量Pj

(j=1,2,…,m)為基向量。與基向量Pj

對(duì)應(yīng)的變量xj

為基變量。除基變量以外的變量為非基變量。線性規(guī)劃問題的數(shù)學(xué)模型

基解：某一確定的基B，令非基變量等于零，由約束條件方程②解出基變量，稱這組解為基解。在基解中變量取非0值的個(gè)數(shù)不大于方程數(shù)m，基解的總數(shù)不超過

基可行解：滿足變量非負(fù)約束條件的基本解，簡(jiǎn)稱基可行解?？尚谢簩?duì)應(yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解線性規(guī)劃問題的數(shù)學(xué)模型——6個(gè)。問題：本例的A中一共有幾個(gè)基？線性規(guī)劃問題的數(shù)學(xué)模型例1.7

求線性規(guī)劃問題的所有基矩陣。解:約束方程的系數(shù)矩陣為2×5矩陣r(A)=2，2階子矩陣有10個(gè)，其中基矩陣只有9個(gè)，即線性規(guī)劃問題的數(shù)學(xué)模型在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量?；兞?、非基變量是針對(duì)某一確定基而言的，不同的基對(duì)應(yīng)的基變量和非基變量也不同.

B2=(P1,P4)

XB=(x1,x4)T;N=(P2,P4,P5)XN=(x2,x3,x5)Tx1

x2

x3

x4

x5P1

P2

P3

P4

P5B4=(P2,P3)N=(P1,P4,P5)XB=(x2,x3)T

XN=(x1,x4,x5)T線性規(guī)劃問題的數(shù)學(xué)模型對(duì)Ｂ１來說，x1,x2是基變量，x3,x4,x5是非基變量，令x3=x4=x5=0，則AX=b變?yōu)橐騶B1|≠０，由克萊姆法則知，x1、x2有唯一解x1＝2/5,x2=1則基本解為xi

≥0，也是基本可行解線性規(guī)劃問題的數(shù)學(xué)模型x1<0,因此

不是可行解，也就不是基本可行解。反之，可行解不一定是基本可行解例如

滿足所有約束條件,但不是任何基矩陣的基本解?；窘鉃閷?duì)B2來說，x1,x4為基變量，令非基變量x2,x3,x5為零，得到

，非基變量不為0線性規(guī)劃問題的數(shù)學(xué)模型可見：一個(gè)基本解是由一個(gè)基決定的。注意：基本解僅是資源約束的解，并未要求其非負(fù)，因此其未必可行。圖解法線性規(guī)劃問題的求解方法一般有兩種方法圖解法單純形法兩個(gè)變量、直角坐標(biāo)三個(gè)變量、立體坐標(biāo)適用于任意變量、但必需將一般形式變成標(biāo)準(zhǔn)形式下面我們分析一下簡(jiǎn)單的情況——

只有兩個(gè)決策變量的線性規(guī)劃問題，這時(shí)可以通過圖解的方法來求解。圖解法具有簡(jiǎn)單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。

解題步驟4將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)值。1在直角平面坐標(biāo)系中畫出所有的約束等式，并找出所有約束條件的公共部分，稱為可行域，可行域中的點(diǎn)稱為可行解。2標(biāo)出目標(biāo)函數(shù)值增加或者減小的方向。3若求最大（?。┲?，則令目標(biāo)函數(shù)等值線沿（逆）目標(biāo)函數(shù)值增加的方向平行移動(dòng)，找與可行域最后相交的點(diǎn)，該點(diǎn)就是最優(yōu)解。圖解法圖解法maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例1.8用圖解法求解線性規(guī)劃問題圖解法x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2X1+X2

（7.6，2）DmaxZminZ此點(diǎn)是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值

maxZ=17.2可行域maxZ=2X1+X2圖解法maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZ（3.8，4）34.2=3X1+5.7X2

藍(lán)色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的。可行域圖解法minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此點(diǎn)是唯一最優(yōu)解圖解法246x1x2246無界解(無最優(yōu)解)maxz=x1+2