第一章線性規(guī)劃與單純形法運籌學教程演示文稿當前第1頁\共有172頁\編于星期五\7點優(yōu)選第一章線性規(guī)劃與單純形法運籌學教程當前第2頁\共有172頁\編于星期五\7點第一節(jié)運籌學釋義和發(fā)展簡史運籌學是一門應用科學，它廣泛應用現(xiàn)有的科學技術知識和數(shù)學方法，解決生產和管理過程中提出的專門問題，為決策者選擇最優(yōu)方案提供定量依據(jù)。運籌學——管理科學用科學（系統(tǒng)化的知識）代替憑經驗的方法當前第3頁\共有172頁\編于星期五\7點1914，戰(zhàn)斗方程1935，Bawdsey雷達站的研究1942，大西洋反潛作戰(zhàn)協(xié)助英國打破德國對英吉利海峽的封鎖：將反潛攻擊由潛艇投擲水雷，改為飛機投擲深水炸彈。起爆深度由100米改為25米。運送物資的船隊及護航艦隊編隊，由小規(guī)模多批次，改為加大規(guī)模，減少批次，這樣損失率將減少當前第4頁\共有172頁\編于星期五\7點當前第5頁\共有172頁\編于星期五\7點當前第6頁\共有172頁\編于星期五\7點141當前第7頁\共有172頁\編于星期五\7點第二節(jié)運籌學研究的基本特征和基本方法基本特征：系統(tǒng)的整體觀念多學科的綜合模型方法的應用研究的基本步驟分析和表述問題建立模型求解模型和優(yōu)化方案測試模型及對模型進行必要的修正建立對解的有效控制方案的實施當前第8頁\共有172頁\編于星期五\7點第三節(jié)運籌學的主要分支線性規(guī)劃非線性規(guī)劃動態(tài)規(guī)劃圖論與網絡分析存儲論排隊論對策論決策論當前第9頁\共有172頁\編于星期五\7點運籌學的主要內容第一章線性規(guī)劃與單純形法第二章對偶理論與靈敏度分析第三章運輸問題第四章目標規(guī)劃第五章整數(shù)規(guī)劃第十章圖與網絡分析第十二章排隊論當前第10頁\共有172頁\編于星期五\7點運籌學學習方法1、課前預習2、認真聽課，適當筆記3、認真作業(yè)運籌學有一定難度，該課程有一定的研究性特征；以線性代數(shù)和概率論為基礎當前第11頁\共有172頁\編于星期五\7點運籌學解決問題的主要程序建立數(shù)學模型（線性規(guī)劃數(shù)學模型）求解數(shù)學模型（圖解法與單純形法）分析求解結果（對偶問題與靈敏度分析）生產問題管理問題當前第12頁\共有172頁\編于星期五\7點第一章線性規(guī)劃與單純形法§1線性規(guī)劃問題及其數(shù)學模型§2線性規(guī)劃問題的幾何意義§3單純形法§4單純形法的計算步驟與表格單純形法§5單純形法的進一步討論§6應用舉例當前第13頁\共有172頁\編于星期五\7點線性規(guī)劃(運籌學)主要解決兩類問題企業(yè)利潤=收入-成本收入由提供產品或服務獲得成本由消耗的資源承擔1、資源有限（獲成本），要求生產的產品獲得的收入（或利潤）最多。12、任務（或產品收入）一定，要求消耗的資源（或成本）最少。2當前第14頁\共有172頁\編于星期五\7點線性規(guī)劃中的兩類數(shù)學模型11、max總收入或總利潤總成本≤b

返回當前第15頁\共有172頁\編于星期五\7點線性規(guī)劃中的兩類數(shù)學模型22、min總成本總收入≥b返回2）表格單純形法當前第16頁\共有172頁\編于星期五\7點

線性規(guī)劃問題的數(shù)學模型線性規(guī)劃的數(shù)學模型的一般形式兩個自變量線性規(guī)劃的圖解法線性規(guī)劃問題的標準形式

線性規(guī)劃問題的解的概念繼續(xù)返回§1線性規(guī)劃問題

及其數(shù)學模型當前第17頁\共有172頁\編于星期五\7點1.1問題的提出線性規(guī)劃是運籌學的一個重要分支。線性規(guī)劃在理論上比較成熟，在實用中的應用日益廣泛與深入。特別是在電子計算機能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領域更為廣泛了。從解決技術問題的最優(yōu)化設計到工業(yè)、農業(yè)、商業(yè)、交通運輸業(yè)、軍事、經濟計劃和管理決策等領域都可以發(fā)揮作用。它已是現(xiàn)代科學管理的重要手段之一。當前第18頁\共有172頁\編于星期五\7點1、線性規(guī)劃問題的提出將生產經營和管理過程中的決策問題

——轉化成數(shù)學模型當前第19頁\共有172頁\編于星期五\7點例1:生產計劃問題(步驟)當前第20頁\共有172頁\編于星期五\7點產品I產品2如何安排生產使利潤最大？當前第21頁\共有172頁\編于星期五\7點是問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。第1步-確定決策變量（設決策變量的原則）設——I的產量——II的產量——利潤當前第22頁\共有172頁\編于星期五\7點第2步--定義目標函數(shù)MaxZ=x1+x2決策變量當前第23頁\共有172頁\編于星期五\7點

MaxZ=2x1+3x2系數(shù)第2步--定義目標函數(shù)當前第24頁\共有172頁\編于星期五\7點對我們有何限制?當前第25頁\共有172頁\編于星期五\7點

x1+2x2

84x1

164x2

12x1、x2

0第3步--表示約束條件當前第26頁\共有172頁\編于星期五\7點該計劃的數(shù)學模型

目標函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

x2當前第27頁\共有172頁\編于星期五\7點決策變量（Decisionvariables）目標函數(shù)（Objectivefunction）約束條件（Constraintconditions）符號約束可行域（Feasibleregion)最優(yōu)解（Optimalsolution)基本概念問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。它是決策變量的函數(shù)指決策變量取值時受到的各種資源條件的限制，通常表達為含決策變量的等式或不等式。滿足約束條件的決策變量的取值范圍可行域中使目標函數(shù)達到最優(yōu)的決策變量的值當前第28頁\共有172頁\編于星期五\7點建立線性規(guī)劃數(shù)學模型的步驟1、選擇適當?shù)臎Q策變量設決策變量的原則2、用決策變量表達目標函數(shù)收入或利潤極大化成本或支出極小化3、用決策變量表達所有的約束條件4、注意變量的符號約束返回當前第29頁\共有172頁\編于星期五\7點例2環(huán)境保護問題當前第30頁\共有172頁\編于星期五\7點

工廠1（工業(yè)污水2萬m3）治污成本1000元/萬m3

500萬m320%自然凈化

200萬m3

工廠2（工業(yè)污水1.4萬m3）

治污成本800元/萬m3

要求污水含量不大于0.2%(步驟)長江嘉陵江朝天門當前第31頁\共有172頁\編于星期五\7點說明從第一化工廠排出的工業(yè)污水流到第二化工廠以前,有20%可以凈化.江水中要求污水含量不大于0.2%.工廠1和工廠2的污水凈化成本分別為1000元/萬m和800元/萬m問每個廠各應處理多少工業(yè)污手,使這兩個工廠總的處理工業(yè)污水費用最小.當前第32頁\共有172頁\編于星期五\7點設：化工廠1每天處理的污水量為x1萬立方米；化工廠2每天處理的污水量為x2萬立方米建模型之前的分析和計算當前第33頁\共有172頁\編于星期五\7點整理得到本問題的數(shù)學模型為：當前第34頁\共有172頁\編于星期五\7點例3合理下料問題書上P38例10原材料，長7.4米一套鋼架任務：100套鋼架目標：成本最少2.9m2.1m1.5m當前第35頁\共有172頁\編于星期五\7點分析下料的方式方式x1x2x3x4x5x6x7x8元鋼ⅠⅡⅢⅣⅤⅥⅦⅧ2.9m211100002.1m021032101.5m10130234余料0.10.30.901.10.40.81.4原材料7.4m2.9m的元鋼不少于100根：2x1+x2+x3+x4≥1002.1m的元鋼不少于100根：2x2+x3+3x5+2x6+x7+x8≥1001.5m的元鋼不少于100根：x1+x3+3x4+x5+2x6+3x7+4x8≥100當前第36頁\共有172頁\編于星期五\7點數(shù)學模型為minz=x1+x2+x3+x4+x5+x6+x7+x82x1+x2+x3+x4≥1002x2+x3+3x5+2x6+x7+x8≥100x1+x3+3x4+x5+2x6+3x7+4x8≥100xj≥0，xj為整數(shù)，j=1,2,…,8能夠求出最優(yōu)解為：x1=10，x2=50，x4=30(最優(yōu)值)minz=90當前第37頁\共有172頁\編于星期五\7點模型建立1、設(未知數(shù))決策變量設按Ⅰ方案下料的原材料根數(shù)為x1,Ⅱ方案為x2，Ⅲ方案為x3，Ⅳ方案為x4,Ⅴ方案為x5，2、用決策變量表達目標函數(shù)minz=0x1+0.1x2+0.2x3+0.3x4+0.8x53、用決策變量表達全部的約束條件4、注意符號約束當前第38頁\共有172頁\編于星期五\7點方式x1x2x3x4x5元鋼ⅠⅡⅢⅣⅤ2.9m120102.1m002211.5m31203余料00.10.20.30.8當前第39頁\共有172頁\編于星期五\7點教材上的模型說明當前第40頁\共有172頁\編于星期五\7點上題計算求得如下方案:x1=30,x2=10,x4=50,其余為0.即按方案1下料30根,按方案2下料10根,按方案4下料50根,總共需要90根原材料可以制造100套鋼架.當前第41頁\共有172頁\編于星期五\7點例4人事管理問題一個企業(yè)每周七天都要生產或營業(yè)每個工作人員每周連續(xù)5天據(jù)分析每天的上班人數(shù)分別60、40、50、30、65、70和75人問該企業(yè)至少需要多少個職工？當前第42頁\共有172頁\編于星期五\7點模型建立1、設(未知數(shù))決策變量設從星期一開始上班的人數(shù)為x1,星期二開始上班的人數(shù)為x2，星期三開始上班的人數(shù)為x3，星期四開始上班的人數(shù)為x4,星期五開始上班的人數(shù)為x5，星期六開始上班的人數(shù)為x6，星期日開始上班的人數(shù)為x7。2、用決策變量表達目標函數(shù)minz=x1+x2+x3+x4+x5+x6+x73、用決策變量表達全部的約束條件4、注意符號約束當前第43頁\共有172頁\編于星期五\7點minz=x1+x2+x3+x4+x5+x6+x7x4+x5+x6+x7+x1≥60x5+x6+x7

+x1+x2≥40x6+x7

+x1+x2+x3≥50x7

+x1+x2+x3+x4≥30x1+x2+x3+x4+x5≥65x2+x3+x4+x5+x6≥70x3+x4+x5+x6+x7≥75xj≥0，xj為整數(shù)，j=1,2,…,7數(shù)學模型為能夠求出最優(yōu)解為：x1=9，x2=0，x3=23，x4=19，x5=14，

x6=19，x7=0(最優(yōu)值)minz=84當前第44頁\共有172頁\編于星期五\7點設決策變量的原則1、將決策者想知道但還不知道的設為未知數(shù)；（返回）2、所取決策變量要便于表達目標函數(shù)和約束條件。3、當將決策者想知道但還不知道的是由多個部分組成時，則應將最基本的部分取為決策變量。(作業(yè))當前第45頁\共有172頁\編于星期五\7點建立線性規(guī)劃數(shù)學模型的步驟1、選擇適當?shù)臎Q策變量設決策變量的原則2、用決策變量表達目標函數(shù)收入或利潤極大化成本或支出極小化3、用決策變量表達所有的約束條件4、注意變量的符號約束返回當前第46頁\共有172頁\編于星期五\7點線性規(guī)劃數(shù)學模型的特點1、一組決策變量(x1,x2,…,xn)決策者可選擇2、一個目標函數(shù)極大化或極小化是決策變量的線性函數(shù)Max(或min)z=c1x1+c2x2+…+cnxn3、一組約束條件決策變量的線性等式或不等式組4、通常變量有符號約束xj≥０當前第47頁\共有172頁\編于星期五\7點P38例11配料問題產品原材料產價品格CPHA≥50%≤25%50B≥25%≤50%35D25原材料供應量10010060原材料價格652535當前第48頁\共有172頁\編于星期五\7點模型建立1、設(未知數(shù))決策變量設A產品中含原材料C、P、H的數(shù)量分別為AC、AP、AHB產品中含原材料C、P、H的數(shù)量分別為BC、BP、BHD產品中含原材料C、P、H的數(shù)量分別為DC、DP、DH。2、用決策變量表達目標函數(shù)(利潤=銷售收入-成本)maxz=50(AC+AP+AH)+35(BC+BP+BH)+25(DC+DP+DH)-65(AC+BC+DC)-25(AP+BP+DP)-35(AH+BH+DH)

=-15AC+25AP+15AH-30BC+10BP-40DC-10DH3、用決策變量表達全部的約束條件4、注意符號約束當前第49頁\共有172頁\編于星期五\7點約束條件整理得AC+BC+DC≤100AP+BP+DP≤100AH+BH+DH≤60含量約束原材料數(shù)量約束當前第50頁\共有172頁\編于星期五\7點數(shù)學模型為maxz=-15AC+25AP+15AH-30BC+10BP-40DC-10DHAC、AP、AH，

BC、BP、BH，DC、DP、DH≥0當前第51頁\共有172頁\編于星期五\7點能夠求得最優(yōu)解和最優(yōu)值最優(yōu)解需要用原料C為100kg，P為50kg，H為50kg，構成產品A。其它產品不生產。即每天只生產產品A為200kg，分別需要用原料C為100kg，P為50kg，H為50kg。最優(yōu)值即總利潤是z=500元/天。當前第52頁\共有172頁\編于星期五\7點生產與庫存的優(yōu)化安排某工廠生產五種產品（i=1，...，5），上半年各月對每種產品的最大市場需求為dij。已知每件產品的單件售價為Si元，生產每件產品所需要的工時為ai，單件成本為Ci元；該工廠上半年各月正常生產工時為ri（j=1，...，6），各月允許的加班工時為ri’,Ci’為加班單件成本。又每月生產的各種產品如當月銷售不完，可以庫存。庫存費用為Hi（元/件.月)。假設1月初所有產品的庫存為0，要求6月末個產品庫存量為ki件。現(xiàn)要求為該廠制定一個生產計劃，在盡可能利用生產能力的條件下，獲取最大利潤。當前第53頁\共有172頁\編于星期五\7點設xij，xij’分別為該廠第i種產品第j個月在正常時間和加班時間內的生產量；yii為i種產品在第j個月的銷售量，wij為第i種產品第j月末的庫存量。當前第54頁\共有172頁\編于星期五\7點例4運輸問題P80,產銷平衡表單位：噸銷地加工廠B1B2B3B4產量A1A2A3

317119432101085749銷量3656當前第55頁\共有172頁\編于星期五\7點作業(yè)P46習題1.9，提示：設從第i個班次開始上班的人數(shù)為xi,i=1,2,…,6習題1.10當前第56頁\共有172頁\編于星期五\7點二、線性規(guī)劃數(shù)學模型的特點1、一組決策變量(x1,x2,…,xn)決策者可選擇2、一個目標函數(shù)極大化或極小化是決策變量的線性函數(shù)Max(或min)z=c1x1+c2x2+…+cnxn3、一組約束條件決策變量的線性等式或不等式組4、通常變量有符號約束或整數(shù)約束或0-1變量約束xj≥０；xj為整數(shù)；xj=0或1當前第57頁\共有172頁\編于星期五\7點線性規(guī)劃模型的一般形式

當前第58頁\共有172頁\編于星期五\7點三、線性規(guī)劃問題的標準形式標準形式為:1、目標函數(shù)最大2、約束條件等式3、決策變量非負4、右端系數(shù)非負當前第59頁\共有172頁\編于星期五\7點將下述線性規(guī)劃化為標準形式當前第60頁\共有172頁\編于星期五\7點向量形式表示線性規(guī)劃問題當前第61頁\共有172頁\編于星期五\7點矩陣形式表示線性規(guī)劃問題當前第62頁\共有172頁\編于星期五\7點可行解，最優(yōu)解圖解法的步驟(1)畫出可行區(qū)域1)作出每個約束取等號的直線2)判斷可行域在直線的那一邊(2)找出最優(yōu)解1)作目標函數(shù)等值線，確定使目標函數(shù)最優(yōu)的移動方向；2)平移目標函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。繼續(xù)返回1.2線性規(guī)劃問題的圖解法

——適用于兩個自變量當前第63頁\共有172頁\編于星期五\7點例1的數(shù)學模型

目標函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

x2圖解法當前第64頁\共有172頁\編于星期五\7點9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2x1+2x2

8(0,4)(8,0)

目標函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

04x1

164x2

12圖解法當前第65頁\共有172頁\編于星期五\7點9—8—7—6—5—4—3—2—1—0x2

目標函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

12可行域圖解法當前第66頁\共有172頁\編于星期五\7點9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2

目標函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

0x1+2x2

84x1

164x2

12可行域BCDEA圖解法當前第67頁\共有172頁\編于星期五\7點9—8—7—6—5—4—3—2—1—0x2

目標函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

12BCDEA2x1+3x2=6圖解法當前第68頁\共有172頁\編于星期五\7點9—8—7—6—5—4—3—2—1—0x2

目標函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

12BCDEAx1+2x2=84x1=16最優(yōu)解(2,4)圖解法當前第69頁\共有172頁\編于星期五\7點線性規(guī)劃問題求解的

幾種可能結果(a)唯一最優(yōu)解

x26—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1當前第70頁\共有172頁\編于星期五\7點(b)無窮多最優(yōu)解6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1線性規(guī)劃問題求解的

幾種可能結果當前第71頁\共有172頁\編于星期五\7點(c)無界解

MaxZ=x1+x2

-2x1+x2

4

x1-x2

2

x1、x2

0

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

幾種可能結果當前第72頁\共有172頁\編于星期五\7點(d)無可行解

MaxZ=2x1+3x2x1+2x2

84x1

164x2

12

-2x1+x24x1、x2

0可行域為空集線性規(guī)劃問題求解的

幾種可能結果當前第73頁\共有172頁\編于星期五\7點圖解法的幾點結論:1、可行域是非空有界或無界的凸多邊形,也可能為空集。2、可行域為有界時，一定有最優(yōu)解1）有唯一最優(yōu)解2）有兩個以上的最優(yōu)解（也必有無窮多個最優(yōu)解）3、可行域為無界時，可能有最優(yōu)解，也可能無最優(yōu)解1）有唯一最優(yōu)解2）有兩個以上的最優(yōu)解（也必有無窮多個最優(yōu)解）3）無界解4、可行域為空集，一定沒有最優(yōu)解若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點得到。若兩個頂點同時得到最優(yōu)解，則其連線上的所有點都是最優(yōu)解。當前第74頁\共有172頁\編于星期五\7點練習：

用圖解法求解LP問題

MaxZ=34x1+40x24x1+6x2

482x1+2x2

182x1+x2

16x1、x2

0當前第75頁\共有172頁\編于星期五\7點圖解法—（練習）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16MaxZ=34x1+40x24x1+6x2

482x1+2x2

182x1+x2

16x1、x2

0當前第76頁\共有172頁\編于星期五\7點圖解法—（練習）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16可行域ABCDE當前第77頁\共有172頁\編于星期五\7點圖解法—（練習）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16ABCDE(8,0)(0,6.8)34x1+40x2=272當前第78頁\共有172頁\編于星期五\7點圖解法—（練習）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16ABCDE(8,0)(0,6.8)當前第79頁\共有172頁\編于星期五\7點圖解法—（練習）

x218—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x14x1+6x2

482x1+2x2

182x1+x2

16ABCDE(8,0)(0,6.8)最優(yōu)解(3,6)4x1+6x2=482x1+2x2=18當前第80頁\共有172頁\編于星期五\7點圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域為凸集目標函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產生

目標函數(shù)等值線的斜率最優(yōu)解當前第81頁\共有172頁\編于星期五\7點圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域為凸集目標函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產生

目標函數(shù)等值線的斜率最優(yōu)解當前第82頁\共有172頁\編于星期五\7點圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域為凸集目標函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產生

目標函數(shù)等值線的斜率最優(yōu)解當前第83頁\共有172頁\編于星期五\7點第三節(jié)單純形法原理

一、線性規(guī)劃問題解的概念標準型可行解:滿足AX=b,X>=0的解X稱為線性規(guī)劃問題的可行解。最優(yōu)解：使Z=CX達到最大值的可行解稱為最優(yōu)解。當前第84頁\共有172頁\編于星期五\7點

基：若B是矩陣A中m×m階非奇異子矩陣（|B|≠0），則B是線性規(guī)劃問題的一個基。不妨設：

,j=1，2，…,m——

基向量。，j=1，2，…,m

——

基變量。,j=m+1,…,n

——

非基變量。線性規(guī)劃問題解的概念當前第85頁\共有172頁\編于星期五\7點例當前第86頁\共有172頁\編于星期五\7點基、基變量、非基變量、基向量、非基向量、基解、基可行解、

可行基當前第87頁\共有172頁\編于星期五\7點例行列式基變量非基變量基向量非基向量當前第88頁\共有172頁\編于星期五\7點對應于基B1的基解X1非基可行解當前第89頁\共有172頁\編于星期五\7點例行列式基變量非基變量基變量非基變量當前第90頁\共有172頁\編于星期五\7點對應于基B2的基解X2基可行解當前第91頁\共有172頁\編于星期五\7點

求解

線性規(guī)劃問題解的概念當前第92頁\共有172頁\編于星期五\7點基解：稱上面求出的X解為基解。基可行解：非負的基解X稱為基可行解可行基：對應基可行解的基稱為可行基線性規(guī)劃問題解的概念T基變量令可求出：當前第93頁\共有172頁\編于星期五\7點

線性規(guī)劃解的關系圖非可行解可行解

基可行解

基解線性規(guī)劃問題解的概念

最優(yōu)解？當前第94頁\共有172頁\編于星期五\7點

例：求基解、基可行解、最優(yōu)解。線性規(guī)劃問題解的概念當前第95頁\共有172頁\編于星期五\7點10051045Y

20452017Y

35005410Y

40550-120N5100-50415N652.5001.517.5Y

7540-3022N82430019

Y

是否基可行解最優(yōu)解線性規(guī)劃問題解的概念解：當前第96頁\共有172頁\編于星期五\7點

：求基解、基可行解、最優(yōu)解。練習：線性規(guī)劃問題解的概念當前第97頁\共有172頁\編于星期五\7點

單純形法原理舉例例6求解下面的線性規(guī)劃

maxz=2x1+3x2+0x3+0x4+0x5x1+2x2+x3=84x1+x4=161.124x2+x5=12x1,x2,x3,x4,x5≥0當前第98頁\共有172頁\編于星期五\7點1、找一個基可行解X0作為初始解;最容易得到的可行基是標準型線性規(guī)劃的系數(shù)矩陣的單位矩陣.當前第99頁\共有172頁\編于星期五\7點2、求檢驗數(shù)，檢驗X0是否為最優(yōu)解（１）求檢驗數(shù)將約束方程組的基變量的系數(shù)矩陣化為單位矩陣（或將基變量用非基變量表出）；通過代入或加減乘除消元法將目標函數(shù)中的基變量消去，則非基變量的系數(shù)即為檢驗數(shù)．（２）最優(yōu)解的判別當檢驗數(shù)全部小于或等于0時，該基可行解為最優(yōu)解,求解可結束.當存在正的檢驗數(shù)時,該基可行解就不是最優(yōu)解,就要換到一個新的(與X0相鄰的)基可行解（X1）．當前第100頁\共有172頁\編于星期五\7點Z=2x1+3x2+0X3=8-x1-2x2X4=16-4x2X5=12-4x2目標函數(shù)的表達式中還存在正系數(shù)的非基變量,這表示目標函數(shù)還有增加的可能,就需要基變量和非基變量對換.一般取正系數(shù)最大的那個基變量x2為換入變量,那么取哪個基變量為換出變量呢?當前第101頁\共有172頁\編于星期五\7點當將x2確定為換入變量,x1=0時,必須確保x3,x4,x5均非負.X3=8-2x2>=0X4=16>=0X5=12-4x2>=0x2必須滿足:x2<=3,當x2最多取值3,X5=0,因此用X2去換X5,因為如果去換X2,必然導致X5小于0.X3=8-x1-2x2X4=16-4x2X5=12-4x2X2=3-1/4x5，代入上面兩式，即得當前第102頁\共有172頁\編于星期五\7點當前第103頁\共有172頁\編于星期五\7點2線性規(guī)劃問題的幾何意義基本概念凸集：線性規(guī)劃問題的幾何意義當前第104頁\共有172頁\編于星期五\7點

頂點:若K是凸集，X∈K；若X不能用不同的兩點的線性組合表示為：則X為頂點.

凸集線性規(guī)劃問題的幾何意義當前第105頁\共有172頁\編于星期五\7點

凸組合：

Xn=2，k=3線性規(guī)劃問題的幾何意義當前第106頁\共有172頁\編于星期五\7點定理1:若線性規(guī)劃問題存在可行域,則其可行域:是凸集.基本定理證明:線性規(guī)劃問題的幾何意義當前第107頁\共有172頁\編于星期五\7點

只要驗證X在D中即可當前第108頁\共有172頁\編于星期五\7點

引理：可行解X為基可行解

X的正分量對應的列向量線性無關定理3：若可行域有界，線性規(guī)劃問題的目標函數(shù)一定可以在其可行域的頂點上達到最優(yōu)。定理2：線性規(guī)劃問題的基可行解X

對應于可行域D的頂點。證明：反證法。分兩步。當前第109頁\共有172頁\編于星期五\7點幾點結論：線性規(guī)劃問題的可行域是凸集?；尚薪馀c可行域的頂點一一對應，可行域有有限多個頂點。最優(yōu)解必在頂點上得到。當前第110頁\共有172頁\編于星期五\7點引理1線性規(guī)劃問題的可行解X=(x1,x2,…,xn)T為基可行解的充分必要條件是X的正分量是線性獨立的。定理2線性規(guī)劃問題的基可行解X對應于可行域的頂點。引理2若K是有界凸集，則任意一點x∈K可表示為K的頂點的凸組合。定理3若可行域有界，線性規(guī)劃問題的目標函數(shù)一定可以在其可行域的頂點上達到最優(yōu)。當前第111頁\共有172頁\編于星期五\7點有時目標函數(shù)可能在多個頂點達到最大值。這時這些頂點的凸組合上也達到最大值。稱這種線性規(guī)劃問題有無限多個最優(yōu)值。當前第112頁\共有172頁\編于星期五\7點四、單純形法迭代原理

1、初始基可行解的確定

為了確定初始基可行解，首先找出初始可行基，其方法如下：1、

若線性規(guī)劃問題

(1.20)

當前第113頁\共有172頁\編于星期五\7點從Pj(j=1,2,…,n)中一般能直接觀察到存在一個初始可行基當前第114頁\共有172頁\編于星期五\7點2、對所有約束條件是“≤”形式的不等式，可以利用化標準型的方法，在每個約束條件的左端加上一個松馳變量。經整理，重新對xj及aij(i=1,2,…,m;j=1,2,…,n)進行編號，則可得下列方程組當前第115頁\共有172頁\編于星期五\7點3.對所有約束條件是“≥”形式的不等式及等式約束情況，若不存在單位矩陣時，就采取人造基的方法。即對不等式約束減去一個非負的剩余變量后，再加上一個非負的人工變量。對于等式約束加上一個非負的人工變量，總能得到一個單位矩陣。當前第116頁\共有172頁\編于星期五\7點x1 +a1,m+1xm+1+…+a1nxn=b1x2+a2,m+1xm+1+…+a2nxn=b2

……… xm+am,m+1xm+1+…+amnxn=bm xj≥0，j=1,2,…n當前第117頁\共有172頁\編于星期五\7點顯然得到一個m×m單位矩陣當前第118頁\共有172頁\編于星期五\7點以B作為可行基。移項得

x1=b1-a1,m+1xm+1-…-a1nxnx2=b2-a2,m+1xm+1-…-a2nxn

………xm=bm-am,m+1xm+1-…-amnxn

令xm+1=xm+2=…=xn=0,由（1.23）可得xi=bi (I=1,2,…,m)又因bj≥0，所以得到一個初始基可行解X=(x1,x2,…,xm,0,…,0)T=(b1,b2,…,bm,0,…,0)T

當前第119頁\共有172頁\編于星期五\7點當前第120頁\共有172頁\編于星期五\7點當前第121頁\共有172頁\編于星期五\7點當前第122頁\共有172頁\編于星期五\7點最優(yōu)性檢驗與解的判別線性規(guī)劃問題的求解結果可能出現(xiàn)唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解四種情況，為此需要建立對解的判別準則。一般情況下，經過迭代后（1.23）式變?yōu)?/p>

(i=1,2,…,m)(1.24)

當前第123頁\共有172頁\編于星期五\7點將（1.24）式代入目標函數(shù)（1.20），整理后得當前第124頁\共有172頁\編于星期五\7點令，（j=m+1,…,n）于是

再（j=m+1,…,n）則 （1.27）

當前第125頁\共有172頁\編于星期五\7點1、最優(yōu)解的判別定理：若X(0)=(0,…,0)T為對應于基B的一個基可行解，且對于一切j=m+1,…,n有σj≤0，則X(0)為最優(yōu)解，稱σj為檢驗數(shù)。當前第126頁\共有172頁\編于星期五\7點2、無窮多最優(yōu)解判別定理：若X(0)=(0,…,0)T為一個基可行解，對于一切j=m+1,…,n有σj≤0，又存在某個非基變量xm+j的檢驗數(shù)σm+k=0,則線性規(guī)劃問題有無窮多最優(yōu)解。因為將xm+j將得到一個新的基可行解仍為最優(yōu)解,由于最優(yōu)解的凸組合還是最優(yōu)解,因此有無窮多最優(yōu)解.當前第127頁\共有172頁\編于星期五\7點3、無界解判別定理:

若X(0)=(0,…,0)T為一個基可行解，有一個非基變量xm+k的檢驗數(shù)σm+k>0,并且對i=1,2,…,m有ai,m+k≤0,那么該線性規(guī)劃問題具有無界解（或稱無最優(yōu)解）當前第128頁\共有172頁\編于星期五\7點例x3 =8-2x2≥0 x4 =16≥0 （1.15）

x5=12-4x2≥0此時最小比θ=min(8/2,-,12/4)=3是進基變量的最大取值，但是若（1.15）式中x2的系數(shù)全部非負，則最小比為+∞，即x2可以取到+∞，目標函數(shù)值z=0+2x1+3x2

就可取到+∞，因此目標函數(shù)無界。當前第129頁\共有172頁\編于星期五\7點3.4基變換

1、換入變量的確定：由（1.27）式看到，當某些σj>0時，xj增加則目標函數(shù)還可以增大，這時要將某個非基變量xj換到基變量中去（稱為換入變量）。若有兩個以上的σj>0，那么選哪個非基變量作為換入變量呢？當前第130頁\共有172頁\編于星期五\7點為了使目標函數(shù)值增加最快，從直觀上一般選σj>0種的大者（可以任意選或按最小下標選）即 max(σj>0)=σk則對應的xk為換入變量。實際上換一次基將使目標函數(shù)值改進σkθ。當前第131頁\共有172頁\編于星期五\7點2、換出變量的確定按最小比值確定換出變量。當前第132頁\共有172頁\編于星期五\7點3.5迭代（旋轉運算） 將約束條件的增廣矩陣中新基變量的系數(shù)通過矩陣的行變換或Gauss變換變?yōu)閱挝痪仃?。當前?33頁\共有172頁\編于星期五\7點例7試用上述方法計算例6的兩個基變換。解約束條件的增廣矩陣為

x1x2x3x4x5b當前第134頁\共有172頁\編于星期五\7點當以x3，x4，x5為基變量，x1，x2為非基變量，令x1=x2=0，可得到一個基可行解

X(0)=(0,0,8,16,12)現(xiàn)用x2去替換x5,于是將x3，x4，x2的系數(shù)矩陣變換為單位矩陣當前第135頁\共有172頁\編于星期五\7點經變換后為

x1x2x3x4x5b

令非基變量x1,x5=0,得到新的基可行解

X(1)=(0，3，2，16，0)T當前第136頁\共有172頁\編于星期五\7點§1.4單純形法的計算步驟

與表格單純形法當前第137頁\共有172頁\編于星期五\7點線性規(guī)劃問題X1+a1,m+1xm+1+…+a1nxn=b1x2+a2,m+1xm+1+…+a2nxn=b2

………xm+am,m+1xm+1+…+amnxn=bm-z+c1x1+c2x2+…+cmxm+cm+1xm+1+…cnxn=0當前第138頁\共有172頁\編于星期五\7點為了便于迭代運算，可將上述方程組寫成增廣矩陣-zx1x2

…xmxm+1

…xnb

當前第139頁\共有172頁\編于星期五\7點若將z看成不參與基變換的基變量，它與x1，x2，…，xm的系數(shù)構成一個基，這時可采用行初等變換將c1,c2,…,cm變換為零，使其對應的系數(shù)矩陣為單位矩陣，當前第140頁\共有172頁\編于星期五\7點得到-zx1x2

…xmxm+1

…xnb當前第141頁\共有172頁\編于星期五\7點可根據(jù)上述增廣矩陣設計計算表如下：

當前第142頁\共有172頁\編于星期五\7點cjc1…cm

cm+1…

cnθCBxB

bx1…xm

xm+1…

xnc1C2…cm

x1x2…xm

b1b2…bm

10…0……

…

00…1a1,m+1a2,m+1…am,m+1

……

…

a1na2n…amn

θ1θ2…θm-z0…0…當前第143頁\共有172頁\編于星期五\7點4.2計算步驟

（1）找出初始可行基，確定初始基可行解，建立初始單純形表。（2）檢驗各非基變量xj的檢驗數(shù)是則已得到最優(yōu)解。可停止計算。否則，轉入下一步。（3）在中，若有某個對應項xk的系數(shù)列向量Pk≤0，則此問題是無界，停止計算。否則，轉入下一步。當前第144頁\共有172頁\編于星期五\7點（4）根據(jù)max(σj>0)=σk,確定xk為換入變量，按θ規(guī)則計算可確定xl換入變量。轉入下一步。（5）以alk為主元素進行迭代（即用高斯消去法或稱為旋轉運算），把xk所對應的列向量當前第145頁\共有172頁\編于星期五\7點將xB列中的xl換為xk,得到新的單純形表。重復（2）—（5），直到終止?，F(xiàn)用例1的標準型來說明上述計算步驟。（1）根據(jù)例1的標準型，以x3,x4,x5為基變量，它對應的單位矩陣為基。這就得到初始即可行解X(0)=(0,0,8,16,12)T將有關數(shù)值填入表中，得到（對應于初始基可行解的）初始單純形表。

當前第146頁\共有172頁\編于星期五\7點表1-3cj23000θcBxBBx1x2x3x4x50x30x40x5816121402041000100014-3-z023000當前第147頁\共有172頁\編于星期五\7點(初始)單純形表的特點1、一個單純形表對應于一個基可行解;2、一個單純形表中，基變量的系數(shù)矩陣是單位矩陣;3、一個單純形表中，目標函數(shù)中基變量的系數(shù)為零，非基變量的系數(shù)為檢驗數(shù)；4、檢驗數(shù)的計算既可用公式法，也可用消去法；5、一個單純形表中，基可行解的基變量為右端常數(shù)；當前第148頁\共有172頁\編于星期五\7點各非基變量的檢驗數(shù)為

σ1=c1-z1=2-(0×1+0×4+0×0)=2 σ2=c2-z2=3-(0×2+0×0+0×4)=3(2)因檢驗數(shù)中有正數(shù)，且P1,P2有正分量存在，轉入下一步（3）max(σ1,σ2)=max(2,3)=3;對應的變量x2

為換入變量。計算θθ=它所在行對應的x5為換出變量，x2所在的列與x5所在的行交叉處[4]為主元素。當前第149頁\共有172頁\編于星期五\7點以[4]為主元素進行旋轉運算，即初等變換，使P2變?yōu)椋?，0，1）T,在xB列中將x2替換x5,于是得到新表1-4

當前第150頁\共有172頁\編于星期五\7點表1.4cj23000θcBxBBx1x2x3x4x50x30x40x22163140001100010-1/201/424--z92000-3/4當前第151頁\共有172頁\編于星期五\7點由于檢驗數(shù)有正數(shù)，還沒有得到最優(yōu)解，max(σ1,σ5)=max(2,-3/4)=2=σ1,則x1為換入變量，θ=則x3為換出變量。以1為主元數(shù)進行旋轉運算，得

當前第152頁\共有172頁\編于星期五\7點表1-5cjcBxBb2x13x20x30x40x5θ2x10x43x22831000011-40010-1/221/4-412-z-1300-201/4當前第153頁\共有172頁\編于星期五\7點由于檢驗數(shù)有正數(shù)，還沒有得到最優(yōu)解，max(σ3,σ5)=max(-2,1/4)=1/4=σ5,則x5為換入變量，θ=則x4為換出變量。以2為主元數(shù)進行旋轉運算，得當前第154頁\共有172頁\編于星期五\7點表1-6cjcBxBb2x13x20x30x40x5θ2x10x53x24421000010-21/21/41/2-1/8010-z-1400-1.5-1/80當前第155頁\共有172頁\編于星期五\7點從表1-6看出檢驗數(shù)都小于或等于零，于是對應的基可行解X=(4,2,0,0,4)為最優(yōu)解,最優(yōu)值z=14.非基變量的檢驗數(shù)都是正，因此有唯一最優(yōu)解。當前第156頁\共有172頁\編于星期五\7點§5單純形法的進一步討論當前第157頁\共有172頁\編于星期五\7點5.1人工變量法5.1人工變量法設線性規(guī)劃問題的約束條件是

分別給每一個約束方程加入人工變量xn+1,xn+2,…,xn+m,得到

當前第158頁