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

返回第15頁，課件共156頁，創(chuàng)作于2023年2月線性規(guī)劃中的兩類數(shù)學(xué)模型22、min總成本總收入≥b返回2）表格單純形法第16頁，課件共156頁，創(chuàng)作于2023年2月

線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型的一般形式兩個(gè)自變量線性規(guī)劃的圖解法線性規(guī)劃問題的標(biāo)準(zhǔn)形式

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

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

——轉(zhuǎn)化成數(shù)學(xué)模型第19頁，課件共156頁，創(chuàng)作于2023年2月例1:生產(chǎn)計(jì)劃問題(步驟)第20頁，課件共156頁，創(chuàng)作于2023年2月產(chǎn)品I產(chǎn)品2如何安排生產(chǎn)使利潤(rùn)最大？第21頁，課件共156頁，創(chuàng)作于2023年2月是問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。第1步-確定決策變量（設(shè)決策變量的原則）設(shè)——I的產(chǎn)量——II的產(chǎn)量——利潤(rùn)第22頁，課件共156頁，創(chuàng)作于2023年2月第2步--定義目標(biāo)函數(shù)MaxZ=x1+x2決策變量第23頁，課件共156頁，創(chuàng)作于2023年2月

MaxZ=2x1+3x2系數(shù)第2步--定義目標(biāo)函數(shù)第24頁，課件共156頁，創(chuàng)作于2023年2月對(duì)我們有何限制?第25頁，課件共156頁，創(chuàng)作于2023年2月

x1+2x2

84x1

164x2

12x1、x2

0第3步--表示約束條件第26頁，課件共156頁，創(chuàng)作于2023年2月該計(jì)劃的數(shù)學(xué)模型

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

約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

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

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

500萬m320%自然凈化

200萬m3

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

治污成本800元/萬m3

要求污水含量不大于0.2%(步驟)長(zhǎng)江嘉陵江朝天門第31頁，課件共156頁，創(chuàng)作于2023年2月說明從第一化工廠排出的工業(yè)污水流到第二化工廠以前,有20%可以凈化.江水中要求污水含量不大于0.2%.工廠1和工廠2的污水凈化成本分別為1000元/萬m和800元/萬m問每個(gè)廠各應(yīng)處理多少工業(yè)污手,使這兩個(gè)工廠總的處理工業(yè)污水費(fèi)用最小.第32頁，課件共156頁，創(chuàng)作于2023年2月設(shè)：化工廠1每天處理的污水量為x1萬立方米；化工廠2每天處理的污水量為x2萬立方米建模型之前的分析和計(jì)算第33頁，課件共156頁，創(chuàng)作于2023年2月整理得到本問題的數(shù)學(xué)模型為：第34頁，課件共156頁，創(chuàng)作于2023年2月例3合理下料問題書上P38例10原材料，長(zhǎng)7.4米一套鋼架任務(wù)：100套鋼架目標(biāo)：成本最少2.9m2.1m1.5m第35頁，課件共156頁，創(chuàng)作于2023年2月分析下料的方式方式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頁，課件共156頁，創(chuàng)作于2023年2月數(shù)學(xué)模型為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頁，課件共156頁，創(chuàng)作于2023年2月模型建立1、設(shè)(未知數(shù))決策變量設(shè)按Ⅰ方案下料的原材料根數(shù)為x1,Ⅱ方案為x2，Ⅲ方案為x3，Ⅳ方案為x4,Ⅴ方案為x5，2、用決策變量表達(dá)目標(biāo)函數(shù)minz=0x1+0.1x2+0.2x3+0.3x4+0.8x53、用決策變量表達(dá)全部的約束條件4、注意符號(hào)約束第38頁，課件共156頁，創(chuàng)作于2023年2月方式x1x2x3x4x5元鋼ⅠⅡⅢⅣⅤ2.9m120102.1m002211.5m31203余料00.10.20.30.8第39頁，課件共156頁，創(chuàng)作于2023年2月教材上的模型說明第40頁，課件共156頁，創(chuàng)作于2023年2月上題計(jì)算求得如下方案:x1=30,x2=10,x4=50,其余為0.即按方案1下料30根,按方案2下料10根,按方案4下料50根,總共需要90根原材料可以制造100套鋼架.第41頁，課件共156頁，創(chuàng)作于2023年2月例4人事管理問題一個(gè)企業(yè)每周七天都要生產(chǎn)或營(yíng)業(yè)每個(gè)工作人員每周連續(xù)5天據(jù)分析每天的上班人數(shù)分別60、40、50、30、65、70和75人問該企業(yè)至少需要多少個(gè)職工？第42頁，課件共156頁，創(chuàng)作于2023年2月模型建立1、設(shè)(未知數(shù))決策變量設(shè)從星期一開始上班的人數(shù)為x1,星期二開始上班的人數(shù)為x2，星期三開始上班的人數(shù)為x3，星期四開始上班的人數(shù)為x4,星期五開始上班的人數(shù)為x5，星期六開始上班的人數(shù)為x6，星期日開始上班的人數(shù)為x7。2、用決策變量表達(dá)目標(biāo)函數(shù)minz=x1+x2+x3+x4+x5+x6+x73、用決策變量表達(dá)全部的約束條件4、注意符號(hào)約束第43頁，課件共156頁，創(chuàng)作于2023年2月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ù)學(xué)模型為能夠求出最優(yōu)解為：x1=9，x2=0，x3=23，x4=19，x5=14，

x6=19，x7=0(最優(yōu)值)minz=84第44頁，課件共156頁，創(chuàng)作于2023年2月設(shè)決策變量的原則1、將決策者想知道但還不知道的設(shè)為未知數(shù)；（返回）2、所取決策變量要便于表達(dá)目標(biāo)函數(shù)和約束條件。3、當(dāng)將決策者想知道但還不知道的是由多個(gè)部分組成時(shí)，則應(yīng)將最基本的部分取為決策變量。(作業(yè))第45頁，課件共156頁，創(chuàng)作于2023年2月二、線性規(guī)劃問題的數(shù)學(xué)模型1、選擇適當(dāng)?shù)臎Q策變量設(shè)決策變量的原則2、用決策變量表達(dá)目標(biāo)函數(shù)收入或利潤(rùn)極大化成本或支出極小化3、用決策變量表達(dá)所有的約束條件4、注意變量的符號(hào)約束返回第46頁，課件共156頁，創(chuàng)作于2023年2月線性規(guī)劃數(shù)學(xué)模型的特點(diǎn)1、一組決策變量(x1,x2,…,xn)決策者可選擇2、一個(gè)目標(biāo)函數(shù)極大化或極小化是決策變量的線性函數(shù)Max(或min)z=c1x1+c2x2+…+cnxn3、一組約束條件決策變量的線性等式或不等式組4、通常變量有符號(hào)約束xj≥０第47頁，課件共156頁，創(chuàng)作于2023年2月P38例11配料問題產(chǎn)品原材料產(chǎn)價(jià)品格CPHA≥50%≤25%50B≥25%≤50%35D25原材料供應(yīng)量10010060原材料價(jià)格652535第48頁，課件共156頁，創(chuàng)作于2023年2月模型建立1、設(shè)(未知數(shù))決策變量設(shè)A產(chǎn)品中含原材料C、P、H的數(shù)量分別為AC、AP、AHB產(chǎn)品中含原材料C、P、H的數(shù)量分別為BC、BP、BHD產(chǎn)品中含原材料C、P、H的數(shù)量分別為DC、DP、DH。2、用決策變量表達(dá)目標(biāo)函數(shù)(利潤(rùn)=銷售收入-成本)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、用決策變量表達(dá)全部的約束條件4、注意符號(hào)約束第49頁，課件共156頁，創(chuàng)作于2023年2月約束條件整理得AC+BC+DC≤100AP+BP+DP≤100AH+BH+DH≤60含量約束原材料數(shù)量約束第50頁，課件共156頁，創(chuàng)作于2023年2月數(shù)學(xué)模型為maxz=-15AC+25AP+15AH-30BC+10BP-40DC-10DHAC、AP、AH，

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

317119432101085749銷量3656第55頁，課件共156頁，創(chuàng)作于2023年2月作業(yè)P46習(xí)題1.9，提示：設(shè)從第i個(gè)班次開始上班的人數(shù)為xi,i=1,2,…,6習(xí)題1.10第56頁，課件共156頁，創(chuàng)作于2023年2月線性規(guī)劃模型的一般形式

第57頁，課件共156頁，創(chuàng)作于2023年2月三、線性規(guī)劃問題的標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式為:1、目標(biāo)函數(shù)最大2、約束條件等式3、決策變量非負(fù)4、右端系數(shù)非負(fù)第58頁，課件共156頁，創(chuàng)作于2023年2月將下述線性規(guī)劃化為標(biāo)準(zhǔn)形式第59頁，課件共156頁，創(chuàng)作于2023年2月向量形式表示線性規(guī)劃問題第60頁，課件共156頁，創(chuàng)作于2023年2月矩陣形式表示線性規(guī)劃問題第61頁，課件共156頁，創(chuàng)作于2023年2月可行解，最優(yōu)解圖解法的步驟(1)畫出可行區(qū)域1)作出每個(gè)約束取等號(hào)的直線2)判斷可行域在直線的那一邊(2)找出最優(yōu)解1)作目標(biāo)函數(shù)等值線，確定使目標(biāo)函數(shù)最優(yōu)的移動(dòng)方向；2)平移目標(biāo)函數(shù)的等值線，找出最優(yōu)點(diǎn)，算出最優(yōu)值。繼續(xù)返回1.2線性規(guī)劃問題的圖解法

——適用于兩個(gè)自變量第62頁，課件共156頁，創(chuàng)作于2023年2月例1的數(shù)學(xué)模型

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

約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

x2圖解法第63頁，課件共156頁，創(chuàng)作于2023年2月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)

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

約束條件x1+2x2

84x1

164x2

12x1、x2

04x1

164x2

12圖解法第64頁，課件共156頁，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0x2

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

約束條件x1+2x2

84x1

164x2

12x1、x2

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

84x1

164x2

12可行域圖解法第65頁，課件共156頁，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2

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

約束條件x1+2x2

84x1

164x2

12x1、x2

0x1+2x2

84x1

164x2

12可行域BCDEA圖解法第66頁，課件共156頁，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0x2

目標(biāo)函數(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圖解法第67頁，課件共156頁，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0x2

目標(biāo)函數(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)圖解法第68頁，課件共156頁，創(chuàng)作于2023年2月線性規(guī)劃問題求解的

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

x26—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1第69頁，課件共156頁，創(chuàng)作于2023年2月(b)無窮多最優(yōu)解6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1線性規(guī)劃問題求解的

幾種可能結(jié)果第70頁，課件共156頁，創(chuàng)作于2023年2月(c)無界解

MaxZ=x1+x2

-2x1+x2

4

x1-x2

2

x1、x2

0

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

幾種可能結(jié)果第71頁，課件共156頁，創(chuàng)作于2023年2月(d)無可行解

MaxZ=2x1+3x2x1+2x2

84x1

164x2

12

-2x1+x24x1、x2

0可行域?yàn)榭占€性規(guī)劃問題求解的

幾種可能結(jié)果第72頁，課件共156頁，創(chuàng)作于2023年2月圖解法的幾點(diǎn)結(jié)論:1、可行域是非空有界或無界的凸多邊形,也可能為空集。2、可行域?yàn)橛薪鐣r(shí)，一定有最優(yōu)解1）有唯一最優(yōu)解2）有兩個(gè)以上的最優(yōu)解（也必有無窮多個(gè)最優(yōu)解）3、可行域?yàn)闊o界時(shí)，可能有最優(yōu)解，也可能無最優(yōu)解1）有唯一最優(yōu)解2）有兩個(gè)以上的最優(yōu)解（也必有無窮多個(gè)最優(yōu)解）3）無界解4、可行域?yàn)榭占欢]有最優(yōu)解若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點(diǎn)得到。若兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則其連線上的所有點(diǎn)都是最優(yōu)解。第73頁，課件共156頁，創(chuàng)作于2023年2月練習(xí)：

用圖解法求解LP問題

MaxZ=34x1+40x24x1+6x2

482x1+2x2

182x1+x2

16x1、x2

0第74頁，課件共156頁，創(chuàng)作于2023年2月圖解法—（練習(xí)）

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第75頁，課件共156頁，創(chuàng)作于2023年2月圖解法—（練習(xí)）

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第76頁，課件共156頁，創(chuàng)作于2023年2月圖解法—（練習(xí)）

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第77頁，課件共156頁，創(chuàng)作于2023年2月圖解法—（練習(xí)）

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)第78頁，課件共156頁，創(chuàng)作于2023年2月圖解法—（練習(xí)）

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第79頁，課件共156頁，創(chuàng)作于2023年2月圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域?yàn)橥辜繕?biāo)函數(shù)不同時(shí)等值線的斜率不同最優(yōu)解在頂點(diǎn)產(chǎn)生

目標(biāo)函數(shù)等值線的斜率最優(yōu)解第80頁，課件共156頁，創(chuàng)作于2023年2月圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域?yàn)橥辜繕?biāo)函數(shù)不同時(shí)等值線的斜率不同最優(yōu)解在頂點(diǎn)產(chǎn)生

目標(biāo)函數(shù)等值線的斜率最優(yōu)解第81頁，課件共156頁，創(chuàng)作于2023年2月圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域?yàn)橥辜繕?biāo)函數(shù)不同時(shí)等值線的斜率不同最優(yōu)解在頂點(diǎn)產(chǎn)生

目標(biāo)函數(shù)等值線的斜率最優(yōu)解第82頁，課件共156頁，創(chuàng)作于2023年2月第三節(jié)單純形法原理

一、線性規(guī)劃問題解的概念標(biāo)準(zhǔn)型可行解:滿足AX=b,X>=0的解X稱為線性規(guī)劃問題的可行解。最優(yōu)解：使Z=CX達(dá)到最大值的可行解稱為最優(yōu)解。第83頁，課件共156頁，創(chuàng)作于2023年2月

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

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

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

——

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

——

非基變量。線性規(guī)劃問題解的概念第84頁，課件共156頁，創(chuàng)作于2023年2月例第85頁，課件共156頁，創(chuàng)作于2023年2月基、基變量、非基變量、基向量、非基向量、基解、基可行解、

可行基第86頁，課件共156頁，創(chuàng)作于2023年2月例行列式基變量非基變量基向量非基向量第87頁，課件共156頁，創(chuàng)作于2023年2月對(duì)應(yīng)于基B1的基解X1非基可行解第88頁，課件共156頁，創(chuàng)作于2023年2月例行列式基變量非基變量基變量非基變量第89頁，課件共156頁，創(chuàng)作于2023年2月對(duì)應(yīng)于基B2的基解X2基可行解第90頁，課件共156頁，創(chuàng)作于2023年2月

求解

線性規(guī)劃問題解的概念第91頁，課件共156頁，創(chuàng)作于2023年2月基解：稱上面求出的X解為基解。基可行解：非負(fù)的基解X稱為基可行解可行基：對(duì)應(yīng)基可行解的基稱為可行基線性規(guī)劃問題解的概念T基變量令可求出：第92頁，課件共156頁，創(chuàng)作于2023年2月

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

基可行解

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

最優(yōu)解？第93頁，課件共156頁，創(chuàng)作于2023年2月

例：求基解、基可行解、最優(yōu)解。線性規(guī)劃問題解的概念第94頁，課件共156頁，創(chuàng)作于2023年2月10051045Y

20452017Y

35005410Y

40550-120N5100-50415N652.5001.517.5Y

7540-3022N82430019

Y

是否基可行解最優(yōu)解線性規(guī)劃問題解的概念解：第95頁，課件共156頁，創(chuàng)作于2023年2月

：求基解、基可行解、最優(yōu)解。練習(xí)：線性規(guī)劃問題解的概念第96頁，課件共156頁，創(chuàng)作于2023年2月二、凸集及定點(diǎn)基本概念凸集：線性規(guī)劃問題的幾何意義第97頁，課件共156頁，創(chuàng)作于2023年2月

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

凸集線性規(guī)劃問題的幾何意義第98頁，課件共156頁，創(chuàng)作于2023年2月定理1:若線性規(guī)劃問題存在可行域,則其可行域:是凸集.三、基本定理證明:線性規(guī)劃問題的幾何意義第99頁，課件共156頁，創(chuàng)作于2023年2月

只要驗(yàn)證X在D中即可第100頁，課件共156頁，創(chuàng)作于2023年2月

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

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

對(duì)應(yīng)于可行域D的頂點(diǎn)。證明：反證法。分兩步。第101頁，課件共156頁，創(chuàng)作于2023年2月幾點(diǎn)結(jié)論：線性規(guī)劃問題的可行域是凸集。基可行解與可行域的頂點(diǎn)一一對(duì)應(yīng)，可行域有有限多個(gè)頂點(diǎn)。最優(yōu)解必在頂點(diǎn)上得到。第102頁，課件共156頁，創(chuàng)作于2023年2月有時(shí)目標(biāo)函數(shù)可能在多個(gè)頂點(diǎn)達(dá)到最大值。這時(shí)這些頂點(diǎn)的凸組合上也達(dá)到最大值。稱這種線性規(guī)劃問題有無限多個(gè)最優(yōu)值。第103頁，課件共156頁，創(chuàng)作于2023年2月四、單純形法迭代原理

1、初始基可行解的確定

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

若線性規(guī)劃問題

(1.20)

第104頁，課件共156頁，創(chuàng)作于2023年2月從Pj(j=1,2,…,n)中一般能直接觀察到存在一個(gè)初始可行基第105頁，課件共156頁，創(chuàng)作于2023年2月2、對(duì)所有約束條件是“≤”形式的不等式，可以利用化標(biāo)準(zhǔn)型的方法，在每個(gè)約束條件的左端加上一個(gè)松馳變量。經(jīng)整理，重新對(duì)xj及aij(i=1,2,…,m;j=1,2,…,n)進(jìn)行編號(hào)，則可得下列方程組第106頁，課件共156頁，創(chuàng)作于2023年2月3.對(duì)所有約束條件是“≥”形式的不等式及等式約束情況，若不存在單位矩陣時(shí)，就采取人造基的方法。即對(duì)不等式約束減去一個(gè)非負(fù)的剩余變量后，再加上一個(gè)非負(fù)的人工變量。對(duì)于等式約束加上一個(gè)非負(fù)的人工變量，總能得到一個(gè)單位矩陣。第107頁，課件共156頁，創(chuàng)作于2023年2月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第108頁，課件共156頁，創(chuàng)作于2023年2月顯然得到一個(gè)m×m單位矩陣第109頁，課件共156頁，創(chuàng)作于2023年2月以B作為可行基。移項(xiàng)得

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

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

第110頁，課件共156頁，創(chuàng)作于2023年2月

(i=1,2,…,m)(2)將（2）式代入目標(biāo)函數(shù)，整理后得

第111頁，課件共156頁，創(chuàng)作于2023年2月第112頁，課件共156頁，創(chuàng)作于2023年2月第113頁，課件共156頁，創(chuàng)作于2023年2月如果我們另行指定基矩陣，如將第j列作為基向量，第l列作為非基向量。l滿足如下條件：那么我們將得到一個(gè)新的解：第114頁，課件共156頁，創(chuàng)作于2023年2月1、最優(yōu)解的判別定理：若X(0)=(0,…,0)T為對(duì)應(yīng)于基B的一個(gè)基可行解，且對(duì)于一切j=m+1,…,n有σj≤0，則X(0)為最優(yōu)解，稱σj為檢驗(yàn)數(shù)。第115頁，課件共156頁，創(chuàng)作于2023年2月2、無窮多最優(yōu)解判別定理：若X(0)=(0,…,0)T為一個(gè)基可行解，對(duì)于一切j=m+1,…,n有σj≤0，又存在某個(gè)非基變量xm+k的檢驗(yàn)數(shù)σm+k=0,則線性規(guī)劃問題有無窮多最優(yōu)解。因?yàn)閷m+k將得到一個(gè)新的基可行解仍為最優(yōu)解,由于最優(yōu)解的凸組合還是最優(yōu)解,因此有無窮多最優(yōu)解.第116頁，課件共156頁，創(chuàng)作于2023年2月3、無界解判別定理:

若X(0)=(0,…,0)T為一個(gè)基可行解，有一個(gè)非基變量xm+k的檢驗(yàn)數(shù)σm+k>0,并且對(duì)i=1,2,…,m有ai,m+k≤0,那么該線性規(guī)劃問題具有無界解（或稱無最優(yōu)解）第117頁，課件共156頁，創(chuàng)作于2023年2月構(gòu)造一個(gè)新解：X（1），將其代入約束方程，滿足方程。將其代入目標(biāo)函數(shù)得到第118頁，課件共156頁，創(chuàng)作于2023年2月§1.4單純形法的計(jì)算步驟

與表格單純形法第119頁，課件共156頁，創(chuàng)作于2023年2月線性規(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第120頁，課件共156頁，創(chuàng)作于2023年2月為了便于迭代運(yùn)算，可將上述方程組寫成增廣矩陣-zx1x2

…xmxm+1

…xnb

第121頁，課件共156頁，創(chuàng)作于2023年2月若將z看成不參與基變換的基變量，它與x1，x2，…，xm的系數(shù)構(gòu)成一個(gè)基，這時(shí)可采用行初等變換將c1,c2,…,cm變換為零，使其對(duì)應(yīng)的系數(shù)矩陣為單位矩陣，第122頁，課件共156頁，創(chuàng)作于2023年2月得到-zx1x2

…xmxm+1

…xnb第123頁，課件共156頁，創(chuàng)作于2023年2月可根據(jù)上述增廣矩陣設(shè)計(jì)計(jì)算表如下：

第124頁，課件共156頁，創(chuàng)作于2023年2月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…第125頁，課件共156頁，創(chuàng)作于2023年2月4.2計(jì)算步驟

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

第128頁，課件共156頁，創(chuàng)作于2023年2月表1-3cj23000θcBxBBx1x2x3x4x50x30x40x5816121402041000100014-3-z023000第129頁，課件共156頁，創(chuàng)作于2023年2月(初始)單純形表的特點(diǎn)1、一個(gè)單純形表對(duì)應(yīng)于一個(gè)基可行解;2、一個(gè)單純形表中，基變量的系數(shù)矩陣是單位矩陣;3、一個(gè)單純形表中，目標(biāo)函數(shù)中基變量的系數(shù)為零，非基變量的系數(shù)為檢驗(yàn)數(shù)；4、檢驗(yàn)數(shù)的計(jì)算既可用公式法，也可用消去法；5、一個(gè)單純形表中，基可行解的基變量為右端常數(shù)；第130頁，課件共156頁，創(chuàng)作于2023年2月各非基變量的檢驗(yàn)數(shù)為

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

為換入變量。計(jì)算θθ=它所在行對(duì)應(yīng)的x5為換出變量，x2所在的列與x5所在的行交叉處[4]為主元素。第131頁，課件共156頁，創(chuàng)作于2023年2月以[4]為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，即初等變換，使P2變?yōu)椋?，0，1）T,在xB列中將x2替換x5,于是得到新表1-4

第132頁，課件共156頁，創(chuàng)作于2023年2月表1.4cj23000θcBxBBx1x2x3x4x50x30x40x22163140001100010-1/201/424--z92000-3/4第133頁，課件共156頁，創(chuàng)作于2023年2月由于檢驗(yàn)數(shù)有正數(shù)，還沒有得到最優(yōu)解，max(σ1,σ5)=max(2,-3/4)=2=σ1,則x1為換入變量，θ=則x3為換出變量。以1為主元數(shù)進(jìn)行旋轉(zhuǎn)運(yùn)算，得

第134頁，課件共156頁，創(chuàng)作于2023年2月表1-5cjcBxBb2x13x20x30x40x5θ2x10x43x22831000011-40010-1/221/4-412-z-1300-201/4第135頁，課件共156頁，創(chuàng)作于2023年2月由于檢驗(yàn)數(shù)有正數(shù)，還沒有得到最優(yōu)解，max(σ3,σ5)=max(-2,1/4)=1/4=σ5,則x5為換入變量，θ=則x4為換出變量。以2為主元數(shù)進(jìn)行旋轉(zhuǎn)運(yùn)算，得第136頁，課件共156頁，創(chuàng)作于2023年2月表1-6cjcBxBb2x13x20x30x40x5θ2x10x53x24421000010-21/21/41/2-1/8010-z-1400-1.5-1/80第137頁，課件共156頁，創(chuàng)作于2023年2月從表1-6看出檢驗(yàn)數(shù)都小于或等于零，于是對(duì)應(yīng)的基可行解X=(4,2,0,0,4)為最優(yōu)解,最優(yōu)值z(mì)=14.非基變量的檢驗(yàn)數(shù)都是正，因此有唯一最優(yōu)解。第138頁，課件共156頁，創(chuàng)作于2023年2月§5單純形法的進(jìn)一步討論第139頁，課件共156頁，創(chuàng)作于2023年2月5.1人工變量法5.1人工變量法設(shè)線性規(guī)劃問題的約束條件是

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

第140頁，課件共156頁，創(chuàng)作于2023年2月a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2………

……………

am1x1+am2x2+…+amnxn +xn+m=bmx1,x2,…,xn≥0,xn+1,xn+2,…,xn+m≥0第141頁，課件共156頁，創(chuàng)作于2023年2月以xn+1,xn+2,…,xn+m為基變量，則可得到m×m一個(gè)單位矩陣，l令非基變量x1,x2,…,xn為零，得到一個(gè)初始基可行解X(0)=(0,0,…,0,b1,b2,…,bm)T若經(jīng)過基變換后，得到的最終單純形表中當(dāng)所有的cj-zj≤0，基變量中不包含人工變量，就得到原問題的一個(gè)基可行解，否則，原問題無可行解。第142頁，課件共156頁，創(chuàng)作于2023年2月1、大M法

在一個(gè)線性規(guī)劃問題的約束條件中加入人工變量后，要求人工變量對(duì)目標(biāo)函數(shù)的取值無影響，為此可取人工變量在目標(biāo)函數(shù)中的系數(shù)為-M(M為非常大的正數(shù))，這樣目標(biāo)函數(shù)要實(shí)現(xiàn)最大化，人工變量只能取零，因此必須把人工變量從基變量中