MBA運(yùn)籌學(xué)培訓(xùn)課程

運(yùn)籌學(xué)北京理工大學(xué)管理與經(jīng)濟(jì)學(xué)院吳祈宗教授1

1、緒論

2、線性規(guī)劃

3、運(yùn)輸問題

4、動(dòng)態(tài)規(guī)劃

5、圖與網(wǎng)絡(luò)分析

6、排隊(duì)論

7、教學(xué)日歷運(yùn)籌學(xué)——目錄說明本教學(xué)課件是與教材緊密配合使用的，教材為：《運(yùn)籌學(xué)》楊民助編著西安交通大學(xué)出版社，2000年6月參考書：《運(yùn)籌學(xué)》清華大學(xué)出版社或其他的《運(yùn)籌學(xué)》方面本科教材的相關(guān)內(nèi)容下面所標(biāo)注的頁(yè)號(hào)，均為本課程教材的頁(yè)號(hào)。例如：p123表示第123頁(yè)p31-34表示從第31頁(yè)到第34頁(yè)2緒論

運(yùn)籌學(xué)（OperationalResearch)直譯為“運(yùn)作研究”運(yùn)籌學(xué)是運(yùn)用科學(xué)的方法（如分析、試驗(yàn)、量化等）來決定如何最佳地運(yùn)營(yíng)和設(shè)計(jì)各種系統(tǒng)的一門學(xué)科。運(yùn)籌學(xué)對(duì)經(jīng)濟(jì)管理系統(tǒng)中的人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。

運(yùn)籌學(xué)有廣泛應(yīng)用（可以自己找一些參考書看）運(yùn)籌學(xué)的產(chǎn)生和發(fā)展（可以自己找一些參考書看）3運(yùn)籌學(xué)解決問題的過程1）提出問題：認(rèn)清問題2）尋求可行方案：建模、求解3）確定評(píng)估目標(biāo)及方案的標(biāo)準(zhǔn)或方法、途徑4）評(píng)估各個(gè)方案：解的檢驗(yàn)、靈敏性分析等5）選擇最優(yōu)方案：決策6）方案實(shí)施：回到實(shí)踐中7）后評(píng)估：考察問題是否得到完滿解決1）2）3）：形成問題；4）5）分析問題：定性分析與定量分析。構(gòu)成決策。4運(yùn)籌學(xué)的分支線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃多目標(biāo)規(guī)劃隨機(jī)規(guī)劃模糊規(guī)劃等圖與網(wǎng)絡(luò)理論存儲(chǔ)論排隊(duì)論決策論對(duì)策論排序與統(tǒng)籌方法可靠性理論等5運(yùn)籌學(xué)在工商管理中的應(yīng)用生產(chǎn)計(jì)劃：生產(chǎn)作業(yè)的計(jì)劃、日程表的編排、合理下料、配料問題、物料管理等庫(kù)存管理：多種物資庫(kù)存量的管理，庫(kù)存方式、庫(kù)存量等運(yùn)輸問題：確定最小成本的運(yùn)輸線路、物資的調(diào)撥、運(yùn)輸工具的調(diào)度以及建廠地址的選擇等人事管理：對(duì)人員的需求和使用的預(yù)測(cè)，確定人員編制、人員合理分配，建立人才評(píng)價(jià)體系等市場(chǎng)營(yíng)銷：廣告預(yù)算、媒介選擇、定價(jià)、產(chǎn)品開發(fā)與銷售計(jì)劃制定等財(cái)務(wù)和會(huì)計(jì)：預(yù)測(cè)、貸款、成本分析、定價(jià)、證券管理、現(xiàn)金管理等***設(shè)備維修、更新，項(xiàng)目選擇、評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)與管理等6運(yùn)籌學(xué)方法使用情況(美1983)（%）7運(yùn)籌學(xué)方法在中國(guó)使用情況(隨機(jī)抽樣)（%）8運(yùn)籌學(xué)的推廣應(yīng)用前景據(jù)美勞工局1992年統(tǒng)計(jì)預(yù)測(cè):

運(yùn)籌學(xué)應(yīng)用分析人員需求從1990年到2005年的增長(zhǎng)百分比預(yù)測(cè)為73%,增長(zhǎng)速度排到各項(xiàng)職業(yè)的前三位.結(jié)論:運(yùn)籌學(xué)在國(guó)內(nèi)或國(guó)外的推廣前景是非常廣闊的工商企業(yè)對(duì)運(yùn)籌學(xué)應(yīng)用和需求是很大的在工商企業(yè)推廣運(yùn)籌學(xué)方面有大量的工作要做9學(xué)習(xí)運(yùn)籌學(xué)要把重點(diǎn)放在分析、理解有關(guān)的概念、思路上。在自學(xué)過程中，應(yīng)該多向自己提問，如一個(gè)方法的實(shí)質(zhì)是什么，為什么這樣做，怎么做等。自學(xué)時(shí)要掌握三個(gè)重要環(huán)節(jié)：1、認(rèn)真閱讀教材和參考資料，以指定教材為主，同時(shí)參考其他有關(guān)書籍。一般每一本運(yùn)籌學(xué)教材都有自己的特點(diǎn)，但是基本原理、概念都是一致的。注意主從，參考資料會(huì)幫助你開闊思路，使學(xué)習(xí)深入。但是，把時(shí)間過多放在參考資料上，會(huì)導(dǎo)致思路分散，不利于學(xué)好。2、要在理解了基本概念和理論的基礎(chǔ)上研究例題，注意例題是為了幫助你理解概念、理論的。作業(yè)練習(xí)的主要作用也是這樣，它同時(shí)還有讓你自己檢查自己學(xué)習(xí)的作用。因此，做題要有信心，要獨(dú)立完成，不要怕出錯(cuò)。因?yàn)?，整個(gè)課程是一個(gè)整體，各節(jié)內(nèi)容有內(nèi)在聯(lián)系，只要學(xué)到一定程度，知識(shí)融會(huì)貫通起來，你做題的正確性自己就有判斷。3、要學(xué)會(huì)做學(xué)習(xí)小結(jié)。每一節(jié)或一章學(xué)完后，必須學(xué)會(huì)用精煉的語(yǔ)言來該書所學(xué)內(nèi)容。這樣，你才能夠從較高的角度來看問題，更深刻的理解有關(guān)知識(shí)和內(nèi)容。這就稱作“把書讀薄”，若能夠結(jié)合自己參考大量文獻(xiàn)后的深入理解，把相關(guān)知識(shí)從更深入、廣泛的角度進(jìn)行論述，則稱之為“把書讀厚”在建數(shù)學(xué)模型時(shí)要結(jié)合實(shí)際應(yīng)用，要學(xué)會(huì)用計(jì)算機(jī)軟件解決問題。如何學(xué)習(xí)運(yùn)籌學(xué)課程返回目錄10各章節(jié)節(jié)的重重點(diǎn)、、難點(diǎn)點(diǎn)及及注意意事項(xiàng)項(xiàng)111、線線性性規(guī)規(guī)劃劃線性規(guī)規(guī)劃模模型：：目標(biāo)函函數(shù)：：Maxz=50x1+100x2約束條條件：：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0**看看p7--9例例1-1，1-2例1.某工廠廠在計(jì)計(jì)劃期期內(nèi)要要安排排甲、、乙兩兩種產(chǎn)產(chǎn)品的的生產(chǎn)產(chǎn)，已已知生生產(chǎn)單單位產(chǎn)產(chǎn)品所所需的的設(shè)備備臺(tái)時(shí)時(shí)及A、B兩種種原材材料的的消耗耗以及及資源源的限限制，，如下下表：：?jiǎn)栴}：：工廠廠應(yīng)分分別生生產(chǎn)多多少單單位甲甲、乙乙產(chǎn)品品才能能使工工廠獲獲利最最多？？121、線線性性規(guī)規(guī)劃劃（（續(xù)續(xù)1.1））1.1線線性規(guī)規(guī)劃的的概念念線性規(guī)規(guī)劃的的組成成：目標(biāo)函函數(shù)Maxf或或Minf約束條條件s.t.(subjectto)滿滿足足于決策變變量用用符符號(hào)來來表示示可控控制的的因素素一般形形式(p10--p11)目標(biāo)函函數(shù)：：Max（（Min））z=c1x1+c2x2+……+cnxn約束條條件：：s.t.a11x1+a12x2+……+a1nxn≤（（=,≥≥））b1a21x1+a22x2+……+a2nxn≤（（=,≥≥））b2………………am1x1+am2x2+……+amnxn≤（（=,≥≥））bmx1，x2，…，，xn≥0標(biāo)準(zhǔn)形形式(p11--p15，，例1-3)目標(biāo)標(biāo)函函數(shù)數(shù)：：Maxz=c1x1+c2x2+……+cnxn約束束條條件件：：s.t.a11x1+a12x2+……+a1nxn=b1a21x1+a22x2+……+a2nxn=b2…………………am1x1+am2x2+……+amnxn=bmx1，x2，……，，xn≥0**練練習(xí)習(xí)：：p68--70習(xí)習(xí)題題11-1，，1-2131、、線線性性規(guī)規(guī)劃劃（（續(xù)續(xù)1.2））1.2線線性性規(guī)規(guī)劃劃問問題題解解的的概概念念及及性性質(zhì)質(zhì)熟悉悉下下列列一一些些解解的的概概念念（（p15--16））可行行解解、、可可行行解解集集（（可可行行域域）），，最最優(yōu)優(yōu)解解、、最最優(yōu)優(yōu)值值，，基基、、基基變變量量、、非非基基變變量量，，基基本本解解、、基基本本可可行行解解，，可可行行基基、、最最優(yōu)優(yōu)基基。。圖解解方方法法及及各各有有關(guān)關(guān)概概念念的的意意義義（（p16--20））看：：圖圖解解法法步步驟驟，，例例1-4，，1-5，，1-6，，1-7，，1-8，，1-9下一一頁(yè)頁(yè)是是一一個(gè)個(gè)圖圖解解法法解解題題的的一一個(gè)個(gè)例例子子，，右右圖圖中中的的陰陰影影部部分分為為可可行行域域。。單純純形形法法的的理理論論基基礎(chǔ)礎(chǔ)（（p20--30））1.2.3段段要要求求看看懂懂，，了了解解如如何何直直接接通通過過對(duì)對(duì)約約束束矩矩陣陣的的分分析析求求出出基基本本可可行行解解1.2.4,1.2.5兩兩段段應(yīng)應(yīng)注注重重結(jié)結(jié)論論的的了了解解，，如如單單純純形形法法思思想想和和關(guān)關(guān)于于線線性性規(guī)規(guī)劃劃解解的的四四個(gè)個(gè)定理理，，而而對(duì)對(duì)證證明明過過程程則則可可根根據(jù)據(jù)自自己己的的數(shù)數(shù)學(xué)學(xué)基基礎(chǔ)礎(chǔ)來來掌掌握握：：基礎(chǔ)礎(chǔ)很很好好，，可可要要求求掌掌握握；；否否則則，，也也可可略略去去不不看看。。**習(xí)習(xí)題題：：p70習(xí)習(xí)題題11-3，，1-4141、、線線性性規(guī)規(guī)劃劃（（續(xù)續(xù)1.2））例1.目標(biāo)標(biāo)函函數(shù)數(shù)：：Maxz=50x1+100x2約束束條條件件：：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到到最最優(yōu)優(yōu)解解：：x1=50，，x2=250最優(yōu)優(yōu)目目標(biāo)標(biāo)值值z(mì)=27500151、、線線性性規(guī)規(guī)劃劃（（續(xù)續(xù)1.3））1.3單單純純形形法法利用用單單純純形形表表的的方方法法求求解解線線性性規(guī)規(guī)劃劃————重重點(diǎn)點(diǎn)(p30--451.3.1,1.3.2,1.3.3)此項(xiàng)項(xiàng)內(nèi)內(nèi)容容是是本本章章的的重重點(diǎn)點(diǎn)，，學(xué)學(xué)習(xí)習(xí)中中應(yīng)應(yīng)注注意意掌掌握握表表格格單單純純形形法法求求解解線線性性規(guī)規(guī)劃劃問問題題的的基基本本過過程程。。要要通通過過讀讀懂懂教教材材內(nèi)內(nèi)容容以以及及大大量量練練習(xí)習(xí)來來掌掌握握。。161、線線性規(guī)規(guī)劃劃（續(xù)續(xù)1.3）表格單純純形法(p40--p45)考慮：bi>0i=1,……,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2………………am1x1+am2x2+…+amnxn≤bmx1，x2，…，，xn≥0加入松弛弛變量：：Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2………………am1x1+am2x2+…+amnxn+xn+m=bmx1，x2，…，，xn，xn+1，…，，xn+m≥017顯然，xj=0j=1,……,n;xn+i=bii=1,…,m是基本可可行解對(duì)應(yīng)的基基是單位位矩陣。。以下是初初始單純純形表：：mm其中：f=-∑cn+ibij=cj-∑cn+iaij為檢驗(yàn)數(shù)數(shù)cn+i=0i=1,…,mi=1i=1an+i,i=1,an+i,j=0(j≠i)i,j=1,……,m1、線線性規(guī)規(guī)劃劃（續(xù)續(xù)1.3）181、線線性規(guī)規(guī)劃劃（續(xù)續(xù)1.3單純形形法解題題例）例1?；瘶?biāo)準(zhǔn)形形式：Maxz=50x1+100x2s.t.x1+x2+x3=3002x1+x2+x4=400x2+x5=250x1,x2,x3,x4,x5≥0最優(yōu)解x1=50x2=250x4=50（松松弛標(biāo)量量，表示示原料A有50個(gè)單位位的剩余余）19注意：?jiǎn)螁渭冃畏ǚㄖ校?、每一一步運(yùn)算算只能用用矩陣初初等行變變換；2、表中中第3列列的數(shù)總總應(yīng)保持持非負(fù)（（≥0）；3、當(dāng)所所有檢驗(yàn)驗(yàn)數(shù)均非非正（≤≤0））時(shí)，得得到最優(yōu)優(yōu)單純形形表。1、線線性規(guī)規(guī)劃劃（續(xù)續(xù)1.3）201、線線性規(guī)規(guī)劃劃（續(xù)續(xù)1.3）一般情況況的處理理及注意意事項(xiàng)的的強(qiáng)調(diào)（（p45--55）1.3.4段主主要是討討論初始始基本可可行解不不明顯時(shí)時(shí)，常用用的方法法。要弄弄清它的的原理，，并通過過例1-14~例例1-17掌握握這些方方法，同同時(shí)進(jìn)一一步熟悉悉用單純純形法解解題?？紤]一般般問題：：bi>0i=1,……,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………………am1x1+am2x2+…+amnxn=bmx1，x2，…，，xn≥0211、線線性規(guī)規(guī)劃劃（續(xù)續(xù)1.3）大M法：：引入人工工變量xn+i≥0i=1,…,m;充充分分大正數(shù)數(shù)M。。得得到到，Maxz=c1x1+c2x2+…+cnxn+Mxn+1+…+Mxn+ms.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2………………am1x1+am2x2+…+amnxn+xn+m=bmx1，x2，…，，xn，xn+1，…，，xn+m≥0顯然，xj=0j=1,……,n;xn+i=bii=1,……,m是基本可可行解對(duì)應(yīng)的基基是單位位矩陣。。結(jié)論：若若得到的的最優(yōu)解解滿足xn+i=0i=1,…,m則是原問問題的最最優(yōu)解；；否則，，原問題題無可行行解。221、線線性規(guī)規(guī)劃劃（續(xù)續(xù)1.3）兩階段法法：引入人工工變量xn+i≥0，，i=1,……,m；構(gòu)構(gòu)造，Maxz=-xn+1-xn+2-…-xn+ms.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2………………am1x1+am2x2+……+amnxn+xn+m=bmx1，x2，…，，xn，xn+1，…，，xn+m≥0第一階階段求求解上上述問問題：：顯然，，xj=0j=1,……,n;xn+i=bii=1,……,m是基本本可行行解對(duì)應(yīng)的的基是是單位位矩陣陣。結(jié)論：：若得得到的的最優(yōu)優(yōu)解滿滿足xn+i=0i=1,……,m則是原原問題題的基基本可可行解解；否否則，，原問問題無無可行行解。。得到原原問題題的基基本可可行解解后，，第二二階段段求解解原問問題。。231、線線性性規(guī)規(guī)劃劃（（續(xù)續(xù)1.3））例題題例：（（LP）Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20x1+2x2+4x3+x4=26x1,x2,x3,x4≥0大M法法問題題（LP-M））Maxz=5x1+2x2+3x3-x4-Mx5-Mx6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0兩階段段法：：第第一階階段問問題（（LP-1）Maxz=-x5-x6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0241、線線性性規(guī)規(guī)劃劃（（續(xù)續(xù)1.3））大M法例例大M法（LP-M）得到最優(yōu)解解：(25/3，10/3，，0，11)T最優(yōu)目標(biāo)值值：112/3251、線性性規(guī)劃劃（續(xù)續(xù)1.3））兩階段法法例第一階段（LP-1）得到原問題題的基本可可行解：(0，15/7，25/7，，52/7)T261、線性性規(guī)劃劃（續(xù)續(xù)1.3））兩階段法法例第二階段把基本可行行解填入表表中得到原問題題的最優(yōu)解解：(25/3，10/3，，0，11)T最優(yōu)目標(biāo)值值：112/3271、線性性規(guī)劃劃（續(xù)續(xù)1.3））1.3.5矩矩陣描述———此段段為選讀，，有困難者者可不看。。1.3.6段段單純形迭迭代過程中中的幾點(diǎn)注注意事項(xiàng)是是對(duì)有關(guān)內(nèi)內(nèi)容的強(qiáng)調(diào)調(diào)和補(bǔ)充，，要認(rèn)真學(xué)學(xué)習(xí)、理解解。**習(xí)題：：p70--71習(xí)習(xí)題11-5，1-6281.4線線性性規(guī)劃應(yīng)用用——建建模（p55--68）本節(jié)介紹了了些線性規(guī)規(guī)劃應(yīng)用的的例子，這這些例子從從多個(gè)方面面介紹建模模對(duì)未來是是很有用的的，應(yīng)認(rèn)真真對(duì)待。除了教材上上的例子之之外，還有有許多其它它應(yīng)用：*合理利利用線材問問題：如何何下料使用用材最少*配料問問題：在原原料供應(yīng)量量的限制下下如何獲取取最大利潤(rùn)潤(rùn)*投資問問題：從投投資項(xiàng)目中中選取方案案，使投資資回報(bào)最大大*產(chǎn)品生生產(chǎn)計(jì)劃：：合理利用用人力、物物力、財(cái)力力等，使獲獲利最大*勞動(dòng)力力安排：用用最少的勞勞動(dòng)力來滿滿足工作的的需要*運(yùn)輸問問題：如何何制定調(diào)運(yùn)運(yùn)方案，使使總運(yùn)費(fèi)最最小**下面是是一些建模模的例子，，有興趣者者，可作為為練習(xí)。這這些例子有有一定的難難度，做起起來會(huì)有一一些困難。。**習(xí)題：：p72--73習(xí)習(xí)題11-7，1-8，1-9，1-101、線性性規(guī)劃劃（續(xù)續(xù)1.4））返回目錄29例．某晝夜夜服務(wù)的公公交線路每每天各時(shí)間間段內(nèi)所需需司機(jī)和乘乘務(wù)人員數(shù)數(shù)如下：設(shè)司機(jī)和乘乘務(wù)人員分分別在各時(shí)時(shí)間段一開開始時(shí)上班班，并連續(xù)續(xù)工作八小小時(shí)，問該該公交線路路怎樣安排排司機(jī)和乘乘務(wù)人員，，既能滿足足工作需要要，又配備備最少司機(jī)機(jī)和乘務(wù)人人員?例：人力資資源分配的的問題30解：設(shè)xi表示第i班班次時(shí)開始始上班的司司機(jī)和乘務(wù)務(wù)人員數(shù),這樣我們們建立如下下的數(shù)學(xué)模模型。目標(biāo)函數(shù)：：Minx1+x2+x3+x4+x5+x6約束條件：：s.t.x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1,x2,x3,x4,x5,x6≥0例：人力資資源分配的的問題（續(xù)續(xù)）31例、明明興公司生生產(chǎn)甲、乙乙、丙三種種產(chǎn)品，都都需要經(jīng)過過鑄造、機(jī)機(jī)加工和裝裝配三個(gè)車車間。甲、、乙兩種產(chǎn)產(chǎn)品的鑄件件可以外包包協(xié)作，亦亦可以自行行生產(chǎn)，但但產(chǎn)品丙必必須本廠鑄鑄造才能保保證質(zhì)量。。數(shù)據(jù)如下下表。問：：公司為了了獲得最大大利潤(rùn)，甲甲、乙、丙丙三種產(chǎn)品品各生產(chǎn)多多少件？甲甲、乙兩種種產(chǎn)品的鑄鑄造中，由由本公司鑄鑄造和由外外包協(xié)作各各應(yīng)多少件件？例：生產(chǎn)計(jì)計(jì)劃的問題題32解：設(shè)x1,x2,x3分別為三道道工序都由由本公司加加工的甲、、乙、丙三三種產(chǎn)品的的件數(shù)，x4,x5分別為由外外協(xié)鑄造再再由本公司司機(jī)加工和和裝配的甲甲、乙兩種種產(chǎn)品的件件數(shù)。求xi的利潤(rùn)：利利潤(rùn)=售售價(jià)-各成本本之和可得到xi（i=1,2,3,4,5））的利潤(rùn)分分別為15、10、、7、13、9元。。這樣我們建建立如下的的數(shù)學(xué)模型型。目標(biāo)函數(shù)：：Max15x1+10x2+7x3+13x4+9x5約束條件：：s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0例：生產(chǎn)計(jì)計(jì)劃的問題題（續(xù)）33例、永久久機(jī)械廠生生產(chǎn)Ⅰ、ⅡⅡ、Ⅲ三種種產(chǎn)品，均均要經(jīng)過A、B兩兩道工序加加工。假設(shè)設(shè)有兩種規(guī)規(guī)格的設(shè)備備A1、A2能完成A工序；；有三種規(guī)規(guī)格的設(shè)備備B1、B2、B3能完成B工工序。Ⅰ可可在A、B的的任何規(guī)格的的設(shè)備上加工工；Ⅱ可在在任意規(guī)格的的A設(shè)備上加加工，但對(duì)B工序，只能能在B1設(shè)備上加工；；Ⅲ只能在A2與B2設(shè)備上加工；；數(shù)據(jù)如下表表。問：為使使該廠獲得最最大利潤(rùn)，應(yīng)應(yīng)如何制定產(chǎn)產(chǎn)品加工方案案？例：生產(chǎn)計(jì)劃劃的問題（續(xù)續(xù)）34解：設(shè)xijk表示第i種種產(chǎn)品，在在第j種種工序上的第第k種設(shè)設(shè)備上加工的的數(shù)量。利潤(rùn)=[（銷售單價(jià)價(jià)-原料料單價(jià)）*產(chǎn)產(chǎn)品件數(shù)]之和-（（每臺(tái)時(shí)的的設(shè)備費(fèi)用*設(shè)備實(shí)際使使用的總臺(tái)時(shí)時(shí)數(shù)）之和。。這樣我們建立立如下的數(shù)學(xué)學(xué)模型:Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123s.t.5x111+10x211≤6000（（設(shè)備A1）7x112+9x212+12x312≤10000（（設(shè)備A2）6x121+8x221≤4000（（設(shè)備B1）4x122+11x322≤7000（（設(shè)備B2）7x123≤4000（（設(shè)備B3）x111+x112-x121-x122-x123=0（ⅠⅠ產(chǎn)品在A、、B工序加工工的數(shù)量相等等）x211+x212-x221=0（ⅡⅡ產(chǎn)品在A、、B工序加工工的數(shù)量相等等）x312-x322=0（ⅢⅢ產(chǎn)品在A、、B工序加工工的數(shù)量相等等）xijk≥0,i=1,2,3;j=1,2;k=1,2,3例：生產(chǎn)計(jì)劃劃的問題（續(xù)續(xù)）35例、某工廠要要做100套套鋼架，每套套用長(zhǎng)為2.9m,2.1m,1.5m的圓鋼各一一根。已知原原料每根長(zhǎng)7.4m，，問：應(yīng)如何何下料，可使使所用原料最最?。拷猓涸O(shè)計(jì)計(jì)下列5種種下料方案案假設(shè)x1,x2,x3,x4,x5分別為上面前前5種方方案下料的原原材料根數(shù)。。這樣我們建建立如下的數(shù)數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5約束條件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0例：套裁下料料問題36例6．某工廠廠要用三種原原料1、2、、3混合調(diào)配配出三種不同例：配料問題題37例：配料問題題（續(xù)）解：設(shè)xij表示第i種種（甲、對(duì)于甲：x11，x12，x13；對(duì)于乙：x21，x22，x23；對(duì)于丙：x31，x32，x33；對(duì)于原料1：x11，x21，x31；對(duì)于原料2：x12，x22，x32；對(duì)于原料3：x13，x23，x33；目標(biāo)函數(shù)：利潤(rùn)最大，利潤(rùn)=收入-原料支出約束條件：規(guī)格要求4個(gè)；供應(yīng)量限制3個(gè)。38Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33s.t.0.5x11-0.5x12-0.5x13≥0（原原材料1不少少于50%））-0.25x11+0.75x12-0.25x13≤0（原原材料2不超超過25%））0.75x21-0.25x22-0.25x23≥0（原原材料1不少少于25%））-0.5x21+0.5x22-0.5x23≤0（原原材料2不超超過50%））x11+x21+x31≤100(供應(yīng)應(yīng)量限制）x12+x22+x32≤100(供應(yīng)應(yīng)量限制）x13+x23+x33≤60(供應(yīng)應(yīng)量限制）xij≥0,i=1,2,3;j=1,2,3例：配料問題題（續(xù)）39例8．某部門門現(xiàn)有資金200萬元，，今后五年內(nèi)內(nèi)考慮給以下下的項(xiàng)目投資資。已知：項(xiàng)項(xiàng)目A：從第一一年到第五年年每年年初都都可投資，當(dāng)當(dāng)年末能收回回本利110%；項(xiàng)目B：從第一年到第四年年每年年初都都可投資，次次年末能收回回本利125%，但規(guī)定定每年最大投投資額不能超過30萬元；項(xiàng)目目C：需在第第三年年初投投資，第五年年末能收回本本利140%，但規(guī)定最大投資額額不能超過80萬元；項(xiàng)項(xiàng)目D：需在在第二年年利155%，但規(guī)定最大投資額不能超過100萬元；據(jù)測(cè)定每萬元每次投資的風(fēng)險(xiǎn)指數(shù)如右表：?jiǎn)枺篴）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎(chǔ)上使得其投資總的風(fēng)險(xiǎn)系數(shù)為最小？解：1）確定決策變量量：連續(xù)投資資問題設(shè)xij(i=1-5，j=1、2、3、4)表示示第i年年初投資于A(j=1)、B(j=2)、C(j=3)、、D(j=4)項(xiàng)目的金金額。這樣我我們建立如下下的決策變量量：Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24例：投資問題題402）約束條件件：第一年：A當(dāng)當(dāng)年末可收回回投資，故第第一年年初應(yīng)應(yīng)把全部資金金投出去，于于是x11+x12=200；；第二年：B次次當(dāng)年末才可可收回投資故第三年：年初的資金為x21+x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初的資金為x31+x22，于是x41+x42=1.1x31+1.25x22；第五年：年初的資金為x41+x32，于是x51=1.1x41+1.25x32；B、C、D的投資限制：xi2≤30(I=1、2、3、4)，x33≤80，x24≤1003）目標(biāo)函數(shù)及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200

x21+x22+x24=1.1x11；

x31+x32+x33=1.1x21+1.25x12；

x41+x42=1.1x31+1.25x22；

x51=1.1x41+1.25x32；

xi2≤30(I=1、2、3、4)，x33≤80，x24≤100

xij≥0(i=1、2、3、4、5；j=1、2、3、4）

b)Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.x11+x12=200

x21+x22+x24=1.1x11；

x31+x32+x33=1.1x21+1.25x12；

x41+x42=1.1x31+1.25x22；

x51=1.1x41+1.25x32；

xi2≤30(I=1、2、3、4)，x33≤80，x24≤1001.1x51+1.25x42+1.4x33+1.55x24≥330

xij≥0(i=1、2、3、4、5；j=1、2、3、4）例：投資問題題（續(xù)）412、線性規(guī)劃劃問題的進(jìn)一一步研究（2.1）2.1對(duì)對(duì)偶原理1、對(duì)偶問題題：考慮前文例1若設(shè)備和原料料都用于外協(xié)協(xié)加工，工廠廠收取加工費(fèi)費(fèi)。試問：設(shè)設(shè)備工時(shí)和原原料A、B各各如何收費(fèi)費(fèi)才最有競(jìng)爭(zhēng)爭(zhēng)力？設(shè)y1，y2，y3分別為每設(shè)備備工時(shí)、原料A、B每單位的收收取費(fèi)用Maxz=50x1+100x2Minf=300y1+400y2+250y3s.t.x1+x2≤300s.t.y1+2y2+≥502x1+x2≤400（不少于甲產(chǎn)產(chǎn)品的利潤(rùn)））x2≤250y1+y2+y3≥100x1,x2≥0y1,y2,y3≥0422、對(duì)偶定義義對(duì)稱形式：互互為對(duì)偶(LP)Maxz=cTx(DP)Minf=bTys.t.Ax≤≤bs.t.ATy≥cx≥0y≥0“Max--≤””““Min--≥”一般形式：若一個(gè)問題的的某約束為等等式，那么對(duì)對(duì)應(yīng)的對(duì)偶問問題的相應(yīng)變變量無非負(fù)限限制；反之，，若一個(gè)問問題的某變量量無非負(fù)限制制，那么對(duì)應(yīng)應(yīng)的對(duì)偶問題題的相應(yīng)約束束為等式。2、線性規(guī)劃劃問題的進(jìn)一一步研究（2.1）433、對(duì)偶定理理（原問題題與對(duì)偶問題題解的關(guān)系））考慮（LP））和（DP））定理2-1（（弱對(duì)偶定定理）若x,y分分別為（LP）和（DP）的可行解解，那么cTx≤bTy。推論若（LP）可行，，那么（LP）無有限最最優(yōu)解的充分分必要條件是是（LD）無無可行解。定理2-2（（最優(yōu)性準(zhǔn)準(zhǔn)則定理）若若x,y分別為（（LP）和（（DP）的可可行解，且cTx=bTy，那么x,y分分別為（LP）和（DP）的最優(yōu)解解。定理2-3（（主對(duì)偶定定理）若（LP）和（DP）均可行行，那么（LP）和（DP）均有最最優(yōu)解，且最最優(yōu)值相等。。以上定理、推推論對(duì)任意形形式的相應(yīng)線線性規(guī)劃的對(duì)對(duì)偶均有效**習(xí)題：p99習(xí)習(xí)題22-12、線性規(guī)劃劃問題的進(jìn)一一步研究（2.1）444、影影子價(jià)價(jià)格——是是一一個(gè)向向量，，它的的分量量表示示最優(yōu)優(yōu)目標(biāo)標(biāo)值隨隨相應(yīng)應(yīng)資源源數(shù)量量變化化的變變化率率。若x*,y*分別為為（LP））和（（DP）的的最優(yōu)優(yōu)解，，那么，，cTx*=bTy*。根據(jù)f=bTy*=b1y1*+b2y2*++bmym*可知f/bi=yi*yi*表示bi變化1個(gè)單單位對(duì)對(duì)目標(biāo)標(biāo)f產(chǎn)產(chǎn)生的的影響響，稱稱yi*為bi的影子子價(jià)格格。注意：：若B是是最最優(yōu)基基，y*=(BT)-1cB為影子子價(jià)格格向量量。2、線線性規(guī)規(guī)劃問問題的的進(jìn)一一步研研究（（2.1））455、由由最優(yōu)優(yōu)單純純形表表求對(duì)對(duì)偶問問題最最優(yōu)解解第1章章例1?；瘶?biāo)準(zhǔn)準(zhǔn)形式式：Maxz=50x1+100x2s.t.x1+x2+x3=300，，2x1+x2+x4=400x2+x5=250，，x1,x2,x3,x4,x5≥0IOB=(p1,p4,p2)(BT)-1cBB-1最優(yōu)解解x1=50x2=250x4=50（松松弛標(biāo)標(biāo)量，，表示示原料料A有有50個(gè)單單位的的剩余余）影子價(jià)價(jià)格y1=50y2=0y3=50,B-1對(duì)應(yīng)的的檢驗(yàn)驗(yàn)數(shù)(BT)-1cB。2、線線性規(guī)規(guī)劃問問題的的進(jìn)一一步研研究（（2.1））462.2對(duì)對(duì)偶偶單純純形法法對(duì)偶單單純形形法在在什么么情況況下使使用：：應(yīng)用前前提：：有一一個(gè)基基，其其對(duì)應(yīng)應(yīng)的基基本解解滿足足①單單純形形表的的檢驗(yàn)驗(yàn)數(shù)行行全部部非正正（對(duì)對(duì)偶可可行））；②變變量取取值可可有負(fù)負(fù)數(shù)（（非可可行解解）。。**注注：通通過矩矩陣行行變換換運(yùn)算算，使使所有有相應(yīng)應(yīng)變量量取值值均為為非負(fù)負(fù)數(shù)即即得到到最優(yōu)優(yōu)單純純性表表。2、線線性規(guī)規(guī)劃問問題的的進(jìn)一一步研研究（（2.2））472、線線性規(guī)規(guī)劃問問題的的進(jìn)一一步研研究（（2.2））對(duì)偶單單純形形法求求解線線性規(guī)規(guī)劃問問題過過程：：1、建建立初初始對(duì)對(duì)偶單單純形形表，，對(duì)應(yīng)應(yīng)一個(gè)個(gè)基本本解，，所有有檢驗(yàn)驗(yàn)數(shù)均均非正正，轉(zhuǎn)轉(zhuǎn)2；；2、若若b’’≥0，，則得得到最最優(yōu)解解，停停止；；否則則，若若有bk<0則則選k行行的的基變變量為為出基基變量量，轉(zhuǎn)轉(zhuǎn)3；；3、若若所有有akj’≥0(j=1,2,……,n)，則則原問問題無無可行行解，，停止止；否否則，，若有有akj’<0則則選=min{j’/akj’┃akj’<0}=r’/akr’那么么r為為進(jìn)基基變量量，轉(zhuǎn)轉(zhuǎn)4；；4、以以akr’為轉(zhuǎn)轉(zhuǎn)軸元元，作作矩陣陣行變變換使使其變變?yōu)?，，該列列其他他元變變?yōu)?，，轉(zhuǎn)2。48例：求解線線性規(guī)規(guī)劃問問題：：Minf=2x1+3x2+4x3S.t.x1+2x2+x3≥32x1-x2+x3≥4x1,x2,x3≥0標(biāo)準(zhǔn)化化：MaxZ=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥02、線線性規(guī)規(guī)劃問問題的的進(jìn)一一步研研究（（2.2））49表格對(duì)對(duì)偶單單純形形法**習(xí)習(xí)題：：p100習(xí)習(xí)題22-2，2-32、線線性規(guī)規(guī)劃問問題的的進(jìn)一一步研研究（（2.2））502.3靈靈敏度度分析析進(jìn)一步步理解解最優(yōu)優(yōu)單純純形表表中各各元素素的含含義考慮問問題Maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn≤b1a21x1+a22x2+……+a2nxn≤b2………………am1x1+am2x2+……+amnxn≤bmx1，x2，…，，xn≥0引入m個(gè)個(gè)松松弛變變量后后，通通過計(jì)計(jì)算得得到最最優(yōu)單單純形形表。。應(yīng)-1-1能夠找找到最最優(yōu)基基B的逆逆矩陣陣B，，以以及BN，檢檢驗(yàn)數(shù)數(shù)等。。2、線線性規(guī)規(guī)劃問問題的的進(jìn)一一步研研究（（2.3））512、線線性規(guī)規(guī)劃問問題的的進(jìn)一一步研研究（（2.3））最優(yōu)單單純形形表B-1(BT)-1cBIO52價(jià)值系系數(shù)C發(fā)生生變化化：m考慮檢驗(yàn)數(shù)數(shù)j=cj-∑criarijj=1,2,……,ni=11、若ck是非基變量量的系數(shù)：：設(shè)ck變化為ck+ckk’=ck+ck-∑criarik=k+ck只要k’≤0，，即ck≤-k，則最優(yōu)解不不變；否則則，將最優(yōu)優(yōu)單純形表表中的檢驗(yàn)驗(yàn)數(shù)k用k’取代，繼續(xù)續(xù)單純形法法的表格計(jì)計(jì)算。例:MaxZ=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥02、線性規(guī)規(guī)劃問題的的進(jìn)一步研研究（2.3）53例：最優(yōu)單單純形表從表中看到到σ3=C3+ΔC3-（C2*a13+C1*a23）可得到ΔΔC3≤9/5時(shí)時(shí)，原最優(yōu)優(yōu)解不變。。2、線性規(guī)規(guī)劃問題的的進(jìn)一步研研究（2.3）542、若cs是基變量的的系數(shù)：設(shè)設(shè)cs變化為cs+cs，那么j’=cj-∑criarij-(cs+cs)asj=j-csasj，對(duì)所有非非基變量i≠s只要對(duì)所有有非基變量量j’≤0，，即j≤csasj，則最優(yōu)解不不變；否則則，將最優(yōu)優(yōu)單純形表表中的檢驗(yàn)驗(yàn)數(shù)j用j’取代，繼續(xù)續(xù)單純形法法的表格計(jì)計(jì)算。Max{j/asjasj>0}≤cs≤Min{j/asjasj<0}例:MaxZ=2x1+3x2+0x3+0x4+0x5S.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5≥02、線性規(guī)規(guī)劃問題的的進(jìn)一步研研究（2.3）55例、下表為為最優(yōu)單純純形表，考考慮基變量量系數(shù)c2發(fā)生變化從表中看到到σj=Cj-（C1*a1j+C5*a5j+（C2+ΔC2）*a2j）j=3、、4可得到-3≤≤ΔC2≤1時(shí)時(shí)，原原最優(yōu)解不不變。2、線性規(guī)規(guī)劃問題的的進(jìn)一步研研究（2.3）56右端項(xiàng)b發(fā)生變變化設(shè)分量br變化為br+br，根據(jù)第1章的討論論，最優(yōu)解解的基變量量xB=B-1b，那么只只要保持B-1(b+b)≥0，則最最優(yōu)基不變變，即基變變量保持，，只有值的的變化；否否則，需要要利用對(duì)偶偶單純形法法繼續(xù)計(jì)算算。對(duì)于問題(LP)Maxz=cTxs.t.Ax≤bx≥0最優(yōu)單純形形表中含有有B-1=（aij）i=1,……,m;j=n+1,……,n+m那么，新的的xi=(B-1b)i+brairi=1,…,m。。由此可得得，最優(yōu)基基不變的條條件是Max{-bi/airair>0}≤br≤Min{-bi/airair<0}2、線性規(guī)規(guī)劃問題的的進(jìn)一步研研究（2.3）57例、上例最最優(yōu)單純形形表如下00.250這里B-1=-20.51各各列分別別對(duì)應(yīng)b1、b2、b3的單一0.5-0.1250變化。因此此，設(shè)b1增加4，，則x1,x5,x2分別變?yōu)椋海?+0*4=4，4+(-2)*4=-4<0，，2+0.5*4=4用對(duì)偶單純純形法進(jìn)一一步求解，，可得：x*=(4,3,2,0,0)Tf*=172、線性規(guī)規(guī)劃問題的的進(jìn)一步研研究（2.3）58增加一個(gè)變變量增加變量xn+1則有相應(yīng)的的pn+1，cn+1。那么，計(jì)計(jì)算出B-1pn+1n+1=cn+1-∑criarin+1填入最優(yōu)單單純形表，，若n+1≤0則最優(yōu)解不不變；否則則，進(jìn)一步步用單純形形法求解。。例、前例增增加x6，p6=(2,6,3)T，c6=5。。計(jì)算得到到2、線性規(guī)規(guī)劃問題的的進(jìn)一步研研究（2.3）用單純形法法進(jìn)一步求求解，可得得：x*=(1,1.5,0,0,0,2)Tf*=16.559增加一個(gè)約約束增加約束一一個(gè)之后，，應(yīng)把最優(yōu)優(yōu)解帶入新新的約束，，若滿足則則最優(yōu)解不不變，否則則填入最優(yōu)優(yōu)單純形表表作為新的的一行，引引入1個(gè)新新的非負(fù)變變量（原約約束若是小小于等于形形式可引入入非負(fù)松弛弛變量，否否則引入非非負(fù)人工變變量），并并通過矩陣陣行變換把把對(duì)應(yīng)基變變量的元素素變?yōu)?，，進(jìn)一步用用單純形法法或?qū)ε紗螁渭冃畏ㄇ笄蠼?。例、前例增增?x1+2x2≤15，原原最優(yōu)解不不滿足這個(gè)個(gè)約束。于于是2、線性規(guī)規(guī)劃問題的的進(jìn)一步研研究（2.3）60A中元素發(fā)發(fā)生變化（只討論N中某某一列變化化情況）與增加變量量xn+1的情況類似似，假設(shè)pj變化。那那么，重新新計(jì)算出B-1pjj=cj-∑criarij填入最優(yōu)單單純形表，，若j≤0則最優(yōu)解不不變；否則則，進(jìn)一步步用單純形形法求解。。2、線性規(guī)規(guī)劃問題的的進(jìn)一步研研究（2.3）可得最優(yōu)解解：x*=(3.2,0.8,0,0,2.4)Tf*=15.2612、線性規(guī)規(guī)劃問題的的進(jìn)一步研研究（2.3）2.3靈靈敏度分分析(內(nèi)內(nèi)容，為重重點(diǎn))2.3.1Ci發(fā)生變化2.3.2Bj發(fā)生變化2.3.3增增加一個(gè)變變量2.3.4增增加一個(gè)約約束2.3.5A中元素發(fā)發(fā)生變化**習(xí)題：：p100習(xí)習(xí)題22-4返回目錄623.1運(yùn)運(yùn)輸問問題模型與與性質(zhì)運(yùn)輸模型例、某公司從兩兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往往三個(gè)銷地地B1、B2、B3，各產(chǎn)地的的產(chǎn)量、各各銷地的銷銷量和各產(chǎn)產(chǎn)地運(yùn)往個(gè)個(gè)銷地每件件物品的運(yùn)運(yùn)費(fèi)如下表表所示，問問：應(yīng)如何何調(diào)運(yùn)可使使總運(yùn)輸費(fèi)費(fèi)用最?。?？3、運(yùn)輸輸問問題（（3.1）63解：產(chǎn)銷平衡衡問題：：總產(chǎn)產(chǎn)量=總銷銷量設(shè)xij為從產(chǎn)地地Ai運(yùn)往銷地地Bj的運(yùn)輸量量，得到到下列運(yùn)運(yùn)輸量表表：Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1、、2；j=1、2、3））3、運(yùn)輸輸問問題（（3.1）64系數(shù)矩陣陣111000000111100100010010001001特點(diǎn)：1、共有m+n行，分別別表示產(chǎn)地和和銷地；mn列分別表示示各變量；2、每列只有有兩個(gè)1，，其余為0，分別表示示只有一個(gè)產(chǎn)產(chǎn)地和一個(gè)銷銷地被使用；；3、運(yùn)輸問問題（3.1）65設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得得到下列一般般運(yùn)輸量問題題的模型：mnMinf=cijxiji=1j=ins.t.xij=sii=1,2,…,mj=1mxij=djj=1,2,…,ni=1xij≥0(i=1,2,……,m;j=1,2,…,n)一般運(yùn)輸模型型：產(chǎn)銷平衡A1、A2、…、Am表示某物資的的m個(gè)產(chǎn)地；；B1、B2、…、Bn表示某物質(zhì)的的n個(gè)銷地；；si表示產(chǎn)地Ai的產(chǎn)量；dj表示銷地Bj的銷量；cij表示把物資為為從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價(jià)。。3、運(yùn)輸問問題（3.1續(xù)）663、運(yùn)輸問問題（3.1續(xù)）變化：1）有時(shí)目標(biāo)標(biāo)函數(shù)求最大大，如求利潤(rùn)潤(rùn)最大或營(yíng)業(yè)業(yè)額最大等；；2）當(dāng)某些運(yùn)運(yùn)輸線路上的的能力有限制制時(shí)，模型中中可直接加入入（等式或不不等式）約束束；3）產(chǎn)銷不平673、運(yùn)輸問問題（求解思路是基本可行解最優(yōu)否結(jié)束否換基運(yùn)輸問題基變變量的特點(diǎn)*運(yùn)輸問問題的基變量量共有m+n-1個(gè)，A的秩為m+n-1。*運(yùn)輸問問題的m+n-1個(gè)變量量構(gòu)成基變量量的充分必要要條件是不含含閉回路。要弄清下列概概念：閉回回路、閉回路路的頂點(diǎn)。683.2運(yùn)運(yùn)輸問題的表表上作業(yè)法——本章重重點(diǎn)1、初始基本本可行解的確確定：（1）西北角角法：從西北角（左左上角）格開開始，在格內(nèi)內(nèi)的右下角標(biāo)標(biāo)上允許取得的最大數(shù)。然然后按行（列列）標(biāo)下一格格的數(shù)。若某某行（列）的的產(chǎn)量（銷量量）已滿足，，則把該行（（列）的其他他格劃去。如如此進(jìn)行下去去，直至得到到一個(gè)基本可可行解。（2）最小元元素法：從運(yùn)價(jià)最小的的格開始，在在格內(nèi)的右下下角標(biāo)上允許取得的最大數(shù)。然然后按運(yùn)價(jià)從從小到大順序序填數(shù)。若某某行（列）的的產(chǎn)量（銷量量）已滿足，，則把該行（（列）的其他他格劃去。如如此進(jìn)行下去去，直至得到到一個(gè)基本可可行解。注：應(yīng)用西北角法法和最小元素素法，每次填填完數(shù)，都只只劃去一行或或一列，只有有最后一個(gè)元元例外（同時(shí)時(shí)劃去一行和和一列）。當(dāng)當(dāng)填上一個(gè)數(shù)數(shù)后行、列同同時(shí)飽和時(shí)，，也應(yīng)任意劃劃去一行（列列）在保留的的列（行）任任意沒被劃去去的格內(nèi)標(biāo)一一個(gè)0。3、運(yùn)輸問問題（3.2）69*3、運(yùn)輸問問題（3.2）70*3、運(yùn)輸問712、最優(yōu)性檢檢驗(yàn)：因?yàn)榍笞钚。?，?dāng)所有檢驗(yàn)驗(yàn)數(shù)均大于等等于0時(shí)為最最優(yōu)解（1）位勢(shì)法法求檢驗(yàn)數(shù)：：位勢(shì)：設(shè)對(duì)應(yīng)基變量量xij的m+n-1個(gè)ij，存在ui,vj滿足ui+vj=cij，i=1,…,m;j=1,…,n.稱稱這些ui,vj為該基本可行行解對(duì)應(yīng)的位位勢(shì)。由于有m+n個(gè)個(gè)變量（ui,vj），m+n-1個(gè)方程（（基變量個(gè)數(shù)數(shù)），故有一一個(gè)自由變量量，位勢(shì)不唯唯一。利用位勢(shì)求檢檢驗(yàn)數(shù)：ij=cij-ui-vji=1,…,m;j=1,…,n3、運(yùn)輸問問題（3.2）72前例，位勢(shì)法法求檢驗(yàn)數(shù)：：step1從任意基變量量對(duì)應(yīng)的cij開始，任取ui或vj，然后利用公公式cij=ui+vj依次找出m+n個(gè)個(gè)ui,vj；從c14=10開開始step2計(jì)算非基變量量的檢驗(yàn)數(shù)ij=cij-ui-vj；填入圓圈內(nèi)3、運(yùn)輸問問題（3.2）733、主元變換換：（1）選負(fù)檢檢驗(yàn)數(shù)中最小小者rk，那么xrk為主元，作為為進(jìn)基變量；；（上頁(yè)圖中x24）（2）以為xrk起點(diǎn)找一條閉閉回路，除xrk外其余頂點(diǎn)必必須為基變量量格；（上頁(yè)圖中藍(lán)藍(lán)色回路））（3）為閉回回路的每一個(gè)個(gè)頂點(diǎn)標(biāo)號(hào)，，xrk為1，沿一一個(gè)方向依次次給各頂點(diǎn)標(biāo)標(biāo)號(hào)；（4）求=min{xijxij對(duì)應(yīng)閉回路上上的偶數(shù)標(biāo)號(hào)號(hào)格}=xpq那么確確定xpq為出基基變量量，為調(diào)整整量；；（5））對(duì)閉閉回路路的各各奇標(biāo)標(biāo)號(hào)頂頂點(diǎn)xij+，對(duì)各各偶標(biāo)標(biāo)號(hào)頂頂點(diǎn)xij-，特別別xpq-=0，變?yōu)闉榉腔兞苛浚?、運(yùn)運(yùn)輸輸問問題題（3.2）重復(fù)2、3步，，直到到所有有檢驗(yàn)驗(yàn)數(shù)均均非負(fù)負(fù)，得得到最最優(yōu)解解。74主元變變換：：由前面面得到到=1，于是是3、運(yùn)運(yùn)輸輸問問題題（3.2）ij≥0，得得到最最優(yōu)解解x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其其余余xij=0;最優(yōu)費(fèi)費(fèi)用：：f*=3*5+10*2+1*3+8*1+4*6+5*3=85**習(xí)習(xí)題：：p123習(xí)習(xí)題33-1,3-2753.3產(chǎn)產(chǎn)銷銷不平平衡的的運(yùn)輸輸問題題1、產(chǎn)產(chǎn)量大大于銷銷量例例、、某公司司從兩兩個(gè)產(chǎn)產(chǎn)地A1、A2將物品品運(yùn)往往三個(gè)個(gè)銷地地B1、B2、B3，各產(chǎn)產(chǎn)地的的產(chǎn)量量、各各銷地地的銷銷量和和各產(chǎn)產(chǎn)地運(yùn)運(yùn)往個(gè)個(gè)銷地地每件件物品品的運(yùn)運(yùn)費(fèi)如如下表表所示示，問問：應(yīng)應(yīng)如何何調(diào)運(yùn)運(yùn)可使使總運(yùn)運(yùn)輸費(fèi)費(fèi)用最最??？？解：增加加一個(gè)個(gè)虛設(shè)設(shè)的銷銷地運(yùn)運(yùn)輸費(fèi)費(fèi)用為為03、運(yùn)運(yùn)輸輸問問題題（3.3）762、銷銷量大大于產(chǎn)產(chǎn)量例、某公司司從兩兩個(gè)產(chǎn)產(chǎn)地A1、A2將物品品運(yùn)往往三個(gè)個(gè)銷地地B1、B2、B3，各產(chǎn)產(chǎn)地的的產(chǎn)量量、各各銷地地的銷銷量和和各產(chǎn)產(chǎn)地運(yùn)運(yùn)往個(gè)個(gè)銷地地每件件物品品的運(yùn)運(yùn)費(fèi)如如下表表所示示，問問：應(yīng)應(yīng)如何何調(diào)運(yùn)運(yùn)可使使總運(yùn)運(yùn)輸費(fèi)費(fèi)用最最?。?？解：增加加一個(gè)個(gè)虛設(shè)設(shè)的產(chǎn)產(chǎn)地運(yùn)運(yùn)輸費(fèi)費(fèi)用為為03、運(yùn)運(yùn)輸輸問問題題（3.3）77下面給給出一一些例例題，，可作作為建建模的的練習(xí)習(xí)：例、石家莊莊北方方研究究院有有一、、二、、三，，三個(gè)個(gè)區(qū)。。每年年分別別需要要用煤煤3000、1000、、2000噸，，由河河北臨臨城、、山西西盂縣縣兩處處煤礦礦負(fù)責(zé)責(zé)供應(yīng)應(yīng)，價(jià)價(jià)格、、質(zhì)量量相同同。供供應(yīng)能能力分分別為為1500、4000噸噸，運(yùn)運(yùn)價(jià)如如下表表。由由于需需大于于供，，經(jīng)院院研究究決定定一區(qū)區(qū)供應(yīng)應(yīng)量可可減少少0--200噸，，二區(qū)區(qū)必須須滿足足需求求量，，三區(qū)區(qū)供應(yīng)應(yīng)量不不少于于1700噸，，試求求總費(fèi)費(fèi)用為為最低低的調(diào)調(diào)運(yùn)方方案。。3、運(yùn)運(yùn)輸輸問問題題（例例題））78解：根據(jù)題題意，，作出出產(chǎn)銷銷平衡衡與運(yùn)運(yùn)價(jià)表表：取M代代表一一個(gè)很很大的的正數(shù)數(shù)，其其作用用是強(qiáng)強(qiáng)迫相相應(yīng)的的x31、x33、x34取值為為0。。3、運(yùn)運(yùn)輸輸問問題題（例例題））79例、設(shè)有A、B、C三個(gè)個(gè)化肥肥廠供供應(yīng)1、2、3、4四個(gè)個(gè)地區(qū)區(qū)的農(nóng)農(nóng)用化化肥。。假設(shè)設(shè)效果果相同同，有有關(guān)數(shù)數(shù)據(jù)如如下表表。試試求總總費(fèi)用用為最最低的的化肥肥調(diào)撥撥方案案。3、運(yùn)運(yùn)輸輸問問題題（例例題））80解：根據(jù)題意意，作出出產(chǎn)銷平平衡與運(yùn)運(yùn)價(jià)表：：最低要求求必須滿滿足，因因此把相相應(yīng)的虛虛設(shè)產(chǎn)地地運(yùn)費(fèi)取取為M，而而最高要要求與最最低要求求的差允允許按需需要安排排，因此此把相應(yīng)應(yīng)的虛設(shè)設(shè)產(chǎn)地運(yùn)運(yùn)費(fèi)取為為0。。對(duì)應(yīng)應(yīng)4””的銷量量50是考考慮問題題本身適適當(dāng)取的的數(shù)據(jù)，，根據(jù)產(chǎn)產(chǎn)銷平衡衡要求確確定D的產(chǎn)量量為50。3、運(yùn)輸輸問問題（（例題））81例、某廠按合合同規(guī)定定須于當(dāng)當(dāng)年每個(gè)個(gè)季度末末分別提提供10、15、25、20臺(tái)同一一規(guī)格的的柴油機(jī)機(jī)。已知知該廠各各季度的的生產(chǎn)能能力及生生產(chǎn)每臺(tái)臺(tái)柴油機(jī)機(jī)的成本本如下表表。如果果生產(chǎn)出出來的柴柴油機(jī)當(dāng)當(dāng)季不交交貨，每每臺(tái)每積積壓一個(gè)個(gè)季度需需儲(chǔ)存、、維護(hù)等等費(fèi)用0.15萬元。。試求在在完成合合同的情情況下，，使該廠廠全年生生產(chǎn)總費(fèi)費(fèi)用為最最小的決決策方案案。3、運(yùn)輸輸問問題（（例題））82解：設(shè)xij為第i季度度生產(chǎn)的的第j季度度交貨的的柴油機(jī)機(jī)數(shù)目，，那末應(yīng)應(yīng)滿足：：交貨：x11=10生生產(chǎn)：x11+x12+x13+x14≤25x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10把第i季度度生產(chǎn)的的柴油機(jī)機(jī)數(shù)目看看作第i個(gè)個(gè)生產(chǎn)廠廠的產(chǎn)量量；把第第j季季度交交貨的柴柴油機(jī)數(shù)數(shù)目看作作第j個(gè)銷銷售點(diǎn)的的銷量；；成本加加儲(chǔ)存、、維護(hù)等等費(fèi)用看看作運(yùn)費(fèi)費(fèi)?？蓸?gòu)構(gòu)造下列列產(chǎn)銷平平衡問題題：目標(biāo)函數(shù)數(shù)：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x443、運(yùn)輸輸問問題（（例題））83例、光明儀器器廠生產(chǎn)產(chǎn)電腦繡繡花機(jī)是是以產(chǎn)定定銷的。。已知1至6月月份各月月的生產(chǎn)產(chǎn)能力、、合同銷銷量和單單臺(tái)電腦腦繡花機(jī)機(jī)平均生生產(chǎn)費(fèi)用用見下表表已知上年年末庫(kù)存存103臺(tái)繡花花機(jī)，如如果當(dāng)月月生產(chǎn)出出來的機(jī)機(jī)器當(dāng)月月不交貨貨，則需需要運(yùn)到到分廠庫(kù)庫(kù)房，每每臺(tái)增加加運(yùn)輸成成本0.1萬元元,每臺(tái)臺(tái)機(jī)器每每月的平平均倉(cāng)儲(chǔ)儲(chǔ)費(fèi)、維