1、第第1頁(yè)頁(yè)運(yùn)運(yùn) 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外線線 性性 規(guī)規(guī) 劃劃Linear ProgrammingLinear Programming運(yùn)運(yùn) 籌籌 學(xué)學(xué) 課課 件件第第2頁(yè)頁(yè)線線 性性 規(guī)規(guī) 劃劃|線性規(guī)劃問(wèn)題線性規(guī)劃問(wèn)題|可行區(qū)域與基本可行解可行區(qū)域與基本可行解|單純形算法單純形算法|初始可行解初始可行解|對(duì)偶理論對(duì)偶理論|靈敏度分析靈敏度分析|計(jì)算軟件計(jì)算軟件|案例分析案例分析第第3頁(yè)頁(yè)線線 性性 規(guī)規(guī) 劃劃 問(wèn)問(wèn) 題題|線性規(guī)劃實(shí)例線性規(guī)劃實(shí)例 生產(chǎn)計(jì)劃問(wèn)題生產(chǎn)計(jì)劃問(wèn)題 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題|線性規(guī)劃模型線性規(guī)劃模型 一般形式一般形式 規(guī)范形式規(guī)范形式 標(biāo)

2、準(zhǔn)形式標(biāo)準(zhǔn)形式 形式轉(zhuǎn)換形式轉(zhuǎn)換 概念概念 第第4頁(yè)頁(yè)某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如表某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如表2.1.1所示，試制訂總利潤(rùn)最大的生產(chǎn)計(jì)劃所示，試制訂總利潤(rùn)最大的生產(chǎn)計(jì)劃單位產(chǎn)品所需原單位產(chǎn)品所需原料數(shù)量（公斤）料數(shù)量（公斤）產(chǎn)品產(chǎn)品Q1產(chǎn)品產(chǎn)品Q2產(chǎn)品產(chǎn)品Q3原料可用量原料可用量（公斤（公斤/日）日）原料原料P12301500原料原料P2024800原料原料P33252000單位產(chǎn)品的利潤(rùn)單位產(chǎn)品的利潤(rùn)（千元）（千元）354生生 產(chǎn)產(chǎn) 計(jì)計(jì) 劃劃 問(wèn)問(wèn) 題題第第5頁(yè)頁(yè)問(wèn)問(wèn) 題題 分分 析析可控因素：可控因素：每天生產(chǎn)三種產(chǎn)品的數(shù)量，分別設(shè)為每天生

3、產(chǎn)三種產(chǎn)品的數(shù)量，分別設(shè)為321,xxx 目標(biāo)：目標(biāo)：每天的生產(chǎn)利潤(rùn)最大每天的生產(chǎn)利潤(rùn)最大 利潤(rùn)函數(shù)利潤(rùn)函數(shù)321453xxx 受制條件：受制條件： 每天原料的需求量不超過(guò)可用量：每天原料的需求量不超過(guò)可用量： 原料原料1P：15003221 xx 原料原料2P：8004232 xx 原料原料3P：2000523321 xxx 蘊(yùn)含約束：蘊(yùn)含約束：產(chǎn)量為非負(fù)數(shù)產(chǎn)量為非負(fù)數(shù) 0,321 xxx 第第6頁(yè)頁(yè)模模 型型321453maxxxx 15003221 xx s.t. 8004232 xx 2000523321 xxx 0,321 xxx 第第7頁(yè)頁(yè)計(jì)計(jì) 算算 結(jié)結(jié) 果果 OBJECTIVE

4、 FUNCTION VALUE 2675.000 VARIABLE VALUE REDUCED COST X1 375.000000 0.000000 X2 250.000000 0.000000 X3 75.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 1) 0.000000 1.050000 2) 0.000000 0.625000 3) 0.000000 0.300000 第第8頁(yè)頁(yè)運(yùn)運(yùn) 輸輸 問(wèn)問(wèn) 題題一一個(gè)個(gè)制制造造廠廠要要把把若若干干單單位位的的產(chǎn)產(chǎn)品品從從兩兩個(gè)個(gè)倉(cāng)倉(cāng)庫(kù)庫(kù)2 , 1; iAi 發(fā)發(fā)送送到到零零售售點(diǎn)點(diǎn)4 , 3

5、, 2 , 1; jBj，倉(cāng)倉(cāng)庫(kù)庫(kù)iA能能供供應(yīng)應(yīng)的的產(chǎn)產(chǎn)品品數(shù)數(shù)量量為為 2 , 1; iai，零零售售點(diǎn)點(diǎn) jB所所需需的的產(chǎn)產(chǎn)品品的的數(shù)數(shù)量量為為4 , 3 , 2 , 1; jbj。 假假設(shè)設(shè)供供給給總總量量和和需需求求總總量量相相等等，且且已已知知從從倉(cāng)倉(cāng)庫(kù)庫(kù)iA運(yùn)運(yùn)一一個(gè)個(gè)單單 位位產(chǎn)產(chǎn)品品往往jB的的運(yùn)運(yùn)價(jià)價(jià)為為ijc。問(wèn)問(wèn)應(yīng)應(yīng)如如何何組組織織運(yùn)運(yùn)輸輸才才能能使使總總運(yùn)運(yùn)費(fèi)費(fèi) 最最iA小小？ 第第9頁(yè)頁(yè)問(wèn)問(wèn) 題題 分分 析析可控因素可控因素：從倉(cāng)庫(kù)：從倉(cāng)庫(kù)iA運(yùn)往運(yùn)往jB的產(chǎn)品數(shù)量的產(chǎn)品數(shù)量 設(shè)為設(shè)為4 , 3 , 2 , 1, 2 , 1; jixij 目標(biāo)目標(biāo)：總運(yùn)費(fèi)最小：總

6、運(yùn)費(fèi)最小 費(fèi)用函數(shù)費(fèi)用函數(shù) 2141ijijijxc 受控條件受控條件： 從倉(cāng)庫(kù)運(yùn)出總量不超過(guò)可用總量，運(yùn)入零售點(diǎn)的數(shù)量不低于需求量。從倉(cāng)庫(kù)運(yùn)出總量不超過(guò)可用總量，運(yùn)入零售點(diǎn)的數(shù)量不低于需求量。 由于總供給量等于總需求量，所以都是等號(hào)。即由于總供給量等于總需求量，所以都是等號(hào)。即 2 , 1;4321 iaxxxxiiiii 4 , 3 , 2 , 1;21 jbxxjjj 蘊(yùn)含約束蘊(yùn)含約束：數(shù)量非負(fù)：數(shù)量非負(fù)4 , 3 , 2 , 1, 2 , 1; 0 jixij 第第10頁(yè)頁(yè)模模 型型min 2141ijijijxc 2 , 1;4321 iaxxxxiiiii s.t. 4 , 3 ,

7、 2 , 1;21 jbxxjjj 4 , 3 , 2 , 1, 2 , 1; 0 jixij 第第11頁(yè)頁(yè)一一 般般 形形 式式 qjxqjxmpibxaxaxapibxaxaxatsxcxcxczjjininiiininiinn,.,2 , 1;,.,2 , 1; 0,.,1;,.,2 , 1;.min221122112211無(wú)無(wú)限限制制 目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件第第12頁(yè)頁(yè)注注 釋釋njxj,.,2 , 1; 為待定的為待定的決策變量決策變量， ),(21ncccc 為為價(jià)值向量?jī)r(jià)值向量， njcj,.,2 , 1; 為為價(jià)值系數(shù)價(jià)值系數(shù)， ),.,(21mbbbb 為為右端向量

8、右端向量， 矩陣矩陣 為為系數(shù)矩陣系數(shù)矩陣。 mnmmnnaaaaaaaaaA212222111211第第13頁(yè)頁(yè)規(guī)規(guī) 范范 形形 式式 0.min xbAxtsxc 第第14頁(yè)頁(yè)標(biāo)標(biāo) 準(zhǔn)準(zhǔn) 形形 式式 0.min xbAxtsxc 第第15頁(yè)頁(yè)概概 念念可行解（或可行點(diǎn)） ：可行解（或可行點(diǎn)） ：滿足所有約束條件的向量滿足所有約束條件的向量 ),(21nxxxx 可行集（或可行域）可行集（或可行域） ：所有的可行解的全體：所有的可行解的全體 0, xbAxxD 最優(yōu)解：最優(yōu)解：在可行域中目標(biāo)函數(shù)值最大（或最小）的可行解，最優(yōu)解的全體在可行域中目標(biāo)函數(shù)值最大（或最小）的可行解，最優(yōu)解的全體稱為

9、最優(yōu)解集合稱為最優(yōu)解集合 DyycxcDxO , 最優(yōu)值：最優(yōu)值：最優(yōu)解的目標(biāo)函數(shù)值最優(yōu)解的目標(biāo)函數(shù)值 Oxxcv , 第第16頁(yè)頁(yè)模模 型型 轉(zhuǎn)轉(zhuǎn) 換換v約束轉(zhuǎn)換約束轉(zhuǎn)換v實(shí)例實(shí)例令令自自由由變變量量 jjjxxx，其其中中 jjxx ,為為非非負(fù)負(fù)變變量量 求最大可以等價(jià)成求負(fù)的最小求最大可以等價(jià)成求負(fù)的最小 xcxc minmax v目標(biāo)轉(zhuǎn)換目標(biāo)轉(zhuǎn)換v變量轉(zhuǎn)換變量轉(zhuǎn)換第第17頁(yè)頁(yè)約約 束束 轉(zhuǎn)轉(zhuǎn) 換換v不等式變等式不等式變等式v不等式變不等式不等式變不等式ininiibxaxaxa 2211 ininiibxaxaxa 2211 ininiibxaxaxa 2211 v等式變不等式等式變

10、不等式第第18頁(yè)頁(yè)不不 等等 式式 變變 等等 式式ininiibxaxaxa 2211 0,2211 iiininiisbsxaxaxa 或或 ininiibxaxaxa 2211 0,2211 iiininiisbsxaxaxa 松弛變量松弛變量剩余變量剩余變量第第19頁(yè)頁(yè)不等式變不等式不等式變不等式ininiibxaxaxa 2211 ininiibxaxaxa 2211 或或 ininiibxaxaxa 2211 ininiibxaxaxa 2211 第第20頁(yè)頁(yè) 例例2.1.3 把問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式把問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式 052222.21max1212121xxxxxxxtsxxz

11、7 , 6 , 5 , 4 , 3 , 1; 05)(2)(22)(2.)(min743164315431431ixxxxxxxxxxxxxtsxxxzi 第第21頁(yè)頁(yè)可行區(qū)域與基本可行解可行區(qū)域與基本可行解 | 圖解法圖解法 |可行域的幾何結(jié)構(gòu)可行域的幾何結(jié)構(gòu)| 基本可行解與基本定理基本可行解與基本定理第第22頁(yè)頁(yè)圖圖 解解 法法對(duì)于只有兩個(gè)變量的線性規(guī)劃問(wèn)題可以用圖解法求解：對(duì)于只有兩個(gè)變量的線性規(guī)劃問(wèn)題可以用圖解法求解： 變量用直角坐標(biāo)系中的點(diǎn)表示變量用直角坐標(biāo)系中的點(diǎn)表示 約束條件用坐標(biāo)系中的半空間或直線的交表示約束條件用坐標(biāo)系中的半空間或直線的交表示 可行區(qū)域是一個(gè)凸多面體可行區(qū)域是

12、一個(gè)凸多面體 目標(biāo)函數(shù)用一組等值線表示，沿著增加或減少的方向目標(biāo)函數(shù)用一組等值線表示，沿著增加或減少的方向 移動(dòng)，與可行域最后的交點(diǎn)就是最優(yōu)解。移動(dòng)，與可行域最后的交點(diǎn)就是最優(yōu)解。 第第23頁(yè)頁(yè)例例2.2.1 解線性規(guī)劃解線性規(guī)劃 2221 xx 2221 xx 521 xx 最優(yōu)解（最優(yōu)解（1，4） 052222.max121212121xxxxxxxtsxxz第第24頁(yè)頁(yè)當(dāng)當(dāng)目目標(biāo)標(biāo)函函數(shù)數(shù)該該邊邊后后，等等值值線線的的方方向向會(huì)會(huì)發(fā)發(fā)生生改改變變， 如如果果等等值值線線與與某某個(gè)個(gè)約約束束對(duì)對(duì)應(yīng)應(yīng)的的函函數(shù)數(shù)直直線線平平行行， 則則該該函函數(shù)數(shù)值值線線上上的的所所有有可可行行解解都都是是

13、最最優(yōu)優(yōu)解解 2221 xx 2221 xx 最最優(yōu)優(yōu)解解（1，4） 521 xx第第25頁(yè)頁(yè)注注 釋釋可能出現(xiàn)的情況可能出現(xiàn)的情況：| 可行域是空集可行域是空集| 可行域無(wú)界無(wú)最優(yōu)解可行域無(wú)界無(wú)最優(yōu)解| 最優(yōu)解存在且唯一，則一定在頂點(diǎn)上達(dá)到最優(yōu)解存在且唯一，則一定在頂點(diǎn)上達(dá)到| 最優(yōu)解存在且不唯一，一定存在頂點(diǎn)是最優(yōu)解最優(yōu)解存在且不唯一，一定存在頂點(diǎn)是最優(yōu)解第第26頁(yè)頁(yè)可行域的幾何結(jié)構(gòu)可行域的幾何結(jié)構(gòu)|基本假設(shè)基本假設(shè)|凸集凸集|可行域的凸性可行域的凸性第第27頁(yè)頁(yè)基基 本本 假假 設(shè)設(shè)考慮慮線線性性規(guī)規(guī)劃劃的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)形形式式 其其中中nmmnRARbRcx ,，并并且且假假定定可可行行域

14、域 0, xbAxRxDn不不空空，系系數(shù)數(shù)矩矩陣陣A是是行行 滿滿秩秩的的，mAr )(，否否則則的的話話可可以以去去掉掉多多余余約約束束。 0.minxbAxtsxc第第28頁(yè)頁(yè)凸凸 集集定義定義 2.2.1：設(shè)：設(shè)nRS 是是n維歐氏空間的點(diǎn)集，若對(duì)任意維歐氏空間的點(diǎn)集，若對(duì)任意 SySx ,的和任意的和任意1 , 0 都有都有 就稱就稱S是一個(gè)是一個(gè)凸集凸集。 定理定理 2.2.1 線性規(guī)劃的可行域線性規(guī)劃的可行域0, xbAxxD是凸集是凸集 定理定理 2.2.2 任意多個(gè)凸集的交還是凸集任意多個(gè)凸集的交還是凸集 Syx )1( 第第29頁(yè)頁(yè)可可 行行 域域 的的 凸凸 性性超平面超

15、平面 bxaRxHn 半空間半空間 bxaRxHn ；bxaRxHn 多面凸集多面凸集 ,.,2, 1;,.,2 , 1;qpppibxapibxaRxSiiiin 定義定義 2.2.2：設(shè)：設(shè)S為凸集為凸集Sx ，如果對(duì)任意，如果對(duì)任意Szy ,和和10 ， 都有都有zyx)1( ,則稱則稱 x 為為 S 的的頂點(diǎn)頂點(diǎn)。 第第30頁(yè)頁(yè)問(wèn)問(wèn) 題題1.可可行行域域頂頂點(diǎn)點(diǎn)的的個(gè)個(gè)數(shù)數(shù)是是否否有有限限？ 2.最最優(yōu)優(yōu)解解是是否否一一定定在在可可行行域域頂頂點(diǎn)點(diǎn)上上達(dá)達(dá)到到？ 3.如如何何找找到到頂頂點(diǎn)點(diǎn)？ 4.如如何何從從一一個(gè)個(gè)頂頂點(diǎn)點(diǎn)轉(zhuǎn)轉(zhuǎn)移移到到另另一一個(gè)個(gè)頂頂點(diǎn)點(diǎn)? 第第31頁(yè)頁(yè)基基 本本

16、可可 行行 解解 與與 基基 本本 定定 理理|定義定義|基本定理基本定理|問(wèn)題問(wèn)題第第32頁(yè)頁(yè)基基 本本 可可 行行 解解 定定 義義令令),(NBA ， x=(Bx,Nx)。 bAx 分塊分塊 bNxBxNB 左乘左乘1 B bBNxBxNB11 即即 NBNxBbBx11 Nx=0 01bBx 第第33頁(yè)頁(yè)定義定義2.2.2： 設(shè)設(shè)B是秩為是秩為m的約束矩陣的約束矩陣A的一個(gè)的一個(gè) m階滿秩階滿秩子方陣，則稱子方陣，則稱B為一個(gè)為一個(gè)基基；B中中 m個(gè)線性無(wú)關(guān)的列向量稱個(gè)線性無(wú)關(guān)的列向量稱為為基向量基向量，變量，變量 x中與之對(duì)應(yīng)的中與之對(duì)應(yīng)的 m個(gè)分量稱為個(gè)分量稱為基變量基變量，其，其

17、余的變量為余的變量為非基變量非基變量， 令所有的非基變量取值為， 令所有的非基變量取值為 0， 得到的解， 得到的解 01bBx稱為相應(yīng)于稱為相應(yīng)于B的的基本解基本解。當(dāng)當(dāng)01 bB則稱基本解為則稱基本解為基本可行解基本可行解，這時(shí)對(duì)應(yīng)的基陣，這時(shí)對(duì)應(yīng)的基陣B為為可行基可行基。 如果如果01 bB則稱該則稱該基可行解為非退化的基可行解為非退化的，如果一個(gè)線，如果一個(gè)線性規(guī)劃的所有基可行解都是非退化的則稱該性規(guī)劃的所有基可行解都是非退化的則稱該規(guī)劃為非退化規(guī)劃為非退化的的。 第第34頁(yè)頁(yè)例例 考慮問(wèn)題：考慮問(wèn)題： 5 , 4 , 3 , 2 , 1; 052222.min52142132121j

18、xxxxxxxxxxtsxxzj 系數(shù)矩陣系數(shù)矩陣 100110102100112A 基陣為基陣為 1000100011B 1010110022B 對(duì)應(yīng)的基解分別為對(duì)應(yīng)的基解分別為 )5 , 2 , 2 , 0 , 0(1x 和和 )6 , 3 , 0 , 0 , 1(2x，其中，其中 x1 為基本可行解，為基本可行解， x2 不是基本可行解。不是基本可行解。 第第35頁(yè)頁(yè)基基 本本 定定 理理定定理理2.2.3 可可行行解解 x是是基基本本可可行行解解的的充充要要條條件件是是它它的的正正分分量量所所對(duì)對(duì)應(yīng)應(yīng)的的矩矩陣陣A中中列列向向量量線線性性無(wú)無(wú)關(guān)關(guān)。 定定理理 2.2.4 x是是基基本本

19、可可行行解解的的充充要要條條件件是是 x是是可可行行域域 D的的頂頂點(diǎn)點(diǎn)。 定定理理 2.2.5 一一個(gè)個(gè)標(biāo)標(biāo)準(zhǔn)準(zhǔn)的的 LP 問(wèn)問(wèn)題題如如果果有有可可行行解解， 則則至至少少有有一一個(gè)個(gè)基基本本可可行行解解 定定理理 2.2.6 一一個(gè)個(gè)標(biāo)標(biāo)準(zhǔn)準(zhǔn)的的 LP 問(wèn)問(wèn)題題如如果果有有有有限限的的最最優(yōu)優(yōu)值值， 則則一一定定存存在在一一個(gè)個(gè)基基本本可可行行解解是是最最優(yōu)優(yōu)解解。 第第36頁(yè)頁(yè)問(wèn)問(wèn) 題題1 基本可行解不一定都是最優(yōu)解，基本可行解不一定都是最優(yōu)解， 最優(yōu)解也不一定都是基本解最優(yōu)解也不一定都是基本解 2 如果有兩個(gè)基本可行解是最優(yōu)解，如果有兩個(gè)基本可行解是最優(yōu)解， 則兩解的凸組合也都是最優(yōu)解

20、。則兩解的凸組合也都是最優(yōu)解。 3 如果最優(yōu)解不唯一，如果最優(yōu)解不唯一， 則會(huì)有多個(gè)基本可行解是最優(yōu)解，它們必然在同一個(gè)面上。則會(huì)有多個(gè)基本可行解是最優(yōu)解，它們必然在同一個(gè)面上。 4行解個(gè)數(shù)有限，可以在基可行解中尋找最優(yōu)解。行解個(gè)數(shù)有限，可以在基可行解中尋找最優(yōu)解。 剩余的問(wèn)題是如何判斷一個(gè)基可行解是最優(yōu)解，剩余的問(wèn)題是如何判斷一個(gè)基可行解是最優(yōu)解， 如果不是則如何從一個(gè)基可行解轉(zhuǎn)到另一個(gè)基可行解。如果不是則如何從一個(gè)基可行解轉(zhuǎn)到另一個(gè)基可行解。 第第37頁(yè)頁(yè)單單 純純 形形 算算 法法|理論方法理論方法|算法步驟算法步驟|單純形表單純形表|算例算例第第38頁(yè)頁(yè)理理 論論 方方 法法定定理理

21、2.3.1（最最優(yōu)優(yōu)性性準(zhǔn)準(zhǔn)則則）如如果果0 ，則則基基可可行行解解x為為原原問(wèn)問(wèn)題題的的最最優(yōu)優(yōu)解解。 定定理理 2.3.2 如如果果向向量量 的的第第k個(gè)個(gè)分分量量0 k ，而而向向量量01 kAB，則則原原問(wèn)問(wèn)題題無(wú)無(wú)界界。 定定理理 2.3.3 對(duì)對(duì)于于非非退退化化的的基基本本可可行行解解x， 若若向向量量 的的第第k個(gè)個(gè)分分量量0 k ，而而向向量量.1kAB 至至少少有有一一個(gè)個(gè)正正分分量量，則則可可以以找找到到一一個(gè)個(gè)新新的的基基本本可可行行解解x 使使得得xcxc 。 第第39頁(yè)頁(yè)定理定理2.3.1 給定一個(gè)非退化的基可行解給定一個(gè)非退化的基可行解 x，對(duì)應(yīng)的可行基為，對(duì)應(yīng)的可

22、行基為 B，則等式約束變?yōu)椋海瑒t等式約束變?yōu)椋?bBNxBxNB11 典式典式 NBNxBbBx11 目標(biāo)函數(shù)目標(biāo)函數(shù)NNBBxcxcxc NNNBxcNxBbBc )(11 NNBBxcNBcbBc)(11 令令 NBNcNBc1 ，0 B ，則則xbBcxcB 1 規(guī)劃等價(jià)于規(guī)劃等價(jià)于 0.min111xbBNxBxtsxbBcNBB 第第40頁(yè)頁(yè)定定 理理 2.3.2令令 )0 , 0 , 1 , 0 , 0 ,(1kkABb其基變量取值為其基變量取值為。非基變量中第非基變量中第 k 個(gè)個(gè) 非基變量取值為非基變量取值為 1，其它為，其它為 0。令令kkbxxx ，其中，其中0 kx。由于

23、由于0 x， 可知對(duì)任意可知對(duì)任意0 kx，0 x，且滿足，且滿足bBNxBxNB11 和和xcxc 。 當(dāng)當(dāng) x時(shí)，時(shí)， kkxxcxc 。 第第41頁(yè)頁(yè)定定 理理 2.3.3 令令 )0 , 0 , 1 , 0 , 0 ,(1kkABb其其基基變變量量取取值值為為。非非基基變變量量中中第第 k 個(gè)個(gè) 非非基基變變量量取取值值為為 1，其其它它為為 0。令令kkbxxx ，其其中中0 kx。為為了了保保證證 0 kkbxxx，即即要要求求對(duì)對(duì)于于.1kAB 的的正正分分量量0)(1 ikikABa，滿滿足足 0 kikixab，其其中中iibBb)(1 。因因而而kikixab /， 令令,

24、.,2 , 1, 0/minmiaabikiki ，令令kbxx 則則顯顯然然 x是是個(gè)個(gè)可可行行解解。 在在原原基基陣陣中中以以第第 k 列列替替代代第第 i 列列，則則顯顯然然所所得得子子陣陣可可逆逆，所所以以 x是是個(gè)個(gè)基基可可 行行解解。其其對(duì)對(duì)應(yīng)應(yīng)的的目目標(biāo)標(biāo)函函數(shù)數(shù)值值xcxcxck 。 第第42頁(yè)頁(yè)算算 法法 步步 驟驟step1 找找一一個(gè)個(gè)初初始始可可行行基基 step2 求求出出典典式式和和檢檢驗(yàn)驗(yàn)數(shù)數(shù) step3 求求,.,2 , 1maxnjjk step4 如如果果0 k 則則該該基基可可行行解解就就是是最最優(yōu)優(yōu)解解停停止止；否否則則轉(zhuǎn)轉(zhuǎn) step5； step5 如

25、如果果01 kAB，則則問(wèn)問(wèn)題題無(wú)無(wú)最最優(yōu)優(yōu)解解，停停止止；否否則則轉(zhuǎn)轉(zhuǎn) step6 step6 求求rkrikikiabmiaab/,.,2 , 1, 0/min step7 以以kA替替代代rA得得到到一一個(gè)個(gè)新新的的基基，轉(zhuǎn)轉(zhuǎn) step2； 第第43頁(yè)頁(yè)單單 純純 形形 表表一般假設(shè)當(dāng)前的基一般假設(shè)當(dāng)前的基),.,(21mAAAB 對(duì)應(yīng)的單純形表為對(duì)應(yīng)的單純形表為 1x rx mx 1mx kx nx 1 11 ma ka1 na1 1 1rma rka rna 1 1mma mka mna 1b rb mb 第第44頁(yè)頁(yè)如如果果kx為為入入基基變變量量，rx為為出出基基變變量量，則則經(jīng)

26、經(jīng)過(guò)過(guò)變變換換單單純純形形表表為為 1x rx mx 1mx kx nx 1 ra1 11ma 0 na1 1/rka 1rma 1 rna mra 1 1mma 0 mna 1b rb mb 其其中中rkikrjijijaaaaa/ kjrimi ,.,2 , 1;rkrjrjaaa/ ， rkrrabb/ ，rkiikiiababb/ 。 第第45頁(yè)頁(yè)目目標(biāo)標(biāo)函函數(shù)數(shù)NNBBxcNBcbBcz)(11 等等價(jià)價(jià)于于 bBcxcNBczBNNB11)( 由由于于0 B ， NBNcNBc1 ，所所以以bBcxzB1 。把把 Z 看看成成變變量量在在 單單純純形形表表中中加加上上一一列列，同同

27、時(shí)時(shí)加加上上一一行行描描述述方方程程bBcxzB1 ，則則可可以以 得得到到新新的的單單純純形形表表： Z 1x rx mx 1mx kx nx 1 0 0 0 1m k n bBcB1 1 11 ma ka1 na1 1 1rma rka rna 1 1mma mka mna 1b rb mb 第第46頁(yè)頁(yè)當(dāng)當(dāng)進(jìn)進(jìn)行行轉(zhuǎn)轉(zhuǎn)換換時(shí)時(shí)只只需需要要把把k 轉(zhuǎn)轉(zhuǎn)換換成成 0 對(duì)對(duì)應(yīng)應(yīng)其其它它位位置置等等價(jià)價(jià)變變換換即即可可。 z 1x rx mx 1mx kx nx 1 0 -k/rka 0 1m 0 n bBcB1 1 ra1 11ma 0 na1 1/rka 1rma 1 rna mra 1 1

28、mma 0 mna 1b rb mb 其其中中rkjrjjjaa/ ；rkkrBBabbBcbBc/11 。 第第47頁(yè)頁(yè)算算 例例例例 2.3.1 求解問(wèn)題求解問(wèn)題 5,.,2 , 1; 021322.2min53243232132jxxxxxxxxxxtsxxzj 第第48頁(yè)頁(yè)初初 始始 單單 純純 形形 表表以以1x、4x和和5x為基變量就可以得到初始基可行解為基變量就可以得到初始基可行解 )2 , 1 , 0 , 0 , 2(， 其對(duì)應(yīng)的單純形表為其對(duì)應(yīng)的單純形表為 1x 2x 3x 4x 5x 1 -2 1 -2 1 1 -3 1 1 -1 1 2 1 2 第第49頁(yè)頁(yè)迭迭 代代 1

29、由于由于012 ，所以該基可行解不是最優(yōu)解，同時(shí)系數(shù)矩陣該列有大于，所以該基可行解不是最優(yōu)解，同時(shí)系數(shù)矩陣該列有大于 0的元素，所以取的元素，所以取2x為入基變量。計(jì)算為入基變量。計(jì)算1,min1211 ，所以取第二個(gè)約束，所以取第二個(gè)約束對(duì)應(yīng)的基變量對(duì)應(yīng)的基變量4x為出基變量，就可以得到一個(gè)新的基可行解，在上表中為出基變量，就可以得到一個(gè)新的基可行解，在上表中把把2x對(duì)應(yīng)的列變成單位向量， 系數(shù)矩陣第對(duì)應(yīng)的列變成單位向量， 系數(shù)矩陣第 2 行對(duì)應(yīng)的元素為行對(duì)應(yīng)的元素為 1， 則可以得， 則可以得到該基可行解的單純形表到該基可行解的單純形表 1x 2x 3x 4x 5x 0 1 -1 -1 1

30、 0 -5 2 1 -3 1 0 2 -1 1 4 1 1 第第50頁(yè)頁(yè)迭迭 代代 2由由于于013 ，所所以以該該基基可可行行解解不不是是最最優(yōu)優(yōu)解解，同同時(shí)時(shí)系系數(shù)數(shù)矩矩陣陣該該列列有有大大于于 0的的元元素素，所所以以取取3x為為入入基基變變量量。計(jì)計(jì)算算21 ，所所以以取取第第 3 個(gè)個(gè)約約束束對(duì)對(duì)應(yīng)應(yīng)的的基基變變量量5x為為出出基基變變量量，就就可可以以得得到到一一個(gè)個(gè)新新的的基基可可行行解解，在在上上表表中中把把3x對(duì)對(duì)應(yīng)應(yīng)的的列列變變成成單單位位向向量量，系系數(shù)數(shù)矩矩陣陣第第 3 行行對(duì)對(duì)應(yīng)應(yīng)的的元元素素為為 1，則則可可以以得得到到該該基基可可行行解解的的單單純純形形表表： 1

31、x 2x 3x 4x 5x 0 0 -1/2 -1/2 -3/2 1 0 -5 -1/2 5/2 1 0 -1/2 3/2 0 1 -1/2 1/2 13/2 5/2 1/2 第第51頁(yè)頁(yè)由于檢驗(yàn)數(shù)都小于等于由于檢驗(yàn)數(shù)都小于等于 0，所以該基可行解就是最優(yōu)解，所以該基可行解就是最優(yōu)解， 對(duì)應(yīng)的最優(yōu)解為對(duì)應(yīng)的最優(yōu)解為)0 , 0 , 2/1 , 2/5 , 2/13(，最優(yōu)值為，最優(yōu)值為-3/2。 注：注： 1. 該算法在實(shí)際應(yīng)用中非常有效，被廣泛采用，該算法在實(shí)際應(yīng)用中非常有效，被廣泛采用， 但在理論上不是多項(xiàng)式時(shí)間算法。但在理論上不是多項(xiàng)式時(shí)間算法。 2. 現(xiàn)在還有待解決的問(wèn)題是如何給出初始

32、基可行現(xiàn)在還有待解決的問(wèn)題是如何給出初始基可行 解以及出現(xiàn)退化的時(shí)候如何處理。解以及出現(xiàn)退化的時(shí)候如何處理。 第第52頁(yè)頁(yè)初初 始始 解解|兩階段法兩階段法|大大M法法|說(shuō)明說(shuō)明第第53頁(yè)頁(yè)兩兩 階階 段段 法法|基本思想基本思想 第一階段第一階段：通過(guò)求解輔助問(wèn)題的最優(yōu)基可行通過(guò)求解輔助問(wèn)題的最優(yōu)基可行 解得到原問(wèn)題的初始基可行解。解得到原問(wèn)題的初始基可行解。 第二階段第二階段：求原問(wèn)題的最優(yōu)解求原問(wèn)題的最優(yōu)解|算例算例第第54頁(yè)頁(yè)輔輔 助助 問(wèn)問(wèn) 題題設(shè)設(shè)原原問(wèn)問(wèn)題題為為 ( 2.4.1) 0.minxbAxtsxc 不不妨妨假假設(shè)設(shè)0 b，如如果果某某一一個(gè)個(gè)元元素素小小于于 0，該該方

33、方程程兩兩邊邊乘乘于于-1 后后則則可可以以使使右右端端數(shù)數(shù)變變成成正正數(shù)數(shù)。考考慮慮如如下下問(wèn)問(wèn)題題 （2.4.2） 0, 0.min1aamnniixxbxAxtsxg 其其中中 ),.,(21mnnnaxxxx 第第55頁(yè)頁(yè)原原 輔輔 助助 題題 問(wèn)問(wèn) 與與 題題 的的 關(guān)關(guān) 系系1. 顯然如果原問(wèn)題顯然如果原問(wèn)題( 2.4.1)有可行解，則規(guī)劃有可行解，則規(guī)劃( 2.4.2)的最優(yōu)值為的最優(yōu)值為 0，反之亦然。，反之亦然。 2由于由于0 b，所以以，所以以 ),.,(21mnnnaxxxx為基變量，就可以得到規(guī)劃（為基變量，就可以得到規(guī)劃（2.4.2）的初始基可行解的初始基可行解 ),

34、 0(b。 3規(guī)劃（規(guī)劃（2.4.2）有可行解）有可行解 ), 0(b，同時(shí)，同時(shí)0 ax，所以，所以01 mnniix。即問(wèn)題的目標(biāo)函數(shù)有下界，即問(wèn)題的目標(biāo)函數(shù)有下界，所所以該問(wèn)題一定有最優(yōu)解。以該問(wèn)題一定有最優(yōu)解。 4因此我們可以首先求規(guī)劃因此我們可以首先求規(guī)劃( 2.4.2)的最優(yōu)基可行解的最優(yōu)基可行解),(axx，如果最優(yōu)值為，如果最優(yōu)值為 0，則，則0 ax，所以，所以x是問(wèn)題是問(wèn)題( 2.4.1)的可行解。的可行解。由于由于),(axx是規(guī)劃（是規(guī)劃（2.4.2）的基可行解，所以）的基可行解，所以其非零分量對(duì)應(yīng)系數(shù)矩陣的列向量線性無(wú)關(guān)。其非零分量對(duì)應(yīng)系數(shù)矩陣的列向量線性無(wú)關(guān)。所以所

35、以x的非零分量對(duì)應(yīng)的系數(shù)矩陣的列的非零分量對(duì)應(yīng)的系數(shù)矩陣的列向量也線性無(wú)關(guān)，所以向量也線性無(wú)關(guān)，所以x是問(wèn)題是問(wèn)題( 2.4.1)的基可行解。的基可行解。在規(guī)劃在規(guī)劃（2.4.2） ，我們稱） ，我們稱ax為人工變?yōu)槿斯ぷ兞俊Ａ俊?第第56頁(yè)頁(yè)求求 輔輔 助助 問(wèn)問(wèn) 題題 的的 三三 種種 情情 況況101 mnniix且且ax為為非非基基變變量量，則則此此時(shí)時(shí)x是是問(wèn)問(wèn)題題( 2.4.1)的的基基可可行行解解， 且且基基變變量量不不變變。在在最最優(yōu)優(yōu)基基可可行行解解的的單單純純形形表表里里刪刪除除 ax對(duì)對(duì)應(yīng)應(yīng)的的列列， 同同時(shí)時(shí)計(jì)計(jì)算算出出檢檢驗(yàn)驗(yàn)數(shù)數(shù)就就可可以以得得到到原原問(wèn)問(wèn)題題的的單

36、單純純形形表表。 201 mnniix且且ax中中有有部部分分變變量量為為基基變變量量，此此時(shí)時(shí)x是是問(wèn)問(wèn)題題( 2.4.1)的的基基 可可行行解解，不不同同的的是是基基變變量量會(huì)會(huì)有有些些改改變變。 301 mnniix，則則原原問(wèn)問(wèn)題題沒(méi)沒(méi)有有可可行行解解。 第第57頁(yè)頁(yè)算算 例例例例 2.4.1 求解求解 如果以如果以4x、5x為基變量，則可以得到該問(wèn)題的基解為基變量，則可以得到該問(wèn)題的基解 )1, 2, 0 , 0 , 0(， 不是可行解，而其第一個(gè)基可行解不能直接給出，下面用兩階段法求解。不是可行解，而其第一個(gè)基可行解不能直接給出，下面用兩階段法求解。 5 , 4 , 3 , 2 ,

37、 1;1226.215min5321432131jxxxxxxxxxtsxxzj第第58頁(yè)頁(yè)第第 1 階階 段段首先引入人工變量，考慮問(wèn)題首先引入人工變量，考慮問(wèn)題 以以6x和和7x為基變量可得其第一個(gè)基可行解為基變量可得其第一個(gè)基可行解 )1 , 2 , 0 , 0 , 0 , 0 , 0(， 其對(duì)應(yīng)的單純形表為其對(duì)應(yīng)的單純形表為 7 , 6 , 5 , 4 , 3 , 2 , 1;1226.min753216432176jxxxxxxxxxxxtsxxzj第第59頁(yè)頁(yè)第第 1 階階 段段 1x 2x 3x 4x 5x 6x 7x -5 -21 0 2 8 -1 -1 3 1 -1 6 -1

38、 1 1 1 2 -1 1 2 1 由于由于083 ，所以該基可行解不是最優(yōu)解，同時(shí)系數(shù)矩陣該列有大于，所以該基可行解不是最優(yōu)解，同時(shí)系數(shù)矩陣該列有大于 0 的的元素，所以取元素，所以取3x為入基變量。為入基變量。計(jì)算計(jì)算622162,min ，所以取第，所以取第 1 個(gè)約束對(duì)應(yīng)個(gè)約束對(duì)應(yīng)的基變量的基變量6x為出基變量， 就可以得到一個(gè)新的基可行解， 在上表中把為出基變量， 就可以得到一個(gè)新的基可行解， 在上表中把3x對(duì)應(yīng)對(duì)應(yīng)的列變成單位向量，系數(shù)矩陣第的列變成單位向量，系數(shù)矩陣第 1 行對(duì)應(yīng)的元素為行對(duì)應(yīng)的元素為 1， 則可以得到該基可行解的單純形表則可以得到該基可行解的單純形表 第第60頁(yè)

39、頁(yè)第第 1 階階 段段1x 2x 3x 4x 5x 6x 7x -3/2 -7/2 -7/2 21/6 7 2/3 4/3 1/3 -1 -4/3 1/3 1/6 -1/6 1 -1/6 1/6 2/3 4/3 1/3 -1 -1/3 1 1/3 1/3 由于由于03/42 ，所以該基可行解不是最優(yōu)解，同時(shí)系數(shù)矩陣該，所以該基可行解不是最優(yōu)解，同時(shí)系數(shù)矩陣該 列有大于列有大于 0 的元素，所以取的元素，所以取 x2為入基變量。為入基變量。計(jì)算計(jì)算3431/ ，所以，所以 取第取第 2 個(gè)約束對(duì)應(yīng)的基變量個(gè)約束對(duì)應(yīng)的基變量7x為出基變量，就可以得到一個(gè)新的為出基變量，就可以得到一個(gè)新的 基可行解

40、，在上表中把基可行解，在上表中把 x2對(duì)應(yīng)的列變成單位向量，系數(shù)矩陣第對(duì)應(yīng)的列變成單位向量，系數(shù)矩陣第 2 行對(duì)應(yīng)的元素為行對(duì)應(yīng)的元素為 1， 則可以得到該基可行解的單純形表則可以得到該基可行解的單純形表 第第61頁(yè)頁(yè)第第 1 階階 段段1x 2x 3x 4x 5x 6x 7x 1/4 -21/8 -21/8 21/8 21/8 63/8 -1 -1 0 1/4 1 -1/8 -1/8 1/8 1/8 1/2 1 1/4 -3/4 -1/4 3/4 3/8 1/4 由于檢驗(yàn)數(shù)都小于等于由于檢驗(yàn)數(shù)都小于等于 0，所以對(duì)應(yīng)的基可行解就是輔助問(wèn)題，所以對(duì)應(yīng)的基可行解就是輔助問(wèn)題 的最優(yōu)解，最優(yōu)值為的

41、最優(yōu)解，最優(yōu)值為 0，且人工變量都是非基變量，所以得到，且人工變量都是非基變量，所以得到 原問(wèn)題的基可行解，對(duì)應(yīng)的基變量為原問(wèn)題的基可行解，對(duì)應(yīng)的基變量為 x2和和 x3， 對(duì)應(yīng)的單純形表為對(duì)應(yīng)的單純形表為 第第62頁(yè)頁(yè)第第 1 階階 段段 1x 2x 3x 4x 5x 1/4 -21/8 -21/8 63/8 1/4 1 -1/8 -1/8 1/2 1 1/4 -3/4 3/8 1/4 第第63頁(yè)頁(yè)第第 2 階階 段段由于由于04/11 ，所以該基可行解不是原問(wèn)題最優(yōu)解，同時(shí)，所以該基可行解不是原問(wèn)題最優(yōu)解，同時(shí) 系數(shù)矩陣該列有大于系數(shù)矩陣該列有大于 0 的元素，所以取的元素，所以取 x1為

42、入基變量。計(jì)算為入基變量。計(jì)算 214121414183/,/min ，所以取第，所以取第 2 個(gè)約束對(duì)應(yīng)的基變量個(gè)約束對(duì)應(yīng)的基變量 x2為為 出基變量，就可以得到一個(gè)新的基可行解，在上表中把出基變量，就可以得到一個(gè)新的基可行解，在上表中把 x1對(duì)對(duì) 應(yīng)的列變成單位向量，系數(shù)矩陣第應(yīng)的列變成單位向量，系數(shù)矩陣第 2 行對(duì)應(yīng)的元素為行對(duì)應(yīng)的元素為 1，則，則 可以得到該基可行解的單純形表可以得到該基可行解的單純形表 1x 2x 3x 4x 5x -1/2 -11/4 -9/4 31/4 -1/2 1 -1/4 1/4 1 2 1/2 -3/2 1/4 1/2 由于檢驗(yàn)數(shù)都小于等于由于檢驗(yàn)數(shù)都小于

43、等于 0，所以對(duì)應(yīng)的基可行解就是原問(wèn)，所以對(duì)應(yīng)的基可行解就是原問(wèn) 題的最優(yōu)解，最優(yōu)值為題的最優(yōu)解，最優(yōu)值為 31/4，對(duì)應(yīng)的最優(yōu)解為，對(duì)應(yīng)的最優(yōu)解為 ) 0 , 0 , 4/ 1 , 0 , 2/ 1 (。 第第64頁(yè)頁(yè)大大 M 法法求解輔助問(wèn)題求解輔助問(wèn)題 當(dāng)當(dāng) M 為足夠大的正數(shù)時(shí)其最優(yōu)解對(duì)應(yīng)的人工變量為足夠大的正數(shù)時(shí)其最優(yōu)解對(duì)應(yīng)的人工變量0 ax，從從 而最優(yōu)解對(duì)應(yīng)于原問(wèn)題的可行解，且目標(biāo)函數(shù)值相等；而最優(yōu)解對(duì)應(yīng)于原問(wèn)題的可行解，且目標(biāo)函數(shù)值相等；同時(shí)同時(shí) 原問(wèn)題的任意可行解原問(wèn)題的任意可行解 x 對(duì)應(yīng)于輔助問(wèn)題的可行解對(duì)應(yīng)于輔助問(wèn)題的可行解 )0 ,(x，且目且目 標(biāo)函數(shù)值相等。標(biāo)函數(shù)

44、值相等。所以兩個(gè)規(guī)劃最優(yōu)值相等，且輔助問(wèn)題所以兩個(gè)規(guī)劃最優(yōu)值相等，且輔助問(wèn)題的最的最 優(yōu)解優(yōu)解 )0 ,(x對(duì)應(yīng)可得原問(wèn)題的最優(yōu)解對(duì)應(yīng)可得原問(wèn)題的最優(yōu)解 x。因此只需求解輔因此只需求解輔助問(wèn)助問(wèn) 題題就可求得原問(wèn)題的最優(yōu)解。就可求得原問(wèn)題的最優(yōu)解。 0, 0.min1aamnniixxbxAxtsxMxcz第第65頁(yè)頁(yè)說(shuō)說(shuō) 明明(1) 退化問(wèn)題的處理退化問(wèn)題的處理 攝動(dòng)方法、字典序方法和攝動(dòng)方法、字典序方法和 Bland 反循環(huán)方法反循環(huán)方法 (2) 修正的單純形算法修正的單純形算法 (3) 特殊問(wèn)題的處理特殊問(wèn)題的處理 運(yùn)輸問(wèn)題、變量有界線性規(guī)劃問(wèn)題等運(yùn)輸問(wèn)題、變量有界線性規(guī)劃問(wèn)題等 第第6

45、6頁(yè)頁(yè)對(duì)對(duì) 偶偶 理理 論論|對(duì)偶規(guī)劃對(duì)偶規(guī)劃|對(duì)偶理論對(duì)偶理論|對(duì)偶單純形算法對(duì)偶單純形算法第第67頁(yè)頁(yè)對(duì)對(duì) 偶偶 規(guī)規(guī) 劃劃|標(biāo)準(zhǔn)形式線性規(guī)劃的對(duì)偶規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃的對(duì)偶規(guī)劃|規(guī)范形式線性規(guī)劃的對(duì)偶規(guī)劃規(guī)范形式線性規(guī)劃的對(duì)偶規(guī)劃|一般形式線性規(guī)劃的對(duì)偶規(guī)劃一般形式線性規(guī)劃的對(duì)偶規(guī)劃|實(shí)例實(shí)例第第68頁(yè)頁(yè)標(biāo)準(zhǔn)形式的對(duì)偶規(guī)劃標(biāo)準(zhǔn)形式的對(duì)偶規(guī)劃考考慮慮線線性性規(guī)規(guī)劃劃的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)形形式式 ( () ) 其其中中nmmnRARbRcx ,。 根根據(jù)據(jù)單單純純形形理理論論，若若x是是最最優(yōu)優(yōu)基基可可行行解解， 其其對(duì)對(duì)應(yīng)應(yīng)的的基基陣陣為為 B 則則其其檢檢驗(yàn)驗(yàn)數(shù)數(shù)為為01 BBBcBBc ， 0

46、1 NBNcNBc ，同同時(shí)時(shí)bBxB1 ，0 Nx，最最優(yōu)優(yōu) 值值為為bBcxcB1 。如如果果令令1 BcB ，則則有有 0 cA xcb 0.minxbAxtsxc第第69頁(yè)頁(yè)同同時(shí)時(shí) 是是下下列列規(guī)規(guī)劃劃的的可可行行解解 ( () ) 對(duì)對(duì)于于規(guī)規(guī)劃劃( () )的的任任意意可可行行解解x x和和規(guī)規(guī)劃劃( () ) 的的任任意意可可行行解解 ，由由于于0 x所所以以有有 由由此此可可知知 是是規(guī)規(guī)劃劃( () )的的最最優(yōu)優(yōu)解解，反反之之亦亦然然。 兩兩個(gè)個(gè)規(guī)規(guī)劃劃的的最最有有解解之之間間存存在在著著密密切切的的關(guān)關(guān)系系，通通過(guò)過(guò) 一一個(gè)個(gè)規(guī)規(guī)劃劃可可以以得得到到另另一一個(gè)個(gè)規(guī)規(guī)劃劃

47、的的最最優(yōu)優(yōu)解解。同同時(shí)時(shí)從從 形形式式上上兩兩者者之之間間也也有有本本質(zhì)質(zhì)的的相相似似，給給定定),(cbA兩兩 個(gè)個(gè)規(guī)規(guī)劃劃相相伴伴而而存存在在，因因而而稱稱兩兩個(gè)個(gè)規(guī)規(guī)劃劃互互為為對(duì)對(duì)偶偶規(guī)規(guī) 劃劃。 cAtsb .maxxcAxb 第第70頁(yè)頁(yè)規(guī)規(guī) 范范 形形 式式 的的 對(duì)對(duì) 偶偶 規(guī)規(guī) 劃劃規(guī)規(guī)范范形形式式的的線線性性規(guī)規(guī)劃劃 0.minxbAxtsxc 0,.minyxbIyAxtsxc 其其對(duì)對(duì)偶偶規(guī)規(guī)劃劃為為 )0 ,(),(.max cIAtsb 0.max cAtsb 第第71頁(yè)頁(yè)一般形式的對(duì)偶規(guī)劃一般形式的對(duì)偶規(guī)劃對(duì)于一般形式的線性規(guī)劃對(duì)于一般形式的線性規(guī)劃 通過(guò)把其轉(zhuǎn)

48、化為標(biāo)準(zhǔn)形式同樣可以得到其對(duì)偶規(guī)劃為通過(guò)把其轉(zhuǎn)化為標(biāo)準(zhǔn)形式同樣可以得到其對(duì)偶規(guī)劃為： qjxqjxmpibxaxaxapibxaxaxatsxcxcxczjjininiiininiinn,.,2 , 1;,.,2 , 1; 0,.,1;,.,2 , 1;.min221122112211無(wú)無(wú)限限制制 mpiqjcAnqjcAtsbijjjj,.,1; 0,.,2 , 1;,.,1;.max 第第72頁(yè)頁(yè)實(shí)實(shí) 例例例例 2.5.1 寫出下列規(guī)劃的對(duì)偶規(guī)劃寫出下列規(guī)劃的對(duì)偶規(guī)劃 5,.,2 , 1;1226.215min5321432131jxxxxxxxxxtsxxj 其對(duì)偶規(guī)劃為其對(duì)偶規(guī)劃為 0

49、0212605.2max2121212121 ts 00212605.2max2121212121 ts 3 , 2 , 1;1226.215min32132131jxxxxxxxtsxxj 第第73頁(yè)頁(yè)對(duì)對(duì) 偶偶 理理 論論定定理理 2.5.1 若若x和和 分分別別是是原原規(guī)規(guī)劃劃和和對(duì)對(duì)偶偶規(guī)規(guī)劃劃的的可可行行解解，則則 x和和 分分別別是是原原規(guī)規(guī)劃劃和和對(duì)對(duì)偶偶規(guī)規(guī)劃劃的的最最優(yōu)優(yōu)解解的的充充要要條條件件是是bxc 。 定定理理 2.5.2 線線性性規(guī)規(guī)劃劃的的對(duì)對(duì)偶偶規(guī)規(guī)劃劃的的對(duì)對(duì)偶偶規(guī)規(guī)劃劃是是原原始始規(guī)規(guī)劃劃。 定定理理 2.5.3 如如果果一一個(gè)個(gè)線線性性規(guī)規(guī)劃劃有有最最優(yōu)優(yōu)

50、解解，則則其其對(duì)對(duì)偶偶規(guī)規(guī)劃劃也也有有最最優(yōu)優(yōu) 解解，且且它它們們的的最最優(yōu)優(yōu)值值相相等等。 定定理理 2.5.4 給給定定一一個(gè)個(gè)原原規(guī)規(guī)劃劃和和對(duì)對(duì)偶偶規(guī)規(guī)劃劃，則則下下面面三三種種情情況況必必有有其其一一： 1.都都有有最最優(yōu)優(yōu)解解 2.都都無(wú)無(wú)可可行行解解 3.一一個(gè)個(gè)有有可可行行解解另另一一個(gè)個(gè)無(wú)無(wú)界界 定定理理 2.5.5 若若x和和 分分別別是是原原規(guī)規(guī)劃劃和和對(duì)對(duì)偶偶規(guī)規(guī)劃劃的的可可行行解解，則則 x和和 分分別別是是原原規(guī)規(guī)劃劃和和對(duì)對(duì)偶偶規(guī)規(guī)劃劃的的最最優(yōu)優(yōu)解解的的充充要要條條件件是是， mibxaiii,.,2 , 1; 0)( njxAcjj,.,2 , 1; 0)(

51、第第74頁(yè)頁(yè)定定 理理 2.5.1對(duì)對(duì)于于規(guī)規(guī)劃劃( () )的的任任意意可可行行解解x和和規(guī)規(guī)劃劃( () )的的任任意意可可行行解解 ， 由由于于0 x所所以以有有 如如果果bxc 則則顯顯然然x和和 分分別別是是原原規(guī)規(guī)劃劃和和對(duì)對(duì)偶偶規(guī)規(guī)劃劃的的最最 優(yōu)優(yōu)解解。反反之之x是是原原規(guī)規(guī)劃劃的的最最優(yōu)優(yōu)解解，則則存存在在最最優(yōu)優(yōu)基基可可行行解解x， 使使得得 令令1 BcB ，則則有有 所所以以 是是對(duì)對(duì)偶偶規(guī)規(guī)劃劃的的最最優(yōu)優(yōu)解解，所所以以 由由此此可可知知 xcAxb xcxc 0 cA xcb bb bxc 第第75頁(yè)頁(yè)定定 理理 2.5.2 cAtsb .max 0,.min cy

52、AAtsbb )0 ,(),(.maxbbIAAxtscx 0.maxxbAxbAxtsxc 0.maxxbAxbAxtsxc 0.minxbAxtsxc 第第76頁(yè)頁(yè)定定 理理 2.5.5x和和 分別是原規(guī)劃和對(duì)偶規(guī)劃的最優(yōu)解的分別是原規(guī)劃和對(duì)偶規(guī)劃的最優(yōu)解的充要條件充要條件是是bxc . x和和 分別是原規(guī)劃和對(duì)偶規(guī)劃的可行解，則分別是原規(guī)劃和對(duì)偶規(guī)劃的可行解，則 所以所以 xcAxb njxAcjj,.,2 , 1; 0)( bxc mibxaiii,.,2 , 1; 0)( 第第77頁(yè)頁(yè)對(duì)偶單純形算法對(duì)偶單純形算法|基本思想基本思想|算法過(guò)程算法過(guò)程|算例算例第第78頁(yè)頁(yè)基基 本本 思

53、思 想想NB1 I0 N 0 B BxNxbBcB101 bB第第79頁(yè)頁(yè)單單 純純 形形 算算 法法從滿足從滿足01 bB的基解入手，在保持的基解入手，在保持01 bB 的條件下的條件下尋找滿足尋找滿足01 cABcB的基解。的基解。 BxNB1 IN 0 B bBcB1 01 bBNx第第80頁(yè)頁(yè)對(duì)對(duì) 偶偶 單單 純純 形形同樣可以從滿足同樣可以從滿足01 cABcB的基解出發(fā)，在保持的基解出發(fā)，在保持 01 cABcB的條件下尋找滿足的條件下尋找滿足01 bB的基解。的基解。 我們稱滿足我們稱滿足01 cABcB的基解為的基解為正則解正則解。對(duì)偶對(duì)偶 單純形算法單純形算法就是從正則解出發(fā)

54、，從一個(gè)正則解調(diào)就是從正則解出發(fā)，從一個(gè)正則解調(diào) 整到另一個(gè)正則解，直至找到可行的正則解。整到另一個(gè)正則解，直至找到可行的正則解。 NB1I0N0BbBcB1bB1BxNx第第81頁(yè)頁(yè)正正 則則 解解01 cABcB0 cA 1 BcB 正則解正則解對(duì)偶可行解對(duì)偶可行解第第82頁(yè)頁(yè)正則解的單純性表正則解的單純性表nmjjrjrrxabx11xnx2x1mxmx0111mabBcB101m00110nna11mmamna1bmbrx011rmarna0rb第第83頁(yè)頁(yè) nmjjrjrrxabx10:1 rjanjm0 rx規(guī)劃無(wú)可行解規(guī)劃無(wú)可行解;0:100 rjanjm0,/00rrjrjxa

55、bx保持正則性保持正則性第第84頁(yè)頁(yè)00/rjjrjjjaa 0/00 rjjra 0 rja0 j 0 rja00/rjjrjjaa 0/min/ rjrjjrkkaaa kx入基變量入基變量第第85頁(yè)頁(yè)1xnx2x1mxmx0111 mabBcB1 01 m 00110 n na11 mmamna1bmbrx011 rmarna0 rbkx0 k ka1rkamka第第86頁(yè)頁(yè)否否算算 法法 過(guò)過(guò) 程程初始正則解初始正則解檢查可行檢查可行是則停止是則停止得最優(yōu)解得最優(yōu)解選出基變量選出基變量檢查檢查是否無(wú)可是否無(wú)可行解行解是則停止是則停止否否無(wú)最優(yōu)解無(wú)最優(yōu)解選入基變量選入基變量計(jì)算典式檢驗(yàn)數(shù)

56、計(jì)算典式檢驗(yàn)數(shù)第第87頁(yè)頁(yè)算算 例例例例：解下列規(guī)劃解下列規(guī)劃 首先化為標(biāo)準(zhǔn)形式首先化為標(biāo)準(zhǔn)形式 0,2413.min321321321321xxxxxxxxxtsxxx 0,2413.min5432153214321321xxxxxxxxxxxxxtsxxx第第88頁(yè)頁(yè)迭迭 代代1x2x3x4x5x111000311100211411第第89頁(yè)頁(yè)迭迭 代代1x2x3x4x5x1110003111002141141411413043121414504304121第第90頁(yè)頁(yè)迭迭 代代1x2x3x4x5x0214141411413043121414504304121第第91頁(yè)頁(yè)1x2x3x4x5

57、x02141414111013313413213145043041211135139013601320134131133137第第92頁(yè)頁(yè)1x2x3x4x5x101331341321311135139013601320134131133137第第93頁(yè)頁(yè)靈靈 敏敏 度度 分分 析析|概況概況|改變價(jià)值向量改變價(jià)值向量|改變右端向量改變右端向量第第94頁(yè)頁(yè)概概 況況|信息的不確定性信息的不確定性 信息的變化：信息的變化： 價(jià)值向量?jī)r(jià)值向量市場(chǎng)變化市場(chǎng)變化 右端向量右端向量資源變化資源變化 系數(shù)矩陣系數(shù)矩陣技術(shù)進(jìn)步技術(shù)進(jìn)步 認(rèn)知的誤差認(rèn)知的誤差|分析方法分析方法 靜態(tài)分析靜態(tài)分析- 比較靜態(tài)分析比

58、較靜態(tài)分析-動(dòng)態(tài)分析動(dòng)態(tài)分析第第95頁(yè)頁(yè)改變價(jià)值向量改變價(jià)值向量v 一般改變情況一般改變情況 v改變非基變量的價(jià)值向量改變非基變量的價(jià)值向量 v改變基變量的價(jià)值向量改變基變量的價(jià)值向量 v算例算例第第96頁(yè)頁(yè)一一 般般 改改 變變 Bx Nx RHS Z Bx 0 NBcNBc1 bBcB1 I NB1 bB1 當(dāng)價(jià)值向量改變時(shí)在單純形表里后影響的只是檢驗(yàn)數(shù)當(dāng)價(jià)值向量改變時(shí)在單純形表里后影響的只是檢驗(yàn)數(shù) 和目標(biāo)函數(shù)值，其它沒(méi)有改變，因而只需計(jì)算新的檢和目標(biāo)函數(shù)值，其它沒(méi)有改變，因而只需計(jì)算新的檢 驗(yàn)數(shù)和目標(biāo)函數(shù)值驗(yàn)數(shù)和目標(biāo)函數(shù)值 和和 如果檢驗(yàn)數(shù)非正，則原最優(yōu)解依然是最優(yōu)解；否如果檢驗(yàn)數(shù)非正，

59、則原最優(yōu)解依然是最優(yōu)解；否則是則是 基可行解。以此為初始基可行解進(jìn)行迭代就可以求出基可行解。以此為初始基可行解進(jìn)行迭代就可以求出 新問(wèn)題的解。新問(wèn)題的解。 NBNcNBc1 bBcxcB1 第第97頁(yè)頁(yè)非非 基基 變變 量量改改變變非非基基變變量量kx的的價(jià)價(jià)值值向向量量kckc ： kBkcNBc 1 kkkkcc 為為了了使使原原最最優(yōu)優(yōu)解解還還是是最最優(yōu)優(yōu)解解則則要要求求 0 kkkkcc ，即即kkkcc 第第98頁(yè)頁(yè)基基 變變 量量改改變變基基變變量量kx的的價(jià)價(jià)值值向向量量kc kc ，基基變變量量kx 對(duì)對(duì)應(yīng)應(yīng)的的約約束束為為第第l個(gè)個(gè) NkkBcNBccNBc11)0 , 0

60、, 0 , 0( )(1)(lkkTNNBcc lkkBBBbccbcbcbBc)(1 NBNcNBc1 第第99頁(yè)頁(yè)算算 例例例例 2.6.1 問(wèn)題問(wèn)題 的目標(biāo)函數(shù)中變量的目標(biāo)函數(shù)中變量2x的系數(shù)由的系數(shù)由 0 變成變成 1. 5 , 4 , 3 , 2 , 1;1226.215min5321432131jxxxxxxxxxtsxxzj第第100頁(yè)頁(yè)1x 2x 3x 4x 5x -1/2 -11/4 -9/4 31/4 -1/2 1 -1/4 1/4 1 2 1/2 -3/2 1/4 1/2 由由于于2x為為非非基基變變量量，所所以以系系數(shù)數(shù)的的改改變變只只影影響響2x的的檢檢驗(yàn)驗(yàn)數(shù)數(shù)， 新