數(shù)據(jù)模型決策線性規(guī)劃

線性規(guī)劃的對偶問題例1：某公司利用現(xiàn)有三條生產(chǎn)線生產(chǎn)兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：設(shè)

Ⅰ產(chǎn)量–––––Ⅱ產(chǎn)量–––––問如何安排生產(chǎn)，使獲利最多？產(chǎn)品甲產(chǎn)品乙每周可用量生產(chǎn)線一104小時生產(chǎn)線二0212小時生產(chǎn)線三3218小時產(chǎn)品利潤3百元5百元一、對偶問題的提出例2.1*有一個中間商接到一批加工定單，需用到該公司的三條生產(chǎn)線,有意租用該公司的三條生產(chǎn)線全部可用時間，問中間商應(yīng)如何出價，才能使公司覺得有利可圖肯把設(shè)備出租，又使自己付出的租金最少？中間商

付出的代價最小出讓代價應(yīng)不低于用同等數(shù)量的資源自己生產(chǎn)的利潤。對方能接受公司生產(chǎn)線一生產(chǎn)線二生產(chǎn)線三利潤（百元）１０３３０２２５４時12時18時ⅠⅡD公司能接受的條件：中間商的意愿：出讓代價應(yīng)不低于用同等數(shù)量的資源自己生產(chǎn)的利潤。設(shè)：生產(chǎn)線一—Y1百元／時,生產(chǎn)線二

––y2百元／時,生產(chǎn)線三––y3百元／時對偶問題原問題中間商公司一對對偶問題設(shè)原線性規(guī)劃問題為：則稱下面的線性規(guī)劃問題：為其對偶規(guī)劃，二、原問題與對偶問題的對應(yīng)關(guān)系1：定義表中間的數(shù)(aij)的每一行與xj對應(yīng)地乘起來相加后不大于這一行右邊的數(shù)bi，就是原問題的一個約束條件。最后一行cj與xj對應(yīng)地乘起來相加就是原問題的目標(biāo)函數(shù)。類似地，把(aij)的每一列與yi對應(yīng)地乘起來相加后不小于cj就是對偶問題的一個約束條件。最后一列與yj對應(yīng)地乘起來相加就是目標(biāo)函數(shù)。所求對偶問題為：化為定義中的形式對偶規(guī)規(guī)劃問問題（（D）為對偶規(guī)規(guī)劃問問題（（D）為對偶規(guī)規(guī)劃問問題（（D）為：：對偶規(guī)規(guī)劃問問題（（D）為：：原問題題（P）對偶問問題（（D）變量約約束：：方程約約束：：變量≥方程≥≥變量無限制制方程=變量≤方程≤方程約約束：：變量約約束：：方程=變量無限制制方程≤變量≥方程≥≥變量≤重要結(jié)結(jié)論２、若原問問題存存在最最優(yōu)解解，則則其對對偶問問題一一定存存在最最優(yōu)解解，且且有相相同的的最優(yōu)優(yōu)值．1、對偶問問題的的對偶偶就是是原問問題。（（即互互為對對偶規(guī)規(guī)劃））練習(xí)：：（P）與(D)的關(guān)系系對應(yīng)應(yīng)表：：

原問題

對偶問題目標(biāo)函函數(shù)max目標(biāo)函函數(shù)min目標(biāo)函函數(shù)系系數(shù)約束方方程常常數(shù)列列約束方方程常常數(shù)列列目標(biāo)函函數(shù)系系數(shù)變量個個數(shù)n約束方方程個個數(shù)n約束方方程個個數(shù)m變量個個數(shù)m約束方方程≤≤變量≥≥0≥≤0=無符號號約束束變量≥≥0約束方方程≥≥≤0≤無符號號約束束=系數(shù)矩矩陣A對偶解解的經(jīng)經(jīng)濟(jì)意意義-------影子價價格資源的的合理理利用用問題題：資源單位消費產(chǎn)品資源限制單位利潤還有現(xiàn)現(xiàn)金，，問應(yīng)應(yīng)該投投資何何種資資源？？決策依依據(jù)：比較第i種資源源增加加一個個單位位，其余余資源源不增增加時時利潤的的增加加值是是否為為正。。決策依依據(jù)：：在取得得最優(yōu)優(yōu)方案案的前前提下下比較第第i種資源源增加加一個個單位位，其其余資資源不不增加加時利利潤的的增加加值設(shè)是是最優(yōu)優(yōu)解，，Z*是最優(yōu)優(yōu)值設(shè)其最最優(yōu)解解最優(yōu)值值為ＷＷ*則Z*＝Ｗ*此時原原問題題變?yōu)闉樽顑?yōu)值值為ＺＺ**此時目目標(biāo)函函數(shù)的的增量量是Ｚ**-Ｚ*此時由由于該該對偶偶問題題可行行域沒沒發(fā)生生變化化，目目標(biāo)函函數(shù)中中第i個系數(shù)數(shù)改變變很小小，所所以可可以假假設(shè)其其最優(yōu)優(yōu)解沒沒有變變化，，則還還是是最優(yōu)優(yōu)解，，設(shè)此時最優(yōu)值值為ＷＷ**則Z**＝Ｗ**＝＝此時對對偶問問題變變?yōu)閆*第i種資源源增加加一個個單位位，其其余資資源不不增加加時利利潤的的增加加值正正好是是原問問題的的對偶偶問題題最優(yōu)優(yōu)解的的第i個分量量對偶價價格邊際價價格1、對偶偶價格格的定定義對偶價價格也也稱為為影子價價格，在用用lingo軟件求求解原原問題時時，程程序的的輸出出結(jié)果果會給給出所所有的的對偶偶價格格資源單位消費產(chǎn)品甲乙資源限制鋼材52170煤炭23100設(shè)備臺時15150單位利潤（萬元）1018最優(yōu)解解X*=(50/7，200/7)最優(yōu)值值Z*=4100/7Y*=(0，32/7,6/7)對偶價價格對偶價價格（（影子子價格格）Y*=(0，32/7,6/7)鋼材煤炭設(shè)備臺時即再增增加1噸鋼材材，利利潤不不會增增加即再增增加1噸煤炭炭，利利潤增增加3/7萬元即再增增加1個臺時時，利利潤增增加6/7萬元例:某公司司利用用現(xiàn)有有三條條生產(chǎn)產(chǎn)線生生產(chǎn)兩兩種產(chǎn)產(chǎn)品品，有有關(guān)數(shù)數(shù)據(jù)如如下表表：問如何何安排排生產(chǎn)產(chǎn)，使使獲利利最多多？產(chǎn)品甲產(chǎn)品乙每周可用量資源單位成本生產(chǎn)線一104小時1百元/小時生產(chǎn)線二0212小時1百元/小時生產(chǎn)線三3218小時1百元/小時產(chǎn)品售價7百元9百元數(shù)學(xué)模模型一一：設(shè)甲產(chǎn)產(chǎn)量–––––––x1乙產(chǎn)量量–––––––––x2則生生產(chǎn)產(chǎn)一一個個單單位位甲甲產(chǎn)產(chǎn)品品獲獲利利潤潤7－1××1－3××1＝3（百百元元））則生生產(chǎn)產(chǎn)一一個個單單位位乙乙產(chǎn)產(chǎn)品品獲獲利利潤潤9－2××1－2××1＝5（百百元元））最優(yōu)優(yōu)解解X*=(2，6)最優(yōu)優(yōu)值值Z*=36Y*=(0,1.5,1)對偶偶價價格格最優(yōu)優(yōu)解解X*=(2,6,2,12,18)最優(yōu)優(yōu)值值Z*=36Y*=(1,2.5,2,0,1.5,1)對偶偶價價格格數(shù)學(xué)學(xué)模模型型二二：：設(shè)甲甲產(chǎn)產(chǎn)量量–––––––––x1乙產(chǎn)產(chǎn)量量–––––––––x2三條條生生產(chǎn)產(chǎn)線線實實際際利利用用時時間間分分別別為為x3,x4,x5小時時注意意：：從剛剛才才的的兩兩個個模模型型可可以以看看到到：：模型型一一中中的的對對偶偶價價格格（（影影子子價價格格））是是指指當(dāng)當(dāng)資資源源增增加加一一個個單單位位時時，，總總利利潤潤的的增增加加量量，，因因此此此此時時的的對對偶偶價價格格準(zhǔn)準(zhǔn)確確來來講講應(yīng)應(yīng)該該稱稱為為影子子利利潤潤。模型型二二中中的的前前三三個個對對偶偶價價格格，，是是指指當(dāng)當(dāng)資源源無無成成本本的的增增加加一一個個單單位位時時總總利利潤潤的的增增加加量量，它它們們反反映映了了資資源源在在系系統(tǒng)統(tǒng)內(nèi)內(nèi)的的真真正正價價值值，，因因此此他他們們才才是是真真正正意意義義上上的的影子子價價格格。例例如如第第二二個個對對偶偶價價格格2.5反映映了了第第二二種種資資源源在在系系統(tǒng)統(tǒng)內(nèi)內(nèi)的的真真正正價價值值是是250元，，比比其其成成本本100元要要大大150元，，因因此此增增加加一一個個單單位位的的第第二二種種資資源源，，利利潤潤增增加加150元。。影子子價價格格是是一一種種資資源源的的虛虛擬擬價價格格≠資源源的的市市場場價價格格,是根根據(jù)據(jù)資資源源在在生生產(chǎn)產(chǎn)中中作作出出的的貢貢獻(xiàn)獻(xiàn)而而作作出出的的估估價價，，它它實實際際上上是是一一種種機(jī)會會成成本本。為什什么么叫叫影影子子價價格格？？機(jī)會會成成本本是指指從從事事某某一一種種業(yè)業(yè)務(wù)務(wù)而而損損失失別別的的業(yè)業(yè)務(wù)務(wù)的的代代價價2、影影子子價價格格在在經(jīng)經(jīng)濟(jì)濟(jì)管管理理中中的的應(yīng)應(yīng)用用影子子價價格格越越大大的的資資源源，，表表明明：：這種種資資源源對對目目標(biāo)標(biāo)增增益益的的影影響響越越大大這種種資資源源對對該該企企業(yè)業(yè)越越稀稀缺缺、、貴貴重重影子子價價格格(影子子利利潤潤)為零零的的資資源源，，表表明明：：這種種資資源源對對該該企企業(yè)業(yè)來來說說相相對對富富裕