【正文】 法（五） 基變量 ————“非自由變量”，記號(hào) xB 非基變量 ————“自由變量”，記號(hào) 基 —— 所有基變量下標(biāo)的集合，記號(hào) B 典式 —— 約束等式是基變量由非基變量表示； 目標(biāo)函數(shù)中不含有基變量 單純形表 ——基可行解典式的表格化 ? 檢驗(yàn)數(shù) ? 入基變量 ? 出基變量 ? 轉(zhuǎn)軸點(diǎn) Bx單純型法（六） ?????????????)2,1(08234..52m a x212121jxxxxxtsxxfj解：引進(jìn)松弛變量 x3 , x4 , x5，把線性規(guī)劃問題化為標(biāo)準(zhǔn)形 ??????????????????)51(08234..52m a x521423121?jxxxxxxxxtsxxfj單純型法（七） 基變量 XB=(x3 , x4 , x5)，可以得到對(duì)應(yīng)的單純形表如下： CxB x1 x2 x3 x4 x5 x3 1 0 1 0 0 4 x4 0 1 0 1 0 3 x5 1 2 0 0 1 8 ? 2 5 0 0 0 0 b[1] 單純型法（八） 單純表矩陣計(jì)算公式： X b XB 1?BAA 1?BAb c － CT＋ C BT 1?BAA CBT1?BAb ???????????????32,10112..32m a x3121321jxxxxxxtsxxxfj x1 x2 x3 b x1 1 0 1 1 x2 0 1 2 1 c 0 0 2 3 單純型法（九） 例 ????????????????2,10644..m a x21212121jxxxxxxxtsxxfj解：化成標(biāo)準(zhǔn)形 ???????????????????5,4,3,2,10644..m a x52142132121jxxxxxxxxxxtsxxfj單純型法（十） 例 解：化成標(biāo)準(zhǔn)形 ??????????????2,1010525..2m a x212121jxxxxxtsxxfj????????????????4,3,2,1010525..2m a x42132121jxxxxxxxtsxxsj單純型法（十一） 例 x1 x2 x3 x4 b x3 1 1 1 0 5 x4 2 5 0 1 10 c 2 1 0 0 0 兩階段法（ 1） 例 ??????????????????5, . . . ,2,101226..215m a x5321432131jxxxxxxxxxtsxxfj解：引入人工變量 x6, x7構(gòu)造輔助問題 ?????????????????5, .. .,2,101226.. 7532164321jxxxxxxxxxxxtsj76 xxzmi n ??兩階段法（ 2） 例 bcfcx1 x2 x3 x4 x5 x6 x7 x6 1 1 6 1 0 1 0 2 x7 [1] 1 2 0 1 0 1 1 2 0 8 1 1 0 0 3 5 0 21 0 0 0 0 0 xB x1 x2 x3 x4 x5 x6 x7 x6 0 1/2 1 1/4 1/4 1/4 1/4 1/4 x1 1 2 0 1/2 3/2 1/2 3/2 1/2 0 0 0 0 0 1 1 0 0 1/2 0 11/4 9/4 11/4 9/4 31/4 cfcb對(duì)偶規(guī)劃（ 1） 例 1 . 3 某種作物在全部生成過程中至少需要氮肥 32 公斤，磷肥 24 公斤，鉀肥 42 公斤。問應(yīng)如何配合使用這些肥料，既能滿足作物對(duì)氮，磷，鉀的需要，又使施肥成本最低？ 表 1 . 5 含量 肥料 成分 甲 乙 丙 丁 氮磷鉀肥的需要量（公斤） 氮 0. 03 0. 03 0 0. 15 32 磷 0. 05 0 0. 2 0. 1 24 鉀 0. 14 0 0 0. 07 42 價(jià)格 元 /公斤 0. 04 0. 15 0. 1 0. 13 對(duì)偶規(guī)劃（ 2） 設(shè)： x1, x2, x3, x4,分別表示甲，乙，丙，丁四種復(fù)合肥的用量 分析： ( 1 ) 表示購買的四種復(fù)合肥中含氮量不能小于作物對(duì)氮的需求量； ( 2 ) 表示購買的四種復(fù)合肥中含磷量不能小于作物對(duì)磷的需求量； ( 3 ) 表示購買的四種復(fù)合肥中含鉀量不能小于作物對(duì)鉀的需求量； ( 4 ) 表示購買的四種復(fù)合肥的量非負(fù) ??????????????????)4(4,3,2`,0)3()2()1(.. i n414314214321????????jxxxxxxxxxtsxxxxfj對(duì)偶規(guī)劃（ 3） ???????????????3,2,1012526..52415m i n32132321jxxxxxxtsxxxfj????????????????0052426155..2m a x212121221yyyyyyytsyyg???????????????????4,3,2,101023421085..4335m i n432143214321jxxxxxxxxxtsxxxxfj ???????????????????????????無限制43214321432143214321,0,32417281473672..4765m i nxxxxxxxxxxxxxxxxtsxxxxf對(duì)偶規(guī)劃（ 4） 原問題 對(duì)偶問題 有最優(yōu)解 解無界 無可行解 有最優(yōu)解 √ － － 解無界 － － √ 無可行解 － √ √ 對(duì)偶單純形法（ 1） ????????????????0226343322121212121x,xxxxxxx.xxfm i n 解：引進(jìn)松弛變量，化成標(biāo)準(zhǔn)型 ???????????????????????5102263433252142132121,. .. ,i,xxxxxxxxxx.xxffm a xi39。 x B x 1 x 2 x 3 x 4 x 5 b x 3 5/ 3 0 1 1 / 3 0 1 x 2 4 /3 1 0 1 /3 0 2 x 5 5 / 3 0 0 2 / 3 1 2 C 2 /3 0 0 1 / 3 0 2 x B x 1 x 2 x 3 x 4 x 5 b x 3 3 1 1 0 0 3 x 4 4 3 0 1 0 6 x 5 1 2 0 0 1 2 C 2 1 0 0 0 0 x B x 1 x 2 x 3 x 4 x 5 b x 1 1 0 3 / 5 1/ 5 0 3 / 5 x 2 0 1 4 / 5 3 / 5 0 6 / 5 x 5 0 0 1 1 1 1 C 0 0 2 / 5 1/ 5 0 1 2 /5 影子價(jià)格（ 1） 定義 1 . 9 ：設(shè) x* 是原問題 的 最優(yōu)解，則 x* 的對(duì)偶解 y* 又稱為影子價(jià)格。 因?yàn)槿?f* 為上述線性規(guī)劃的最優(yōu)目標(biāo)函數(shù)值，則 f * = C BTAB 1b = ( y *) b ，**iiybf??? 它表示在第 i 種資源數(shù)量 b i 附近的某個(gè)閉區(qū)間內(nèi)，該種資源數(shù)量增加一個(gè)單位（此時(shí)其他資源數(shù)量不變），生產(chǎn)計(jì)劃的最大利潤 f* 將增加 y i * 個(gè)單位。 資源的市場價(jià)格是已知數(shù)，相對(duì)比較穩(wěn)定，而它的影子價(jià)格則有賴于資源的利用情況，是未知數(shù)。 （三）資源的影子價(jià)格實(shí)際上又是一種機(jī)會(huì)成本。所以影子價(jià)格對(duì)市場有調(diào)節(jié)作用。 表 5 產(chǎn)品 單位消耗 資源 I I I 現(xiàn)有資源 鋼 材（噸） 1 2 100 （噸） 煤（噸） 2 2 180 （噸） 機(jī)械加工時(shí)間（小時(shí)） 1 6 240 （小時(shí)） 利 潤（萬元） 1 3 設(shè)： x 1 ， x 2 表示產(chǎn)品 I 和 I I 的計(jì)劃產(chǎn)量。 ?????????????????????3,2,10..81512m a x321321321321jxxxxxxxxxxtsxxxfj且為整數(shù) 靈敏度分析（ 3） x B x 1 x 2 x 3 x 4 x 5 x 6 b x 4 0 0 1/ 5 1 2 0 1200 x 2 5/ 6 1 1 0 5/ 3 0 3000 x 6 7/ 60 0 1/ 10 0 7/ 6 1 300 c 1/ 2 0 7 0 25 0 45000 目標(biāo)規(guī)劃（ 1） 例 某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，這些產(chǎn)品分別要在 A 、 B 、 C 、 D 四種不同的設(shè)備上工。問如何安排生產(chǎn)，使獲得的總利潤最大？ 單位產(chǎn)品 占用設(shè)備臺(tái)時(shí) 產(chǎn)品甲