【正文】 若某個約束條件右端常數(shù)的為負(fù)值，只需在該約束條件兩端同乘以（ 1）即可。 線性規(guī)劃問題的標(biāo)準(zhǔn)型 山東理工大學(xué)管理學(xué)院 解： ① 令 f 39。= x1 –2x2 +3x4 –3x5 x1 +x2 +x4 x5 +x6 =7 x1 x2 +x4 x5 x7 =2 x1 , x2 , x4 , … , x7 ?0 167。 線性規(guī)劃問題的標(biāo)準(zhǔn)型 山東理工大學(xué)管理學(xué)院 max f=CX AX =b X?0 167。 A= (P1 … Pm Pm+1 … Pn )=(B N) 基向量 非基向量 … X= (x1 … xm xm+1 … xn )T=(XB XN)T 基變量 非基變量 XB XN … 1. LP問題解的概念 也就是說，基矩陣 B是由 A的 m個線性無關(guān)的列向量組成。 定義 3 基本可行解 ——滿足非負(fù)約束條件的基本解， 稱為基本可行解。 ※ 基本解中非零分量的數(shù)目，不大于方程的個數(shù) m。 n! m!(nm)! 1. LP問題解的概念 bB 1?????????? ?01 bBX山東理工大學(xué)管理學(xué)院 例 1 x1+2x2 +x3 =30 3x1+2x2 +x4 =60 2x2 +x5 =24 x1 … x 5 ?0 1 2 1 0 0 3 2 0 1 0 0 2 0 0 1 P1 P2 P3 P4 P5 A= 1. LP問題解的概念 山東理工大學(xué)管理學(xué)院 x1 + 2 x 2 +x 3 = 30 3x 1 +2x 2 +x 4 = 60 2x 2 +x 5 =24 x 1 … x 5 ? 0 B=(P3 P4 P5)=I 顯然 B可逆， 為一基矩陣 x3=30( x1+2 x2) x4=60(3x1+2 x2) x5 =24 2 x2 令 x1 = x2 =0, 解得： x3=30, x4=60, x5=24 1. LP問題解的概念 TX )24603000(?則 稱為對應(yīng)于基矩陣 B的基本解。 山東理工大學(xué)管理學(xué)院 62 約束方程的 解空間 線性規(guī)劃問題解的概念之間的關(guān)系 基本解 可行解 非可行解 基本 可行解 最優(yōu)解 山東理工大學(xué)管理學(xué)院 2. LP問題解的性質(zhì) ?若 LP問題有可行解，則可行解集 (可行域 )是凸集 (可能有界，也可能無界 )，有有限個頂點。 ?若 LP問題有最優(yōu)解，則一定可以在基本可行解中找到。 山東理工大學(xué)管理學(xué)院 66 2. 單純型表及其格式 山東理工大學(xué)管理學(xué)院 67 ? 對于 (max , ?)，松弛變量對應(yīng)的列構(gòu)成一個單位陣 ? 所有檢驗數(shù) λj ? 0，則為最優(yōu)解，否則進(jìn)行下一步。 山東理工大學(xué)管理學(xué)院 max f =40x1+ 50x2 x1+2x2 ? 30 3x1+2x2 ? 60 2x2 ? 24 x1 , x2 ?0 例 1 用單純形法求解下列 LP問題 山東理工大學(xué)管理學(xué)院 x1 +2x2 +x3 =30 3x1 +2x2 +x4 =60 2x2 + +x5 =24 x1 , …, x5 ?0 max f =40x1+ 50x2+0x4+0 問應(yīng)如何安排生產(chǎn)計劃才能使利潤最大 ？ 4 5 利潤（元 /件） 45 1 1 丙 80 1 2 乙 90 3 1 甲 有效臺時 B A 設(shè)備 產(chǎn)品 山東理工大學(xué)管理學(xué)院 ??????????????0,45802903.21212121xxxxxxxxts21 45m a x xxf ??該問題的數(shù)學(xué)模型 設(shè) A、 B兩種產(chǎn)品的產(chǎn)量分別為 x1, x2 ,則這個問題可以歸結(jié)為求解下列線性規(guī)劃問題： 山東理工大學(xué)管理學(xué)院 設(shè) y1, y2, y3分別表示設(shè)備甲、乙、丙每臺時的加工費（或租金） ,則 ????????????0,4352.321321321yyyyyyyyytsm i n g y y y? ? ?90 80 451 2 3 如果工廠準(zhǔn)備將設(shè)備進(jìn)行出租，請為該廠的決策者進(jìn)行決策。已知甲、乙、丙、丁四種復(fù)合肥料每公斤的價格以及氮磷鉀的含量，如下表所示： 甲 乙 丙 丁 肥料需要量 / 公斤 氮 0 32 磷 0 24 鉀 0 0 42 每公斤價格 / 元 問：應(yīng)如何選購這些肥料，即能滿足作物對氮磷鉀的需要，又使施肥成本最低？ 山東理工大學(xué)管理學(xué)院 設(shè)用 1x ， 2x ， 3x ， 4x 分別表示甲乙丙丁四種肥料的用量，則該問題的數(shù)學(xué)模型為： 4321 i n xxxxf ???? s .t . 0,432141431421?????????xxxxxxxxxxxx 山東理工大學(xué)管理學(xué)院 現(xiàn)從另外一個角度考慮：有一化肥公司生產(chǎn)氮、磷、鉀三種單成分化肥，現(xiàn)要為這三種化肥定價，既要獲利最大，又要和生產(chǎn)甲乙丙丁四種復(fù)合肥料公司競爭，因此以這些單成分化肥的價格、施肥滿足作物需要時，要求利潤最大。 y1 y2 max f = 5x1 +6x2 3x1 –2x2 ? 7 3x1 +2x2 ? 7 4x1 +x2 ? 9 x1 , x2 ?0 山東理工大學(xué)管理學(xué)院 對偶問題 3y139。 +2y1 +y2 ? 6 y139。 7y1 +9y2 令 y1 = y139。 X* 和 Y* 分別為原問題和對偶問題的可行解，且可行解對應(yīng)的原問題和對偶問題的目標(biāo)函數(shù)值相等，即 CX* = Y*b ，則 X* 和 Y*分別為原問題和對偶問題的最優(yōu)解。 該性質(zhì)說明，原問題和對偶問題之一無最優(yōu)解，則另一個也無最優(yōu)解。 山東理工大學(xué)管理學(xué)院 XB = B1b， 則對偶問題的最優(yōu)解為 Y=CBB1. ，則他們必都有最優(yōu)解。 ??????????????0,45802903.21212121xxxxxxxxts21 45m a x xxf ??????????????0,4352.321321321yyyyyyyyytsm i n g y y y? ? ?90 80 451 2 3例 原問題 對偶問題 山東理工大學(xué)管理學(xué)院 xj x1 x2 x3 x4 x5 B1b x3 x1 x2 0 0 1 2 5 1 0 0 1 1 0 1 0 1 2 25 35 10 f 0 0 0 1 3 215 xj x1 x2 x3 x4 x5 b x3 x4 x5 1 2 1 0 0 2 1 0 1 0 1 1 0 0 1 90 80 45 f 5 4 0 0 0 0 初始單純形表 最優(yōu)單純形表 原問題 山東理工大學(xué)管理學(xué)院 y1 y2 y3 y4 y5 B1b y2 y3 2 1 0 1 1 5 0 1 1 2 1 3 g’ 25 0 0 35 10 215 對偶問題最優(yōu)單純形表： 綜上所述，一對對偶問題的解必然是下列三種情況之一： ，且最優(yōu)目標(biāo)函數(shù)值相等。 ，則另一個問題無可行解。 山東理工大學(xué)管理學(xué)院 三、對偶解的經(jīng)濟(jì)涵義 —— 影子價格 通過求解：原問題和對偶問題的最優(yōu)解分別為 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 , , 4 3 5 2 0 , 45 80 2 90 3 45 80 90 min 4 5 max 3 2 1 3 2 1 3 2 1 2 1 2 1 2 1 2 1 3 2 1 2 1 y y y y y y y y y x x x x x x x x y y y g x x f 215 min , ) 3 , 1 , 0 ( ) , , ( 215 max , ) 25 , 10 , 35 ( ) , , ( 3 2 1 3 2 1 ? ? ? ? ? ? g y y y y f x x x x T T 山東理工大學(xué)管理學(xué)院 對偶問題是資源定價問題，對偶問題的最優(yōu)解 y y ...、ym稱為 m種資源的 影子價格（ Shadow Price）。 由對偶定理可知 ， 當(dāng)達(dá)到最優(yōu)解時，原問題與對偶問題的目標(biāo)函數(shù)值相等，即有 f *=CX*=Y*b=y1* b1+ y2* b2+…+ ym* bm 現(xiàn)考慮在最優(yōu)解處，右端項 bi的微小變動對目標(biāo)函數(shù)值的影響，由上式，將 f *對 bi求偏導(dǎo)數(shù)： ),...,2,1(**miybf ii???? 該式表明了，若原問題的某一個約束條件的右端項 bi每增加一個單位，則由此引起的最優(yōu)目標(biāo)函數(shù)值的增加量，就等于與該約束條件相對應(yīng)的對偶變量的最優(yōu)解的值。 ，并解釋其經(jīng)濟(jì)意義。 ② 影子價格可以告訴管理人員，花多大的代價增加資源才是合算的。 ④ 影子價格在資源購銷決策中的應(yīng)用。通過這項工作，他的總收入將有所提高，該教授掌握了咨詢補(bǔ)償?shù)幕疽?guī)律： “ 一個專家的價值正比于廠商和專家之間的距離 ” 。遺憾的是，旅行時間也將增加。每小時咨詢工作所要求的旅行時間對于企業(yè) A、 B、 C來說分別為 、 、 。據(jù)此，我們可以很快建立該問題的線性規(guī)劃模型。 對偶問題的模型為： 山東理工大學(xué)管理學(xué)院 思路： 單純形法：找基 B，滿足 右端常數(shù)非負(fù) ， 但檢驗數(shù) 不全 ? 0。 對偶單純形法：找基 B，滿足 檢驗數(shù) ? 0， 但 右端常數(shù)不全 ?0。 四、對偶單純形法 山東理工大學(xué)管理學(xué)院 例 1： max f =2x1 +x2 x1+ x2 + x3 = 5 2x2 + x3 ? 5 4x2 +6x3 ? 9 x1 , x2 , x3 ?0 max f =2x1 +x2 x1+ x2 + x3 = 5 2x2 + x3 +x4 = 5 4x2 –6x3 +x5 =9 x1 … x5 ?0 山東理工大學(xué)管理學(xué)院 xj x1 x2 x3 x4 x5 B1b