《運籌學》 課件 第1-7章-線性規(guī)劃-圖與網絡

7/16/2024第1章線性規(guī)劃1CONTENTS目錄7/16/20241.1

線性規(guī)劃建模1.2

線性規(guī)劃的解1.3

線性規(guī)劃的圖解法1.4線性規(guī)劃的基本定理1.5

單純形法1.6

單純形法的進一步討論1.7應用舉例21.1線性規(guī)劃建模例1.1

生產計劃問題問產品A,B各生產多少,可獲最大利潤?生產經營中經常提出的一個問題是：如何合理地利用人、財、物，以降低成本，獲取效益，這就是規(guī)劃問題。7/16/20241.1.1線性規(guī)劃引例

AB備用資源

鋼材（噸）1230勞動力（工時）3260特種設備（臺時）0224

利潤（元/件）40504

x1

+2x2

303x1+2x2

60

2x2

24

x1，x2

0maxz=40x1+50x2解:設產品A,B的產量分別為變量x1,

x2s.t.7/16/20241.1.1線性規(guī)劃引例5例1.2混合配料問題請設計一個既保證維生素攝入量，又最經濟的配食方案。

飼料ABC

每單位成本

飼料14102飼料26125飼料31716飼料42538每天維生素12148的最低需求維生素/mg7/16/20241.1.1線性規(guī)劃引例6解：設每天給每頭奶牛喂食飼料i的單位用量為xi

(i=1,2,3,4)minz=2x1

+5x2+6x3+8x4

4x1

+6x2+x3+2x4

12x1

+x2+7x3+5x4

14

2x2

+x3+3x4

8

xi

0(i=1,…,4)7/16/20241.1.1線性規(guī)劃引例s.t.7線性規(guī)劃問題的特征要解決的問題的目標可以用數(shù)值指標反映對于要實現(xiàn)的目標有多種方案可選擇有影響決策的若干約束條件線性規(guī)劃模型的要素決策變量：向量

(x1,

…,xn)T

，即決策人要考慮和控制的因素（通常非負）約束條件：線性等式或不等式目標函數(shù)：z=f(x1,

…,xn)

線性式，求

z

極大或極小7/16/20241.1.1線性規(guī)劃引例8max(min)z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn(=,)b1a21x1+a22x2+…+a2nxn

(=,)b2………am1x1+am2x2+…+amnxn

(=,)bmxj()0,j=1,2,…,n7/16/20241.1.2線性規(guī)劃模型的一般形式9a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn

=b2…………am1x1+am2x2+…+amxn

=bmxj0(j=1,2,…,n)maxz=c1x1+c2x2+…+cnxn其中

bi

0(i=1,2,…,m)7/16/20241.1.3線性規(guī)劃模型的標準形式10maxz=cTxs.t.Ax=bx

0

a11a12………a1n其中A=

a21a22………

a2n

…

am1am2………amn

x1

x=x2

xn…

b1

b=b2

bm…

c1

c=c2

cn…標準形式的矩陣表示：7/16/20241.1.3線性規(guī)劃模型的標準形式11(1)目標函數(shù)(2)約束條件(3)決策變量非標準型

標準型7/16/20241.1.3線性規(guī)劃模型的標準形式12(1)

目標函數(shù)xoz-z令z’=

－

z非標準型

標準型7/16/20241.1.3線性規(guī)劃模型的標準形式13(2)

約束條件例1.

maxz=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20非標準型

標準型7/16/20241.1.3線性規(guī)劃模型的標準形式14(2)

約束條件

x1+2x2+x3=303x1+2x2+x4=602x2+

+x5=24

x1,

…,x50

x3,x4,x5

稱為松弛變量(slackvariables)例1.

maxz=40x1+50x2+0·x3+0·x4+0·x5非標準型

標準型7/16/20241.1.3線性規(guī)劃模型的標準形式154x1+6x2+x3+2x4

12x1+x2+7x3+5x4

142x2+x3+3x4

8

x1,

…,x4

0

例2.

minz=2x1+5x2+6x3+8x4(2)

約束條件非標準型

標準型7/16/20241.1.3線性規(guī)劃模型的標準形式16(2)

約束條件4x1+6x2+x3+2x4-x5=12x1+x2+7x3+5x4-x6=142x2+x3+3x4-x7=8

x1,

…,x7

0

x5,x6,x7

剩余變量(surplusvariables)例2.

minz=2x1+5x2+6x3+8x4非標準型

標準型7/16/20241.1.3線性規(guī)劃模型的標準形式17(3)

決策變量3

x1'-3x1"+2x28x1'

-x1"–4x2

14x1',x1",x203x1+2x28x1–4x2

14x20令

x1=x1'-x1"非標準型

標準型7/16/20241.1.3線性規(guī)劃模型的標準形式18(3)

決策變量x1'

+x211x1'

16x1',x20x1+x25-6

x110x20-6+6x1+6

10+6

令

x1'

=x1+6

0

x1'

16非標準型

標準型7/16/20241.1.3線性規(guī)劃模型的標準形式197/16/20241.1.3線性規(guī)劃模型的標準形式變換的方法目標函數(shù)為

min型，價值系數(shù)一律反號，即令

f

(x)=-f(x)=-

cTx第

i個約束的

bi

為負值，則該行左右兩端系數(shù)同時反號，同時不等號也要反向第

i個約束為型，在不等式左邊增加一個非負的變量

xn+i，稱為松弛變量；同時令

cn+i

=0第

i個約束為型，在不等式左邊減去一個非負的變量

xn+i，稱為剩余變量；同時令

cn+i

=0若

xj0，令

xj=-

xj

，代入非標準型，則有

xj

0若

xj正負不限，令

xj=xj

-

xj

，xj

0，xj

0，代入非標準型201.2線性規(guī)劃的解maxz=cTxs.t.Ax=b(1)x

0(2)定義1：滿足約束(1)，(2)的x=(x1,…,xn)T稱為LP問題的可行解，全部可行解的集合稱為可行域。定義2：使目標函數(shù)達到最大值的的可行解稱為LP問題的最優(yōu)解。(LP)7/16/20241.2線性規(guī)劃的解22BN(m<n)rank(A)=m[至少有一個m階子式不為0]Am×n

滿秩m×m滿秩子矩陣a11…a1ma1m+1…a1na21…

a2ma2m+1…

a2n………am1…

ammamm+1…

amnP1…

PmPm+1…

PnAm×n=maxz=cTxs.t.Ax=bx

0x

=(x1,…,xn)T7/16/20241.2線性規(guī)劃的解23定義3：基(基陣)

—

若A

中一個m×m子矩陣B

是可逆矩陣，則稱方陣B

為LP問題的一個基。A=(P1…

PmPm+1…

Pn)=(BN)

基向量

非基向量

BN…X=(x1…

xmxm+1…

xn)T=(XBXN)T

基變量

非基變量

XB

XN…7/16/20241.2線性規(guī)劃的解24AX=b的求解A=(BN)X=(XBXN)TXBXN(BN)=bBXB+NXN=bBXB=b-NXNXB=B-1b-B-1NXN7/16/20241.2線性規(guī)劃的解25定義4：基本解

—

對應于基B，X=為AX=b的一個解。B-1b

0定義5：基本可行解

—基B，基本解X=

B-1b

0若B-1b0，稱基

B為可行基。若其基本解是最優(yōu)解，成為最優(yōu)基本解，相應的基為最優(yōu)基?！?/p>

基本解中最多有m個非零分量;基本解的數(shù)目7/16/20241.2線性規(guī)劃的解26約束方程的解空間基本解可行解非可行解基本可行解7/16/20241.2線性規(guī)劃的解271.3線性規(guī)劃的圖解法非負約束Thenon-negativeconstraintsx2x1最簡單、直觀的方法但只適用有兩個決策變量的情況7/16/20241.3.1圖解法的步驟29012345678可行域x2非可行域x1+2x2￡843214x1￡16x1最優(yōu)解點x1=4，x2

=2z=

2x1+3x2即x2=

-2x1/3+z/3z取不同值時是一束斜率為-2/3平行線，z最大值出現(xiàn)在最高的一條線上。

4x2￡

127/16/20241.3.1圖解法的步驟已知某線性規(guī)劃模型歸結為：目標函數(shù)max

z=

2x1+3x2約束條件x1+2x2

8

4

x1

16

s.t.4x2

12x1,x2

0307/16/20241.3.1圖解法的步驟max

z=x1+3x2 s.t. x1+x2≤6

-x1+2x2≤8

x1≥0,x2≥0可行域目標函數(shù)等值線最優(yōu)解64-860x1x231例1.1

maxz=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x207/16/20241.3.2線性規(guī)劃解的幾種可能性32DABC解：(1)確定可行域

x10x1=0(縱)x20x2=0(橫)x1+2x230(0,15)(30,0)0102030x23x1+2x2

60(0,30)(20,0)

2x2

24(0,12)203010x17/16/20241.3.2線性規(guī)劃解的幾種可能性33(2)求最優(yōu)解解：x*=(15,7.5)zmax=975z=40x1+50x20=40x1+50x2(0,0),

(10,-8)C點：

x1+2x2=30

3x1+2x2=60DABC0102030x2203010x17/16/20241.3.2線性規(guī)劃解的幾種可能性34例：

maxz=40x1+80x2

x1+2x2303x1+2x2602x224

x1,x207/16/20241.3.2線性規(guī)劃解的幾種可能性無窮多個最優(yōu)解35最優(yōu)解：BC線段B點x(1)=(6,12)C點x(2)=(15,7.5)x*=

x(1)+(1-

)x(2)(01)求解DABC0102030x2203010x1Z=40x1+80x2=0

1.3.2線性規(guī)劃解的幾種可能性036無界無有限最優(yōu)解例：

maxz=2x1+4x22x1+x2

8-2x1+x22x1,x20Z=02x1+x2=8-2x1+x2=28246x240x17/16/20241.3.2線性規(guī)劃解的幾種可能性無界解37例：

maxz=2x1+x2

x1+x2

22x1+2x26x1,x20無解無可行解7/16/20241.3.2線性規(guī)劃解的幾種可能性無可行解x1+x2=22x1+2x2=64123x220x13387/16/20241.3.2線性規(guī)劃解的幾種可能性

線性規(guī)劃的可行域及最優(yōu)解的可能結果圖示：

(a)可行域封閉，唯一最優(yōu)解(b)可行域封閉，多個最優(yōu)解(d)可行域開放，多個最優(yōu)解(e)可行域開放，目標函數(shù)無界(f)可行域為空集(c)可行域開放，唯一最優(yōu)解39唯一解無窮多個最優(yōu)解無有限最優(yōu)解無可行解有解無解總結:7/16/20241.3.2線性規(guī)劃解的幾種可能性40可行域為凸多邊形若有最優(yōu)解，一定在可行域的頂點達到X(1)X(2)凸多邊形凹多邊形X(1)X(2)7/16/20241.3.3圖解法的啟示41凸集及其性質定義1：凸集—

D是n維歐氏空間上的一個集合

X(1),

X(2)∈D,對任一個滿足

X=

X(1)+(1-

)X(2)(01)

有X∈D凸集中任意兩點的連線仍然屬于該集合。

7/16/20241.3.3圖解法的啟示42凸集及其性質定義2：凸組合—

X(1),X(2),…,X(k)

是n維歐氏空間中

的

k個點,若有一組數(shù)

μ1,μ2,…

,μk

滿足

0

μi1

(i=1,…,k)

μi=1

ki=1有點X=μ1X(1)

+…+μkX(k)則稱點X為X(1),X(2),…,X(k)

的凸組合。7/16/20241.3.3圖解法的啟示437/16/20241.3.3圖解法的啟示—凸集D,點XD，若找不到兩個不

同的點

X(1),X(2)D使得

X=

X(1)

+(1-

)

X(2)

(0<<1)

則稱

X為D的頂點。凸集及其性質定義3：頂點凸多邊形也稱為極點extremepoint44幾何概念代數(shù)概念約束直線滿足一個等式約束的解約束半平面滿足一個不等式約束的解約束半平面的交集：凸多邊形滿足一組不等式約束的解約束直線的交點基本解可行域的極點基本可行解目標函數(shù)等值線：一組平行線目標函數(shù)值等于一個常數(shù)的解1.3.3圖解法的啟示0451.4線性規(guī)劃的基本定理若(LP)問題有可行解，則可行解集（可行域）是凸集（可能有界，也可能無界），有有限個頂點。(LP)問題的基本可行解可行域的頂點。若(LP)問題有最優(yōu)解，必定可以在基本可行解（頂點）達到。7/16/20241.4線性規(guī)劃的基本原理47若(LP)問題有可行解，則可行解集（可行域）是凸集（可能有界，也可能無界），有有限個頂點。即證滿足約束條件的所有點組成的圖形是凸集。or7/16/20241.4線性規(guī)劃的基本原理48

(LP)問題的基本可行解可行域的頂點。引理：線性規(guī)劃問題的可行解

X

=(x1,

…,xn)

為基本可行解的充要條件是

X的正分量所對應的系數(shù)列向量是線性獨立的。證明：由基本可行解定義顯然成立；若向量P1,P2,…,Pk

線性獨立，則必有k≤m；（1）“k=m”

恰好構成一個基；（2）“k<m”一定可以從其余列向量中找出(m-k)個與P1,P2,…,Pk

構成一個基，其對應的解恰為X。7/16/20241.4線性規(guī)劃的基本原理49

(LP)問題的基本可行解可行域的頂點。反證法（1）X

不是基本可行解X

不是可行域的頂點假設X的前m個分量為正：由引理，P1,P2,…,Pm

線性相關，即7/16/20241.4線性規(guī)劃的基本原理50反證法（2）X

不是可行域的頂點X

不是基本可行解可以找到可行域內另外兩個不同點Y和Z：X=aY+(1-a)Z(0<a<1)

(LP)問題的基本可行解可行域的頂點。7/16/20241.4線性規(guī)劃的基本原理51

若(LP)問題有最優(yōu)解，必定可以在基本可行解（頂點）達到。證明：設是線性規(guī)劃的一個最優(yōu)解。若不是基本可行解，則不是頂點。可以找到另兩個點。代入目標函數(shù)：如果仍然都不是基本可行解，按上面的方法繼續(xù)做下去，最后一定可以找到一個基本可行解，且目標函數(shù)值等于。7/16/20241.4線性規(guī)劃的基本原理521.5單純形法單純形法的基本思路：從一個初始的基本可行解出發(fā)，經過判斷，如果是最優(yōu)解，則結束；否則經過基變換得到另一個改善的基本可行解，如此一直進行下去，直到找到最優(yōu)解。(1)

確定初始基本可行解(2)從一個基本可行解轉換到相鄰的基本可行解(3)最優(yōu)性檢驗和解的判別7/16/20241.5.1迭代原理54(1)

確定初始基本可行解一般約束條件的變量系數(shù)矩陣中總會存在一個單位矩陣：7/16/20241.5.1迭代原理55(2)從一個基本可行解轉換到相鄰的基本可行解僅變換一個基變量P1P2…PmPm+1…Pj…Pnb7/16/20241.5.1迭代原理56P1P2…Pl-1PjPl+1…PmbPlPj進行初等變換形成單位矩陣(2)從一個基本可行解轉換到相鄰的基本可行解7/16/20241.5.1迭代原理57(3)最優(yōu)性檢驗和解的判別將基本可行解和分別代入目標函數(shù)得：>0≤

0

>07/16/20241.5.1迭代原理58單純形法的基本思路：從一個初始的基本可行解出發(fā)，經過判斷，如果是最優(yōu)解，則結束，否則經過基變換得到另一個改善的基本可行解，如此一直進行下去，直到找到最優(yōu)解。第1步：求初始基可行解，列出初始單純形表。第2步：最優(yōu)性檢驗。第3步：從一個基可行解轉換到相鄰的目標函數(shù)值更大的基可行解，列出新的單純形表。第4步：重復第2、3步，一直到計算結束為止。7/16/20241.5.2迭代步驟59非標準形的LP問題標準的LP問題設法使約束方程的系數(shù)矩陣中包含一個單位陣以此作為基求出問題的一個初始基可行解為了書寫規(guī)范和便于計算，對單純形的計算有一種專門的表格，稱為單純形表。

含初始基可行解的單純形表

——初始單純形表

含最優(yōu)解的單純形表

——最終單純形表第1步-求初始基可行解，列出初始單純形表7/16/20241.5.2迭代步驟60

cj

c1…cm…cj…cnCB

基b

x1…

xm

…

xj

…

xn

c1

x1b1

c2

x2

b2

：：：：：：

cm

xm

bm10…a1j…a1n00…a2j…a2n

：：：：

：：

：：01…amj

…amn

cj

-zj0…0……基變量基變量的取值檢驗數(shù)σj第1步-求初始基可行解，列出初始單純形表7/16/20241.5.2迭代步驟61

cj

c1…cm…cj…cnCB

基b

x1…

xm

…

xj

…

xn

c1

x1b1

c2

x2

b2

：：：：：：

cm

xm

bm10…a1j…a1n00…a2j…a2n

：：：：

：：

：：01…amj

…amncj-zj0…0……所有檢驗數(shù)≤0，且基變量中不含人工變量時，即為最優(yōu)解。當表中存在

cj–zj＞0時，如有

Pj≤0，則問題為無界解。如果都不是，下一步……第2步–最優(yōu)性檢驗1.5.2迭代步驟062確定換入變量和換出變量第3步–換基，使目標函數(shù)值更大換入變量=進基變量=EnteringVariable根據(jù)，確定xk為換入變量換出變量=出基變量=LeavingVariable按

規(guī)則計算，可確定xl為換出變量7/16/20241.5.2迭代步驟637/16/20241.5.2迭代步驟以

alk

為主元素(pivotnumber)進行迭代，得到新的單純形表。第3步–換基，使目標函數(shù)值更大旋轉運算Pivoting64

cj

c1…cl…cm…

cj…ck…CB

基b

x1…

xl

…

xm

…

xj

…

xk…

c1

x1b1：：：

ck

xk：：：

cm

xm

bm1…0…

…0…：：：：：0…0

…

…1…

：：

：：：0…1

…

…0…cj-zj0……0……0…1.5.2迭代步驟第3步–換基，使目標函數(shù)值更大旋轉運算Pivoting065例1.4

用單純形法求解線性規(guī)劃問題maxz=40x1+50x2

x1+2x2

30

3x1+2x2

60

2x2

24x1,x20s.t.第4步–重復2、3步，直到計算結束7/16/20241.5.2迭代步驟66解：首先將上述問題化為標準型：1.5.2迭代步驟7/16/202467單純法求解cBxBbx1x2x3x4x54050000x3x4x500030602413022210001000104050000-z

153012初始單純形表重新計算檢驗數(shù)，結果如下頁檢驗數(shù)判別換基迭代非基變量檢驗數(shù)為計算

06850122x2501121/2036-106-11.5.2迭代步驟cBxBbx1x2x3x4x54050000x3x4001201010-1-11/2400-25-z

06

12--第2單純形表00336101x25060-840計算

非基變量檢驗數(shù)為檢驗數(shù)判別06904061x14011018-32000-4015第3單純形表-400701.5.2迭代步驟cBxBbx1x2x3x4x54050000x3x4012110-11/20-z

第3單純形表00x25060-840檢驗數(shù)判別0700x1401018-32000-4015-400700x59-3/211/2015-1/211/2015/23/4-1/4-35/2-15/20-975檢驗數(shù)全非正,已經取得最優(yōu)解,最優(yōu)解為:X*=(15,15/2,0,0,9)TZ*=975最終單純形表FinalSimplextableau1.5.2迭代步驟1.6單純形法的進一步討論前面的例子中，化為標準形式后約束條件的系數(shù)矩陣都含有單位矩陣，可以作為初始可行基。如果化為標準形式的約束條件的系數(shù)矩陣中不存在單位矩陣呢？如何建立初始單純形表？例1.5:maxz=x1+2x2+x3

x1+4x2-2x3

120x1+x2+x3=60x1

,x2,x30s.t.7/16/20241.6單純形法的進一步討論72maxz=x1+2x2+x3x1+4x2-2x3-x4

=

120x1+x2+x3

=60x1

,x2,x3,x4

0s.t.可以添加兩列單位向量P5

，P6，構成單位矩陣。maxz=x1+2x2+x3-Mx5

-Mx6x1+4x2-2x3-x4+x5

=

120x1+x2+x3

+x6

=

60x1,x2,x3,x4,

x5,x6

0s.t.人工變量-M罰因子7/16/20241.6.1人工變量法–大M法73

12

10-M

-M

CBXB

b

x1x2x3x4x5x6

2

x2

601

1

10010

x4

120306

1-14-10-100-2-M最終單純形表:7/16/20241.6.1人工變量法–大M法747/16/20241.6.1人工變量法–兩階段法大M是一個很大的數(shù),但計算機處理時取多大呢?兩階段法不用確定M具體值，可用于計算機求解。第一階段：先求解一個目標函數(shù)中只包含人工變量的

線性規(guī)劃問題，判斷其有否可行解：-當人工變量取值為0時，這時的最優(yōu)解就是原線性規(guī)劃問題的

一個基可行解；-如果最優(yōu)解的基變量中含有非零的人工變量，則原線性規(guī)劃問題

無可行解。第二階段：有可行解時去掉人工變量再求解。757/16/20241.6.1人工變量法–兩階段法maxz=x1+2x2+x3x1+4x2-2x3-x4

=

120x1+x2+x3

=60x1

,x2,x3,x4

0s.t.x1+4x2-2x3-x4+x5

=

120x1+x2+x3

+x6

=

60x1,x2,x3,x4,

x5,x6

0s.t.maxz=x1+2x2+x3-Mx5

-Mx676第一階段的線性規(guī)劃問題：minz=x5

+x6x1+4x2-2x3-x4+x5

=

120x1+x2+x3+x6

=

60x1,x2,x3,x4,

x5,x60s.t.第二階段去除人工變量，目標函數(shù)回歸到：maxz=x1+2x2+x3(maxz=-x5

-x6

)maxz=x1+2x2+x3-Mx5-Mx6從第一個階段的最后一張單純形表出發(fā)，繼續(xù)用單純形法計算。1.6.1人工變量法–兩階段法077例1.6:maxz=2x1+x2x1+x2

22x1+2x2

6x1,x20s.t.maxz=2x1+x2+0x3+0x4-Mx5x1+x2+x3

=

22x1+2x2-x4

+x5

=

6x1,x2,x3,x4,

x50s.t.判定無解條件:

當進行到最優(yōu)表時，仍有人工變量在基中，且≠0，則說明原問題無可行解。7/16/20241.6.2無可行解78

2100-MCBXB

b

x1x2x3x4x50

x3211100-M

x56220-11cj-zj2+2M1+2M0-M02x1211100-Mx5200-2-11cj-zj0-1-2-2M-M07/16/20241.6.2無可行解79例1.7：maxz=4x1+x2-x1+x2

2x1–4x2

4x1–2x2

8x1,x20-x1+x2+x3

=2x1–4x2+x4

=

4x1–

2x2+x5

=

8x1,…,x50—當表中存在

cj–zj

＞0時有Pj≤0，則問題為無界解。7/16/20240801.6.3無界解7/16/202480

41000

CBXB

b

x1x2x3x4x50

x32-111000

x441-40100x581-2001

0410007/16/20240811.6.3無界解7/16/202481

41000

CBXB

b

x1x2x3x4x50x360-31104x141-40100x54020-11160170-400

x312001-1/23/24

x112100-121

x22010-1/21/2500009/2-17/21.6.3無界解082本問題無界。x1x2OZ=00831.6.3無界解—當所有檢驗數(shù)時，對某個非基變量xj

有cj-zj=0，且可以找到。—這表明可以找到另一個頂點（基可行解），其目標函數(shù)值也到達最大。—由于可行域為凸集，所以該兩點連線上的點也屬于可行域，且目標函數(shù)值相等。即有無窮多解?！绻蟹腔兞康?，則LP問題唯一解。7/16/20241.6.4無窮多最優(yōu)解84例1.8:

maxz=40x1+80x2x1+2x2

30

3x1+2x2

60

2x2

24

x1,x20x1+2x2+x3

=

303x1+2x2

+x4

=

602x2+x5=

24

x1…x507/16/20241.6.4無窮多最優(yōu)解85

4080000CBXBbx1x2x3x4x50x3

30121000x4603

2

0100x5240

2001040800000x361010-10

x4

363

0

01-180x2

12

01001/2(接下表)

40000-400861.6.4無窮多最優(yōu)解

4080000CBXBbx1x2x3x4x5

40x161

010-10x4

1800-31280x21201001/2120000-400040x11510-1/21/200x5

900-3/21/2180x215/2

0

13/4-1/40

120000-40000871.6.4無窮多最優(yōu)解X(1)=(6,12)Z(1)=1200X(2)=(15,15/2)Z(2)=1200無窮多解全部解：X=α+(1-α)

(0

α1)6151215/27/16/20241.6.4無窮多最優(yōu)解88退化解：—有時存在兩個以上相同的最小值，從而使下一個表的基可行解中出現(xiàn)一個或多個基變量等于零的退化解。7/16/20241.6.5退化和循環(huán)89例:maxz=10x1+

12x23x1+4x2

64x1+x2

23x1+2x2

3x1,x203x1+4x2+x3

=64x1+x2+x4

=

23x1+2x2+x5

=

3x1…x507/16/20241.6.5退化和循環(huán)90

1012000XBb

x1x2x3x4x5θi

0

x36341003/20x42410102/10x53320013/20101200012x23/23/411/40020x41/213/40-1/4102/130x50

3/20-1/20101810-30012x23/2011/20-1/20x41/2005/61-13/610x1010-1/302/3

1800-8/30-2/3

()()

1.6.5退化和循環(huán)退化解zmax=18x*

=(0,3/2,0,1/2,0)T但是，退化解情形有可能出現(xiàn)迭代計算的死循環(huán)！7/16/20241.6.5退化和循環(huán)92死循環(huán)的例子：1.6.5退化和循環(huán)093和初始基可行解相同1.6.5退化和循環(huán)094—為避免出現(xiàn)計算循環(huán)，可采用Bland(1974)準則:(1)當存在多個時，始終選取下標值為最小的變量作為換入變量；(2)當計算

θ值出現(xiàn)兩個或以上相同的最小比值時，始終選取下標值為最小的變量作為換出變量；7/16/20241.6.5退化和循環(huán)95前例中，在第5張表時我們運用Bland法則，得：7/16/20241.6.5退化和循環(huán)961.7應用舉例7/16/20241.7應用舉例

(1)要求解問題的目標能用數(shù)值指標來表示，并且目標函數(shù)z=f(x)為線性函數(shù)；

(2)存在著多種可選方案；

(3)要達到的目標是在一定約束條件下實現(xiàn)的,這些約束條件可用線性等式或不等式來描述。一般來講，一個經濟、管理問題凡滿足以下條件時，才能建立線性規(guī)劃的模型。下面舉例說明線性規(guī)劃在經濟管理等方面的應用。98

7/16/20241.7.1風險控制問題997/16/20241.7.1風險控制問題該問題可以表述為如下的線性規(guī)劃模型：

1007/16/20241.7.1風險控制問題目標函數(shù)是帶有絕對值的特殊線性規(guī)劃問題，如何將其轉換成一般的線性規(guī)劃模型呢？

101例1.11某工廠生產三種不同型號的潤滑油A，B和C，表1.28是工廠剛剛接到的一季度生產訂單。已知每月生產三種潤滑油的單位成本如表1.29所示，生產單位潤滑油所需的工時分別為1，0.8和1.5（小時/噸）。該工廠每個月的最大生產能力均為900（小時）。若生產出來的潤滑油當月不交貨，每噸庫存1個月的存儲費分別為220，200和160元。請為該廠設計一個既保證完成訂單，又使一季度生產和庫存總成本最低的生產計劃。7/16/20241.7.2生產庫存問題102表1.28一季度生產訂單（單位：噸）7/16/20241.7.2生產庫存問題表1.29一季度單位生產成本（單位：元/噸）103

目標函數(shù)：總成本由生產成本和庫存成本兩部分構成：7/16/20241.7.2生產庫存問題

104約束條件：工時約束——各個月生產工時均不超過最大生產能力：交貨要求——各個月足以完成訂單需求即每月庫存量不小于0，于是有：非負約束——決策變量為生產產品的數(shù)量，因此是非負的，即7/16/20241.7.2生產庫存問題

105某工廠生產一型號的機床，每臺機床上分別需用2.9、2.1、1.5米長的軸1根、2根和1根，這些軸需用同一種圓鋼制作，圓鋼的長度為7.4米。如需要生產100臺機床，問應如何安排下料，才能使用料最??？試建立其線性規(guī)劃模型。B1B2B3B4B5B6B7B8需要量2.9m2.1m1.5m余料10302010.10220.21200.30130.81110.90301.10041.4100200100最少7/16/20241.7.3合理下料問題106解：設x1,x2,x3,x4,x5

分別為上面前

5種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學模型。

目標函數(shù)：

minx1+x2+x3+x4+x5

約束條件：

s.t.

x1+2x2+x4≥1002x3+2x4+x5≥2003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0必須為整數(shù)！7/16/20241.7.3合理下料問題107某部門在五年內考慮給下列項目投資：項目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115％。項目B：從第三年初需投資，到第五年末能回收本利125％，但規(guī)定最大投資額不超過4萬元。項目C：第二年初需要投資，到第五年末能回收本利140％，但規(guī)定最大投資額不超過3萬元。項目D：五年內每年初可購買公債于當年末歸還并加利息6％。該部門現(xiàn)有資金10萬元，問應如何確定給這些項目每年的投資額，使到第五年末擁有的資金本利總額最大。

7/16/20241.7.4組合投資問題1087/16/20241.7.4組合投資問題確定變量：

以XiA,XiB,XiC,XiD(i=1,2,3,4,5)分別表示第

i年年初給項目A,B,C,D的投資額。具體列于下表：第1年第2年第3年第4年第5年ABCDX1AX1DX2AX2CX2DX3AX3BX3DX4