【正文】 般表達(dá)式可寫成 1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 2m a x( m in)( , )( , )( , )0 , 1 , 2 , ,nnnnnnm m m n n mjZ c x c x c xa x a x a x ba x a x a x ba x a x a x bx j n? ? ? ?? ? ? ? ? ???? ? ? ? ? ?????? ? ? ? ? ??????或或或為了書寫方便，上式也可寫成： 線性規(guī)劃的數(shù)學(xué)模型 11m a x( m i n)( , ) 1 , 2 , ,0 , 1 , 2 , ,njjjnij j ijjZ c xa x b i mx j n????? ? ? ???? ????? 或在實(shí)際中一般 xj≥0,但有時 xj≤0或 xj無符號限制 。 怎樣辨別一個模型是線性規(guī)劃模型？ 圖解法的步驟： 。 一般地，將目標(biāo)函數(shù)直線放在可行域中，求最大值時直線沿著矢量方向移動，求最小值時沿著矢量的反方向移動。 例 27. 某工廠在計劃期內(nèi)要安排 Ⅰ 、 Ⅱ 兩種產(chǎn)品的生產(chǎn) ， 已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及 A、 B兩種原材料的消耗 、 資源的限制 ， 如下表： 問題：工廠應(yīng)分別生產(chǎn)多少單位 Ⅰ 、 Ⅱ 產(chǎn)品才能使工廠獲利最多？ Ⅰ Ⅱ 資源限制 設(shè)備 1 1 300 臺時 原料 A 2 1 400 千克 原料 B 0 1 250 千克 單位產(chǎn)品獲利 50 元 100 元 線性規(guī)劃模型： 目標(biāo)函數(shù)： Max z = 50 x1 + 100 x2 約束條件： . x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0 圖解法： A， B， C， D， E是可行域的頂點(diǎn)，最優(yōu)解為B(50, 250) x1 x2 z=27500=50x1+100x2 C B A D E 當(dāng)一個系數(shù)發(fā)生變化時，其他系數(shù)保持不變 1)目標(biāo)函數(shù)中的系數(shù) ci 的靈敏度分析 考慮例 27的情況 ， ci 的變化只影響目標(biāo)函數(shù)等值線的斜率 ， 目標(biāo)函數(shù) z = 50 x1 + 100 x2 在 z = x2 (斜率為 0 ) 到 z = x1 + x2 (斜率為 1 )之間時 ， 原最優(yōu)解 x1 = 50， x2 = 250 仍是最優(yōu)解 。 增加的利潤： (50 60+ 100 250) (50 50+100 250) = 500元 ， 單位臺時增加的利潤為： 500 / 10 = 50 元 。 解釋： 原最優(yōu)解沒有把原料 A 用盡 ， 有 50千克的剩余 ，因此增加 10千克值增加了庫存 ， 而不會增加利潤 。 在使用百分之一百法則進(jìn)行靈敏度分析時 ， 要注意： 1） 當(dāng)允許增加量 （ 允許減少量 ） 為無窮大時 ， 則對任意增加量 （ 減少量 ） ， 其允許增加 （ 減少 ） 百分比均看作 0； 2） 百分之一百法則是充分條件 ， 但非必要條件；也就是說超過 100%并不一定變化； 3） 百分之一百法則不能用于目標(biāo)函數(shù)決策變量系數(shù)和約束條件右邊常數(shù)值同時變化的情況 。 ? 目標(biāo)為 max時，影子價格 =對偶價格 ? 目標(biāo)為 min時，影子價格 =對偶價格 作業(yè) ? 閱讀教材第四章 ? 教材第二章習(xí)題 6 ? 教材第三章習(xí)題 2 線性規(guī)劃問題的標(biāo)準(zhǔn)型為 : 1．目標(biāo)函數(shù)求最大值 2．約束條件都為等式方程 3．決策變量 xj非負(fù) 4．約束條件右邊常數(shù) bi非負(fù) 單純形法 在用單純法求解線性規(guī)劃問題時，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。 b. 當(dāng)某一個決策變量 xj沒有符號限制時，可以令 xj = xj’ xj” 其中 xj’≥0， xj”≥0 即用兩個非負(fù)變量之差來表示一個無符號限制的變量，當(dāng)然 xj的符號取決于 xj’和 xj”的大小。=x－ a，則 a≤x≤b等價于 0≤ x39。 【 例 28】 將下列線性規(guī)劃化為標(biāo)準(zhǔn)型 321 3m in xxxZ ????????????????????????無符號要求、32132132132100)3(523)2(3)1(82xxxxxxxxxxxx【 解 】 : (1)目標(biāo)函數(shù)為 min，令 Z’=Z； (2)因為 x3無符號要求 ，即 x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令 0, 33333 ????????? xxxxx 其中 (4)第二個約束條件是 ≥號，在 ≥號 左端減去剩余變量 (Surplus variable)x5， x5≥0。 通過以上變換 ， 可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題： Max z = 2x1 + 3 x2 4x3 . 3x1+4x25x3 +x4 = 6 2x1 +x3 x5 = 8 x1 x2 x3 = 9 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0 【 例 210】 將下例線性規(guī)劃化為標(biāo)準(zhǔn)型 ???????????無約束、 211212145||||m a xxxxxxxxZ【 解 】 此題關(guān)鍵是將目標(biāo)函數(shù)中的絕對值去掉。 【 解 】 約束方程的系數(shù)矩陣為 2 5矩陣 ?????????10261001115A,610 151 ????????B ,010 152 ????????B ,110 053 ????????B ?????? ??26114B???????10019B,12017 ????????B ,02118 ????????B,16016 ???????B,06 115 ???????B容易看出 r(A)=2， 2階子矩陣有 C52=10個，其中第 1列與第 3列構(gòu)成的 2階矩陣不是一個基，基矩陣只有 9個，即 由線性代數(shù)知，基矩陣 B必為非奇異矩陣并且 |B|≠0。 基變量 、 非基變量是針對某一確定基而言的 ， 不同的基對應(yīng)的基變量和非基變量也不同 。 TX )1,27,21,0,0(? 基本解 (basis solution) 對某一確定