【正文】 問應(yīng)如何使用這些肥料，既能滿足作物生長的需要，又能使施肥成本最低？ 原始數(shù)據(jù)表 肥肥 料料 數(shù)數(shù) 量量 成成 分分 甲甲 乙乙 丙丙 丁丁需需 要要 量量 （（ 公公 斤斤氮氮 00 .. 00 33 00 .. 33 00 00 .. 11 55 33 33磷磷 00 .. 00 55 00 00 .. 22 00 .. 11 22 44鉀鉀 00 .. 11 44 00 00 00 .. 00 77 44 22每每 公公 斤斤 價價 格格 （（ 元元 ）） 44 11 55 11 00 11 33解： 假設(shè)用甲、乙、丙、丁為 X XX X4公斤。 常數(shù)項(xiàng)是負(fù)數(shù)且最小，確定出基變量 x5。 ?如果某資源的對偶解小于零，表明該資源在系統(tǒng)內(nèi)無獲利能力，應(yīng)賣出該資源。 max g=23x1+40x25 x310x4 . 2x1+3x2 x3 =0 x1+2x2 x4 =0 x3 ? 25 x4 ? 15 x1,x2 , x3 , x4 ? 0 （模型二） 最優(yōu)解 X=(5,5,0,0) 最優(yōu)值 Z=40 對偶解 Y=(6,11,1,1) 一般來講，如果模型顯性地處理所有資源的成本計(jì)算（模型二）則對偶解與影子價格相等，我們按以下原則考慮企業(yè)的經(jīng)營策略： ?如果某資源的影子價格高于市場價格，表明該資源在系統(tǒng)內(nèi)有獲利能力，應(yīng)買入該資源。因而在經(jīng)濟(jì)管理中有十分重要的價值。 ?影子價格的取值與系統(tǒng)的價值取向有關(guān)，并受系統(tǒng)狀態(tài)變化的影響。 j=1,2,… ,n) 在一對變量中，其中一個大于 0，另一個一定等于 0 原問題與對偶問題解的對應(yīng)關(guān)系 對對 偶偶 問問 題題問問 題題 與與 解解 的的狀狀 態(tài)態(tài)有有 最最 優(yōu)優(yōu) 解解 無無 界界 無無 可可 行行 解解有有 最最 優(yōu)優(yōu) 解解 一一 定定 不不 可可 能能 不不 可可 能能無無 界界 不不 可可 能能 不不 可可 能能 可可 能能原原問問題題無無 可可 行行 解解 不不 可可 能能 可可 能能 可可 能能 22 對偶解的經(jīng)濟(jì)解釋 如果把線性規(guī)劃的約束看成廣義資源約束，右邊項(xiàng)則代表某種資源的可用量。 原問題 : 2x1+x3= 4 根據(jù)對偶規(guī)劃的對稱性 ,若原規(guī)劃某個變量無非負(fù)限制 ,則與之對應(yīng)的對偶約束為等式約束 . 若原規(guī)劃中有等式約束 ,則與之對應(yīng)的對偶變量無非負(fù)限制 . 例 27： 寫出下列線性規(guī)劃問題的對偶問題 min S = 3x1 2x2 + x3 . x1+2x2 = 1 2x2 x3 ? 2 2x1 +x3 ? 3 x1 2x2 + 3x3 ? 4 x1， x2 ? 0 ， x3 無非負(fù)限制 不等式兩邊乘(1) min g = 3x1 2x2 + x3 . x1+2x2 = 1 y1 2x2 + x3 ? 2 y2 2x1 +x3 ? 3 y3 x1 2x2 + 3x3 ? 4 y4 x1， x2 ? 0 ， x3 無非負(fù)限制 解 : 綜合運(yùn)用對偶原則得到 max Z = y1+2y2 +3y3 +4y4 . y1+ 2y3 + y4 ? 3 x1 2y1 2y2 2y4 ? 2 x2 y2+ y3 +3y4 = 1 x3 y2, y3, y4 ? 0 ， y1 無非負(fù)約束 x3 無非負(fù)限制 x1+2x2= 1 對偶問題的基本定理 定理 :(對稱性定理 ) 對偶問題的對偶就是原問題 . min z’=CTX . AX ≥ b X ≥0 max g’=Yb . YA ≤ C Y ≥0 min g=Yb . YA ≥ C Y ≥0 max z=CTX . AX ≤ b X ≥0 對偶的定義 對偶的定義 定理 :(弱對偶定理 ) 對于互為對偶問題 (I)(II)中的任意的可行解 X(0),Y(0),都有 CTX(0) ≤Y(0) b 用非線性函數(shù)馬鞍面說明定理的含義（鞍點(diǎn)）。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最??？ 各種食物的營養(yǎng)成分表 序號 食品名稱 熱量 (千卡 ) 蛋白質(zhì) (克 ) 鈣 (毫克 ) 價格 (元 ) 1 豬肉 1000 50 400 14 2 雞蛋 800 60 200 6 3 大米 900 20 300 3 4 白菜 200 10 500 2 解： 設(shè) xj為第 j種食品每天的購入量，則配餐問題的線性規(guī)劃模型為： min S=14x1+6x2 +3x3+2x4 . 1000x1+800x2 +900x3+200x4 ? 3000 50x1+ 60x2 + 20x3+ 10x4 ? 55 400x1+200x2 +300x3+500x4 ? 800 x1， x2 ， x3 ， x4 ? 0 () 該問題的對偶問題 ： max g = 3000 y1+55y2+800y3 . 1000 y1+50y2+400y3 ? 14 () 800 y1+60y2+200y3 ? 6 900 y1+20y2+300y3 ? 3 200 y1+10y2+500y3 ? 2 y1， y2， y3 ? 0 該問題的對偶問題 ()經(jīng)濟(jì)意義可解釋為：市場上有一廠商生產(chǎn)三種可代替食品中的熱量、蛋白質(zhì)和鈣的營養(yǎng)素，該廠商希望它的產(chǎn)品既有市場競爭力，又能帶來最大利潤，因此需要構(gòu)造一個模型來研究定價問題。 該企業(yè)家所付的租金不能太低，否則家具廠的管理者覺得無利可圖而不肯出租給他。桌子售價 50元 /個，椅子銷售價格 30/個，生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種。 假如有一個企業(yè)家有一批等待加工的訂單，有意利用該家具廠的木工和油漆工資源來加工他的產(chǎn)品。 任何線性規(guī)劃問題都有對偶問題， 而且都有相應(yīng)的意義。 。 對偶問題的基本定理 定理 (最優(yōu)準(zhǔn)則 ) 若原問題的某一個可行解與對偶問題的某一可行解的目標(biāo)函數(shù)值相等 ,則它們分別是原問題與對偶問題的最優(yōu)解 . 對偶問題的基本定理 定理 (對偶定理 ) 若原問題有最優(yōu)解 ,則對偶問題也有最優(yōu)解 ,且最優(yōu)值相等 . 對偶問題的基本定理 定理 (對偶定理 ) 若原問題有最優(yōu)解 ,則對偶問題也有最優(yōu)解 ,且最優(yōu)值相等。因此，也稱為最優(yōu)價格。如果某資源是稀缺資源，其影子價格必然大于零。每單位原料的采購成本為 5元，每小時人工工資為 10元。 ?如果某資源的影子價格等于市場價格，表明該資源在系統(tǒng)內(nèi)處于平衡狀態(tài)，既不用買入，也不必賣出該資源。 對偶單純形法其基本思路：在換基迭代過程中，始終保持檢驗(yàn)數(shù)非正，逐步使基變量值變成非負(fù)，最后求得最優(yōu)解或判斷無最優(yōu)解。但常數(shù)項(xiàng)為負(fù)數(shù)的行元素全大于零，原問題無可行解。 謝謝大家！ 。 Cj 1 2 0 0 0 C B X B x 1 x 2 x 3 x 4 x 5 b 0 X 4 1 2 1 1 0 1 0 X 5 1 2 1 0 1 6 σ 1 2