運籌學-運籌學完整

運籌學

(OperationsResearch)任課教師：黃得建開課單位：理工學院聯(lián)系方式：

E-mail:經濟學核心課程6/2/2023運籌學--運籌學完整緒論（1）運籌學簡述（2）運籌學的主要內容（3）本課程的教材及參考書（4）本課程的特點和要求（5）本課程授課方式與考核（6）運籌學在工商管理中的應用本章主要內容：6/2/2023運籌學--運籌學完整運籌學簡述運籌學（OperationsResearch） 系統(tǒng)工程的最重要的理論基礎之一，在美國有人把運籌學稱之為管理科學(ManagementScience)。運籌學所研究的問題，可簡單地歸結為一句話：“依照給定條件和目標，從眾多方案中選擇最佳方案”故有人稱之為最優(yōu)化技術。6/2/2023運籌學--運籌學完整運籌學簡述運籌學的歷史“運作研究(OperationalResearch)小組”:解決復雜的戰(zhàn)略和戰(zhàn)術問題。例如：如何合理運用雷達有效地對付德軍的空襲對商船如何進行編隊護航，使船隊遭受德國潛艇攻擊時損失最少；在各種情況下如何調整反潛深水炸彈的爆炸深度，才能增加對德國潛艇的殺傷力等。6/2/2023運籌學--運籌學完整運籌學的主要內容數學規(guī)劃（線性規(guī)劃、整數規(guī)劃、目標規(guī)劃、動態(tài)規(guī)劃等）圖論存儲論排隊論對策論排序與統(tǒng)籌方法決策分析6/2/2023運籌學--運籌學完整本課程的教材及參考書選用教材《運籌學基礎及應用》胡運權主編（第5版）高等教育出版社參考教材《運籌學教程》胡運權主編（第2版）清華出版社《管理運籌學》韓伯棠主編（第2版）高等教育出版社《運籌學》(修訂版)錢頌迪主編清華出版社6/2/2023運籌學--運籌學完整本課程的特點和要求先修課：高等數學，基礎概率、線性代數特點：系統(tǒng)整體優(yōu)化；多學科的配合；模型方法的應用運籌學的研究的主要步驟：真實系統(tǒng)系統(tǒng)分析問題描述模型建立與修改模型求解與檢驗結果分析與實施數據準備6/2/2023運籌學--運籌學完整本課程授課方式與考核學科總成績平時成績（40％）課堂考勤（50％）平時作業(yè)（50％）期末成績（60％）講授為主，結合習題作業(yè)6/2/2023運籌學--運籌學完整運籌學在工商管理中的應用運籌學在工商管理中的應用涉及幾個方面：生產計劃運輸問題人事管理庫存管理市場營銷財務和會計另外，還應用于設備維修、更新和可靠性分析，項目的選擇與評價，工程優(yōu)化設計等。6/2/2023運籌學--運籌學完整Chapter1線性規(guī)劃

(LinearProgramming)LP的數學模型圖解法單純形法單純形法的進一步討論－人工變量法LP模型的應用本章主要內容：6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型1.規(guī)劃問題生產和經營管理中經常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題：（1）當任務或目標確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設備、原標材料、人工、時間等）去完成確定的任務或目標（2）在一定的資源條件限制下，如何組織安排生產獲得最好的經濟效益（如產品量最多、利潤最大.）6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型例1.1如圖所示，如何截取x使鐵皮所圍成的容積最大？xa6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型例1.2某企業(yè)計劃生產甲、乙兩種產品。這些產品分別要在A、B、C、D、四種不同的設備上加工。按工藝資料規(guī)定，單件產品在不同設備上加工所需要的臺時如下表所示，企業(yè)決策者應如何安排生產計劃，使企業(yè)總的利潤最大？設備產品ABCD利潤（元）甲21402乙22043有效臺時12816126/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型解：設x1、x2分別為甲、乙兩種產品的產量，則數學模型為：maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤126/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型2.線性規(guī)劃的數學模型由三個要素構成決策變量Decisionvariables目標函數Objectivefunction約束條件Constraints其特征是：（1）問題的目標函數是多個決策變量的線性函數，通常是求最大值或最小值；（2）問題的約束條件是一組多個決策變量的線性不等式或等式。

怎樣辨別一個模型是線性規(guī)劃模型？

6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型目標函數：約束條件：3.線性規(guī)劃數學模型的一般形式簡寫為：6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型向量形式：其中：6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型矩陣形式：其中：6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型3.線性規(guī)劃問題的標準形式特點：(1)目標函數求最大值（有時求最小值）(2)約束條件都為等式方程，且右端常數項bi都大于或等于零(3)決策變量xj為非負。6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型（2）如何化標準形式目標函數的轉換如果是求極小值即，則可將目標函數乘以(-1)，可化為求極大值問題。也就是：令，可得到上式。即

若存在取值無約束的變量，可令其中：變量的變換6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型約束方程的轉換：由不等式轉換為等式。稱為松弛變量稱為剩余變量變量的變換可令，顯然6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型例1.3將下列線性規(guī)劃問題化為標準形式用替換，且解:（１）因為x3無符號要求，即x3取正值也可取負值，標準型中要求變量非負，所以6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型(2)第一個約束條件是“≤”號，在“≤”左端加入松馳變量x4，x4≥0,化為等式；(3)第二個約束條件是“≥”號，在“≥”左端減去剩余變量x5，x5≥0；(4)第3個約束方程右端常數項為-5，方程兩邊同乘以(-1),將右端常數項化為正數；(5)目標函數是最小值，為了化為求最大值，令z′=-z,得到maxz′=-z，即當z達到最小值時z′達到最大值，反之亦然;6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型標準形式如下：6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型4.線性規(guī)劃問題的解線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個解，使目標函數(1)達到最大值。6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型

可行解：滿足約束條件②、③的解為可行解。所有可行解的集合為可行域。

最優(yōu)解：使目標函數達到最大值的可行解。

基：設A為約束條件②的m×n階系數矩陣(m<n)，其秩為m，B是矩陣A中m階滿秩子矩陣（∣B∣≠0），稱B是規(guī)劃問題的一個基。設：稱B中每個列向量Pj(j=12……m)為基向量。與基向量Pj

對應的變量xj為基變量。除基變量以外的變量為非基變量。6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型

基解：某一確定的基B，令非基變量等于零，由約束條件方程②解出基變量，稱這組解為基解。在基解中變量取非0值的個數不大于方程數m，基解的總數不超過

基可行解：滿足變量非負約束條件的基本解，簡稱基可行解?？尚谢簩诨尚薪獾幕Q為可行基。非可行解可行解基解基可行解6/2/2023運籌學--運籌學完整線性規(guī)劃問題的數學模型例1.4求線性規(guī)劃問題的所有基矩陣。解:約束方程的系數矩陣為2×5矩陣r(A)=2，2階子矩陣有10個，其中基矩陣只有9個，即6/2/2023運籌學--運籌學完整圖解法線性規(guī)劃問題的求解方法一般有兩種方法圖解法單純形法兩個變量、直角坐標三個變量、立體坐標適用于任意變量、但必需將一般形式變成標準形式下面我們分析一下簡單的情況——只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。6/2/2023運籌學--運籌學完整圖解法maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2

≥3.8s.t.X1+1.9X2≤10.2X1-1.9X2≤-3.8X1，X2≥0例1.5用圖解法求解線性規(guī)劃問題6/2/2023運籌學--運籌學完整圖解法x1x2oX1-1.9X2=3.8(≥)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≤)X1+1.9X2=10.2(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2X1+X2

（7.6，2）DmaxZminZ此點是唯一最優(yōu)解，且最優(yōu)目標函數值maxZ=17.2可行域maxZ=2X1+X26/2/2023運籌學--運籌學完整圖解法maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZ（3.8，4）34.2=3X1+5.7X2

藍色線段上的所有點都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標函數值maxZ=34.2是唯一的?？尚杏?/2/2023運籌學--運籌學完整圖解法minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此點是唯一最優(yōu)解6/2/2023運籌學--運籌學完整圖解法246x1x2246無界解(無最優(yōu)解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ6/2/2023運籌學--運籌學完整x1x2O10203040102030405050無可行解(即無最優(yōu)解)maxZ=3x1+4x2例1.76/2/2023運籌學--運籌學完整圖解法 學習要點： 1.通過圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解） 2.作圖的關鍵有三點： (1)可行解區(qū)域要畫正確 (2)目標函數增加的方向不能畫錯 (3)目標函數的直線怎樣平行移動6/2/2023運籌學--運籌學完整單純形法基本原理凸集：如果集合C中任意兩個點X1、X2，其連線上的所有點也都是集合C中的點，稱C為凸集。凸集凸集不是凸集頂點6/2/2023運籌學--運籌學完整單純形法基本原理定理1：若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。定理2：線性規(guī)劃問題的基可行解X對應可行域(凸集)的頂點。定理3：若問題存在最優(yōu)解，一定存在一個基可行解是最優(yōu)解。（或在某個頂點取得）6/2/2023運籌學--運籌學完整單純形法的計算步驟單純形法的思路找出一個初始可行解是否最優(yōu)轉移到另一個基本可行解（找出更大的目標函數值）最優(yōu)解是否循環(huán)核心是：變量迭代結束6/2/2023運籌學--運籌學完整單純形法的計算步驟單純形表6/2/2023運籌學--運籌學完整單純形法的計算步驟例1.8用單純形法求下列線性規(guī)劃的最優(yōu)解解：1）將問題化為標準型，加入松馳變量x3、x4則標準型為:6/2/2023運籌學--運籌學完整單純形法的計算步驟2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj3400θicB基bx1x2x3x40x34021100x43013013400檢驗數6/2/2023運籌學--運籌學完整單純形法的計算步驟3）進行最優(yōu)性檢驗如果表中所有檢驗數，則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。4）從一個基可行解轉換到另一個目標值更大的基可行解，列出新的單純形表確定換入基的變量。選擇，對應的變量xj作為換入變量，當有一個以上檢驗數大于0時，一般選擇最大的一個檢驗數，即：，其對應的xk作為換入變量。確定換出變量。根據下式計算并選擇θ

，選最小的θ對應基變量作為換出變量。 6/2/2023運籌學--運籌學完整單純形法的計算步驟用換入變量xk替換基變量中的換出變量，得到一個新的基。對應新的基可以找出一個新的基可行解，并相應地可以畫出一個新的單純形表。5）重復3）、4）步直到計算結束為止。 6/2/2023運籌學--運籌學完整單純形法的計算步驟cj3400θicB基變量bx1x2x3x40x34021100x430130134000x34x23x14x2換入列bi/ai2，ai2>04010換出行將3化為15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/5－2/5400－1－16/2/2023運籌學--運籌學完整單純形法的計算步驟例1.9用單純形法求解解：將數學模型化為標準形式：不難看出x4、x5可作為初始基變量，列單純形表計算。6/2/2023運籌學--運籌學完整單純形法的計算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/36/2/2023運籌學--運籌學完整單純形法的計算步驟 學習要點： 1.線性規(guī)劃解的概念以及3個基本定理 2.熟練掌握單純形法的解題思路及求解步驟6/2/2023運籌學--運籌學完整單純形法的進一步討論－人工變量法人工變量法： 前面討論了在標準型中系數矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。6/2/2023運籌學--運籌學完整單純形法的進一步討論－人工變量法例1.10用大M法解下列線性規(guī)劃解：首先將數學模型化為標準形式系數矩陣中不存在單位矩陣，無法建立初始單純形表。6/2/2023運籌學--運籌學完整單純形法的進一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數學模型：其中：M是一個很大的抽象的數，不需要給出具體的數值，可以理解為它能大于給定的任何一個確定數值；再用前面介紹的單純形法求解該模型，計算結果見下表。6/2/2023運籌學--運籌學完整單純形法的進一步討論－人工變量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi-Mx64-431-101040x5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M0x63-650-1013/5-Mx58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——-Mx531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→→6/2/2023運籌學--運籌學完整單純形法的進一步討論－人工變量法 解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數非零,則線規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數為零,則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。3）無界解判別：某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。4）無可行解的判斷：當用大M單純形法計算得到最優(yōu)解并且存在Ri>0時，則表明原線性規(guī)劃無可行解。5）退化解的判別：存在某個基變量為零的基本可行解。6/2/2023運籌學--運籌學完整單純形法的進一步討論－人工變量法單純性法小結:建立模型個數取值右端項等式或不等式極大或極小新加變量系數兩個三個以上xj≥0xj無約束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解圖解法、單純形法單純形法不處理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj’

=-xj不處理約束條件兩端同乘以-1加松弛變量xs加入人工變量xa減去xs加入xa不處理令z′=-ZminZ=－maxz′0-M6/2/2023運籌學--運籌學完整A6/2/2023運籌學--運籌學完整線性規(guī)劃模型的應用 一般而言，一個經濟、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。要求解問題的目標函數能用數值指標來反映，且為線性函數存在著多種方案要求達到的目標是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述6/2/2023運籌學--運籌學完整線性規(guī)劃在管理中的應用人力資源分配問題例1.11某晝夜服務的公交線路每天各時間段內所需司機和乘務人員人數如下表所示：班次時間所需人員16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030設司機和乘務人員分別在各時間段開始時上班，并連續(xù)工作8小時，問該公交線路應怎樣安排司機和乘務人員，即能滿足工作需要，又使配備司機和乘務人員的人數減少?6/2/2023運籌學--運籌學完整線性規(guī)劃在管理中的應用解：設xi表示第i班次時開始上班的司機和乘務人員人數。此問題最優(yōu)解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司機和乘務員150人。6/2/2023運籌學--運籌學完整線性規(guī)劃在管理中的應用2.生產計劃問題 某廠生產Ⅰ、Ⅱ、Ⅲ三種產品，都分別經A、B兩道工序加工。設A工序可分別在設備A1和A2上完成，有B1、B2、B3三種設備可用于完成B工序。已知產品Ⅰ可在A、B任何一種設備上加工；產品Ⅱ可在任何規(guī)格的A設備上加工，但完成B工序時，只能在B1設備上加工；產品Ⅲ只能在A2與B2設備上加工。加工單位產品所需工序時間及其他各項數據如下表，試安排最優(yōu)生產計劃，使該廠獲利最大。6/2/2023運籌學--運籌學完整線性規(guī)劃在管理中的應用設備產品設備有效臺時設備加工費（單位小時）ⅠⅡⅢ27910000321B168124000250B247000783B37114000200原料費（每件）0.250.350.5售價（每件）1.252.002.86/2/2023運籌學--運籌學完整線性規(guī)劃在管理中的應用解：設xijk表示產品i在工序j的設備k上加工的數量。約束條件有：6/2/2023運籌學--運籌學完整線性規(guī)劃在管理中的應用目標是利潤最大化，即利潤的計算公式如下：帶入數據整理得到：6/2/2023運籌學--運籌學完整線性規(guī)劃在管理中的應用因此該規(guī)劃問題的模型為：6/2/2023運籌學--運籌學完整線性規(guī)劃在管理中的應用3.套裁下料問題例：現(xiàn)有一批某種型號的圓鋼長8米，需要截取2.5米長的毛坯100根，長1.3米的毛坯200根。問如何才能既滿足需要，又能使總的用料最少？解：為了找到一個省料的套裁方案，必須先設計出較好的幾個下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿足對各種不同規(guī)格圓鋼的需要并達到省料的目的，為此可以設計出4種下料方案以供套裁用。ⅠⅡⅢⅣ2.5m32101.3m0246料頭00.40.30.26/2/2023運籌學--運籌學完整線性規(guī)劃在管理中的應用設按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料的原材料根數分別為xj(j=1，2,3,4)，可列出下面的數學模型：6/2/2023運籌學--運籌學完整線性規(guī)劃在管理中的應用4.配料問題例：某人每天食用甲、乙兩種食物（如豬肉、雞蛋），其資料如下：問兩種食物各食用多少，才能既滿足需要、又使總費用最?。?1.5原料單價1.007.5010.000.10.151.70.751.101.30A1A2A3

最低需要量

甲乙含量食物成分6/2/2023運籌學--運籌學完整線性規(guī)劃在管理中的應用解：設Xj表示Bj種食物用量6/2/2023運籌學--運籌學完整Chapter2對偶理論

(DualityTheory)線性規(guī)劃的對偶模型對偶性質對偶問題的經濟解釋－影子價格對偶單純形法本章主要內容：6/2/2023運籌學--運籌學完整線性規(guī)劃的對偶模型 設某工廠生產兩種產品甲和乙，生產中需4種設備按A，B，C，D順序加工，每件產品加工所需的機時數、每件產品的利潤值及每種設備的可利用機時數列于下表：產品數據表設備產品ABCD產品利潤（元／件）

甲

21402乙

22043設備可利用機時數（時）

1281612問：充分利用設備機時，工廠應生產甲和乙型產品各多少件才能獲得最大利潤？1.對偶問題的現(xiàn)實來源6/2/2023運籌學--運籌學完整線性規(guī)劃的對偶模型解：設甲、乙型產品各生產x1及x2件，則數學模型為：反過來問：若廠長決定不生產甲和乙型產品，決定出租機器用于接受外加工，只收加工費，那么４種機器的機時如何定價才是最佳決策？6/2/2023運籌學--運籌學完整線性規(guī)劃的對偶模型在市場競爭的時代，廠長的最佳決策顯然應符合兩條：

（1）不吃虧原則。即機時定價所賺利潤不能低于加工甲、乙型產品所獲利潤。由此原則，便構成了新規(guī)劃的不等式約束條件。（2）競爭性原則。即在上述不吃虧原則下，盡量降低機時總收費，以便爭取更多用戶。設A、B、C、D設備的機時價分別為y1、y2、y3、y4，則新的線性規(guī)劃數學模型為：6/2/2023運籌學--運籌學完整線性規(guī)劃的對偶模型把同種問題的兩種提法所獲得的數學模型用表2表示，將會發(fā)現(xiàn)一個有趣的現(xiàn)象。原問題與對偶問題對比表A（y1）

B（y2）C（y3）

D（y4）

甲（x1）

21402乙（x2）

220431281612

minωmaxz

6/2/2023運籌學--運籌學完整線性規(guī)劃的對偶模型2.原問題與對偶問題的對應關系原問題（對偶問題）對偶問題（原問題）6/2/2023運籌學--運籌學完整線性規(guī)劃的對偶模型（1）對稱形式 特點：目標函數求極大值時，所有約束條件為≤號，變量非負;目標函數求極小值時，所有約束條件為≥號，變量非負.已知P，寫出D6/2/2023運籌學--運籌學完整線性規(guī)劃的對偶模型例2.1寫出線性規(guī)劃問題的對偶問題解：首先將原問題變形為對稱形式6/2/2023運籌學--運籌學完整線性規(guī)劃的對偶模型6/2/2023運籌學--運籌學完整線性規(guī)劃的對偶模型(2)非對稱型對偶問題 若給出的線性規(guī)劃不是對稱形式，可以先化成對稱形式再寫對偶問題。也可直接按教材表2-2中的對應關系寫出非對稱形式的對偶問題。6/2/2023運籌學--運籌學完整線性規(guī)劃的對偶模型原問題（或對偶問題）對偶問題（或原問題）約束條件右端項目標函數變量的系數目標函數變量的系數約束條件右端項目標函數max目標函數min約束條件m個m個變量≤≥0≥≤0=無約束變量n個n個約束條件≥0≥≤0≤無約束=6/2/2023運籌學--運籌學完整線性規(guī)劃的對偶模型例2.2寫出下列線性規(guī)劃問題的對偶問題.解：原問題的對偶問題為6/2/2023運籌學--運籌學完整對偶性質例2.3分別求解下列2個互為對偶關系的線性規(guī)劃問題分別用單純形法求解上述2個規(guī)劃問題，得到最終單純形表如下表：6/2/2023運籌學--運籌學完整對偶性質XBb原問題的變量原問題的松弛變量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2000－1/4－1/2XBb對偶問題的變量對偶問題的剩余變量y1y2y3y4y5y21/4-4/510-1/41/4y31/215/2011/2-3/215/2007/23/2原問題最優(yōu)表對偶問題最優(yōu)表6/2/2023運籌學--運籌學完整對偶性質原問題與其對偶問題的變量與解的對應關系： 在單純形表中，原問題的松弛變量對應對偶問題的變量，對偶問題的剩余變量對應原問題的變量。6/2/2023運籌學--運籌學完整對偶性質性質1對稱性定理：對偶問題的對偶是原問題minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≥bX≥06/2/2023運籌學--運籌學完整對偶性質性質2

弱對偶原理(弱對偶性)：設和分別是問題(P)和(D)的可行解，則必有推論1:原問題任一可行解的目標函數值是其對偶問題目標函數值的下屆；反之，對偶問題任意可行解的目標函數值是其原問題目標函數值的上界。推論2:

在一對對偶問題（P）和（D）中，若其中一個問題可行但目標函數無界，則另一個問題無可行解；反之不成立。這也是對偶問題的無界性。6/2/2023運籌學--運籌學完整對偶性質推論3：在一對對偶問題（P）和（D）中，若一個可行（如P），而另一個不可行（如D），則該可行的問題目標函數值無界。性質3

最優(yōu)性定理：如果是原問題的可行解，是其對偶問題的可行解，并且:則是原問題的最優(yōu)解，是其對偶問題的最優(yōu)解。6/2/2023運籌學--運籌學完整對偶性質性質4強對偶性：若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函數值相等。 還可推出另一結論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。性質5

互補松弛性：設X0和Y0分別是P問題和D問題的可行解，則它們分別是最優(yōu)解的充要條件是：其中：Xs、Ys為松弛變量6/2/2023運籌學--運籌學完整對偶性質性質5的應用： 該性質給出了已知一個問題最優(yōu)解求另一個問題最優(yōu)解的方法，即已知Y＊求X＊或已知X＊求Y＊互補松弛條件由于變量都非負，要使求和式等于零，則必定每一分量為零，因而有下列關系：若Y＊≠0，則Xs必為0；若X＊≠0，則Ys必為0利用上述關系，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。6/2/2023運籌學--運籌學完整對偶性質例2.4

已知線性規(guī)劃的最優(yōu)解是X＊=(6,2,0)T,求其對偶問題的最優(yōu)解Y＊。解：寫出原問題的對偶問題，即標準化6/2/2023運籌學--運籌學完整對偶性質設對偶問題最優(yōu)解為Y＊＝(y1，y2),由互補松弛性定理可知，X＊和Y＊滿足：即：因為X1≠0，X2≠0，所以對偶問題的第一、二個約束的松弛變量等于零，即y3＝0，y4＝0，帶入方程中：解此線性方程組得y1=1,y2=1,從而對偶問題的最優(yōu)解為：Y＊=(1,1)，最優(yōu)值w=26。6/2/2023運籌學--運籌學完整對偶性質例2.5已知線性規(guī)劃的對偶問題的最優(yōu)解為Y＊=(0,-2)，求原問題的最優(yōu)解。解:對偶問題是標準化6/2/2023運籌學--運籌學完整對偶性質設對偶問題最優(yōu)解為X＊＝(x1，x2，x3)T,由互補松弛性定理可知，X＊和Y＊滿足：將Y＊帶入由方程可知，y3＝y(tǒng)5＝0，y4＝1?！遹2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0將x2，x5分別帶入原問題約束方程中，得：解方程組得：x1=-5,x3=-1,所以原問題的最優(yōu)解為X＊=(-5,0,-1)，最優(yōu)值z=-126/2/2023運籌學--運籌學完整對偶性質原問題與對偶問題解的對應關系小結對應關系原問題最優(yōu)解無界解無可行解對偶問題最優(yōu)解(Y,Y)(N,N)————無界解————(Y,Y)無可行解——(Y,Y)無法判斷6/2/2023運籌學--運籌學完整思考題判斷下列結論是否正確，如果不正確，應該怎樣改正？1）任何線性規(guī)劃都存在一個對應的對偶線性規(guī)劃.2）原問題第i個約束是“≤”約束，則對偶變量yi≥0.3）互為對偶問題，或者同時都有最優(yōu)解，或者同時都無最優(yōu)解.4）對偶問題有可行解，則原問題也有可行解.5）原問題有多重解，對偶問題也有多重解.6）對偶問題有可行解，原問題無可行解，則對偶問題具有無界解.7）原問題無最優(yōu)解，則對偶問題無可行解.8）對偶問題不可行，原問題可能無界解.9）原問題與對偶問題都可行，則都有最優(yōu)解.10）原問題具有無界解，則對偶問題不可行.11）對偶問題具有無界解，則原問題無最優(yōu)解.12）若X*、Y*是原問題與對偶問題的最優(yōu)解，則X*=Y*.6/2/2023運籌學--運籌學完整對偶問題的經濟解釋－影子價格1.影子價格的數學分析：定義：在一對P和D中，若P的某個約束條件的右端項常數bi（第i種資源的擁有量）增加一個單位時，所引起目標函數最優(yōu)值z*的改變量稱為第i種資源的影子價格，其值等于D問題中對偶變量yi*。由對偶問題得基本性質可得：6/2/2023運籌學--運籌學完整對偶問題的經濟解釋－影子價格2.影子價格的經濟意義1）影子價格是一種邊際價格 在其它條件不變的情況下，單位資源數量的變化所引起的目標函數最優(yōu)值的變化。即對偶變量yi就是第i種資源的影子價格。即：

6/2/2023運籌學--運籌學完整對偶問題的經濟解釋－影子價格2）影子價格是一種機會成本 影子價格是在資源最優(yōu)利用條件下對單位資源的估價，這種估價不是資源實際的市場價格。因此，從另一個角度說，它是一種機會成本。若第i種資源的單位市場價格為mi，則有當yi*>mi時，企業(yè)愿意購進這種資源，單位純利為yi*－mi，則有利可圖；如果yi*<mi，則企業(yè)有償轉讓這種資源，可獲單位純利mi－yi

*，否則，企業(yè)無利可圖，甚至虧損。結論：若yi*>mi則購進資源i，可獲單位純利yi*－mi

若yi*<mi則轉讓資源i，可獲單位純利mi－yi6/2/2023運籌學--運籌學完整對偶問題的經濟解釋－影子價格3）影子價格在資源利用中的應用根據對偶理論的互補松弛性定理:Y*Xs=0,YsX*=0表明生產過程中如果某種資源bi未得到充分利用時，該種資源的影子價格為0；若當資源資源的影子價格不為0時，表明該種資源在生產中已耗費完。6/2/2023運籌學--運籌學完整對偶問題的經濟解釋－影子價格4）影子價格對單純形表計算的解釋單純形表中的檢驗數其中cj表示第j種產品的價格;表示生產該種產品所消耗的各項資源的影子價格的總和,即產品的隱含成本。當產值大于隱含成本時，即，表明生產該項產品有利，可在計劃中安排；否則，用這些資源生產別的產品更有利，不在生產中安排該產品。6/2/2023運籌學--運籌學完整對偶單純形法 對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是根據對偶原理和單純形法原理而設計出來的，因此稱為對偶單純形法。不要簡單理解為是求解對偶問題的單純形法。對偶單純形法原理對偶單純形法基本思路： 找出一個對偶問題的可行基，保持對偶問題為可行解的條件下，判斷XB是否可行（XB為非負），若否，通過變換基解，直到找到原問題基可行解（即XB為非負），這時原問題與對偶問題同時達到可行解，由定理4可得最優(yōu)解。6/2/2023運籌學--運籌學完整對偶單純形法找出一個DP的可行基LP是否可行（XB≥0）保持DP為可行解情況下轉移到LP的另一個基本解最優(yōu)解是否循環(huán)結束6/2/2023運籌學--運籌學完整對偶單純形法例2.9用對偶單純形法求解：解:（1）將模型轉化為求最大化問題，約束方程化為等式求出一組基本解，因為對偶問題可行，即全部檢驗數≤0（求max問題）。6/2/2023運籌學--運籌學完整對偶單純形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-2-2-1100-100x5-2-3-1010-120x6-1-1-5001-14(-9/-1.-12/-1.

-15/-5)λj-9-12-1500006/2/2023運籌學--運籌學完整對偶單純形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/5-9/5010-1/5-36/50x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-342cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/14001-9/14-1/14-9/7-12x29/14100-5/141/1423/7(-3/-9,-45/-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/146/2/2023運籌學--運籌學完整對偶單純形法cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3原問題的最優(yōu)解為：X*=（2,2,2,0,0,0），Z*=72其對偶問題的最優(yōu)解為：Y*=（1/3,3,7/3），W*=726/2/2023運籌學--運籌學完整對偶單純形法對偶單純形法應注意的問題：

用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對偶問題的最優(yōu)解初始表中一定要滿足對偶問題可行，也就是說檢驗數滿足最優(yōu)判別準則最小比值中的絕對值是使得比值非負，在極小化問題σj≥0，分母aij<0這時必須取絕對值。在極大化問題中，σ

j≤0，分母aij<0，總滿足非負，這時絕對值符號不起作用，可以去掉。如在本例中將目標函數寫成這里σj≤0在求θk時就可以不帶絕對值符號。6/2/2023運籌學--運籌學完整對偶單純形法對偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進基變量后確定出基變量，對偶單純形法是先確定出基變量后確定進基變量；普通單純形法的最小比值是其目的是保證下一個原問題的基本解可行，對偶單純形法的最小比值是其目的是保證下一個對偶問題的基本解可行對偶單純形法在確定出基變量時，若不遵循規(guī)則，任選一個小于零的bi對應的基變量出基，不影響計算結果，只是迭代次數可能不一樣。6/2/2023運籌學--運籌學完整本章小結 學習要點： 1.線性規(guī)劃解的概念以及3個基本定理 2.熟練掌握單純形法的解題思路及求解步驟6/2/2023運籌學--運籌學完整Chapter3運輸規(guī)劃

(TransportationProblem)運輸規(guī)劃問題的數學模型表上作業(yè)法運輸問題的應用本章主要內容：6/2/2023運籌學--運籌學完整運輸規(guī)劃問題的數學模型例3.1某公司從兩個產地A1、A2將物品運往三個銷地B1,B2,B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最??？B1B2B3產量A1646200A2655300銷量1501502006/2/2023運籌學--運籌學完整運輸規(guī)劃問題的數學模型解：產銷平衡問題：總產量=總銷量＝500設xij為從產地Ai運往銷地Bj的運輸量，得到下列運輸量表：B1B2B3產量A1x11x12x13200A2x21x22x23300銷量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）6/2/2023運籌學--運籌學完整運輸規(guī)劃問題的數學模型運輸問題的一般形式：產銷平衡A1、A2、…、Am表示某物資的m個產地；B1、B2、…、Bn表示某物質的n個銷地；ai表示產地Ai的產量；bj表示銷地Bj的銷量；cij表示把物資從產地Ai運往銷地Bj的單位運價。設xij為從產地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：6/2/2023運籌學--運籌學完整運輸規(guī)劃問題的數學模型變化：1）有時目標函數求最大。如求利潤最大或營業(yè)額最大等；2）當某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)；3）產銷不平衡時，可加入假想的產地（銷大于產時）或銷地（產大于銷時）。定理:設有m個產地n個銷地且產銷平衡的運輸問題，則基變量數為m+n-1。6/2/2023運籌學--運籌學完整表上作業(yè)法表上作業(yè)法是一種求解運輸問題的特殊方法，其實質是單純形法。步驟描述方法第一步求初始基行可行解（初始調運方案）最小元素法、元素差額法、第二步求檢驗數并判斷是否得到最優(yōu)解當非基變量的檢驗數σij全都非負時得到最優(yōu)解，若存在檢驗數σij<0，說明還沒有達到最優(yōu)，轉第三步。閉回路法和位勢法第三步調整運量，即換基，選一個變量出基，對原運量進行調整得到新的基可行解，轉入第二步6/2/2023運籌學--運籌學完整表上作業(yè)法例3.2某運輸資料如下表所示：單位銷地運價產地產量311310719284741059銷量3656問：應如何調運可使總運輸費用最??？6/2/2023運籌學--運籌學完整表上作業(yè)法解：第1步求初始方案方法1：最小元素法基本思想是就近供應，即從運價最小的地方開始供應（調運），然后次小，直到最后供完為止。B1B2B3B4產量A17A2

4A39銷量36563113101927410583416336/2/2023運籌學--運籌學完整表上作業(yè)法總的運輸費＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元 元素差額法對最小元素法進行了改進，考慮到產地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調運，否則會增加總運費。例如下面兩種運輸方案。85102120151515510總運費是z=10×8+5×2+15×1=105最小元素法：6/2/2023運籌學--運籌學完整表上作業(yè)法85102120151551510總運費z=10×5+15×2+5×1=85后一種方案考慮到C11與C21之間的差額是8－2=6，如果不先調運x21，到后來就有可能x11≠0，這樣會使總運費增加較大，從而先調運x21，再是x22，其次是x12用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。6/2/2023運籌學--運籌學完整表上作業(yè)法方法2：Vogel法1）從運價表中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。B1B2B3B4產量行差額A177A2

41A391銷量3656列差額25133113101927410586/2/2023運籌學--運籌學完整表上作業(yè)法2）再從差值最大的行或列中找出最小運價確定供需關系和供需數量。當產地或銷地中有一方數量供應完畢或得到滿足時，劃去運價表中對應的行或列。重復1)和2)，直到找出初始解為至。B1B2B3B4產量行差額A177A2

41A3

91銷量3656列差額251331131019274105856/2/2023運籌學--運籌學完整表上作業(yè)法單位銷地運價產地產量行差額311310719284741059銷量3656列差額71135215××6/2/2023運籌學--運籌學完整表上作業(yè)法單位銷地運價產地產量行差額311310719284741059銷量3656列差額7135275×××3×6/2/2023運籌學--運籌學完整表上作業(yè)法單位銷地運價產地產量行差額311310719284741059銷量3656列差額113515×××3×631××2該方案的總運費:(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元6/2/2023運籌學--運籌學完整表上作業(yè)法第2步最優(yōu)解的判別（檢驗數的求法） 求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數來判斷，記xij的檢驗數為λij由第一章知，求最小值的運輸問題的最優(yōu)判別準則是：所有非基變量的檢驗數都非負，則運輸方案最優(yōu)求檢驗數的方法有兩種：閉回路法位勢法（▲）6/2/2023運籌學--運籌學完整表上作業(yè)法閉回路的概念為一個閉回路，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。如下表6/2/2023運籌學--運籌學完整表上作業(yè)法例下表中閉回路的變量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8個頂點，這8個頂點間用水平或垂直線段連接起來，組成一條封閉的回路。B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43一條回路中的頂點數一定是偶數，回路遇到頂點必須轉90度與另一頂點連接，表3－3中的變量x32及x33不是閉回路的頂點，只是連線的交點。6/2/2023運籌學--運籌學完整表上作業(yè)法閉回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如變量組不能構成一條閉回路，但A中包含有閉回路

變量組變量數是奇數，顯然不是閉回路，也不含有閉回路；6/2/2023運籌學--運籌學完整表上作業(yè)法用位勢法對初始方案進行最優(yōu)性檢驗：1）由ij=Cij-（Ui+Vj）計算位勢Ui，Vj，因對基變量而言有ij=0，即Cij-（Ui+Vj）=0，令U1=02）再由ij=Cij-（Ui+Vj）計算非基變量的檢驗數ijB1B2B3B4UiA1A2A3Vj3113101927410584363130-1-531029（1）（2）（1）（-1）（10）（12）當存在非基變量的檢驗數kl≥0，說明現(xiàn)行方案為最優(yōu)方案，否則目標成本還可以進一步減小。6/2/2023運籌學--運籌學完整表上作業(yè)法當存在非基變量的檢驗數kl<0且kl=min{ij}時，令Xkl進基。從表中知可選X24進基。第3步確定換入基的變量第4步確定換出基的變量以進基變量xik為起點的閉回路中，標有負號的最小運量作為調整量θ，θ對應的基變量為出基變量，并打上“×”以示換出作為非基變量。6/2/2023運籌學--運籌學完整表上作業(yè)法B1B2B3B4UiA1A2A3Vj311310192741058436313(＋)(－)(＋)(－)調整步驟為：在進基變量的閉回路中標有正號的變量加上調整量θ，標有負號的變量減去調整量θ，其余變量不變，得到一組新的基可行解。然后求所有非基變量的檢驗數重新檢驗。1256/2/2023運籌學--運籌學完整表上作業(yè)法當所有非基變量的檢驗數均非負時，則當前調運方案即為最優(yōu)方案，如表此時最小總運費：Z=(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元B1B2B3B4UiA1A2A3Vj3113101927410585363120-2-531039（0）（2）（2）（1）（12）（9）6/2/2023運籌學--運籌學完整表上作業(yè)法表上作業(yè)法的計算步驟：分析實際問題列出產銷平衡表及單位運價表確定初始調運方案（最小元素法或Vogel法）求檢驗數（位勢法）所有檢驗數≥0找出絕對值最大的負檢驗數，用閉合回路調整，得到新的調運方案得到最優(yōu)方案，算出總運價6/2/2023運籌學--運籌學完整表上作業(yè)法表上作業(yè)法計算中的問題：（1）若運輸問題的某一基可行解有多個非基變量的檢驗數為負，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標函數值得到改善，但通常取σij<0中最小者對應的變量為換入變量。（2）無窮多最優(yōu)解 產銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的σij＝0，則該問題有無窮多最優(yōu)解。6/2/2023運籌學--運籌學完整表上作業(yè)法⑵退化解：

※表格中一般要有(m+n-1)個數字格。但有時在分配運量時則需要同時劃去一行和一列，這時需要補一個0，以保證有(m+n-1)個數字格作為基變量。一般可在劃去的行和列的任意空格處加一個0即可。

※利用進基變量的閉回路對解進行調整時，標有負號的最小運量（超過2個最小值）作為調整量θ，選擇任意一個最小運量對應的基變量作為出基變量，并打上“×”以示作為非基變量。6/2/2023運籌學--運籌學完整表上作業(yè)法銷地產地B1B2B3B4產量A116A210A322銷量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11檢驗數是0，經過調整，可得到另一個最優(yōu)解。6/2/2023運籌學--運籌學完整表上作業(yè)法銷地產地B1B2B3B4產量A17A24A39銷量36562011443137782106×3×416×06×××在x12、x22、x33、x34中任選一個變量作為基變量，例如選x34例：用最小元素法求初始可行解6/2/2023運籌學--運籌學完整運輸問題的應用求極大值問題目標函數求利潤最大或營業(yè)額最大等問題。6/2/2023運籌學--運籌學完整運輸問題的應用求解方法： 將極大化問題轉化為極小化問題。設極大化問題的運價表為C，用一個較大的數M（M≥max{cij}）去減每一個cij得到矩陣C′，其中C′=（M－cij）≥0,將C′作為極小化問題的運價表，用表上用業(yè)法求出最優(yōu)解。6/2/2023運籌學--運籌學完整運輸問題的應用例3.3下列矩陣C是Ai（I=1，2，3）到Bj的噸公里利潤,運輸部門如何安排運輸方案使總利潤最大.銷地產地B1B2B3產量A12589A2910710A365412銷量81496/2/2023運籌學--運籌學完整運輸問題的應用銷地產地B1B2B3產量A12589A2910710A365412銷量8149得到新的最小化運輸問題，用表上作業(yè)法求解即可。6/2/2023運籌學--運籌學完整運輸問題的應用產銷不平衡的運輸問題 當總產量與總銷量不相等時,稱為不平衡運輸問題.這類運輸問題在實際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。當產大于銷時，即：數學模型為：6/2/2023運籌學--運籌學完整運輸問題的應用由于總產量大于總銷量，必有部分產地的產量不能全部運送完，必須就地庫存，即每個產地設一個倉庫，假設該倉庫為一個虛擬銷地Bn+1，bn+1作為一個虛設銷地Bn+1的銷量(即庫存量)。各產地Ai到Bn+1的運價為零，即Ci,n+1=0,（i=1，…，m）。則平衡問題的數學模型為：具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可6/2/2023運籌學--運籌學完整運輸問題的應用當銷大于產時，即：數學模型為：由于總銷量大于總產量,故一定有些需求地不完全滿足,這時虛設一個產地Am+1，產量為：6/2/2023運籌學--運籌學完整運輸問題的應用銷大于產化為平衡問題的數學模型為：具體計算時，在運價表的下方增加一行Am+1，運價為零。產量為am+1即可。6/2/2023運籌學--運籌學完整運輸問題的應用例3.4求下列表中極小化運輸問題的最優(yōu)解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因為有：6/2/2023運籌學--運籌學完整運輸問題的應用所以是一個產大于銷的運輸問題。表中A2不可達B1，用一個很大的正數M表示運價C21。虛設一個銷量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列，得到新的運價表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj20603545201806/2/2023運籌學--運籌學完整運輸問題的應用下表為計算結果?？煽闯觯寒a地A4還有20個單位沒有運出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj20603545201806/2/2023運籌學--運籌學完整運輸問題的應用3.生產與儲存問題例3.5某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產能力及生產每臺柴油機的成本如右表。如果生產出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用0.15萬元。試求在完成合同的情況下，使該廠全年生產總費用為最小的決策方案。季度生產能力/臺單位成本/萬元Ⅰ2510.8Ⅱ3511.1Ⅲ3011Ⅳ1011.36/2/2023運籌學--運籌學完整運輸問題的應用解：設xij為第i季度生產的第j季度交貨的柴油機數目，那么應滿足：交貨：

x11=10生產：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10把第i季度生產的柴油機數目看作第i個生產廠的產量；把第j季度交貨的柴油機數目看作第j個銷售點的銷量；設cij是第i季度生產的第j季度交貨的每臺柴油機的實際成本，應該等于該季度單位成本加上儲存、維護等費用?？蓸嬙煜铝挟a銷平衡問題：6/2/2023運籌學--運籌學完整運輸問題的應用jiⅠⅡⅢⅣ產量Ⅰ10.810.9511.111.2525ⅡM11.1011.2511.4035ⅢMM11.0011.1530ⅣMMM11.3010銷量1015252010070由于產大于銷，加上一個虛擬的銷地D，化為平衡問題，即可應用表上作業(yè)法求解。6/2/2023運籌學--運籌學完整運輸問題的應用該問題的數學模型：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23 +11.4x24+11.0x33+11.15x34+11.3x44

jiⅠⅡⅢⅣD產量Ⅰ10.810.9511.111.25025ⅡM11.1011.2511.40035ⅢMM11.0011.15030ⅣMMM11.30010銷量10152520301001006/2/2023運籌學--運籌學完整運輸問題的應用jiⅠⅡⅢⅣD產量Ⅰ1015025Ⅱ053035Ⅲ25530Ⅳ1010銷量1015252030100100最優(yōu)生產決策如下表，最小費用z＝773萬元。6/2/2023運籌學--運籌學完整Chapter4整數規(guī)劃

(IntegerProgramming)整數規(guī)劃的特點及應用分支定界法分配問題與匈牙利法本章主要內容：6/2/2023運籌學--運籌學完整整數規(guī)劃的特點及應用整數規(guī)劃（簡稱：IP） 要求一部分或全部決策變量取整數值的規(guī)劃問題稱為整數規(guī)劃。不考慮整數條