1、第四章 線性規(guī)劃的對偶問題 4.1 對稱的對偶規(guī)劃 在線性規(guī)劃早期發(fā)展中,對偶問題是一項重要的發(fā)現(xiàn)。早在1928著名數(shù)學(xué)家John.Von.Neumann在研究對策理論時就已經(jīng)有原始和對偶的思想。 對偶理論有著重要的應(yīng)用。首先是在原始和對偶兩個線性規(guī)劃中求解任一規(guī)劃時，會自動地給出另一個規(guī)劃的最優(yōu)解。當(dāng)對偶問題比原問題有較少分量時，求解對偶問題比求解原始問題方便得多。對偶理論另一個應(yīng)用是Lemke，1954提出的對偶單純形法。 對偶理論對影子價值的分析在經(jīng)濟理論上有著重要作用。,音絡(luò)綠怎歌頂瀉堯淳捍眠可彼楔項凍堿常隊義茹嬸界費達搓澇淮茫撻娠茨中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中

2、南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,一 對偶問題的提出: 例:某廠生產(chǎn)A.B.C三種暢銷產(chǎn)品,每臺產(chǎn)品需四種資源,具體數(shù)據(jù)表：,問怎樣安排生產(chǎn),效益最大？,設(shè)決策變量 得出模型:,屈威訛藝掠頃斃臣航做膛翔鵬怒佯疇歉幻安焦衷簡中俘杖衛(wèi)爺食俘錄煎挖中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,現(xiàn)在工廠考慮不進行生產(chǎn)而把全部可利用的資源都讓給其它企業(yè)單位,但又希望給這些資源訂一個合理價格,既使別的單位愿意買,又使工廠能得到生產(chǎn)這些產(chǎn)品時可以得到的最大效益.,這就需建立另一個線性規(guī)劃模型,設(shè) 代表銷售這四種資 源的價格，買方希望總售

3、價盡可能低,即：,原來生產(chǎn)產(chǎn)品A每臺需用的資源按現(xiàn)在的單價計算,每臺收益為:,嶺逢稿花咒莊饞悉淘蓋崇賬仟發(fā)苔址秀辣記緯掂慨緞島飛氰啪擬益帆乒覺中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,易見,后一個問題的數(shù)據(jù)完全由另一問題數(shù)據(jù)確定. 對每一個線性規(guī)劃問題都伴隨有另一個線性規(guī)劃問題,即：,都伴隨一個對偶規(guī)劃(LD)。,定義1:對應(yīng)著每一個(LP),都存在著線性規(guī)劃問題(LD),其中 是m維行向量,稱(LP)為原始線性規(guī)劃，稱(LD)為(LP)的對偶線性規(guī)劃。,因此得到的線性規(guī)劃問題模型如下:,捂韭泌碳稀蝗倦花囑屑魯滔峰甲高沈紀可甸獻碳紫豹

4、雞盧遞力琳彬惰畫超中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,下面進一步探討(LP)與(LD)之間的關(guān)系：,其對偶問題: (LD),(LP),廄呆禮粘搗潛賦簍攔旦寧涼憋闌娶恢蛤盾吧壽氟某賂筋擴兢剝讓纂炎羅謙中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,用下表表示二者之間關(guān)系,更為清楚:,對偶線性規(guī)劃問題一定要有一對線性規(guī)劃問題，沒有一個“對偶”的線性規(guī)劃問題，也就無所謂“原始線性規(guī)劃問題”如果沒有原始線性規(guī)劃問題，也就無所謂對偶線性規(guī)劃問題了。,癥致鱉滁紉災(zāi)枚想彌友矢拼宏拾遷隊廄顧

5、稽縣芭老長漁飽丑唯菱麻徹恩坑中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,線性規(guī)劃的對偶關(guān)系具有“對合”性質(zhì),什么是對合性質(zhì)呢?,可見，（LP）與（LP）是同一類型的問題，依照定義1，又可寫出（LP）的對偶線性規(guī)劃。記為（LD） （LD）,灸輔卓難霞幕學(xué)炊遇從昂位衷孜友括尊淬秧吳耪澄瓢遺沈靖旭農(nóng)灑詞盡珊中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,（LD） 又可等價地寫成：,既（LD）就是前面的（LP） 這表明，對于一個給定的（LP）可以根據(jù)對偶規(guī)則寫出（LD）；而對于新問題（LD）

6、，又可根據(jù)對偶規(guī)則寫出其對偶。而此對偶又剛好回到原問題本身。即（LP）的對偶是（LD） ，（LD）的對偶是（LP）。,這就是線性規(guī)劃對偶關(guān)系的“對合”性質(zhì)。這樣我們可以把一個相互對偶的線性規(guī)則中任何一個稱為原問題，而把另一個稱為對偶問題，稱它們互為對偶。下面我們舉例說明怎樣由一個規(guī)則寫出其對偶問題。,綿膠痹惟寇乓慚襟盂耳島廟造臆聾走臭籃若彰謀學(xué)誡委廊氦獄味費徑尸嗜中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,解：因目標函數(shù)最小化，故先把約束條件都寫成“ ”形式：,娠憐廠骸穗聾療盧變涪貼歇床勃賠似娜料沮猜豆姜澎須狽跟暫蹄崩賓樁摸中南大學(xué)數(shù)學(xué)

7、院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,由于這是個（LD）問題。故其對偶是（LP）問題。,對偶函數(shù)目標系數(shù)由給出的（LD）約束右端列向量（-7，14，3) 可得，對偶的約束方程右端常數(shù)，向量由（LD）的目標函數(shù) 系數(shù)向量（5，-6，7，1）可得，從而寫出（LP）問題：,長立坐穩(wěn)署咽傾憑炕布苗抿雖壟飄勁下把倦效藐滬謝純箱匿巢牧拋幾蔫巖中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,所以把它們稱為一對對稱的對偶規(guī)劃。 下面來討論它們的關(guān)系。,二 （LP）、（LD）的對偶定理 定理1 對于（LP）

8、的任意可行解x 及（LD）的任意可行解 u 有 c x u b 。 證： 因 x 、u滿足： A x b , x0 （1） u Ac u0 （2） 用u左乘（1），x右乘（2）的： c xu Axu b 故c xu b 。,由于（LP） 與（LD） 形式上是等價的,妙史踏仲漫袖律踩犬桂絨肇肄珠彌其甄訖閏孺硒邯筷蠅聶擅毗燥纓駿膊呆中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,定理1 給出了（LP）（LD）這對互為對偶的線性規(guī)問題目標函數(shù)的一個界限。若（LP）有可行解x，則（LD）的目標值u b就有了下界c x；反之，若（LD）有可行解u，則

9、（LP）的目標值c x就有了上界u b。 推論： 若（LP）有無界解，則（LD）無可行解。 若（LD）有無界解，則（LP）無可行解。 證： 只證前面，后面一樣，反證法。 若（LP）有無界解，而（LD）有可行解u0， 而根據(jù)定理一，對（LP）的任何可行解x，c xu0 b 這與（LP）目標函數(shù)無上界矛盾。 注： 這個推論的逆不一定成立。 即一對對偶問題中有一個無可行解，不能判定另一個有無 界解。,倆香舀墟畔翅匡撫務(wù)賀圓幅焰癡謎首忻駛氨菏出絢緣力芽壞砸指羽耀追狐中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,例： （LP）,（LD）,上面（LP

10、）無可行解，而（LD）并沒有無界解，而是無可行解。,行英而藏窮蘑警臂護攤凰駛狼堪集嘛蜀蓋餃喻橫瑟苞漁懈喧弄四奄辱捧簧中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,定理2：,證明：,具拘折或惦迂姓菏泡濺較輝訛奇協(xié)久萊吐悄諧柱需斧萍獎輥貧打?qū)掦@燦并中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,證明：,推論2,姥粉絮旬詢撐擻漸緩扣油斜瞅祖扁瞪與姐贈濾僵財點佛媒噓凳代恕您鴛串中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,這樣（LP）就化

11、成了等價的（*）問題。 由于假定（LP）有最優(yōu)解，則（*）亦有最優(yōu)解。,斑孽粉盜軒豁廊迸誰誨恿簧逝蚌姥毆囑客負沈段壯毒嘔汁弘聞亨卡軌鵲約中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,潰嚴敝啡蒙破晶宦義只烘米攝超別國柒犀隴古逐祭羊冀象掙很貶毆依忙寇中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,焚燕話宇彌角憐完儈槳恿索詩譴扶怎鑼刀陛敗賺棱價耗魔蔗痰惋憎氨漆勺中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,有,定理4,證明：,噬驟把午毋

12、墮正趣業(yè)雙值販站極銳步蔑彬氏勁汲閘闡曾積悸把仁轟銹份釣中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,證畢,由此可得如下松緊關(guān)系：,沈華甄韭堰需話符瑯休賠鍵綱鰓訴羞并靜遂籽塞睦甜丟篷混鹽巋平勇等瞬中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,噎嘶曉毀攔弊符好裂李俊炎繕擾折萊豢米扼加輕恐螞鎢斃咱醉酗猾擅覺歲中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,對偶松緊關(guān)系又稱為互補松弛條件。 下面通過一個例子說明對偶松弛關(guān)系：,例,（LP）

13、,引進松弛變量 ，（LP）化為：,翌或冕鋼閣貫裙碉剩救剃溉妮互郭奪擺謄聶綽渙垃痊袱阻肆毆波若斤堪焦中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,得（LP）的最優(yōu)解,陶恕葡疥軋的鯨掀欄采侯電跑佰嘔脂隘捆戀孟閩獵瘁淘鋤蠟傣棒六瞞娩觀中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,雹敬舒殖沃樟控神蘊咆異藹笛上沃拌薯莫夾伊狀坑謅娘假注忿畏昂帛賜斂中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,又,撇首騁徘遣絨勞滴半礬渠洽補償裸寡未族左侮滄俐

14、豹延抵悼換日絨蓬料拄中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,可見，用單純形法迭代的到（LP)最優(yōu)解時，對偶(LD)的 最優(yōu)解 可以直接從（LD)的最優(yōu)單純形到表上得到。在問題的松弛變量 （y1，y2)的檢驗數(shù)就是對偶(LD)的最優(yōu)解。 這個結(jié)果對一般情形也成立。下面予以證明。,蜘硬媚茅鼻楚秦助勒賊砌刮壬獨盔秸梢柄皋茬撥惑汾鄭俗荔千雞移鉛赴雙中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,用單純形求解。得到一個判別數(shù)全非負的最優(yōu)基本解。對應(yīng)松弛變量yi的判別數(shù) 又 yi在目標函數(shù)中

15、系數(shù) pn+i為第i分量為1的m維單位列向量。(i=1m)且,一對相互對偶的線性規(guī)劃（LP）（LD）之間解的可能構(gòu)形有 哪些？這可用對偶定理來回答，因為（LP）（LD）都單獨分 別有三種可能：,燦睛脾烷陌行陜箭顱深磐滓更愁猖碰景修瑚邏臆救喉裂遲遷尿秦旗沿掙萄中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,綜合以上對偶定理知：（LP）（LD）之間只可能有下面三種情形： （1） 兩者都有最優(yōu)解。 （2） 兩者都沒有可行解。 （3） 一個問題有無界解，另一個問題沒有可行解。 其他情形都不可能出現(xiàn)了，因為，一個問題有最優(yōu)解，另一個問題有無界解，或一

16、個問題有最優(yōu)解，另一個問題無可行解，將與定理3矛盾。 如果兩個問題都有無界解，將與推論1矛盾。,弱低呸陀她矚湊黃胖屯刻啃貧乘瞅旺振廈塌茲姚酪逾摸氖泵抖窗蜜詠蘋螞中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,4.2 非對稱及混合型對偶規(guī)劃,一 （SLP）的對偶規(guī)劃：,在單純形法中，我們總是先將（LP）問題化為（SLP）求解，因此，有必要研究（SLP）的對偶規(guī)劃問題。,先將（SLP）：,改寫成（LP）,再根據(jù)（LP）的對偶定義寫出其對偶規(guī)劃：,孩址硒拓羌壤豺潤酮哲衙鑲蛙謠側(cè)幼秦后頭怪趟悟申竄阿鋪筋罪構(gòu)鉚側(cè)坯中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性

17、規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,(LD),這就是(SLP)的對偶線性規(guī)劃，這一線性規(guī)劃問題還可進 一步簡化。引進m維行向量u ：,那么u就不一定有非負約束了。于是將上面（LD)寫成：,（SLD),u無限制,疑基漲咯度茲泛天速堯蛋劃荊初嘆揭造拳峪練祿茨藥粵婦舞帝點董趨枷匡中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,(LP)（亦即(SLP) 的對偶是(LD)亦即(SLD) 。而 (LP)與(LD)是對稱對偶規(guī)劃，具有對合性。即(LD)也就是(SLD) 的對偶是(LP)(亦即(SLP)）。故知: (SLP)與

18、(SLD)這對對偶 規(guī)劃也具有對合性質(zhì)的。,二 (SLP)、(SLD)的對偶定理： 下面我們考察前面已證明的關(guān)于(LP) (LD)的一些定理，考 慮是否對(SLP) (SLD)也成立。 定理1 對(SLP)的任意可行解x，(SLD)的任意可行解u 。有：,證明：,程吶守早鈍膨蟬緩寸伺拋拷瑣足窖拯庸慌蒲僳竣妊補篩丫現(xiàn)曉幌車嚏勸儡中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,推論1：若(SLP)有無界解，則(SLD)無可行解；若(SLD) 有無界解，則(SLP)無可行解。其逆不成立。,定理3：若(SLP),(SLD)中一個有最優(yōu)解，則另一個也

19、有 最優(yōu)解，并且兩者的目標函數(shù)值相等。,推論2：若x*，u*分別是(SLP),(SLD)的可行解，且cx*=u*b。 則x*,u*分別是(SLP),(SLD)的最優(yōu)解。 （這些結(jié)論的證明與(LP),(LD)類似結(jié)論證明一樣）,定理2：對偶(SLP),(SLD)有最優(yōu)解 兩者同時有可行解。,酥朱弱粟波仔最骨烘裕搪扶蛛悸軒岸塞邢鹼生炔匿卒拇諄抿耗岳喀秧搶汐中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,根據(jù)第一節(jié)的定理3知，(LP)即(SLP)有最優(yōu)解。 故得證。,并且目標值 根據(jù)上面的推論2即可知： 因此我們證明了若(SLP)有最優(yōu)解，則(S

20、LD)必有最優(yōu)解。 反之，若(SLD)有最優(yōu)解u*,則,是(SLD)的最優(yōu)解。,茶寓叉詞雛酪煙源華墾廬錐參錘鉆凈顆啥嚴斗筏謂幟螟弟盼只樹相種沈梁中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,我們由上面定理證明過程可見：若B*是(SLP)的最優(yōu)基，那 么單純乘子 就是(SLD)的最優(yōu)解。因此我們定義： 定義2：對于(SLP)的一個基B，若單純到乘子 為對 偶(SLD)的可行解，則稱B為對偶可行基。 若 為對偶(SLD)的最優(yōu)解，則稱B為對偶最優(yōu)基。 上面定理3的證明表明：(SLP)的最優(yōu)基B*必是對偶最優(yōu) 基。這個結(jié)論在后面的對偶單純形法迭

21、代中將是十分重要。,定理4：(SLP),(SLD)的可行解x*，u*分別是最優(yōu)解,乾鄧朽娟債繳距哼裝趁惑姜彎簾拋染竅損工賜虹彭值偏瀾翹圍揍肖泰共好中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,我們下面再細看一下這里的松弛條件：,濘羊灼聾曹秤窖兌獨味愛乓獰貝跡供帽圾酷諜役凱茲考映蒸潰九陸盡康嗓中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,從而得出如下的松緊關(guān)系： （1）若(SLP)有最優(yōu)解x*，使得對指標j滿足x*j0，則稱j對 （SLD)是松的。對(SLD)的一切最優(yōu)解u*就必有u*

22、pj=cj 稱j對(SLD)是緊的。 （2）若(SLD)有最優(yōu)解u*,使前對指標j滿足u*pjcj.則稱j對 (SLD)是松的。對(SLP)的一切最優(yōu)解x*就必有xj*=0，稱j對 (SLP) 是緊的。 從上述對偶定理知：(SLP)，(SLD)這一對對偶規(guī)劃的解之間也有下面三種情形： （1） 兩者都有最優(yōu)解。 （2） 兩者都沒有可行解。 （3） 其中一個有無界解，而另一個無可行解。 除此之外，不能再有其他的形式了。其理由與4.1一樣。,俊帛溝低戈灸頹膿晴棘沉仕恤簍漿寢琢忘糠策菜溯它搔位淋友榨劫攪庭旦中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶

23、問題,上面我們已經(jīng)討論過了對稱及非對稱型對偶規(guī)劃。但實際問 題中會出現(xiàn)兩種情形共存的問題，即所謂混合型的對稱規(guī)劃問題。 定義:對于一個線形規(guī)劃問題,若它的約束包括兩個部分,一部分的約束是方程式 ，另一部分約束是不等式 (或 ) ,其變量也分兩類, 其一類有非負限制,另一類沒有限制，稱這種類型的問題為混合型問題。 考慮混合型問題：,(I),三 混合型對偶線形規(guī)劃,封顆首肆宿草剩巷骨漸它翁棱呻魚寓假曼歉坎醛輾錄拷行忱酞康猙蛀蒸籠中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,.,庭澗旗湖碑臨毖艾祭制茸淮阜陛蝗逛生們志廷躬賈孰飛震少豫景維依烏騰中

24、南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,愉吱百丁鰓緞轟迫糙躺屋胸搶曙縷痕庫戍雪攬溯做玉櫻剖函雍迅悅尼湛糯中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,根據(jù)上面求混合型對偶規(guī)劃過程，我們總結(jié)出混合型對偶 的特點如下： （對偶表）：,桃醋壁屈鈣同署啼淋孩旦同胰碧卿棵酬好途柞壹中陪千贖咕慘弛旋疼乾課中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,例：寫出下面線性規(guī)劃的對偶規(guī)劃：,（1）,（2）,澳彬搶脂刪娥刀錢宣許摟賈剔畦鍬炬醞茂隋

25、每鞋淑徑輪恐熊賈苞蔡而系偶中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,杖者蛻漏夢傲樂吠俘荊沛覽掠車圃咆敲銷混邀淬碉凄畔橫塢倚痛字復(fù)椒砒中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,注意：（1）寫出的對偶問題，其系數(shù)矩陣必須是原問題的系數(shù)矩陣的轉(zhuǎn)置。 （2）寫出對偶的前一步，問題統(tǒng)一化形式是必須的，否則容易出錯。,漲亭畏紡鍍責(zé)秦伍字煮翔桐蓉肘擒沈返盈昭停哪商泅繞咽告惠當(dāng)獸辣晃弦中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,桅拭速

26、淹吟廄椿匿終爺吏樸蹭煤湊危全艘垢潭晴夷烘才碘鎬熔打矛箭醋揪中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,例2 用對偶定理證明，下面兩個問題不能同 時成立： （1）,(2),證明：構(gòu)造一對對偶線性規(guī)劃問題：,(LD),（LP),讀孝驅(qū)裸衍七俺豪濕辭餞傈鉆爆皺儲恐給預(yù)邪感引菜鴨飲跡滿汁診拌樟維中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,（LP),故（1）成立時，（2）不可能也成立。 反之，若（2）成立時，同樣不可能有（1）成立。,旁凰拙磊機鳳渡雜晝糊擴粕千癌挨閣頑卵杜揮沏托維窒瘴洗抽淌

27、嘴吟伎槍中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,途城酌咀鈴菱莖釋蔥隊耿宵雹目拍付賜嗡閉撓創(chuàng)溫劍躇放許鼎板默葵窯抱中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,某囚壞劣棕坤荷傘兆彈破播攏睜吩失奪旬?dāng)渴麠Ｐ由t媚盎吁默從涼河臼中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,若 有解。即(SLP)有可行解。而對此(SLP),其 任意可行解也是最優(yōu)解。根據(jù)對偶定理3，知(SLD)也有最 優(yōu)解u， 反之，若 且對滿足 的任意u，有 表

28、明（SLD)有可行解，且目標值有下界。因而此(SLD) 有最優(yōu)解。根據(jù)對偶定理3，即可知：(SLP)也有最優(yōu)解x， 滿足：,例5：利用對偶定理證明Farkas引理： 有解 有解，且對滿足 的任意 u必有 。其中A是 矩陣，b是m維列向量。 證明：構(gòu)造一對對偶規(guī)劃向量如下：,至抑俏歧詹訃樸勞豈漓排泛蜂蚌紋飼閱萍歹謾瀉句說拋貸巳湊災(zāi)頓礦羅仔中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,（LP),(SLP),(LD),SLD),渺境肢巨廄追碧屈妒想毯幻隆笛內(nèi)虐活隔崖取去變妻賠叭蹋頁訓(xùn)摹望纂佃中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南

29、大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,從而,反之，若存在u，使c表成（*）式。則（LP)有可行解。即 （SLP)有可行解。又已設(shè)(LD)有可行解。即(SLP)有可行解 根據(jù)對偶定理2 。即知：(SLD),(SLP) 均有最優(yōu)解。從而 （LD)有最優(yōu)解。 設(shè)上面A1.Am是A的行向量。,我們將原來的一對（LP),(LD)等價的化為如上所示的一對 (SLP),(SLD)。這樣(LD)有最優(yōu)解等價與(SLD)有最優(yōu)解。 有根據(jù)對偶定理3（SLD)有最優(yōu)解等價于（SLP)有最優(yōu)解。 而（SLP)有最優(yōu)解等價與(LP)有最優(yōu)解。 因此，若（LD)有最優(yōu)解等價于(LP)有最優(yōu)解u。從而,翼殖貫錯

30、殃忿怪響律茅友緝啊撅絨辮曰宴肆呂霍法裝柞給腦漸衣捏阜薊繁中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,4.3 對偶單純形法,一 什么是對偶單純形法,問晰亭船莊稀嫉籌吧舍低禮牢軌檔阿刷秸坤副信潛柜奔廈劊市焙磅歐薪卒中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,沿這一途徑求得(SLP)的基本最優(yōu)基的方法，稱為對偶單純 形法。,二 對偶單純形法的迭代原理 用對偶單純形法求解(SLP)，起始于一個對偶可行基B：,與單純形法一樣，對偶單純形法也要找出一個樞軸元 來進行旋轉(zhuǎn)變換，因而我們可以直接

31、用單純形法中的逐次迭代公式即：,捧括除掇吉抑村腿礙澈除賃滓加房脫涵竟稗熏產(chǎn)粉絲篙竿癰嘔顏媽騁塑隆中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,2 入基、出基變量選擇：單純形法中先定入基變量 即先定k，后定出基變量 ，即后定l ;而對偶變單純 形法中，先定出基變量l，后定入基變量k.,3 表格形式中數(shù)據(jù)：單純形法中 ， 總是非負的，逐次迭代，減少檢驗數(shù)行中負元素的個數(shù)； 對偶單純形法，檢驗數(shù)行中的元素總是非負的，逐次迭代，減少基變量 取值中負元素的個數(shù)。,這樣，由于單純形法可以在表上進行，對偶單純形法也可以在表上進行。當(dāng)然，兩者并不是完全相

32、同的，而有各自的特點。 我們分三點討論： 1 樞軸選擇：單純形法中要求 ，對偶單純形法中要 求,糾稽就纜見腑蓄綜睫箋廖鑄混懈平潦帽豪備繪燦肇?zé)胛蒗r發(fā)奸企揪蘇睡曉中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,當(dāng)我們了解了對偶單純形法和單純形法之間這些關(guān)系以后，我們就可以具體研究對偶單純形法。考慮以下幾個問題：,（2）怎樣選取樞軸元 為使變換后的新變量 不再取負值，應(yīng)使,蔫售棲醛局甚拍載悲毛瓷淬饒咒棋饞往簿箔鈔蝎涉掂燼咯難酸螢聲安術(shù)妮中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,(3)入

33、基變換 的選?。?因?qū)ε紗渭冃畏ㄊ峭ㄟ^對偶可行基的迭代，所以迭代后所有檢驗數(shù)非負。即 根據(jù)迭代公式 因 時 因此選取 則確定 為入基變量.,膩頓假碰忱弧夏區(qū)餅嘉岡功顫詩呆瞞恰蠱逆遂刨亮礦脊京滇牽利墨爬丈銑中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,（4）目標函數(shù)迭代公式： 由于對偶單純形法的迭代并不是在（SLP)的可行基上進行的，因此考慮(SLP)的目標函數(shù)迭代沒意義，而應(yīng)考慮對偶目標值的迭代公式。若迭代后對偶可行基為B,故 是對偶可行解。 設(shè)對偶目標值為 ,則,設(shè)迭代后對偶可行基為 ，對偶目標值為 ,則：,夷籬當(dāng)兩家遮大時是停完街腔悠

34、咐耀懈謾略闖署喀躊役諒恃髓簍別夫唬雛中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,與 做內(nèi)積： 其中 是新基變量的取值,根據(jù)單純形法的迭代公式：（3.2.13）,可見，對偶單純形法迭代后必將使對偶目標值減少。剩下的問題就是要考慮對偶單純形法的終止準則。,因,娠序肋態(tài)輝爵亢藐梁逐事昆掀舟靖攢穩(wěn)欄褒戈燒汞恐碎九立掣技犁場臺亭中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,定理4.3.1 設(shè)B是(SLP）的一個基（或是一個對偶可行基），且 中有負分量，即 若第s行中的所有系數(shù) 則(SLP)無

35、可行解。,若對偶單純形法中基變換 ，則B是最優(yōu)基，得到最優(yōu)解。終止。,因此，對偶單純形法的終止準則是：,涉迭業(yè)鮮北帆倒實灘狐絮畔船迅緣癡脅霓齡援取囑渤動綢佳驗瑰份焰懇念中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,定義4.3.1：若對偶可行基B對應(yīng)的所有非基變量判別數(shù) ，則稱對偶可行解 是非退化的對偶可行解。否則是退化的。,恥基威淆韓眷蟄柳軸鼎哉亭株碼影唯卯星擁廓部逛廊顯拂香刻砸怨做毗椽中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,這表明每迭代一次對偶目標函數(shù)值必然減少，所以迭代過程

36、中對偶可行基不會重復(fù)出現(xiàn)，而對偶可行基的數(shù)目是有界的。對偶單純形法是在對偶可行基上進行的，因此必須在有限步內(nèi)完成。否則，若迭代過程是無限的，就必然會出現(xiàn)兩次迭代有同一個對偶可行基的情形。此時，它們對應(yīng)的對偶單純形法目標值相等。這是不可能的。這樣就證明了對偶單純形法經(jīng)有限次迭代后或者判斷(SLP)無可行解，或者得到(SLP)的最伏基本可行解，因而對于對偶可行解非退化的情形，對偶單純形法必在有限步內(nèi)終止。,郊誡絢辨亥字饑梢昨曲喀撻夠能故僻府精場童鷹量鎂隔商鬃慨碳薔樸那念中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,步驟2 如有： （否則（SL

37、P）無可行解，迭代中止。）可定出k:,步驟以為樞軸元進行樞軸運算，用公式,三 對偶單純形法的迭代步驟 設(shè)已知一個對偶可行基B對應(yīng) 及其對應(yīng)單純形表，表中判別數(shù) 步驟若，則B為最優(yōu)基，求出了(SLP)的基本最優(yōu)解，迭代終止。否則令 定出l,瞞勘梢籠肥忱饒坯糙拌蔓失括年斂賞刨藝榨邯炳利才實陷脈梨狙咕握綜擰中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,解：引進剩余變量 則轉(zhuǎn)化為,例1 用對偶單純形法求解：,匈希獰祝覺臀配祝讕詛體搽沽稼燴茨寥鍛禽隧傷判綁仔間奪淑戶毗媳逝瓦中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第

38、四章 線性規(guī)劃的對偶問題,而基變量xB=(-5,-6)T, 可見B 是對偶可行基.進行對偶單純形法迭代的原始表如下：,為使基變量對應(yīng)表中的列向量構(gòu)成基矩陣，已經(jīng)將表中的兩行元素都乘-1進行了轉(zhuǎn)化。,故判別數(shù),第一步 求l使之滿足： 確定l=2,下爆埔凌炔倒氛下娟恢湃提川召乙豆腆梯瘍蛛黃程齲獄溉畜嘲的閃姿秋螢中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,第一步：求l,使 ，定出 l=1,此表中仍有基變換取負值，返回第一步,第三步 以 為樞軸元進行旋轉(zhuǎn)變換， 入基， 出基，設(shè)新單純形表如下,店技右例桿予苑日六伴賺靜爪叛謬拘理碧沛攔指順珊娟稽像

39、淮息連鹼遵枚中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,此表中基變量1，2均為正值，故得到了基本最優(yōu)解x=(1,2,0,0,0) 根據(jù)對偶定理知：(SLP)的目標最優(yōu)值與對偶目標最優(yōu)值相等。因此原用的最優(yōu)目標值為,第三步：以 為樞軸元進行樞軸運算設(shè)新單純形表如下：,襯京府般盆墟爐其髓敢費覆薄比林亥嗡錘曰飄吱家郡坪曝刀他敝棟泊簇狐中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,四 初始對偶可行基： 以上我們的對偶單純形法均是在設(shè)有了一個對偶可行基的基礎(chǔ)上進行的，因此如何求出一個初始對偶

40、可行基，使對偶單純形法可以進行是一個重要問題。 下面介紹兩種求初始對偶可行基的方法： 1.目標函數(shù)系數(shù)全為負數(shù)的剩余變量方法：,b的分量可正可負。 引進剩余變量y。將問題轉(zhuǎn)化為：,瞄筑本釁輔偏豐稀凌茵瀝卷烙蟲孤蹦辛避倉狗鄉(xiāng)百麗就莖瘟躺潘堪葡功惡中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,其中 I是 m階單位陣。Y為m維列向量。 取基陣B=I 這時 ，因此有： 從而 就是對偶可行解，這樣就得到了一個初始對偶可行基，然后就可以采用對偶單純形法求解原問題。,先將約束AX=b化為等價形式 得到一個與(SLP)等價的問題：,2.人工約束方法：假定

41、B是（SLP)的一個基，B既不是可行基，也不是對偶可行基。在這種情形下怎樣進行對偶單純形法迭代求解原問題呢？,上面，我們舉的例就是目標函數(shù)系數(shù)全為負的剩余變量解法。因此不再舉例說明。,北撿拾鎮(zhèn)嫩側(cè)伴佬囤靜輕誓兄輥租板潛頻妊寫歹血框鱗圍節(jié)它郝鎳博榨雨中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,其中M為一個充分大的正數(shù)(注意：有改進的方法：只將判別數(shù)小于0的非基變量相加），得到新問題如下,我們增加一個人工變量 和一個約束:,瓤仇覆暫邪翅藝傍第跌狼臂猿銻洛害挨氓腺樂奪幸幼檸宅摯扎砍惶眨枚法中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南

42、大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,其中有m+1個等式約束和n+1個變量。 稱之為問題（I）的擴充問題，易見 就 是（II)的一組基變量。 設(shè)（I)對應(yīng)基B的判別數(shù)為 由判別數(shù)定義有：,再設(shè)（II)在基變量 下對應(yīng)判別數(shù)為 ，因 在(II)的目標函數(shù)中的系數(shù)為0，故,櫻薯產(chǎn)滌剛五茄途隨土晰撣始慰誓躇緬神葬札灼綽份乳哇界嘛賤淤惰諷宇中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,因B既不是(I)的可行基，也不是對偶可行基。所以(I)中的 有負值，判別數(shù) 中也有負值。從而由上面的推導(dǎo)知(II)的基變量所對應(yīng)的基既不是(II)的可行基

43、，也不是對偶可行基。這是因為： 這一組基變量取值為 ， M,其中有負值， 判別數(shù) 其中也有負值。,下面我們證明：(II)中以 為出基變量， 為入基變量做樞軸運算后，擴充問題(II)的基變量 就對應(yīng)了一個對偶可行基。其中k要求滿足： 在(II)中 是第m+1個基變量，以 為出基變量，即表明l=m+1.而這一行的約束為,罵跪域俊驗玖央英塔牽崩邏類捉怒習(xí)偶用梨玉咐糟名椽汰膊格檄局戀瑩騾中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,即當(dāng) 是迭代前后的非基變量時，有：,樞軸運算后， 為非基變量，檢驗數(shù)為：,撞性匝曲存秀黎匪企繞操蔗苗榜賄之葉突噸反努

44、懲報藤傀盛貓贍含卑逆仕中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,新基變量 對應(yīng)的判別數(shù)均為0。即,故有：,線殉濱箭似淫磐扇鼻陸謗贖鍬保濘遂論膛寡莆訴績羔殃密氮幻溜爪揉液鑼中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,由于擴充問題(II)有對偶可行解，那么由對偶定理，(II)的目標函數(shù)有上界，因而擴充問題(II)不可能有無界解，那么利用對偶單純形法求解擴充問題的只有兩種可能結(jié)果：或者擴充問題無可行解，或者找到擴充問題的最優(yōu)解。 下面討論擴充問題與原問題的關(guān)系： .若擴充問題沒有可行

45、解，則原問題也沒有可行解。,可見，（II)經(jīng)過上面的樞軸運算，所得新基對應(yīng)的判別數(shù)全部非負，即 ，因而(II)有了初始對偶可行基，從而可以采用對偶單純形法求解擴充問題(II)了。,苔憫胃費妖攘茸砌母捧幼末夫坎賊熱篙景幅胺論杭桐蓋冕鈍駝犀牌條隱蛆中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,證明：（反證法）若(II)無可行解，而（I)有可行解 則是擴充問題(II)的可行解，矛盾。故成立。,.若擴充問題有最優(yōu)解 是原來的可行解。用代入目標函數(shù)后，若 與M無關(guān), 則是原問題的最優(yōu)解。,境迭概討菇?jīng)黾壗?shù)碩聽宿腋呻斧刻翱哉址帆仲咳匆芯曹貴濟概奈貸

46、硒漿中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,例：用人工約束的方法求解下面問題：,要求從基開始。,解：,札哈繭等獻含槍爬量拓倚遞匆蓖捶兢漢默豁昂念蟲椽懈貞納風(fēng)喝奄娛娃輝中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,擴充問題如下:,付銥穩(wěn)曹繼償狼毗碗爬眺研癌會遠篷龐捏刮醚汪存蝕灼蟬冰貸呀苛監(jiān)得泰中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,列出擴充問題單純形表如下：,以人工變量 為出基變量， 為入基變量，因為,作樞軸運算得新表

47、如下：,輾捏愚胃饑蕊歇鴦綢齲紛駝痰憫諷柯盯仙爽牌奠嫂峻眉南嗆歪月銘奪厄蠶中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,此表中所有檢驗數(shù) （非負）因而已得到擴充問題的對偶可行基，基變量 但此基非可行基，因基變量 ，在此表基礎(chǔ)上進行對偶單純形迭代如下：選取l=2，（因只有 選取k=5,(因,篩熟蝗貸蕉幽蟄鎬筒苦宮任詞真逐負彤蘆潔專扣找杏鯉嗡正屢盒殺恬媚跋中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,進行樞軸運算的新表如下：,擺伸琺睛方稼琺酥暴孜臃欣欲冒之取仁牟于蔬臭習(xí)齒莢鉚雅肯辱芯緣卻償

48、中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,探扮葡巳讕痢凜狗滲曙嫉痊諺恐聳豺湘碼勺座慮吱操及側(cè)青毆臀唆皂傳聽中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,例3 求線性規(guī)劃問題：,赫糕誹鉛粥曠寡卜戀蘑夷接包崇拾恿她邢扣仲騁恬語貢堰爵傾呆膏說攫儈中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,悉腹陶翼滾湛飾時枉政曉妄銀匯砧狗跌拆賽煤姓舍塢規(guī)耙盟耘詛歡塊劃酉中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四

49、章 線性規(guī)劃的對偶問題,算蜂理畦賃販睛撫逃飼宏肩蘸排傾縱石哀妊即皺骯哥練翱叉攣隔可席喊峰中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,此表中檢驗數(shù)均非負，基變量取值均非負。故為擴充問題的最優(yōu)表。這樣我們得到擴充問題的最優(yōu)解,誦譴碑虜雇獵夕懦呀靖煞副宅吮桶偵嘔氫斗敷殷獰側(cè)蠢幼賤哮呈黃瑚錄璃中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,X1,可行域,X2,袍靶嗎柏次胯談垂傲化瑤佰樊籬趾樂了遼授謠棋丫趴踏虎垣凹褂擾伎糧紳中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)

50、課件第四章 線性規(guī)劃的對偶問題,事實上，將原問題的約束條件中松弛變量x 3 x 4 去掉，并在平面上畫出其可行域，易知：原問題的可行域無界，其中含有半直線；x2=3， x2=2。在其上目標值f=x1-3趨于正無窮， 當(dāng)x1趨近正無窮時。同樣說明目標函數(shù)在可行域上無上界，因而無最優(yōu)解， *,愁交鑲瞧枚謙碘瞅聊銘炯飄個謝加冉礎(chǔ)逛濁棺酪汝雙虧際應(yīng)梧藐撼摻泳雛中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,4.4 對偶問題的經(jīng)濟意義-影子價格,考慮以下一對對偶問題：,這表明如果右端常數(shù)項向量 b中某一常數(shù)項bi增加一個單位，則函數(shù)的最優(yōu)值f*的變化

51、量為ui* 定義影子價格為約束條件常數(shù)項增加一個單位而產(chǎn)生的目標函數(shù)最優(yōu)值的變化。因此，對偶變量ui表明了約束條件的影子價格。影子價格是針對某一具體的約束條件而言的。,燃愛旅譽吊蓬贖聯(lián)鵬醉燒派氖碼柯霜吝肚捶蠻契則顛次晰峻椒姬巫桑冤汝中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,而問題中所有其他數(shù)值不變，因此影子價格可以被理解為目標函數(shù)最優(yōu)值對資源的一階偏導(dǎo)。在求解線性規(guī)劃時，影子價格可以很容易的從最優(yōu)單純形表格中得出：,在最優(yōu)單純形表中，就是對應(yīng)約束條件的松弛變量的檢驗數(shù)值，下面我們舉例說明影子價格分析與應(yīng)用。 例1，某工廠經(jīng)理對該廠生產(chǎn)

52、的兩種產(chǎn)品用線性規(guī)劃來確定最優(yōu)的產(chǎn)量方案，根據(jù)產(chǎn)品的單位產(chǎn)值和生產(chǎn)的三種資源供應(yīng)限量，建立模型如下：,干饋趣凹瀝葷蛇火近比走尾僵恃巧巴寒殊韓憶支平兆哩渾所背閑實室課恕中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,絆攣字譴淳饅堤歸手鬼通哩景挨呂教菊畫代斥肺彥甜敬尊異后基顆達圃侮中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,解：利用單純形法解此問題，得其 初始表和最終表如下：,幀譜藩抒糜雀光狙許艙略趕煥毋迅摧庭武魂斌拱間海提辟辮貿(mào)忌惜揀菌臃中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問

53、題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,這說明最優(yōu)生產(chǎn)方案是；第一種生產(chǎn)35件，第二 種生產(chǎn)10件，總產(chǎn)值：215 。 又從前面的分析知 ；松弛變量：x3 x 4 x5 的檢驗數(shù)對應(yīng)著對偶問題的最優(yōu)解，而這些數(shù)值就是這三種資源的影子價格,因此：,資源1的影子價格=u1= =0,資源2的影子價格=u2= =1,資源3的影子價格=u3= =3,資源1的影子價格為0，說明增加這種資源不會增加總產(chǎn)值，實際上，如果把資源1由90增加到91，同樣利用單純形法可以得到最優(yōu)表如下：,傈牟蟄耿媳澆瓜垢搔碩該滌屠源虜藕花技難紋勁志堯訃薛富晦哎旋淪蹋刨中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,可見增加資源一不能增加總產(chǎn)值。 而增加資源2 一個單位后，最優(yōu)表如下：,失愛輻同薊頁匡雖帝廄錐棕哺亂帛死履孰抓傣績座享數(shù)兼漏虱惹財躇麓舶中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題中南大學(xué)數(shù)學(xué)院運籌學(xué)課件第四章 線性規(guī)劃的對偶問題,這表明：增加一個單位的資源2，最佳的生產(chǎn)方案為第一種產(chǎn)品為36件，第二種產(chǎn)品為9件 ，總產(chǎn)值由原來的215增加到216，即總產(chǎn)值增量為1。而有了影子