線性規(guī)劃問題的數(shù)學(xué)模型

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

1.運輸問題2.生產(chǎn)的組織與計劃問題

3.合理下料問題4.配料問題

5.布局問題6.分配問題第2頁,共53頁，2024年2月25日，星期天（二）線性規(guī)劃問題的數(shù)學(xué)模型1.運輸問題

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

運價工地磚廠B1B2B3A1506070A260110160第3頁,共53頁，2024年2月25日，星期天解：設(shè)xij表示由磚廠Ai運往工地Bj磚的數(shù)量（i=1,2；j=1,2,3)運量工地磚廠B1B2B3發(fā)量A1x11x12x1323A2x21x22x2327收量17181550第4頁,共53頁，2024年2月25日，星期天目標(biāo)函數(shù)

約束條件第5頁,共53頁，2024年2月25日，星期天2.生產(chǎn)的組織與計劃問題

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

產(chǎn)品耗用資源

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

第6頁,共53頁，2024年2月25日，星期天

解：假設(shè)生產(chǎn)A產(chǎn)品x1公斤，

B產(chǎn)品x2公斤，x1

，x2稱為決

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

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

約束條件

目標(biāo)函數(shù)第7頁,共53頁，2024年2月25日，星期天

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

⑴

每一個問題都是求一組變量（稱為決策變量）的值。這組變量的一組定值就代表一個具體方案。通常要求這組變量的取值是非負(fù)的。

⑵

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

都有一個期望達(dá)到的目標(biāo)，并且這個目標(biāo)可以表示為決策變量的線性函數(shù)（稱為目標(biāo)函數(shù)）。按所研究問題的不同，要求目標(biāo)函數(shù)值最大化或最小化。我們將具有上述三個特點的最優(yōu)化問題歸結(jié)為線性規(guī)劃問題，其數(shù)學(xué)模型稱為線性規(guī)劃問題的數(shù)學(xué)模型，簡稱線性規(guī)劃數(shù)學(xué)模型。第8頁,共53頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型的一般形式

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

x1,

x2,…,xn稱為決策變量，簡稱變量。第9頁,共53頁，2024年2月25日，星期天滿足約束條件的一組變量的值稱為線性規(guī)劃問題的一個可行解，使目標(biāo)函數(shù)取得最大（或最?。┑目尚薪夥Q為最優(yōu)解。此時，目標(biāo)函數(shù)的值稱為最優(yōu)值。

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

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

其次，確定約束條件，并根據(jù)實際問題添加非負(fù)條件。明確問題中所有的限制條件，并用決策變量的線性等式或不等式表示。一般可用表格形式列出所有的限制數(shù)據(jù)，然后根據(jù)所列出的數(shù)據(jù)寫出相應(yīng)的約束條件，以避免遺漏或重復(fù)所規(guī)定的限制要求。

最后，確定目標(biāo)函數(shù)，并確定是求極大還是求極小。用決策變量的線性函數(shù)來表示實際問題所要達(dá)到的目標(biāo)，得到目標(biāo)函數(shù)。第10頁,共53頁，2024年2月25日，星期天第二節(jié)兩個變量的線性規(guī)劃問題的圖解法例1

求x1、x2的值，使它們滿足并且使目標(biāo)函數(shù)f=2x1+5x2的值最大。圖解法是利用直觀的幾何圖形求解線性規(guī)劃的一種幾何解法第11頁,共53頁，2024年2月25日，星期天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頁,共53頁，2024年2月25日，星期天x1x1+2x2=8x1+2x2=6x1+2x2=2x1+2x2=0x2=3x1=4x1+2x2=80x2例2

若把例1的目標(biāo)函數(shù)改為s=x1+2x2

，最優(yōu)解有

無窮多個，它們對應(yīng)的目標(biāo)函數(shù)值都是8。（見下圖）第13頁,共53頁，2024年2月25日，星期天例3

求x1、x2的值，使它們滿足并且使目標(biāo)函數(shù)s=2x1+2x2的值最小。第14頁,共53頁，2024年2月25日，星期天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頁,共53頁，2024年2月25日，星期天例5

求x1、x2的值，使它們滿足并且使目標(biāo)函數(shù)s=2x1+2x2的值最小。第16頁,共53頁，2024年2月25日，星期天x1x2-x1+

x2=1x1+

x2=-2沒有可行解，當(dāng)然沒有最優(yōu)解。解：第17頁,共53頁，2024年2月25日，星期天（一）線性規(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)型的特點為（1）目標(biāo)函數(shù)為最大值形式（2）約束條件用等式表示且等式右端的常數(shù)為非負(fù)值（3）決策變量非負(fù)。第18頁,共53頁，2024年2月25日，星期天

把一般的線性規(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.約束條件為不等式

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

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

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

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

xj//

代入約束條件和目標(biāo)函數(shù)中。第19頁,共53頁，2024年2月25日，星期天例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頁,共53頁，2024年2月25日，星期天（二）、基本概念

定義在線性規(guī)劃的標(biāo)準(zhǔn)型中，如果有變量只在某一個約束方程中系數(shù)為1，在其余約束方程中系數(shù)全為0，則稱為該約束的一個基變量；如果每個等式約束都有一個基變量，則稱等式約束條件是這些基變量的典型方程組。如果線性規(guī)劃的約束條件是典型方程組，不失一般性，設(shè)n個變量的線性規(guī)劃問題的典型方程組為：第21頁,共53頁，2024年2月25日，星期天其中基變量為x1,

x2,

…

,

xm，從而xm+1,

xm+2,

…

,

xn稱為非基變量。

令非基變量xm+1=0,

xm+2=0,

…

xn=0

，則可求得約束方程的一個解：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)型，從可行域的一個基本可行解開始，轉(zhuǎn)移到另一個基本可行解，并且使目標(biāo)函數(shù)值逐步變優(yōu)，當(dāng)目標(biāo)函數(shù)值達(dá)到最大值時，就得到問題的最優(yōu)解。第22頁,共53頁，2024年2月25日，星期天下面舉例說明單純形法的基本思想

例2

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

解

先將問題化成標(biāo)準(zhǔn)型第23頁,共53頁，2024年2月25日，星期天

顯然x4,

x5為基變量，x1,

x2,

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

x2+

x3+0,令非基變量x1=

x2=

x3

=0則有f=2x1+3

x2+1x3+0=0

,

同時得到一個基本可行解

x1=

x2=

x3

=0,x4=1,x5=3

由f=2x1+3

x2+

x3+0可知，非基變量的系數(shù)都是正數(shù)，若將其中任意一個非基變量變成基變量（取值從0變成正數(shù)）,都可以使目標(biāo)函數(shù)值增加,所以只要在目標(biāo)函數(shù)的表達(dá)式中還存在有正系數(shù)的非基變量，就表示目標(biāo)函數(shù)值還有增加的可能，從而不是最優(yōu)解，就需要將非基變量與基變量進(jìn)行對換。我們把非基變量轉(zhuǎn)換為基變量稱為進(jìn)基。一般選擇正系數(shù)最大的那個非基變量（本例為x2

）為進(jìn)基變量，以求得目標(biāo)函數(shù)值較快的增加。將x2換入到基變量中。同時，還要確定基變量中有一個要換出來成為非基變量。變量由基變量轉(zhuǎn)化成非基變量稱為出基。第24頁,共53頁，2024年2月25日，星期天

怎樣確定出基變量，由（2）式，x2

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

x3仍為非基變量，故x1,

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

隨著x2的值增加，x4,

x5的值會逐漸變小，由于

才能保證x4≥0,

x5≥0

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

x2替換x5

（x5出基），于是得到新的基變量x4,

x2

,非基變量x1,

x3,

x5

。這種確定出基變量的方法稱為最小比值原則。第25頁,共53頁，2024年2月25日，星期天由（2）式寫出用非基變量表示基變量的表達(dá)式：整理得

代入目標(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)基、出基變量，又得到另一個基本可行解

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

=0f=2×1+3×2=8用非基變量表示目標(biāo)函數(shù)f=8-3x3–5x4-1x5第26頁,共53頁，2024年2月25日，星期天式中所有非基變量的系數(shù)均是負(fù)數(shù)，意味著目標(biāo)函數(shù)值不可能再增加，故此時的基本可行解就是最優(yōu)解，最優(yōu)值為8

2．最優(yōu)性檢驗由標(biāo)準(zhǔn)形等式約束條件得代入目標(biāo)函數(shù)進(jìn)行簡單的運算后，用非基變量表示目標(biāo)函數(shù)為稱為非基變量的檢驗數(shù)。將用檢驗數(shù)來判定線性規(guī)劃問題是否有最優(yōu)解，有最優(yōu)解定理。第27頁,共53頁，2024年2月25日，星期天定理

(1)如果關(guān)于非基變量的所有檢驗數(shù)

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

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

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

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

第28頁,共53頁，2024年2月25日，星期天3.單純形表

用表格的形式來表示上面求解線性規(guī)劃問題的單純形法的計算過程可以使計算和檢驗更加簡便。具體方法如下：

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

x1

+c2

x2

+…+cnxn=0且作為等式約束方程組的第m+1個方程，得對方程組(3-1)的增廣矩陣施行初等行變換，化為如下的階梯形矩陣第29頁,共53頁，2024年2月25日，星期天將矩陣表示成單純形表xBb100010

001-f000-f0x1x2…xmxm+1…xnx1x2…xmb1b2bm……………………a1m+1a2m+1amm+1a1na2namn……下面通過具體的例子說明用單純形法求解線性規(guī)劃問題。

第30頁,共53頁，2024年2月25日，星期天例1

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

將該線性規(guī)劃問題化為標(biāo)準(zhǔn)型第31頁,共53頁，2024年2月25日，星期天顯然x3,

x4,

x5為基變量，x1,

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

121

[2]0108400016-f

2

3

00001x3x4x5x1x2x3x4x5初始基本可行解為

x1=

x2=0,x3=12,x4=8,x5=16。由于檢驗系數(shù)有正數(shù)，所以這個基本可行解不是最優(yōu)解。從x1，

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

用最小比值原則確定出基變量的一般方法是：在單純形表中，b列元素與進(jìn)基變量列對應(yīng)的正元素之比，取其比值最小的所對應(yīng)的基變量出基。第32頁,共53頁，2024年2月25日，星期天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注：比值相等時可任選其一

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

非基變量的檢驗數(shù)小于0第33頁,共53頁，2024年2月25日，星期天例2

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

x3,

x4為基變量，x1,

x2為非基變量。可得初始單純形表

XBb[1]-1102-31014-f32000X1X3X4X2X3X4第34頁,共53頁，2024年2月25日，星期天XBb1-11020-23110-f05-30-6X1X2X3X4X1X4有檢驗數(shù)>0系數(shù)列均≤0

無最優(yōu)解例3

用單純形法求解線性規(guī)劃問題第35頁,共53頁，2024年2月25日，星期天解

將該線性規(guī)劃問題化為標(biāo)準(zhǔn)型：F=-f

進(jìn)行換基迭代，計算過程如表第36頁,共53頁，2024年2月25日，星期天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非基變量有檢驗數(shù)<0

，有檢驗數(shù)=0無窮多個最優(yōu)解其中一個最優(yōu)解是x1=6,

x2=0最優(yōu)值為f=-F=-18第37頁,共53頁，2024年2月25日，星期天第四節(jié)兩階段法

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

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

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

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

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

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

y1、

y2,引入輔助線性規(guī)劃問題第40頁,共53頁，2024年2月25日，星期天Z用非基變量表示：

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

x1

x2x3

x4y1y2by1511[8]1010y224320110-Z754100020第41頁,共53頁，2024年2月25日，星期天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ōu)值Z=0，且人工變量均已出基，于是進(jìn)入第二階段。第42頁,共53頁，2024年2月25日，星期天第二階段

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

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

用非基變量表示，由上表最后一次換基迭代知：用單純形法進(jìn)行計算，如下表所示第43頁,共53頁，2024年2月25日，星期天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頁,共53頁，2024年2月25日，星期天例2

用兩階段法求解下面的線性規(guī)劃問題解化成標(biāo)準(zhǔn)型第45頁,共53頁，2024年2月25日，星期天解第一階段

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

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

第46頁,共53頁，2024年2月25日，星期天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頁,共53頁，2024年2月25日，星期天于是得輔助問題的最優(yōu)值Z=0。人工變量y2尚未出基，且y2所在行的非人工人工變量列元素均為零，無法讓y2出基。但是由最后一個單純形表中y2