對(duì)偶問(wèn)題及對(duì)偶單純形法完整課件

1、Duality Theory 線性規(guī)劃的對(duì)偶問(wèn)題 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格 對(duì)偶單純形法第四章 線性規(guī)劃的對(duì)偶理論 靈敏度分析 對(duì)偶問(wèn)題的基本性質(zhì)2022/9/241Duality Theory 線性規(guī)劃的對(duì)偶問(wèn)題 對(duì)偶問(wèn)題的 線性規(guī)劃的對(duì)偶問(wèn)題Duality Theory 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格 對(duì)偶單純形法 靈敏度分析 對(duì)偶問(wèn)題的基本性質(zhì)第四章 線性規(guī)劃的對(duì)偶理論2022/9/242 線性規(guī)劃的對(duì)偶問(wèn)題Duality Theory 對(duì)偶問(wèn)題的例如：平面中矩形的面積與周長(zhǎng)的關(guān)系周長(zhǎng)一定面積最大的矩形是正方形 : 面積一定周長(zhǎng)最短的矩形是正方形一、對(duì)偶問(wèn)題的提出 對(duì)同一問(wèn)題從不同角度考慮

2、，有兩種對(duì)立的描述。例1、應(yīng)如何安排生產(chǎn)計(jì)劃，使一天的總利潤(rùn)最大？ 某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，要用A、B、C三種不同的原料。每生產(chǎn)1噸甲產(chǎn)品，需耗用三種原料分別為1，1，0單位；生產(chǎn)1噸乙產(chǎn)品，需耗用三種原料分別為1，2，1單位。每天原料供應(yīng)的能力分別為6，8，3單位。又知道每生產(chǎn)1噸甲產(chǎn)品企業(yè)利潤(rùn)為300元，每生產(chǎn)1噸乙產(chǎn)品企業(yè)利潤(rùn)為400元。2022/9/243例如：平面中矩形的面積與周長(zhǎng)的關(guān)系一、對(duì)偶問(wèn)題的提出 例1、應(yīng)如何安排生產(chǎn)計(jì)劃，使一天的總利潤(rùn)最大？max x1 0 , x2 0s.t. x1 + x2 6z = 3x1 + 4x2 x1 + 2x2 8 x2 3設(shè) xj 表示第

3、 j 種產(chǎn)品每天的產(chǎn)量 假設(shè)該企業(yè)決策者決定不生產(chǎn)甲、乙產(chǎn)品，而是將廠里的現(xiàn)有資源外售。決策者應(yīng)怎樣制定每種資源的收費(fèi)標(biāo)準(zhǔn)才合理？2022/9/244例1、應(yīng)如何安排生產(chǎn)計(jì)劃，使一天的總利潤(rùn)最大？max x例1、應(yīng)怎樣制定收費(fèi)標(biāo)準(zhǔn)才合理？設(shè) yj 表示第 j 種原料的收費(fèi)單價(jià) 分析問(wèn)題： 1、出讓每種資源的收入不能低于自己生產(chǎn)時(shí)的可獲利潤(rùn)； 2、定價(jià)不能太高，要使對(duì)方能夠接受。 把生產(chǎn)一噸甲產(chǎn)品所用的原料出讓，所得凈收入應(yīng)不低于生產(chǎn)一噸甲產(chǎn)品的利潤(rùn)： 乙產(chǎn)品同理： 把企業(yè)所有原料出讓的總收入：只能在滿足所有產(chǎn)品的利潤(rùn)的條件下,其總收入盡可能少,才能成交.s.t.2022/9/245例1、應(yīng)怎樣

4、制定收費(fèi)標(biāo)準(zhǔn)才合理？設(shè) yj 表示第 j 種原料一、對(duì)偶問(wèn)題的提出 任何一個(gè)求極大的線性規(guī)劃問(wèn)題都有一個(gè)求極小的線性規(guī)劃問(wèn)題與之對(duì)應(yīng)，反之亦然. 把其中一個(gè)叫原問(wèn)題，則另一個(gè)就叫做它的對(duì)偶問(wèn)題，這一對(duì)互相聯(lián)系的兩個(gè)問(wèn)題就稱為一對(duì)對(duì)偶問(wèn)題。 s.t.LP1s.t.LP2原問(wèn)題（P）對(duì)偶問(wèn)題（D）2022/9/246一、對(duì)偶問(wèn)題的提出 任何一個(gè)求極大的線性規(guī)劃問(wèn)二、原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系s.t.Ps.t.Dyj 表示對(duì)第 j 種資源的估價(jià)矩陣形式：s.t.s.t. max z=CX s.t. AX b X 0 min w =bTY s.t. ATY CT Y 02022/9/247二、原問(wèn)題與

5、對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系s.t.Ps.t.Dyj 表示(一)對(duì)稱型對(duì)偶問(wèn)題其中 yi 0 （i = 1,2,m）稱為對(duì)偶變量。 變量均具有非負(fù)約束，且約束條件：當(dāng)目標(biāo)函數(shù)求極大時(shí)均取“”號(hào)，當(dāng)目標(biāo)函數(shù)求極小時(shí)均取“”號(hào)。max z = c1x1 + c2x2 + + cnxns.t. a11x1 + a12x2 + + a1nxn b1 a21x1 + a22x2 + + a2nxn b2 (P) am1x1 + am2x2 + + amnxn bm xj 0 （j = 1,2,n）min w = b1 y1 + b2 y2 + +bm yms.t. a11y1 + a21 y2 + + am1ym

6、 c1 a12y1 + a22y2 + + am2 ym c2 (D) a1ny1 + a2ny2 + + amnym cn yi 0 （i = 1,2,m） max z=CX s.t. AX b X 0 min w =bTY s.t. ATY CT Y 02022/9/248(一)對(duì)稱型對(duì)偶問(wèn)題其中 yi 0 （i = 1,2,(二)非對(duì)稱型對(duì)偶問(wèn)題分析：化為對(duì)稱形式。max x10, x20, x3無(wú)約束s.t. a11x1 + a12x2 + a13x3 b1z = c1x1 + c2x2 + c3x3 a31x1 + a32x2 + a33x3 b3 a21x1 + a22x2 + a

7、23x3 = b2令maxs.t.2022/9/249(二)非對(duì)稱型對(duì)偶問(wèn)題分析：化為對(duì)稱形式。max x10(二)非對(duì)稱型對(duì)偶問(wèn)題maxs.t.對(duì)偶變量mins.t.對(duì)偶問(wèn)題：2022/9/2410(二)非對(duì)稱型對(duì)偶問(wèn)題maxs.t.對(duì)偶變量mins.t.對(duì)(二)非對(duì)稱型對(duì)偶問(wèn)題mins.t.令mins.t.mins.t.2022/9/2411(二)非對(duì)稱型對(duì)偶問(wèn)題mins.t.令mins.t.mins3個(gè)=約束條件變 量(二)非對(duì)稱型對(duì)偶問(wèn)題mins.t.原問(wèn)題對(duì)偶問(wèn)題目標(biāo)函數(shù) max目標(biāo)函數(shù) min目標(biāo)函數(shù)的系數(shù)約束條件右端常數(shù)約束條件右端常數(shù)目標(biāo)函數(shù)的系數(shù)3個(gè)=3個(gè)00無(wú)符號(hào)限制約束條

8、件變 量3個(gè)00無(wú)符號(hào)限制原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）2022/9/24123個(gè)約束條件變 量(二)非對(duì)稱型對(duì)偶問(wèn)題mins.t.原3個(gè)=約束條件變 量(一)對(duì)稱型對(duì)偶問(wèn)題原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）目標(biāo)函數(shù) max目標(biāo)函數(shù) min目標(biāo)函數(shù)的系數(shù)約束條件右端常數(shù)約束條件右端常數(shù)目標(biāo)函數(shù)的系數(shù)3個(gè)=3個(gè)00無(wú)符號(hào)限制約束條件變 量3個(gè)00無(wú)符號(hào)限制s.t.s.t.2個(gè)2個(gè)2022/9/24133個(gè)約束條件變 量(一)對(duì)稱型對(duì)偶問(wèn)題原問(wèn)題（對(duì)偶問(wèn)題）二、原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系2022/9/2414二、原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系2022/9/2414例2、寫出下述線性規(guī)劃問(wèn)題的對(duì)

9、偶問(wèn)題解：設(shè)對(duì)偶變量為maxs.t.mins.t.則對(duì)偶問(wèn)題為2022/9/2415例2、寫出下述線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題解：設(shè)對(duì)偶變量為maxs例3、寫出下述線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題解：設(shè)對(duì)偶變量為mins.t.maxs.t.則對(duì)偶問(wèn)題為2022/9/2416例3、寫出下述線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題解：設(shè)對(duì)偶變量為mins練習(xí)、寫出下述線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題maxs.t.mins.t.2022/9/2417練習(xí)、寫出下述線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題maxs.t.mins. 對(duì)偶問(wèn)題的基本性質(zhì)Duality Theory 線性規(guī)劃的對(duì)偶問(wèn)題 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格 對(duì)偶單純形法 靈敏度分析第二章 線性規(guī)

10、劃的對(duì)偶理論2022/9/2418 對(duì)偶問(wèn)題的基本性質(zhì)Duality Theory 線性規(guī)劃的對(duì)偶問(wèn)題的基本性質(zhì)對(duì)稱性弱對(duì)偶性無(wú)界性最優(yōu)性原問(wèn)題與對(duì)偶問(wèn)題單純形表間的性質(zhì)互補(bǔ)松弛性強(qiáng)對(duì)偶性2022/9/2419對(duì)偶問(wèn)題的基本性質(zhì)對(duì)稱性弱對(duì)偶性無(wú)界性最優(yōu)性原問(wèn)題與對(duì)偶問(wèn)題對(duì)偶問(wèn)題的基本性質(zhì) max z=CX s.t. AX b X 0 min w =bTY s.t. ATY CT Y 0s.t.（P）s.t.（D）2022/9/2420對(duì)偶問(wèn)題的基本性質(zhì) max z=CX min 對(duì)偶問(wèn)題1、對(duì)稱性定理：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。對(duì)偶問(wèn)題max z = CXs.t. AX b X 0max w =

11、 bTYs.t. ATY CTY 0 min w = bTYs.t. ATY CT Y 0min z = CXs.t. AX b X 02022/9/2421 對(duì)偶問(wèn)題1、對(duì)稱性定理：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。對(duì)偶2、弱對(duì)偶性定理：設(shè) 和 分別是原問(wèn)題（P）和其對(duì)偶問(wèn)題（D）的可行解，則恒有2022/9/24222、弱對(duì)偶性定理：設(shè) 和 2、弱對(duì)偶性定理：設(shè) 和 分別是原問(wèn)題（P）和其對(duì)偶問(wèn)題（D）的可行解，則恒有推論：原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之，對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。2022/9/24232、弱對(duì)偶性定理：設(shè) 和 3、無(wú)界

12、性定理：在互為對(duì)偶的兩個(gè)問(wèn)題中，若一個(gè)問(wèn)題具有無(wú)界解，則另一個(gè)問(wèn)題無(wú)可行解。原問(wèn)題有可行解但目標(biāo)函數(shù)值無(wú)界對(duì)偶問(wèn)題無(wú)可行解對(duì)偶問(wèn)題有可行解但目標(biāo)函數(shù)值無(wú)界原問(wèn)題無(wú)可行解推論：原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之，對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。2022/9/24243、無(wú)界性定理：在互為對(duì)偶的兩個(gè)問(wèn)題中，若一個(gè)問(wèn)題具有無(wú)界解3、無(wú)界性定理：在互為對(duì)偶的兩個(gè)問(wèn)題中，若一個(gè)問(wèn)題具有無(wú)界解，則另一個(gè)問(wèn)題無(wú)可行解。原問(wèn)題有無(wú)界解對(duì)偶問(wèn)題無(wú)可行解推論：原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之，對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值是其原問(wèn)

13、題目標(biāo)函數(shù)值的上界?？赡苁菬o(wú)可行解推論1：在互為對(duì)偶的兩個(gè)問(wèn)題中，若一個(gè)問(wèn)題無(wú)可行解，則另一個(gè)問(wèn)題或具有無(wú)界解或無(wú)可行解。2022/9/24253、無(wú)界性定理：在互為對(duì)偶的兩個(gè)問(wèn)題中，若一個(gè)問(wèn)題具有無(wú)界解3、無(wú)界性定理：在互為對(duì)偶的兩個(gè)問(wèn)題中，若一個(gè)問(wèn)題具有無(wú)界解，則另一個(gè)問(wèn)題無(wú)可行解。推論1：在互為對(duì)偶的兩個(gè)問(wèn)題中，若一個(gè)問(wèn)題無(wú)可行解，則另一個(gè)問(wèn)題或具有無(wú)界解或無(wú)可行解。推論2：在互為對(duì)偶的兩個(gè)問(wèn)題中，若一個(gè)問(wèn)題有可行解，另一個(gè)問(wèn)題無(wú)可行解，則可行的問(wèn)題無(wú)界。無(wú)界解無(wú)可行解無(wú)可行解無(wú)界解對(duì)偶問(wèn)題原問(wèn)題2022/9/24263、無(wú)界性定理：在互為對(duì)偶的兩個(gè)問(wèn)題中，若一個(gè)問(wèn)題具有無(wú)界解例1、利用

14、對(duì)偶理論證明問(wèn)題無(wú)界（無(wú)最優(yōu)解）解：設(shè)對(duì)偶變量為maxs.t.mins.t.則對(duì)偶問(wèn)題為由 知，第一個(gè)約束可知對(duì)偶問(wèn)題無(wú)條件不成立，可行解。易知(0, 0, 0)T 是原問(wèn)題的一個(gè)可行解，故原問(wèn)題可行。由無(wú)界性定理可知，原問(wèn)題有無(wú)界解，即無(wú)最優(yōu)解。對(duì)偶問(wèn)題不可行原問(wèn)題無(wú)界或不可行無(wú)界 不可行2022/9/2427例1、利用對(duì)偶理論證明問(wèn)題無(wú)界（無(wú)最優(yōu)解）解：設(shè)對(duì)偶變量為m練習(xí)、證明下列線性規(guī)劃問(wèn)題無(wú)最優(yōu)解mins.t.maxs.t. 對(duì)偶問(wèn)題原問(wèn)題的一個(gè)可行解：對(duì)偶問(wèn)題不可行：找矛盾2022/9/2428練習(xí)、證明下列線性規(guī)劃問(wèn)題無(wú)最優(yōu)解mins.t.maxs.t4、最優(yōu)性定理：設(shè) 和 分別是

15、原問(wèn)題（P）和其對(duì)偶問(wèn)題（D）的可行解，且有則 和 分別是原問(wèn)題（P）和其對(duì)偶問(wèn)題（D）的最優(yōu)解。設(shè) 和 分別是P和D的最優(yōu)解：因此2022/9/24294、最優(yōu)性定理：設(shè) 和 5、互補(bǔ)松弛性定理：設(shè) 和 分別是原問(wèn)題和其對(duì)偶問(wèn)題的最優(yōu)解，若對(duì)偶變量 ，則原問(wèn)題相應(yīng)的約束條件若約束條件 ，則相應(yīng)的對(duì)偶變量2022/9/24305、互補(bǔ)松弛性定理：設(shè) 和 皮肌炎是一種引起皮膚、肌肉、心、肺、腎等多臟器嚴(yán)重?fù)p害的，全身性疾病，而且不少患者同時(shí)伴有惡性腫瘤。它的1癥狀表現(xiàn)如下： 1、早期皮肌炎患者，還往往伴有全身不適癥狀，如-全身肌肉酸痛，軟弱無(wú)力，上樓梯時(shí)感覺(jué)兩腿費(fèi)力；舉手梳理頭發(fā)時(shí)，舉高手臂很吃

16、力；抬頭轉(zhuǎn)頭緩慢而費(fèi)力。皮肌炎圖片皮肌炎的癥狀表現(xiàn) 皮肌炎是一種引起皮膚、肌肉、心、肺、腎等多臟器嚴(yán)重5、互補(bǔ)松弛性定理：設(shè) 和 分別是原問(wèn)題和其對(duì)偶問(wèn)題的最優(yōu)解，若對(duì)偶變量 ，則原問(wèn)題相應(yīng)的約束條件若約束條件 ，則相應(yīng)的對(duì)偶變量2022/9/24325、互補(bǔ)松弛性定理：設(shè) 和 5、互補(bǔ)松弛性定理：設(shè) 和 分別是原問(wèn)題和其對(duì)偶問(wèn)題的最優(yōu)解，若對(duì)偶變量 ，則原問(wèn)題相應(yīng)的約束條件若約束條件 ，則相應(yīng)的對(duì)偶變量若 ，則若 ，則若 ，則若 ，則2022/9/24335、互補(bǔ)松弛性定理：設(shè) 和 例2、利用互補(bǔ)松弛定理求最優(yōu)解maxs.t.已知原問(wèn)題的最優(yōu)解是求對(duì)偶問(wèn)題的最優(yōu)解。解：設(shè)對(duì)偶變量為mins.

17、t.則對(duì)偶問(wèn)題為設(shè)對(duì)偶問(wèn)題的最優(yōu)解為因由互補(bǔ)松弛性知解方程組得故對(duì)偶問(wèn)題的最優(yōu)解為2022/9/2434例2、利用互補(bǔ)松弛定理求最優(yōu)解maxs.t.已知原問(wèn)題的最優(yōu)例3、利用互補(bǔ)松弛定理求最優(yōu)解已知原問(wèn)題的最優(yōu)解是maxs.t.求對(duì)偶問(wèn)題的最優(yōu)解。對(duì)偶變量為mins.t.則對(duì)偶問(wèn)題為設(shè)對(duì)偶問(wèn)題的最優(yōu)解為將 代入原問(wèn)題約束條件得解：由互補(bǔ)松弛性知又故對(duì)偶問(wèn)題的最優(yōu)解為得2022/9/2435例3、利用互補(bǔ)松弛定理求最優(yōu)解已知原問(wèn)題的最優(yōu)解是maxs.例4、利用互補(bǔ)松弛定理求最優(yōu)解已知其對(duì)偶問(wèn)題的最優(yōu)解是mins.t.求原問(wèn)題的最優(yōu)解。對(duì)偶問(wèn)題為設(shè)原問(wèn)題的最優(yōu)解為解：mins.t.將 代入原問(wèn)題約

18、束條件得：(2)、(3)、(4)為嚴(yán)格不等式由互補(bǔ)松弛性知又因由互補(bǔ)松弛性知得故原問(wèn)題最優(yōu)解為2022/9/2436例4、利用互補(bǔ)松弛定理求最優(yōu)解已知其對(duì)偶問(wèn)題的最優(yōu)解是min6、強(qiáng)對(duì)偶性（對(duì)偶定理）定理：若原問(wèn)題有最優(yōu)解，則其對(duì)偶問(wèn)題也一定具有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值相等。s.t.用單純形法求原問(wèn)題的最優(yōu)解：2022/9/24376、強(qiáng)對(duì)偶性（對(duì)偶定理）定理：若原問(wèn)題有最優(yōu)解，則其對(duì)偶問(wèn)題s.t.2022/9/2438s.t.2022/9/2438非基變量基變量XsXIA0C基變量 基變量 基可 系數(shù) 行解 0 Xs bXB XNB NCB CN2022/9/2439非基變量基變量XsXI

19、A0C基變量 基變量 基可 XB I 0CB CNB NXB XN單純形法計(jì)算的矩陣描述非基變量基變量XsI0基變量 基變量 基可 系數(shù) 行解 0 Xs b基變量非基變量XB基變量 基變量 基可 系數(shù) 行解 CNCBB-1N B-1N B-1XN XsB-1bCB進(jìn)行初等行變換CBB-1 若CNCBB-1N 0CBB-1 0 最優(yōu)解X*= B-1bB-1存在2022/9/2440 XB I 0CB CNB NXB 6、強(qiáng)對(duì)偶性（對(duì)偶定理） min w =bTY s.t. ATY CT Y 0 若CNCBB-1N 0CBB-1 0 最優(yōu)解X*= B-1b令YT= CBB-1，則有CNYT N 0

20、，Y 0因CBYTB = 0，故CYT A 0，即AT Y CT ，說(shuō)明Y是D的可行解 max z=CX s.t. AX b X 0此時(shí)目標(biāo)函數(shù)值w =bTY=YTb= CBB-1b原問(wèn)題的最優(yōu)值 z= CB-1b= CBB-1b由最優(yōu)性定理知，Y是D的最優(yōu)解。定理：若原問(wèn)題有最優(yōu)解，則其對(duì)偶問(wèn)題也一定具有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值相等。2022/9/24416、強(qiáng)對(duì)偶性（對(duì)偶定理） min w =bTY 若C6、強(qiáng)對(duì)偶性（對(duì)偶定理）推論：若一對(duì)對(duì)偶問(wèn)題都有可行解，則它們都有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值必相等。定理：若原問(wèn)題有最優(yōu)解，則其對(duì)偶問(wèn)題也一定具有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值相等。 互為對(duì)

21、偶的兩個(gè)問(wèn)題，只會(huì)出現(xiàn)以下三種關(guān)系： 都有最優(yōu)解，且最優(yōu)值相等 一個(gè)有無(wú)界解，另一個(gè)無(wú)可行解； 兩個(gè)都無(wú)可行解。2022/9/24426、強(qiáng)對(duì)偶性（對(duì)偶定理）推論：若一對(duì)對(duì)偶問(wèn)題都有可行解，則它判斷下列說(shuō)法是否正確，為什么？1、如果線性規(guī)劃問(wèn)題存在可行解，則其對(duì)偶問(wèn)題也一定存在可行解。2、如果線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題也一定無(wú)可行解。3、如果線性規(guī)劃問(wèn)題的原問(wèn)題和對(duì)偶問(wèn)題都具有可行解，則該線性規(guī)劃一定具有有限最優(yōu)解。2022/9/2443判斷下列說(shuō)法是否正確，為什么？1、如果線性規(guī)劃問(wèn)題存在可行解對(duì)偶問(wèn)題的基本性質(zhì)一個(gè)問(wèn)題max另一問(wèn)題min應(yīng)用有最優(yōu)解有最優(yōu)解強(qiáng)對(duì)偶性無(wú)界解（有

22、可行解）無(wú)可行解無(wú)界性（證無(wú)最優(yōu)解）無(wú)可行解無(wú)界解（有可行解）已知最優(yōu)解求最優(yōu)解互補(bǔ)松弛性2022/9/2444對(duì)偶問(wèn)題的基本性質(zhì)一個(gè)問(wèn)題max另一問(wèn)題min應(yīng)用有最優(yōu)解有7、原問(wèn)題與對(duì)偶問(wèn)題單純形表間的性質(zhì)？ XB I 0CB CNB NXB XN非基變量基變量XsI0基變量 基變量 基可 系數(shù) 行解 0 Xs b基變量非基變量XB基變量 基變量 基可 系數(shù) 行解 CNCBB-1N B-1N B-1XN XsB-1bCBYT= CBB-1CBB-1 2022/9/24457、原問(wèn)題與對(duì)偶問(wèn)題單純形表間的性質(zhì)？ XB I 0CB Duality Theory 線性規(guī)劃的對(duì)偶問(wèn)題 對(duì)偶問(wèn)題的經(jīng)濟(jì)

23、解釋影子價(jià)格 對(duì)偶單純形法 靈敏度分析 對(duì)偶問(wèn)題的基本性質(zhì)第二章 線性規(guī)劃的對(duì)偶理論2022/9/2446Duality Theory 線性規(guī)劃的對(duì)偶問(wèn)題 對(duì)偶問(wèn)題的第一步：找到一個(gè)滿足最優(yōu)檢驗(yàn)的初始基本解；第二步：檢驗(yàn)當(dāng)前解是否可行。若可行，已得到最優(yōu)，否則轉(zhuǎn)入下一步。第三步：選擇b最小一行的變量作為換出變量第四步：換入變量mincj-zj/aij(負(fù)數(shù)和零不參與比較)第五步：迭代運(yùn)算，到第二步。對(duì)偶單純形法2022/9/2447第一步：找到一個(gè)滿足最優(yōu)檢驗(yàn)的初始基本解；對(duì)偶單純形法202對(duì)偶單純形法 Max z=-6x1-3x2-2x3例：2022/9/2448對(duì)偶單純形法 Max z=-

24、6x1-3x2-2x3例：20cj-6-3-2000cBxBbx1x2x3x4x5x60 x4-20-1-1-11000 x5-6-1/2-1/2-1/40100 x6-10-2-1-1001zj000000cj-zj-6-3-2000對(duì)偶單純形法找到一個(gè)滿足最優(yōu)檢驗(yàn)的初始基本解檢驗(yàn)當(dāng)前解不可行，選擇b最小一行的變量作為換出變量；換入變量mincj-zj/aij2022/9/2449cj-6-3-2000cBxBbx1x2x3x4x5x60 xcj-6-3-2000cBxBbx1x2x3x4x5x6-2x320111-1000 x5-1-1/4-1/40-1/4100 x610100-101z

25、j-2-2-2200cj-zj-4-10-200對(duì)偶單純形法檢驗(yàn)當(dāng)前解不可行，選擇b最小一行的變量作為換出變量；換入變量mincj-zj/aij2022/9/2450cj-6-3-2000cBxBbx1x2x3x4x5x6-2cj-6-3-2000cBxBbx1x2x3x4x5x6-2 x3 16001-240-3 x2 41101-400 x6 10-100-101zj-3-3-2140cj-zj-300-1-40對(duì)偶單純形法2022/9/2451cj-6-3-2000cBxBbx1x2x3x4x5x6-2 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格Duality Theory 線性規(guī)劃的對(duì)偶問(wèn)題 對(duì)偶單純

26、形法 靈敏度分析 對(duì)偶問(wèn)題的基本性質(zhì)第二章 線性規(guī)劃的對(duì)偶理論2022/9/2452 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格Duality Theor bi 代表第i種資源的擁有量；yi*代表在資源最優(yōu)利用條件下對(duì)第i種資源的單位估價(jià)。這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價(jià)。 一、影子價(jià)格的概念設(shè) xj 表示第 j 種產(chǎn)品每天的產(chǎn)量設(shè) yj 表示第 j 種原料的收費(fèi)單價(jià) 由對(duì)偶定理知當(dāng)P問(wèn)題求得最優(yōu)解X*時(shí)，D問(wèn)題也得到最優(yōu)解Y*，且有影子價(jià)格2022/9/2453 bi 代表第i種資源的擁有量；yi*代表在資源最優(yōu)利若 ，則若 ，則當(dāng)某個(gè)右端常數(shù)bi bi+1時(shí)一、影子價(jià)格

27、的概念由 得說(shuō)明 的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下， 每增加一個(gè)單位時(shí)目標(biāo)函數(shù)z的增量邊際價(jià)格說(shuō)明若某資源 未被充分利用，則該種資源的影子價(jià)格為0；若某資源的影子價(jià)格不為0，則說(shuō)明已有資源在已消耗完畢。2022/9/2454若 ，則若 ，則當(dāng)某個(gè)右端常數(shù)二、在經(jīng)營(yíng)管理中的應(yīng)用y1* = 2y2* = 1y3* = 0Y*T= CBB-1CBB-1 2022/9/2455二、在經(jīng)營(yíng)管理中的應(yīng)用y1* = 2Y*T= CBB-1C二、在經(jīng)營(yíng)管理中的應(yīng)用y1* = 2y2* = 1y3* = 0若原料A增加1單位，該廠按最優(yōu)計(jì)劃安排生產(chǎn)可多獲利200元；若原料B增加1單位，可多獲利100元;原料C本已剩余，再增加不會(huì)帶來(lái)收益。1、指示企業(yè)內(nèi)部挖潛的方向影子價(jià)格能說(shuō)明增加哪種資源對(duì)增加經(jīng)濟(jì)效益最有利 2022/9/2456二、在經(jīng)營(yíng)管理中的應(yīng)用y1* = 2若原料A增加1單位，該廠二、在經(jīng)營(yíng)管理中的應(yīng)用y1* = 2y2* = 1y3* = 02、在企業(yè)經(jīng)營(yíng)決策中的作用當(dāng)某種資源的影子價(jià)格高于市場(chǎng)價(jià)格時(shí)：當(dāng)某種資源的影子價(jià)格低于市場(chǎng)價(jià)格