第1章線性規(guī)劃及對偶問題ppt課件

1、第1章 線性規(guī)劃及對偶問題課時：8學(xué)時主講：關(guān)文忠教學(xué)要求與主要內(nèi)容：教學(xué)要求與主要內(nèi)容：n教學(xué)要求：教學(xué)要求：n通過本章的學(xué)習(xí)，了解線性規(guī)劃及其對偶問題的基本理論；通過本章的學(xué)習(xí)，了解線性規(guī)劃及其對偶問題的基本理論；掌握線性規(guī)劃求解的基本方法掌握線性規(guī)劃求解的基本方法單純形法單純形法,了解對偶單了解對偶單純形方法，熟悉靈敏度分析的方法；會建構(gòu)線性規(guī)劃模型，純形方法，熟悉靈敏度分析的方法；會建構(gòu)線性規(guī)劃模型，并會用并會用“規(guī)劃求解模板進行求解。規(guī)劃求解模板進行求解。n主要內(nèi)容：主要內(nèi)容：n1.1 線性規(guī)劃模型線性規(guī)劃模型n1.2 線性規(guī)劃求解基本方法線性規(guī)劃求解基本方法n1.2.1 圖解法圖解

2、法n1.2.2 單純形法簡介單純形法簡介n1.3 線性規(guī)劃對偶問題線性規(guī)劃對偶問題n1.4 線性規(guī)劃應(yīng)用舉例線性規(guī)劃應(yīng)用舉例n本章小結(jié)本章小結(jié)1.1 線性規(guī)劃線性規(guī)劃(Linear Programming)模型模型n1.1.1 問題的提出問題的提出產(chǎn)品甲產(chǎn)品甲 產(chǎn)品乙產(chǎn)品乙生產(chǎn)能力生產(chǎn)能力( (小時小時) )設(shè)備設(shè)備A A7 73 3210210設(shè)備設(shè)備B B4 45 5200200設(shè)備設(shè)備C C2 24 4180180計劃利潤計劃利潤( (元元/ /件件) )70706565設(shè)：產(chǎn)品甲生產(chǎn)設(shè)：產(chǎn)品甲生產(chǎn)x1，產(chǎn)品乙生產(chǎn)，產(chǎn)品乙生產(chǎn)x2目的：目的：Max z=70 x1+65x2約束條件：約束

3、條件：設(shè)備設(shè)備A生產(chǎn)能力限制：生產(chǎn)能力限制：7x1+3x2210設(shè)備設(shè)備B生產(chǎn)能力限制：生產(chǎn)能力限制：4x1+5x2200設(shè)備設(shè)備C生產(chǎn)能力限制：生產(chǎn)能力限制：2x1+4x21801212121212max70657321045200. .24180,0zxxxxxxstxxx x產(chǎn)量非負限制：產(chǎn)量非負限制： x1，x20決策變量決策變量決策變量決策變量目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件三要素：三要素：1.決策變量決策變量2.目標(biāo)函數(shù)目標(biāo)函數(shù)3.約束條件約束條件1.1.2 線性規(guī)劃模型線性規(guī)劃模型n1.適用條件：適用條件：n（1優(yōu)化條件優(yōu)化條件:問題目標(biāo)最大化、最小化的要求；問題目標(biāo)最大化、最小

4、化的要求；n（2約束條件約束條件:問題目標(biāo)受一系列條件的限制；問題目標(biāo)受一系列條件的限制；n（3選擇條件選擇條件:實現(xiàn)目標(biāo)存在多種備選方案；實現(xiàn)目標(biāo)存在多種備選方案；n（4非負條件的選擇非負條件的選擇:根據(jù)問題的實際意義決定是否非負。根據(jù)問題的實際意義決定是否非負。n2. 構(gòu)建線性規(guī)劃模型的步驟構(gòu)建線性規(guī)劃模型的步驟n（1科學(xué)選擇決策變量科學(xué)選擇決策變量n（2根據(jù)實際問題的背景材料，找出所有的約束條件根據(jù)實際問題的背景材料，找出所有的約束條件n（3明確目標(biāo)要求明確目標(biāo)要求n（4確定是否增加決策變量的非負條件確定是否增加決策變量的非負條件 例2nMin z=2x1+6x2+5x3+4x4+3x5

5、n 0.50 x1+2.00 x2+3.00 x3+1.50 x4+0.80 x585n 0.10 x1+0.06x2+0.04x3+0.15x4+0.20 x55n 0.08x1+0.70 x2+0.35x3+0.25x4+0.02x518n x1x50飼料飼料 營養(yǎng)甲營養(yǎng)甲( (克克/ /公斤公斤) ) 營養(yǎng)乙營養(yǎng)乙( (克克/ /公斤公斤) ) 營養(yǎng)丙營養(yǎng)丙( (克克/ /公斤公斤) ) 成本成本( (元元/ /公斤公斤) )1 10 050500 010100 008082 22 22 200000 006060 070706 63 33 300000 004040 035355 54

6、 41 150500 015150 025254 45 50 080800 020200 002023 3需要需要85克克5克克18克克設(shè)設(shè)X1X2X3X4x5由決策變量、目標(biāo)函數(shù)和約束條件構(gòu)成的問題稱為規(guī)劃問題，如果決策變量為可由決策變量、目標(biāo)函數(shù)和約束條件構(gòu)成的問題稱為規(guī)劃問題，如果決策變量為可控連續(xù)變量，目標(biāo)函數(shù)和約束條件則是決策變量的線性函數(shù)，則稱為線性規(guī)劃問控連續(xù)變量，目標(biāo)函數(shù)和約束條件則是決策變量的線性函數(shù)，則稱為線性規(guī)劃問題。（題。（P12例例1.3）3. 線性規(guī)劃模型表示形式線性規(guī)劃模型表示形式1 122()nnMax Min Zc xc xc x11 11221121 122

7、2221 12212(. .(,0nnnnmmmnnmna xa xa xba xa xa xbsta xa xa xbx xx 或 ，）或 ，）或 ，）(1,2, )jxjn決策變量；決策變量；(1,2, )jcjn目標(biāo)函數(shù)系數(shù)、價值系數(shù)或費用系數(shù)；目標(biāo)函數(shù)系數(shù)、價值系數(shù)或費用系數(shù)；(1,2, )ib im右端項或資源常數(shù)；右端項或資源常數(shù)；(1,2, ;1,2, )ija im jn 稱為約束系數(shù)或技術(shù)系數(shù)。稱為約束系數(shù)或技術(shù)系數(shù)。（1一般形式：一般形式：（2集合形式：集合形式：12nxxXx111212122212nnmmmnaaaaaaAaaa1()njjjMax Min Zc x1(

8、1,2,). .0(1,2, )nijjijja xb imstxjn 或，）1()njjjMax Min Zc x1(. .0(1,2, )njjjjp xbstxjn 或，）12mbbbb12,(1,2, )jjjmjaapjna（3向量形式：向量形式：()Max Min ZCX(. .0AXbstX 或，）（4矩陣形式：矩陣形式：12( ,)nCc cc127065MaxZxx121212127321045200. .241800,0 xxxxstxxxx【例【例3】 將線性規(guī)劃模型一般表達式化為矩陣形式。將線性規(guī)劃模型一般表達式化為矩陣形式。111221223132734524aaAa

9、aaa12( ,)TXx x12( ,)(70,65)Cc c123210200180bbbb12(70,65)xMaxZx.0AXbstX解解:12732104520024180 xxMaxZCX設(shè)設(shè):1.1.3 線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式1 122nnMaxZc xc xc x11 11221121 1222221 12212. .,0nnnnmmmnnmna xa xa xba xa xa xbsta xa xa xbx xx線性規(guī)劃標(biāo)準(zhǔn)模型的一般表達式：線性規(guī)劃標(biāo)準(zhǔn)模型的一般表達式： 非標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)化方法：非標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)化方法： 1.目標(biāo)函數(shù)目標(biāo)函數(shù)1njjjMinZc xZZ

10、令 11()nnjjjjjjMaxZc xc x 2.約束條件為不等式約束條件為不等式:1 122iiinnia xa xa xb引進松馳變量引進松馳變量xs:1 122iiinnsia xa xa xxb1 122iiinnia xa xa xb引進剩余變量引進剩余變量xs:1 122iiinnsia xa xa xxb4.決策變量為自由變量決策變量為自由變量:jxuv令0,0uv 5.約束右端項為負約束右端項為負:1 122iiinnia xa xa xb兩端乘兩端乘-1:03.約束條件為不等式約束條件為不等式: 12335MinZxxx121231231239234. .3260,0,x

11、xxxxstxxxxxx 無約束【例【例4】將線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)式】將線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)式解解:13(1)0,xx1132313,0 xy xyyyy 令無約束無約束122335MinZyxyy 121223122392334. .326,0ijyxyxyystyxyyx y 1223(2)()35MinZMaxZyxyy 1223(3)326yxyy 1223326yxyy(4)在第一、第三約束左端加上松弛變量在第一、第三約束左端加上松弛變量x4,x60 ，在第二約束左端減去剩余變量，在第二約束左端減去剩余變量x50 1223()35MaxZyxyy12412235122362456

12、92334. .326, , ,0yxxyxyyxstyxyyxw x u v x x x作業(yè)：P7576習(xí)題1、2，P78:8(1)9(2)建模1.2 線性規(guī)劃基本解法線性規(guī)劃基本解法n幾個基本概念幾個基本概念:n可行解：凡滿足約束條件的決策變量的取值稱為線性規(guī)劃可行解：凡滿足約束條件的決策變量的取值稱為線性規(guī)劃的可行解。的可行解。n可行域：所有可行解的集合稱為線性規(guī)劃的可行域?？尚杏颍核锌尚薪獾募戏Q為線性規(guī)劃的可行域。n最優(yōu)解：使目標(biāo)函數(shù)達到最優(yōu)值的可行解稱為線性規(guī)劃的最優(yōu)解：使目標(biāo)函數(shù)達到最優(yōu)值的可行解稱為線性規(guī)劃的最優(yōu)解最優(yōu)解 n1.2.1 圖解法圖解法(graphical met

13、hod)n步驟步驟:n(1)平面上畫出直角坐標(biāo)平面上畫出直角坐標(biāo);n(2)圖示約束條件圖示約束條件,標(biāo)出滿足所有約束條件的公共區(qū)域標(biāo)出滿足所有約束條件的公共區(qū)域(可行可行域域);n(3)圖示目標(biāo)函數(shù)的一根基線圖示目標(biāo)函數(shù)的一根基線(母線母線)按目標(biāo)值要求按目標(biāo)值要求,讓基線平讓基線平行移動行移動,直到與可行域相切為止直到與可行域相切為止,切點即為最優(yōu)解切點即為最優(yōu)解;n(4)求出切點坐標(biāo)值求出切點坐標(biāo)值,代入目標(biāo)函數(shù)求得目標(biāo)函數(shù)最優(yōu)值代入目標(biāo)函數(shù)求得目標(biāo)函數(shù)最優(yōu)值.可行域1232MaxZxx1212122108. .,0 xxxxstx x【例【例1.6】 運用圖解法求解線性規(guī)劃問題運用圖解法

14、求解線性規(guī)劃問題(5,0)3 22 618MaxZ 2x1+x2=10 x1+x2=8(2,6)x1108302 5 8x2(0,8)3x1+2x2=6四種結(jié)局四種結(jié)局:x1x2唯一最優(yōu)解x2x1無窮多最優(yōu)解x1x2無界解x2x1無可行解1.2.2 單純形法簡介n最優(yōu)解一定在可行域的頂點上最優(yōu)解一定在可行域的頂點上,將頂點坐標(biāo)代入目標(biāo)函數(shù)有將頂點坐標(biāo)代入目標(biāo)函數(shù)有:n(0,0):z=30+20=0n(5,0):z=35+20=15n(0,8):z=30+28=16n(2,6):z=32+26=18n單純形法的基本思路就是基本單純形法的基本思路就是基本可行解的轉(zhuǎn)移，先找到一個初可行解的轉(zhuǎn)移，先找

15、到一個初始基本可行解，如果不是最優(yōu)始基本可行解，如果不是最優(yōu)解，設(shè)法轉(zhuǎn)移到另一個基本可解，設(shè)法轉(zhuǎn)移到另一個基本可行解，并使目標(biāo)函數(shù)值不斷增行解，并使目標(biāo)函數(shù)值不斷增加，直到找到最優(yōu)解。加，直到找到最優(yōu)解。(5,0)(2,6)108302 5 8x2(0,8)x11.解的概念解的概念21 101101A123421 101011018xxxx2110:,1101NB設(shè)12:32MaxZxx例(1.6)121212210. .8,0 xxstxxx x12343200MaxZxxxx12312514321080 xxxxxxxx標(biāo)準(zhǔn)化NB3124,NBxxXXxxAXb10,(3,2),(0,0)

16、8NBbCC:(, )NNBBXAXbN BNXBXbX則(,)NNBNNBBBMaxZCXXMaxZCCC XC XXNBNXBXbNNBBmax ZC XC X1| 0,:0:NBBXXB b若:取則0AXbX:max ZCX一般地標(biāo)準(zhǔn)化n定義定義:nA為為mn階矩陣階矩陣,若若A的秩的秩為為m,B為為A中的任意中的任意mm階子矩陣階子矩陣,且行列式且行列式|B|0,則稱則稱B為線性規(guī)劃為線性規(guī)劃的一個基；的一個基；n對應(yīng)的對應(yīng)的XB為基變量；為基變量；nXN為非基變量；為非基變量；0BXX稱為基本解稱為基本解n滿足非負約束的基本解滿足非負約束的基本解為基本可行解；為基本可行解；n與基本可

17、行解對應(yīng)的與基本可行解對應(yīng)的B稱稱為可行基。為可行基。2. 基變量、目標(biāo)函數(shù)的非基變量表達基變量、目標(biāo)函數(shù)的非基變量表達3124121228xxxxxx1200 xx 由于12343200MaxZxxxx12312416210.80 xxxstxxxxx基變量的非基變量表達：基變量的非基變量表達：31241021811xxxx312410:8xbbx故11221021(3,2)(0,0)811xxxx121021(0,0)(2,3)(0,0)811xx 111112341234212222( ,)( ,)( ,)bxaac cc cc caabx3 1421313423123144242c b

18、c bcc ac axcc ac ax01mn m iiiZcb1mjjjjn m iijiczcca01n mjjjZZx當(dāng)j0時，Z可進一步增大，稱為檢驗數(shù)。3124(3,2)(0,0)xxZxx目標(biāo)函數(shù)的非基變量表達：目標(biāo)函數(shù)的非基變量表達：3.單純形法計算步驟單純形法計算步驟cj3200cBxBbx1x2x3x40 x31021100 x481101j=cj-zj320012:32MaxZxx例121212210. .8,0 xxstxxx x12343200MaxZxxxx123124210. .80(1,2,3,4)jxxxstxxxxj解：解：1標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化2找出初始基本可行解，

19、列出初始單純形表找出初始基本可行解，列出初始單純形表3判別：求出檢驗數(shù)判別：求出檢驗數(shù)j=cj-zj，當(dāng)所有，當(dāng)所有j0,找到最優(yōu)解，否則轉(zhuǎn)第找到最優(yōu)解，否則轉(zhuǎn)第4 步步（1找出最大檢驗數(shù)找出最大檢驗數(shù)j，對應(yīng)的變量為引，對應(yīng)的變量為引進變量入基變量）。（進變量入基變量）。（x1）（2根據(jù)最小比值原則確定離去變量根據(jù)最小比值原則確定離去變量出基變量）。（出基變量）。（x3）max0kjjj 4找出新的基本可行解找出新的基本可行解（3用引進變量替換離去變量，列出新用引進變量替換離去變量，列出新的單純形表的單純形表cj3200cBxBbx1x2x3x4 0 x310211050 x4811018j

20、=cj-zj3200min0ilikiklkbbaaaa.主元素行主元素行=原主元素行原主元素行/主主b.主元素列：新表中為單位向量，除主元主元素列：新表中為單位向量，除主元素位為素位為“1”，其余為，其余為“0”c.其它行列數(shù)學(xué)按矩形規(guī)則得到其它行列數(shù)學(xué)按矩形規(guī)則得到0-3/21/20j=cj-zj61-1/21/203x401001/21/215x13 x4x3x2x1bxBcB0023cj-1-100j=cj-zj2-1106x22-11012x13 x4x3x2x1bxBcB0023cjABC主0/1CCB ABB 主A=0，則該行數(shù)字不變，則該行數(shù)字不變B=0，則該列數(shù)學(xué)不變，則該列

21、數(shù)學(xué)不變最優(yōu)解：最優(yōu)解：x1=4,x2=2,x6=4,其它其它=0最優(yōu)值：最優(yōu)值：max z=24+32=14作業(yè)：作業(yè)：P26：21），），33）演示實驗演示實驗線性規(guī)劃線性規(guī)劃Excel求解求解1. ExcelORM線性規(guī)劃線性規(guī)劃目標(biāo)函數(shù)目標(biāo)函數(shù)max,變量個數(shù)變量個數(shù)2,約束個數(shù)約束個數(shù)2,確定生成電子表模型確定生成電子表模型并輸入數(shù)據(jù)并輸入數(shù)據(jù).12:32MaxZxx例121212210. .8,0 xxstxxx x2. 調(diào)用規(guī)劃求解模板調(diào)用規(guī)劃求解模板,設(shè)置規(guī)劃求解參數(shù)對設(shè)置規(guī)劃求解參數(shù)對話框話框(工具工具規(guī)劃求解規(guī)劃求解)3. 求解求解1.3 線性規(guī)劃的對偶問題n假若該企業(yè)打算

22、放棄生假若該企業(yè)打算放棄生產(chǎn)產(chǎn)品的項目，而將所產(chǎn)產(chǎn)品的項目，而將所有設(shè)備出租，收取租金，有設(shè)備出租，收取租金，如何確定三種設(shè)備單位如何確定三種設(shè)備單位臺時的租金，才能使企臺時的租金，才能使企業(yè)不至于蝕本？業(yè)不至于蝕本？12yy每臺時估價12min108wyy總臺時收入1223yy122yy12121223. .2,0yystyyy y1.3.1 線性規(guī)劃的對偶模型線性規(guī)劃的對偶模型生產(chǎn)產(chǎn)品生產(chǎn)產(chǎn)品I的臺時出租收入不小于產(chǎn)品的臺時出租收入不小于產(chǎn)品I的利潤的利潤生產(chǎn)產(chǎn)品生產(chǎn)產(chǎn)品II的臺時出租收入不小于產(chǎn)品的臺時出租收入不小于產(chǎn)品II的利潤的利潤12min108wyy(1)(2)(2)式稱為式稱為

23、(1)式的對偶問題式的對偶問題1232MaxZxx121212210.8,0 xxstxxx x 原問題原問題 對偶問題對偶問題目標(biāo)函數(shù)目標(biāo)函數(shù)max約束右端項約束右端項目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù)約約 m個個束束 條條 件件 n個個變變 0量量 無約束無約束 0Min目標(biāo)函數(shù)中的系數(shù)目標(biāo)函數(shù)中的系數(shù)約束右端項約束右端項m 0 變變無約束無約束 量量0n個個 約約 束束 條條 件件11max(1,)0(1, )njjjnijjijjzc xa xbimxjn原問題11min(1, )0(1,)niijmijijiiwb ya ycjnyim對偶問題 規(guī)范形式規(guī)范形式非規(guī)范形式可按下面方法轉(zhuǎn)換非規(guī)范

24、形式可按下面方法轉(zhuǎn)換n對偶單純形法迭代步驟：對偶單純形法迭代步驟：n1列出單純形表，表中原列出單純形表，表中原問題檢驗數(shù)為對偶問題基本問題檢驗數(shù)為對偶問題基本可行解可行解n2表中基變量列為對偶問表中基變量列為對偶問題檢驗數(shù)題檢驗數(shù)n當(dāng)所有檢驗數(shù)當(dāng)所有檢驗數(shù)0時，找到最時，找到最優(yōu)解，否則轉(zhuǎn)第三步優(yōu)解，否則轉(zhuǎn)第三步n3（1找出最小檢驗數(shù)，找出最小檢驗數(shù)，對應(yīng)變量為離去變量對應(yīng)變量為離去變量n （2對偶問題基本可行對偶問題基本可行解與離去變量所在行之最小解與離去變量所在行之最小比值比值n=minj/akj |akj=0則無可行解則無可行解)確定主元素，主元素對應(yīng)變確定主元素，主元素對應(yīng)變量為引進變

25、量量為引進變量n （3將引進變量替換離將引進變量替換離去變量列出新的單純形表，去變量列出新的單純形表，轉(zhuǎn)轉(zhuǎn)2cj-10-800cBYBby1y2y3y400y3y4-3-2-2-1-1-11001cj-zj-10-800 581.3.2 對偶單純形法對偶單純形法12121223. .2,0yystyyy y12:min108wyy例123125232yyyyyy 1234:max10800zyyyy標(biāo)準(zhǔn)化0-1/21/213/2y1-100-5-30cj-zj5/211-1/2-1/20-1/2y40y4y3y2y1bYBcB00-8-10cj原問題最終單純形表原問題最終單純形表原問題原問題

26、對偶問題對偶問題 解解 檢驗數(shù)檢驗數(shù)檢驗數(shù)檢驗數(shù) 解解對偶問題的解稱為原問題的影子價格對偶問題的解稱為原問題的影子價格;影子價格可由檢驗數(shù)直接得到影子價格可由檢驗數(shù)直接得到.1-1011y1-10-6-200cj-zj-21101y2-8y4y3y2y1bYBcB00-8-10cjcj3200cBxBbx1x2x3x43x12101-12x2601-12j=cj-zj00-1-10-1/21/213/2y1-100-5-30cj-zj5/211-1/2-1/20-1/2y40y4y3y2y1bYBcB00-8-10cj1.4應(yīng)用舉例(P54運作實例1-1)媒體媒體可達消費者可達消費者數(shù)數(shù)(人人

27、)單位廣告成單位廣告成本本(元元)媒體可提供廣媒體可提供廣告數(shù)告數(shù)(個個)單位廣告影響單位廣告影響力數(shù)據(jù)力數(shù)據(jù)電視電視I(非黃金檔非黃金檔)x11500015001565電視電視2(黃金檔黃金檔)x22000040001090網(wǎng)絡(luò)網(wǎng)絡(luò)x34000020004030報紙報紙x4120004502040雜志雜志x5100006001520解解:1.決策變量決策變量:xj2.目的目的:廣告影響力最大廣告影響力最大max Z=65x1+90 x2+30 x3+40 x4+20 x53.約束條件約束條件:可達消費者人數(shù)限制可達消費者人數(shù)限制:15000 x1+20000 x2+40000 x3+12000 x4+10000 x52000000電視廣告數(shù)量限制電視廣告數(shù)量限制: x1+x210廣告總預(yù)算限制廣告總預(yù)算限制: 1500 x1+4000 x2+2000 x3+450 x4+600 x5300000電視廣告限制電