教案五線性規(guī)劃的對偶問題

教案五線性規(guī)劃的對偶問題教學內(nèi)容第四節(jié)線性規(guī)劃的對偶問題2.對偶單純形法教學學時7學時教學目標1.理解對偶問題的基本概念教學過程一、復(fù)習鞏固1.單純形法的基本原理(見課件)2.單純形解法(見課件)3.大M法(見課件)(1)對偶問題的基本概念(見課件)對偶現(xiàn)象每一個線性規(guī)劃都伴隨著另一個線性規(guī)劃，兩者有密切關(guān)系，互為對偶.其中一個問題稱為原問題，另一個問題稱為其對偶問題.兩者間只要得到其中一個問題的解，那么也就得到了另一個問題的解.下面通過一個實例來解釋對偶線性規(guī)劃的概念.例2-12以例2-1為例，我們討論了一個制藥廠的生產(chǎn)計劃的數(shù)學模型及其解法.現(xiàn)在假定該制藥廠決定在計劃期內(nèi)不生產(chǎn)藥品I、Ⅱ,而將生產(chǎn)設(shè)備的有效臺時全部租給某公司，那么該公司應(yīng)對設(shè)備A、B、C、D每小時付多少租金，才能使成本最小，而又能為制藥廠所接受?從租用設(shè)備的公司的角度考慮，一是所付的租金越低越好；二是所付的租金總額能使制藥廠接受，即租金應(yīng)不低于制藥廠自己生產(chǎn)該兩種藥品所得利潤，否則，制藥廠寧可自己生產(chǎn)，而不租給公司.設(shè)公司租用該制藥廠A、B、C、D四種設(shè)備的租金(元/小時)分別為y,、y?、y,和y?.在考慮租用設(shè)備的定價時，能使該制藥廠接受的條件是：公司租用該制藥廠用以生產(chǎn)每千克藥品I所需A、B、C、D四種設(shè)備的臺時的租金不應(yīng)少于200元，即2y?+y?+4y?+0y?≥200同樣，公司租用該制藥廠用以生產(chǎn)每千克藥品Ⅱ所需A、B、C、D四種設(shè)備的臺時的租金不應(yīng)少于300元，即2y?+2y?+0y?+4y?≥300公司在考慮自身利益時，其目標是使付出的租金總額為最小，即MinW=12y?+8y?+16y?+12y.于是，上面的問題可以用下列線性規(guī)劃的數(shù)學模型表示：MinW=12y?+8y?+16y?+12y?s.t.若把制藥廠利潤最大的線性規(guī)劃問題稱為原問題，則想租用A、B、C、D四種設(shè)備的公司的租金最小的線性規(guī)劃問題稱為原問題的對偶問題(dualproblem);反之，若把租用A、B、C、D四種設(shè)備的公司的租金最小的線性規(guī)劃問題稱為原問題，則制藥廠利潤最大的線性規(guī)劃問題稱為原問題的對偶問題.影子價格一般地，我們稱對偶問題的最優(yōu)解為原問題約束條件的影子價格，即對偶問題的解y,稱為第i種資源的影子價格.它并不是某種資源在市場上的價格，而是代表單位資源在最優(yōu)利用的條件下所產(chǎn)生的經(jīng)濟效果.為了和市場價格相區(qū)別，我們才稱它為影子價格.它在經(jīng)濟上是一個很有意義的數(shù)據(jù)，通過它我們可以知道，當增加某種資源時，可以使利潤增長的大小.另外，影子價格還給出了是否應(yīng)當購進某種資源以增加生產(chǎn)量，而獲得更多利潤的價格標準.(2)對稱的對偶線性規(guī)劃(見課件)如果一個線性規(guī)劃具備下面兩個條件，則稱它具有對稱形式：①所有的變量都是非負的；②所有的約束條件都是不等式，而且在目標函數(shù)是求極大值的情況，不等式具有小于和等于(≤)的符號，在目標函數(shù)是求極小值的情況，不等式具有大于和等于(≥)的符號.對稱形式的原問題和對偶問題叫做對稱的對偶線性規(guī)劃.原問題和對偶問題在形式上的對比如果我們把線性規(guī)劃稱為原問題，則必同時存在另一線性規(guī)劃問題，我們稱為對偶問題：用簡縮形式表示：原問題為對偶問題為原問題為MaxZ=CX對偶問題為MinW=Ybs.t.原問題與對偶問題之間的關(guān)系1)原問題是求目標函數(shù)的最大值，對偶問題是求目標函數(shù)的最小值.2)原問題約束條件的右端項變成對偶問題目標函數(shù)的系數(shù).原問題目標函4)原問題約束條件的每一行正好對應(yīng)于對偶問題的每一列，所以原問題中5)原問題中約束條件的每一列正好對應(yīng)于對偶問題的每一行，所以原問題6)對偶問題的對偶規(guī)劃正是原問題.例2-13設(shè)原問題為：MiW=2x,+5x試寫出它的對偶問題.(3)非對稱的對偶線性規(guī)劃(見課件)對于我們經(jīng)常遇到的非對稱形式的線性規(guī)劃，我們可首先將其化為等價的的對應(yīng)關(guān)系，將其化為對偶問題.實際上，我們在考慮對稱的對偶線性對稱的對偶線性規(guī)劃(dualofanonnormalLP)時，也可以按表2-13原問題與對偶問題之間的對應(yīng)關(guān)系，直接進行變換，得到原問題表2-13原問題與對偶問題間的轉(zhuǎn)換原問題(或?qū)ε紗栴})對偶問題(或原問題)目標函數(shù)MinW約束條件數(shù)：m個第i個約束條件為“≤”對偶變量數(shù)：m個對偶變量y,≥0第i個約束條件為“≥”第i個約束條件為“=”第j個約束條件為“≥”第j個約束條件為“≤”第j個約束條件為“=”限定向量b限定向量b系數(shù)矩陣A?例2-14可按表2-13的原則，將原問題直接轉(zhuǎn)化成對偶問題：MinW=20y?+10y?+5y?(4)對偶問題的基本性質(zhì)(見課件)1)對偶問題的對偶是原問題(對稱性質(zhì)).2)若x和γ分別是原問題和對偶問題的可行解，則CX≤γb(弱對偶性質(zhì)).3)設(shè)x和γ分別是原問題和對偶問題的可行解，當兩者目標函數(shù)值相等，即CX=γb時，X,γ分別是原問題和對偶問題的最優(yōu)解(可行解是最優(yōu)解的性質(zhì)).4)若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，且目標函數(shù)值相等(對偶性質(zhì)).5)若x和γ分別是原問題和對偶問題的可行解，則x和γ為原問題及對偶VX=0和γ=0其中，u=(ui,u?,…,um)”,ui,u?,…,un是原問題的松弛變量，γ=(v?,Vz,…,Vn),vi,vz,…,V,是對偶問題的剩余變量(松弛互補性質(zhì)).此性質(zhì)在線性規(guī)劃中有廣泛應(yīng)用.如從已知的原問題最優(yōu)解(或?qū)ε紗栴}最優(yōu)解)求取對偶問題最優(yōu)解(或原問題最優(yōu)解);驗證原問題的可行解是否最優(yōu)解等等.6)原問題的檢驗數(shù)對應(yīng)于對偶問題的一個基本解.由對偶性質(zhì)可知，在求解原問題的過程中，利用單純形表每一次迭代所得例2-15設(shè)原問題為：已知其對偶問題的最優(yōu)解為y=1.2,y,=0.2,=28,試利用對偶性質(zhì)求該問題的最優(yōu)解相應(yīng)的目標函數(shù)最小值W由松弛互補性質(zhì)可知，在最優(yōu)條件下，vX=0u?^y?^=0,u?`y,^=0,v,x?1=0,v,^x??=0,v?*x;1=0,v?*x?'=0;這解方程得x;=x?=4綜上所得，原問題的最優(yōu)解為x*=(0為z*=28.1)若原問題可行，但有無界解(或稱無有限最優(yōu)解),則對偶問題不可行；若對偶問題可行，但有無界解(或稱無有限最優(yōu)解),則原問題不可行；2)若原問題可行，而對偶問題不可行，則原問題有無界解(或稱無有限最優(yōu)解);若對偶問題可行，而原問題不可行，則對偶問題有無界解(或稱無有限最優(yōu)解).2.對偶單純形法那么根據(jù)對偶問題的對稱性，我們也可以這樣來處理：保持對偶問題的解基本可行解.這樣，也使原問題和對偶問題都達到了最優(yōu)解.事實上，對偶單純形法(dualsimplexmethod)并不是解對偶問題的單純形法，而是應(yīng)用對偶原理來求解原問題的最優(yōu)解的一種方法.(1)對偶單純形法的要點(見課件)例2-16用對偶單純形法求解下列線性規(guī)劃問題s.t.解此問題可用大M法去解，但用大M法求解很麻煩，現(xiàn)在用對偶單純形法求解.先將原問題化為標準形式，為此引入剩余變量x,xs,令z=-W,得.t.然后將約束條件等式的兩邊都乘以(-1),得到MaxZ=-1600x?-2500x?-400x建立這個問題的初始單純形表，見表2-14:表2-14對偶單純形法求解例2-16(1)b00解為x=(000-4-3)’,它是一個不可行解.而全部檢驗數(shù)c,-z,≤0,的迭代是在保持檢驗數(shù)小于等于零的條件下，逐步使x,≥0,j=1,2,…,5.為了1)首先確定換出變量：選擇具有負數(shù)的基本變量中絕對值最大的基本變量為換出變量.2)確定換入變量：用換出變量那一行具有負值的系數(shù)分別去除同列的檢驗則原問題無可行解.3)把換出變量的那一行除以樞元位置的系數(shù)，使樞元位置變?yōu)?.(2)表解形式的對偶單純形法(見課件)按上述迭代的要點，對表2-14繼續(xù)運算，見表2-15.表2-15對偶單純形法求解例2-16(2)-1600-2500-40000b00θ-40040θ-400-2500X?θ-16001-2500X?2-5若對應(yīng)兩個約束條件的對偶變量分別為y,和y,,則對偶問題的最優(yōu)解為y*=(20060000200),最優(yōu)值=2600.(3)對偶單純形法的優(yōu)點及用途(見課件)1)初始解可以是非可行解，當檢驗數(shù)都是小于等于零時，就可以進行基變換，這樣就避免了增加人工變量，使運算簡化.再用對偶單純形法求解，簡化計算.在上述討論線性規(guī)劃問題時，假定a。,b,,c,都是精確的數(shù)據(jù)，然而在大多數(shù)實際問題中，這些系數(shù)往往是估計值和預(yù)測值，而且它們也隨著某些條件的變化而變化.因此很自然會想到，當這些系數(shù)中的一個或幾個發(fā)生變化時，已求得的規(guī)劃問題的最優(yōu)解會發(fā)生什么變化?如果最優(yōu)解發(fā)生了變化，又怎樣用最簡單的方法找到新的最優(yōu)解?這就是線性規(guī)劃靈敏度分析(sensitivityanalysisofLP)的任務(wù).(1)單純形法的矩陣表達式(見課件)設(shè)有一線性規(guī)劃問題，用矩陣表示為MaxZ=CX列向量，0為n×1列向量.現(xiàn)引入松弛變量化為標準型MaxZ=CX+0Xs,0有m+n個元素.如果我們把系數(shù)矩陣A分為兩塊，A=(B,N),B也稱基矩陣(即原始系數(shù)于是線性規(guī)劃問題可以寫成MaxZ=CnX+CxXx+0X;在單純形法的每次迭代中，是用行變換的方法將基矩陣變成單位矩陣.用矩陣方法，則將上述約束方程的兩邊乘以基矩陣B的逆矩陣B-',于是可得X=B~1b-B-'NXx-B-'Xs將式(2-11)代入目標函數(shù)可得Z=C?B-b-C?B-'NXv-C?或者z+(C?B-1N-Cx)Xx+C?B1Xs=C?B-1b(2-13)從式(2-9)可知，在單純形表每次迭代后，每個變量的系數(shù)列向量是B的逆陣B'乘以該變量的原始列向量而得到的，右端常數(shù)的列向量是B的逆陣B-1乘以右端常數(shù)的原始列向量而得到的.從式(2-10)可見，其松弛變量的系數(shù)矩陣正好是基矩陣的逆陣B-'.更一般地理解，在任一單純形表中相應(yīng)于初始基本例如第二章第三節(jié)的例2-8中，表2-4、表2-5、表2-6和表2-7給出了單純形法的計算過程，其中表2-7為最優(yōu)解單純形表，其基本變量是x,x,,x。和x,.對應(yīng)于表2-7的基矩陣對應(yīng)于表2-7的b列向量是對應(yīng)于表2-7的非基本變量的檢驗數(shù)是C、-C。B-'n,松弛變量的檢驗數(shù)(2)系數(shù)變化的靈敏度分析(見課件)系數(shù)變化的靈敏度分析是在決策變量和約束條件數(shù)目不變時，研究各種系化時，已得到的最優(yōu)解保持不變，或者最優(yōu)解的基本變量保持不變(但數(shù)值有所改變);二是如果某些系數(shù)的變化引起最優(yōu)解的變化，如何用最簡便的方法求出因為C,=c;-Z,(j=1,2,…,n)(式中c,是基本變量的成本或利潤系數(shù))新的檢驗數(shù)C':C'=c,+△c,-Z,=C,+△c 例2-17以例2-8的最終計算表(表2-7)為例.設(shè)基本變量x,在目標函b0X?00040x?14300+△c,x?020+2△c;b′=B-(b+△b)=B~`b+B?1△b=b'+B~1△b≥0所以△b,在[-8,0]之間變動時(即b,的變化范圍在[8,16]時),原來最優(yōu)解,最優(yōu)值z=1375,表2-17右端常數(shù)變化后的最優(yōu)解見表2-17.bθ0x?007-20x?13X?09-40如果△b,的變化超出了[-8,0]的范圍，這時最優(yōu)解的基本變量就發(fā)生變化.在這種情況下要用對偶單純形法繼續(xù)求出新的最優(yōu)解則最終單純形表變?yōu)楸?-18.表2-18右端常數(shù)變化后的對偶單純形法求解C?bX?0000X?15X?00Z=1425θ0240X?4X?122新的最優(yōu)解x*=(420024)',最優(yōu)值Z=1400.矩陣A中的系數(shù)改變對最優(yōu)解的影響當對應(yīng)于P,的變量x,為非基本變量的系數(shù)時，它的變化不會改變基矩陣B和它的逆陣B-',所以只需修改單純形表中所對應(yīng)x,的列就可以了.P;=B~1P若極大化問題C;≤0,則得到的還是新問題的最優(yōu)單純形表，最優(yōu)解和最優(yōu)值不變，否則可用單純形法求解.當對應(yīng)于p,的變量x,為基本變量的系數(shù)時，它的變化會改變基矩陣B和它的逆陣B-1,所以會影響到最終單純形表的右端向量和非基本變量對應(yīng)的列.下例2-19以例2-1為例，若計劃生產(chǎn)的藥品I的工藝結(jié)構(gòu)有了改進，相應(yīng)地生產(chǎn)單位藥品I所需設(shè)備4、B、C、D的臺時改為(3,2,5,2),它的利潤也提高到每千克400元.試分析已求得的最優(yōu)計劃有何變化?解當x,的系數(shù)列向量變化后，原最終單純形表(表2-7)中x,的系數(shù)列向原最終單純形表變成表2-19:表2-19決策變量系數(shù)改變對最優(yōu)解的影響(1)C?bX?0x?00040x?14X?3-802由x,的系數(shù)列向量可知，到此尚未完成行變換，所以需繼續(xù)使x,的系數(shù)列向量變成單位列向量，于是得到表2-20.表2-20決策變量系數(shù)改變對最優(yōu)解的影響(2)bX0X?000x?1x?0 =1520元.4.線性規(guī)劃在衛(wèi)生管理中的應(yīng)用(1)放射科的業(yè)務(wù)安排(見課件)A醫(yī)院估計今后放射科如果開展此3項業(yè)務(wù)，在現(xiàn)有放射科醫(yī)務(wù)人員力量和病人需求的情況下，每月此3項業(yè)務(wù)的最多提供量為1800人次.平均每人次檢查時間、每月機器實際可使用時間、平均每人次檢查利潤如下表2-2