線性規(guī)劃的對(duì)偶與對(duì)偶單純形法

線性規(guī)劃的對(duì)偶與對(duì)偶單純形法第1頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月對(duì)偶原理對(duì)偶問題概念：任何一個(gè)線性規(guī)劃問題都有一個(gè)與之相對(duì)應(yīng)的線性規(guī)劃問題，如果前者稱為原始問題，后者就稱為“對(duì)偶”問題。對(duì)偶問題是對(duì)原問題從另一角度進(jìn)行的描述其最優(yōu)解與原問題的最優(yōu)解有著密切的聯(lián)系，在求得一個(gè)線性規(guī)劃最優(yōu)解的同時(shí)也就得到對(duì)偶線性規(guī)劃的最優(yōu)解，反之亦然。對(duì)偶理論就是研究線性規(guī)劃及其對(duì)偶問題的理論，是線性規(guī)劃理論的重要內(nèi)容之一。第2頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月問題的導(dǎo)出ABC擁有量工時(shí)1113材料1479單件利潤(rùn)233第3頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月ABC擁有量工時(shí)1113材料1479單件利潤(rùn)233假設(shè)有客戶提出要求，購(gòu)買工廠所擁有的工時(shí)和材料，為客戶加工別的產(chǎn)品，由客戶支付工時(shí)費(fèi)和材料費(fèi)。那么工廠給工時(shí)和材料制訂的最低價(jià)格應(yīng)是多少，才值得出賣工時(shí)和材料?第4頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月ABC擁有量工時(shí)1113材料1479單件利潤(rùn)233出賣資源獲利應(yīng)不少于生產(chǎn)產(chǎn)品的獲利;約束價(jià)格應(yīng)該盡量低，這樣，才能有競(jìng)爭(zhēng)力;目標(biāo)價(jià)格應(yīng)該是非負(fù)的第5頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月ABC擁有量工時(shí)1113材料1479單件利潤(rùn)233用y1和y2分別表示工時(shí)和材料的出售價(jià)格總利潤(rùn)最小minW=3y1+9y2保證A產(chǎn)品利潤(rùn)y1+y2≥2保證B產(chǎn)品利潤(rùn)y1+4y2≥3保證C產(chǎn)品利潤(rùn)y1+7y2≥3售價(jià)非負(fù)y1≥0y2≥0第6頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月ABC擁有量工時(shí)1113材料1479單件利潤(rùn)233第7頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月對(duì)偶問題的定義對(duì)稱形式的對(duì)偶問題第8頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月對(duì)偶的定義原始問題minf(x)=CTXs.t. AX≥b X≥0對(duì)偶問題maxz(y)=bTys.t.ATy≤C y≥0≥minbACTCATbT≤maxmnmn第9頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月對(duì)偶問題的特點(diǎn)（1）目標(biāo)函數(shù)在一個(gè)問題中是求最大值在另一問題中則為求最小值（2）一個(gè)問題中目標(biāo)函數(shù)的系數(shù)是另一個(gè)問題中約束條件的右端項(xiàng)（3）一個(gè)問題中的約束條件個(gè)數(shù)等于另一個(gè)問題中的變量數(shù)（4）原問題的約束系數(shù)矩陣與對(duì)偶問題的約束系數(shù)矩陣互為轉(zhuǎn)置矩陣第10頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月minf=CTXs.t. AX≤b X≥0maxz=bTYs.t.ATY≤CY≤0其他形式問題的對(duì)偶minf=CTXs.t. AX≥b X≥0maxz=bTYs.t.ATY≤CY≥0minf=CTXs.t. AX=b X≥0maxz=bTYs.t.ATY≤CY：unr第11頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月一般線性規(guī)劃問題的對(duì)偶問題第12頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月對(duì)偶問題對(duì)應(yīng)表原問題（對(duì)偶問題）對(duì)偶問題（原問題）目標(biāo)函數(shù)min目標(biāo)函數(shù)max約束條件：m個(gè)第i個(gè)約束類型為“≥”第i個(gè)約束類型為“≤”第i個(gè)約束類型為“＝”變量數(shù)：m個(gè)第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量是自由變量

變量數(shù)：n個(gè)第j個(gè)變量≤0第j個(gè)變量≥0第j個(gè)變量是自由變量

約束條件：n個(gè)第j個(gè)約束類型為“≥”第j個(gè)約束類型為“≤”第j個(gè)約束類型為“＝”第13頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月例寫出如下LP問題的對(duì)偶問題對(duì)偶問題第14頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月對(duì)偶問題的性質(zhì)1、對(duì)偶的對(duì)偶就是原始問題maxz’=-CTXs.t.-AX≤-b X≥0miny=-bTWs.t.-ATW≥-C W≥0maxy=bTWs.t.ATW≤C W≥0minz=CTXs.t.AX≥b X≥0對(duì)偶的定義對(duì)偶的定義第15頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月2、對(duì)偶定理（1）弱對(duì)偶性（可行解的目標(biāo)函數(shù)值之間的關(guān)系）設(shè)X、Y分別是原始問題和對(duì)偶問題的可行解 f=CTX≥YTAX≥YTb=z第16頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月（3）最優(yōu)性（2）無界性如果原問題（對(duì)偶問題）具有無界解，則其對(duì)偶問題（原問題）無可行解。第17頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月無界性在一對(duì)對(duì)偶問題，若其中一個(gè)問題可行但目標(biāo)函數(shù)無界，則另一個(gè)問題不可行；反之不成立。這也是對(duì)偶問題的無界性。關(guān)于無界性有如下結(jié)論：?jiǎn)栴}無界無可行解無可行解無可行解問題無界對(duì)偶問題原問題無界如：（原）無可行解（對(duì)）第18頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月已知試用對(duì)偶理論證明原問題無界。解：=（0.0.0）是P的一個(gè)可行解，而D的第一個(gè)約束條件不能成立（因?yàn)閥1,

y2≥0)。因此，對(duì)偶問題不可行，可知，原問題無界。第19頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月（4）強(qiáng)對(duì)偶性（最優(yōu)解的目標(biāo)函數(shù)之間的關(guān)系）如果原問題有最優(yōu)解，則其對(duì)偶問題也一定有最優(yōu)解，且兩者的目標(biāo)函數(shù)值相等設(shè)X*、Y*分別是原始問題和對(duì)偶問題的最優(yōu)解

f=CTX*=Y*TAX*=Y*Tb=z第20頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月第21頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月在線性規(guī)劃問題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，3、互補(bǔ)松弛性則其對(duì)應(yīng)的對(duì)偶變量一定為零。即第22頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月第23頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月解：先寫出它的對(duì)偶問題第24頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月練習(xí)已知線性規(guī)劃問題第25頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月對(duì)偶單純形法對(duì)偶單純形法并不是求解對(duì)偶問題解的方法，而是利用對(duì)偶理論求解原問題的解的方法。對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題：可行基B若B對(duì)應(yīng)的基本解是可行解最優(yōu)基B若B對(duì)應(yīng)的基本解是最優(yōu)解對(duì)偶可行基B若CBB-1是對(duì)偶問題可行解即C-CBB-1A≥0或檢驗(yàn)數(shù)≥0第26頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題：最優(yōu)基B可行基B對(duì)偶可行基B單純形法可行基B保持可行性對(duì)偶可行基B對(duì)偶單純形法可行基B保持對(duì)偶可行性對(duì)偶可行基B第27頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題：對(duì)偶單純形法可行基B保持對(duì)偶可行性對(duì)偶可行基B①找一個(gè)基，建立初始對(duì)偶單純形表，檢驗(yàn)數(shù)全部非負(fù)；②若b列元素非負(fù)，則已經(jīng)是最優(yōu)基。反之，則取相應(yīng)行的基變量為出基變量；③為保證能對(duì)基的可行性有所改進(jìn)，則將來的主元應(yīng)該為負(fù)數(shù)；為保證下一個(gè)基還能是對(duì)偶可行基，應(yīng)使檢驗(yàn)數(shù)仍為非負(fù)的。④主元變換第28頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月下面通過例題說明對(duì)偶單純形法的步驟：例3用對(duì)偶單純形法求解線性規(guī)劃問題：解：先將問題改寫為：第29頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月2）算法步驟第一步：建立一個(gè)初始單純形表，使表中檢驗(yàn)行的值全部即對(duì)其對(duì)偶問題而言是一基本可行解約束條件兩端乘“－1”，得第30頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月根據(jù)原問題和對(duì)偶問題之間的對(duì)稱關(guān)系，這時(shí)單純形表中原基變量列數(shù)字相當(dāng)于對(duì)偶問題解的非基變量的檢驗(yàn)數(shù)第31頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月第二步：由于對(duì)偶問題的求解是使目標(biāo)函數(shù)達(dá)到最小值所以最優(yōu)判別準(zhǔn)則是當(dāng)所有檢驗(yàn)數(shù)大于等于零時(shí)為最優(yōu)（也即這時(shí)原問題是可行解）如果不滿足這個(gè)條件，找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)，設(shè)為，其對(duì)應(yīng)的原問題的基變量即為對(duì)偶問題的換入變量第三步：將行數(shù)字與表中第行對(duì)應(yīng)的數(shù)字對(duì)比令第32頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月第五步：重復(fù)第二～四步，一直到找出最優(yōu)解為止。第四步：用換入變量替換對(duì)偶問題中的換出變量（在單純形表中反映為用替原問題的基變量），得到一個(gè)新的單純形表。表中數(shù)字計(jì)算同用單純形法時(shí)完全一樣。新表中對(duì)偶問題仍保持基本可行解，原問題基變量列數(shù)字相當(dāng)于對(duì)偶問題的檢驗(yàn)數(shù)。第33頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月

y2

1/3

y5－1/3

011/6－1/6

0－5

0[-2/3]－1/3

1Cj-815

014

0

y2

1/4

y3?－5/4

10－1/4

1/415/2011/2－3/2cj-17/2

15/2007/23/21524500

y1

y2y3y4y5

y4－2

y5－1

0

［－6］－110

－5

－2－101cj0

15

24

5

0

0第34頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月例4考慮線性規(guī)劃問題第35頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月第36頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月基變量右端項(xiàng)－f6.8300000x3-2.6-11000-800x4-3.8-30100-1000x5-1.6-10010-100x6

-6-100001-6000第37頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月基變量右端項(xiàng)－f500000.3-1800x3

-20100-0.1-200x4-20010-0.3800x5-10001-0.1500x20.61000-0.1600第38頁(yè)，課件共45頁(yè)，創(chuàng)作于2023年2月基變量右端項(xiàng)－f002.5000.05-2300x110-0.5000.05100x400-1100.021000x500-0.5010.05600x2010.3000.13540至此，右端項(xiàng)的所有分量都已非負(fù)，當(dāng)前的迭代點(diǎn)已是一個(gè)對(duì)偶可行的餓基本可行解，因而也是最優(yōu)解，即最優(yōu)解為相應(yīng)的目標(biāo)函數(shù)值為第39頁(yè)，課件共45頁(yè)，創(chuàng)作于2023