中國礦業(yè)大學管理運籌學教學教案第一課時線性規(guī)劃地基本問題

管理運籌學中國礦業(yè)大學管理學院2006年9月O.R.

任課教師：王新宇，副教授，博士單位：管理學院－管理科學與工程系Email：wxy_cumt@163.comTel(home)理運籌學教學公用信箱

用戶：orteaching@163.com密碼:123456供網上答疑、資料分發(fā)收集、平時交流使用，歡迎各位同學使用，密碼勿改！試題結構：選擇，15分填空，10分計算題，75分課程的最終成績：考試：70~80％平時作業(yè)和出席率20~10％實驗報告10％課程要求：認真聽課獨立完成作業(yè)不允許無故缺席上課保持安靜歡迎提問一、運籌學的起源與發(fā)展起源于二次大戰(zhàn)的一門新興交叉學科與作戰(zhàn)問題相關如雷達的設置、運輸船隊的護航、反潛作戰(zhàn)中深水炸彈的深度、飛行員的編組、軍事物資的存儲等英國稱為OperationalResearch美國稱為OperationsResearch戰(zhàn)后在經濟、管理和機關學校及科研單位繼續(xù)研究1952年，Morse和Kimball出版《運籌學方法》1948年英國首先成立運籌學會1952年美國成立運籌學會1959年成立國際運籌學聯(lián)合會(IFORS)我國于1982年加入IFORS，并于1999年8月組織了第15屆大會二、運籌學的特點及研究對象運籌學的定義為決策機構對所控制的業(yè)務活動作決策時，提供以數量為基礎的科學方法——Morse和Kimball運籌學是把科學方法應用在指導人員、工商企業(yè)、政府和國防等方面解決發(fā)生的各種問題，其方法是發(fā)展一個科學的系統(tǒng)模式，并運用這種模式預測，比較各種決策及其產生的后果，以幫助主管人員科學地決定工作方針和政策——英國運籌學會運籌學是應用分析、試驗、量化的方法對經濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有根據的最優(yōu)方案，以實現(xiàn)最有效的管理——中國百科全書現(xiàn)代運籌學涵蓋了一切領域的管理與優(yōu)化問題，稱為ManagementScience三、運籌學的特點及研究對象運籌學的分支數學規(guī)劃：線性規(guī)劃、非線性規(guī)劃、整數規(guī)劃、動態(tài)規(guī)劃、目標規(guī)劃等圖論與網路理論隨機服務理論：排隊論存儲理論決策理論對策論系統(tǒng)仿真：隨機模擬技術、系統(tǒng)動力學可靠性理論金融工程四、運籌學解決問題的方法步驟明確問題建立模型設計算法整理數據求解模型評價結果明確問題建立模型設計算法整理數據求解模型評價結果簡化？滿意？YesNoNo五、運籌學的發(fā)展趨勢運籌學的危機脫離實際應用，陷入數學陷阱IT對運籌學的影響MIS,DSS,MRP-II,CIMS,ERPORDept.-->Dept.OfOR&IS運籌學與行為科學結合群決策和談判對策理論多層規(guī)劃合理性分析服務行業(yè)中的應用金融服務業(yè)信息、電信服務業(yè)醫(yī)院管理四、運籌學的發(fā)展趨勢軟計算面向強復雜系統(tǒng)的計算、實時控制、知識推理智能算法：模擬退火、遺傳算法、人工神經網絡、戒律算法等系統(tǒng)仿真面向問題后勤(Logistics)全球供應鏈管理電子商務：集成特性隨機和模糊OR問題本身的不確定性人類知識的局限性目錄第一章線性規(guī)劃的基本問題第二章線性規(guī)劃的對偶問題與靈敏度分析第三章目標規(guī)劃與整數規(guī)劃第四章非線性規(guī)劃第五章動態(tài)規(guī)劃第六章矩陣對策第七章圖與網絡第八章網絡計劃技術(統(tǒng)籌法)第九章存儲論第十章決策論OR第一章線性規(guī)劃的基本問題(Linearprogramming)1.1線性規(guī)劃問題及其數學模型1.1.1線性規(guī)劃問題

(1)給定了一定數量的資源，研究如何運用這些資源使完成的任務最多。

(2)給定了一項任務，研究如何統(tǒng)籌安排使消耗的資源最少。LP例：生產計劃問題問如何安排生產可獲得最大收益？設：x1、x2分別為甲、乙兩種產品的產量，Z為總利潤，則

Z（X）=4x1+5x2約束條件非負約束目標函數2x1+x2

x1，x2≥0≤45≤

90≤80

x1+x2

x1+3x2

MaxLP例2：配料問題設：x1、x2分別為甲、乙兩種金屬的含量，Z為總成本特征：（1）存在一組決策變量(decisionvariable)

（2）存在若干約束條件(≤,=或≥)(constraints)

（3）一個目標函數“max”“min”(objectivefunction)

Z（X）=2x1+5x2約束條件

非負約束目標函數

x2

x1，x2≥0≤0.06=1≥

0.92

x1

x1+x2

MinLP其中：（2）和（3）中各決策變量之間的關系均為線性關系。1.1.2線性規(guī)劃數學模型的一般形式

Max(Min)Z（X）=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1n

xn

≤(=,≥)b1a21x1+a22x2+…+a2n

xn

≤(=,≥)b2…………..am1x1+am2x2+…+amn

xn

≤(=,≥)bm

x1，x2，…，xn≥0

LP

Max(Min)Z（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1n

xn

≤(=,≥)b1a21x1+a22x2+…+a2n

xn

≤(=,≥)b2…………..am1x1+am2x2+…+amn

xn

≤(=,≥)bm

x1，x2，…，xn≥0

1.1.3線性規(guī)劃數學模型的標準型

MaxZ（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1n

xn=b1a21x1+a22x2+…+a2n

xn=b2……………..am1x1+am2x2+…+amn

xn=bm

x1，x2，…，xn≥0LP1.1.3線性規(guī)劃數學模型的標準型

MaxZ（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1n

xn=b1a21x1+a22x2+…+a2n

xn=b2……………..am1x1+am2x2+…+amn

xn=bm

x1，x2，…，xn≥0標準型特征（1）決策變量均為非負變量（2）所有約束條件都是“=”型（3）目標函數為“Max”型（4）常數項bi(i=1,2,…,n)≥0標準型形式縮寫（1）一般形式（2）向量形式（3）矩陣形式LP（1）一般形式MaxZ（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1n

xn=b1a21x1+a22x2+…+a2n

xn=b2……………..am1x1+am2x2+…+amn

xn=bm

x1，x2，…，xn≥0Σa1jxj=b1

Σa2jxj=b2

Σamjxj=bm

nΣaijxj=bij=1xj≥0(i=1,2,…,m)

nMax(Z)=Σcjxjj=1(j=1,2,…,n)St:LPMaxZ（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1n

xn=b1a21x1+a22x2+…+a2n

xn=b2……………..am1x1+am2x2+…+amn

xn=bm

x1，x2，…，xn≥0a11a21…am1a12a22…am2a1na2n…amnx1+x2+xn

=b1b2…bm…+（2）向量形式

MaxZ(X)=CX

nΣpjxj=bj=1xj≥0(j=1,2,…,n)LPa1ja2j…amj=pj令（3）矩陣形式

MaxZ（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1n

xn=b1a21x1+a22x2+…+a2n

xn=b2……………..am1x1+am2x2+…+amn

xn=bm

x1，x2，…，xn≥0Max(Z)=CXAX=b

a11a12…a1n

a21a22…a2n

……………am1am2…amnx1x2…xnb1b2

…bm=X≥0

LP線性規(guī)劃數學模型的一般形式線性規(guī)劃數學模型的標準型（1）一般形式

nΣaijxj=bij=1xj≥0(i=1,2,…,m)

nMax(Z)=Σcjxjj=1(j=1,2,…,n)St:（2）向量形式

MaxZ(X)=CX

nΣpjxj=bj=1xj≥0(j=1,2,…,n)Max(Z)=CXAX=bX≥0

（3）矩陣形式St:St:LP1.1.4線性規(guī)劃的標準化問題目標函數為“Min”型

MinZ=CXΣaijxj

≤bi這時xn+i稱為松弛變量Σaijxj

+xn+i

=biΣaijxj

≥bi這時xn+i稱為剩余變量也可統(tǒng)稱為松弛變量Σaijxj

-xn+i=bi決策變量xi無非負約束(1)(2)令：Z/=-Z1.1.4.2約束條件為“≤”則：Max(-Z)=-CX或“≥”型令：xi

=xi/

-xi//（其中xi/

、xi//≥0

）代入原問題LP例：將下列線性規(guī)劃模型化成標準型

MinZ（X）=3x1-x2+3x3

x1+x2+x3≤6x1+x2-x3≥2-3x1+2x2+x3=5x1，x2≥0

其標準型如下：

Max[-Z（X）]=-3x1+x2-3x3/+3x3//x1+x2+x3/

-x3//+x4x1+x2-x3/

+x3//-x5-3x1+2x2+x3/

-x3//

=5x1，x2,x3/

,

x3//

,

x4,

x5≥0=6=2+0x4+0x5LP1.2線性規(guī)劃的解標準型

MaxZ（X）=c1x1+c2x2+…+cnxn

(1-1)a11x1+a12x2+…+a1n

xn=b1a21x1+a22x2+…+a2n

xn=b2……………..am1x1+am2x2+…+amn

xn=bm

(1-2)x1，x2，…，xn≥0(1-3)

線性規(guī)劃的可行解(Feasiblesolotion)

滿足約束條件(1-2)，(1-3)的解

X=（x1，x2，…，xn）稱為線性規(guī)劃問題的可行解。線性規(guī)劃的最優(yōu)解(Optimalsolution)

滿足約束條件(1-1)的可行解

X*=（x1*，x2*，…，xn*）稱為線性規(guī)劃問題的最優(yōu)解。LP線性規(guī)劃的基若A為線性方程組（1-2）的mn階系數矩陣，其秩為m，則A中任意m個線性無關的列向量構成的mm階子矩陣,稱為該線性規(guī)劃的一個基，記為B。顯然基矩陣的行列式不等于零。例：232003110233=（P1，P2，P3，P4）x1,x2,x3,x4A=320311233=（P2，P3，P4）

x2,x3,x4若：B=為基向量為基變量LP(1)基向量：組成基矩陣的m個列向量稱為基向量。(2)非基向量：其余的n-m個列向量稱為非基向量。(3)基變量：與基向量相對應的m個變量稱為基變量。(4)非基變量：其余的n-m個變量稱為非基變量。線性規(guī)劃的基本解a11x1+…+a1mxm+a1m+1xm+1+…+a1n

xn=b1a21x1+…+a2mxm+a2m+1xm+1+…+a2n

xn=b2……………am1x1+…+ammxm+amm+1xm+1+…+amn

xn=bm

LPa11x1+…+a1mxm=b1a21x1+…+a2mxm=b2………..

am1x1+…+ammxm=bm

若：x1，x2，…，xm為基變量；令n-m個非基變量xm+1=xm+2=…=xn=0再由方程組:解出基變量x*1，x*2，…，x*m的值,則解向量:

X*=(x*1，x*2，…，x*m,0,…,0)稱之為對應一個基的基本解。a11x1+…+a1mxm+a1m+1xm+1+…+a1n

xn=b1a21x1+…+a2mxm+a2m+1xm+1+…+a2n

xn=b2……………am1x1+…+ammxm+amm+1xm+1+…+amn

xn=bm

a12x2+…+a1mxm+a1m+1xm+1=b1a22x2+…+a2mxm+a1m+1xm+1=b2………………..

am2x2+…+ammxm

+a1m+1xm+1=bm

若：x2，…，xm

，xm+1為基變量；令n-m個非基變量x1=xm+2=…=xn=0由方程組:解出基變量x*2，…，x*m，x*m+1的值,則解向量:

X*=(0，x*2，…，x*m,x*m+10,…,0)稱之為對應一個基的基本解。LP根據基本解的定義不難得出以下結論：

線性規(guī)劃的基本解不是唯一的，它與線性規(guī)劃的基一一對應，個數不超過Cnm。LP線性規(guī)劃的基本可行解滿足非負條件（1-3）的基本解稱為基本可行解；對應于基本可行解的基稱為可行基。圖示：可行解基本可行解基本解方程組的解LP1．2．2線性規(guī)劃的圖解法1．2．2．1一般情形例1:MaxZ（X）=4x1+5x2x1+x2

≤452x1+x2

≤80x1+3x2

≤90x1，x2≥0ADOCBX2X1多邊形OABCD為線性規(guī)劃的可性域，目標函數在C(45/2,45/2)達到最大x1=45/2x2=45/2,Z=405/2454580403090目標:x2=-4/5x1+1/5Z(等值線)Z=0LPADOCBX2X1LPCOADBX2X1LP1．2．2．2特殊情形(1)多重最優(yōu)解例2MaxZ（X）=4x1+4x2x1+x2

≤452x1+x2

≤80x1+3x2

≤90x1，x2≥0DCBAX2X1OR等直線與線段CB平形，線段CB上的任意點均可使目標函數取得相同的最大值，則該規(guī)劃有多重最優(yōu)解LP(2)無最優(yōu)解例3MaxZ（X）=5x1+4x2-4x1+3x2≤3-2x1+4x2≤8x1，x2≥001B可行域無界AX1②①（6/5，13/5）2X2注意；可行域無界，并不意味著目標函數值無界。如果目標函數為:MinZ（X）=5x1+4x2LP01B可行域無界AX1②①（6/5，13/5）2X2LP01B可行域無界AX1②①（6/5，13/5）2X2唯一最優(yōu)解無界可行域無窮多最優(yōu)解無最優(yōu)解LP(3)無可行解7例4

MaxZ（X）=x1+2x2

x1+x2≤510x1+7x2≥70x1，x2≥0無可行域（解）X10X25510有界可行域無界可行域無可行域唯一最優(yōu)解無窮多最優(yōu)解無最優(yōu)解無可行解LP有界可行域無界可行域無可行域唯一最優(yōu)解無窮多最優(yōu)解無最優(yōu)解無可行解LP1．2．3線性規(guī)劃解的基本性質

(1)滿足線性規(guī)劃約束條件的可行解集（可行域）構成一個凸多邊形。(2)凸多邊形的頂點（極點）與基本可行解一一對應（即一個基本可行解對應一個頂點）。(3)線性規(guī)劃問題若有最優(yōu)解，則最優(yōu)解一定在凸多邊形的某個頂點上取得。由（2）和（3）可得如下結論：線性規(guī)劃問題若有最優(yōu)解，則最優(yōu)解一定是某個基本可行解。LPADOCBX2X1

MaxZ（X）=4x1+5x2+0x3+0x4+0x5x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0

x2=0x1=0x3=0x4=0x5=0LP107*60*60*24*365=31536*1010<1015確定初始基本可行解X(k)k=0

檢驗X(k)是否最優(yōu)轉換到另一個基本可行解X(k+1)

并使Z(X(k+1))>Z(X(k))NY停1．3單純形法1．3．1單純形法的基本思路LP例1MaxZ（X）=4x1+5x2x1+x2≤452x1+x2≤80x1+3x2≤90x1，x2≥0將上式化為標準形式

MaxZ（X）=4x1+5x2+0x3+0x4+0x5x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0

(1)確定初始的基本可行解

X（0）=（0，0，45，80，90）Tx3為第1種資源的剩余量x4為第2種資源的剩余量x5為第3種資源的剩余量LP(2)檢驗將X（0）代入目標函數，即

MaxZ（X（0））=4x1+5x2+0x3+0x4+0x5=0

由于非基變量x1、x2的系數都>0,所以X（0）不是最優(yōu)解。(3)基變換確定進基變量:x2的系數>x1的系數,∴x2進基變量確定退出變量：分析：

x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0

LP

x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0

注意x1仍然為0如果：x3=0x2=45/1

X（1）=（0，45，0，35，-45）

x4=0x2=80/1

X（1）=（0，80，-35，0，-150）

x5=0x2=90/3

X（1）=（0，30，15，50，0）分析：LP

x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90

x2=θ=min{45/1,80/1,90/3}=30

當x2由0變到30時，x5首先變?yōu)?，故x5為退出基變量。變換方程，求新的基本可行解

X（1）=（0，30，15，50，0）T（4）返回（2）檢驗

Z（X（1））=4x1+5(30-1/3x1-1/3x5)=150+7/3x1-5/3x5

因7/3>0，故X（1）仍不滿足最優(yōu)性條件，繼續(xù)進行轉換（5）返回（3）基變換確定進基變量為x1

確定退出變量2/3x1+x3-1/3x5=155/3x1+x4-1/3x5=501/3x1+x2+1/3x5=30x1=θ=min{45/2,30,90}=45/2當x1由0變到45/2時，x3首先變?yōu)?，故x3為退出基變量。LP2/3x1+x3-1/3x5=155/3x1+x4-1/3x5=501/3x1+x2+1/3x5=30x1+3/2x3-1/2x5=45/2-5/2x3+x4+1/2x5=25/2

x2-1/2x3+1/2x5=45/2求新的基本可行解當x1由0變到45/2時，x3首先變?yōu)?，故x3為退出基變量。LP求新的基本可行解x1+3/2x3-1/2x5=45/2-5/2x3+x4+1/2x5=25/2x2-1/2x3+1/2x5=45/2

X（2）=（45/245/2025/20）T

返回（2）繼續(xù)檢驗

Z（X（2））=4(45/2-3/2x3+1/2x5)+5(45/2+1/2x3-1/2x5)=405/2-7/2x3-1/2x5

所有非基變量的檢驗數均≤0，問題已獲得最優(yōu)解。

X*=X（2）=（45/245/2025/20）TZ（X*）=405/2LP第一步：尋找初始基本可行解第三步：換基迭代（2）確定出基變量：（2）確定出基變量：三、換基迭代在第4個方程五、循環(huán)迭代：單純形原理的矩陣描述設標準的線性規(guī)劃問題為

min z= CTX s.t. AX=b X0矩陣A可以分塊記為A=[B，N]

相應地，向量X和C可以記為

AX=b可以寫成

BXB+NXN=b即

XB=B-1b-B-1NXN

對于一個確定的基B，目標函數z可以寫成目標函數z用非基變量表出的形式單純形表的結構

左端同乘B-111100x1x2x3x4x54

50

0

0

21010130014

50

0

0

45

80

90x3x4x50

0

045/180/190/3[]CBxBcjb

MaxZ（X）=4x1+5x2+0x3+0x4+0x5x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0

1．3．2單純形表仍以例1為例LP2/3010-1/330x3x4x20

0

45/230905/3001-1/31/31001/37/3000-5/355015][11100x1x2x3x4x54

50

0

0

21010130014

50

0

0

45

80

90x3x4x50

0

045/180/190/3[]CBxBcjb1233/1/2/3/3=1/31/=3/1+-2/=3/2+-103/20-1/2x1x4x24

0

00-5/211/201-1/201/200-7/20-1/2525/245/21/1//=3/245/22/3010-1/3x1x2x3x4x54

50

0

0

5/3001-1/31/31001/315

50

30x3x4x20

0

5CBxBcjb7/3000-5/345/230903/1/2/[]2//1//3//=2/+-5/32//1//=3/+-1/33//1//≤0=cj-CBPj103/20-1/2x1x4x24

0

00-5/211/201-1/201/200-7/20-1/2525/245/245/22//1//3//≤0=cj-CBPj所有的檢驗數均已小于或等于零，問題已獲得最優(yōu)解

X*=（45/2，45/2，0，25/2，0）TZ=405/2

求解方法—單純形方法maxz=50x1+40x2

s.t.

3x1+5x2≤150

x2≤20

8x1+5x2≤300

x1,x2≥0標準化maxz=50x1+40x2

s.t.

3x1+5x2＋x3

=150(1)

x2

+x4

=20(2)

8x1+5x2

+x5=300(3)

x1,x2,x3,x4,x5≥0

單純形表（初始）

B1=(P3,P4,P5)=I當前基本可行解：(0,0,150,20,300),Z=0當前基本可行解：(75/2,0,75/2,20,0),Z=1875B2=(P3,P4,P1)=當前基本可行解：(30,12,0,8,0),Z=1980達到最優(yōu)解B3=(P2,P4,P1)=轉換關系思考：對于特殊的線性規(guī)劃問題，如有多重最優(yōu)解，及無最優(yōu)解時，如何從單純形表中獲得有關信息？例2MaxZ（X）=4x1+4x2+0x3+0x4+0x5x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0單純形表：LP11100x1x2x3x4x54

40

0

0

21010130014

40

0

0

45

80

90x3x4x50

0

045/180/290CBxBcjb[]=cj-CBPj多重解01/21-1/2050x3x1x50

4

10802011/201/2005/20-1/21020-200405][11100x1x2x3x4x54

40

0

0

21010130014

40

0

0

45

80

90x3x4x50

0

045/180/290[]CBxBcjb=cj-CBPj012-1025x2x1x54

4

3525/210-11000-52100-40003510][=cj-CBPj01/21-1/2050x3x1x50

4

10802011/201/2005/20-1/21020-200405][=cj-CBPj所有的檢驗數均小于或等于零，最優(yōu)解：

X1*=（35，10，0，0，25）T非基變量x4的檢驗數為0，表明該規(guī)劃有無限多最優(yōu)解,繼續(xù)迭代求出另一個最優(yōu)(基本可行)解?！?ADOCBX2X1

MaxZ（X）=4x1+5x2+0x3+0x4+0x5x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0

x2=0x1=0x3=0x4=0x5=0LP012-1025x2x1x54

4

3525/210-11000-52100-40003510][=cj-CBPj’≤001-1/201/2x2x1x44

4

103/20-1/200-5/211/200-400045/2=cj-CBPj≤045/225/2X2*=（45/2，45/2，0，25/2，0）T

X*=aX1*+(1-a)X2*

（0<=a<=1）

Z(X*)=180本題說明：1、最優(yōu)解不唯一，但最優(yōu)值唯一3、在實際應用中，有多種方案可供選擇例3MaxZ（X）=5x1+4x2+0x3+0x4-4x1+3x2+x3=3-2x1+4x2+x4=8x1,…,x4≥0無最優(yōu)解[]LP令：x1=M>0(任意大)，x2=0,x3=3+4M,x4=8+2MZ=５Ｍ，可以任意大！??！[][]LP即使繼續(xù)迭代計算此問題無最優(yōu)解。[]LP例3MaxZ（X）=5x1+4x2-4x1+3x2≤3-2x1+4x2≤8x1，x2≥001B可行域無界AX1②①（6/5，13/5）2X2LP3、將約束方程化為每個方程只含一個基變量目標函數表示成非基變量的函數

單純形法步驟：1、化標準型

2、選定一個可行基，并得一基本可行解X？5、判斷X是否為最優(yōu)解：若目標函數行中所有檢驗數λi≤0,

則X為最優(yōu)解。若存在某個λ

j>0,且所有的aij<0，則不存在有界最優(yōu)解。否則轉下一步4、做單純形表6、換基迭代（1）入基變量：設λ

k=max{λ

i|λ

i>0},取xk為入基變量（2）出基變量：

7、對單純形表做初等行變換：把基變量對應的列化為單位向量，目標函數的基變量系數化為零，得一新的基本可行解X。轉第4步例題：人員安排問題醫(yī)院護士24小時值班，每次值班8小時。不同時段需要的護士人數不等。據統(tǒng)計：

序號時段最少人數安排人數106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6建模:目標函數：minZ=x1+x2+x3+x4+x5+x6約束條件：x1+x2

≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30

x6+x1≥60非負性約束：xj

≥0,j=1,2,…6ＬＩＮＤＯ中一般整型變量的命令是:ＧＩＮ變量名或GIN變量的總數（適用于全部是整型變量）０－１變量的命令是：INTEGER變量名或INTEGER變量的總數（適用于全部是整型變量）1.4人工變量法人為地構造一個單位矩陣來充當初始可行基，再通過單純形迭代將它們逐個地從基變量中替換出來。若經過基的變換，基變量中不再含有非零的人工變量，這表示原問題有解。若在最終表中當所有Cj-zj≤0，而在其中還有某個非零人工變量，這表示無可行解。大M法兩階段法例：MinZ（X）=-3x1+x2+x3x1-2x2+x3≤11-4x1+x2+2x3≥3-2x1+x3=1x1，x2，x3≥0

Max[-Z（X）]=3x1-x2-x3x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1，x2，x3，x4，x5≥0其標準型：（以下稱為模型1，用M1表示）M1+0x4+0x5LP1．4確定初始基本可行解的兩種方法1．4．1大M法

Max[-Z（X）]=3x1-x2-x3+0x4+0x5x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1，x2，x3，x4，x5≥0M1構造新問題M2

Max[-Z（X）]=3x1-x2-x3+0x4+0x5x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1，x2，x3，x4，x5，≥0原理核心：打破原來的約束，再設法恢復。+x7+x6M2-Mx6

-Mx7，x7x6LP基本思想:假定人工變量在基變量中的價值系數為一個絕對值很大的-M(M>>0,對于極小化問題用+M),這樣只要基變量中還存在人工變量,目標函數就不可能實現(xiàn)極值.x1x2x3x4x5x6x711

31x4x6x70

-M

-M11/13/2[]CBxBcjb3-1-100-M-M1

-21

1

0

00-4

12

0

-1

10-2

01

0

0

013-6M

-1+M-1+3M

0

-M

001單純形表:LP

Max[-Z（X）]=3x1-x2-x3+0x4+0x5-Mx6-Mx7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1，x2，x3，x4，x5，x6，x7≥0x1x2x3x4x5x6x711

31x4x6x70

-M

-M11/13/2[]CBxBcjb3-1-111-M-M1

-21

1

0

00-4

12

0

-1

10-2

01

0

0

013-6M

-1+M-1+3M

0

-M

0011x4x6x30

-M

-1[]3

-20

1

0

0-10

10

0

-1

1-2-2

01

0

0

011M-10

0

-M

01-3M11101x4x6x30

-M

-1[]3

-20

1

0

0-10

10

0

-1

1-2-2

01

0

0

011M-10

0

-M

01-3M11109x1x2x33

-1

-11

0

0

1/3

-2/3

2/3-5/30

10

0

-1

1-20

01

2/3

-4/3

4/3-7/3000

-1/3

-1/3

141x2x4x30

-13

00

1

-2

2-50

10

0

-1

1-2-2

01

0

0

01

10

0

0

-1

1-M-M-1-112[]1例4

MaxZ（X）=x1+2x2x1+x2≤510x1+7x2≥70x1，x2≥0[]所有的檢驗數都小于或等于零，但人工變量x5仍未從基變量中退出，這表明原問題無可行解?！?

MaxZ（X）=x1+2x2x1+x2+x3=510x1+7x2-x4=70x1，…，x4≥0+x5-Mx5，x5再例：（LP）Maxz=5x1

+2x2

+3x3

-x4

s.t.x1+

2x2+

3x3=152x1

+x2

+5x3=20

x1

+2x2

+4x3

+x4

=26

x1

,x2

,x3

,x4

≥0Maxz=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)目標值：112/31．4．2兩階段法例：Max[-Z（X）]=-3x1+x2+x3+0x4+0x5x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1，x2，x3，x4，x5≥0第一階段：據給定的問題構造其輔助問題，為原問題求初始基本可行解.輔助問題:

x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1，...，x5≥0+x6+x7x6+x7，x6，x7MinW(X)=LP

x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1，...，x5≥0+x6+x7x6+x7，x6，x7MinW(X)=LP輔助問題最優(yōu)解X=(0,1,1,12,0,0,0)[][]≤0LP第二階段：將第一階段求出的最優(yōu)解，作為第二階段的初始基本可行解，然后在原問題的目標函數下進行優(yōu)化，以決定原問題的最優(yōu)解。

X*=(4,1,9,0,0);Z(X*)=-2≤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兩階段法第一階段問題（LP-1）

Maxz=-x5

-x6s.t.x1+2x2

+3x3

+x5

=152x1

+x2

+5x3

+x6=20

x1

+2x2+4x3

+x4

=26x1,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)目標值：112/3兩階段法計算步驟小結

是否否

是唯一最優(yōu)解LP問題引人松弛變量`人工變量,列出單純形表非基變量檢驗數j≤0對任一j>0有aij≤0令k=max{j}Xk為入基變量對所有aik≥0計算min(θi)

=min(bi/aik)=θ

lXl為出基變量換基迭代1.Xk替代Xl2.對主元行3.對主元列4.對其它行列變換無最優(yōu)解無可行解基變量含有非零人工變量非基變量檢驗數為零多重最優(yōu)解打印結果結束是是注意：單純形法中1、每一步運算只能用矩陣初等行變換；2、表中第3列(b列)的數總應保持非負（≥0）；3、當所有檢驗數均非正（≤0）時，得到最優(yōu)單純形表。若直接對目標求最h，要求所有檢驗數均非負；4、當最優(yōu)單純形表存在非基變量對應的檢驗數為零時，可能存在無窮多解；單純形法注意事項5、關于退化和循環(huán)。如果在一個基本可行解的基變量中至少有一個分量xBi=0(i=1,2,…,m)，則稱此基本可行解是退化的基本可行解。一般情況下，退化的基本可行解（極點）是由若干個不同的基本可行解（極點）在特殊情況下合并成一個基本可行解（極點）而形成的。退化的結構對單純形迭代會造成不利的影響。

可能出現(xiàn)以下情況：①進行進基、出基變換后，雖然改變了基，但沒有改變基本可行解（極點），目標函數當然也不會改進。進行若干次基變換后，才脫離退化基本可行解（極點），進入其他基本可行解（極點）。這種情況會增加迭代次數，使單純形法收斂的速度減慢。②在特殊情況下，退化會出現(xiàn)基的循環(huán)，一旦出現(xiàn)這樣的情況，單純形迭代將永遠停留在同一極點上，因而無法求得最優(yōu)解。

在單純形法求解線性規(guī)劃問題時，一旦出現(xiàn)這種因退化而導致的基的循環(huán)，單純形法就無法求得最優(yōu)解，這是一般單純形法的一個缺陷。但是實際上，盡管退化的結構是經常遇到的，而循環(huán)現(xiàn)象在實際問題中出現(xiàn)得較少。盡管如此，人們還是對如何防止出現(xiàn)循環(huán)作了大量研究。1952年Charnes提出了“攝動法”，1954年Dantzig，Orden和Wolfe又提出了“字典序法”，這些方法都比較復雜，同時也降低了迭代的速度。1976年，Bland提出了一個避免循環(huán)的新方法，其原則十分簡單。僅在選擇進基變量和出基變量時作了以下規(guī)定：①在選擇進基變量時，在所有j

>0的非基變量中選取下標最小的進基；②當有多個變量同時可作為出基變量時，選擇下標最小的那個變量出基。這樣就可以避免出現(xiàn)循環(huán),當然，這樣可能使收斂速度降低。合理利用線材問題：如何下料使用材最少。配料問題：在原料供應量的限制下如何獲取最大利潤。投資問題：從投資項目中選取方案，使投資回報最大。線性規(guī)劃應用建模一、線性規(guī)劃---產品生產計劃：合理利用人力、物力、財力等，使獲利最大。勞動力安排：用最少的勞動力來滿足工作的需要。運輸問題：如何制定調運方案，使總運費最小。數學規(guī)劃的建模有許多共同點，要遵循下列原則：

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

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

(3)容易求解。對線性規(guī)劃來說，容易求解問題主要是控制問題的規(guī)模，包括決策變量的個數和約束條件的個數。這條原則的實現(xiàn)往往會與(1)發(fā)生矛盾，在實現(xiàn)時需要對兩條