運籌學第一章線性規(guī)劃及單純形法

LinearProgramming（LP）

線性規(guī)劃問題及其數(shù)學模型

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

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

線性規(guī)劃的單純形法

線性規(guī)劃模型的應用第一章線性規(guī)劃及單純形法

線性規(guī)劃問題及其數(shù)學模型第一章線性規(guī)劃及單純形法LinearProgramming（LP）

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

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

線性規(guī)劃的單純形法

線性規(guī)劃模型的應用一、問題的提出

為了完成一項任務或達到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務或達到一定的目的，這個過程就是規(guī)劃。例1、有一正方形鐵皮，應如何裁剪能使容積最大？xa

無約束的極值問題例2、如何安排生產(chǎn)才能使利潤最大？資料如圖

設備產(chǎn)品ABCD利潤（元）

Ⅰ21402

Ⅱ22043

有效臺時1281612目標max

x1≥0,x2≥0s.t.2x1+2x2≤12

帶約束的極值問題x1x2z=2x1+3x2

約束條件x1+2x2≤84x1≤164x2≤12subjectto函數(shù)數(shù)學模型例3、合理配料問題數(shù)學模型x1x2

x3

x4

x5

x6z=4x1+3x2+6x3+5x4+2.7x5+2.2x6mins.t.x1+0x2+2x3+2x4+x5+2x6≥9

0x1+x2+3x3+x4+3x5+2x6≥19

x1,x2,…,x6≥0

每天服用這六種營養(yǎng)物各多少克，才能既獲得每日最少所需又使花費最?。慷?、數(shù)學模型組成要素：

決策變量

約束條件

目標函數(shù)線性規(guī)劃：連續(xù)的（數(shù)值取實數(shù)）關于變量的線性等式或不等式關于變量的線性函數(shù)（一次方）

問題中有未知的變量，需要我們?nèi)デ蠼?，此外有目標函?shù)及約束條件，一般有非負條件存在，由此組成規(guī)劃問題的數(shù)學模型。線性規(guī)劃數(shù)學模型的一般形式s.t.s.t.向量形式s.t.s.t.向量形式矩陣形式s.t.s.t.線性規(guī)劃問題的數(shù)學模型s.t.s.t.s.t.s.t.三、線性規(guī)劃問題的標準形式s.t.s.t.s.t.s.t.標準形式的主要特征s.t.③決策變量xj取值非負④約束條件右端常數(shù)項bi為非負值①目標函數(shù)為求極大值（也可用求極小值）②所有約束條件都是等式（非負條件除外）

√非標準形式化為標準形式的方法⑴目標函數(shù)的轉換⑵約束方程的轉換：由不等式轉換為等式⑶變量的變換稱為松弛變量稱為剩余變量x1+x24x1+x2－

x3=4⑷

約束條件右端常數(shù)項的變換：bi﹤0x1+x23x1+x2+x3=3例1、將下列線性規(guī)劃問題化為標準形式+0x5+0x4maxz

=－2x1

+

x2

－

3x3

maxz

=－2x1

+

(x2

－

x2)

+3x3

+0x4+0x53x1

－

2(x2

－

x2)－

x3

=－4－3x1

+2(x2

－

x2)+

x3

=4解：設min

x1≥0,x2取值無約束,x3≤0s.t.x1+2x2+4x3≤6z=2x1

－x2

+3x3

3x1

－

2x2+x3=－4

2x1

－

x2－

3x3≥

5

x1,x2

,x2

,x3

,x4,x5≥0

x1+2x2+4x3+x4

=6s.t.

2x1

－

x2－

3x3－

x5

=5引入變量令x1

+

2(x2

－

x2)－

4x3

+

x4=6第二個約束方程兩邊乘(－1),從而得到標準形式2x1

－

(x2

－

x2)＋

3x3

－

x5

=5－3x1

+2x2

－

2x2

+

x3

=4

x1,x2

,x2

,x3

,x4,x5≥0s.t.x1

+2x2

－

2x2

－

4x3

+

x4=62x1

－

x2

＋

x2

＋

3x3

－

x5

=5maxz

=－2x1

+

x2

－

x2

+3x3

+0x4+0x5例2、將下列線性規(guī)劃問題化為標準形式x1

＋

2(x2

－

x2)＋

x3

＋

x4

=5x1,x2

,x2

,x3

,x4,

x5,

x6

≥0x1

＋

(x2

－

x2)＋

x3

＋

x6

=2maxz=x1

+2(x2

－

x2)

+3x3

+0x4+0x5+

0x6解：max

x1≥0,x2取值無約束,x3≤0s.t.x1+2x2－

x3≤5z=x1+2x2

－

3x3

2x1+

3x2－

x3≥6

－x1

－

x2+

x3≥

－2引入變量令第三個約束方程兩邊乘(－1),從而得到標準形式2x1

＋

3(x2

－

x2)＋

x3

－

x5

=6s.t.x1

＋

2x2

－

2x2

＋

x3

＋

x4

=5x1,x2

,x2

,x3

,x4,x5,x6≥0x1

＋

x2

－

x2

＋

x3

＋

x6

=2maxz=x1

+2x2

－

2x2

+3x3

+0x4+0x5+

0x62x1

＋

3x2

－

3x2

＋

x3

－

x5

=6練習：將下列線性規(guī)劃問題化為標準形式min

x1,x2≥0,x3取值無約束s.t.x1

－

x2+x3≤10z=－2x1+3x2

－

x3

3x1+

2x2－

x3≥8x1

－

3x2+

x3=－1－x1

＋

3x2

－

x3

＋

x3

=1maxz

=2x1

－3x2+

x3

－

x3

+0x4+0x53x1

＋

2x2

－

x3

＋

x3

－

x5

=8

x1,x2,x3

,x3

,x4,x5≥0s.t.x1

－

x2

＋

x3

－

x3

＋

x4

=10解：設引入變量令第三個約束方程兩邊乘(－1),從而得到標準形式即：系數(shù)矩陣的秩為m且小于n，則根據(jù)線性代數(shù)定理可知，②若有解則必有無窮多解，這是線性規(guī)劃問題能尋求最優(yōu)解的余地所在。

四、線性規(guī)劃問題的解s.t.③②①

可行解：滿足約束條件②、③的解

最優(yōu)解：使目標函數(shù)①達到最大值的可行解方程組②中：通常m＜n，且m個方程線性無關。

可行域：所有可行解構成的集合思考題：

某部門有一批資金用于甲、乙、丙、丁、戊五個工程項目的投資，由于某種原因，決定用于項目甲的投資不大于其他各項投資之和；而用于項目乙和戊的投資之和不小于項目丙的投資。已知用于各個工程項目時所得的凈收益(投入資金的百分比)如上表所示。試確定使該部門收益最大的投資分配方案。要求：建立線性規(guī)劃模型，并化為標準形式。工程項目甲乙丙丁戊收益（%）108659分析：z=0.1x1+0.08x2+0.06x3+0.05x4+0.09x5maxs.t.x1+x2+x3+x4+x5=1

x1－

x2－

x3－

x4－

x5≤0

x1,x2,…,x5≥0

工程項目甲乙丙丁戊收益（%）108659設xj表示用于第j個項目的投資百分比。目標函數(shù)約束條件

用于甲的投資不大于其他各項投資之和；而用于乙和戊的投資之和不小于丙的投資。x2－

x3+x5≥0

總投資的要求對甲的要求對乙、戊的要求非負要求標準形式z=0.1x1+0.08x2+0.06x3+0.05x4+0.09x5+0x6+0x7

maxs.t.x1+x2+x3+x4+x5=1

x1－

x2－

x3－

x4－

x5+0x6

=0

x1,x2,…,x5,x6,

x7≥0

x2－

x3+x5+x7

=0

線性規(guī)劃問題的求解方法第一章線性規(guī)劃及單純形法LinearProgramming（LP）

線性規(guī)劃問題及其數(shù)學模型

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

線性規(guī)劃的單純形法

線性規(guī)劃模型的應用一、預備知識：解的概念

可行解：滿足約束條件的解

最優(yōu)解：使目標函數(shù)達到極值的可行解

可行域：所有可行解構成的集合s.t.一、預備知識：凸集與頂點x1x2x2x1x1x2x1x2x1x2x1x2凸集：集合C中任意兩點連線上的所有點還在C內(nèi)

任給x1,x2

C,x=

x1+(1－

)x2

C(0<

<1)頂點：凸集C中不在任意兩不同點連線上的點

對x,任給x1,x2

C,不存在x=

x1+(1－

)x2(0<

<1)凸集非凸集二、圖解法步驟：將約束條件在圖上表示建立直角坐標系確立滿足約束條件的解的范圍(可行域)繪制出目標函數(shù)的圖形在可行域中確定最優(yōu)解定義：用圖示的方法求解線性規(guī)劃問題的最優(yōu)解優(yōu)點：直觀性強，計算方便缺點：只適用于問題中是兩(三)個變量的情況123456781234562x1+2x2=12x1+2x2=84x1=164x2=12唯一最優(yōu)解此時z=14。(4,2)示例1：s.t.①②③④0x2

x1z=0x1=4,x2=2,

123456781234563x1+2x2=12x1+2x2=6x2=2無窮多最優(yōu)解示例2：0x2

x1s.t.①②③x1－x2=－1x1+2x2=2無界解(無最優(yōu)解)示例3：s.t.①②x1x2

0思考：若目標函數(shù)改為minz=x1+x2呢？

若改為minz=x1+

2x2呢？無可行解示例4：s.t.①②x1+x2=1x1x2

02x1+3x2=62x2=12練習：s.t.x1=83x1+4x2

=36(4,6)x1812x243690唯一最優(yōu)解此時z=42。x1=4,x2=6,

（4）無可行解：無可行域，模型約束條件矛盾圖解法的幾點啟示線性規(guī)劃問題解的情況有：（1）唯一最優(yōu)解：只有一點為最優(yōu)解點（2）無窮多最優(yōu)解：有許多點為最優(yōu)解點（3）無界解：最優(yōu)解取值無界，無最優(yōu)解LP問題的可行域若存在則一定是凸集(有限個頂點)LP問題若有最優(yōu)解，則定能在可行域某頂點達到LP問題的解題思路：頂點→相鄰頂點→……三、單純形法（SimplexMethod）美國數(shù)學家丹齊格(G.B.Dantzig)1947年創(chuàng)建簡捷、規(guī)范，是舉世公認的解決線性規(guī)劃問題行之有效的方法。

理論根據(jù)：基本思想：在凸集的有限個頂點上搜索最優(yōu)解該搜索策略可極大地減少訪問頂點的數(shù)量。

由可行域的一個頂點出發(fā)，沿著凸集邊緣逐個計算與判定所遇到的頂點，直至找到最優(yōu)解所對應的頂點為止。

線性規(guī)劃問題的可行域是n維向量空間中的多面凸集，其最優(yōu)值如果存在則必在該凸集的某頂點處達到。s.t.(一)基解與基可行解系數(shù)矩陣A是m×n矩陣（設m<n），其秩R(A)=m。線性規(guī)劃問題的基：矩陣A中的m×m階滿秩子矩陣B。(|B|≠0)基解：令非基變量為零，對m個基變量求解后合并所得的解。最多個基向量：B中的m個列向量Pr?；兞浚号c基向量對應的m個變量xr。剩下n-m個非基變量。(一)基解與基可行解基解：令非基變量為零，對m個基變量求解后合并所得的解。設

，

令非基變量基變量為，|B|≠0基變量的唯一解基解最多個(一)基解與基可行解基解：令非基變量為零，對m個基變量求解后合并所得的解?；尚薪猓簼M足變量非負約束條件xj≥0的基解?？尚谢簩诨尚薪獾幕；尚薪饪尚薪夥强尚薪饣饣馐欠窕尚薪饽繕撕瘮?shù)值例題：列出全部基、基解、基可行解和指出最優(yōu)解s.t.s.t.標準化系數(shù)矩陣:例題：用圖解法求最優(yōu)解s.t.x1+x2=3x1+2x2=4(2,1)12341230x2

x1基解對應于各直線交點基可行解是可行域的頂點(二)單純形法的基本定理定理1：若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。定理3：若線性規(guī)劃問題有最優(yōu)解，則一定存在一個基可行解是最優(yōu)解。定理2：線性規(guī)劃問題的基可行解對應其可行域的頂點。理論根據(jù)：

線性規(guī)劃問題的可行域是n維向量空間中的多面凸集，其最優(yōu)值如果存在則必在該凸集的某頂點處達到。在有限個基可行解中搜索最優(yōu)解（迭代）(三)單純形法的求解思路確定一個初始基可行解是否最優(yōu)改進為新的基可行解最優(yōu)解是否循環(huán)結束化標準形1、確定初始基可行解s.t.s.t.標準化約束方程組的系數(shù)矩陣：基變量值：初始基可行解：記2、最優(yōu)性檢驗s.t.初始基可行解：任一可行解：由約束方程組得代入目標函數(shù)可得：則有：檢驗數(shù)基變量的其中2、最優(yōu)性檢驗當前基可行解是最優(yōu)解若所有，則對任意可行解X，都有線性規(guī)劃問題存在無界解（無最優(yōu)解）若存在某個，且所有令只需保證由所有顯然此時因找可行解X，使z無限大。線性規(guī)劃問題無可行解2、最優(yōu)性檢驗當前基可行解是最優(yōu)解：所有線性規(guī)劃問題有唯一最優(yōu)解′線性規(guī)劃問題有無窮多最優(yōu)解′′線性規(guī)劃問題存在無界解（無最優(yōu)解）若存在某個，且所有存在和當前基可行解非最優(yōu)解，但LP問題有最優(yōu)解其中所有；

或

有非基變量,且3、尋找改進的基可行解

相鄰的基可行解：若兩個基可行解之間僅變換一個基變量。

將一個基變量變成非基變量（換出），一個非基變量變成基變量（換入），進而找出一個目標函數(shù)值更大的“相鄰”基可行解。入基變量的確定由和越大，值上升的可能性越大因此，一般取對應的變量作為換入基的變量。3、尋找改進的基可行解出基變量的確定令換入變量為得到基可行解，需保證且至少一個為0（換出）則只需取其余非基變量，存在此時換出。確定為換出變量，由稱為主元素?？尚薪猓鹤C明是基可行解？§3-1引理3、尋找改進的基可行解約束方程組的系數(shù)矩陣：初始基

，

變量換入,換出，新可行解對應向量：是線性無關的，故是基可行解。s.t.單純形法的求解思路確定一個初始基可行解是否最優(yōu)改進為新的基可行解最優(yōu)解是否循環(huán)結束化標準形？步驟簡單總結經(jīng)過何種運算可轉到第③步，實現(xiàn)循環(huán)迭代？①將線性規(guī)劃問題化成標準形式;②找出或構造一個m階單位矩陣作初始可行基，得到初始基可行解;③計算各非基變量xj的檢驗數(shù)

j，若所有

j≤0，則問題已得到最優(yōu)解，停止計算，否則轉入下步;④若存在某個

s>0，且對應的所有系數(shù)ais≤0，則此問題是無界解，停止計算，否則轉入下步;⑤根據(jù)max{

j|

j＞0}=

k原則，確定xk為入基變量，再按

=min{bi/aik|aik＞0}=bl/alk規(guī)則，確定xl為出基變量，得到改進的基可行解。將其化為單位矩陣，

則LP問題形式為s.t.4、迭代運算初始基

，

變量換入,換出，新可行基：s.t.4、迭代運算①主元素所在行：②

其余行：4、迭代運算新檢驗數(shù)

s.t.整理后可得

①將線性規(guī)劃問題化成標準形式;②找出或構造一個m階單位矩陣作初始可行基，得到初始基可行解;③計算各非基變量xj的檢驗數(shù)

j，若所有

j≤0，則問題已得到最優(yōu)解，停止計算，否則轉入下步;④若存在某個

s>0，且對應的所有系數(shù)ais≤0，則此問題是無界解，停止計算，否則轉入下步;⑤根據(jù)max{

j|

j＞0}=

k原則，確定xk為入基變量，再按

=min{bi/aik|aik＞0}=bl/alk規(guī)則，確定xl為出基變量；⑥以alk為主元素進行迭代，利用初等行變換將xk所在列化為單位向量，即alk化為1，其它元素化為0，得到改進的可行基，轉入第③步。計算步驟總結(四)單純形表格法——單純形表s.t.……max

x1,x2≥0s.t.

2x1+2x2≤12z=2x1+3x2

4x1

≤

165x2≤15例題：用單純形法求解線性規(guī)劃問題+0x4+0x3maxz=2x1

+3x2s.t.引入變量得到標準形式解：+0x55x2+x5

=154x1

+

x4=162x1

+2x2+

x3=12x1,x2,x3,x4,x5≥0+0x4+0x3maxz=2x1

+3x2s.t.引入變量得到標準形式解：+0x55x2+x5

=154x1

+

x4=162x1

+2x2+

x3=12x1,x2,x3,x4,x5≥0此時所有檢驗數(shù)得到最優(yōu)解最優(yōu)值為①將線性規(guī)劃問題化成標準形式;②找出或構造一個單位矩陣作初始可行基，確定初始基可行解，建立初始單純形表;③檢驗各非基變量xj的檢驗數(shù)

j，若所有

j≤0，則問題已得到最優(yōu)解，停止計算，否則轉入下步;④若存在某個

s>0，且對應的所有系數(shù)ais≤0，則此問題是無界解，停止計算，否則轉入下步;⑤根據(jù)max{

j|

j＞0}=

k原則，確定xk為入基變量，再按

=min{bi/aik|aik＞0}=bl/alk規(guī)則，確定xl為出基變量；⑥用xk替換基變量中的xl，利用初等行變換將xk所在列化為單位向量，得到新的單純形表，轉入第③步。單純形法計算步驟標準化系數(shù)矩陣(五)單純形法的進一步討論

用單純形法解題時，需要有個單位矩陣作為初始可行基當約束條件都是“≤”時，加入松弛變量就形成了初始基

但實際存在“≥”或“＝”型的約束，沒有現(xiàn)成的單位矩陣s.t.－2x1＋

x2－x3

－

x5

=1解：引入變量從而得到標準形式s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9maxz=－3x1

+

0x2

+

x3+0x4+0x5約束方程組的系數(shù)矩陣：maxz=－3x1

+

0x2

+

x3+0x4+0x5(五)單純形法的進一步討論采用添加人工變量的方法

因是在等式中人為加進的，為保證約束條件的意義，最優(yōu)解中人工變量只能等于0

在等式約束中加入若干人工變量，人為構造一個單位矩陣

人工變量的添加不能影響最優(yōu)解的取值：－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9約束方程組的系數(shù)矩陣：兩種處理方法

大M法兩階段法＋

x6

=1

＋

x7

=9=4,x6,x7≥0如何處理？1、大M法maxz=－3x1

+

0x2

+

x3+0x4+0x5－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0－Mx6－Mx7

為保證最優(yōu)解中人工變量取值為0，可令目標函數(shù)中人工變量的系數(shù)為足夠大的一個負值，用“－M”代表。

由于系數(shù)是一個足夠大的負值，因此，只要人工變量的取值不為零，目標函數(shù)就不可能實現(xiàn)最大化。

計算時，把M看做一個代數(shù)符號直接參加單純形法求解。

若最終單純形表中，人工變量仍是基變量且值不為零，則說明該問題求不到最優(yōu)解，即無可行解。－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0maxz=－3x1

+

0x2

+

x3+0x4+0x5－Mx6－Mx7使人工變量盡快出基此時所有檢驗數(shù)得到最優(yōu)解最優(yōu)值為－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0maxz=－3x1

+0x2

+

x3+0x4+0x5

用大M法處理人工變量，用手工計算不會出現(xiàn)任何問題。

但用計算機求解時，由于在程序中只能用很大的數(shù)代替M，有可能受計算機的誤差影響，導致結果發(fā)生錯誤，使大M法失效。2、兩階段法

第一階段：構造判斷是否存在可行解的模型

構造僅含人工變量(系數(shù)為1)且要求極小化的目標函數(shù)

用單純形法求解，若minw=0，說明人工變量為0，問題存在基可行解，進入第二個階段；若minw≠0，說明最優(yōu)解中人工變量非零，無可行解，停止。minw=x6+

x7minw=x6+

x72、兩階段法－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥02、兩階段法

第二階段：從上階段的最終單純形表出發(fā)，去掉人工變量，引入原來的目標函數(shù)，繼續(xù)迭代，找出問題的最終解maxz=－3x1

+

0x2

+

x3+0x4+0x5人工變量法總結約束方程組

在等式約束中加人工變量，人為構造單位矩陣作初始可行基目標函數(shù)

為保證原約束條件的意義，最優(yōu)解中人工變量只能是0大M法

令目標函數(shù)中人工變量的系數(shù)為足夠大的一個負值“－M”兩階段法1、構造僅含人工變量且求極小化的目標函數(shù)，單純形法求解；2、去掉上階段最終單純形表中的人工變量，引入原目標函數(shù)，繼續(xù)迭代，找出問題的最終解。

若最終單純形表中，人工變量仍是基變量且值不為零，則說明該問題求不到最優(yōu)解，即無可行解。3、由單純形表判別解的類別無可行解唯一最優(yōu)解所有無窮多最優(yōu)解無界解（無最優(yōu)解）最終單純形表的基變量中仍有非零人工變量存在某個，且所對應的系數(shù)最優(yōu)解某非基變量至少一個且≤0≥0保證當前的基可行解是最優(yōu)解

至少有一個等于0，如

至少有一個大于0，如

＞0

存在，保證當xp入基時有xl出基說明能得到另一個最優(yōu)基可行解兩個基可行解連線上的所有點都是最優(yōu)解無窮多最優(yōu)解示例1：s.t.標準化s.t.此時所有檢驗數(shù)得到最優(yōu)解最優(yōu)值為此時所有檢驗數(shù)得另一最優(yōu)解最優(yōu)值為無界解(無最優(yōu)解)示例2：s.t.標準化s.t.且所對應系數(shù)取值無限制160x2

x14x1=16無可行解示例3：s.t.標準化s.t.此時所有檢驗數(shù)但人工變量仍留在基變量中且不為零，問題無可行解。單純形法小結

根據(jù)實際問題給出數(shù)學模型，首先化為標準形式，構造出單位矩陣作為基，列出初始單純形表.單純形法計算框圖唯一最優(yōu)解添加松弛變量、人工變量列出初始單純形表計算非基變量各列的檢驗數(shù)бj所有бj

0基變量中有非零的人工變量

否某非基變量檢驗數(shù)為零﹡

否無可行解無窮多最優(yōu)解對任一бj≥0有aik≤0無界解令бk=max{бj}xk為入基變量對所有aik>0計算θi=bi/aik

令θl=min{θi}xl為出基變量

alk為主元素迭代運算1、用非基變量xk替換基變量xl2、對主元素行(第l行)

令bl/alk→bl；alj/alk→ajl3、對主元素列(第k列)

令1→alk;0→其它元素4、表中其它行令ri－rl/alk·aik→ri列出新的單純形表否否是是

是是循環(huán)補充說明單純形法在計算中可能出現(xiàn)以下兩種情況：同時出現(xiàn)多個相同的最大

j值同時出現(xiàn)多個相同的最小θ值

理論上可能出現(xiàn)死循環(huán)，但實際很罕見，一般不需特殊處理，任選其中一個對應的變量入基或出基即可。

若遇到極端情況，可利用勃蘭特(bland)規(guī)則：當存在多個

j>0時，選取下標值最小的變量入基；當出現(xiàn)多個相同最小θ時，選取下標值最小的變量出基。

線性規(guī)劃模型的應用第一章線性規(guī)劃及單純形法LinearProgramming（LP）

線性規(guī)劃問題及其數(shù)學模型

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

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

線性規(guī)劃的單純形法線性規(guī)劃問題的建模

建模是運籌學方法的核心和精髓，建立一個正確的數(shù)學模型，是問題解決的關鍵，答案利用線性規(guī)劃程序可很快獲得。正確的建模要求建模者：理解生產(chǎn)和管理問題的本質(zhì)，明確目標和錯綜復雜的約束條件，通過調(diào)查和統(tǒng)計資料獲取原始可靠的數(shù)據(jù)。建模過程的規(guī)律：①通過對實際問題的分析、理解，明確那些是決策變量，目標要求是什么，有哪些資源限制條件；②把變量、常數(shù)、約束條件、目標要求的相互關系聯(lián)系起來列出相應的方程式；③注意變量、系數(shù)、常數(shù)的計量單位要統(tǒng)一。線性規(guī)劃問題的應用

問題需滿足的條件

①目標函數(shù)能用數(shù)值指標來反映，且為線性函數(shù)；

②存在多種方案及有關數(shù)據(jù)；

③要達到的目標是在一定約束條件下實現(xiàn)的，這些條件可用線性等式或不等式描述。相關問題生產(chǎn)計劃問題（合理利用資源，使利潤最高或完成計劃）合理配料問題（保證飲食、藥品等效果前提下使成本最低）投資方案選擇問題（固定資金投入時使效益最高）人員分派問題（多項任務分配，使人數(shù)最少或效率最大）合理下料問題（在給定材料中截取零件，使用料最?。┻\輸問題＊（多個產(chǎn)銷地及運價限制，安排方案使運費最低）……生產(chǎn)計劃問題：如何安排生產(chǎn)使利潤最大？資料如圖

設備產(chǎn)品ABCD利潤（元）

Ⅰ21402

Ⅱ22043

有效臺時1281612max

x1,x2≥0s.t.2x1+2x2≤12z=2x1+3x2

x1+2x2≤84x1≤164x2≤12設xj表示第j種產(chǎn)品在計劃期內(nèi)的產(chǎn)量合理配料問題：資料如圖

設xj表示第j種營養(yǎng)物所需克數(shù)z=4x1+3x2+6x3+5x4+2.7x5+2.2x6mins.t.x1+0x2+2x3+2x4+x5+2x6≥9

0x1+x2+3x3+x4+3x5+2x6≥19

x1,x2,…,x6≥0

每天服用6種營養(yǎng)物各多少克，才能既獲得每日所需又使花費最?。客顿Y方案選擇問