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

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

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

甲乙丙調(diào)出量

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

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

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

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

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

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

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

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

minS時(shí)，可令求

，相當(dāng)于求minS

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

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

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

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

5）重復(fù)3）、4）步直到計(jì)算結(jié)束為止。單純形法的計(jì)算步驟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單純形法的計(jì)算步驟 學(xué)習(xí)要點(diǎn)： 1.線性規(guī)劃解的概念以及3個(gè)基本定理 2.熟練掌握單純形法的解題思路及求解步驟問(wèn)題:表1中我們選取了入基,如果選取入基結(jié)果又如何呢?路徑1路徑2結(jié)論：1.每一個(gè)單純形表對(duì)應(yīng)一個(gè)極點(diǎn)，表一對(duì)應(yīng)黃點(diǎn)；表二對(duì)應(yīng)綠點(diǎn)；表三對(duì)應(yīng)藍(lán)點(diǎn)。2.一般來(lái)說(shuō)，路徑不同，迭代次數(shù)可能不同。(1)如果單純形表中的基變量取值皆為正數(shù)，稱這個(gè)基可行解為非退化解。若LP的所有基可行解都是非退化的，則LP經(jīng)過(guò)有限次迭代可達(dá)到最優(yōu).(2)如果單純形表中的基變量取值有的為零時(shí)，稱為L(zhǎng)P的退化解，此時(shí)稱LP是退化的，理論上認(rèn)為這種線性規(guī)劃在迭代過(guò)程中可能產(chǎn)生循環(huán)，從而得不到最優(yōu)解。為避免循環(huán)，常采用1976年R.G.Bland提出Bland法則：a.單純形表中有若干個(gè)檢驗(yàn)數(shù)時(shí)，取下標(biāo)號(hào)小的非基變量入基；b.

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

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

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

具體做法：將原規(guī)劃最優(yōu)表中的松弛變量的檢驗(yàn)數(shù)乘以-1，就得到了對(duì)應(yīng)于原規(guī)劃約束條件右端常數(shù)項(xiàng)（即資源限制量）的影子價(jià)格。（2）影子價(jià)格是一種邊際價(jià)格（Boundaryprice）在上式中，對(duì)求偏導(dǎo)數(shù)，得這說(shuō)明，的值相當(dāng)于在給定的生產(chǎn)條件下，每增加一個(gè)單位時(shí)，目標(biāo)函數(shù)S的增加量，即總收入的變化率（總收入增加一個(gè)影子價(jià)格值）。（3）影子價(jià)格是一種機(jī)會(huì)成本（Opportunitycost）在純市場(chǎng)經(jīng)濟(jì)條件下，當(dāng)某種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，可以買進(jìn)這種資源擴(kuò)大生產(chǎn)；相反當(dāng)市場(chǎng)價(jià)格高于影子價(jià)格，可賣出這種資源獲取更大的利潤(rùn)。注意：由于影子價(jià)格可為決策者提供決策依據(jù)，因此各種資源的影子價(jià)格應(yīng)當(dāng)保密。（4）影子價(jià)格大于零時(shí)，對(duì)應(yīng)的松弛變量為非基變量，其取值為零，則該約束條件為等式，這說(shuō)明此種資源已被充分利用。影子價(jià)格等于零時(shí)，對(duì)應(yīng)的松弛變量為基變量，一般地說(shuō)，其取值大于零，則該約束條件不等式是成立的（“<”關(guān)系）。這說(shuō)明此資源是過(guò)剩資源，沒(méi)有被充分利用。影子價(jià)格等于零，不是說(shuō)該資源沒(méi)有價(jià)格，而是表明該資源是過(guò)剩資源，再買進(jìn)此資源不會(huì)增加總收入。檢驗(yàn)數(shù)的含義：4.對(duì)偶單純形法定義1：將線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式后，對(duì)某一確定的基矩陣B，令非基變量等于零，根據(jù)系統(tǒng)約束條件解出基變量，則這組解稱為基矩陣B的基解。滿足非負(fù)約束條件的基解，稱為基可行解。試找出下列線性規(guī)劃模型的基解，并判斷是否可行？是否最優(yōu)？定義2：設(shè)是線性規(guī)劃的一組基變量，其對(duì)應(yīng)的基矩陣是B，對(duì)應(yīng)的基解為，如果這組基對(duì)應(yīng)的檢驗(yàn)數(shù)全部小于等于零，即，則稱這組基為該線性規(guī)劃的一組正則基。為正則解。線性規(guī)劃的對(duì)偶單純形法是從第一個(gè)正則解開(kāi)始迭代的。對(duì)偶單純形法的迭代步驟:（1）從一個(gè)正則解開(kāi)始，列出對(duì)偶單純形表；（2）如基變量的取值全部大于等于零，則線性規(guī)劃已取得最優(yōu)解，計(jì)算結(jié)束；否則轉(zhuǎn)（3）；（3）在基變量中，挑選取負(fù)值中最小的一個(gè)，作為出基變量（若最小負(fù)值相同，可由Bland法則確定）；（4）在出基變量行中，如果非基變量的約束系數(shù)全部非負(fù)，則原問(wèn)題不存在可行解；否則轉(zhuǎn)（5）；（5）在出基變量行中，如果有些非基變量的約束系數(shù)為負(fù)，則分別計(jì)算這些變量的檢驗(yàn)數(shù)與出基變量行中負(fù)系數(shù)的比值，比值最小者對(duì)應(yīng)的非基變量為入基變量（若比值相同，由Bland法則確定）；（6）出、入基交叉點(diǎn)上的元素為主元素，用方框框起來(lái)，將其變?yōu)?，用矩陣初等行變換將其所在列的其余元素變?yōu)?，得到一張新表，轉(zhuǎn)（2）。對(duì)偶單純形法的迭代步驟:例1：利用對(duì)偶單純形法解下邊的線性規(guī)劃解：首先將LP化為標(biāo)準(zhǔn)形再變形為對(duì)偶單純形表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對(duì)偶單純形表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ù)項(xiàng)變化的靈敏度分析；3）系統(tǒng)約束系數(shù)的靈敏度分析；4）增加一個(gè)新決策變量的靈敏度分析；5）增加一個(gè)新約束條件的靈敏度分析例：某工廠用甲、乙兩種原料生產(chǎn)A,B,C,D四種產(chǎn)品，每種產(chǎn)品消耗的原料定額如下表，現(xiàn)有甲原料18噸，乙原料3噸。而每單位產(chǎn)品A,B,C,D的利潤(rùn)分別是9萬(wàn)元、8萬(wàn)元、50萬(wàn)元和19萬(wàn)元。問(wèn)如何組織生產(chǎn)才能使總利潤(rù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+檢驗(yàn)數(shù)解不等式組即當(dāng)C產(chǎn)品的利潤(rùn)在（47.5,52）之間時(shí)，最優(yōu)解不變。有關(guān)靈敏度分析的例題綜合例題：考慮下列線性規(guī)劃求出最優(yōu)解后，分別對(duì)下列各種變化進(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)單純形表：因?yàn)閏2未超過(guò)允許值，所以最優(yōu)解保持不變。C2-140004005/47/411/43/41/211/4001/41/20-1/4101/4-3/20-1/401Z=5-1-30-100簡(jiǎn)便方法（對(duì)于目標(biāo)函數(shù)極大化的情況）：（1）非基變量的目標(biāo)函數(shù)系數(shù)變化時(shí)，利用該非基變量的原檢驗(yàn)數(shù)加系數(shù)變化的量，并列為小于等于零的不等式。（2）基變量的目標(biāo)函數(shù)系數(shù)變化時(shí)，會(huì)影響所有非基變量的檢驗(yàn)數(shù)，以原檢驗(yàn)數(shù)加上系數(shù)變化的基變量對(duì)應(yīng)的消耗系數(shù)的相反數(shù)與系數(shù)變化量的乘積，并列為小于等于零的不等式組。2）約束條件右端常數(shù)項(xiàng)變化的靈敏度分析最優(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)時(shí)，最優(yōu)基不變。簡(jiǎn)便方法：基變量的取值加上該資源的松弛變量所在列的系數(shù)為的系數(shù)，并列為大于等于零的不等式。有關(guān)靈敏度分析的例題綜合例題：考慮下列線性規(guī)劃求出最優(yōu)解后，當(dāng)右邊常數(shù)項(xiàng)變化時(shí)，求出變化后的最優(yōu)解。2042最優(yōu)單純形表：基本解不可行，最優(yōu)基已變化，用對(duì)偶單純形法求最優(yōu)解。帶入?yún)?shù)后的對(duì)偶單純形表：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ù)，其變化僅影響該非基變量的檢驗(yàn)數(shù)。分析不改變最優(yōu)解基變量及其取值情況下，求非基變量系數(shù)的變動(dòng)范圍處理方法：3）的靈敏度分析98501900C-4-2/300-13/3-10/3S=8824/3012/3-10/3-1/2-1/310-1/64/3211950分析的靈敏度范圍非基變量對(duì)應(yīng)的消耗系數(shù)的靈敏度范圍簡(jiǎn)便方法：令該非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)加上消耗系數(shù)資源對(duì)應(yīng)的松弛變量的檢驗(yàn)數(shù)與變化值的乘積小于等于零，求得靈敏度區(qū)間例：某工廠用甲、乙兩種原料生產(chǎn)A,B,C,D四種產(chǎn)品，每種產(chǎn)品