第2章-線性規(guī)劃(第1節(jié))

線性規(guī)劃問題

線性規(guī)劃模型

線性規(guī)劃解的基本概念

線性規(guī)劃的圖解

利用EXCEL求解線性規(guī)劃模型行解

單純形法

第二章線性規(guī)劃（第1節(jié)）

某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如表2-1所示。該工廠每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問應(yīng)如何安排計(jì)劃使該工廠獲利最多？資源

產(chǎn)品ⅠⅡ

擁有量

設(shè)備12

8臺(tái)時(shí)原材料A

40

16kg原材料B04

12kg§1線性規(guī)劃問題—例1如何用數(shù)學(xué)關(guān)系式描述這問題，必須考慮：設(shè)分別表示計(jì)劃生產(chǎn)產(chǎn)品Ⅰ、Ⅱ的數(shù)量，稱它為決策變量；(確定決策變量階段)生產(chǎn)數(shù)量的多少受資源擁有量的限制，這是約

束條件；

(確定約束條件階段)如何安排生產(chǎn)，使利潤(rùn)最大，這是目標(biāo)。(確定目

標(biāo)函數(shù)階段)§1線性規(guī)劃問題—例1

數(shù)學(xué)模型§1線性規(guī)劃問題—例1

目標(biāo)函數(shù)：約束條件：靠近某河流有兩個(gè)化工廠(見圖2-1)，流經(jīng)第一化工廠的河流流量為每天500萬立方米，在兩個(gè)工廠之間有一條流量為每天200萬立方米的支流。

§1線性規(guī)劃問題—例2圖2-1§1線性規(guī)劃問題—例2第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬立方米，第二化工廠每天排放這種工業(yè)污水1.4萬立方米。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%。這兩個(gè)工廠都需各自處理一部分工業(yè)污水。第一化工廠處理工業(yè)污水的成本是1000元/萬立方米。第二化工廠處理工業(yè)污水的成本是800元/萬立方米?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個(gè)工廠總的處理工業(yè)污水費(fèi)用最小。

建模型之前的分析和計(jì)算

設(shè)：第一化工廠每天處理工業(yè)污水量為x1萬立方米，第二化工廠每天處理工業(yè)污水量為x2萬立方米

§1線性規(guī)劃問題—例2數(shù)學(xué)模型§1線性規(guī)劃問題—例2

目標(biāo)函數(shù)：約束條件：§1線性規(guī)劃問題—例3

WyndorGlass公司生產(chǎn)高質(zhì)量的玻璃產(chǎn)品，包括窗和玻璃門，擁有3個(gè)工廠。鋁框架和硬件在工廠1制造，木質(zhì)框架在工廠2生產(chǎn)，玻璃生產(chǎn)和產(chǎn)品組裝在工廠3完成。現(xiàn)有兩種產(chǎn)品：8英尺玻璃門（產(chǎn)品1），4*6英尺框架（產(chǎn)品2）。產(chǎn)品1需要工廠1和工廠3的生產(chǎn)能力，分別是1小時(shí)和3小時(shí)，而不需要工廠2的生產(chǎn)能力;產(chǎn)品2需要工廠2和工廠3的生產(chǎn)能力，分別是2小時(shí)和2小時(shí)，而不需要工廠1的生產(chǎn)能力.工廠1每周可用生產(chǎn)時(shí)間為4小時(shí),工廠2每周可用生產(chǎn)時(shí)間為12小時(shí)，工廠3每周可用生產(chǎn)時(shí)間為18小時(shí)，每批產(chǎn)品1的利潤(rùn)為3（千）美元，每批產(chǎn)品2的利潤(rùn)為5（千）美元.試確定該如何安排產(chǎn)品的生產(chǎn)？建模過程如下：§1線性規(guī)劃問題—例3

1、確定決策變量。設(shè)分別為每周計(jì)劃生產(chǎn)產(chǎn)品1、2的數(shù)量。

2、確定目標(biāo)函數(shù)。公司要求利潤(rùn)最大，設(shè)Z表示企業(yè)的利潤(rùn)，

則有

3、確定約束條件。該問題有有三個(gè)工廠的生產(chǎn)能力限制，據(jù)此

可建立三種資源約束如下：

工廠1：

工廠2：

工廠3：

可得上述問題的數(shù)學(xué)模型為：§1線性規(guī)劃問題—例3§2線性規(guī)劃模型

線性規(guī)劃模型的一般形式目標(biāo)函數(shù)：約束條件：

線性規(guī)劃模型的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：約束條件：§2線性規(guī)劃解的基本概念—1

可行解。凡是滿足所有約束條件的所有解成為可行解。所有的可行解構(gòu)成可行解域，簡(jiǎn)稱可行域?；窘?。所有約束條件直線的交點(diǎn)對(duì)應(yīng)的解稱為基本解?；究尚薪?。位于可行解域邊界上的約束條件直線的交點(diǎn)對(duì)應(yīng)的解。最優(yōu)解。凡使得目標(biāo)函數(shù)值達(dá)到最優(yōu)（最大或最?。┑目尚薪獬蔀樽顑?yōu)解。

這里介紹一下線性規(guī)劃解的幾個(gè)基本概念：最優(yōu)解可行域目標(biāo)函數(shù)線460x1x2§3線性規(guī)劃解的基本概念—29基可行解本解基本解線性規(guī)劃的可行域是凸集線性規(guī)劃的最優(yōu)解在極點(diǎn)上凸集凸集不是凸集極點(diǎn)

可行域的性質(zhì)：最優(yōu)解可行域目標(biāo)函數(shù)線460x1x2§4線性規(guī)劃的圖解法9基可行解本解基本解§5利用EXCEL求解線性規(guī)劃模型這里以線性規(guī)劃模型3為例，來講解利用EXCEL求解的一般過程和方法。其規(guī)劃模型如下：

§5利用EXCEL求解線性規(guī)劃模型（練習(xí)1）練1：明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機(jī)加工和裝配三個(gè)車間，已知生產(chǎn)單位產(chǎn)品需要各車間的工作時(shí)間及各車間的資源限制如下表2-2所示。另外，該工廠每生產(chǎn)一件產(chǎn)品甲可獲利23元，每生產(chǎn)一件產(chǎn)品乙可獲利25元，每生產(chǎn)一件產(chǎn)品丙可獲利22元，問：公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？數(shù)學(xué)模型

目標(biāo)函數(shù)：約束條件：§5利用EXCEL求解線性規(guī)劃模型（練習(xí)1）§5利用EXCEL求解線性規(guī)劃模型（練習(xí)2）練2：某工廠要做100套鋼架，每套用長(zhǎng)為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長(zhǎng)7.4m，問：應(yīng)如何下料，可使所用原料最省件？數(shù)學(xué)模型

目標(biāo)函數(shù)：約束條件：§5利用EXCEL求解線性規(guī)劃模型（練習(xí)2）6.1單純形法的求解思路6.2單純形法求解過程的應(yīng)用舉例6.3單純形表6.4單純形的經(jīng)濟(jì)信息§6單純形法(重點(diǎn)、難點(diǎn))一般線性規(guī)劃問題具有線性方程組的變量數(shù)大于方程個(gè)數(shù)，這時(shí)有不定的解。但可以從線性方程組中找出一個(gè)個(gè)的單純形，每一個(gè)單純形可以求得一組解，然后再判斷該解使目標(biāo)函數(shù)值是增大還是變小，決定下一步選擇的單純形。這就是迭代，直到目標(biāo)函數(shù)實(shí)現(xiàn)最大值或最小值為止。這樣問題就得到了最優(yōu)解，先舉一例來說明?！?.1單純形法求解線性規(guī)劃的思路

以例1來討論如何用單純形法求解。通過引入松弛變量將例1的數(shù)?；癁闃?biāo)準(zhǔn)型：§6.1單純形法求解線過程的應(yīng)用例

需要注意的是，如果數(shù)模的目標(biāo)函數(shù)是Min型，則要轉(zhuǎn)化為Max型。如目標(biāo)函數(shù)由于，令則原目標(biāo)函數(shù)化為Max型為：

約束方程(2-2)式的系數(shù)矩陣從(2-2)式中可以看到x3,x4,x5的系數(shù)列向量

P3,P4,P5是線性獨(dú)立的，這些向量構(gòu)成一個(gè)基

對(duì)應(yīng)于B的變量x3,x4,x5為基變量.

從(2-2)式中可以得到（2-3）式

將(2-3)式代入目標(biāo)函數(shù)(2-1)

得到當(dāng)令非基變量x1=x2=0，便得到z=0。這時(shí)得到一個(gè)基可行解X(0)X(0)=(0,0,8,16,12)T

這個(gè)基可行解表示：工廠沒有安排生產(chǎn)產(chǎn)品Ⅰ、Ⅱ；資源都沒有被利用，所以工廠的利潤(rùn)指標(biāo)z=0。

第一步：確定初始基本可行解從分析目標(biāo)函數(shù)的表達(dá)式(2-4)可以看到非基變量x1,x2(即沒有安排生產(chǎn)產(chǎn)品Ⅰ，Ⅱ)的系數(shù)都是正數(shù)，因此將非基變量變換為基變量，目標(biāo)函數(shù)的值就可能增大。從經(jīng)濟(jì)意義上講，安排生產(chǎn)產(chǎn)品Ⅰ或Ⅱ，就可以使工廠的利潤(rùn)指標(biāo)增加。所以只要在目標(biāo)函數(shù)(2-4)的表達(dá)式中還存在有正系數(shù)的非基變量，這表示目標(biāo)函數(shù)值還有增加的可能，就需要將非基變量與基變量進(jìn)行對(duì)換。

如何確定換入，換出變量一般選擇正系數(shù)最大的那個(gè)非基變量x2為換入變量，將它換入到基變量中去，同時(shí)還要確定基變量中有一個(gè)要換出來成為非基變量，可按以下方法來確定換出變量。現(xiàn)分析(2-3)式，當(dāng)將x2定為換入變量后，必須從x3,x4,x5中確定一個(gè)換出變量，并保證其余的都是非負(fù)，即x3,x4,x5≥0。第二步：確定入基變量與出基變量

當(dāng)x1=0,由(2-3)式得到

x2取何值時(shí)，才能滿足非負(fù)要求？

從(2-5)式中可以看出，只有選擇x2=min(8/2,-,12/4)=3時(shí)，才能使(2-5)式成立。因當(dāng)x2=3時(shí)，基變量x5=0，這就決定用x2去替換x5。

以上數(shù)學(xué)描述說明了每生產(chǎn)一件產(chǎn)品Ⅱ，需要用掉各種資源數(shù)為(2，0，4)。由這些資源中的薄弱環(huán)節(jié)，就能確定產(chǎn)品Ⅱ的產(chǎn)量。這里就是由原材料B的數(shù)量確定了產(chǎn)品Ⅱ的產(chǎn)量x2=12/4=3件。

為了求得以x3,x4,x2為基變量的一個(gè)基可行解和進(jìn)一步分析問題，需將(2-3)中x2的位置與x5的位置對(duì)換。得到

用高斯消去法將(2-6)式中x2的系數(shù)列向量變換為單位列向量。其運(yùn)算步驟是：③′=③/4；①′=①-2×③′;②′=②,并將結(jié)果仍按原順序排列有：

再將(2-7)式代入目標(biāo)函數(shù)(2-1)式得到

第三步：確定新解從目標(biāo)函數(shù)的表達(dá)式(2-8)中可以看到，非基變量x1的系數(shù)是正的，說明目標(biāo)函數(shù)值還可以增大，X(1)還不是最優(yōu)解。于是再用上述方法，確定換入、換出變量，繼續(xù)迭代，再得到另一個(gè)基可行解X(2)X(2)=(2,3,0,8,0)T再經(jīng)過一次迭代，再得到一個(gè)基可行解X(3)X(3)=(4,2,0,0,4)T而這時(shí)得到目標(biāo)函數(shù)的表達(dá)式是：z=14-1.5x3-0.125x4(2-9)第四步：迭代再檢查(2-9)式，可見到所有非基變量x3,x4的系數(shù)都是負(fù)數(shù)。這說明若要用剩余資源x3,x4，就必須支付附加費(fèi)用。所以當(dāng)x3=x4=0時(shí)，即不再利用這些資源時(shí)，目標(biāo)函數(shù)達(dá)到最大值。所以X(3)是最優(yōu)解。即當(dāng)產(chǎn)品Ⅰ生產(chǎn)4件，產(chǎn)品Ⅱ生產(chǎn)2件，工廠才能得到最大利潤(rùn)。

第五步：確定最優(yōu)解通過上例，可以了解利用單純形法求解線性規(guī)劃問題的思路?，F(xiàn)將每步迭代得到的結(jié)果與圖解法做一對(duì)比，其幾何意義就很清楚了。原例1的線性規(guī)劃問題是二維的，即兩個(gè)變量x1,x2；當(dāng)加入松弛變量x3,x4,x5后，變換為高維的。這時(shí)可以想象，滿足所有約束條件的可行域是高維空間的凸多面體(凸集)。這凸多面體上的頂點(diǎn)，就是基可行解。初始基可行解X(0)=(0,0,8,16,12)T就相當(dāng)于圖2-2中的原點(diǎn)(0，0)，X(1)=(0,3,2,16,0)T相當(dāng)于對(duì)應(yīng)圖解法中的Q4點(diǎn)(0，3)；X(2)=(2，3，0，8，0)T相當(dāng)于圖解法中的Q3點(diǎn)(2，3)；最優(yōu)解X(3)=(4，2，0，0，4)T相當(dāng)于圖解法中的Q2點(diǎn)(4，2)。從初始基可行解X(0)開始迭代，依次得到X(1)，X(2)，X(3)。這相當(dāng)于圖解法中的目標(biāo)函數(shù)平移時(shí)，從0點(diǎn)開始，首先碰到Q4，然后碰到Q3，最后達(dá)到Q2。下面討論一般線性規(guī)劃問題的求解。

為了便于理解計(jì)算關(guān)系，現(xiàn)設(shè)計(jì)一種計(jì)算表，稱為單純形表。下面用例1的來