【正文】 性規(guī)劃問題可能有各種不同的形式。為了便于今后討論，我們規(guī)定線性規(guī)劃問題的標準型為： 1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 212m a x( ), , , 0nnnnnnm m m n n mnZ c x c x c xa x a x a x ba x a x a x ba x a x a x bx x x? ? ? ?? ? ? ???? ? ? ?????? ? ? ?????清華大學出版社 標準型具有如下特點： （ 1）目標函數(shù)求最大值； （ 2）所求的變量都要求是非負的； （ 3）所有的約束條件都是等式； （ 4）常數(shù)項非負。 3. 基 : 假設 A 是約束方程組的系數(shù)矩陣，其秩數(shù)為 m ， B是矩陣 A 中由 m 列構(gòu)成的非奇異子矩陣 (B的行列式的值不為 0)，則稱 B 是線性規(guī)劃問題的一個基。,m )稱為基向量，與基向量 Pj 相對應的變量 xj ( j = 1,2, T 清華大學出版社 為了進一步討論線性規(guī)劃問題的解，下面研究約束方程組 ()的求解問題。 ,xm,0, 11 1 1 1 1111111: ( )m m nm m nm m m m m m nmnj j j jj j ma a a ax x b x xa a a aP x b P x???? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?????或T 清華大學出版社 4. 基本可行解 : 滿足非負條件 ()的基本解稱為基本可行解。一般地講，基本可行解的數(shù)目要小于基本解的數(shù)目，至多相等。沿箭頭方向移動目標函數(shù)的等值線，平移等值線直至與可行域 OABCD相切或融合為一條直線，此時就得到最優(yōu)解為 B點，其坐標可通過解方程組得到： 2x1+2x2=14 3x2=15 解得： x1=2 x2=5 這就是本線性規(guī)劃問題的最優(yōu)解。 （ 4）若可行域無界，則可能發(fā)生最優(yōu)解無界的情況； （ 5）若可行域是空集，此時無最優(yōu)解。 清華大學出版社 三、基本定理 1. 凸集：假設 K是 n維歐氏空間的一個點集，若對于 K中的任意兩點 X X2，其連線上的所有點 ?X1+(1?)X2， ( 0 ? ? ? 1)都在集合 K中，即： ?X1+(1?)X2 ?K ( 0 ? ? ? 1) 則稱K為凸集。 ?k，且 0 ? ?i ? 1， i = 1,2, 清華大學出版社 定理 若線性規(guī)劃問題存在可行域，則其可行域： D = { X | AX = b , X ? 0 } ，是凸集。 定理 若線性規(guī)劃問題在 k個頂點上達到最優(yōu)解 （ k?2），則在這些頂點的凸組合上也達到最優(yōu)解。, bm, 0, 12 0m m nx x x??? ? ? ?T 清華大學出版社 2．最優(yōu)性檢驗 假定已求得 (LP)的一個基本可行解 X(0) ，假設： 目標函數(shù)用非基變量表示的形式。 定理 無有限最優(yōu)解判別定理： 若 為對應于基 B 的基本可行解，有一個 ，而對于 有 ，則線性規(guī)劃問題無有限最優(yōu)解 (也稱為無最優(yōu)解 )。這就是說，要使原基本可行解的某一個正分量 xj變?yōu)?0，同時保持其余分量均非負。 m in { | 0 }ili j lii j i lbbaaa???? ? ? ?清華大學出版社 例 1－ 8 利用單純形算法求解例 1－ 1的線性規(guī)劃問題。x5 3x2+x3=15 4x1+x4=12 2x1+2x2＋ x5=14 x1， x2， x3， x4， x5≥0 解： （ 1）由標準型得到初始單純形表： cj 2 3 0 0 0 θi XB b x1 x2 x3 x4 x5 x3 15 0 [3] 1 0 0 5 x4 12 4 0 0 1 0 x5 14 2 2 0 0 1 7 Z 0 2 3 0 0 0 清華大學出版社 (2) max{?1, ?2}=3=?2，所以 x2為換入變量。這時分別給每一個約束條件加入一個人工變量 xn+1, …, xn+m , 得 : 由此可以得到一個 m階單位矩陣。 清華大學出版社 二、人工變量法 (大 M法 ) 對于加入人工變量的線性規(guī)劃問題的目標函數(shù)如何處理？我們希望人工變量對目標函數(shù)取值不受影響。這就是大 M法。利用表 1—15得初始單純形表，單純形算法得表 1—16 ～表 1—19。第一階段是先求出基本可行解 (或判斷出原線性規(guī)劃問題無解 )，第二階段利用已求出的初始基本可行解來求最優(yōu)解。 2) 若 (LP)*的最優(yōu)基本可行解 則 (LP) 必不可行。 各階段的計算方法及步驟與前述單純形法完全相同，下面用例子說明該方法的應用。 表 1—23 cj 0 0 0 0 0 1 1 θ XB b x1 x2 x3 x4 x5 x6 x7 x4 12 3 0 0 1 2 2 5 x2 1 0 1 0 0 1 1 2 x3 1 2 0 1 0 0 0 1 W39。因人工變量 x6 = x7 = 0，所以 ( 0, 1, 1 ,12, 0 )T 是原問題的基本可行解。盡可能多地掌握一些典型模型不僅有助于深刻理解線性規(guī)劃本身的理論，而且有利于靈活地處理千差萬別的問題，提高解決實際問題的能力。已知產(chǎn)品的規(guī)格要求、產(chǎn)品單價、每天能供應的原材料數(shù)量及原材料單價分別見表 12表 129。 ， x9 ? 0 清華大學出版社 第六節(jié) 線性規(guī)劃的對偶理論與靈敏度分析 一、對偶問題的提出 對偶理論是線性規(guī)劃問題的最重要的內(nèi)容之一。假設有客戶提出要求，租賃工廠的工時和購買工廠的材料，為其加工生產(chǎn)別的產(chǎn)品，由客戶支付工時費和材料費，此時工廠應考慮如何為每種資源定價，同樣使其獲得的利潤最大？ 分析問題： 每種資源定價不能低于自己生產(chǎn)時的可獲利潤； 定價又不能太高，要使對方能夠接受。其中一個是另一個問題的對偶問題。 （ 3）（無界性）若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。 從上述性質(zhì)中，可看到原問題與對偶問題的解必然是下列三種情況之一： ①原問題與對偶問題都有最優(yōu)解，且 CX=Yb； ②一個問題具有無界解，則它的對偶問題無可行解； ③兩個問題均無可行解。 ????????????????????0,32 235 95243m i n5154321543254321xxxxxxxxxxxxxxxxZ?清華大學出版社 解：對偶問題為 ????????????????????????0,)5( 923 )4( 5 5)3( 2 )2( 4 )1( 3 32m a x2121212121221yyyyyyyyyyyyyW可求得對偶問題的最優(yōu)解： Y*=（ 1， 3）， W=11。 清華大學出版社 三、對偶問題的經(jīng)濟解釋 ——影子價格 影子價格 在一對 LP和 DP中，若 LP的某個約束條件的右端項常數(shù) bi增加一個單位時，所引起的目標函數(shù)最優(yōu)值 Z*的改變量稱為第 i個約束條件的影子價格，又稱為邊際價格。 影子價格是在最優(yōu)決策下對資源的一種估價，沒有最優(yōu)決策就沒有影子價格，所以影子價格又稱“最優(yōu)計劃價格”，“預測價格”等等。 （ 2）對市場資源的最優(yōu)配置起著推進作用 即在配置資源時，對于影子價格大的企業(yè)，資源優(yōu)先供給 （ 3）可以預測產(chǎn)品的價格 產(chǎn)品的機會成本為 CBB1AC，只有當產(chǎn)品價格定在機會成本之上，企業(yè)才有利可圖。 ② 直接用影子價格與市場價格相比較，進行決策，是否買入該資源。若存在 ，計算 ),2,1( nja lj ??0?lja 0?ljalkkkljljjji azcaazc ???????????? ??? 0m i n?清華大學出版社 按 Θ規(guī)則，所對應的列變量的非基變量為換入變量； （ 4）以 為主元素，按單純形法進行換基迭代，得到新的單純形表； 重復（ 1）－（ 4）的步驟進行計算。 清華大學出版社 五、靈敏度分析 在前面的線性規(guī)劃問題討論中，都是假定為常數(shù)，但實際工作中這些系數(shù)往往是估計值和預測值。 下面分別就各個參數(shù)改變后的情形進行討論。 表 1－ 42 5 8 6 0 0 XB b x1 x2 x3 x4 x5 0 x4 12 1 1 1 1 0 0 x5 20 1 2 2 0 1 0 5 8 6 0 0 清華大學出版社 經(jīng)過計算得最優(yōu)表如表 1－ 43。 在例 1－ 25中，如果改變 ，使 時，原最優(yōu)方案不發(fā)生改變。 清華大學出版社 （ 2）、基變量的價值系數(shù) 的靈敏度分析 ①如果 的改變，使全部檢驗數(shù) 仍小于零時，這時對最優(yōu)解方案沒有影響，但對最優(yōu)值發(fā)生改變。這時原方案已不是最優(yōu)方案。 是一個不等式組，從中可以解得 b的變化范圍，若 B1b中有小于 0的分量，則需用對偶單純形法迭代，以求出新的最優(yōu)方案。 （ 1）、產(chǎn)品 D的利潤為多少時，投產(chǎn)產(chǎn)品 D有利？ 只有 時， 才能進入基，也就是說產(chǎn)品 D才能生產(chǎn)，這時解得 。 在電力約束條件中加入松弛變量得 2x1+x2+3x3＋ x6＝ 13 以 x6為基變量，將上式反映到最終單純形表中得到表 1－ 53 1316824 ????清華大學出版社 表 1－ 53 5 8 6 0 0 0 XB b x1 x2 x3 x4 x5 x6 5 x1 4 1 0 0 2 1 0 8 x2 8 0 1 1 1 1 0 0 x6 13 2 1 3 0 0 1 84 0 0 2 2 3 0 在表 1－ 53中， x x x6為基變量，因此所對應的列向量應為單位向量，因此經(jīng)計算得表 1－ 54。 ija jx 1?BjP基變量的工藝發(fā)生改變 當 是基變量 的系數(shù)時，它的變化會使發(fā)生改變 ，所以最終單純形表 也要發(fā)生變化，若在例 1－ 25中，生產(chǎn)產(chǎn)品 A的工藝發(fā)生改變，生產(chǎn)產(chǎn)品 A對甲、乙原材料的需求分別為 2， 2。目標值為 82。 01266166 ????? ? cPBCc B? 6x126 ?c 126 ?c清華大學出版社 添加新約束的靈敏度分析 在例 1－ 25中，假設電力供應緊張，若電力供應最多為 13單位，而生產(chǎn)產(chǎn)品 A、 B、 C每單位需電力分別為 3個單位，問該公司生產(chǎn)方案是否需要改變？ 解：先將原問題的最優(yōu)解 x1＝ 4， x2＝ 8， x3＝ 0代入電力約束條件 2x1+x2+3x3?13。 問：投產(chǎn)產(chǎn)品 D是否有利？ 0212102311 12)8,5(106166 ??????????????????????? ? PBCcB?因此最優(yōu)方案不變。 清華大學出版社 資源約束數(shù)量 b的靈敏度分析 從矩陣形