第1-4章 線性規(guī)劃及對偶理論2

夫運籌帷幄之中決勝于千里之外運籌學(xué)課件線性規(guī)劃LinearProgramming本章內(nèi)容線性規(guī)劃問題的數(shù)學(xué)建模圖解法單純形法原理單純形法的計算步驟WinQSB軟件求解教學(xué)說明教學(xué)目標(biāo)：掌握LP的建模方法，熟練地使用單純形法求解模型，借助WinQSB軟件求解問題重點與難點：重點是LP的建模與解法；難點是單純形法的原理教學(xué)方法：配合課件和WinQSB軟件，課堂講授為主，案例研討為輔思考題、討論題、作業(yè)：教材第1-3章習(xí)題學(xué)時分配：8學(xué)時線性規(guī)劃的產(chǎn)生與發(fā)展1939年蘇聯(lián)的經(jīng)濟學(xué)家康托洛維奇在《生產(chǎn)組織與計劃中的數(shù)學(xué)方法》一書中，首次用線性規(guī)劃方法解決了生產(chǎn)組織與運輸問題。1947年美國數(shù)學(xué)家G.B.Dantzig提出了線性規(guī)劃的數(shù)學(xué)模型，并給出了求解該模型的單純形法（Simplexmethod)。這標(biāo)志著線性規(guī)劃這一運籌學(xué)的重要分支的誕生。計算機的發(fā)展促進(jìn)了LP計算理論的發(fā)展，使其應(yīng)用更加廣泛和深入。線性規(guī)劃的應(yīng)用范圍生產(chǎn)中的組織與計劃問題運輸問題合理下料問題配料問題生產(chǎn)布局問題特點：在現(xiàn)有條件下，統(tǒng)籌安排，使總的經(jīng)濟效益最好，或者是總成本最省。某工廠制造A、B兩種產(chǎn)品，它們的原材料單位消耗、單位利潤以及資源現(xiàn)有量如下表：問如何組織生產(chǎn)，使工廠獲得最大利潤？例1：生產(chǎn)組織與計劃問題AB資源現(xiàn)有量（噸）鋼材23600煤21400單位利潤（萬元）205產(chǎn)品資源資源消耗1－1線性規(guī)劃的數(shù)學(xué)建模建立數(shù)學(xué)模型步驟1.假設(shè)決策變量：設(shè)A、B兩種產(chǎn)品各生產(chǎn)個單位；2.建立目標(biāo)函數(shù)：利潤函數(shù)是，求它的最大值，即3.現(xiàn)有資源的限制條件：4.決策變量必須有非負(fù)限制：數(shù)學(xué)模型目標(biāo)函數(shù)系統(tǒng)約束非負(fù)限制

注意：目標(biāo)函數(shù)和約束條件中變量的次數(shù)都是一次的，這樣的模型稱為線性規(guī)劃數(shù)學(xué)模型。生產(chǎn)計劃安排問題的一般描述資源產(chǎn)品消耗資源現(xiàn)有量單位產(chǎn)品利潤求解使工廠獲得最大利潤的生產(chǎn)方案。生產(chǎn)計劃安排問題的一般數(shù)學(xué)模型解：設(shè)表示生產(chǎn)產(chǎn)品的單位數(shù)，則有如下的數(shù)學(xué)模型：設(shè)有某種物資從A、B、C三個產(chǎn)地調(diào)出，運往甲、乙、丙三個需求地，其調(diào)運量及運價如下表。求運費最省的調(diào)運方案。

甲乙丙調(diào)出量

A2457B1344C3239調(diào)入量686（20）調(diào)出調(diào)入運價例2：運輸問題設(shè)表示從i地調(diào)往j地的調(diào)運量產(chǎn)銷平衡運輸問題的一般描述產(chǎn)量銷量產(chǎn)地銷地運價求解使運輸總成本最低的方案。設(shè)表示從i地調(diào)往j地的調(diào)運量產(chǎn)銷平衡運輸問題的一般模型例3：合理配載問題某貨船的前艙、中艙、后艙的載重分別為2000噸、3000噸、1000噸，容積分別為100000立方米、135000立方米、30000立方米；顧客托運的貨物A、B、C的重量、體積、運費等資料已知。為了保持貨船的穩(wěn)定，要求三個貨艙載貨率必須平衡。問如何裝載，使收入最大？例4：連續(xù)投資問題某地區(qū)今后三年內(nèi)可以有A、B、C、D四個項目的投資選擇，總資金量為3000萬元。其中項目A在三年內(nèi)每年年初投資，當(dāng)年年底可回收本利和為120％；項目B第一年年初投資，第二年年底可回收本利和為150％，但投資額不超過2000萬元；項目C第二年年初投資，第三年年底可回收本利和為160％，但投資額不超過1500萬元；項目D第三年年初投資，當(dāng)年年底可收回本利和為140％，投資額不超過1000萬元。問如何安排投資，使第三年年底本利和的金額最大？思考題1：配料問題

某化工廠要用三種原料混合配置三種不同規(guī)格的產(chǎn)品，各產(chǎn)品的規(guī)格、單價見下表：產(chǎn)品規(guī)格單價（元/公斤）A原料Ⅰ不少于50%原料Ⅱ不超過25%50B原料Ⅰ不少于25%原料Ⅱ不超過50%35C不限25問如何安排生產(chǎn)使得生產(chǎn)利潤最大？原料日最大供應(yīng)量單價(元/公斤)Ⅰ10065Ⅱ10025Ⅲ6035原料的單價與每天最大供應(yīng)量見下表：思考題2：人力資源分配問題某個中型百貨商場對售貨人員（周工資400元）的需求經(jīng)統(tǒng)計如下表為了保證銷售人員充分休息，銷售人員每周連續(xù)工作5天，休息2天。問應(yīng)如何安排銷售人員的工作時間，使得人力總成本最??？星期一二三四五六日人數(shù)12151214161819思考題3：合理下料問題要制作100套鋼筋架子，每套有長2.9m、2.1m和1.5m的鋼筋各一根。已知原材料長7.4m，應(yīng)如何切割，使用原材料最節(jié)省，試建立線性規(guī)劃模型并求解。課堂練習(xí)：三種產(chǎn)品要分別經(jīng)過A,B兩道工序。產(chǎn)品Ⅰ可在A,B的任何設(shè)備上加工；產(chǎn)品Ⅱ可在A的任何設(shè)備上加工后，只能在B1設(shè)備上加工；產(chǎn)品Ⅲ只能在A2和B2設(shè)備上加工。

試安排最優(yōu)生產(chǎn)計劃，使該廠獲利最大。1－2線性規(guī)劃問題解的性質(zhì)⒈兩個變量的線性規(guī)劃問題的圖解法幾個基本概念：⑴滿足所有約束條件的解稱為LP問題的可行解；所有可行解的集合稱為可行解集。⑵使目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解稱為LP問題的最優(yōu)解。問題：線性規(guī)劃是一個帶有約束條件的極值問題，能否用微積分方法求解?例1：用圖解法求解下面的LP問題目標(biāo)函數(shù)等值線此點為LP的最優(yōu)解maxSminS得到這個最優(yōu)解：本問題有唯一最優(yōu)解。例2：用圖解法解下面的線性規(guī)劃

目標(biāo)函數(shù)等值線maxSminS得到LP的最優(yōu)解及目標(biāo)函數(shù)最優(yōu)值：

除A、B兩個最優(yōu)解外，AB線段上的所有點都是LP的最優(yōu)解。本問題有無窮多最優(yōu)解。例3：用圖解法解下面的線性規(guī)劃無界的可行解集

此題有可行解，但無最優(yōu)解maxSminS例4：用圖解法解下面的線性規(guī)劃無可行解

本題無可行解，更無最優(yōu)解有唯一最優(yōu)解，這個最優(yōu)解一定在可行解集合的某一頂點上達(dá)到有無窮多最優(yōu)解，最優(yōu)解充滿一個線段，可以用它的兩個端點作為代表有可行解，但無最優(yōu)解（無界解）無可行解小結(jié)：LP圖解法有如下四種情況線性規(guī)劃問題解的關(guān)系線性規(guī)劃問題的解無可行解

有可行解唯一最優(yōu)解無最優(yōu)解有最優(yōu)解無窮多最優(yōu)解⒉線性規(guī)劃問題的標(biāo)準(zhǔn)形式將一般的LP轉(zhuǎn)化為LP標(biāo)準(zhǔn)形：規(guī)定:⑴求目標(biāo)函數(shù)的最大值為標(biāo)準(zhǔn)形，即目標(biāo)函數(shù)為maxS。如果問題是求

minS時，可令求

，相當(dāng)于求minS

。規(guī)定:⑵以等式約束為標(biāo)準(zhǔn)形。設(shè)第k

個等式為(3)LP中所有的變量都有非負(fù)限制。如果實際問題中的LP里某個變量無非負(fù)限制，可如下處理:(4)若約束條件為等式，但右端項為負(fù)值，則在等式兩邊同時乘以-1即可規(guī)定:將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形根據(jù)以上的規(guī)定，LP的標(biāo)準(zhǔn)形為：兩種縮寫形式：矩陣表示法：3.LP問題解的性質(zhì)⑴幾個概念①凸集：若連接n維點集S中任意兩點的線段仍在S內(nèi)，則稱S為凸集。即凸集凸集不是凸集極點②極點：若凸集S中的點x，不能成為S中任何線段的內(nèi)點，則稱x為S的極點。③設(shè)為LP的一個可行解，若或的非零分量對應(yīng)的A中列向量線性無關(guān)，則稱它為基礎(chǔ)可行解。由這些列向量組成的矩陣稱為基矩陣，與這些列向量對應(yīng)的變量稱為基變量，其余的變量稱為非基變量。使目標(biāo)函數(shù)值達(dá)到最優(yōu)值的可行解稱為最優(yōu)解；使目標(biāo)函數(shù)達(dá)到最優(yōu)值的基礎(chǔ)可行解稱為基礎(chǔ)最優(yōu)解?？尚薪饧A(chǔ)可行解最優(yōu)解基礎(chǔ)最優(yōu)解線性規(guī)劃解的關(guān)系目標(biāo)函數(shù)約束條件行列式≠0基矩陣右邊常數(shù)=⑵幾個重要定理（單純形法的理論依據(jù)）定理1

線性規(guī)劃問題的可行解集為凸集，即連接線性規(guī)劃問題任意兩個可行解的線段上的點仍為可行解。定理2可行解集S中的點x是極點的充要條件是x為基礎(chǔ)可行解（簡單地說，凸多邊形的頂點就是基礎(chǔ)可行解）。定理3線性規(guī)劃的目標(biāo)函數(shù)的最優(yōu)值，一定可在極點上達(dá)到。1－3單純形方法(Simplexmethod)x1x2O單純形法的解題思路：⒈用消去法解LP問題解：引入松弛變量將其化為標(biāo)準(zhǔn)形式2.單純形方法理論推導(dǎo)設(shè)A是的矩陣，且R(A)=m（m<n），即A是行滿秩的。于是，A中一定存在m列線性無關(guān)，這m行m列構(gòu)成A的一個非奇異子矩陣，稱為線性規(guī)劃的一個基矩陣B（簡稱為一個基），基矩陣B各列對應(yīng)的變量稱為基變量。為方便起見，不妨設(shè)A的前m列線性無關(guān)?，F(xiàn)將A，B，C，x按一定規(guī)則作成分塊矩陣。對于標(biāo)準(zhǔn)型的LP問題目標(biāo)函數(shù)約束條件行列式≠0基矩陣右邊常數(shù)=類似地，為了用原題所給的數(shù)據(jù)做判優(yōu)，下面證明：線性規(guī)劃的有解判別定理：單純形法的計算步驟單純形法的思路找出一個初始基本可行解是否最優(yōu)轉(zhuǎn)移到另一個基本可行解（找出更大的目標(biāo)函數(shù)值）否核心是：變量迭代結(jié)束基礎(chǔ)最優(yōu)解是是否可轉(zhuǎn)移無界解是否3.單純形表S＝目標(biāo)函數(shù)值基變量取值檢驗數(shù)單純形表的形式單純形法的計算步驟例1用單純形法求下列線性規(guī)劃的最優(yōu)解解：1）將問題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為:單純形法的計算步驟2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj3400cB基x1x2x3x40x34021100x4301301Z=03400單純形法的計算步驟3）進(jìn)行最優(yōu)性檢驗如果表中所有檢驗數(shù)，則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。4）從一個基可行解轉(zhuǎn)換到另一個目標(biāo)值更大的基可行解，列出新的單純形表確定換入基的變量。選擇，對應(yīng)的變量xj作為換入變量，當(dāng)有一個以上檢驗數(shù)大于0時，一般選擇最大的一個檢驗數(shù)，即：，其對應(yīng)的xk作為換入變量。確定換出變量。根據(jù)下式計算并選擇θ

，選最小的θ對應(yīng)基變量作為換出變量。 單純形法的計算步驟用換入變量xk替換基變量中的換出變量，得到一個新的基。對應(yīng)新的基可以找出一個新的基可行解，并相應(yīng)地可以畫出一個新的單純形表。

5）重復(fù)3）、4）步直到計算結(jié)束為止。單純形法的計算步驟cj3400θicB基變量x1x2x3x40x34021100x430130134000x34x23x14x2換入列bi/ai2，ai2>04010換出行將3化為15/311801/301/3101－1/3303005/30－4/3乘以3/5后得到103/5－1/51801－1/5－2/5400－1－1Z=0Z=40Z=70單純形法的計算步驟 學(xué)習(xí)要點： 1.線性規(guī)劃解的概念以及3個基本定理 2.熟練掌握單純形法的解題思路及求解步驟問題:表1中我們選取了入基,如果選取入基結(jié)果又如何呢?路徑1路徑2結(jié)論：1.每一個單純形表對應(yīng)一個極點，表一對應(yīng)黃點；表二對應(yīng)綠點；表三對應(yīng)藍(lán)點。2.一般來說，路徑不同，迭代次數(shù)可能不同。(1)如果單純形表中的基變量取值皆為正數(shù)，稱這個基可行解為非退化解。若LP的所有基可行解都是非退化的，則LP經(jīng)過有限次迭代可達(dá)到最優(yōu).(2)如果單純形表中的基變量取值有的為零時，稱為LP的退化解，此時稱LP是退化的，理論上認(rèn)為這種線性規(guī)劃在迭代過程中可能產(chǎn)生循環(huán)，從而得不到最優(yōu)解。為避免循環(huán)，常采用1976年R.G.Bland提出Bland法則：a.單純形表中有若干個檢驗數(shù)時，取下標(biāo)號小的非基變量入基；b.

用法則選取出基變量時，若比值相同，則選取下標(biāo)號小的基變量出基。說明：(3)當(dāng)所有的檢驗數(shù)全部小于等于零時，若有某個非基變量的檢驗數(shù)也是零，則該線性規(guī)劃有無窮多組解，否則有唯一解。將這個檢驗數(shù)為零的變量入基，得到另一個基礎(chǔ)最優(yōu)解。（P31）(4)當(dāng)某非基變量的檢驗數(shù)大于零時，但中對應(yīng)列系數(shù)已無正數(shù)，則表示無論引入該非基變量多少，基變量不會向違反非負(fù)約束的方向發(fā)展，從而使目標(biāo)函數(shù)可以無限制地增加，因此存在無界解（P32）說明：例2：解線性規(guī)劃解：注意到對應(yīng)A中的列向量恰好構(gòu)成三階單位方陣，可以作為第一個可行基。單純形表C2-11-211-1-2201030201011100230013S’=-507000812-201000-210-3110020-301-3S’=200-700-6最優(yōu)解為

最優(yōu)值S=-203.第一個可行解的求法（大M法）以上各例的系數(shù)矩陣A中，都存在一個m階單位陣，因此很容易用單純行法求解。但是大多數(shù)LP問題并不是這樣。例3：解：化為標(biāo)準(zhǔn)形填寫單純形表：C3-1-100-M-M0-M-M11311-211000-4120-110-2010001S’=-4M3-6M

M-13M-10-M00C3-1-100-M-M0-M-110113-20100-10100-11-2-2010001S’=-M-11

M-100-M0-3M+1C3-1-100-M-M0-1-112113001-22-50100-11-2-2010001S’=-21

000-1-M+1-M-1C3-1-100-M-M3-1-14191001/3-2/32/3-5/30100-11-20012/3-4/34/3-7/3S’=20

00-1/3-1/3-M+1/3-M+2/3終止表說明：關(guān)于大M法的幾種情況（1）上表稱為終止表。在終止表中，如果基變量里不含有人工變量，或者基變量里含有人工變量，但是人工變量取值為零，則LP一定有最優(yōu)解；（2）在終止表中，如果基變量里含有人工變量，且人工變量取值大于零，則LP無最優(yōu)解（P37）1-4WinQSB軟件應(yīng)用第2章線性規(guī)劃的對偶理論對偶問題的提出原問題與對偶問題對偶問題的基本性質(zhì)影子價格對偶單純形法靈敏度分析線性規(guī)劃的對偶理論教學(xué)目的與要求：了解對偶問題產(chǎn)生的經(jīng)濟背景，熟練掌握對偶單純形法和影子價格概念，熟練掌握靈敏度分析方法。重點與難點：重點同上，難點是對偶理論。教學(xué)方法：課堂講授為主并配合課件和WinQSB軟件。思考題、討論題、作業(yè)：教材第4章習(xí)題參考資料：見緒論學(xué)時分配：8學(xué)時2－1對偶線性規(guī)劃問題對偶問題的提出內(nèi)容一致，而從相反的角度提出的一對問題，稱為一對對偶問題。例1：某工廠在計劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品，這些產(chǎn)品分別需要在A、B、C、D四種不同的設(shè)備上加工。產(chǎn)品在各臺設(shè)備上需要加工的臺時數(shù)如下表：ABCD甲2140乙2204產(chǎn)品設(shè)備已知A、B、C、D設(shè)備的有效臺時數(shù)分別是12、8、16、12。售出一單位甲產(chǎn)品獲利2萬元，一單位乙產(chǎn)品獲利3萬元。如何安排生產(chǎn)使工廠獲利最大？從相反的角度提出問題：工廠決策者決定不生產(chǎn)甲、乙兩種產(chǎn)品，而對設(shè)備的有效臺時數(shù)進(jìn)行出租，用租金的方法獲得最大利潤。應(yīng)如何考慮？決策者要考慮給每一種設(shè)備出租一個臺時的定價。在何種價格下，決策者接受出租設(shè)備呢？建立LP數(shù)學(xué)模型顯然，當(dāng)maxZ=minW時，對于決策者來說這兩種方案都是最優(yōu)的。2.對偶線性規(guī)劃的模型對偶線性規(guī)劃的特點：一個規(guī)劃中的每一個約束，對應(yīng)對偶規(guī)劃中的一個決策變量；一個規(guī)劃中目標(biāo)函數(shù)系數(shù)恰為對偶規(guī)劃約束條件右端常數(shù)項；一個規(guī)劃求最小化，而對偶規(guī)劃求最大化；目標(biāo)函數(shù)求最小化搭配約束；目標(biāo)函數(shù)求最大化搭配約束；兩個規(guī)劃都有非負(fù)限制。例1：寫出下面原規(guī)劃的對偶規(guī)劃定理1如果線性規(guī)劃中第k個約束條件是等式，則它的對偶規(guī)劃中的第k個變量無非負(fù)限制，反之亦然。例2：寫出下面原規(guī)劃的對偶規(guī)劃例3：寫出下面原規(guī)劃的對偶規(guī)劃原規(guī)劃與對偶規(guī)劃的對應(yīng)關(guān)系變量約束條件目標(biāo)函數(shù)LP原問題LP對偶問題約束條件變量目標(biāo)函數(shù)練習(xí)：寫出下列LP問題的對偶問題模型3.對偶線性規(guī)劃的性質(zhì)定理2(弱對偶定理)對偶規(guī)劃(1)，(2)有最優(yōu)解的充分必要條件是它們同時有可行解。定理3(最優(yōu)性定理)如果分別是(1)，(2)的可行解，且則分別是(1)，(2)的最優(yōu)解。定理4如果對偶規(guī)劃(1)，(2)中，有一個存在最優(yōu)解，那么另一個也一定有最優(yōu)解。并且兩個規(guī)劃的目標(biāo)函數(shù)的最優(yōu)值相等。注意：重點研究兩個規(guī)劃的最優(yōu)解之間的關(guān)系分別化為標(biāo)準(zhǔn)形原問題的最優(yōu)單純形表C2100002115/27/23/20015/4-15/21001/4-1/2010-1/43/2S=17/2000-1/4-1/2對偶問題的最優(yōu)單純形表b-15-24-500-24-51/41/2-5/410-1/41/415/2011/2-3/2g’=-17/2-15/200-7/2-3/2重要結(jié)論：給出一對對偶線性規(guī)劃，只需解其中一個線性規(guī)劃得出最優(yōu)解和目標(biāo)函數(shù)最優(yōu)值。它的對偶規(guī)劃的目標(biāo)函數(shù)最優(yōu)值與原規(guī)劃的目標(biāo)函數(shù)值相同，而最優(yōu)解可用原規(guī)劃最優(yōu)表中的松弛變量的檢驗數(shù)乘以“-1”得到。例：線性規(guī)劃問題其對偶問題的最優(yōu)解為求原問題的最優(yōu)解。提示：運用對偶模型最優(yōu)解之間的關(guān)系，分析松弛變量取值，決定對應(yīng)變量的值。4.影子價格(Shadowprice)根據(jù)最優(yōu)性定理，

是原規(guī)劃約束條件右端項，它代表第i種資源的擁有量，對偶變量表示對一個單位第i種資源的估價。它不是該資源的市場價格，而是根據(jù)該資源在生產(chǎn)中做出的貢獻(xiàn)而作的估價，稱為影子價格。關(guān)于影子價格的幾個重要結(jié)論:（1）影子價格的求法：對偶問題的最優(yōu)解，即為原問題約束條件右端常數(shù)項的影子價格。

具體做法：將原規(guī)劃最優(yōu)表中的松弛變量的檢驗數(shù)乘以-1，就得到了對應(yīng)于原規(guī)劃約束條件右端常數(shù)項（即資源限制量）的影子價格。（2）影子價格是一種邊際價格（Boundaryprice）在上式中，對求偏導(dǎo)數(shù)，得這說明，的值相當(dāng)于在給定的生產(chǎn)條件下，每增加一個單位時，目標(biāo)函數(shù)S的增加量，即總收入的變化率（總收入增加一個影子價格值）。（3）影子價格是一種機會成本（Opportunitycost）在純市場經(jīng)濟條件下，當(dāng)某種資源的市場價格低于影子價格時，可以買進(jìn)這種資源擴大生產(chǎn)；相反當(dāng)市場價格高于影子價格，可賣出這種資源獲取更大的利潤。注意：由于影子價格可為決策者提供決策依據(jù)，因此各種資源的影子價格應(yīng)當(dāng)保密。（4）影子價格大于零時，對應(yīng)的松弛變量為非基變量，其取值為零，則該約束條件為等式，這說明此種資源已被充分利用。影子價格等于零時，對應(yīng)的松弛變量為基變量，一般地說，其取值大于零，則該約束條件不等式是成立的（“<”關(guān)系）。這說明此資源是過剩資源，沒有被充分利用。影子價格等于零，不是說該資源沒有價格，而是表明該資源是過剩資源，再買進(jìn)此資源不會增加總收入。檢驗數(shù)的含義：4.對偶單純形法定義1：將線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式后，對某一確定的基矩陣B，令非基變量等于零，根據(jù)系統(tǒng)約束條件解出基變量，則這組解稱為基矩陣B的基解。滿足非負(fù)約束條件的基解，稱為基可行解。試找出下列線性規(guī)劃模型的基解，并判斷是否可行？是否最優(yōu)？定義2：設(shè)是線性規(guī)劃的一組基變量，其對應(yīng)的基矩陣是B，對應(yīng)的基解為，如果這組基對應(yīng)的檢驗數(shù)全部小于等于零，即，則稱這組基為該線性規(guī)劃的一組正則基。為正則解。線性規(guī)劃的對偶單純形法是從第一個正則解開始迭代的。對偶單純形法的迭代步驟:（1）從一個正則解開始，列出對偶單純形表；（2）如基變量的取值全部大于等于零，則線性規(guī)劃已取得最優(yōu)解，計算結(jié)束；否則轉(zhuǎn)（3）；（3）在基變量中，挑選取負(fù)值中最小的一個，作為出基變量（若最小負(fù)值相同，可由Bland法則確定）；（4）在出基變量行中，如果非基變量的約束系數(shù)全部非負(fù)，則原問題不存在可行解；否則轉(zhuǎn)（5）；（5）在出基變量行中，如果有些非基變量的約束系數(shù)為負(fù)，則分別計算這些變量的檢驗數(shù)與出基變量行中負(fù)系數(shù)的比值，比值最小者對應(yīng)的非基變量為入基變量（若比值相同，由Bland法則確定）；（6）出、入基交叉點上的元素為主元素，用方框框起來，將其變?yōu)?，用矩陣初等行變換將其所在列的其余元素變?yōu)?，得到一張新表，轉(zhuǎn)（2）。對偶單純形法的迭代步驟:例1：利用對偶單純形法解下邊的線性規(guī)劃解：首先將LP化為標(biāo)準(zhǔn)形再變形為對偶單純形表C-2-1000000-3-6-2-3-1100-4-3010-1-2001-S=0-2-10000-10-122-5/301-1/304/310-1/305/300-2/31-S=-2-2/300-1/30對偶單純形表C-2-10000-10-122-5/301-1/304/310-1/305/300-2/31-S=-2-2-1000-2-103/56/5110-3/51/50014/5-3/50001-11-S=-12/500-2/5-1/505.靈敏度分析靈敏度分析的主要內(nèi)容1）目標(biāo)函數(shù)系數(shù)變化的靈敏度分析；2）約束條件右端常數(shù)項變化的靈敏度分析；3）系統(tǒng)約束系數(shù)的靈敏度分析；4）增加一個新決策變量的靈敏度分析；5）增加一個新約束條件的靈敏度分析例：某工廠用甲、乙兩種原料生產(chǎn)A,B,C,D四種產(chǎn)品，每種產(chǎn)品消耗的原料定額如下表，現(xiàn)有甲原料18噸，乙原料3噸。而每單位產(chǎn)品A,B,C,D的利潤分別是9萬元、8萬元、50萬元和19萬元。問如何組織生產(chǎn)才能使總利潤最大。ABCD甲乙321040021/2單位消耗最優(yōu)表為C9850190019502124/3012/3-10/3-1/2-1/310-1/64/3S=88-4-2/300-13/3-10/3進(jìn)行靈敏度分析:1）目標(biāo)函數(shù)系數(shù)變化的靈敏度分析C9+

850190019502124/3012/3-10/3-1/2-1/310-1/64/3S=88-4-2/300-13/3-10/3（1）是非基變量的系數(shù)1cD1cD（2）是基變量的系數(shù)C9850190019502124/3012/3-10/3-1/2-1/310-1/64/3S=88-4-2/300-13/3-10/3+檢驗數(shù)解不等式組即當(dāng)C產(chǎn)品的利潤在（47.5,52）之間時，最優(yōu)解不變。有關(guān)靈敏度分析的例題綜合例題：考慮下列線性規(guī)劃求出最優(yōu)解后，分別對下列各種變化進(jìn)行靈敏度分析，求出變化后的最優(yōu)解。目標(biāo)函數(shù)系數(shù)c3變?yōu)?C2-140004005/47/411/43/41/211/4001/41/20-1/4101/4-3/20-1/401Z=5-1-30-100最優(yōu)單純形表：c3的系數(shù)已超出允許變化范圍，在上表中替換相應(yīng)的數(shù)，用單純形法求解。115/4-3/2帶入后的單純形表：目標(biāo)函數(shù)系數(shù)c2變?yōu)?最優(yōu)單純形表：因為c2未超過允許值，所以最優(yōu)解保持不變。C2-140004005/47/411/43/41/211/4001/41/20-1/4101/4-3/20-1/401Z=5-1-30-100簡便方法（對于目標(biāo)函數(shù)極大化的情況）：（1）非基變量的目標(biāo)函數(shù)系數(shù)變化時，利用該非基變量的原檢驗數(shù)加系數(shù)變化的量，并列為小于等于零的不等式。（2）基變量的目標(biāo)函數(shù)系數(shù)變化時，會影響所有非基變量的檢驗數(shù)，以原檢驗數(shù)加上系數(shù)變化的基變量對應(yīng)的消耗系數(shù)的相反數(shù)與系數(shù)變化量的乘積，并列為小于等于零的不等式組。2）約束條件右端常數(shù)項變化的靈敏度分析最優(yōu)單純形表C9850190019502124/3012/3-10/3-1/2-1/310-1/64/3S=88-4-2/300-13/3-10/3初始單純形表C985019000018332104100021/201S’=098501900最優(yōu)基B可行基最優(yōu)基例如，第一種資源限制量發(fā)生變化即當(dāng)時，最優(yōu)基不變。簡便方法：基變量的取值加上該資源的松弛變量所在列的系數(shù)為的系數(shù)，并列為大于等于零的不等式。有關(guān)靈敏度分析的例題綜合例題：考慮下列線性規(guī)劃求出最優(yōu)解后，當(dāng)右邊常數(shù)項變化時，求出變化后的最優(yōu)解。2042最優(yōu)單純形表：基本解不可行，最優(yōu)基已變化，用對偶單純形法求最優(yōu)解。帶入?yún)?shù)后的對偶單純形表：C2-140004005/47/411/43/41/211/4001/41/20-1/4101/4-3/20-1/401Z=5-1-30-100-20C2-140004005-1-33/41/211/4001/41/20-1/4101/4-3/20-1/401Z=20-18-30-10040-14-225/6011/601/31/300-1/311/3-1/6101/60-2/3Z=14-3/200-1/20-240-136110101/21/2-1001-3-101001/2-1/2Z=11-2000-3/2-5/2當(dāng)為基變量的系數(shù)，其變化一定影響最優(yōu)解當(dāng)為非基變量的系數(shù)，其變化僅影響該非基變量的檢驗數(shù)。分析不改變最優(yōu)解基變量及其取值情況下，求非基變量系數(shù)的變動范圍處理方法：3）的靈敏度分析98501900C-4-2/300-13/3-10/3S=8824/3012/3-10/3-1/2-1/310-1/64/3211950分析的靈敏度范圍非基變量對應(yīng)的消耗系數(shù)的靈敏度范圍簡便方法：令該非基變量對應(yīng)的檢驗數(shù)加上消耗系數(shù)資源對應(yīng)的松弛變量的檢驗數(shù)與變化值的乘積小于等于零，求得靈敏度區(qū)間例：某工廠用甲、乙兩種原料生產(chǎn)A,B,C,D四種產(chǎn)品，每種產(chǎn)品