【正文】 ? 所有檢驗(yàn)數(shù) λj ? 0，則為最優(yōu)解，否則進(jìn)行下一步。 （改進(jìn)基可行解） ? 從 λj 0 中找最大者，其對(duì)應(yīng)變量 xk稱為 換入變量 ， ? xk所在 列稱為主元列 ? 確定換入變量的最大值和換出變量 ? 最小比值原則 0m in ?????? ??ikikiiaab?山東理工大學(xué)管理學(xué)院 68 ? 設(shè)第 l 行使 ? 最小，則第 l 行對(duì)應(yīng)的基變量 x l稱為 換出變量 ，第 l 行稱為主元行 迭代過程 ? 主元行 l 行與 主 元 列 k 列相交的元素 alk 稱為主元，迭代以主元為中心進(jìn)行 ? 迭代的實(shí)質(zhì)是線性變換，即要將主元 alk變?yōu)?1， 主列 上其它元素變?yōu)?0。 山東理工大學(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+0x3 +0x4+0x5 標(biāo)準(zhǔn)化 山東理工大學(xué)管理學(xué)院 建立初始單純形表 xj x1 x2 x3 x4 x5 b x3 1 2 1 0 0 30 x4 3 2 0 1 0 60 x5 0 2 0 0 1 24 40 50 0 0 0 0 基變量 * 30/2=15 60/2=30 24/2=12 λj 山東理工大學(xué)管理學(xué)院 第一步迭代 xj x1 x2 x3 x4 x5 b x3 1 0 1 0 1 6 x4 3 0 0 1 1 36 x2 0 1 0 0 12 40 0 0 0 25 600 基變量 6/1=6 36/3=12 __ λj 山東理工大學(xué)管理學(xué)院 第二步迭代 xj x1 x2 x3 x4 x5 b x1 1 0 1 0 1 6 x4 0 0 3 1 2 18 x2 0 1 0 0 12 0 0 40 0 15 840 基變量 18/2=9 12/=24 __ λj 山東理工大學(xué)管理學(xué)院 第三步迭代 xj x1 x2 x3 x4 x5 b x1 1 0 0 15 x5 0 0 1 9 x2 0 1 0 0 0 0 975 基變量 該問題的最優(yōu)解為： X*=(15, , 0, 0, 9)T, f * = 975 λj 山東理工大學(xué)管理學(xué)院 例 2 用單純形法求解下列 LP問題 ??????????????????0,33242m a x2121212121xxxxxxxxxxf?????????????????????0,33242m a x5432152142132121xxxxxxxxxxxxxxxxf山東理工大學(xué)管理學(xué)院 xj x1 x2 x3 x4 x5 b x3 2 1 1 0 0 4 x4 1 1 0 1 0 2 x5 3 1 0 0 1 3 1 1 0 0 0 0 基變量 0 1 2 8 9 3 2 0 0 2 1 21 該問題具有無(wú)界解 λj 山東理工大學(xué)管理學(xué)院 用單純形法求解下列 LP問題 ??????????????0,10251553410m a x21212121xxxxxxxxf????????????????0,10251553410m a x432142132121xxxxxxxxxxxxf課堂練習(xí) 山東理工大學(xué)管理學(xué)院 xj x1 x2 x3 x4 b x3 3 5 1 0 15 x4 5 2 0 1 10 10 4 0 0 0 基變量 15/3=5 λj * 10/5=2 山東理工大學(xué)管理學(xué)院 xj x1 x2 x3 x4 b x3 0 19/5 1 3/5 9 x1 1 2/5 0 1/5 2 0 0 0 2 20 基變量 45/19 λj * 5 最優(yōu)解為 X*=( 2, 0, 9, 0 )T max f = 20 山東理工大學(xué)管理學(xué)院 xj x1 x2 x3 x4 b x2 0 1 5/19 3/19 45/19 x1 1 0 2/19 5/19 20/19 0 0 0 2 20 基變量 λj 最優(yōu)解為 X*=( 20/19, 45/19, 0, 0 )T max f = 20 山東理工大學(xué)管理學(xué)院 線性規(guī)劃問題的對(duì)偶理論 ? 線性規(guī)劃的對(duì)偶問題 ? 對(duì)偶問題的基本性質(zhì) ? 對(duì)偶問題的經(jīng)濟(jì)意義 ? 對(duì)偶單純形法 ? 小結(jié) ? 作業(yè) 山東理工大學(xué)管理學(xué)院 線性規(guī)劃的對(duì)偶問題 一、原問題與對(duì)偶問題 例 某廠在計(jì)劃期內(nèi)要安排生產(chǎn) A、 B兩種產(chǎn)品 ， 這兩種產(chǎn)品分別需要在甲 、 乙丙三種不同的設(shè)備上加工 ， 有關(guān)數(shù)據(jù)如表 314所示 。 問應(yīng)如何安排生產(chǎn)計(jì)劃才能使利潤(rùn)最大 ？ 4 5 利潤(rùn)（元 /件） 45 1 1 丙 80 1 2 乙 90 3 1 甲 有效臺(tái)時(shí) 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 ,則這個(gè)問題可以歸結(jié)為求解下列線性規(guī)劃問題： 山東理工大學(xué)管理學(xué)院 設(shè) y1, y2, y3分別表示設(shè)備甲、乙、丙每臺(tái)時(shí)的加工費(fèi)（或租金） ,則 ????????????0,4352.321321321yyyyyyyyytsm i n g y y y? ? ?90 80 451 2 3 如果工廠準(zhǔn)備將設(shè)備進(jìn)行出租，請(qǐng)為該廠的決策者進(jìn)行決策。 山東理工大學(xué)管理學(xué)院 問題（ P）： 問題（ D）： 出租方（生產(chǎn)者） 希望獲利最大 希望付出（成本、費(fèi)用）最小 承租方 原問題與對(duì)偶問題 ??????????????0,45802903.21212121xxxxxxxxts21 45m a x xxf ??????????????0,4352.321321321yyyyyyyyytsm i n g y y y? ? ?90 80 451 2 3山東理工大學(xué)管理學(xué)院 例 2:某種作物，全部生產(chǎn)過程至少需氮肥 32公斤，磷肥24公斤，鉀肥 42公斤。已知甲、乙、丙、丁四種復(fù)合肥料每公斤的價(jià)格以及氮磷鉀的含量，如下表所示： 甲 乙 丙 丁 肥料需要量 / 公斤 氮 0 32 磷 0 24 鉀 0 0 42 每公斤價(jià)格 / 元 問：應(yīng)如何選購(gòu)這些肥料，即能滿足作物對(duì)氮磷鉀的需要，又使施肥成本最低？ 山東理工大學(xué)管理學(xué)院 設(shè)用 1x ， 2x ， 3x ， 4x 分別表示甲乙丙丁四種肥料的用量，則該問題的數(shù)學(xué)模型為： 4321 i n xxxxf ???? s .t . 0,432141431421?????????xxxxxxxxxxxx 山東理工大學(xué)管理學(xué)院 現(xiàn)從另外一個(gè)角度考慮：有一化肥公司生產(chǎn)氮、磷、鉀三種單成分化肥，現(xiàn)要為這三種化肥定價(jià)，既要獲利最大，又要和生產(chǎn)甲乙丙丁四種復(fù)合肥料公司競(jìng)爭(zhēng)，因此以這些單成分化肥的價(jià)格、施肥滿足作物需要時(shí)，要求利潤(rùn)最大。 設(shè)用 1y ， 2y ， 3y 分別表示 氮、磷、鉀三種化肥的定價(jià) ，則該問題的數(shù)學(xué)模型為： 321422432m a x yyyg ??? s .t. 0,32132121321?????????yyyyyyyyyyy 山東理工大學(xué)管理學(xué)院 321422432m a x yyyg ??? s .t . 0,32132121321?????????yyyyyyyyyyy 4321 i n xxxxf ???? s .t . 0,432141431421?????????xxxxxxxxxxxx （ P） （ D） 山東理工大學(xué)管理學(xué)院 對(duì)稱的對(duì)偶問題 原問題 對(duì)偶問題 ? ? ? ? ? ? 0 min Y C YA Yb g ? ? ? ? ? ? 0 max X b AX CX f 山東理工大學(xué)管理學(xué)院 例 3：寫出下面問題的對(duì)偶規(guī)劃 max f = 5x1 +6x2 3x1 –2x2 =7 4x1 +x2 ? 9 x1 , x2 ?0 山東理工大學(xué)管理學(xué)院 解： 3x1 –2x2 ? 7 3x1 –2x2 ? 7 4x1 +x2 ? 9 y139。 y1 y2 max f = 5x1 +6x2 3x1 –2x2 ? 7 3x1 +2x2 ? 7 4x1 +x2 ? 9 x1 , x2 ?0 山東理工大學(xué)管理學(xué)院 對(duì)偶問題 3y139。 3y1 +4y2 ?5 2y139。 +2y1 +y2 ? 6 y139。 ,