線性規(guī)劃的對(duì)偶問(wèn)題

《線性規(guī)劃的對(duì)偶問(wèn)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、教案五線性規(guī)劃的對(duì)偶問(wèn)題教學(xué)內(nèi)容第四節(jié)線性規(guī)劃的對(duì)偶問(wèn)題1．線性規(guī)劃的對(duì)偶問(wèn)題2．對(duì)偶單純形法3．線性規(guī)劃的靈敏度分析4．線性規(guī)劃在衛(wèi)生管理中的應(yīng)用教學(xué)學(xué)時(shí)7學(xué)時(shí)教學(xué)目標(biāo)1．理解對(duì)偶問(wèn)題的基本概念2．掌握對(duì)偶單純形法3．掌握線性規(guī)劃的靈敏度分析4．掌握線性規(guī)劃在衛(wèi)生管理中的應(yīng)用重點(diǎn)難點(diǎn)重點(diǎn)是對(duì)偶問(wèn)題的基本概念、對(duì)偶單純形法線、靈敏度分析、線性規(guī)劃在衛(wèi)生管理中的應(yīng)用。難點(diǎn)是對(duì)偶問(wèn)題的基本概念和線性規(guī)劃的靈敏度分析教學(xué)手段教師與學(xué)生互動(dòng)使用多媒體課件教學(xué)過(guò)程一、復(fù)習(xí)鞏固1．單純形法的基本原理（見(jiàn)課件）2．單純形解法（見(jiàn)課件）3．大法

2、（見(jiàn)課件）二、講授新課1．線性規(guī)劃的對(duì)偶問(wèn)題（1）對(duì)偶問(wèn)題的基本概念（見(jiàn)課件）對(duì)偶現(xiàn)象每一個(gè)線性規(guī)劃都伴隨著另一個(gè)線性規(guī)劃，兩者有密切關(guān)系，互為對(duì)偶．其中一個(gè)問(wèn)題稱為原問(wèn)題，另一個(gè)問(wèn)題稱為其對(duì)偶問(wèn)題．兩者間只要得到其中一個(gè)問(wèn)題的解，那么也就得到了另一個(gè)問(wèn)題的解．下面通過(guò)一個(gè)實(shí)例來(lái)解釋對(duì)偶線性規(guī)劃的概念．例2-12以例2-1為例，我們討論了一個(gè)制藥廠的生產(chǎn)計(jì)劃的數(shù)學(xué)模型及其解法．現(xiàn)在假定該制藥廠決定在計(jì)劃期內(nèi)不生產(chǎn)藥品Ⅰ、Ⅱ，而將生產(chǎn)設(shè)備的有效臺(tái)時(shí)全部租給某公司，那么該公司應(yīng)對(duì)設(shè)備每小時(shí)付多少租金，才能使成本最小，而又能為制藥廠所

3、接受？從租用設(shè)備的公司的角度考慮，一是所付的租金越低越好；二是所付的租金總額能使制藥廠接受，即租金應(yīng)不低于制藥廠自己生產(chǎn)該兩種藥品所得利潤(rùn)，否則，制藥廠寧可自己生產(chǎn)，而不租給公司．設(shè)公司租用該制藥廠四種設(shè)備的租金（元/小時(shí)）分別為、、和．在考慮租用設(shè)備的定價(jià)時(shí)，能使該制藥廠接受的條件是：公司租用該制藥廠用以生產(chǎn)每千克藥品Ⅰ所需四種設(shè)備的臺(tái)時(shí)的租金不應(yīng)少于200元，即同樣，公司租用該制藥廠用以生產(chǎn)每千克藥品Ⅱ所需四種設(shè)備的臺(tái)時(shí)的租金不應(yīng)少于300元，即公司在考慮自身利益時(shí)，其目標(biāo)是使付出的租金總額為最小，即于是，上面的問(wèn)題可以用下

4、列線性規(guī)劃的數(shù)學(xué)模型表示：若把制藥廠利潤(rùn)最大的線性規(guī)劃問(wèn)題稱為原問(wèn)題，則想租用四種設(shè)備的公司的租金最小的線性規(guī)劃問(wèn)題稱為原問(wèn)題的對(duì)偶問(wèn)題（dualproblem）；反之，若把租用四種設(shè)備的公司的租金最小的線性規(guī)劃問(wèn)題稱為原問(wèn)題，則制藥廠利潤(rùn)最大的線性規(guī)劃問(wèn)題稱為原問(wèn)題的對(duì)偶問(wèn)題．影子價(jià)格一般地，我們稱對(duì)偶問(wèn)題的最優(yōu)解為原問(wèn)題約束條件的影子價(jià)格，即對(duì)偶問(wèn)題的解稱為第種資源的影子價(jià)格．它并不是某種資源在市場(chǎng)上的價(jià)格，而是代表單位資源在最優(yōu)利用的條件下所產(chǎn)生的經(jīng)濟(jì)效果．為了和市場(chǎng)價(jià)格相區(qū)別，我們才稱它為影子價(jià)格．它在經(jīng)濟(jì)上是一個(gè)很有意

5、義的數(shù)據(jù)，通過(guò)它我們可以知道，當(dāng)增加某種資源時(shí)，可以使利潤(rùn)增長(zhǎng)的大?。硗?，影子價(jià)格還給出了是否應(yīng)當(dāng)購(gòu)進(jìn)某種資源以增加生產(chǎn)量，而獲得更多利潤(rùn)的價(jià)格標(biāo)準(zhǔn)．（2）對(duì)稱的對(duì)偶線性規(guī)劃（見(jiàn)課件）如果一個(gè)線性規(guī)劃具備下面兩個(gè)條件，則稱它具有對(duì)稱形式：①所有的變量都是非負(fù)的；②所有的約束條件都是不等式，而且在目標(biāo)函數(shù)是求極大值的情況，不等式具有小于和等于（）的符號(hào)，在目標(biāo)函數(shù)是求極小值的情況，不等式具有大于和等于（）的符號(hào)．對(duì)稱形式的原問(wèn)題和對(duì)偶問(wèn)題叫做對(duì)稱的對(duì)偶線性規(guī)劃．原問(wèn)題和對(duì)偶問(wèn)題在形式上的對(duì)比如果我們把線性規(guī)劃…………………………

6、稱為原問(wèn)題，則必同時(shí)存在另一線性規(guī)劃問(wèn)題，我們稱為對(duì)偶問(wèn)題：…………………………而且用簡(jiǎn)縮形式表示：原問(wèn)題為對(duì)偶問(wèn)題為;矩陣形式表示：原問(wèn)題為對(duì)偶問(wèn)題為MinW＝Y(jié)b其中，原問(wèn)題與對(duì)偶問(wèn)題之間的關(guān)系1）原問(wèn)題是求目標(biāo)函數(shù)的最大值，對(duì)偶問(wèn)題是求目標(biāo)函數(shù)的最小值．2）原問(wèn)題約束條件的右端項(xiàng)變成對(duì)偶問(wèn)題目標(biāo)函數(shù)的系數(shù)．原問(wèn)題目標(biāo)函數(shù)中的系數(shù)變成對(duì)偶問(wèn)題約束條件的右端項(xiàng)．3）原問(wèn)題約束條件是“”，對(duì)偶問(wèn)題的約束條件則是“”．4）原問(wèn)題約束條件的每一行正好對(duì)應(yīng)于對(duì)偶問(wèn)題的每一列，所以原問(wèn)題中約束條件的數(shù)目等于對(duì)偶問(wèn)題中變量的數(shù)目．5）原問(wèn)

7、題中約束條件的每一列正好對(duì)應(yīng)于對(duì)偶問(wèn)題的每一行，所以原問(wèn)題中變量的數(shù)目正好等于對(duì)偶問(wèn)題中的約束條件的數(shù)目．6）對(duì)偶問(wèn)題的對(duì)偶規(guī)劃正是原問(wèn)題．例2-13設(shè)原問(wèn)題為：　　　　　　　　　　　　　　　　　　　試寫出它的對(duì)偶問(wèn)題．解　　　　　　　　　?。?）非對(duì)稱的對(duì)偶線性規(guī)劃（見(jiàn)課件）對(duì)于我們經(jīng)常遇到的非對(duì)稱形式的線性規(guī)劃，我們可首先將其化為等價(jià)的對(duì)稱形式的線性規(guī)劃問(wèn)題，然后再按對(duì)稱的對(duì)偶線性規(guī)劃原問(wèn)題與對(duì)偶問(wèn)題之間的對(duì)應(yīng)關(guān)系，將其化為對(duì)偶問(wèn)題．實(shí)際上，我們?cè)诳紤]對(duì)稱的對(duì)偶線性規(guī)劃或非對(duì)稱的對(duì)偶線性規(guī)劃（dualofanonnormal

8、LP）時(shí)，也可以按表2-13原問(wèn)題與對(duì)偶問(wèn)題之間的對(duì)應(yīng)關(guān)系，直接進(jìn)行變換，得到原問(wèn)題或?qū)ε紗?wèn)題．表2-13原問(wèn)題與對(duì)偶問(wèn)題間的轉(zhuǎn)換原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件數(shù)：個(gè)對(duì)偶變量數(shù)：個(gè)第個(gè)約束條件為“”對(duì)偶變量0第個(gè)約束條件為“”對(duì)