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

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

1.運(yùn)輸問(wèn)題2.生產(chǎn)的組織與計(jì)劃問(wèn)題

3.合理下料問(wèn)題4.配料問(wèn)題

5.布局問(wèn)題6.分配問(wèn)題第2頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三（二）線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.運(yùn)輸問(wèn)題

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

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

約束條件第5頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三2.生產(chǎn)的組織與計(jì)劃問(wèn)題

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

產(chǎn)品耗用資源

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

第6頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三

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

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

，x2稱為決

策變量，簡(jiǎn)稱變量。得到利潤(rùn)7x1+12x2萬(wàn)元，這一問(wèn)

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

約束條件

目標(biāo)函數(shù)第7頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三

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

⑴

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

⑵

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

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

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

x1,

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

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

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

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

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

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

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

，最優(yōu)解有

無(wú)窮多個(gè)，它們對(duì)應(yīng)的目標(biāo)函數(shù)值都是8。（見(jiàn)下圖）第13頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三例3

求x1、x2的值，使它們滿足并且使目標(biāo)函數(shù)s=2x1+2x2的值最小。第14頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三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ù)無(wú)上界，因此無(wú)最優(yōu)解第15頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三例5

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

x2=1x1+

x2=-2沒(méi)有可行解，當(dāng)然沒(méi)有最優(yōu)解。解：第17頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三（一）線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

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

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

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

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

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

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

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

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

xj//

代入約束條件和目標(biāo)函數(shù)中。第19頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三例1

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

x4≥0

,

x5≥0

，將式中不等式約束條件變換成等式約束條件：⑵將3x1-x2-2x3=-5兩邊同乘-1，變?yōu)?3x1+x2+2x3=5⑶變量x3無(wú)非負(fù)約束，引進(jìn)非負(fù)變量x6,x7，令x3=x7-x6

，代入約束條件和目標(biāo)函數(shù)。得最后，令F=-f，則可將求f的最小值問(wèn)題轉(zhuǎn)化成求F的最大值問(wèn)題。標(biāo)準(zhǔn)型為：第20頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三（二）、基本概念

定義在線性規(guī)劃的標(biāo)準(zhǔn)型中，如果有變量只在某一個(gè)約束方程中系數(shù)為1，在其余約束方程中系數(shù)全為0，則稱為該約束的一個(gè)基變量；如果每個(gè)等式約束都有一個(gè)基變量，則稱等式約束條件是這些基變量的典型方程組。如果線性規(guī)劃的約束條件是典型方程組，不失一般性，設(shè)n個(gè)變量的線性規(guī)劃問(wèn)題的典型方程組為：第21頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三其中基變量為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è)基本可行解開(kāi)始，轉(zhuǎn)移到另一個(gè)基本可行解，并且使目標(biāo)函數(shù)值逐步變優(yōu)，當(dāng)目標(biāo)函數(shù)值達(dá)到最大值時(shí)，就得到問(wèn)題的最優(yōu)解。第22頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三下面舉例說(shuō)明單純形法的基本思想

例2

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

解

先將問(wèn)題化成標(biāo)準(zhǔn)型第23頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三

顯然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

,

同時(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ù)的表達(dá)式中還存在有正系數(shù)的非基變量，就表示目標(biāo)函數(shù)值還有增加的可能，從而不是最優(yōu)解，就需要將非基變量與基變量進(jìn)行對(duì)換。我們把非基變量轉(zhuǎn)換為基變量稱為進(jìn)基。一般選擇正系數(shù)最大的那個(gè)非基變量（本例為x2

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

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

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

x3仍為非基變量，故x1,

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

隨著x2的值增加，x4,

x5的值會(huì)逐漸變小，由于

才能保證x4≥0,

x5≥0

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

x2替換x5

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

x2

,非基變量x1,

x3,

x5

。這種確定出基變量的方法稱為最小比值原則。第25頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三由（2）式寫(xiě)出用非基變量表示基變量的表達(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ù)，說(shuō)明目標(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頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三式中所有非基變量的系數(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)行簡(jiǎn)單的運(yùn)算后，用非基變量表示目標(biāo)函數(shù)為稱為非基變量的檢驗(yàn)數(shù)。將用檢驗(yàn)數(shù)來(lái)判定線性規(guī)劃問(wèn)題是否有最優(yōu)解，有最優(yōu)解定理。第27頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三定理

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

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

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

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

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

第28頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三3.單純形表

用表格的形式來(lái)表示上面求解線性規(guī)劃問(wèn)題的單純形法的計(jì)算過(guò)程可以使計(jì)算和檢驗(yàn)更加簡(jiǎn)便。具體方法如下：

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

x1

+c2

x2

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

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

第30頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三例1

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

將該線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型第31頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三顯然x3,

x4,

x5為基變量，x1,

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

121

[2]0108400016-f

2

3

00001x3x4x5x1x2x3x4x5初始基本可行解為

x1=

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

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

用最小比值原則確定出基變量的一般方法是：在單純形表中，b列元素與進(jìn)基變量列對(duì)應(yīng)的正元素之比，取其比值最小的所對(duì)應(yīng)的基變量出基。第32頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三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頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三例2

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

x3,

x4為基變量，x1,

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

XBb[1]-1102-31014-f32000X1X3X4X2X3X4第34頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三XBb1-11020-23110-f05-30-6X1X2X3X4X1X4有檢驗(yàn)數(shù)>0系數(shù)列均≤0

無(wú)最優(yōu)解例3

用單純形法求解線性規(guī)劃問(wèn)題第35頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三解

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

進(jìn)行換基迭代，計(jì)算過(guò)程如表第36頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三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無(wú)窮多個(gè)最優(yōu)解其中一個(gè)最優(yōu)解是x1=6,

x2=0最優(yōu)值為f=-F=-18第37頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三第四節(jié)兩階段法

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

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

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

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

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

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

y1、

y2,引入輔助線性規(guī)劃問(wèn)題第40頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三Z用非基變量表示：

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

x1

x2x3

x4y1y2by1511[8]1010y224320110-Z754100020第41頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三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由于得到輔助問(wèn)題的最優(yōu)值Z=0，且人工變量均已出基，于是進(jìn)入第二階段。第42頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三第二階段

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

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

用非基變量表示，由上表最后一次換基迭代知：用單純形法進(jìn)行計(jì)算，如下表所示第43頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三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ī)劃問(wèn)題最優(yōu)解為

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

f=40/3

第44頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三例2

用兩階段法求解下面的線性規(guī)劃問(wèn)題解化成標(biāo)準(zhǔn)型第45頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三解第一階段

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

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

第46頁(yè)，講稿共53頁(yè)，2023年5月2日，星期三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è)，講稿共53頁(yè)，2023年5月2日，星期三于是得輔助問(wèn)題的最優(yōu)值Z=0。人工變量y2尚未出基，且y2所在行的非人工人工變量列元素均為零，無(wú)法讓y2出基。但是由最后