【正文】 迭代 保持 檢驗(yàn)數(shù) ? 0， 使 右端常數(shù) ?0。 迭代 保持右端常數(shù) ?0， 使 檢驗(yàn)數(shù) ? 0。 山東理工大學(xué)管理學(xué)院 1 2 3m a x 1 0 0 1 2 0 1 6 0f x x x? ? ??????????????????????0,20608040.321321321321xxxxxxxxxxxxts式中 f—從事咨詢工作每月可得的利潤(rùn)總和 （ 元 /月 ） 。教授估計(jì)三個(gè)企業(yè)每月要求最大的咨詢時(shí)間分別是 80、60、 20小時(shí) 。目前他有較多的咨詢機(jī)會(huì)，但可用時(shí)間有限，他希望詳細(xì)分析這種情況，他是否要雇助手？如果這樣，他應(yīng)付多少工資？ 山東理工大學(xué)管理學(xué)院 設(shè)： x1 = 每月為 A企業(yè)咨詢的小時(shí)數(shù) （ 利潤(rùn)： 100元 /h） x2 = 每月為 B企業(yè)咨詢的小時(shí)數(shù) （ 利潤(rùn)： 120元 /h） x3 = 每月為 C企業(yè)咨詢的小時(shí)數(shù) （ 利潤(rùn)： 160元 /h） 進(jìn)一步假定該教授每月有 40小時(shí) 用于咨詢工作，并且希望他的旅行時(shí)間每月在 24小時(shí) 以內(nèi)。也就是說，要求咨詢的單位愈遠(yuǎn)，他得到的報(bào)酬愈多。 山東理工大學(xué)管理學(xué)院 例 : 一個(gè)大學(xué)教授用部分時(shí)間從事于咨詢工作。 ③ 影子價(jià)格在新產(chǎn)品開發(fā)決策中的應(yīng)用。 山東理工大學(xué)管理學(xué)院 ??????????????????????0,0,0750105564086.1064m a x321321321321321xxxxxxxxxxxxtsxxxfxj x1 x2 x3 x4 x5 x6 B1b x2 x5 x3 0 1 0 2 0 2 0 0 6 1 1/2 0 1 1 0 40 160 55 f 1 0 0 2 0 790 山東理工大學(xué)管理學(xué)院 ① 影子價(jià)格可以告訴管理人員，增加哪一種資源對(duì)增加經(jīng)濟(jì)效益最有益。 山東理工大學(xué)管理學(xué)院 例 4 某工廠生產(chǎn)三種產(chǎn)品，三種產(chǎn)品對(duì)于原材料、勞動(dòng)力、電力的單位消耗系數(shù)，資源限量和單位產(chǎn)品價(jià)格如下表所示： A B C 資源限量 原材料（ kg） 勞動(dòng)力（人） 電力（度） 2 6 5 1 5 4 8 10 320 640 750 單位價(jià)格（元） 4 6 10 資源 產(chǎn)品 。 影子價(jià)格 是指在最優(yōu)解的基礎(chǔ)上，當(dāng)?shù)? i 個(gè)約束條件的右端項(xiàng) bi 增加一個(gè)單位時(shí)，目標(biāo)函數(shù)的變化量。 山東理工大學(xué)管理學(xué)院 例 3 已知線性規(guī)劃問題 ??????????????0,132232.321321321xxxxxxxxxts21 3m a x xxf ??試用對(duì)偶理論證明上述問題無最優(yōu)解。 。 最優(yōu)解。 若原問題和對(duì)偶問題之一有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且兩者的最優(yōu)目標(biāo)函數(shù)值相等。 若原問題（對(duì)偶問題）的目標(biāo)函數(shù)無界，則其對(duì)偶問題 （原問題）必?zé)o可行解。 y1 ， 則 min g=7y1 +9y2 3y1+4y2 ?5 2y1 +y2 ? 6 y1自由 , y2 ? 0 山東理工大學(xué)管理學(xué)院 非對(duì)稱的對(duì)偶問題 原問題 對(duì)偶問題 ? ? ? ? ? ? 0 max X b AX CX f ? ? ? ? ? 無正負(fù)限制 Y C YA Yb g min 山東理工大學(xué)管理學(xué)院 混合形式的對(duì)偶問題 ???????????????????????無限制321321321321321,0,0322252.523m a xyyyyyyyyyyyytsyyyg? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 無限制 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 , 0 , 0 5 2 2 2 3 . 3 2 25 min x x x x x x x x x x x x t s x x x f 山東理工大學(xué)管理學(xué)院 例 4：寫出下列線性規(guī)劃的對(duì)偶規(guī)劃 min f= 4x1 +2x2 –3x3 x1+2x2 ? 6 2x1 +3x3 ? 9 x1 +5x2 –2x3 = 4 x2 , x3 ?0 max g= 6y1 +9y2 +4y3 y1+2y2 + y3 = 4 2y1 +5y3 ? 2 3y2 2y3 ? 3 y1 ? 0 , y2 ?0 , y3為 自由變量 解：原線性規(guī)劃的對(duì)偶規(guī)劃為： 山東理工大學(xué)管理學(xué)院 課堂練習(xí) 32145m a x xxxf ??? ???????????????????0,0458022903.21321321321xxxxxxxxxxxts 寫出下列線性規(guī)劃問題的對(duì)偶規(guī)劃 山東理工大學(xué)管理學(xué)院 原問題和對(duì)偶問題的關(guān)系 原問題（或?qū)ε紗栴}） 對(duì)偶問題（或原問題） 目標(biāo)函數(shù)形式 m ax f 目標(biāo)函數(shù)形式 m in g 約 束 條 件 m 個(gè)約束 約束 ? 約束 ? = 變 量 m 個(gè)變量 變量 ? 0 變量 ? 0 無正負(fù)限制 變 量 n 個(gè)變量 變量 ? 0 變量 ? 0 無正負(fù)限制 約 束 條 件 n 個(gè)約束 約束 ? 約束 ? = 約束方程右端項(xiàng) 目標(biāo)函數(shù)中的系數(shù) 目標(biāo)函數(shù)中的系數(shù) 約束方程右端項(xiàng) 山東理工大學(xué)管理學(xué)院 二、對(duì)偶問題的基本性質(zhì) gfYbCX ?? ，即 若 X和 Y分別是原問題和對(duì)偶問題的任一可行解，則必有 該性質(zhì)告訴我們，最大化問題的任一可行解的目標(biāo)函數(shù)值都是其對(duì)偶最小化問題目標(biāo)函數(shù)的下界；而最小化問題的任一可行解的目標(biāo)函數(shù)值都是其對(duì)偶最大化問題目標(biāo)函數(shù)的上界。 , y1 , y2 ? 0 min g=7y139。 3y1 +4y2 ?5 2y139。 設(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。 山東理工大學(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公斤。x5 標(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