1、2020/6/20,1,運(yùn)籌學(xué) OPERATIONS RESEARCH,第二章 線性規(guī)劃的對(duì)偶理論,2020/6/20,2,第二章 線性規(guī)劃的對(duì)偶理論 ( Dual Linear Programming, DLP),原問(wèn)題與對(duì)偶問(wèn)題 對(duì)偶問(wèn)題的基本性質(zhì) 影子價(jià)格 對(duì)偶單純形法 靈敏度分析 參數(shù)線性規(guī)劃,2020/6/20,3,1 對(duì)偶問(wèn)題的提出,一、 線性規(guī)劃單純形法的矩陣描述 設(shè)有線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式,將系數(shù)矩陣表示成：,初始單純形表,初等行變換后,初始表中是 I 的位置，經(jīng)變換后成為,2020/6/20,4,其中,記,則,例：書(shū) P36 例10，驗(yàn)證上述公式。,上述公式對(duì)于靈敏度分析很有

2、幫助 。,2020/6/20,5,，各生產(chǎn)多少, 可獲最大利潤(rùn)?,二、 對(duì)偶問(wèn)題的提出 設(shè)有原問(wèn)題,乙方租借設(shè)備： 甲方以何種價(jià)格將設(shè)備A、B、 C租借給乙方比較合理？ 請(qǐng)為 其定價(jià)。 解： 假設(shè)A、B、C的單位租金 分別為 。,思路： 就甲方而言， 租金收入應(yīng)不低于將設(shè)備用于自己生產(chǎn)時(shí)的利潤(rùn)。,2020/6/20,6,而就乙方而言，希望甲方的租金收入在滿足約束的條件下越小越好， 這樣雙方才可能達(dá)成協(xié)議。 于是得到下述 的線性規(guī)劃模型：,所以：生產(chǎn)產(chǎn)品的資源用于出租時(shí)，租金收入應(yīng)滿足：,類(lèi)似的，生產(chǎn)產(chǎn)品的資源用于出租時(shí)，租金收入應(yīng)滿足：,總的租金收入：,2020/6/20,7,原問(wèn)題,對(duì)偶問(wèn)題

3、,用矩陣將上述原問(wèn)題對(duì)偶問(wèn)題寫(xiě)出,2020/6/20,8,即： 原 問(wèn) 題,對(duì) 偶 問(wèn) 題,2020/6/20,9,2 原問(wèn)題與對(duì)偶問(wèn)題,對(duì)于一般的線性規(guī)劃問(wèn)題，,2020/6/20,10,類(lèi)似于前面的資源定價(jià)問(wèn)題，每一個(gè)約束條件對(duì)應(yīng)一個(gè)“ 對(duì)偶變量”，它就 相當(dāng)于給各資源的單位定價(jià)。于是我們有如下的對(duì)偶規(guī)劃：,2020/6/20,11,對(duì)偶問(wèn)題與原問(wèn)題的關(guān)系：,原 問(wèn) 題,對(duì) 偶 問(wèn) 題,目標(biāo)函數(shù)：MAX,約束條件：m個(gè)約束,變量 ： n個(gè)變量,目標(biāo)函數(shù)：MIN,約束條件：n個(gè)約束,變量 ： m個(gè)變量,這是規(guī)范形式 的原問(wèn)題，由此寫(xiě)出其對(duì)偶問(wèn)題如右方所示，那么，當(dāng)原問(wèn)題 不是規(guī)范形式時(shí)，應(yīng)如

4、何寫(xiě)出其對(duì)偶問(wèn)題？可以先將原問(wèn)題化成規(guī)范的 原問(wèn)題，再寫(xiě)出對(duì)偶問(wèn)題。,2020/6/20,12,例 寫(xiě)出下述規(guī)劃的對(duì)偶問(wèn)題,于是對(duì)偶問(wèn)題即為：,解 先將該問(wèn)題化為規(guī)范形式,也即為：,于是對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。-對(duì)稱性,互為對(duì)偶,2020/6/20,13,如何寫(xiě)出非規(guī)范的原問(wèn)題相應(yīng)的對(duì)偶問(wèn)題： 目標(biāo)函數(shù)MIN MAX 約束條件 約束條件 = ? 4. 變量 ?,例：P55 例2，寫(xiě)出下面規(guī)劃的對(duì)偶規(guī)劃,2020/6/20,14,解：將原問(wèn)題模型變形,則對(duì)偶問(wèn)題是,2020/6/20,15,小結(jié)：對(duì)偶問(wèn)題與原問(wèn)題的關(guān)系：,原 問(wèn) 題,對(duì) 偶 問(wèn) 題,目標(biāo)函數(shù)：MAX,約束條件：m個(gè)約束,變量 ：

5、 n個(gè)變量,目標(biāo)函數(shù)：MIN,約束條件：n個(gè)約束,變量 ： m個(gè)變量,約束條件右端項(xiàng) 價(jià)值系數(shù),價(jià)值系數(shù) 約束條件右端項(xiàng),2020/6/20,16,3 對(duì)偶問(wèn)題的基本性質(zhì),就上節(jié)所討論的一般的線性規(guī)劃問(wèn)題及其對(duì)偶問(wèn)題，有如下的性質(zhì)： 1、弱對(duì)偶性 如果 分 別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，則恒有 考慮利用 及 代入。,2、無(wú)界性 如果原問(wèn)題（對(duì)偶問(wèn)題）有無(wú)界解，則其對(duì)偶問(wèn)題 （原問(wèn)題）無(wú)可行解。,2020/6/20,17,3、最優(yōu)性 如果 分 別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，且有 則 分別是原問(wèn)題和對(duì)偶問(wèn)題的 最優(yōu)解。,證明 設(shè) 分別是原問(wèn)題和 對(duì)偶問(wèn)題的最優(yōu)解，則由弱對(duì)偶性， 又 ，所以,202

6、0/6/20,18,4、強(qiáng)對(duì)偶性 如果原問(wèn)題有最優(yōu)解，則其對(duì)偶問(wèn)題也必有最優(yōu)解， 且兩者最優(yōu)目標(biāo)函數(shù)值相等，即 。,證明 設(shè)有線性規(guī)劃問(wèn)題 經(jīng)單純形法計(jì)算后，令 ， 最終表中 所以 ,即： 由此可知 是對(duì)偶問(wèn)題的可行解 ，又 ， 就是最優(yōu)解。,2020/6/20,19,5、互補(bǔ)松弛性：在線性規(guī)劃的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的 對(duì)偶變量值非零，則該約束條件取嚴(yán)格等式；反之，如果約束條件取 嚴(yán)格不等式，則其對(duì)偶變量一定為零。即 若 若,證明 由弱對(duì)偶性知： 又因在最優(yōu)解中 ，于是上式應(yīng)為等式，即有,2020/6/20,20,而 ，故要使得上式成立，必有 即,后半部分是前一命體的逆否命題，自然成

7、立。 互補(bǔ)松弛性還可寫(xiě)為 對(duì)偶問(wèn)題的相應(yīng)的互補(bǔ)松弛性見(jiàn)書(shū) P58。 例 書(shū)P76 ，習(xí)題2-4,2020/6/20,21,6、設(shè)原問(wèn)題是： 對(duì)偶問(wèn)題是： 則原問(wèn)題的檢驗(yàn)數(shù)行對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)基解（不一定是可行解）， 對(duì)應(yīng)關(guān)系如下表 。,原問(wèn)題與對(duì)偶問(wèn)題存在一對(duì)互補(bǔ)基解，原問(wèn)題的松弛變量與對(duì)偶問(wèn)題 的變量對(duì)應(yīng)；原問(wèn)題的變量與對(duì)偶問(wèn)題的剩余變量對(duì)應(yīng)?；パa(bǔ)的基解 對(duì)應(yīng)的目標(biāo)函數(shù)值相等。,2020/6/20,22,例 書(shū)P59 例3,2020/6/20,23,2020/6/20,24,1、 對(duì)偶變量 可理解為對(duì)一個(gè)單位第 種資源的估價(jià)，稱為影子價(jià) 格，但并非市場(chǎng)價(jià)格。,2、 對(duì)偶變量 的值（即影子價(jià)格

8、）表示第 種資源數(shù)量變化一個(gè)單位時(shí)，目標(biāo)函數(shù)的增量。因?yàn)?4 影子價(jià)格,假設(shè)有原問(wèn)題和對(duì)偶問(wèn)題如下：,2020/6/20,25,資源增加一個(gè)單位時(shí)，最優(yōu)解及目標(biāo)函數(shù)值的變化,2020/6/20,26,3、 影子價(jià)格可用于指導(dǎo)資源的購(gòu)入與賣(mài)出。 當(dāng) 影子價(jià)格 市場(chǎng)價(jià)格時(shí)，買(mǎi)入； 影子價(jià)格 市場(chǎng)價(jià)格 時(shí)，賣(mài)出.,4、 由互補(bǔ)松弛性可知， 即影子價(jià)格為 零，經(jīng)濟(jì)解釋：資源未用完，再增加對(duì)目標(biāo)函數(shù)也無(wú)貢獻(xiàn)。反之， 表明該種資源用盡，再購(gòu)進(jìn)用于擴(kuò)大生 產(chǎn)可增加總利潤(rùn)。,2020/6/20,27,5 對(duì)偶單純形法,在單純形表中， 列對(duì)應(yīng)原問(wèn)題的基可行解， 行 對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)基解（不一定可行），當(dāng) 時(shí)，

9、 在檢驗(yàn)數(shù)行就得到對(duì)偶問(wèn)題的基可行解，此時(shí)兩個(gè)問(wèn)題的目 標(biāo)函數(shù)值相等 ，由最優(yōu)性條件知，兩個(gè) 問(wèn)題都達(dá)到了最優(yōu)解。,單純形法：找一個(gè)初始基可行解，保持b列為正，通過(guò)迭代 找到下一個(gè)基可行解，使目標(biāo)函數(shù)值不斷增大，當(dāng)檢驗(yàn)數(shù)行 全部小于等于零時(shí)，達(dá)到最優(yōu)解。,2020/6/20,28,對(duì)偶單純形法：找一個(gè)對(duì)偶問(wèn)題的基可行解（保持 行非 正），原問(wèn)題的解為基解（ b列可以為負(fù)），通過(guò)迭代，當(dāng) b列全部為正（原問(wèn)題也達(dá)到了基可行解），即找到最優(yōu)解。,3、檢查是否達(dá)最優(yōu) ：b列 非負(fù)時(shí)達(dá)最優(yōu)，否則繼續(xù)1、2。,2020/6/20,29,1、 為何只考慮 行中 的元素對(duì)應(yīng)的變量進(jìn)基？為使迭代后的基變量取正

10、值。,2、為何采用最小比值規(guī)則選擇進(jìn)基變量？為了使得迭代后的多偶問(wèn)題解仍為可行解（檢驗(yàn)數(shù)行仍為非正）,3、 原問(wèn)題無(wú)可行解的判別準(zhǔn)則：當(dāng)對(duì)偶問(wèn)題存在可行解時(shí)， 若有某個(gè) ，而所有 ，則原問(wèn)題無(wú)可行解，對(duì)偶 問(wèn)題目標(biāo)值無(wú)界。 因?yàn)榈趓行的約束方程即為： 其中 ， ，因此不可能存在 使上式成 立。也即原問(wèn)題無(wú)可行解。,2020/6/20,30,例、用對(duì)偶單純形法求解下述問(wèn)題,解 將問(wèn)題改寫(xiě)為目標(biāo)最大化，并化為標(biāo)準(zhǔn)型,2020/6/20,31,列單純形表,達(dá)到最優(yōu),2020/6/20,32,注意： 1、 使用對(duì)偶單純形法時(shí)，當(dāng)約束條件是 時(shí)，可以不必 添加人工變量。 2、使用對(duì)偶單純形法時(shí)，初始單純

11、形表中要保證對(duì)偶解為 可行解常難以做到， 所以一般不單獨(dú)使用，常與靈敏 度分析結(jié)合使用。,2020/6/20,33,6 靈敏度分析,靈敏度分析：線性規(guī)劃問(wèn)題中的某些參數(shù)發(fā)生變化，對(duì)解的影響。（C，A，b）,靈敏度分析的一般步驟： 1、 將參數(shù)的改變經(jīng)計(jì)算后反映到最終單純形表中； 2、 檢查原問(wèn)題和對(duì)偶問(wèn)題是否仍為可行解； 3、 按照下表對(duì)應(yīng)情況，決定下一步驟。,2020/6/20,34,一、C 的變化分析 C的變化只影響檢驗(yàn)數(shù)。,例、設(shè)有如下的線性規(guī)劃模型 試分析 分別在什么范圍變化時(shí)，最優(yōu)解不變？,2020/6/20,35,解：?jiǎn)栴}的最終單純形表如下：,2020/6/20,36,1、當(dāng) 變化

12、時(shí)，假設(shè) ，則要使得問(wèn)題的最優(yōu)解 保持不變，則檢驗(yàn)數(shù)行 即可，即要求,2、當(dāng) 變化時(shí)，假設(shè) ，則要使得問(wèn)題的最優(yōu)解 保持不變，則檢驗(yàn)數(shù)行 即可，即要求,2020/6/20,37,二、b 的變化分析 b的變化將只影響原問(wèn)題的基可行解，即最終表中的b列數(shù)值。,例、設(shè)有如下的線性規(guī)劃模型 試分析 分別在什么范圍變化時(shí)，最優(yōu)基不變？,2020/6/20,38,解：將 重新計(jì)算后填入問(wèn)題的最終單純形表：,1、當(dāng) 變化時(shí)，假設(shè) ，則問(wèn)題的解變?yōu)?填入下表，得,2020/6/20,39,要使得最優(yōu)基保持不變，則b列數(shù)值 即可，即要求,同理可得 的變化范圍是： 的變化范圍是：,2020/6/20,40,三、增

13、加一個(gè)變量的變化分析 增加一個(gè)變量，在方程組（矩陣A）中就要增加一個(gè)系數(shù)列，在原來(lái)的最終表中也要添加一列 ，檢驗(yàn)數(shù)也要計(jì)算，其余部分不受影響。如果檢驗(yàn)數(shù)行仍 ，則最優(yōu)解不變，否則繼續(xù)迭代尋找最優(yōu)。 一般分析步驟： 1、計(jì)算增加的新變量系數(shù)列 在原最終表中的結(jié)果 ； 2、計(jì)算新變量對(duì)應(yīng)的檢驗(yàn)數(shù) ； 3、根據(jù) 的符號(hào)判斷是否仍是最優(yōu)解，若是，最優(yōu)解不變；若不是，繼續(xù)求解。,2020/6/20,41,例、設(shè)有如下的線性規(guī)劃模型 現(xiàn)增加變量 ，其對(duì)應(yīng)系 數(shù)列為 ，價(jià)值 系數(shù) ，請(qǐng)問(wèn)最優(yōu)解是否改變？,解：最終表,2020/6/20,42,新變量的檢驗(yàn)數(shù)及系數(shù)列分別為：,填入表中，易知未達(dá)最優(yōu)，繼續(xù)迭代求

14、解。,2020/6/20,43,已達(dá)最優(yōu)。最優(yōu)解為 最優(yōu)目標(biāo)值,2020/6/20,44,四、增加一個(gè)約束條件的變化分析 增加一個(gè)約束條件，相當(dāng)于增加一道工序。 分析方法: 1）先將原最優(yōu)解帶入此新約束，若滿足條件，說(shuō)明此約束未起作用，原最優(yōu)解不變； 2）否則，將新約束加入到最終表中，繼續(xù)分析。,例、在上例中添加新約束 ，分析最優(yōu)解的變化情況。 解：因?yàn)閷⒃顑?yōu)解 帶入此約束， 不滿足約束，原解已不是最優(yōu)，繼續(xù)分析。,2020/6/20,45,6,x,2020/6/20,46,已達(dá)最優(yōu)。最優(yōu)解為 最優(yōu)目標(biāo)值,2020/6/20,47,7 參數(shù)線性規(guī)劃,參數(shù)線性規(guī)劃：研究參數(shù)連續(xù)變化時(shí)最優(yōu)解的變

15、化以及目標(biāo)函數(shù)值隨參數(shù)變化的情況。 注：當(dāng)多個(gè)參數(shù)同時(shí)變化時(shí)，可以引入一個(gè)參數(shù) 來(lái)表示這種變化。如：b列多個(gè)值發(fā)生變化時(shí)，可表示成 求解參數(shù)線性規(guī)劃的步驟： 1、 令 求解得最終單純形表； 2、 將參數(shù)的變化反映到最終單純形表中； 3、 找到使得最優(yōu)解不變的參數(shù)變化范圍，在臨界點(diǎn)處令參數(shù)增加或減少，分析最優(yōu)解的變化，并分析目標(biāo)函數(shù)值隨參數(shù)變化的情況。,2020/6/20,48,例：求解下述參數(shù)線性規(guī)劃問(wèn)題:,解：求得 時(shí)最終單純形表并將參數(shù)的變化填入表中 ：,2020/6/20,49,2、 是臨界點(diǎn)，當(dāng) 時(shí)， 所以選擇 作為進(jìn)基變量，迭代一步得到：,1、由表可知，當(dāng) 時(shí)，即 最優(yōu)解不變 。目標(biāo)

16、函數(shù)值 是：,2020/6/20,50,3、由上表可知，當(dāng) 時(shí)，即 最優(yōu)解不變 。目標(biāo)函數(shù)值 是,4、 是臨界點(diǎn)，當(dāng) 時(shí)， 所以選擇 作為進(jìn)基變量，迭代一步得到：,2020/6/20,51,5、由上表可知，當(dāng) 時(shí)，最優(yōu)解不再變化。 目標(biāo)函數(shù)值是,6、 是臨界點(diǎn)，當(dāng) 時(shí)， 所以選擇 作為進(jìn)基變量，迭代一步得到：,此時(shí)無(wú)論 如何增加，檢驗(yàn)數(shù)始終為負(fù)，最優(yōu)解不再變化。 目標(biāo)函數(shù)值是,2020/6/20,52,15,24,34,2020/6/20,53,例：某文教用品廠利用原材料白坯紙生產(chǎn)原稿紙、日記本、練習(xí)本三種產(chǎn)品，該廠現(xiàn)有工人100人，每天白坯紙供應(yīng)量限制是3萬(wàn)kg，如果單獨(dú)生產(chǎn)各種產(chǎn)品時(shí)，每人每天生產(chǎn)原稿紙30捆、日記本30打、練習(xí)本30箱。已知原材料消耗為每捆原 稿紙用白坯紙 公斤，每打日記本用白坯紙 公斤， 每箱練習(xí)本用白坯紙 公斤。又知每捆原稿紙可盈利2 元，每打筆記本盈利3元，每箱練習(xí)本盈利1元。試決定 （1）在現(xiàn)有生產(chǎn)條件下，工廠盈利最大的生產(chǎn)方案； （2）如果白坯紙的供應(yīng)數(shù)量不變，當(dāng)工人人數(shù)不足時(shí)可招收臨時(shí)工，其工資支出為每人每天40元，問(wèn)該廠要不要招收臨時(shí)工，最多招多少？,202