第一章線性規(guī)劃

第1章線性規(guī)劃制作：數(shù)理學(xué)院趙建強(qiáng)

§1.4初始基本可行解的確定

4§1.1線性規(guī)劃問題及其數(shù)學(xué)模型

1§1.2線性規(guī)劃問題的解

2§1.3單純形法

3本章的教學(xué)目的和要求：

1、掌握線性規(guī)劃數(shù)學(xué)模型的基本特征和標(biāo)準(zhǔn)形式，以及線性規(guī)劃問題數(shù)學(xué)模型的建立方法，學(xué)會(huì)用圖解法求解簡(jiǎn)單的線性規(guī)劃問題。2、理解線性規(guī)劃問題的解的概念，了解線性規(guī)劃的基本理論。3、了解單純形表的構(gòu)成，熟練掌握運(yùn)用單純形法求解線性規(guī)劃問題。4、掌握人工變量法（包括大Ｍ法和兩階段法）的計(jì)算步驟。5、本章將安排4學(xué)時(shí)的上機(jī)實(shí)驗(yàn)，練習(xí)如何建立線性規(guī)劃模型解決相關(guān)的實(shí)際問題，并會(huì)用相關(guān)的數(shù)學(xué)軟件求解該線性規(guī)劃模型。教學(xué)重點(diǎn)：線性規(guī)劃的標(biāo)準(zhǔn)形式、圖解法、單純形法。教學(xué)難點(diǎn)：?jiǎn)渭冃畏?、人工變量法?！?.1線性規(guī)劃問題及其數(shù)學(xué)模型教學(xué)目的和要求：使學(xué)生了解常見的幾種線性規(guī)劃實(shí)例；掌握線性規(guī)劃的一般形式、標(biāo)準(zhǔn)形式、向量形式、矩陣形式等；會(huì)將線性規(guī)劃的一般形式標(biāo)準(zhǔn)化。教學(xué)重點(diǎn)：線性規(guī)劃的一般形式、標(biāo)準(zhǔn)形式；線性規(guī)劃的標(biāo)準(zhǔn)化。教學(xué)難點(diǎn)：線性規(guī)劃的標(biāo)準(zhǔn)化。教學(xué)過程：

在經(jīng)濟(jì)活動(dòng)及工程技術(shù)中會(huì)遇到各種各樣的實(shí)際問題，描述實(shí)際問題共性的抽象的數(shù)學(xué)形式稱為該問題的數(shù)學(xué)模型．通常建立線性規(guī)劃問題數(shù)學(xué)模型要遵循以下步驟：(1)明確問題中有待確定的未知量(稱為決策變量)，并用數(shù)學(xué)符號(hào)表示；(2)明確問題中所有的限制條件(稱為約束條件)，并用決策變量的一組線性方程或線性不等式表示；(3)明確問題的目標(biāo)，并用決策變量的一個(gè)線性函數(shù)(稱為目標(biāo)函數(shù))表示，按問題的不同取最大值或最小值．1.1.1線性規(guī)劃問題的幾個(gè)實(shí)例下面結(jié)合幾個(gè)實(shí)際例子來介紹線性規(guī)劃問題的特點(diǎn)，并按上面給出的三個(gè)步驟來建立它們的數(shù)學(xué)模型.例1.1-1生產(chǎn)計(jì)劃問題假設(shè)某廠計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品都要分別在A，B，C三種不同設(shè)備上加工．按工藝資料規(guī)定：生產(chǎn)每件甲產(chǎn)品需占用設(shè)備的小時(shí)數(shù)分別為2，l，4；生產(chǎn)每件乙產(chǎn)品需占用設(shè)備的小時(shí)數(shù)分別為2，2，0.已知各設(shè)備計(jì)劃期內(nèi)用于生產(chǎn)這兩種產(chǎn)品的能力(小時(shí)數(shù))分別為12，8，16；又知每生產(chǎn)一件甲產(chǎn)品，該廠會(huì)獲得利潤(rùn)2元，每生產(chǎn)一件乙產(chǎn)品，該廠能獲利潤(rùn)3元，問該廠應(yīng)安排生產(chǎn)兩種產(chǎn)品各多少件才能使總的利潤(rùn)收入為最大?解(1)明確決策變量工廠需要確定的是甲、乙兩種產(chǎn)品的計(jì)劃生產(chǎn)量，設(shè)x1,x2分別為甲、乙兩種產(chǎn)品的計(jì)劃生產(chǎn)量，總的利潤(rùn)為z．

(2)明確約束條件因設(shè)備A在計(jì)劃期內(nèi)有效時(shí)間為12小時(shí)，不允許超過．故有對(duì)設(shè)備B，C也可列出類似的不等式此外產(chǎn)品的產(chǎn)量

只能取非負(fù)值，即

≥0≥0這種限制稱為變量的非負(fù)約束條件．(3)明確目標(biāo)工廠的目標(biāo)是在各種設(shè)備能力允許的條件下，使總利潤(rùn)收入

為最大．

綜合起來，該問題的數(shù)學(xué)模型為：求一組變量

的值在滿足約束條件

的情況下，

為最大．

使利潤(rùn)例1.1-2運(yùn)輸問題設(shè)有三個(gè)地方

生產(chǎn)某種物資

簡(jiǎn)稱為產(chǎn)地)

(四個(gè)地方

需要該種物資

（簡(jiǎn)稱為銷地)

產(chǎn)地的產(chǎn)量和銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)表見表1.1—1，問如何組織物資的運(yùn)輸，才能在滿足供需的條件下使總的運(yùn)費(fèi)最少．表1.1—1產(chǎn)銷運(yùn)輸表例1.1-3合理下料問題某工廠生產(chǎn)某一種型號(hào)的機(jī)床，每臺(tái)機(jī)床上需要2.9m，2.1m,1.5m的軸分別為一根、二根、一根，這些軸需用同一種圓鋼制作，圓鋼的長(zhǎng)度為7.4m，如果要生產(chǎn)100臺(tái)機(jī)床，問應(yīng)如何安排下料，才能使用料最省?1.1.2線性規(guī)劃問題的數(shù)學(xué)模型一、線性規(guī)劃模型的一般形式上述各例具有下列共同特征：

1、存在一組變量

，稱為決策變量，通常要求這些變量的取值是非負(fù)的．2、存在若干個(gè)約束條件，可以用一組線性等式或線性不等式來描述．

3、存在一個(gè)目標(biāo)函數(shù)，它是決策變量的線性函數(shù)，按實(shí)際問題求最大值或最小值．

根據(jù)以上特征，可以將線性規(guī)劃問題抽象為一般的數(shù)學(xué)表達(dá)式，

即線性規(guī)劃問題數(shù)學(xué)模型（簡(jiǎn)稱線性規(guī)劃模型）的一般形式為：

式中max表示求最大值，min表示求最小值，

是由實(shí)際問題所確定的常數(shù).

為利潤(rùn)系數(shù)或成本系數(shù)；

稱為限定系數(shù)或常數(shù)項(xiàng)；

稱為結(jié)構(gòu)系數(shù)或消耗系數(shù)；

為決策變量；每一個(gè)約束條件只有

一種符號(hào)

．

二、線性規(guī)劃模型的標(biāo)準(zhǔn)形式線性規(guī)劃模型的具體形式是多種多樣的．為了討論和計(jì)算方便，

我們要在這眾多的形式中規(guī)定一種形式，將其稱為

線性規(guī)劃模型的標(biāo)準(zhǔn)形式．

通常線性規(guī)劃模型的標(biāo)準(zhǔn)形式為

上述形式的特點(diǎn)是：

線性規(guī)劃模型的標(biāo)準(zhǔn)形式可以寫成簡(jiǎn)縮形式：

線性規(guī)劃模型的標(biāo)準(zhǔn)形式有時(shí)用矩陣或向量描述往往更為方便．

用向量表示線性規(guī)劃模型的標(biāo)準(zhǔn)形式為其中

向量

是變量

對(duì)應(yīng)的約束條件中的系數(shù)列向量.

用矩陣表示線性規(guī)劃的標(biāo)準(zhǔn)形式為

其中其它同前．我們稱A為約束方程的系數(shù)矩陣（m×n），

一般m<n，m、n為正整數(shù)．

三、線性規(guī)劃模型的標(biāo)準(zhǔn)化我們對(duì)線性規(guī)劃問題的研究是基于標(biāo)準(zhǔn)形式進(jìn)行的，因此對(duì)于給定的非標(biāo)準(zhǔn)形式線性規(guī)劃問題的數(shù)學(xué)模型，則需要將其化為標(biāo)準(zhǔn)形式．一般地，對(duì)于不同形式的線性規(guī)劃模型，可以采用以下一些方法將其化為標(biāo)準(zhǔn)形式．對(duì)于目標(biāo)函數(shù)是求最小值的線性規(guī)劃問題，只要將目標(biāo)函數(shù)的系數(shù)反號(hào)，即可化為等價(jià)的最大值問題．2．約束條件為“≤”（“≥”）類型的線性規(guī)劃問題，

可在不等式左邊加上（或減去）一個(gè)非負(fù)的新變量，

即可化為等式．這個(gè)新增的非負(fù)變量稱為松弛變量（或剩余變量），也可統(tǒng)稱為松弛變量．在目標(biāo)函數(shù)中一般認(rèn)為新增的松弛變量的系數(shù)為零．3．如果在一個(gè)線性規(guī)劃問題中，決策變量

的符號(hào)沒有限制，我們可用兩個(gè)非負(fù)的新變量和

之差來代替，即將變量

寫成

且有

通常將這樣的

稱為自由變量．如果Xk<=0,則令Xk/=-Xk

4．當(dāng)常數(shù)項(xiàng)

為負(fù)值時(shí)，可在該約束條件的兩邊

分別乘以-1．

例1.1-4將下列線性規(guī)劃模型化成標(biāo)準(zhǔn)形式解通過以下四個(gè)步驟：（1）目標(biāo)函數(shù)兩邊乘上-1化為求最大值；（2）以

代入目標(biāo)函數(shù)和所有的約束條件中，

其中

（3）在第一個(gè)約束條件的左邊加上松弛變量

（4）在第二個(gè)約束條件的左邊減去剩余變量

于是得到該線性規(guī)劃模型的標(biāo)準(zhǔn)形式：練習(xí)：化標(biāo)準(zhǔn)型p361.3(4),(5),1.9(3)作業(yè)：p341.1（1）（4）（5）、1.2§1.2線性規(guī)劃問題的解教學(xué)目的和要求：掌握線性規(guī)劃問題的基本概念；掌握線性規(guī)劃圖解法；了解線性規(guī)劃問題的解的特殊情況；掌握線性規(guī)劃解的基本性質(zhì)。教學(xué)重點(diǎn)：線性規(guī)劃問題的基本概念、基本性質(zhì)、圖解法。教學(xué)難點(diǎn)：線性規(guī)劃的基本性質(zhì)。教學(xué)過程：1.２.１線性規(guī)劃問題的基本概念設(shè)有線性規(guī)劃問題

一、可行解滿足線性規(guī)劃約束條件（1.2-2）和(1.2-3)的解

稱為線性規(guī)劃問題的可行解．

所有可行解的集合稱為可行域或可行解集．二、最優(yōu)解使線性規(guī)劃的目標(biāo)函數(shù)（1.2-1）式達(dá)到最大的可行解稱為線性規(guī)劃的最優(yōu)解．

三、基本解設(shè)A是約束方程組(1.2-2)的（m×n）階的系數(shù)矩陣（m<n）,其秩為m，則A中任意m個(gè)線性無關(guān)的列向量構(gòu)成的m×m階子矩陣

稱為線性規(guī)劃的一個(gè)基矩陣或簡(jiǎn)稱為一個(gè)基，記為B．顯然，

B為非奇異矩陣，即|B|≠0．

基矩陣的m個(gè)列向量稱為基向量，其余n-m個(gè)向量稱為非基向量；與m個(gè)基向量相對(duì)應(yīng)的m個(gè)變量稱為基變量，其余的n-m個(gè)變量則稱為非基變量．顯然，基變量隨著基的變化而變化，當(dāng)基被確定以后，基變量和非基變量也隨之確定了．

若令約束方程組(1.2-2)中的n-m個(gè)非基變量為零，再對(duì)余下的m個(gè)基變量求解，所得到的約束方程組的解稱為基本解．基本解的個(gè)數(shù)總是小于

等于

的．

如設(shè)

為線性規(guī)劃的一個(gè)基，于是

為基變量，

就為非基變量．

現(xiàn)令非基變量

，方程組(1.2-2)就變?yōu)榇藭r(shí)方程組有m個(gè)方程，m個(gè)未知數(shù)，

可唯一地解出

則向量就是對(duì)應(yīng)于基B的基本解．

四、基本可行解

滿足非負(fù)條件（1.2-3）的基本解稱為基本可行解；對(duì)應(yīng)于基本可行解的基稱為可行基．

顯然，基本可行解既是基本解，又是可行解．一般，基本可行解的數(shù)目要少于基本解的數(shù)目，最多兩者相等．當(dāng)基本可行解的非零分量個(gè)數(shù)恰為m時(shí)，稱此解是非退化的解；如果有的基變量也取零值，即基本可行解的非零分量個(gè)數(shù)小于m時(shí)，稱此解是退化解．例1.2-1求下列線性規(guī)劃問題的所有基本解，并指出哪些是基本可行解．解將已知模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣

則易知均為線性規(guī)劃問題的基矩陣．對(duì)應(yīng)基

，基變量為

，非基變量為

．令

得

.從而

為線性規(guī)劃問題的一個(gè)基本解．

因

均大于零，故

為線性規(guī)劃問題的一個(gè)基本可行解．

對(duì)應(yīng)于其他基

的基本解列表見表1.2-1．

表1.2-1對(duì)應(yīng)于其他基的基本解

2.線性規(guī)劃的圖解法線性規(guī)劃的圖解法(解的幾何表示)：對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問題，可以二維直角坐標(biāo)平面上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。圖解法求解線性規(guī)劃問題的步驟如下：2.線性規(guī)劃的圖解法(1)建立直角坐標(biāo)系：分別取決策變量x1,x2

為坐標(biāo)向量。

2.線性規(guī)劃的圖解法（2）繪制可行域：對(duì)每個(gè)約束（包括非負(fù)約束）條件，作出其約束半平面（不等式）或約束直線（等式）。各半平面與直線交出來的區(qū)域若存在，其中的點(diǎn)為此線性規(guī)劃的可行解。稱這個(gè)區(qū)域?yàn)榭尚屑蚩尚杏?。然后進(jìn)行下步。否則若交為空，那么該線性規(guī)劃問題無可行解。

2.線性規(guī)劃的圖解法

（3）繪制目標(biāo)函數(shù)等值線，并移動(dòng)求解：目標(biāo)函數(shù)隨著取值不同，為一族相互平行的直線。首先，任意給定目標(biāo)函數(shù)一個(gè)值，可作出一條目標(biāo)函數(shù)的等值線（直線）；然后，確定該直線平移使函數(shù)值增加的方向；最后，依照目標(biāo)的要求平移此直線。2.線性規(guī)劃的圖解法結(jié)果若目標(biāo)函數(shù)等值線能夠移動(dòng)到既與可行域有交點(diǎn)又達(dá)到最優(yōu)的位置，此目標(biāo)函數(shù)等值線與可行域的交點(diǎn)即最優(yōu)解（一個(gè)或多個(gè)），此目標(biāo)函數(shù)的值即最優(yōu)值。否則，目標(biāo)函數(shù)等值線與可行域?qū)⒔挥跓o窮遠(yuǎn)處，此時(shí)稱無有限最優(yōu)解。

2.線性規(guī)劃的圖解法

Max

z=1500x1

+2500x2

s.t.3x1+2x2

≤65(A)

2x1+x2

≤40(B)

3x2

≤75(C)

x1,x2

≥0(D,E)2.線性規(guī)劃的圖解法例題作圖（1）按照?qǐng)D解法的步驟：（1）以決策變量x1

，x2

為坐標(biāo)向量作平面直角坐標(biāo)系；

2.線性規(guī)劃的圖解法（2）對(duì)每個(gè)約束（包括非負(fù)約束）條件作出直線（A、B、C、D、E），并通過判斷確定不等式所決定的半平面。各約束半平面交出來的區(qū)域即可行集或可行域如下圖陰影所示。

2.線性規(guī)劃的圖解法例題作圖（2）第2步圖示(1)分別作出各約束半平面X2≥0x1

≥03x2

≤753x1+2x2

≤65

2x1+x2

≤40

2.線性規(guī)劃的圖解法例題作圖（3）第2步圖示(2)各約束半平面的交－可行域2.線性規(guī)劃的圖解法（3）任意給定目標(biāo)函數(shù)一個(gè)值（例如37500）作一條目標(biāo)函數(shù)的等值線，并確定該等值線平移后值增加的方向（向上移動(dòng)函數(shù)值增大），平移此目標(biāo)函數(shù)的等值線，使其達(dá)到既與可行域有交點(diǎn)又不可能使值再增加的位置，得到交點(diǎn)(5,25)T，即最優(yōu)解。此目標(biāo)函數(shù)的值為70000。2.線性規(guī)劃的圖解法例題作圖（4）第3步圖示作出目標(biāo)函數(shù)等值線函數(shù)值增大2.線性規(guī)劃的圖解法例題作圖（5）第3步圖示(2)求出最優(yōu)解1

2.線性規(guī)劃的圖解法根據(jù)上面的過程我們得到這個(gè)線性規(guī)劃的最優(yōu)解x1=5、x2=25，最優(yōu)值z(mì)=70000即最優(yōu)方案為生產(chǎn)甲產(chǎn)品5件、乙產(chǎn)品25件，可獲得最大利潤(rùn)為70000元。2.線性規(guī)劃的圖解法線性規(guī)劃的解有如下幾種情況：

1、存在有限最優(yōu)解：惟一最優(yōu)解；無窮多個(gè)最優(yōu)解

2、無有限最優(yōu)解（無界解）

3、無可行解（可行域空）

2.線性規(guī)劃的圖解法例2.5：在例2.4的線性規(guī)劃模型中，如果目標(biāo)函數(shù)變?yōu)椋?/p>

Maxz=1500x1

+1000x2

那么，最優(yōu)情況下目標(biāo)函數(shù)的等值線與直線（A）重合。這時(shí)，最優(yōu)解有無窮多個(gè)，是從點(diǎn)(5,25)T到點(diǎn)(15,10)T線段上的所有點(diǎn)，最優(yōu)值為32500。如下圖所示：

2.線性規(guī)劃的圖解法

無窮多解的情況(15,10)T

2.線性規(guī)劃的圖解法

例2.6：在例2.4的線性規(guī)劃模型中,如果約束條件（A）、（C）變?yōu)椋?/p>

3x1

+2x2

≥65(A’）

3x2

≥75(C’）并且去掉（D、E）的非負(fù)限制。那么，可行域成為一個(gè)上無界的區(qū)域。這時(shí)，沒有有限最優(yōu)解，如下圖所示：

2.線性規(guī)劃的圖解法

無有限解的情況

2、線性規(guī)劃的圖解法例2.7：在例2.4的線性規(guī)劃模型中，如果增加約束條件（F）為：

x1

+x2≥40

（F）那么，可行域成為空的區(qū)域。這時(shí)，沒有可行解，顯然線性規(guī)劃問題無解。如下圖所示：

2.線性規(guī)劃的圖解法

無可行解的情況

根據(jù)以上例題，進(jìn)一步分析討論可知線性規(guī)劃的可行域和最優(yōu)解有以下幾種可能的情況

1.可行域?yàn)榉忾]的有界區(qū)域

(a)有唯一的最優(yōu)解；

(b)有無窮多個(gè)最優(yōu)解；

2.可行域?yàn)榉忾]的無界區(qū)域

(c)有唯一的最優(yōu)解；

2.線性規(guī)劃的圖解法

(d)有無窮多個(gè)最優(yōu)解；

(e)目標(biāo)函數(shù)無界(即雖有可行解，但在可行域中，目標(biāo)函數(shù)可以無限增大或無限減少)，因而沒有有限最優(yōu)解。

3.可行域?yàn)榭占?/p>

(f)沒有可行解，原問題無最優(yōu)解

2.線性規(guī)劃的圖解法圖1.2—5無界解圖1.2—6無可行解可行域解空集有界集無界集無可行解唯一最優(yōu)解無窮多最優(yōu)解無界解.2.4線性規(guī)劃問題解的基本性質(zhì)

根據(jù)線性規(guī)劃解的基本概念，并從圖解法中直觀地看到線性規(guī)劃

問題的解具有以下一些基本性質(zhì)．（有關(guān)性質(zhì)的證明略）

定理1線性規(guī)劃的可行解集是一個(gè)凸集．

凸集的幾何意義是：若以集合中任意兩點(diǎn)為端點(diǎn)的線段仍在該集合中，則稱該集合為凸集．

定理2若一個(gè)線性規(guī)劃有可行解，則它必有基本可行解．

定理3設(shè)線性規(guī)劃的可行解集為D，則D的頂點(diǎn)（極點(diǎn)）就是線性規(guī)劃的基本可行解．

定理4若線性規(guī)劃問題有最優(yōu)解，則一定存在一個(gè)基本可行解

是它的最優(yōu)解．即：最優(yōu)解一定可以在D的頂點(diǎn)（極點(diǎn)）上達(dá)到．

定理5若線性規(guī)劃存在兩個(gè)相異的基本可行解

和

為最優(yōu)解，則以

線段上的一切點(diǎn)

為端點(diǎn)的也都是線性規(guī)劃的最優(yōu)解．

上述性質(zhì)告訴我們，求解線性規(guī)劃問題，只需在基本可行解（凸多邊形的頂點(diǎn)）中尋找就行了．由于凸多邊形的頂點(diǎn)是有限的，因而基可行解的個(gè)數(shù)也是有限的，這就保證了線性規(guī)劃若有最優(yōu)解，一定可以在有限步內(nèi)得到最優(yōu)解．作業(yè)：1.4線性規(guī)劃模型

作如表1.3－1形式的表格稱為單純形表．§1.3單純形法

單純形法是求解線性規(guī)劃問題的常用算法，它是1947年由丹塞格(Geofe·Dantzig)提出的．下面通過典式介紹其求解原理表1.3－1下面我們討論單純形表與線性規(guī)劃模型間的對(duì)應(yīng)關(guān)系。對(duì)于線性規(guī)劃模型若將其系數(shù)矩陣A用分塊矩陣來表示，即為研究方便起見，不妨設(shè)為一個(gè)基，再令則有相應(yīng)地可有即以

和

分別表示基變量和非基變量．

同樣有

其中

為目標(biāo)函數(shù)中基變量的系數(shù)，

為非基變量的系數(shù)，

于是對(duì)約束條件有設(shè)B為基，即B的行列式不等于零，則

B-1存在，故由

可得到

（1.3-11）

（1.3-12）即

同樣對(duì)目標(biāo)數(shù)有將（1.3-12）式代入上式，得（1.3-13）

顯然，若令非基變量

XN=0，由（1.3-12）式得

如果使

，便可得到一個(gè)基本可行解：當(dāng)B=I（單位矩陣）時(shí)，則有我們把由（1.3-11）和(1.3-13)式結(jié)合成(1.3-14),(1.3-15),(1.3-16)式稱為線性規(guī)劃對(duì)應(yīng)于基的典式．表1.3-1的單純形表排列的就是典式的一系列數(shù)據(jù)，實(shí)際上它是把約束條件中的基變量用非基變量表示，同時(shí)把目標(biāo)函數(shù)中基變量也用非基變量來表示，所形成的一種利于在表格上運(yùn)算的一種形式．

為目標(biāo)函數(shù)中非基變量的系數(shù)向量，其中第

個(gè)分量

為非基變量

這就是檢驗(yàn)數(shù)即：

如果初始基矩陣B=I，則基變量的值為右端項(xiàng)

而由（1.3-14）式得

同時(shí)可以看出

的系數(shù)．回顧典式：對(duì)于線性規(guī)劃模型對(duì)于選定的基1.3-10兩端乘以B-1將它化為典式下面以例1.3-1，結(jié)合典式與定理六，介紹單純形法求解過程．例1.3-1求解例1.1-1所示的線性規(guī)劃問題．解：

引進(jìn)松弛變量

將例1.1-1的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式

則(1.3-2)的系數(shù)矩陣

(1.3-1)(1.3-2)首先，我們找出一個(gè)初始基本可行解，在

中

是線性無關(guān)的，故

為(1.3－2)的一個(gè)基，對(duì)應(yīng)的基變量為

,非基變量為

若令

，可得

．顯然，

可作為本問題的一個(gè)初始基本可行解．

可作為本問題的一個(gè)初始基本可行解．

討論求解初始基本可行解的一般方法．）

（我們將在本章1.4中當(dāng)前基本可行解的實(shí)際意義是不生產(chǎn)任何產(chǎn)品，目標(biāo)函數(shù)（利潤(rùn)）為0，即

必須尋找新的基本可行解，

這肯定不是最優(yōu)解．下一步我們且使目標(biāo)函數(shù)值增加．

由目標(biāo)函數(shù)(1.3-1)式可看出，由于

前面的系數(shù)均為正數(shù)，所以當(dāng)

由現(xiàn)在的非基變量（即取0值）變?yōu)榛兞?/p>

（取非零值），可使目標(biāo)函數(shù)值增加．又因?yàn)?/p>

的系數(shù)比

的系數(shù)大（利潤(rùn)增加快），故選

作為新的基本可行解中

的基變量，稱其為進(jìn)基變量．

為保證基變量個(gè)數(shù)不變（等于系數(shù)矩陣A的秩m），還需要

確定原來的基變量

哪一個(gè)被換出來作為非基變量

（稱為出基變量）．為此，我們進(jìn)行下面的分析．由約束方程

(1.3-2)的前三式可得當(dāng)

進(jìn)基以后，令

，而

仍為非基變量，即

．同時(shí)還必須保證所有的變量滿足非負(fù)約束條件

（1.3-3）（即(2.3-2)式的最后一式成立），于是有或?qū)憺樯a(chǎn)產(chǎn)品乙必須同時(shí)兼顧三種設(shè)備臺(tái)時(shí)，因此產(chǎn)品乙最多不得超過4件，否則，第二種設(shè)備臺(tái)時(shí)就不夠用了．但由式(1.3-4)可得這說明生產(chǎn)4件乙產(chǎn)品,A設(shè)備臺(tái)時(shí)還剩4，而B設(shè)備能力已用盡．

因此出基變量的選擇原則應(yīng)該是由最薄弱的資源來決定．即選取

（1.3-5）

正好體現(xiàn)了兼顧各種限制條件的思想，又稱最小比值法則．

為了簡(jiǎn)便地得到一個(gè)新的基本可行解，可以通過對(duì)約束方程組

(1.3-2)的前三式進(jìn)行變換，即將(1.3-2)式的第二式

,第一、三式

x2的系數(shù)變成1x2的系數(shù)變成都是0．于是我們得到方程組其變換過程為用

乘(1.3-2)式的第二式得(1.3-7)式；

用-1乘(1.3-2)式的第二式加到第一式得(1.3-6)式；

若非基變量

等于零，基變量

值就可以從右邊常數(shù)項(xiàng)直接得到．

所以得新的基本可得解

相應(yīng)地我們把目標(biāo)函數(shù)用非基變量表示成

(1.3-8)而當(dāng)

時(shí)，

．顯然

上述結(jié)果表明，生產(chǎn)產(chǎn)品乙4件，可獲得利潤(rùn)12元．

從（1.3-8）式可見，非基變量

x1的系數(shù)仍是正數(shù)，這說明

x1進(jìn)基，仍可使目標(biāo)函數(shù)值增大，即

不是最優(yōu)解．重復(fù)上述步驟，

確定進(jìn)基變量（

）和出基變量（

），經(jīng)過迭代

得到另一個(gè)基本可行解

表示，（1.3-8）式變成而目標(biāo)函數(shù)用非基變量（1.3-9）

由于目標(biāo)函數(shù)(1.3-9)的非基變量的系數(shù)均小于零，即當(dāng)

增加時(shí)，目標(biāo)函數(shù)只會(huì)減少，因此，

就是最優(yōu)解．

此結(jié)果表明，工廠應(yīng)生產(chǎn)產(chǎn)品甲4件，產(chǎn)品乙2件，可獲得

最大利潤(rùn)14元．從上述代數(shù)解法可以看到，求最優(yōu)解的過程

是一種迭代選優(yōu)的過程，即從一個(gè)基本可行解到另一個(gè)基本可行解，且使目標(biāo)函數(shù)值一次比一次好，在幾何上，則是從可行域的一個(gè)頂點(diǎn)迭代到

另一個(gè)頂點(diǎn)．

1.３.２線性規(guī)劃的典式和單純形表單純形法就是將上述的代數(shù)解法表格化，即將運(yùn)算過程中

相關(guān)數(shù)據(jù)之間的關(guān)系完全在表格上反映出來．723.單純形法計(jì)算流程初始基本可行解是否最優(yōu)解或無限最優(yōu)解?結(jié)束沿邊界找新的基本可行解NY73單純形法的基本步驟可描述如下：

（1）尋找一個(gè)初始的可行基和相應(yīng)基本可行解（極點(diǎn)），確定基變量、非基變量以及基變量、非基變量（全部等于0）和目標(biāo)函數(shù)的值，并將目標(biāo)函數(shù)和基變量分別用非基變量表示；

3.單純形法74

（2）在用非基變量表示的目標(biāo)函數(shù)表達(dá)式（2-12）中，我們稱非基變量xj的系數(shù)（或其負(fù)值）為檢驗(yàn)數(shù)記為j

。若j>0，那么相應(yīng)的非基變量xj，它的值從當(dāng)前值0開始增加時(shí)，目標(biāo)函數(shù)值隨之增加。這個(gè)選定的非基變量xj稱為“進(jìn)基變量”，轉(zhuǎn)（3）。如果任何一個(gè)非基變量的值增加都不能使目標(biāo)函數(shù)值增加，即所有j

非正，則當(dāng)前的基本可行解就是最優(yōu)解，計(jì)算結(jié)束；3.單純形法75

（3）在用非基變量表示的基變量的表達(dá)式（2-11）中，觀察進(jìn)基變量增加時(shí)各基變量變化情況，確定基變量的值在進(jìn)基變量增加過程中首先減少到0的變量xr

，滿足，=minb’i/a’ij

a’ij>0=b’r

/a’rj這個(gè)基變量xr稱為“出基變量”。當(dāng)進(jìn)基變量的值增加到

時(shí)，出基變量xr的值降為0時(shí)，可行解就移動(dòng)到了相鄰的基本可行解（極點(diǎn)），轉(zhuǎn)（4）。3.單純形法76如果進(jìn)基變量的值增加時(shí)，所有基變量的值都不減少，即所有a’ij

非正，則表示可行域是不封閉的，且目標(biāo)函數(shù)值隨進(jìn)基變量的增加可以無限增加，此時(shí)，不存在有限最優(yōu)解，計(jì)算結(jié)束；（4）將進(jìn)基變量作為新的基變量，出基變量作為新的非基變量，確定新的基、新的基本可行解和新的目標(biāo)函數(shù)值。在新的基變量、非基變量的基礎(chǔ)上重復(fù)（1）。3.單純形法3、單純形法例2.10Maxz=1500x1+2500x2

s.t.3x1+2x2≤652x1+x2≤403x2≤75

x1,x2≥0

化標(biāo)準(zhǔn)形式：

Maxz=1500x1+2500x2

s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x5

0單純形法過程(1)152001-1/3153010-2/32500x22501001/3-62500

1500000-2500/3

單純形法過程(2)-700000

0-5000-500

2501001/3500-2/311/91500x15101/30-2/93、單純形法單純形表81注意：?jiǎn)渭冃畏ㄖ校?/p>

1.每一步運(yùn)算只能用矩陣初等行變換；

2.表中第3列的數(shù)總應(yīng)保持非負(fù)（≥0）；

3.當(dāng)所有檢驗(yàn)數(shù)均非正（≤0）時(shí)，得到最優(yōu)單純形表。3.線性規(guī)劃

多解情況

線性規(guī)劃問題可能存在無窮多解的情況，這時(shí)，利用單純形表亦可求出。例

Max

z=x1+5x2

+4x3

-x5

-2x6

s.t.

x1+2x2

+3x3

+x5

=152x1

+x2

+5x3

+x6=20

x1

+2x2+4x3

+x4

=26

x1,x2,x3,x4,x5,x6

≥0用單純形法求解得到解為

x’＝(0,15/7,25/7,52/7,0,0)T由于x1的檢驗(yàn)數(shù)為零，可繼續(xù)迭代，繼續(xù)求解另一解為x”＝(25/3,0,0,11,10/3,0)T于是x’，x”線段上的任一點(diǎn)均為最優(yōu)解。此線性規(guī)劃的最優(yōu)解可表示為：

x=

x’+(1-)x”，其中[01]無有限最優(yōu)解的情況

線性規(guī)劃問題可能存在無有限最優(yōu)解（目標(biāo)函數(shù)取向+）的情況。這時(shí)，利用單純形表亦可得出此結(jié)論。例

Max

z=15x1+18x2

－2x3

+5x5

s.t.

-3x1-12x2

+x3

=-81-2x1

-(22/3)x2

+x4=-137/3-6x2

+x5=-30

x1,x2,x3,x4,x5

≥0用單純形法求解得到

表中x3的檢驗(yàn)數(shù)大于零，而其對(duì)應(yīng)的約束矩陣元素均非正，說明此線性規(guī)劃無有限最優(yōu)解。

注意：?jiǎn)渭冃畏ㄖ?、每一步運(yùn)算只能用矩陣初等行變換；

2、表中第3列(b列)的數(shù)總應(yīng)保持非負(fù)（≥0）；

3、當(dāng)所有檢驗(yàn)數(shù)均非正（≤0）時(shí)，得到最優(yōu)單純形表。

4、當(dāng)最優(yōu)單純形表存在非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)為零時(shí)，可能存在無窮多解；Maxz=c1x1+c2x2+…+cnxn

s.t.

a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn

=b2...

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn

≥0§1.4初始基本可行解的確定大M法：引入人工變量xn+i

≥0（i=1,…,m）及充分大正數(shù)M

。得到：Max

z=c1x1+c2x2+…+cnxn-Mxn+1-…-Mxn+m

s.t.

a11x1+a12x2+…+a1nxn

+xn+1

=b1a21x1+a22x2+…+a2nxn+xn+2=b2...am1x1+am2x2+…+amnxn+xn+m=bm

x1，x2，…，xn

，xn+1，…，xn+m

≥0

Maxz=5x1+2x2+3x3-x4-Mx5-Mx6

s.t.

x1+2x2+3x3+x5

=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4

=26

x1,x2,x3,x4,x5,x6

≥0大M法問題(LP-M）大M法

（LP-M）得到最優(yōu)解：(25/3，10/3，0，11)T

最優(yōu)目標(biāo)值：112/3顯然，xj

=0j=1,…,n;

xn+i=bi

i=1,…,m

是基本可行解。對(duì)應(yīng)的基是單位矩陣。結(jié)論：若得到的最優(yōu)解滿足

xn+i=0

i=1,…,m

則是原問題的最優(yōu)解；否則，原問題無可行解。兩階段法：

引入人工變量xn+i

≥0，i=1,…,m；構(gòu)造:Maxz=-xn+1

-xn+2

-…-xn+m

s.t.

a11x1+a12x2+…+a1nxn+xn+1

=b1

a21x1+a22x2+…+a2nxn+xn+2

=b2...

am1x1+am2x2+…+amnxn+xn+m

=bmx1,x2...

xn,xn+1,…,xn+m

≥0第一階段求解上述問題：顯然，xj=0j=1,…,n;

xn+i=bi

i=1,…,m

是基本可行解,它對(duì)應(yīng)的基是單位矩陣。

Maxz=5x1+2x2+3x3-x4-Mx5-Mx6

s.t.

x1+2x2+3x3+x5

=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4

=26

x1,x2,x3,x4,x5,x6

≥0兩階段法：第一階段問題（LP-1）

Max

z=-x5

-x6

s.t.

x1+2x2

+3x3

+x5

=152x1

+x2

+5x3

+x6=20

x1

+2x2+4x3

+x4

=26

x1,x2,x3,x4,x5,x6

≥0第一階段(LP-1）

得到原問題的基本可行解:(0，15/7，25/7，52/7)T第二階段把基本可行解填入表中

得到原問題的最優(yōu)解:(25/3，10/3，0，11)T最優(yōu)目標(biāo)值：112/3合理利用線材問題：如何下料使用材最少。配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)。投資問題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大。5.線性規(guī)劃應(yīng)用(選學(xué))建模一、線性規(guī)劃---產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大。勞動(dòng)力安排：用最少的勞動(dòng)力來滿足工作的需要。運(yùn)輸問題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。

數(shù)學(xué)規(guī)劃的建模有許多共同點(diǎn)，要遵循下列原則：

(1)容易理解。建立的模型不但要求建模者理解，還應(yīng)當(dāng)讓有關(guān)人員理解。這樣便于考察實(shí)際問題與模型的關(guān)系，使得到的結(jié)論能夠更好地應(yīng)用于解決實(shí)際問題。

(2)容易查找模型中的錯(cuò)誤。這個(gè)原則的目的顯然與(1)相關(guān)。常出現(xiàn)的錯(cuò)誤有：書寫錯(cuò)誤和公式錯(cuò)誤。

(3)容易求解。對(duì)線性規(guī)劃來說，容易求解問題主要是控制問題的規(guī)模，包括決策變量的個(gè)數(shù)和約束條件的個(gè)數(shù)。這條原則的實(shí)現(xiàn)往往會(huì)與(1)發(fā)生矛盾，在實(shí)現(xiàn)時(shí)需要對(duì)兩條原則進(jìn)行統(tǒng)籌考慮。建立線性規(guī)劃模型的過程可以分為四個(gè)步驟：

(1)設(shè)立決策變量；

(2)明確約束條件并用決策變量的線性等式或不等式表示；

(3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極?。∕in）；

(4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。例2.12：某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：

人力資源分配的問題設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班，并連續(xù)工作8h，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?解：設(shè)xi

表示第i班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5+x6

約束條件：s.t.

x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0人力資源分配的問題例2.13:某工廠要做100套鋼架，每套用長(zhǎng)為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長(zhǎng)7.4m，問：應(yīng)如何下料，可使所用原料最??？套裁下料問題解:考慮下列各種下料方案（按一種邏輯順序給出）把各種下料方案按剩余料頭從小到大順序列出假設(shè)x1,x2,x3,x4,x5

分別為上面前5種方案下料的原材料根數(shù)。我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：

Min

x1+x2+x3+x4+x5

約束條件：

s.t.

x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0套裁下料問題

例2.14:明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？生產(chǎn)計(jì)劃的問題解：設(shè)x1,x2,x3

分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5

分別為由外協(xié)鑄造再由本公司機(jī)加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。生產(chǎn)計(jì)劃的問題

求xi

的利潤(rùn):利潤(rùn)=售價(jià)-各成本之和可得到

xi（i=1,2,3,4,5）的利潤(rùn)分別為15、10、7、13、9元。這樣我們建立如下數(shù)學(xué)模型：目標(biāo)函數(shù):

Max15x1+10x2+7x3+13x4+9x5

約束條件：

s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0生產(chǎn)計(jì)劃的問題

例2.15:永久機(jī)械廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，均要經(jīng)過A、B

兩道工序加工。假設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成A

工序；有三種規(guī)格的設(shè)備B1、B2、B3能完成B

工序。Ⅰ可在A、B的任何規(guī)格的設(shè)備上加工；Ⅱ可在任意規(guī)格的A設(shè)備上加工，但對(duì)B工序,只能在B1設(shè)備上加工；Ⅲ只能在A2與B2設(shè)備上加工；數(shù)據(jù)如下表。問：為使該廠獲得最大利潤(rùn)，應(yīng)如何制定產(chǎn)品加工方案？

生產(chǎn)計(jì)劃的問題解：設(shè)xijk

表示第i

種產(chǎn)品，在第j

種工序上的第k

種設(shè)備上加工的數(shù)量.利潤(rùn)=[（銷售單價(jià)-原料單價(jià)）×產(chǎn)品件數(shù)]之和-（每臺(tái)時(shí)的設(shè)備費(fèi)用×設(shè)備實(shí)際使用的總臺(tái)時(shí)數(shù)）之和。

生產(chǎn)計(jì)劃的問題這樣我們建立如下的數(shù)學(xué)模型:Max

0.75x111+0.7753x112+1.15x211+1.3611x212

+1.9148x312-0.375x121-0.5x221-0.4475x122

-1.2304x322-0.35x123

s.t

5x111+10x211≤6000

（設(shè)備A1

）

7x112+9x212+12x312≤10000（設(shè)備A2

）

6x121+8x221≤4000(設(shè)備B1

）

4x122+11x322≤700(設(shè)備B2

）

7x123≤4000

（設(shè)備B3

）生產(chǎn)計(jì)劃的問題x111+x112-x121-x122-x123=0(Ⅰ產(chǎn)品在A、B工序加工的數(shù)量相等）x211+x212-x221=0

(Ⅱ產(chǎn)品在A、B工序加工的數(shù)量相等）x312-x322=0(Ⅲ產(chǎn)品在A、B工序加工的數(shù)量相等）xijk≥0,i=1,2,3;j=1,2;k=1,2,3

生產(chǎn)計(jì)劃的問題例2.14:某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問：該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？配料問題配料問題

解：設(shè)xij

表示第i

種（甲、乙、丙）產(chǎn)品中原料j的含量。這樣我們建立數(shù)學(xué)模型時(shí)，要考慮：

對(duì)于甲：x11，x12，x13；對(duì)于乙：x21，x22，x23；對(duì)于丙：x31，x32，x33；對(duì)于原料1：x11，x21，x31；對(duì)于原料2：x12，x22，x32；對(duì)于原料3：x13，x23，x33；目標(biāo)函數(shù)：

利潤(rùn)最大，利潤(rùn)=收入-原料支出

約束條件：規(guī)格要求4個(gè)；

供應(yīng)量限制3個(gè)。

Max

z=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

配料問題s.t.0.5x11-0.5x12-0.5x13≥0

（原材料1不少于50%）

-0.25x11+0.75x12-0.25x13≤0

（原材料2不超過25%）

0.75x21-0.25x22-0.25x23≥0

（原材料1不少于25%）

-0.5x21+0.5x22-0.5x23≤0

（原材料2不超過50%）

x11+x21+x31≤100(供應(yīng)量限制）

x12+x22+x32≤100(供應(yīng)量限制）

x13+x23+x33≤60(供應(yīng)量限制）

xij≥0,i=1,2,3;j=1,2,3配料問題

投資