對(duì)偶模型 課件

《對(duì)偶模型 課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、Chapter2對(duì)偶問(wèn)題DualProblem1.線性規(guī)劃的對(duì)偶模型DualModelofLP2.對(duì)偶性質(zhì)Dualproperty3.對(duì)偶單純形法DualSimplexMethod4.靈敏度分析SensitivityAnalysis運(yùn)籌學(xué)OperationsResearch在線性規(guī)劃問(wèn)題中，存在一個(gè)有趣的問(wèn)題，即每一個(gè)線性規(guī)劃問(wèn)題都伴隨有另一個(gè)線性規(guī)劃問(wèn)題，稱它為對(duì)偶線性規(guī)劃問(wèn)題?！纠?.1】某企業(yè)用四種資源生產(chǎn)三種產(chǎn)品，工藝系數(shù)、資源限量及價(jià)值系數(shù)如下表：產(chǎn)品資源ABC資源限量Ⅰ986500Ⅱ547450Ⅲ832300Ⅳ76

2、4550每件產(chǎn)品利潤(rùn)1008070建立總收益最大的數(shù)學(xué)模型?！窘狻吭O(shè)x1，x2，x3分別為產(chǎn)品A，B，C的產(chǎn)量，則線性規(guī)劃數(shù)學(xué)模型為：現(xiàn)在從另一個(gè)角度來(lái)考慮企業(yè)的決策問(wèn)題。假如企業(yè)自己不生產(chǎn)產(chǎn)品，而將現(xiàn)有的資源轉(zhuǎn)讓或出租給其它企業(yè)，那么資源的轉(zhuǎn)讓價(jià)格是多少才合理？?jī)r(jià)格太高對(duì)方不愿意接受，價(jià)格太低本單位收益又太少。合理的價(jià)格應(yīng)是對(duì)方用最少的資金購(gòu)買本企業(yè)的全部資源，而本企業(yè)所獲得的利潤(rùn)不應(yīng)低于自己用于生產(chǎn)時(shí)所獲得的利潤(rùn)。這一決策問(wèn)題可用下列線性規(guī)劃數(shù)學(xué)模型來(lái)表示。設(shè)y1，y2，y3及y4分別表示四種資源的單位增殖價(jià)格（售價(jià)＝成本

3、＋增殖），總增殖最低可用minw=500y1+450y2+300y3+550y4表示。企業(yè)生產(chǎn)一件產(chǎn)品A用了四種資源的數(shù)量分別是9，5，8和7個(gè)單位，利潤(rùn)是100,企業(yè)出售這些數(shù)量的資源所得的利潤(rùn)不能少于100，即同理，對(duì)產(chǎn)品B和C有價(jià)格不可能小于零，即有yi≥0,i=1,…,4.從而企業(yè)的資源價(jià)格模型為這是一個(gè)線性規(guī)劃數(shù)學(xué)模型，稱這一線性規(guī)劃問(wèn)題是前面生產(chǎn)計(jì)劃問(wèn)題的對(duì)偶線性規(guī)劃問(wèn)題或?qū)ε紗?wèn)題。生產(chǎn)計(jì)劃的線性規(guī)劃問(wèn)題稱為原始線性規(guī)劃問(wèn)題或原問(wèn)題。【例2.2】某人根據(jù)醫(yī)囑，每天需補(bǔ)充A、B、C三種營(yíng)養(yǎng)，A不少于80單位，B不少于

4、150單位，C不少于180單位。此人準(zhǔn)備每天從六種食物中攝取這三種營(yíng)養(yǎng)成分。已知六種食物每百克的營(yíng)養(yǎng)成分含量及食物價(jià)格如下表，試建立此人在滿足健康需要的基礎(chǔ)上花費(fèi)最少的數(shù)學(xué)模型。營(yíng)養(yǎng)成分一二三四五六需要量A13251440811≥80B24930251215≥150C1872134100≥180食物單價(jià)（元/100g）0.50.40.80.90.30.2含量食物【解】設(shè)xj為每天第j種食物的用量，數(shù)學(xué)模型為現(xiàn)有一制藥廠要生產(chǎn)一種包含A、B、C三種營(yíng)養(yǎng)成分的合成藥，如何制定價(jià)格，使得此藥既要暢銷又要產(chǎn)值最大。設(shè)yi（i=1，2，

5、3）為第i種營(yíng)養(yǎng)成分的單價(jià)，則影子價(jià)格(Shadowprice):上面兩個(gè)線性規(guī)劃有著重要的經(jīng)濟(jì)含義。原始線性規(guī)劃問(wèn)題考慮的是充分利用現(xiàn)有資源，以產(chǎn)品的數(shù)量和單位產(chǎn)品的收益來(lái)決定企業(yè)的總收益，沒有考慮到資源的價(jià)格，但實(shí)際在構(gòu)成產(chǎn)品的收益中，不同的資源對(duì)收益的貢獻(xiàn)也不同，它是企業(yè)生產(chǎn)過(guò)程中一種隱含的潛在價(jià)值，經(jīng)濟(jì)學(xué)中稱為影子價(jià)格，即對(duì)偶問(wèn)題中的決策變量yi的值。由后面的對(duì)偶性質(zhì)可知：原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)值相等，故有即yi是第i種資源的變化率，說(shuō)明當(dāng)其它資源供應(yīng)量bk(k≠i)不變時(shí)，bi增加一個(gè)單位時(shí)目標(biāo)值Z增加yi個(gè)單位。例

6、如，第一種資源的影子價(jià)格為y1=2，第二種資源的影子價(jià)格為y2=2，即當(dāng)?shù)谝环N資源增加一個(gè)單位時(shí)，Z增加2個(gè)單位，當(dāng)?shù)诙N資源增加一個(gè)單位時(shí)，Z增加2個(gè)單位。企業(yè)可利用影子價(jià)格調(diào)節(jié)生產(chǎn)規(guī)模。例如，目標(biāo)函數(shù)Z表示利潤(rùn)（或產(chǎn)值），當(dāng)?shù)趇種資源的影子價(jià)格大于零（或高于市場(chǎng)價(jià)格）時(shí)，表示有利可圖，企業(yè)應(yīng)購(gòu)進(jìn)該資源擴(kuò)大生產(chǎn)規(guī)模，當(dāng)影子價(jià)格等于零（或低于市場(chǎng)價(jià)格），企業(yè)不能增加收益，這時(shí)應(yīng)將資源賣掉或出讓，縮小生產(chǎn)規(guī)模。應(yīng)當(dāng)注意，是在最優(yōu)基B不變的條件下有上述經(jīng)濟(jì)含義，當(dāng)某種資源增加或減少后，最優(yōu)基B可能發(fā)生了變化，這時(shí)yi的值也隨之變化

7、。在例2.1中，原問(wèn)題的最優(yōu)解X＝（24.24，0，46.96）對(duì)偶問(wèn)題的最優(yōu)解Y＝（10.6，0.91，0，0）最優(yōu)值z(mì)=w=5712.12分析：1.y1=10.6說(shuō)明在現(xiàn)有的資源限量的條件下，增加一個(gè)單位第一種資源可以給企業(yè)帶來(lái)10.6元的利潤(rùn)；如果要出售該資源，其價(jià)格至少在成本價(jià)上加10.6元。2.y3=0說(shuō)明增加第三種資源不會(huì)增加利潤(rùn)，因?yàn)榈谌N資源還有沒有用完。問(wèn)題：1.第三、四種資源的售價(jià)是多少，是否不值錢？2.如果要增加利潤(rùn)，企業(yè)應(yīng)增加哪幾種資源，各增加多少后再進(jìn)行調(diào)整？上面兩種形式的線性規(guī)劃稱為對(duì)稱形式。原問(wèn)題

8、和對(duì)偶問(wèn)題是互為對(duì)偶的兩個(gè)線性規(guī)劃問(wèn)題，已知一個(gè)問(wèn)題就可寫出另一個(gè)問(wèn)題。對(duì)稱形式的定義是：目標(biāo)函數(shù)求極大值時(shí)，所有約束條件為≤號(hào)，變量非負(fù)；目標(biāo)函數(shù)求極小值時(shí)，所有約束條件為≥號(hào)，變量非負(fù)。對(duì)稱形式的線性規(guī)劃的對(duì)偶問(wèn)題亦是對(duì)稱形式。以上是依據(jù)經(jīng)濟(jì)問(wèn)題推導(dǎo)出對(duì)偶問(wèn)題，還可以用代