線性規(guī)劃問題的數(shù)學(xué)模型省名師優(yōu)質(zhì)課獲獎(jiǎng)?wù)n件市賽課一等獎(jiǎng)?wù)n件

數(shù)學(xué)建模系列講座

（一）線性規(guī)劃模型第1頁線性規(guī)劃問題第一節(jié)線性規(guī)劃問題數(shù)學(xué)模型（一）引言線性規(guī)劃是運(yùn)籌學(xué)主要分支之一，也是研究較早、發(fā)展較快、應(yīng)用較廣而且比較成熟一個(gè)分支。自1947年線性規(guī)劃被成功利用于工業(yè)、交通、農(nóng)業(yè)和軍事等各個(gè)領(lǐng)域后，現(xiàn)在它已成為管理科學(xué)主要基礎(chǔ)和伎倆之一。伴隨計(jì)算機(jī)普及，它適應(yīng)領(lǐng)域越來越廣泛。線性規(guī)劃研究問題主要有兩類：一是一項(xiàng)任務(wù)確定后，怎樣統(tǒng)籌安排，盡可能作到用最少人力物力資源去完成這一任務(wù)。二是已經(jīng)有一定數(shù)量人力物力資源，怎樣安排使用他們，使得完成任務(wù)最多。其實(shí)這兩類問題是一個(gè)問題兩個(gè)方面，就是所謂尋求整個(gè)問題某個(gè)整體指標(biāo)最優(yōu)問題。

1.運(yùn)輸問題2.生產(chǎn)組織與計(jì)劃問題3.合理下料問題4.配料問題5.布局問題6.分配問題第2頁（二）線性規(guī)劃問題數(shù)學(xué)模型1.運(yùn)輸問題

設(shè)有兩個(gè)磚廠A1、A2。其產(chǎn)量分別為23萬塊與27萬塊。它們生產(chǎn)供給B1、B2、B3三個(gè)工地。其需要量分別為17萬塊、18萬塊和15萬塊。自各產(chǎn)地到各工地運(yùn)價(jià)格以下表：問應(yīng)怎樣調(diào)運(yùn)，才使總運(yùn)費(fèi)最省。

運(yùn)價(jià)工地磚廠B1B2B3A1506070A260110160第3頁解：設(shè)xij表示由磚廠Ai運(yùn)往工地Bj磚數(shù)量（i=1,2；j=1,2,3)運(yùn)量工地磚廠B1B2B3發(fā)量A1x11x12x1323A2x21x22x2327收量17181550第4頁目標(biāo)函數(shù)約束條件第5頁2.生產(chǎn)組織與計(jì)劃問題

某工廠生產(chǎn)A、B兩種產(chǎn)品，現(xiàn)有資源數(shù)、生產(chǎn)每單位產(chǎn)品所需原材料數(shù)以及每單位產(chǎn)品可得利潤以下表所表示。問怎樣制訂生產(chǎn)計(jì)劃使兩種產(chǎn)品總利潤最大？單位產(chǎn)品

產(chǎn)品耗用資源

資源A（千克）B（千克）現(xiàn)有資源銅（噸）94360電力（千瓦）45200勞動(dòng)日（個(gè)）310300單位利潤（萬元/千克）712

第6頁

解：假設(shè)生產(chǎn)A產(chǎn)品x1千克，B產(chǎn)品x2千克，x1，x2稱為決

策變量，簡稱變量。得到利潤7x1+12x2萬元，這一問

題數(shù)學(xué)模型為：

約束條件

目標(biāo)函數(shù)第7頁

上述例子即使有不一樣實(shí)際內(nèi)容，不過都可歸結(jié)為一類優(yōu)化問題。從數(shù)學(xué)上說它們含有以下共同特征：

⑴

每一個(gè)問題都是求一組變量（稱為決議變量）值。這組變量一組定值就代表一個(gè)詳細(xì)方案。通常要求這組變量取值是非負(fù)。

⑵

存在一定限制條件，稱為約束條件。這些約束條件都能夠用一組線性等式或不等式來表示。⑶

都有一個(gè)期望到達(dá)目標(biāo)，而且這個(gè)目標(biāo)能夠表示為決議變量線性函數(shù)（稱為目標(biāo)函數(shù)）。按所研究問題不同，要求目標(biāo)函數(shù)值最大化或最小化。我們將含有上述三個(gè)特點(diǎn)最優(yōu)化問題歸結(jié)為線性規(guī)劃問題，其數(shù)學(xué)模型稱為線性規(guī)劃問題數(shù)學(xué)模型，簡稱線性規(guī)劃數(shù)學(xué)模型。第8頁線性規(guī)劃問題數(shù)學(xué)模型普通形式

（1）式稱為目標(biāo)函數(shù)（2）式中等式或不等式稱為約束條件（3）式是非負(fù)約束條件

x1,

x2,…,xn稱為決議變量，簡稱變量。第9頁滿足約束條件一組變量值稱為線性規(guī)劃問題一個(gè)可行解，使目標(biāo)函數(shù)取得最大（或最?。┛尚薪夥Q為最優(yōu)解。此時(shí)，目標(biāo)函數(shù)值稱為最優(yōu)值。

建立線性規(guī)劃數(shù)學(xué)模型步驟

首先，確定決議變量。線性規(guī)劃數(shù)學(xué)模型建得是否輕易，求解是否方便，取決于決議變量選取是否得當(dāng)。

其次，確定約束條件，并依據(jù)實(shí)際問題添加非負(fù)條件。明確問題中全部限制條件，并用決議變量線性等式或不等式表示。普通可用表格形式列出全部限制數(shù)據(jù)，然后依據(jù)所列出數(shù)據(jù)寫出對應(yīng)約束條件，以防止遺漏或重復(fù)所要求限制要求。

最終，確定目標(biāo)函數(shù)，并確定是求極大還是求極小。用決議變量線性函數(shù)來表示實(shí)際問題所要到達(dá)目標(biāo)，得到目標(biāo)函數(shù)。第10頁第二節(jié)兩個(gè)變量線性規(guī)劃問題圖解法例1求x1、x2值，使它們滿足而且使目標(biāo)函數(shù)f=2x1+5x2值最大。圖解法是利用直觀幾何圖形求解線性規(guī)劃一個(gè)幾何解法第11頁x12x1+5x2=192x1+5x2=152x1+5x2=82x1+5x2=4x2=3x1=4x1+2x2=80x2最優(yōu)解為x1=2，x2=3相應(yīng)目標(biāo)函數(shù)最大值為S=2*2+5*3=19第12頁x1x1+2x2=8x1+2x2=6x1+2x2=2x1+2x2=0x2=3x1=4x1+2x2=80x2例2

若把例1目標(biāo)函數(shù)改為s=x1+2x2，最優(yōu)解有

無窮多個(gè)，它們對應(yīng)目標(biāo)函數(shù)值都是8。（見下列圖）第13頁例3求x1、x2值，使它們滿足而且使目標(biāo)函數(shù)s=2x1+2x2值最小。第14頁x1x20X1-x2=1X1+2x2=02X1+2x2=22X1+2x2=62X1+2x2=102X1+2x2=16最優(yōu)解X1=1，x2=0,目標(biāo)函數(shù)最小值s=2解：例4

若把例3改為使目標(biāo)函數(shù)值最大，從圖可看出目標(biāo)函數(shù)無上界，所以無最優(yōu)解第15頁例5

求x1、x2值，使它們滿足而且使目標(biāo)函數(shù)s=2x1+2x2值最小。第16頁x1x2-x1+

x2=1x1+

x2=-2沒有可行解，當(dāng)然沒有最優(yōu)解。解：第17頁（一）線性規(guī)劃問題標(biāo)準(zhǔn)形式

線性規(guī)劃問題數(shù)學(xué)模型有各種不一樣形式。為了便于討論，需要將線性規(guī)劃數(shù)學(xué)模型寫成統(tǒng)一格式。

線性規(guī)劃問題標(biāo)準(zhǔn)型是：第三節(jié)單純形法約束條件（2）式又稱等式約束（3）式稱非負(fù)約束。標(biāo)準(zhǔn)型特點(diǎn)為（1）目標(biāo)函數(shù)為最大值形式（2）約束條件用等式表示且等式右端常數(shù)為非負(fù)值（3）決議變量非負(fù)。第18頁

把普通線性規(guī)劃問題化成標(biāo)準(zhǔn)型過程稱為線性規(guī)劃問題標(biāo)準(zhǔn)化。線性規(guī)劃問題標(biāo)準(zhǔn)化方法以下：1.求目標(biāo)函數(shù)最小值

令F=-f，則可將求f最小值問題轉(zhuǎn)化成求F最大值問題，即2.約束條件為不等式

引入一個(gè)非負(fù)變量xn+i，轉(zhuǎn)化為線性等式，稱

xn+i為松弛變量。3.若有bi≤0可在該約束條件兩邊同乘-1，化為

4.假如有某個(gè)變量xj無非負(fù)約束

可引進(jìn)非負(fù)變量xj/,xj//，令xj=xj/-

xj//

代入約束條件和目標(biāo)函數(shù)中。第19頁例1

將下面線性規(guī)劃問題化成標(biāo)準(zhǔn)型。解⑴引進(jìn)松弛變量

x4≥0

,

x5≥0

，將式中不等式約束條件變換成等式約束條件：⑵將3x1-x2-2x3=-5兩邊同乘-1，變?yōu)?3x1+x2+2x3=5⑶變量x3無非負(fù)約束，引進(jìn)非負(fù)變量x6,x7，令x3=x7-x6，代入約束條件和目標(biāo)函數(shù)。得最終，令F=-f，則可將求f最小值問題轉(zhuǎn)化成求F最大值問題。標(biāo)準(zhǔn)型為：第20頁（二）、基本概念

定義在線性規(guī)劃標(biāo)準(zhǔn)型中，假如有變量只在某一個(gè)約束方程中系數(shù)為1，在其余約束方程中系數(shù)全為0，則稱為該約束一個(gè)基變量；假如每個(gè)等式約束都有一個(gè)基變量，則稱等式約束條件是這些基變量經(jīng)典方程組。假如線性規(guī)劃約束條件是經(jīng)典方程組，不失普通性，設(shè)n個(gè)變量線性規(guī)劃問題經(jīng)典方程組為：第21頁其中基變量為x1,

x2,

…

,

xm，從而xm+1,

xm+2,

…

,

xn稱為非基變量。

令非基變量xm+1=0,

xm+2=0,

…

xn=0，則可求得約束方程一個(gè)解：x1=b1,

x2=b2,

…

,

xm=bm,

xm+1=0

,

xm+2=0,

…

,

xn=0稱為基本解。假如bi≥0(i=1,2,…,m)則稱此基本解為基本可行解。

(三)、單純形法1．單純形法基本思想單純形法基本思緒是：依據(jù)標(biāo)準(zhǔn)型，從可行域一個(gè)基本可行解開始，轉(zhuǎn)移到另一個(gè)基本可行解，而且使目標(biāo)函數(shù)值逐步變優(yōu)，當(dāng)目標(biāo)函數(shù)值到達(dá)最大值時(shí)，就得到問題最優(yōu)解。第22頁下面舉例說明單純形法基本思想

例2

求解線性規(guī)劃問題

解

先將問題化成標(biāo)準(zhǔn)型第23頁顯然x4,

x5為基變量，x1,

x2,

x3為非基變量，約束條件是經(jīng)典方程組。由（1）可得：將（2）代入目標(biāo)函數(shù)可得f=2x1+3

x2+

x3+0,令非基變量x1=

x2=

x3

=0則有f=2x1+3

x2+1x3+0=0

,

同時(shí)得到一個(gè)基本可行解

x1=

x2=

x3

=0,x4=1,x5=3

由f=2x1+3

x2+

x3+0可知，非基變量系數(shù)都是正數(shù)，若將其中任意一個(gè)非基變量變成基變量（取值從0變成正數(shù)）,都能夠使目標(biāo)函數(shù)值增加,所以只要在目標(biāo)函數(shù)表示式中還存在有正系數(shù)非基變量，就表示目標(biāo)函數(shù)值還有增加可能，從而不是最優(yōu)解，就需要將非基變量與基變量進(jìn)行對換。我們把非基變量轉(zhuǎn)換為基變量稱為進(jìn)基。普通選擇正系數(shù)最大那個(gè)非基變量（本例為x2）為進(jìn)基變量，以求得目標(biāo)函數(shù)值較快增加。將x2換入到基變量中。同時(shí)，還要確定基變量中有一個(gè)要換出來成為非基變量。變量由基變量轉(zhuǎn)化成非基變量稱為出基。第24頁怎樣確定出基變量，由（2）式，x2

為進(jìn)基變量，x1,

x3仍為非基變量，故x1,

x3值為零。代入（2）式可得

伴隨x2值增加，x4,

x5值會(huì)逐步變小，因?yàn)?/p>

才能確保x4≥0,

x5≥0

（即解可行性）。當(dāng)x2=9/4時(shí)，x5=0。即用

x2替換x5（x5出基），于是得到新基變量x4,

x2

,非基變量x1,

x3,

x5

。這種確定出基變量方法稱為最小比值標(biāo)準(zhǔn)。第25頁由（2）式寫出用非基變量表示基變量表示式：整理得

代入目標(biāo)函數(shù)得f=27/4+5/4

x1-17/4

x3–9/4x5令非基變量x1=

x3=

x5

=0得一新基本可行解

x1=0,x2=9/4,x3=0,x4=1/4,x5

=0代入代入目標(biāo)函數(shù)

得對應(yīng)目標(biāo)函數(shù)值

f=27/4非基變量x1系數(shù)是正數(shù)，說明目標(biāo)函數(shù)值還可能增加，于是再用上述方法，確定進(jìn)基、出基變量，又得到另一個(gè)基本可行解

x1=1,x2=2,x3=x4=x5

=0f=2×1+3×2=8用非基變量表示目標(biāo)函數(shù)f=8-3x3–5x4-1x5第26頁式中全部非基變量系數(shù)均是負(fù)數(shù)，意味著目標(biāo)函數(shù)值不可能再增加，故此時(shí)基本可行解就是最優(yōu)解，最優(yōu)值為8

2．最優(yōu)性檢驗(yàn)由標(biāo)準(zhǔn)形等式約束條件得代入目標(biāo)函數(shù)進(jìn)行簡單運(yùn)算后，用非基變量表示目標(biāo)函數(shù)為稱為非基變量檢驗(yàn)數(shù)。將用檢驗(yàn)數(shù)來判定線性規(guī)劃問題是否有最優(yōu)解，有最優(yōu)解定理。第27頁定理(1)假如關(guān)于非基變量全部檢驗(yàn)數(shù)

則基本可行解就是最優(yōu)解(2)假如關(guān)于非基變量全部檢驗(yàn)數(shù)且其中有一個(gè)非基變量xm+k檢驗(yàn)數(shù)為零

則該線性規(guī)劃問題有無窮多個(gè)最優(yōu)解(3)假如存在非基變量xm+k檢驗(yàn)數(shù)>0

且xm+k對應(yīng)系數(shù)列均小于等于零

則該線性規(guī)劃問題無最優(yōu)解

第28頁3.單純形表

用表格形式來表示上面求解線性規(guī)劃問題單純形法計(jì)算過程能夠使計(jì)算和檢驗(yàn)愈加簡便。詳細(xì)方法以下：

將目標(biāo)函數(shù)式改寫為-f+c1

x1

+c2

x2

+…+cnxn=0且作為等式約束方程組第m+1個(gè)方程，得對方程組(3-1)增廣矩陣施行初等行變換，化為以下階梯形矩陣第29頁將矩陣表示成單純形表xBb100010

001-f000-f0x1x2…xmxm+1…xnx1x2…xmb1b2bm……………………a1m+1a2m+1amm+1a1na2namn……下面經(jīng)過詳細(xì)例子說明用單純形法求解線性規(guī)劃問題。

第30頁例1

用單純形法解線性規(guī)劃問題解

將該線性規(guī)劃問題化為標(biāo)準(zhǔn)型第31頁顯然x3,

x4,

x5為基變量，x1,

x2為非基變量?？傻脝渭冃伪?下表所表示）。這種直接從線性規(guī)劃問題得到單純形表稱為初始單純形表xBb22100

121

[2]0108400016-f

2

3

00001x3x4x5x1x2x3x4x5初始基本可行解為x1=

x2=0,x3=12,x4=8,x5=16。因?yàn)闄z驗(yàn)系數(shù)有正數(shù)，所以這個(gè)基本可行解不是最優(yōu)解。從x1，

x2中選一個(gè)檢驗(yàn)數(shù)最大變量x2進(jìn)基。依據(jù)最小比值標(biāo)準(zhǔn)(mim{12/2,8/2}=4)確定,x4出基。進(jìn)基變量x2所在列與出基變量x4所在行交叉處元素稱為主元，加上方括號(hào)，再施行行初等變換，將主元所在列主元化為1，其余元素化為0，得下表注

用最小比值標(biāo)準(zhǔn)確定出基變量普通方法是：在單純形表中，b列元素與進(jìn)基變量列對應(yīng)正元素之比，取其比值最小所對應(yīng)基變量出基。第32頁xBb

1

01-104

1/2101/20

4[4]000

16-f1/200

-3/20-12x3x2x5x2x3x5x4x11xBb001-1-1/400101/2-1/8210004-f000

-3/2

-1/8-14x1x2x3x4x5x3注：比值相等時(shí)可任選其一

x2x11/4最優(yōu)解為x1=4x2=2x3=x4=x5=0目標(biāo)函數(shù)值為f=14

非基變量檢驗(yàn)數(shù)小于0第33頁例2

用單純形法求解線性規(guī)劃問題解

x3,

x4為基變量，x1,

x2為非基變量?？傻贸跏紗渭冃伪?/p>

XBb[1]-1102-31014-f32000X1X3X4X2X3X4第34頁XBb1-11020-23110-f05-30-6X1X2X3X4X1X4有檢驗(yàn)數(shù)>0系數(shù)列均≤0

無最優(yōu)解例3用單純形法求解線性規(guī)劃問題第35頁解

將該線性規(guī)劃問題化為標(biāo)準(zhǔn)型：F=-f進(jìn)行換基迭代，計(jì)算過程如表第36頁XBb[1]11006120108010013-F33000011100601-1102010013-F00-300-18XBb[1]11006120108010013-F33000011100601-1102010013-F00-300-18XBb[1]11006120108010013-F33000011100601-1102010013-F00-300-18xBb

[1]

1100

6

12010

801003-F

33

0000

11100601-110

201003-F0

0

-300-18

x1x4

x3x5

x2

x3x4x5x1x4x511非基變量有檢驗(yàn)數(shù)<0，有檢驗(yàn)數(shù)=0無窮多個(gè)最優(yōu)解其中一個(gè)最優(yōu)解是x1=6,

x2=0最優(yōu)值為f=-F=-18第37頁第四節(jié)兩階段法

求解線性規(guī)劃問題單純形法必須滿足每個(gè)等式約束都有一個(gè)基變量即線性規(guī)劃約束條件是經(jīng)典方程組，但經(jīng)常出現(xiàn)情況是線性規(guī)劃標(biāo)準(zhǔn)型約束條件不是經(jīng)典方程組，從而不含有初始單純形表，這時(shí)，需要在線性規(guī)劃問題中加入人工變量，把問題變?yōu)榧s束條件是經(jīng)典方程組情形，再按上述方法換基迭代求出最優(yōu)解。

人工變量是后加入原約束方程組中虛擬變量，我們必須把它們從基變量中逐步替換掉。若經(jīng)過基變換，基變量中不再含有些人工變量，這表示原問題有解；若經(jīng)過基變換，最終在基中還有一個(gè)或幾個(gè)人工變量，這意味著原問題無可行解。兩階段法是處理人工變量方法之一，它是將加入人工變量后線性規(guī)劃問題分成兩階段求解。第38頁第一階段：判斷原線性規(guī)劃問題是否有基本可行解。其方法是：對于線性規(guī)劃問題標(biāo)準(zhǔn)型目標(biāo)函數(shù)、等式約束、非負(fù)約束引入人工變量y1,

y2,…,ym，結(jié)構(gòu)一個(gè)輔助線性規(guī)劃問題。

對輔助線性規(guī)劃問題應(yīng)用單純形法，求出輔助問題最優(yōu)解。若最優(yōu)值Z=0，說明全部些人工變量都變換為非基變量，表明原問題已得到一個(gè)基本可行解，則進(jìn)入第二階段；不然原問題無可行解，計(jì)算結(jié)束。第39頁第二階段：在第一階段所得初始單純形表基礎(chǔ)上，進(jìn)行換基迭代。將第一階段最終計(jì)算表中目標(biāo)函數(shù)系數(shù)換成原問題目標(biāo)函數(shù)系數(shù)，劃去人工變量所在列，完成單純形表，就得到求解原問題初始單純形表。然后用單純形法進(jìn)行計(jì)算求出最優(yōu)解。例1

用兩階段法求解下面線性規(guī)劃問題解第一階段

：第一、第二約束中暫缺基變量，分別引入人工變量y1、

y2,引入輔助線性規(guī)劃問題第40頁Z用非基變量表示：

用單純形表進(jìn)行換基迭代以下XBb511[8]101024320110-Z7541000201001-Z00011102-Z0000-1-10XB

x1

x2x3

x4y1y2by1511[8]1010y224320110-Z754100020第41頁XBx1x2x3x4

y1y2b

x45/81/81/811/805/4y23/4[15/4]11/40-1/4115/2-Z3/415/411/40-5/4015/2

x4

3/501/3012/15-1/301x21/5111/150-1/154/152-Z0000-1-10因?yàn)榈玫捷o助問題最優(yōu)值Z=0，且人工變量均已出基，于是進(jìn)入第二階段。第42頁第二階段

在第一階段最終表中劃去人工變量所在列，并將-Z行換成

-f行即得原問題初始單純形表。這里需注意是，填–f行前，需將f

用非基變量表示，由上表最終一次換基迭代知：用單純形法進(jìn)行計(jì)算，以下表所表示第43頁XBx1x2x3x4bx4[3/5]01/3011x21/5111/1502-f20-1/30-10x1101/185/35/3x20113/18-1/35/3-f00-4/9-10/3-40/3原線性規(guī)劃問題最優(yōu)解為

x1=5/3,x2=5/3,x3=x4=0最優(yōu)值為

f=40/3

第44頁例2

用兩階段法求解下面線性規(guī)劃問題解化成標(biāo)準(zhǔn)型第45頁解第一階段

：引入人工變量y1、y2、y3,引入輔助線性規(guī)劃問題Z用非基變量表示：

用單純形表進(jìn)行換基迭代以下：

第46頁xBx1x2x3y1y2y3by195010014y213-20102y3[3]-230014-Z136100020y10[11]-910-32y2011/3-301-1/32/3x11-2/31001/34/3-Z044/3-1200-13/38/3x201-9/111/110-3/112/11y2000-1/312/30x1105/112/3305/3316/11-Z000-4/30-1/30第47頁于是得輔助問題最優(yōu)值Z=0。人工變量y2還未出基，且y2所在行非人工人工變量列元素均為零，無法讓y2出基。不過由最終一個(gè)單純形表中y2所在行，得這表明原問題約束方程組中第二個(gè)方程可由第一個(gè)方程減去二倍第三個(gè)方程得出。所以，第二個(gè)方程是多出，故最終一個(gè)迭代基變量y2所