[高等教育]4線性規(guī)劃的對(duì)偶問題ppt課件

1、線性規(guī)劃的對(duì)偶問題的例子線性規(guī)劃的對(duì)偶問題的例子某工廠消費(fèi)A，B兩種產(chǎn)品，知制造A產(chǎn)品每件需勞動(dòng)力7人，原料5公斤，電力2度。制造B產(chǎn)品每件需勞動(dòng)力5人，原料8公斤，電力5度，工廠可運(yùn)用的勞動(dòng)力最多為3500人，原料最多為4000公斤，電力最多為2000度，A產(chǎn)品每件利潤(rùn)6元， B產(chǎn)品每件利潤(rùn)7元，問如何安排消費(fèi)，才使工廠的利潤(rùn)最大？線性規(guī)劃的對(duì)偶問題的例子線性規(guī)劃的對(duì)偶問題的例子設(shè)x1,x2分別是A，B產(chǎn)品的消費(fèi)量，那么：勞動(dòng)力約束原料約束電力約束問題：某公司欲購(gòu)買該工廠的三種資源勞動(dòng)力、原料、電力，確定這三種資源的價(jià)錢，使工廠情愿出賣同時(shí)又使公司化費(fèi)最小？線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問

2、題設(shè)購(gòu)買該廠的資源(勞動(dòng)力，原料，電力)的單位價(jià)錢分別為y1,y2,y3,那么有消費(fèi)1個(gè)單位的A產(chǎn)品的資源出賣給公司應(yīng)大于其利潤(rùn)消費(fèi)1個(gè)單位的B產(chǎn)品的資源出賣給公司應(yīng)大于其利潤(rùn)線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題兩個(gè)問題的線性規(guī)劃如下：0,200052400085350057. .76 Z2121212121xxxxxxxxtsxxMax123123123123 3500400020007526. . 5857,0Min fyyyyyystyyyy yy兩個(gè)線性規(guī)劃之間的關(guān)系？?jī)蓚€(gè)線性規(guī)劃之間的關(guān)系？線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題豢養(yǎng)場(chǎng)的混合飼料由兩種配料組成，混合飼料必需含有維生素B和

3、維生素C，并且維生素B和C的含量分別不低于5和6，現(xiàn)知第一種配料中每單位維生素B含量為3，維生素C含量為3，單價(jià)為13，第二種配料中每單位維生素B含量為1，維生素C含量為4，單價(jià)為10，問在保證營(yíng)養(yǎng)的條件下，應(yīng)如何配方，使混合飼料的費(fèi)用最??？線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題設(shè)第一種配料用x1單位，第二種配料用x2單位第一個(gè)約束為維生素B的含量，第二個(gè)約束為維生素C的含量。線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題現(xiàn)有某個(gè)制藥廠要推銷維生素B和維生素C藥劑，廠商希望豢養(yǎng)場(chǎng)可以用維生素B和維生素C藥劑來配制混合飼料，為做到這一點(diǎn)，必需保證維生素B和維生素C的價(jià)錢不超越上述兩種配料，在這種條件下，應(yīng)如

4、何確定維生素B和C藥劑的價(jià)錢，使制藥廠的收益最大？線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題設(shè)y1,y2分別是維生素B和C藥劑的單價(jià)在具有第一種配料的營(yíng)養(yǎng)條件下，藥劑的價(jià)錢不超越第一種配料在具有第二種配料的營(yíng)養(yǎng)條件下，藥劑的價(jià)錢不超越第二種配料兩個(gè)線性規(guī)劃的特點(diǎn)兩個(gè)線性規(guī)劃的特點(diǎn)約束條件的右端是另一個(gè)規(guī)劃的目的函數(shù)的系數(shù)約束條件的系數(shù)矩陣的轉(zhuǎn)置是另一個(gè)規(guī)劃的約束條件的系數(shù)矩陣這兩個(gè)線性規(guī)劃具有對(duì)稱性。線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題稱(LP)和(LD)是一對(duì)相互對(duì)偶的線性規(guī)劃問題目的函數(shù)求最小，約束條件寫成大于等于；目的函數(shù)求最大，約束條件寫成小于等于。規(guī)范方式的對(duì)偶規(guī)范方式的對(duì)偶規(guī)范方式的對(duì)偶

5、規(guī)范方式的對(duì)偶兩種方式的對(duì)偶兩種方式的對(duì)偶對(duì)稱方式：規(guī)范方式： 規(guī)范方式的對(duì)偶問題例子規(guī)范方式的對(duì)偶問題例子那么它的對(duì)偶問題為：對(duì)偶性與最優(yōu)性對(duì)偶性與最優(yōu)性l研討一對(duì)相互對(duì)偶的線性規(guī)劃問題它們最優(yōu)解之間的關(guān)系。l先思索對(duì)稱方式的對(duì)偶問題，再思索規(guī)范方式的對(duì)偶問題。弱對(duì)偶性：弱對(duì)偶性：弱對(duì)偶性：最優(yōu)性最優(yōu)性l假設(shè)X，Y分別是LP和LD的可行解，且l CTXbTY，那么X，Y分別是LP和LD的最優(yōu)解。l證：對(duì)LP的任一可行解X，bTY CTX，bTY CTX這闡明CTX是bTY的一個(gè)下界。當(dāng)bTYCTX時(shí)，目的函數(shù)CTX到達(dá)最大值。無界性無界性l假設(shè)LP的目的函數(shù)(求Max)在可行域內(nèi)無上界，那么

6、對(duì)偶問題LD是不可行的。l假設(shè)對(duì)偶問題LD的目的函數(shù)(求Min)在可行域內(nèi)無下界，那么原問題LP是不可行的。l反證法：假設(shè)LD是可行的，即存在可行解Y，由弱對(duì)偶性，CTX bTY此即闡明LP的目的函數(shù)有上界。無界性無界性l該定理的逆定理不成立。l有能夠LP和LD都是不可行的。(LP)無界，1,xZ(LD)不可行。(LP)和(LD)都是不可行的。無界性的逆定理不成立無界性的逆定理不成立互補(bǔ)松弛性質(zhì)互補(bǔ)松弛性質(zhì)互補(bǔ)松弛性質(zhì)互補(bǔ)松弛性質(zhì)l假設(shè)LP有最優(yōu)解X * ，那么LD也有最優(yōu)解Y * ，且有X * TV * 0，Y * TU * 0l其中V * ATY * C ，U * b AX * 。l証：假

7、設(shè)y，Y分別是LP和LD的最優(yōu)解，那么CTX*=bTY*.將它們化成規(guī)范方式，并求出最優(yōu)解。(LD)的剩余變量：(LP)的松弛變量：它們的最優(yōu)解滿足互補(bǔ)松弛性質(zhì)!對(duì)偶問題最優(yōu)解的性質(zhì)對(duì)偶問題最優(yōu)解的性質(zhì)l對(duì)稱方式：l假設(shè)LP有最優(yōu)解X，那么對(duì)偶問題LD也有最優(yōu)解Y，且y是LP最優(yōu)單純形表中松弛變量V下的檢驗(yàn)數(shù)的負(fù)值；l X是LD最優(yōu)單純形表中剩余變量U下的檢驗(yàn)數(shù)的負(fù)值。用對(duì)偶單純形法求解(LD),列出初始單純形表如下：最優(yōu)解：剩余變量y3,y4下的檢驗(yàn)數(shù)： -24, -8最優(yōu)單純形表可求得最優(yōu)解如下：對(duì)偶問題的最優(yōu)解：y1=24,y2=8對(duì)偶問題LP的初始單純形表如下：1224,8 336xx

8、Max z最優(yōu)解：松弛變量的檢驗(yàn)數(shù)：-2 , -2規(guī)范方式的對(duì)偶問題最優(yōu)規(guī)范方式的對(duì)偶問題最優(yōu)解的性質(zhì)解的性質(zhì)假設(shè)規(guī)范方式LP有根本最優(yōu)解y，且：0*1bBXXXNB那么(LD)的最優(yōu)解為：TTBBCY)(*1規(guī)范方式的對(duì)偶問題：CYAtsYbMaxTT. . 1*()TTTTBA yAC BLP中根本最優(yōu)解y*的檢驗(yàn)數(shù)？規(guī)范方式的對(duì)偶問題規(guī)范方式的對(duì)偶問題最優(yōu)解的性質(zhì)最優(yōu)解的性質(zhì)根本解y*的檢驗(yàn)數(shù)： CT CBTB-1A 0ATy*=AT(CBTB-1)TCy*是對(duì)偶問題的可行解對(duì)偶問題LD的目的函數(shù)值原問題LP的目的函數(shù)值*1()TTTTBzb ybC B*1TTBfC xC B bf*=

9、z*,兩目的函數(shù)值相等。恰好是單純形表中x4,x5,x6下的檢驗(yàn)數(shù)的負(fù)值 。單純形法的求解單純形法的求解 . .()0TMax C XAXbstLPX(LP)(LP)問題：?jiǎn)栴}：假設(shè)假設(shè)x x滿足條件：滿足條件：1.xB=B-1b1.xB=B-1b0,xN=0;0,xN=0;2.CT-CBTB-1A2.CT-CBTB-1A0 0那么x是(LP)的最優(yōu)解。單純形法是在滿足第1個(gè)條件下，經(jīng)過運(yùn)算逐漸使第二個(gè)條件滿足。對(duì)偶單純形法的求解對(duì)偶單純形法的求解對(duì)偶 單純形法是在滿足第2個(gè)條件下CT-CBTB-1A 0 ，經(jīng)過運(yùn)算逐漸使第1個(gè)條件滿足。即在單純形表中要求檢驗(yàn)數(shù)行小于零，而初始根本解不一定可行

10、。原問題與對(duì)偶問題之間的方式原問題與對(duì)偶問題之間的方式l原問題(LP)的目的函數(shù)求May,那么對(duì)偶問題(LD)的目的函數(shù)求Min;l原問題(LP)的主約束條件有m個(gè)，那么對(duì)偶問題(LD)的對(duì)偶變量有m個(gè)；l原問題(LP)的變量有n個(gè)，那么對(duì)偶問題(LD)的主約束條件有n個(gè)；l原問題(LP)的第i個(gè)約束條件為型，那么對(duì)偶問題(LD)的第i個(gè)變量yi0;原問題與對(duì)偶問題之間的關(guān)系原問題與對(duì)偶問題之間的關(guān)系l原問題(LP)的第i約束條件為型，那么對(duì)偶問題(LD)的第i個(gè)變量yi 0;l原問題(LP)的第i約束條件為=型，那么對(duì)偶問題(LD)的第i個(gè)變量yi 無非負(fù)限制;l原問題(LP)的第i個(gè)變量y

11、i為 0，那么對(duì)偶問題(LD)的第i個(gè)約束條件為型;l原問題(LP)的第i個(gè)變量yi為 0，那么對(duì)偶問題(LD)的第i個(gè)約束條件為型;l原問題(LP)的第i個(gè)變量yi無非負(fù)限制，那么對(duì)偶問題(LD)的第i個(gè)約束條件為=型;原問題與對(duì)偶問題之間的關(guān)系原問題與對(duì)偶問題之間的關(guān)系l原問題(LP)的目的函數(shù)求May,主約束條件為型，那么稱此約束為規(guī)范約束，否那么稱為非規(guī)范約束。l同樣對(duì)偶問題(LD)的目的函數(shù)求Min,主約束條件為型，那么稱此約束為規(guī)范約束，否那么稱為非規(guī)范約束。l(LP)的每一個(gè)約束對(duì)應(yīng)于(LD)的每一個(gè)變量。l(LP)的每一個(gè)變量對(duì)應(yīng)于(LD)的每一個(gè)約束。寫出以下線性規(guī)劃的對(duì)偶問

12、題寫出以下線性規(guī)劃的對(duì)偶問題對(duì)偶問題應(yīng)有3個(gè)變量；4個(gè)約束。對(duì)偶問題的目的函數(shù)：第一個(gè)約束對(duì)應(yīng)于第一個(gè)變量。y1+2y2 2寫出以下線性規(guī)劃的對(duì)偶問題寫出以下線性規(guī)劃的對(duì)偶問題0, 0, 06425. .532 321432314321321xxxxxxxxxxxxtsxxxSMin第二個(gè)約束對(duì)應(yīng)第二個(gè)變量：y1+y3 3 它應(yīng)是規(guī)范約束第三個(gè)約束對(duì)應(yīng)第三個(gè)變量：-y1+y2+y3 -5 它是規(guī)范約束第四個(gè)約束對(duì)應(yīng)第四個(gè)變量：y1+y3=0 它是等式約束對(duì)偶問題的第一個(gè)變量0，第二個(gè)變量0，第三個(gè)變量無非負(fù)限制。用對(duì)偶單純形法求解： 第三行1 2 0 0 -1 50-3 -6 0 0 3 -1

13、50第二行 0 -11 0 1 3 0第一行 0 -6 1 0 3 -120檢驗(yàn)數(shù)0 10 0 0 3 -150第一行0 1 -1/6 0 -1/2 20 0 11 -11/6 0 -11/2 220 第二行0 0 -11/6 1 -5/2 2200 -2 1/3 0 1 -40第三行1 0 1/3 0 0 100 -10 5/3 0 5 -200檢驗(yàn)數(shù)0 0 5/3 0 8 -350最優(yōu)解：x1=10,x2=20,Min S=350對(duì)偶問題的最優(yōu)解？對(duì)偶問題(按對(duì)稱方式)：對(duì)偶問題(按普通方式)：對(duì)偶問題解的意義對(duì)偶問題解的意義某工廠消費(fèi)A，B兩種產(chǎn)品，知制造A產(chǎn)品每件需勞動(dòng)力7人，原料5公

14、斤，電力2度。制造B產(chǎn)品每件需勞動(dòng)力5人，原料8公斤，電力5度，工廠可運(yùn)用的勞動(dòng)力最多為3500人，原料最多為4000公斤，電力最多為2000度，A產(chǎn)品每件利潤(rùn)6元， B產(chǎn)品每件利潤(rùn)7元，問如何安排消費(fèi)，才使工廠的利潤(rùn)最大？可列出如下的線性規(guī)劃模型： 對(duì)偶問題解的意義對(duì)偶問題解的意義設(shè)y1,y2分別是A，B產(chǎn)品的消費(fèi)量，那么：可求得最優(yōu)解：對(duì)偶問題解的意義對(duì)偶問題解的意義最優(yōu)單純形表如下：最優(yōu)基底B=(P1，P4，P2)，B-1=？工廠的勞動(dòng)力添加一個(gè)單位，工廠可添加多少利潤(rùn)？對(duì)偶問題解的意義對(duì)偶問題解的意義設(shè)工廠的勞動(dòng)力從3500添加到3500+b1在基底B下，根本解為B-1(b+ b)12521259151125725225312595151280260300200040003500010bbbb此時(shí)，目的函數(shù)值為：1251612521513760)280(7)300(6*bbbS對(duì)偶問題解的意義對(duì)偶問題解的意義勞動(dòng)力每添加一個(gè)單位，工廠可添加利潤(rùn)：16/25同理可算得電力每添加一個(gè)單位，工廠可添加利潤(rùn)：19/253257325313513257252253125951512802