第1章線性規(guī)劃及單純形法1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型

第一化工廠每天排放污水2萬(wàn)m3，第二化工廠每天排放污水1.4萬(wàn)m3。污水從工廠1流到工廠2前會(huì)有20%自然凈化。根據(jù)環(huán)保要求，河水中污水的含量應(yīng)不大于0.2%。而工廠1和工廠2處理污水的成本分別為1000元/萬(wàn)m3和800元/萬(wàn)m3。問(wèn)兩工廠各應(yīng)處理多少污水才能使處理污水的總費(fèi)用最低？例1

靠近某河流有兩個(gè)化工廠，流經(jīng)一廠的河流流量為每天500萬(wàn)m3，工廠之間有一條流量為每天200萬(wàn)m3的支流。1.1.1問(wèn)題提出

設(shè)工廠1和工廠2每天分別處理污水x1和x2萬(wàn)m3，則有：Minz=1000x1+800x2(2-x1)/500≤0.002[0.8(2-x1)+1.4-x2]/700≤0.002x1≤2,x2≤1.4x1,x2≥0

設(shè)備產(chǎn)品ABCD利潤(rùn)(元)

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612

例2已知資料如表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12設(shè)：X1——產(chǎn)品Ⅰ產(chǎn)量X2——產(chǎn)品Ⅱ產(chǎn)量建模1.1.1問(wèn)題提出1.用未知自變量(決策變量)表示可變因素，變量的一組數(shù)據(jù)代

表一種解決方案，通常情況下決策變量取非負(fù)值。2．都有一個(gè)要達(dá)到的目標(biāo)，它也是自變量的線性函數(shù)，稱為

目標(biāo)函數(shù)。根據(jù)需要，要求目標(biāo)函數(shù)極大化或極小化。3．存在限制條件，它們可用自變量的線性方程(等式)或線性不

等式來(lái)表示。這些條件稱為約束條件。

以上例子的共同特征：1.1.1問(wèn)題提出maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12設(shè)：X1——產(chǎn)品Ⅰ產(chǎn)量，X2——產(chǎn)品Ⅱ產(chǎn)量線性規(guī)劃數(shù)學(xué)模型三要素1.1.1問(wèn)題提出6其他典型問(wèn)題：合理下料問(wèn)題運(yùn)輸問(wèn)題投資組合問(wèn)題1.1.1問(wèn)題提出1.1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型的表示一般表示方式:

目標(biāo)函數(shù)：約束條件：1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型簡(jiǎn)寫形式1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型的表示向量形式1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型的表示矩陣形式1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型的表示練習(xí)1：某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如表所示，試制訂總利潤(rùn)最大的生產(chǎn)計(jì)劃。1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式maxz=c1x1+c2x2++cnxna11x1+a12x2++a1nxn=b1a21x1+a22x2++a2nxn=b2

am1x1+am2x2++amnxn=bmx1,x2,,xn≥0其中，bi≥0(i=1,2,,m)（一）定義及形式一般形式1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型簡(jiǎn)寫形式矩陣形式（一）定義及形式1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型（二）如何將一般問(wèn)題化為標(biāo)準(zhǔn)型1、目標(biāo)函數(shù)為minz=c1x1+c2x2++cnxn令z=-z,變?yōu)閙axz

=-c1x1-c2x2--cnxn2、約束條件為a11x1+a12x2++a1nxn≤b1加入非負(fù)變量xn+1，稱為松弛變量，有

a11x1+a12x2++a1nxn+xn+1=b11.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式（二）如何將一般問(wèn)題化為標(biāo)準(zhǔn)型令xj=xj-xj

，對(duì)模型中的進(jìn)行變量代換。3、約束條件為a11x1+a12x2++a1nxn≥b1減去非負(fù)變量xn+1，稱為剩余變量，有

a11x1+a12x2++a1nxn-xn+1=b14、變量xj無(wú)約束。1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式（二）如何將一般問(wèn)題化為標(biāo)準(zhǔn)型令xj=xj-xj

，對(duì)模型中的進(jìn)行變量代換。3、約束條件為a11x1+a12x2++a1nxn≥b1減去非負(fù)變量xn+1，稱為剩余變量，有

a11x1+a12x2++a1nxn-xn+1=b14、變量xj無(wú)約束。令xj

=-xj5、變量xj≤01.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式minz=x1+2x2

+3x3

s.t.-2x1+x2+x3≤9-3x1+x2+2x3≥43x1-2x2-3x3=-6x1≤0,x2≥0,x3取值無(wú)約束例3（二）如何將一般問(wèn)題化為標(biāo)準(zhǔn)型1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式解：令得標(biāo)準(zhǔn)形式為：1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式1.1.4線性規(guī)劃問(wèn)題的解19一、線性規(guī)劃問(wèn)題的解求解線性規(guī)劃問(wèn)題：就是從滿足約束方程組和約束不等式的決策變量取值中，找出使得目標(biāo)函數(shù)達(dá)到最大的值。Maxz=CX（1）

s.t.AX=b（2）

X

0（3）（一）解、可行解、最優(yōu)解1.滿足約束條件（2）

的X，稱為線性規(guī)劃

問(wèn)題的解。2.滿足約束條件（2）與（3）的X，稱為線性規(guī)劃的問(wèn)題可行解。3.滿足目標(biāo)函數(shù)（1）的可行解X，稱為線性規(guī)劃的問(wèn)題最優(yōu)解。1.1.4線性規(guī)劃問(wèn)題的解（二）基、基向量、基變量1.設(shè)r(A)=m,并且B是A的m

階非奇異的子矩陣（det(B)

0),則稱矩陣B為線性規(guī)劃問(wèn)題的一個(gè)基。1.1.4線性規(guī)劃問(wèn)題的解（二）基、基向量、基變量1.設(shè)r(A)=m,并且B是A的m

階非奇異的子矩陣（det(B)

0),則稱矩陣B為線性規(guī)劃問(wèn)題的一個(gè)基。1.1.4線性規(guī)劃問(wèn)題的解

maxZ=2x1+3x22x1

+2x2+x3

=12x1

+2x2+x4

=84x1

+

+x5

=164x2

+x6

=12x1

，x2，x3

，x4，x5，x6

02.矩陣B=（P1，P2….Pm)，其列向量Pj稱為對(duì)應(yīng)基B的基向量。3.與基向量Pj相對(duì)應(yīng)的變量xj就稱為基變量，其余的就稱為非基變量。1.1.4線性規(guī)劃問(wèn)題的解

maxZ=2x1+3x2

2x1

+2x2+x3

=12

x1

+2x2+x4

=8

4x1

+

+x5

=16

4x2

+x6

=12x1

，x2，x3

，x4，x5，x6

0(1)可行解：滿足約束條件的解稱為可行解，可行解的集合稱為可行域。(2)最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。(3)基：約束方程組的一個(gè)滿秩子矩陣稱為規(guī)劃問(wèn)題的一個(gè)基，基中的每一個(gè)列向量稱為基向量，與基向量對(duì)應(yīng)的變量稱為基變量，其他變量稱為非基變量。基本概念小結(jié)：1.1.4線性規(guī)劃問(wèn)題的解(4)基解：在約束方程組中，令所有非基變量為0，可以解出基變量的唯一解，這組解與非基變量的0共同構(gòu)成基解。(5)基可行解：滿足變量非負(fù)的基解稱為基可行解(6)可行基：對(duì)應(yīng)于基可行解的基稱為可行基1.1.4線性規(guī)劃問(wèn)題的解1.1.5有關(guān)線性和線性規(guī)劃模型的假設(shè)1比例性目標(biāo)函數(shù)的值同決策變量的取值成嚴(yán)格的比例。2可疊加性決策變量間相互獨(dú)立，決策變量的各自取值對(duì)目標(biāo)函數(shù)

總的取值互不影響。3可分性決策變量允許取小數(shù)、分?jǐn)?shù)或任一實(shí)數(shù)。4確定性線性規(guī)劃模型中的參數(shù)必須是確定的常數(shù)1.2圖解法1、建立直角坐標(biāo)系，將約束條件

表示在圖中。2、確定滿足約束條件的解的范圍。3、繪制目標(biāo)函數(shù)的圖形。4、確定最優(yōu)解。一、圖解法步驟1.2圖解法二、舉例⑴⑵⑶⑷一、圖解法步驟012345678123456⑴⑵⑶⑷作圖∴最優(yōu)解：x1=4，x2=2有唯一最優(yōu)解，Z=14x2

x1(42)⑴⑵⑶⑷

例二、

例三、⑴⑵⑶無(wú)窮多最優(yōu)解⑴⑵無(wú)界解x1x1x2

x2

⑴⑵x1x2

無(wú)可行解例四、1.2圖解法三、LP問(wèn)題可行域和解的情況1、可行域封閉唯一最優(yōu)解2、可行域封閉多個(gè)最優(yōu)解3、可行域開(kāi)放唯一最優(yōu)解4、可行域開(kāi)放多個(gè)最優(yōu)解5、可行域開(kāi)放目標(biāo)函數(shù)無(wú)界6、無(wú)可行解1.2圖解法四、啟示：

圖解法的解題思路和幾何上的直觀結(jié)論對(duì)求解一般的線性規(guī)劃有什么啟示?1、求解LP問(wèn)題時(shí)，解的四種情況2、若LP問(wèn)題的可行域存在，則可行域是凸集。3、若存在最優(yōu)解，則最優(yōu)解一定在可行域的頂點(diǎn)

（邊界）找到4、解題思路：逐個(gè)比較凸集頂點(diǎn)的目標(biāo)函數(shù)值。1.3單純形法原理34凸集：如果集合C中任意兩個(gè)點(diǎn)，其連線上的所有點(diǎn)也都是集合C中的點(diǎn)。集合C為凸集。頂點(diǎn)：如果對(duì)于凸集C中的點(diǎn)X，不存在C中的任意其它兩個(gè)不同的點(diǎn)，使得X在它們的連線上，這時(shí)稱X為凸集的頂點(diǎn)。1.3.1預(yù)備知識(shí)1.3單純形法原理35定理2:

線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)線性規(guī)劃問(wèn)題可行域（凸集）的頂點(diǎn)。定理3:

若線性規(guī)劃問(wèn)題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。定理1:若線性規(guī)劃問(wèn)題存在可行解，則問(wèn)題的可行域是凸集。1.3.2基本定理maxz=2x1+3x2

（1）s.t.-2x1+3x2

6（2-1）

3x1-2x2

6（2-2）

x1+x2

4（2-3）

x1,x2

0

（3）（1）用圖解法求解（2）化為標(biāo)準(zhǔn)形式。（3）找出問(wèn)題的所有基解，

指出哪些是基可行解。已知下列線性規(guī)劃問(wèn)題：練習(xí)（1）：x243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域本問(wèn)題解的情況：基解：點(diǎn)（O，A，B，Q1，Q2，Q3，Q4）可行解：由點(diǎn)（O，Q1，Q2，Q3，Q4）圍成的區(qū)域。基可行解：點(diǎn)（O，Q1，Q2，Q3，Q4）最優(yōu)解：Q3練習(xí)（2）：minz=2x1+3x2s.t.2x1+2x2≤84x1≥12x2≥-16x1≤0,x2

取值無(wú)約束。

將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式：1.3單純形法原理1.3.3單純形法求解思路尋求最優(yōu)解的思路：

設(shè)給定線性規(guī)劃問(wèn)題：（一）確定初始基可行解1.3單純形法原理添加松弛變量得其標(biāo)準(zhǔn)形為：因此約束方程組的系數(shù)矩陣為：（一）確定初始基可行解1.3.3單純形法求解思路1.3單純形法原理由于該矩陣含有一個(gè)單位子矩陣，因此，這個(gè)單位陣就是一組基，就可以求出一個(gè)基可行解：稱其為初始基可行解。（一）確定初始基可行解1.3.3單純形法求解思路1.3單純形法原理⑴⑵⑶⑷例：（一）確定初始基可行解1.3.3單純形法求解思路1.3單純形法原理（二）從初始基可行解轉(zhuǎn)換到另一個(gè)基可行解

思路：對(duì)初始基可行解的系數(shù)矩陣進(jìn)行初等行變換，構(gòu)造出一個(gè)新的單位矩陣，其各列所對(duì)應(yīng)的變量即為一組新的基變量，求出其數(shù)值，就是一個(gè)新的基可行解。1.3.3單純形法求解思路1.3單純形法原理（三）最優(yōu)性檢驗(yàn)和解的判別設(shè)有基可行解比較兩者對(duì)應(yīng)的目標(biāo)函數(shù)值，哪一個(gè)更優(yōu)？1.3.3單純形法求解思路1.3單純形法原理（三）最優(yōu)性檢驗(yàn)和解的判別1.3.3單純形法求解思路1.3單純形法原理46小結(jié)：1、確定初始基可行解2、最優(yōu)性檢驗(yàn)和解的判別3、從初始基可行解轉(zhuǎn)換為另一個(gè)基可行解4、重復(fù)步驟2-3直至得到最優(yōu)解設(shè)給定線性規(guī)劃問(wèn)題：解:標(biāo)準(zhǔn)化：

maxZ=2x1+3x2+0x3+0x4+0x5+0x6

2x1

+2x2+x3

=12

x1

+2x2+x4

=8

4x1

+

+x5

=16

4x2

+x6

=12x1

，x2，x3

，x4，x5，x6

01.4單純形法計(jì)算步驟例

maxZ=2x1+3x22x1+2x2

12

x1+2x2

8

4x1

164x2

12x1

，x2

048(1)找到初始可行基，建立初始單純形表.(2)進(jìn)行最優(yōu)性檢驗(yàn)2024/6/1349入基變量由最大增加原則確定入基變量：(3)從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解

當(dāng)某些非基變量的檢驗(yàn)數(shù)時(shí)，為使目標(biāo)函數(shù)值增加地更快，一般選擇正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的非基變量入基

，成為新的基變量。

50由最小比值原則選擇出基變量；為確保新的基可行解的非零分量非負(fù)，按下述規(guī)則求得最小比值，其所對(duì)應(yīng)的原基變量中的出基。(3)從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解由最大增加原則確定入基變量：(3)從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解由最小比值原則選擇出基變量；入基變量由最大增加原則確定入基變量：出基變量52(3)從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解由最小比值原則選擇出基變量；入基變量由最大增加原則確定入基變量：于是，新的一組基是：出基變量以為主元素進(jìn)行換基迭代：即利用初等行變換將入基變量

所在的系數(shù)列變?yōu)閱挝涣邢蛄浚優(yōu)?。這樣原來(lái)基矩陣中的就不再是單位向量，取而代之的是，這樣就找到了一組新的基。53(3)從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解由最小比值原則選擇出基變量；入基變量由最大增加原則確定入基變量：于是，新的一組基是：出基變量以為主元素進(jìn)行換基迭代：(4)重復(fù)二、三兩步，直至找到最優(yōu)解。54(1)找到初始可行基，建立初始單純形表.561.4單純形法計(jì)算步驟特殊情況：（1）出現(xiàn)兩個(gè)或兩個(gè)以上相同的最大，此時(shí)可任選一個(gè)所對(duì)應(yīng)的變量作為進(jìn)基變量。

（2）利用規(guī)則決定出基變量時(shí)，出現(xiàn)兩個(gè)或兩個(gè)以上的最小比值，則迭代后，會(huì)出現(xiàn)一個(gè)或幾個(gè)基變量等于零的情況，稱此為退化現(xiàn)象。1.4單純形法計(jì)算步驟找出一個(gè)初始可行解是否最優(yōu)轉(zhuǎn)移到另一個(gè)基本可行解最優(yōu)解是否循環(huán)核心是：變量迭代結(jié)束求解步驟1.4單純形法計(jì)算步驟小結(jié)——單純形法的要點(diǎn)（1）化線性規(guī)劃模型為標(biāo)準(zhǔn)型，建立初始單純形表。（2）根據(jù)單純形表按照最大增加原則選擇換入變量；（3）按照最小比值原則選擇換出變量；（4）實(shí)施矩陣的初等變換進(jìn)行換基迭代；（5）建立新的單純形表；（6）重復(fù)上述過(guò)程直到求得最優(yōu)表格為止。2024/6/1359當(dāng)所有時(shí)，現(xiàn)有頂點(diǎn)對(duì)應(yīng)的基可行解即為最優(yōu)解。小結(jié)——解的情況2024/6/13601.當(dāng)所有時(shí)，現(xiàn)有頂點(diǎn)對(duì)應(yīng)的基可行解即為最優(yōu)解。小結(jié)——解的情況2.當(dāng)所有時(shí)，又對(duì)某個(gè)非基變量有則該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。611.當(dāng)所有時(shí)，現(xiàn)有頂點(diǎn)對(duì)應(yīng)的基可行解即為最優(yōu)解。小結(jié)——解的情況2.當(dāng)所有時(shí)，又對(duì)某個(gè)非基變量有則該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。3.如果存在某個(gè)，又向量的所有分量，對(duì)任

意，恒有，則存在無(wú)界解。單純形法與圖解法比較例

maxZ=50x1+30x2

4x1+3x2+x3=120(1)2x1+x2+x4=20(2)x1

，x2

040502530(0，0)(15，20)(1)(2)63用單純形法解題時(shí)，需要有一個(gè)單位陣作為初始基。當(dāng)約束條件都是“≤”時(shí)，加入松弛變量就形成了初始基。§1.5單純形法的進(jìn)一步討論64

maxZ=2x1+3x2+0x3+0x4+0x5+0x6

2x1

+2x2+x3

=12

x1

+2x2+x4

=8

4x1

+

+x5

=16

4x2

+x6

=12x1

，x2，x3

，x4，x5，x6

0解:將模型標(biāo)準(zhǔn)化例3

maxZ=2x1+3x2

2x1+2x2

12x1+2x2

8

4x1

16

4x2

12x1

，x2

065但實(shí)際存在“≥”或“＝”型的約束，沒(méi)有現(xiàn)成的單位矩陣。例maxZ=-3x1+x3

x1+x2+x3

4-2x1+x2

-x3

≥

13x2+x3

=9x1

，x2，x3

0采用人造基的辦法：添加人工變量，構(gòu)造單位矩陣§1.5單純形法的進(jìn)一步討論66

人工單位矩陣的構(gòu)造方法在“

”的不等式約束中減去一個(gè)剩余變量后可變?yōu)榈仁郊s束，但此剩余變量的系數(shù)是（-1），所以再加入一個(gè)人工變量，其系數(shù)是（+1），因而在系數(shù)矩陣中可得到一個(gè)相應(yīng)的單位向量，以便構(gòu)成初始單位陣，即初始基矩陣。在原本就是“

=”的約束中可直接添加一個(gè)人工變量，以便得到初始基矩陣。注意：人工變量是在等式中人為加入的，只有它等于0時(shí)，約束條件才是它本來(lái)的意義。求解帶人工變量的線性規(guī)劃有兩種方法：☆大M法☆兩階段法例解線性規(guī)劃1.5.1

大M法

68添加人工變量，構(gòu)造初始基：69-30100-M-Mx1x2x3x4x5x6x71111000-21-10-1100310001初始單純形表：CCBXBb0x44-Mx61-Mx79-3-2M4M10-M0041330211-10-21-10-11060403-311-10x430x21-Mx76-3+6M01+4M03M-4M070-30100-M-M初始單純形表：C30211-10-21-10-11060403-311-10x430x21-Mx76-3+6M01+4M03M-4M0-30100-M-Mx1x2x3x4x5x6x7CCBXBb00303/2-M-3/2-M+1/2-33/20001-1/21/2-1/2011/30001/3102/301/2-1/21/60x400x23-3x1171-30100-M-Mx1x2x3x4x5x6x7CCBXBb00303/2-M-3/2-M+1/2-33/20001-1/21/2-1/2011/30001/3102/301/2-1/21/60x400x23-3x11-9/2000-3/4-M+3/4-M-1/40x400x25/21x33/20001-1/21/2-1/2-1/2100-1/41/41/43/20103/4-3/41/472此時(shí)人工變量全部出基，并已達(dá)最優(yōu)條件。最優(yōu)解為最優(yōu)值為-9/2000-3/4-M+3/4-M-1/40x400x25/21x33/20001-1/21/2-1/2-1/2100-1/41/41/43/20103/4-3/41/4731.5.2兩階段法

第一階段：構(gòu)造目標(biāo)函數(shù)只含人工變量的線性規(guī)劃問(wèn)題，求解后判斷原線性規(guī)劃問(wèn)題是否有基本可行解，若有，則進(jìn)行第二階段；第二階段：將第一階段的最終單純形表所對(duì)應(yīng)的解，去掉人工變量，作為第二階段的初始單純形表的初始基可行解，進(jìn)行單純形法的迭代。1.5.2兩階段法

(2)第二階段先在第一階段的最終單純形表去掉人工變量，再還原原目標(biāo)函數(shù)，即maxz′=-2x1-3x2+0x3，繼續(xù)迭代：

781.5.3關(guān)于解的判別

一、唯一最優(yōu)解當(dāng)所有時(shí)，該基可行解即為最優(yōu)解。791.5.3關(guān)于解的判別

二、無(wú)窮多最優(yōu)解80二、無(wú)窮多最優(yōu)解1.5.3關(guān)于解的判別

81三、無(wú)界解1.5.3關(guān)于解的判別

82四、無(wú)可行解1.5.3關(guān)于解的判別

1.5.4單純形法小結(jié)：三要素決策變量約束條件目標(biāo)函數(shù)兩個(gè)三個(gè)以上x(chóng)j≥0xj無(wú)約束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa標(biāo)準(zhǔn)化圖解法、單純形法單純形法不處理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj′=-xj不處理約束條件兩端同乘以-1加松弛變量xs加人工變量xa減去xs加入xa不處理令z′=-Z

0-M個(gè)數(shù)取值限制右端常數(shù)約束方向要求系數(shù)A,b,C停止1,3/2§1.6

改進(jìn)單純形法——矩陣描述一、矩陣形式的單純形法若記：線性規(guī)劃模型為：

maxz=CXAX=bX≥0基變量：XB非基變量：XN

基矩陣：B

非基矩陣：N基變量的價(jià)值系數(shù)：CB非基變量的價(jià)值系數(shù)：CN則有：maxz=CBXB+CNXNBXB+NXN=b①XB,XN

≥0為求XB，用B-1左乘①式兩端，有：B-1BXB+B-1NXN=B-1b從而有：XB=B-1b?

B-1NXN令非基變量XN=0，則有：1）基變量：XB=B-1b3）目標(biāo)函數(shù)值：z=CBXB=CBB-1b2）檢驗(yàn)數(shù)：σN=CN?CBB-1N=CB(B-1b?B-1NXN)+CNXN

z=CBXB+CNXN=CBB-1b+(CN?CBB-1N)XN4）非基矩陣:B-1N將XB=B-1b?

B-1NXN代入目標(biāo)函數(shù)：

運(yùn)籌學(xué)的研究步驟ax提出問(wèn)題建模求解解的檢驗(yàn)及控制決策實(shí)施例1.7應(yīng)用舉例

設(shè)備產(chǎn)品ABCD利潤(rùn)(元)

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612已知資料如表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？1.7應(yīng)用舉例問(wèn)題可以歸結(jié)為線性規(guī)劃模型的條件（1）問(wèn)題目標(biāo)能用效益指標(biāo)度量（2）為達(dá)到目標(biāo)有多種方案（3）目標(biāo)要在一定約束條件下實(shí)現(xiàn)，條件可用線性

等式或不等式描述

設(shè)備產(chǎn)品ABCD利潤(rùn)(元)

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612已知資料如表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12設(shè)：X1——產(chǎn)品Ⅰ產(chǎn)量X2——產(chǎn)品Ⅱ產(chǎn)量建模1.7應(yīng)用舉例1.7應(yīng)用舉例

例11工業(yè)原材料的合理利用解：先看有多少種裁料方案，再進(jìn)行組合和選擇。ⅠⅡⅢⅣⅤⅥ3m4m5m201120210002011300總長(zhǎng)/m1111101099料頭/m001122某大樓改造工程用11m長(zhǎng)角鋼切割成鋼窗用料。每扇窗含3m長(zhǎng)2根、4m長(zhǎng)3根，5m長(zhǎng)2根，若需鋼窗100扇，至少需要多少根角鋼原材料？1.7應(yīng)用舉例