線(xiàn)性規(guī)劃及其對(duì)偶問(wèn)題

1、線(xiàn)性規(guī)劃及其對(duì)偶問(wèn)題線(xiàn)性規(guī)劃及其對(duì)偶問(wèn)題1 線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型(1) 線(xiàn)性規(guī)劃問(wèn)題線(xiàn)性規(guī)劃問(wèn)題例、生產(chǎn)組織與計(jì)劃問(wèn)題例、生產(chǎn)組織與計(jì)劃問(wèn)題a, b a, b 各生產(chǎn)多少各生產(chǎn)多少, , 可獲最大利潤(rùn)可獲最大利潤(rùn)? ?可用資源可用資源煤煤勞動(dòng)力勞動(dòng)力倉(cāng)庫(kù)倉(cāng)庫(kù)a b1 23 20 2單位利潤(rùn)單位利潤(rùn)40 50306024解解: 設(shè)產(chǎn)品設(shè)產(chǎn)品a, b產(chǎn)量分別為變量產(chǎn)量分別為變量x1， x2可以建立如下的數(shù)學(xué)模型：可以建立如下的數(shù)學(xué)模型：max z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目標(biāo)函數(shù)目標(biāo)

2、函數(shù)約束條件約束條件可用資源可用資源煤煤勞動(dòng)力勞動(dòng)力倉(cāng)庫(kù)倉(cāng)庫(kù)a b1 23 20 2單位利潤(rùn)單位利潤(rùn)40 50306024 例 某建筑設(shè)計(jì)院設(shè)計(jì)每萬(wàn)辦公建筑和工業(yè)廠(chǎng)房需要的建筑師、結(jié)構(gòu)工程師、設(shè)備工程師和電氣工程師的平均人數(shù)列在表。問(wèn)該院應(yīng)如何安排設(shè)計(jì)任務(wù)，才能使設(shè)計(jì)費(fèi)收入最大?專(zhuān)業(yè)建筑物建筑結(jié)構(gòu)設(shè)備電器設(shè)計(jì)費(fèi)收入（萬(wàn)元/萬(wàn) ）辦公建筑532136工業(yè)廠(chǎng)房121220全院現(xiàn)有專(zhuān)業(yè)人數(shù)28261210解設(shè)辦公建筑和工業(yè)廠(chǎng)房各承攬、萬(wàn)。根據(jù)題意max z36x120 x2 5 x1x228 s.t 3 x12x228 2 x1x212 x12x210 x1 、x2 0 2.9m 2.9m鋼筋架子鋼

3、筋架子100100個(gè)，每個(gè)需用個(gè)，每個(gè)需用 2.1m 2.1m 各各1 1，原料長(zhǎng)，原料長(zhǎng)7.4m7.4m 1.5m 1.5m求：如何下料，使得殘余料頭最少。求：如何下料，使得殘余料頭最少。解：首先列出各種可能的下料方案；解：首先列出各種可能的下料方案； 計(jì)算出每個(gè)方案可得到的不同長(zhǎng)度鋼筋的數(shù)量及殘余計(jì)算出每個(gè)方案可得到的不同長(zhǎng)度鋼筋的數(shù)量及殘余料頭長(zhǎng)度；料頭長(zhǎng)度； 確定決策變量；確定決策變量； 根據(jù)下料目標(biāo)確定目標(biāo)函數(shù)；根據(jù)下料目標(biāo)確定目標(biāo)函數(shù)； 根據(jù)不同長(zhǎng)度鋼筋的需要量確定約束方程。根據(jù)不同長(zhǎng)度鋼筋的需要量確定約束方程。例、合理下料問(wèn)題例、合理下料問(wèn)題設(shè)按第設(shè)按第i i種方案下料的原材料為

4、種方案下料的原材料為x xi i根根8 , 7 , 6 , 5 , 4 , 3 , 2 , 1100432030100002302010000002. .4 . 18 . 02 . 01 . 109 . 03 . 01 . 087654321876543218765432187654321ixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxzmini為大于零的整數(shù)，組合方案組合方案 1 2 3 4 5 6 7 8 2.9m 2 1 1 1 0 0 0 0 2.1m 0 2 1 0 3 2 1 0 1.5m 1 0 1 3 0 2 3 4 合合 計(jì)計(jì) 7.3m 7.1m 6.

5、5m 7.4m 6.3m 7.2m 6.6m 6.0m 料料 長(zhǎng)長(zhǎng) 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 料料 頭頭 0.1m 0.3m 0.9m 0.0m 1.1m 0.2m 0.8m 1.4m例、運(yùn)輸問(wèn)題例、運(yùn)輸問(wèn)題 工工 廠(chǎng)廠(chǎng) 1 2 3 庫(kù)存庫(kù)存 倉(cāng)倉(cāng) 1 2 1 3 50 2 2 2 4 30 庫(kù)庫(kù) 3 3 4 2 10 需求需求 40 15 35運(yùn)輸運(yùn)輸單價(jià)單價(jià)求：求：運(yùn)輸費(fèi)用最小的運(yùn)輸方案運(yùn)輸費(fèi)用最小的運(yùn)輸方案。解：設(shè)解：設(shè)x xijij為為i i 倉(cāng)庫(kù)運(yùn)到倉(cāng)庫(kù)運(yùn)到j(luò) j工廠(chǎng)的產(chǎn)品數(shù)量工廠(chǎng)的產(chǎn)品數(shù)量 其中：其中：i i 1 1，2 2，3

6、 3 j j 1 1，2 2，3 3min z= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 + x12+ x13 = = 50 x21 + x22+ x23 = = 30 x31 + x32+ x33 = = 10 x11 + x21+ x31 = 40 x12 + x22+ x32 = 15x13 + x23+ x33 = 35 xij 0s.t(2) 線(xiàn)性規(guī)劃問(wèn)題的特點(diǎn)線(xiàn)性規(guī)劃問(wèn)題的特點(diǎn)l決策變量：決策變量： ( (x x1 1 x xn n) )t t 代表某一方案，代表某一方案， 決策者要考慮決策者要考慮和控制的因素非負(fù)

7、；和控制的因素非負(fù)；l目標(biāo)函數(shù)：目標(biāo)函數(shù)：z=(z=(x x1 1 x xn n) ) 為線(xiàn)性函數(shù)，求為線(xiàn)性函數(shù)，求z z極大或極小極大或極小; ;l約束條件：可用線(xiàn)性等式或不等式表示約束條件：可用線(xiàn)性等式或不等式表示. .具備以上三個(gè)要素的問(wèn)題就稱(chēng)為具備以上三個(gè)要素的問(wèn)題就稱(chēng)為 線(xiàn)性規(guī)劃問(wèn)題線(xiàn)性規(guī)劃問(wèn)題。0,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxczminmax目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件(3) 線(xiàn)性規(guī)劃模型一般形式線(xiàn)性規(guī)劃模型一般形式隱含的假設(shè)隱含的假設(shè)l比例性：決策變量變化引起目標(biāo)

8、的改變量與決策變量改比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成正比變量成正比l可加性：每個(gè)決策變量對(duì)目標(biāo)和約束的影響?yīng)毩⒂谄渌杉有裕好總€(gè)決策變量對(duì)目標(biāo)和約束的影響?yīng)毩⒂谄渌兞孔兞縧連續(xù)性：每個(gè)決策變量取連續(xù)值連續(xù)性：每個(gè)決策變量取連續(xù)值l確定性：線(xiàn)性規(guī)劃中的參數(shù)確定性：線(xiàn)性規(guī)劃中的參數(shù)aij , bi , cj為確定值為確定值2 線(xiàn)性規(guī)劃問(wèn)題的圖解法線(xiàn)性規(guī)劃問(wèn)題的圖解法 20,.1xbaxtscxzminmax定義定義1 1：滿(mǎn)足約束：滿(mǎn)足約束(2)(2)的的x=(x=(x x1 1 x xn n) )t t稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題的稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題的可行解可行解，全部可行解的集合稱(chēng)為

9、，全部可行解的集合稱(chēng)為可行域可行域。定義定義2 2：滿(mǎn)足：滿(mǎn)足(1)(1)的可行解稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題的的可行解稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解最優(yōu)解。例例1 max z=40x1+ 50x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0 0s.t解：解：(1)(1)、確定可行域、確定可行域 x1+2x2 30 3x1+2x2 60 2x2 24 x x1 1 0 0 x x2 2 0 02030100102030x2dabc2x2 24x1+2x2 303x1+2x2 60x x1 1 0 0x x2 2 0 0可行域可行域(2)(2)、求最優(yōu)解、求最優(yōu)解最優(yōu)解：最優(yōu)解：x*

10、 = (15,7.5) zmax =975z=40x1+50x20=40x1+50x2 (0,0)， (10,-8)c點(diǎn)：點(diǎn)： x1+2x2 =30 3x1+2x2 =600203010102030x1x2dabc最優(yōu)解最優(yōu)解z=975可行解可行解z=0等值線(xiàn)等值線(xiàn)例例2、 max z=40x1+ 80x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0 0s.t解：解：(1)(1)、確定可行域與上例完全相同。、確定可行域與上例完全相同。 (2)(2)、求最優(yōu)解、求最優(yōu)解0203010102030dabc最優(yōu)解最優(yōu)解z=1200最優(yōu)解：最優(yōu)解：bcbc線(xiàn)段線(xiàn)段最優(yōu)解：

11、最優(yōu)解：bcbc線(xiàn)段線(xiàn)段b b點(diǎn)：點(diǎn)：x x(1)(1)=(6,12) c=(6,12) c點(diǎn)：點(diǎn)：x x(2)(2)=(15,7.5)=(15,7.5)x=x= x x(1)(1)+(1-+(1- )x)x(2) (2) ( (0 0 1 1) ) max z=1200 max z=1200 x1 6 15 x2 12 7.5x= = +(1- )x1 =6 +(1- )15x2=12 +(1- )7.5x1 =15-9 x2 =7.5+4.5 (0 1)例例3、 max z=2x1+ 4x2 2x1+x2 8-2x1+x2 2x1 , x2 0s.tz=08246x240x1-2x1+x2

12、 22x1+x2 8x1 0x2 0可行域可行域無(wú)界無(wú)界無(wú)有限最優(yōu)解無(wú)有限最優(yōu)解無(wú)有限最優(yōu)解無(wú)有限最優(yōu)解可行域可行域無(wú)上界無(wú)上界例例4、 max z=3x1+2x2 -x1 -x2 1x1 , x2 0無(wú)可行域無(wú)可行域無(wú)可行解無(wú)可行解-1x2-1x10s.tx2 0x1 0-x1 -x2 1直觀(guān)結(jié)論直觀(guān)結(jié)論n線(xiàn)性規(guī)劃問(wèn)題的解有四種情況線(xiàn)性規(guī)劃問(wèn)題的解有四種情況q唯一最優(yōu)解唯一最優(yōu)解q無(wú)窮多最優(yōu)解無(wú)窮多最優(yōu)解q無(wú)有限最優(yōu)解無(wú)有限最優(yōu)解q無(wú)可行解無(wú)可行解n若線(xiàn)性規(guī)劃問(wèn)題有解，則可行域是一個(gè)凸多邊形若線(xiàn)性規(guī)劃問(wèn)題有解，則可行域是一個(gè)凸多邊形（或凸多面體）；（或凸多面體）；n若線(xiàn)性規(guī)劃問(wèn)題有最優(yōu)解，則

13、若線(xiàn)性規(guī)劃問(wèn)題有最優(yōu)解，則q唯一最優(yōu)解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)；唯一最優(yōu)解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)；q無(wú)窮多個(gè)最優(yōu)解對(duì)應(yīng)于可行域的一條邊；無(wú)窮多個(gè)最優(yōu)解對(duì)應(yīng)于可行域的一條邊；3 單純形法單純形法3.1 3.1 線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式3.2 3.2 線(xiàn)性規(guī)劃問(wèn)題的基本解線(xiàn)性規(guī)劃問(wèn)題的基本解3.3 3.3 單純形法的基本思想單純形法的基本思想3.1 3.1 線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式0,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxczminmax目標(biāo)函數(shù)目標(biāo)函數(shù)約束

14、條件約束條件(1) 線(xiàn)性規(guī)劃模型一般形式線(xiàn)性規(guī)劃模型一般形式價(jià)值系數(shù)價(jià)值系數(shù)決策變量決策變量技術(shù)系數(shù)技術(shù)系數(shù)右端常數(shù)右端常數(shù)0,b,bbxxxbxaxaxabxaxaxabxaxaxatsxcxcxczmaxm21nmnmnmmnnnnnn0,.21221122222121112121112211(2) 線(xiàn)性規(guī)劃模型標(biāo)準(zhǔn)形式線(xiàn)性規(guī)劃模型標(biāo)準(zhǔn)形式0.xbaxtscxzmaxncccc21mnmmnnaaaaaaaaaa212222111211nxxxx21價(jià)值向量?jī)r(jià)值向量決策向量決策向量系數(shù)矩陣系數(shù)矩陣mbbbb21右端向量右端向量(3) 線(xiàn)性規(guī)劃模型矩陣形式線(xiàn)性規(guī)劃模型矩陣形式對(duì)于各種非標(biāo)準(zhǔn)形

15、式的線(xiàn)性規(guī)劃問(wèn)題，我們總可對(duì)于各種非標(biāo)準(zhǔn)形式的線(xiàn)性規(guī)劃問(wèn)題，我們總可以通過(guò)以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式以通過(guò)以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式: :(4) 一般型向標(biāo)準(zhǔn)型的轉(zhuǎn)化一般型向標(biāo)準(zhǔn)型的轉(zhuǎn)化l目標(biāo)函數(shù)目標(biāo)函數(shù)l目標(biāo)函數(shù)為極小化目標(biāo)函數(shù)為極小化l約束條件約束條件l分兩種情況：大于、小于分兩種情況：大于、小于l決策變量決策變量l可能存在小于零的情況可能存在小于零的情況3.2 3.2 線(xiàn)性規(guī)劃問(wèn)題的基本解線(xiàn)性規(guī)劃問(wèn)題的基本解 302.1xbaxtscxzmax(1) 解的基本概念解的基本概念定義定義 在線(xiàn)性規(guī)劃問(wèn)題中，約束方程組在線(xiàn)性規(guī)劃問(wèn)題中，約束方程組(2)(2)的系的系數(shù)矩陣數(shù)矩陣a(a(假定

16、假定 ) )的任意一個(gè)的任意一個(gè) 階的非奇階的非奇異異( (可逆可逆) )的子方陣的子方陣b(b(即即 ) )，稱(chēng)為線(xiàn)性規(guī)劃，稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題的一個(gè)問(wèn)題的一個(gè)基陣基陣或或基基。mm0bnm mnmmmmmmmmnmmmnmmmaaaaaaaaaaaaaaaaaaa212122212222211211111211mmmmmmaaaaaaaaab212222111211mnmmmmnmmnmmaaaaaaaaan212221212111基陣基陣非基陣非基陣tmbxxxx21tnmmnxxxx21基基向向量量非非基基向向量量基變量基變量非基變量非基變量nbanbxxxbax bxxnbnbbnxbx

17、nbnbnxbbxnbnxbbbx11nbxxxnnxnxbbbx11令令0nx則則01bbx定義定義 在約束方程組在約束方程組(2) 中，對(duì)于中，對(duì)于一個(gè)選定的基一個(gè)選定的基b，令所有的非基變，令所有的非基變量為零得到的解，稱(chēng)為相應(yīng)于基量為零得到的解，稱(chēng)為相應(yīng)于基b的基本解。的基本解。定義定義 在基本解中，若該基本解滿(mǎn)足非負(fù)約束，在基本解中，若該基本解滿(mǎn)足非負(fù)約束，即即 ，則稱(chēng)此基本解為，則稱(chēng)此基本解為基本可行解基本可行解，簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)基可行解基可行解；對(duì)應(yīng)的基；對(duì)應(yīng)的基b稱(chēng)為稱(chēng)為可行基可行基。01bbxb基本解中最多有基本解中最多有m個(gè)非零分量。個(gè)非零分量?；窘獾臄?shù)目不超過(guò)基本解的數(shù)目不超過(guò)

18、 個(gè)。個(gè)。!mnmncmnnbnbnnnbnnbbnbnbxnbccbbcxcnxbbbcxcxcxxcccxz)()(),(111101bbxb01nbccbnnbx若若b滿(mǎn)足下列條件，稱(chēng)為滿(mǎn)足下列條件，稱(chēng)為最優(yōu)基最優(yōu)基 稱(chēng)為稱(chēng)為最優(yōu)解最優(yōu)解例例 現(xiàn)有線(xiàn)性規(guī)劃問(wèn)題現(xiàn)有線(xiàn)性規(guī)劃問(wèn)題0,24261553.221212121xxxxxxtsxxzmax試求其基本解、基本可行解。試求其基本解、基本可行解。解解: (1)首先將原問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型首先將原問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型 引入松弛變量引入松弛變量x3和和x40,2402615053.243214321432121xxxxxxxxxxxxtsxxzmax(

19、2) 求基本解求基本解由上式得由上式得10260153a2415b可能的基陣可能的基陣10260153a265312b061313b160314b021523b120524b100134b612121234!24! 2! 424c 由于所有由于所有|b| 0，所以有所以有6個(gè)基陣和個(gè)基陣和6個(gè)基本解。個(gè)基本解。242615532121xxxx對(duì)于基陣對(duì)于基陣265312b令令03x04x則則tx0043415246153131xxx對(duì)于基陣對(duì)于基陣令令02x04x則則tx0304061313b為基本可行解，為基本可行解，b13為可行基為可行基為基本可行解，為基本可行解，b12為可行基為可行基2

20、46153411xxx對(duì)于基陣對(duì)于基陣令令02x03x則則tx6005242155232xxx對(duì)于基陣對(duì)于基陣令令01x04x則則tx045120160314b021523b242155422xxx對(duì)于基陣對(duì)于基陣令令01x03x則則tx對(duì)于基陣對(duì)于基陣令令01x02x則則tx241500120524b100134b為基本可行解，為基本可行解，b24為可行基為可行基為基本可行解，為基本可行解，b34為可行基為可行基0abcdetx0043415tx0304tx6005tx241500tx18030tx045120所以，本問(wèn)所以，本問(wèn)題存在題存在6個(gè)基個(gè)基本解，其中本解

21、，其中4個(gè)為基可行個(gè)為基可行解解.(2) 幾點(diǎn)結(jié)論幾點(diǎn)結(jié)論v若線(xiàn)性規(guī)劃問(wèn)題有可行解若線(xiàn)性規(guī)劃問(wèn)題有可行解,則可行域是一個(gè)凸多邊形或則可行域是一個(gè)凸多邊形或凸多面體凸多面體(凸集凸集),且僅有有限個(gè)頂點(diǎn)且僅有有限個(gè)頂點(diǎn)(極點(diǎn)極點(diǎn));v線(xiàn)性規(guī)劃問(wèn)題的每一個(gè)基可行解都對(duì)應(yīng)于可行域上的一線(xiàn)性規(guī)劃問(wèn)題的每一個(gè)基可行解都對(duì)應(yīng)于可行域上的一個(gè)頂點(diǎn)個(gè)頂點(diǎn)(極點(diǎn)極點(diǎn));v若線(xiàn)性規(guī)劃問(wèn)題有最優(yōu)解若線(xiàn)性規(guī)劃問(wèn)題有最優(yōu)解,則最優(yōu)解必可在基可行解則最優(yōu)解必可在基可行解(極極點(diǎn)點(diǎn))上達(dá)到上達(dá)到;v線(xiàn)性規(guī)劃問(wèn)題的基可行解線(xiàn)性規(guī)劃問(wèn)題的基可行解(極點(diǎn)極點(diǎn))的個(gè)數(shù)是有限的的個(gè)數(shù)是有限的,不會(huì)超不會(huì)超過(guò)過(guò) 個(gè)個(gè).mnc上述結(jié)論說(shuō)

22、明上述結(jié)論說(shuō)明:線(xiàn)性規(guī)劃的最優(yōu)解可通過(guò)有限次運(yùn)算在基可行解中獲得線(xiàn)性規(guī)劃的最優(yōu)解可通過(guò)有限次運(yùn)算在基可行解中獲得.3.3 3.3 單純形法單純形法 (1) 單純形法的引入單純形法的引入(2)(2)表格單純形法表格單純形法 n jm+1 k 1 - cbtb*amnamjamm+1 0 am1bm* xm cm aknakjakm+1 akk ak1bk* xk ck a1na1ja1m+1 a1ka11b1* x1 c1 xn xjxm+1xm xk x1 b*xbcb cn cjcm+1cm ck c1 cj 單純形表單純形表ammmmaxzc1x1十c2x2十十cnxn a11x1a12x

23、2十十a(chǎn)1nxnb1 a21x1a22x2十十a(chǎn)2nxnb2 am1x1am2x2十十a(chǎn)mnxnbm xj0 (jl、2、，n)a1mmiijijacc110) 102050(10118)503020(1820)000010(03kjkab*cj1018000cbxbbx1x2x3x4x5170521001002301015015001x3x5x400010 18000170/2100/3150/5maxz10 x118x2 （1） 5x12x2 x3170 s.t 2x13x2x4100 （2） x15x2x5150 xj0 （j1，2，3，4，5） 主元x3x400 x2100/2cj10

24、18000cbxbbx1x2x3x4x5170521001002301015015001x3x5x400010 18000170/2150/3100181/5001/53010110（0 23/ 50 7/518 1/5）32/57/50111023/513/502/532/500018/5550/2350/7150maxz10 x118x2 （1） 5x12x2 x3170 s.t 2x13x2x4100 （2） x15x2x5150 xj0 （j1，2，3，4，5） 218 （0 00 018 1） 010100（30 3）7/52（1/5 3）x3x400 x2100/2cj101800

25、0cbxbbx1x2x3x4x5170521001002301015015001x3x5x400010 18000170/2150/3100181/5001/530107/50111023/513/502/532/500018/5550/2350/7150 x3x1x201018150/7005/7 3/7540/7 00123/7 11/7200/70101/72/7x*=(50/7, 200/7, 540/7, 0, 0)t z*=4100/700032/76/7例 某房地產(chǎn)公司欲開(kāi)發(fā)一七通一平空地，總面積2500m2。公司原計(jì)劃開(kāi)發(fā)商業(yè)樓1000m2，住宅樓5250m2。請(qǐng)根據(jù)下列前提條

26、件，確定其是否最佳開(kāi)發(fā)方式。(1)根據(jù)規(guī)劃要求：沿馬路建商業(yè)房，為4層樓框架結(jié)構(gòu)，其余為磚混住宅，為6層樓；容積率為2.5，建筑密度50%。(2)開(kāi)發(fā)日期為2003年12月，建筑物完成時(shí)間不超過(guò)一年半。(3)根據(jù)預(yù)測(cè)，一年半以后商業(yè)樓平均造價(jià)為1400元/m2，磚混住宅平均造價(jià)為950元/m2 ，不計(jì)土地成本。(4)預(yù)計(jì)建筑物完成后商業(yè)樓及住宅均可全部售出，商業(yè)樓出售當(dāng)時(shí)的平均售價(jià)為2400元/m2 ，住宅樓出售當(dāng)時(shí)的平均售價(jià)為1700元/m2 。(5)物業(yè)出售時(shí)的稅費(fèi)為總額的5%。(6)公司投入資金不超過(guò)650萬(wàn)元。分析：容積率總建筑面積/總占地面積建筑密度建筑基地總面積/總占地面積 (1)

27、總建筑面積25002.5=6250m2(2)建筑基地總面積250050%1250m2(3)商業(yè)樓每平方米的利潤(rùn):(0.240.14一0.245%)=0.088(萬(wàn)元/m2)(4)住宅樓每平方米的利潤(rùn):(0.17一0.095一0.175%)=0.0665(萬(wàn)元/m2)設(shè)商業(yè)樓建筑面積為x1m2;磚混住宅建筑面積為x2m2求x1、x2目標(biāo)函數(shù)max z=0.088 x10.0665 x2滿(mǎn)足: x1x26250 x1/4+x2/61250 0.14 x1十0.095 x2650 x1、x20 (1)總建筑面積 25002.5=6250m2(2)建筑基地總面積 250050%1250m2(3)商業(yè)樓

28、每平方米的利潤(rùn): (0.240.14一0.245%)=0.088(萬(wàn)元/元m2)(4)住宅樓每平方米的利潤(rùn):(0.17一0.095一0.175%)=0.0665(萬(wàn)元/m2)為了便于計(jì)算，變換一下約束條件及目標(biāo)函數(shù)。（由于在整個(gè)價(jià)值最優(yōu)程序中只是相對(duì)的價(jià)值是重要的，而不是它們絕對(duì)值。絕對(duì)值的值只影響目標(biāo)函數(shù)的最后值，但不影響設(shè)計(jì)變量的最優(yōu)值）因此，我們可以將其變換為:x1/4+x2/61250 轉(zhuǎn)變?yōu)? x1十2 x215000 0.14 x1十0.095 x2650 轉(zhuǎn)變?yōu)?.4737 x1十x26842max z=0.088 x10.0665 x2 轉(zhuǎn)變?yōu)閙ax z= z /0.06651

29、.323 x1x2max z=0.088 x10.0665 x2 x1x26250 x1/4+x2/61250 0.14 x1十0.095 x2650 x1、x20cj1.3231000cbxbbx1x2x3x4x5625011100150003201068421.43710011.3231000數(shù)學(xué)模型max z= 1.323 x1+x2x1x262503 x1十2 x2150001.4737 x1十x26842x1、x20 x3x4x5000max z= 1.323 x1+x2x1x262503 x1十2 x2150001.4737 x1十x26842x1、x20cj1.3231000cb

30、xbbx1x2x3x4x50 x36250111000 x415000320100 x568421.43710011.32310006250/115000/36842/1.47370 x30 x4x11.3230146430.6786000.678610710-0.035801 -2.0358160700.321410-0.678600.102200-0.89784643/0.6786=68421607/0.3214=50001.32300 x30 x4x1146430.6786000.678610710-0.035801 -2.0358160700.321410-0.678600.10220

31、0-0.89784643/0.6786=68421607/0.3214=50000 x41.323x1x211500003.111402.11140125000.11141 -1.4602012501-2.11140 -0.754200-0.31800 0 -1.1136最優(yōu)解:x1=1250, x2=5000, x4=1250, x3= x50z=6654即z=0.0665 z=442.5（萬(wàn)）n 例 某項(xiàng)目經(jīng)理部有三種住宅可以承建。三種住宅每百平方米的利潤(rùn)分別為6000元、8000元和5000元。承建時(shí)主要考慮木工和瓦工工時(shí)的安排。由于現(xiàn)在瓦工空閑，應(yīng)盡量多安排；而可支配的木工工時(shí)雖然僅有

32、26000個(gè)，但不允許有任何空閑。三種住宅每百平方米需用的瓦工和木工工時(shí)列在表中。另外，公司要求至少安排12000瓦工工時(shí)。問(wèn)三種住宅各承建多少平方米可使利潤(rùn)最大?甲住宅乙住宅丙住宅可動(dòng)用的總工時(shí)瓦工工時(shí)200010001500至少 12000木工工時(shí)10004000300026000 解 設(shè)甲、乙、丙三種住宅各承建x1、x2平方米，根據(jù)問(wèn)題的要求，可得下列線(xiàn)性規(guī)劃模型例 某工程的混凝土量總計(jì)1500m3；分三種標(biāo)號(hào)c20，c25，c30，其需要量為400m3、600m3 、500m3。今供應(yīng)32.5#水泥250t、 42.5#水泥200t、，水泥單價(jià)及用量見(jiàn)表。試選擇合理的配制方案，使水泥費(fèi)

33、用最省。混凝土標(biāo)號(hào)單位混凝土的水泥用量（kg/m3）水泥標(biāo)號(hào)c20c25c30水泥單價(jià)（元/t）水泥限量（t）32.5#253302362206525042.5#2112573022192200混凝土用量（m3）400600500設(shè)：由32.5#水泥配制的c20，c25，c30混凝土各為x1、x2、x3， 由42.5#水泥配制的c20，c25，c30混凝土各為x4、x5、x6則32.5#水泥的總耗量為 253x1302x2362x342.5#水泥的總耗量為 211x4257x5302x6目標(biāo)函數(shù)：min z2065（ 253x1302x2362x3 ） 2192（ 211x4257x5302x

34、6 ）253x1302x2362x3 250211x4257x5302x6 200 x1x4400 x2x5600 x3x6 500 xi0解得： x148 x2600 x344 x4252 x50 x6486 z28337.416（元）混 凝 土 標(biāo) 號(hào)單 位 混 凝 土 的 水 泥 用 量 （ kg/m3）水 泥 標(biāo) 號(hào)c20c25c30水 泥 單 價(jià)（ 元 /t）水 泥 限 量（ t）32.5#253302362206525042.5#2112573022192200混 凝 土 用 量 （ m3）400600500n案例:建設(shè)監(jiān)理公司監(jiān)理工程師配置問(wèn)題n某建設(shè)監(jiān)理公司(國(guó)家甲級(jí))，側(cè)重國(guó)

35、家大中型項(xiàng)目的監(jiān)理，僅在武漢市就正在監(jiān)理七項(xiàng)工程，總投資均在5000萬(wàn)元以上。由于工程開(kāi)工的時(shí)間不同，多工程工期之間相互搭接，具有較長(zhǎng)的連續(xù)性，2002年監(jiān)理的工程量與2003年監(jiān)理的工程量大致相同。n每項(xiàng)工程安排多少監(jiān)理工程師進(jìn)駐工地，一般是根據(jù)工程的投資，建筑規(guī)模，使用功能，施工的形象進(jìn)度，施工階段來(lái)決定的。監(jiān)理工程師的配置數(shù)量是隨之而變化的。由于監(jiān)理工程師從事的專(zhuān)業(yè)不同，他們每人承擔(dān)的工作量也是不等的。有的專(zhuān)業(yè)一個(gè)工地就需要三人以上，而有的專(zhuān)業(yè)一人則可以兼管三個(gè)以上的工地。n因?yàn)閺氖卤O(jiān)理業(yè)的專(zhuān)業(yè)多達(dá)幾十個(gè)，僅以高層民用建筑為例就涉及到建筑學(xué)專(zhuān)業(yè)、工民建(結(jié)構(gòu))專(zhuān)業(yè)、給水排水專(zhuān)業(yè)、采暖通風(fēng)

36、專(zhuān)業(yè)、強(qiáng)電專(zhuān)業(yè)、弱電專(zhuān)業(yè)、自動(dòng)控制專(zhuān)業(yè)、技術(shù)經(jīng)濟(jì)專(zhuān)業(yè)、總圖專(zhuān)業(yè)、合同和信息管理人員等，這就需要我們合理配置這些人力資源。為了方便計(jì)算，我們把所涉及的專(zhuān)業(yè)技術(shù)人員按總平均人數(shù)來(lái)計(jì)算，工程的施工形象進(jìn)度，按標(biāo)準(zhǔn)施工期和高峰施工期來(lái)劃分。通常標(biāo)準(zhǔn)施工期需求的人數(shù)較容易確定。但高峰施工期比較難確定了。原因有兩點(diǎn):n(1)高峰施工期各工地不是同時(shí)來(lái)到，是可以事先預(yù)測(cè)的，在同一個(gè)城市里相距不遠(yuǎn)的工地，就存在著各工地的監(jiān)理工程師如何交錯(cuò)使用的運(yùn)籌問(wèn)題。n(2)各工地總監(jiān)在高峰施工期到來(lái)的時(shí)候要向公司要人，如果每個(gè)工地都按高峰施工期配置監(jiān)理工程師的數(shù)量，將造成極大的人力資源浪費(fèi)，這一點(diǎn)應(yīng)該說(shuō)主要是人為因素所造

37、成的。n因此，為了達(dá)到高峰施工期監(jiān)理工程師配置數(shù)量最優(yōu)，人員合理地交錯(cuò)使用，扼制人為因素，根據(jù)歷年來(lái)的經(jīng)驗(yàn)對(duì)高峰施工期的監(jiān)理工程師數(shù)量在合理交錯(cuò)發(fā)揮作用的前提下限定了范圍。另經(jīng)統(tǒng)計(jì)測(cè)算得知，全年平均標(biāo)準(zhǔn)施工期占7個(gè)月，人年成本4萬(wàn)元;高峰施工期占5個(gè)月，人年成本7萬(wàn)元。標(biāo)準(zhǔn)施工期所需監(jiān)理工程師如下表:工程(工地)1234567所需最少監(jiān)理師人數(shù)5443322另外在高峰施工期各工地所需監(jiān)理工程師的數(shù)量要求第1和第2工地的總?cè)藬?shù)不少于14人;第2和第3工地的總?cè)藬?shù)不少于13人;第3和第4工地的總?cè)藬?shù)不少于11人;第4和第5工地的總?cè)藬?shù)不少于10人;第5和第6工地的總?cè)藬?shù)不少于9人;第6和第7工地的

38、總?cè)藬?shù)不少于7人;第7和第1工地的總?cè)藬?shù)不少于14人。求2003年:1高峰施工期公司最少配置多少個(gè)監(jiān)理工程師?2監(jiān)理工程師年耗費(fèi)的總成本是多少?n已知條件匯總：為了達(dá)到高峰施工期監(jiān)理工程師配置數(shù)量最優(yōu)，人員合理地交錯(cuò)使用，扼制人為因素，根據(jù)歷年來(lái)的經(jīng)驗(yàn)對(duì)高峰施工期的監(jiān)理工程師數(shù)量在合理交錯(cuò)發(fā)揮作用的前提下限定了范圍。另經(jīng)統(tǒng)計(jì)測(cè)算得知，全年平均標(biāo)準(zhǔn)施工期占7個(gè)月，人年成本4萬(wàn)元;高峰施工期占5個(gè)月，人年成本7萬(wàn)元。另外在高峰施工期各工地所需監(jiān)理工程師的數(shù)量要求第1和第2工地的總?cè)藬?shù)不少于14人;第2和第3工地的總?cè)藬?shù)不少于13人;第3和第4工地的總?cè)藬?shù)不少于11人;第4和第5工地的總?cè)藬?shù)不少于1

39、0人;第5和第6工地的總?cè)藬?shù)不少于9人;第6和第7工地的總?cè)藬?shù)不少于7人;第7和第1工地的總?cè)藬?shù)不少于14人。求2003年:1高峰施工期公司最少配置多少個(gè)監(jiān)理工程師?2監(jiān)理工程師年耗費(fèi)的總成本是多少?標(biāo)準(zhǔn)施工期所需監(jiān)理工程師如下表:工程(工地)1234567所需最少監(jiān)理師人數(shù)5443322n設(shè)xi為第i工地最少配置監(jiān)理工程師人數(shù)約束條件:標(biāo) 準(zhǔn) 施 工 期 所 需 監(jiān) 理 工 程 師 如 下 表 :工 程 (工 地 )1234567所 需 最 少 監(jiān) 理 師 人 數(shù)5443322第1和第2工地的總?cè)藬?shù)不少于14人;第2和第3工地的總?cè)藬?shù)不少于13人;第3和第4工地的總?cè)藬?shù)不少于11人;第4和第

40、5工地的總?cè)藬?shù)不少于10人;第5和第6工地的總?cè)藬?shù)不少于9人;第6和第7工地的總?cè)藬?shù)不少于7人; 第7和第1工地的總?cè)藬?shù)不少于14人。x15x24x34x43x53x62x72 x1、x2、x3、x4、x5、x6、 x7 0 x1x214 x2x313 x3x411 x4x510 x5x69 x6x77 x7x17minz= x1+ x2 +x3+ x4+ x5 + x6 + x72監(jiān)理工程師年耗費(fèi)的總成本(47/12+7 5/12） min（x1+ x2 +x3+ x4+ x5 + x6 + x7）4 4 線(xiàn)性規(guī)劃的對(duì)偶理論線(xiàn)性規(guī)劃的對(duì)偶理論4.1 對(duì)偶問(wèn)題4.2 對(duì)偶問(wèn)題的基本性質(zhì)4.3

41、影子價(jià)格4.4 對(duì)偶單純形法4.1 對(duì)偶問(wèn)題(1) (1) 對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的提出例例1 1、生產(chǎn)組織與計(jì)劃問(wèn)題、生產(chǎn)組織與計(jì)劃問(wèn)題a, ba, b各生產(chǎn)多少各生產(chǎn)多少, , 可獲最大利潤(rùn)可獲最大利潤(rùn)? ?可用資源可用資源煤煤勞動(dòng)力勞動(dòng)力倉(cāng)庫(kù)倉(cāng)庫(kù)a b1 23 20 2單位利潤(rùn)單位利潤(rùn)40 50306024max z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件如果因?yàn)槟撤N原因，不愿意自己生產(chǎn)，而希望通如果因?yàn)槟撤N原因，不愿意自己生產(chǎn)，而希望通過(guò)將現(xiàn)有資源承接對(duì)外加工來(lái)獲得收益，那么應(yīng)過(guò)將

42、現(xiàn)有資源承接對(duì)外加工來(lái)獲得收益，那么應(yīng)如何確定各資源的如何確定各資源的使用價(jià)格使用價(jià)格？max z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件兩個(gè)原則兩個(gè)原則l 所得不得低于生產(chǎn)所得不得低于生產(chǎn)的獲利的獲利l 要使對(duì)方能夠接受要使對(duì)方能夠接受設(shè)三種資源的使用單價(jià)分別為設(shè)三種資源的使用單價(jià)分別為 y1 , y2 , y3y1 y2 y3生產(chǎn)單位產(chǎn)品生產(chǎn)單位產(chǎn)品a a的資源消耗所得不少于單位產(chǎn)品的資源消耗所得不少于單位產(chǎn)品a a的獲利的獲利生產(chǎn)單位產(chǎn)品生產(chǎn)單位產(chǎn)品b b的資源消耗所得不少于單位產(chǎn)品

43、的資源消耗所得不少于單位產(chǎn)品b b的獲利的獲利y1 +3 y2 40 2y1 + 2 y2 + 2y3 50 50通過(guò)使用所有資源對(duì)外加工所獲得的收益通過(guò)使用所有資源對(duì)外加工所獲得的收益w = 30y1 + 60 y2 + 24y3根據(jù)原則根據(jù)原則2 ，對(duì)方能夠接受的價(jià)格顯然是越低越好，因此，對(duì)方能夠接受的價(jià)格顯然是越低越好，因此此問(wèn)題可歸結(jié)為以下數(shù)學(xué)模型：此問(wèn)題可歸結(jié)為以下數(shù)學(xué)模型：min w = 30y1 + 60 y2 + 24y3 y1 + 3y2 402y1 + 2 y2 + 2y3 50y1 , y2 , y3 0s.t目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件原線(xiàn)性規(guī)劃問(wèn)題稱(chēng)為原線(xiàn)性規(guī)劃問(wèn)

44、題稱(chēng)為原問(wèn)題原問(wèn)題，此問(wèn)題為此問(wèn)題為對(duì)偶問(wèn)題對(duì)偶問(wèn)題，y1 , y2 , y3 稱(chēng)為稱(chēng)為影子價(jià)格影子價(jià)格(2) (2) 對(duì)偶問(wèn)題的形式對(duì)偶問(wèn)題的形式njxbxaxaxabxaxaxabxaxaxatsxcxcxczmaxjmnmnmmnnnnnn, 2 , 10.221122222121112121112211定義定義 設(shè)原線(xiàn)性規(guī)劃問(wèn)題為設(shè)原線(xiàn)性規(guī)劃問(wèn)題為 則稱(chēng)下列線(xiàn)性規(guī)劃問(wèn)題則稱(chēng)下列線(xiàn)性規(guī)劃問(wèn)題miycyayayacyayayacyayayatsybybybwmininmmnnnmmmmmm, 2 , 10.221122222112112211112211為其對(duì)偶問(wèn)題，其中為其對(duì)偶問(wèn)題，其中

45、yi (i=1,2,m) 稱(chēng)為稱(chēng)為對(duì)偶變量對(duì)偶變量。上述對(duì)偶問(wèn)題稱(chēng)為上述對(duì)偶問(wèn)題稱(chēng)為對(duì)稱(chēng)型對(duì)偶問(wèn)題對(duì)稱(chēng)型對(duì)偶問(wèn)題。原問(wèn)題簡(jiǎn)記為原問(wèn)題簡(jiǎn)記為(p)，對(duì)偶問(wèn)題簡(jiǎn)記為，對(duì)偶問(wèn)題簡(jiǎn)記為(d)對(duì)偶關(guān)系對(duì)應(yīng)表對(duì)偶關(guān)系對(duì)應(yīng)表 原問(wèn)題原問(wèn)題 對(duì)偶問(wèn)題對(duì)偶問(wèn)題目標(biāo)函數(shù)類(lèi)型目標(biāo)函數(shù)類(lèi)型 max min目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù) 目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù) 右邊項(xiàng)系數(shù)右邊項(xiàng)系數(shù)與右邊項(xiàng)的對(duì)應(yīng)關(guān)系與右邊項(xiàng)的對(duì)應(yīng)關(guān)系 右邊項(xiàng)系數(shù)右邊項(xiàng)系數(shù) 目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù)變量數(shù)與約束數(shù)變量數(shù)與約束數(shù) 變量數(shù)變量數(shù)n 約束數(shù)約束數(shù) n的對(duì)應(yīng)關(guān)系的對(duì)應(yīng)關(guān)系 約束數(shù)約束數(shù)m 變量數(shù)變量數(shù)m原問(wèn)題變量類(lèi)型與原問(wèn)題變量類(lèi)型與 0 對(duì)偶問(wèn)題約

46、束類(lèi)型對(duì)偶問(wèn)題約束類(lèi)型 變量變量 0 約束約束 的對(duì)應(yīng)關(guān)系的對(duì)應(yīng)關(guān)系 無(wú)限制無(wú)限制 原問(wèn)題約束類(lèi)型與原問(wèn)題約束類(lèi)型與 0 對(duì)偶問(wèn)題變量類(lèi)型對(duì)偶問(wèn)題變量類(lèi)型 約束約束 變量變量 0 的對(duì)應(yīng)關(guān)系的對(duì)應(yīng)關(guān)系 無(wú)限制無(wú)限制4.2 對(duì)偶問(wèn)題的基本性質(zhì)定理定理1 1 對(duì)偶問(wèn)題的對(duì)偶就是原問(wèn)題對(duì)偶問(wèn)題的對(duì)偶就是原問(wèn)題max w=-ybs.t. -ya-cy0min z=-cxs.t. -ax-bx 0max z=cxs.t. ax bx 0min w=ybs.t. ya c y0對(duì)偶的定義對(duì)偶的定義對(duì)偶的定義對(duì)偶的定義定理定理2 2 ( (弱對(duì)偶定理弱對(duì)偶定理) )分別為分別為(p), (d)的可行解，則有

47、的可行解，則有c bx， yx y證明：由證明：由ax b, y 0 有有 yax b y 由由 ay c, x 0 有有 y a x c x所以所以c x y a x yb推論推論2、(p)有可行解有可行解, 但無(wú)有限最優(yōu)解，則但無(wú)有限最優(yōu)解，則(d)無(wú)可無(wú)可行解。行解。定理定理3、 yx,分別為分別為(p), (d)的可行解，且的可行解，且x yc=b, 則它們是則它們是(p), (d) 的最優(yōu)解。的最優(yōu)解。證明：對(duì)任證明：對(duì)任x，有，有cx b y =cxx最優(yōu)最優(yōu)推論推論1、(p), (d)都有可行解，則必都有最優(yōu)解。都有可行解，則必都有最優(yōu)解。定理定理4 4( (主對(duì)偶定理主對(duì)偶定理

48、) )若一對(duì)對(duì)偶問(wèn)題若一對(duì)對(duì)偶問(wèn)題(p)(p)和和(d)(d)都有可行解，則它們都都有可行解，則它們都有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值必相等。有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值必相等。證明：證明： (1) 當(dāng)當(dāng)x*和和y*為原問(wèn)題和對(duì)偶問(wèn)題的一個(gè)可行解為原問(wèn)題和對(duì)偶問(wèn)題的一個(gè)可行解有有bax *cay*byaxy*cxaxybyaxycx*原問(wèn)題目標(biāo)函數(shù)值原問(wèn)題目標(biāo)函數(shù)值對(duì)偶問(wèn)題目標(biāo)函數(shù)值對(duì)偶問(wèn)題目標(biāo)函數(shù)值所以原問(wèn)題的目標(biāo)函數(shù)值有上界，即可找到有限所以原問(wèn)題的目標(biāo)函數(shù)值有上界，即可找到有限最優(yōu)解；對(duì)偶問(wèn)題有下界，也存在有限最優(yōu)解。最優(yōu)解；對(duì)偶問(wèn)題有下界，也存在有限最優(yōu)解。(2) 當(dāng)當(dāng)x*為原問(wèn)題的一個(gè)最

49、優(yōu)解，為原問(wèn)題的一個(gè)最優(yōu)解，b為相應(yīng)的最優(yōu)基為相應(yīng)的最優(yōu)基,通通過(guò)引入松弛變量過(guò)引入松弛變量xs,將問(wèn)題將問(wèn)題(p)轉(zhuǎn)化為標(biāo)準(zhǔn)型轉(zhuǎn)化為標(biāo)準(zhǔn)型0,.0sssxxbixaxtsxcxzmax令令sxxx*00111bcabcciabccbbb0011abccbcbb01bcb令令01bcyb0ayccay所以所以y*是對(duì)偶問(wèn)題的可行解，是對(duì)偶問(wèn)題的可行解，對(duì)偶問(wèn)題的目標(biāo)函數(shù)值為對(duì)偶問(wèn)題的目標(biāo)函數(shù)值為bbcbywb1x*是原問(wèn)題的最優(yōu)解，原是原問(wèn)題的最優(yōu)解，原問(wèn)題的目標(biāo)函數(shù)值為問(wèn)題的目標(biāo)函數(shù)值為bbccxzb1wz推論：推論：若一對(duì)對(duì)偶問(wèn)題中的任意一個(gè)有最優(yōu)解，則另一個(gè)若一對(duì)對(duì)偶問(wèn)題中的任意一個(gè)有最

50、優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等。也有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等。一對(duì)對(duì)偶問(wèn)題的關(guān)系，有且僅有下列三種：一對(duì)對(duì)偶問(wèn)題的關(guān)系，有且僅有下列三種：l 都有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等；都有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等；l 兩個(gè)都無(wú)可行解；兩個(gè)都無(wú)可行解；1.1. 一個(gè)問(wèn)題無(wú)界，則另一問(wèn)題無(wú)可行解。一個(gè)問(wèn)題無(wú)界，則另一問(wèn)題無(wú)可行解。n從兩圖對(duì)比可明顯看到原問(wèn)題無(wú)界，其對(duì)偶問(wèn)題無(wú)可行解y1y20112212121y,yyyyy0242212121x ,xxxxxn例4 已知線(xiàn)性規(guī)劃問(wèn)題max z=x1+x2-x1+x2+x32-2x1+x2-x31x1,x2,x30試用對(duì)偶理論證明上述

51、線(xiàn)性規(guī)劃問(wèn)題無(wú)最優(yōu)解。n上述問(wèn)題的對(duì)偶問(wèn)題為min w=2y1+y2-y1-2y21y1+ y21y1- y20y1，y20由第1約束條件，可知對(duì)偶問(wèn)題無(wú)可行解；原問(wèn)題雖然有可行解，但無(wú)最優(yōu)解。n例5 已知線(xiàn)性規(guī)劃問(wèn)題min w=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53 xj0，j=1，2，5 已知其對(duì)偶問(wèn)題的最優(yōu)解為y1*=4/5，y2*=3/5；z=5。試用對(duì)偶理論找出原問(wèn)題的最優(yōu)解 。n例5 已知線(xiàn)性規(guī)劃問(wèn)題 解：先寫(xiě)出它的對(duì)偶問(wèn)題max z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22 3y

52、1+y23 y1，y20n例5 已知線(xiàn)性規(guī)劃問(wèn)題 將y1* =4/5,y2* =3/5的值代入約束條件，得=1/53，=17/55，=7/52 它們?yōu)閲?yán)格不等式；由互補(bǔ)松弛性得 x2*=x3*=x4*=0。因y1，y20；原問(wèn)題的兩個(gè)約束條件應(yīng)取等式，故有 x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原問(wèn)題的最優(yōu)解為 x*=(1，0，0，0，1)t；w*=5定理定理5 若若 x , y分別為分別為(p) , (d)的可行解，則的可行解，則x , y為為最優(yōu)解的充要條件是最優(yōu)解的充要條件是00xcyaaxby同時(shí)同時(shí)成立成立證證: (: (必要性）必要性）原問(wèn)題

53、原問(wèn)題 對(duì)偶問(wèn)題對(duì)偶問(wèn)題0,.ssxxbxaxtscxzmax0,.ssyycyyatsybwminbxaxscyyasaxbxscyaysybyxyaxscxxyyaxs0xyyxss y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 對(duì)偶問(wèn)題的變量對(duì)偶問(wèn)題的變量 對(duì)偶問(wèn)題的松弛變量對(duì)偶問(wèn)題的松弛變量 原始問(wèn)題的變量原始問(wèn)題的變量 原始問(wèn)題的松弛變量原始問(wèn)題的松弛變量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一對(duì)變量中，其中一個(gè)大于在一對(duì)變量中，其中一個(gè)大于0 0，另一個(gè)一定等于，另一個(gè)一定等于0 0 影子價(jià)格越大，說(shuō)

54、明這種資源越是相對(duì)緊缺影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺 影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺 如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于價(jià)格一定等于0 0種資源的邊際利潤(rùn)第種資源的增量第最大利潤(rùn)的增量iibzyiooimmiiybybybybwz2211mmiiiybybbybybzz)(2211iiybz4.3 影子價(jià)格變量yi*的經(jīng)濟(jì)意義是在其他條件不變的情況下，單位資源變化所引起的目標(biāo)函的最優(yōu)值的變化。n第1章中例1的影價(jià)格及其經(jīng)濟(jì)解釋。 由表1-5可知cj23000 cbxbbx

55、1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80-z-1400-3/2-1/80y1*=1.5，y2*=0.125，y3*=0。 n第1章中例1的影價(jià)格及其經(jīng)濟(jì)解釋。 這說(shuō)明是其他條件不變的情況下，若設(shè)備增加一臺(tái)時(shí)，該廠(chǎng)按最優(yōu)計(jì)劃安排生產(chǎn)可多獲利1.5元；原材料a增加1kg，可多獲利0.125元；原材料b增加1kg，對(duì)獲利無(wú)影響。 從圖2-1可看到，設(shè)備增加一臺(tái)時(shí)，代表該約束條件的直線(xiàn)由移至 ， 相 應(yīng) 的 最 優(yōu) 解 由 ( 4 ， 2 ) 變 為 ( 4 ， 2 . 5 ) ， 目 標(biāo) 函 數(shù)z=24+32.5=15.5，即比原來(lái)的增大1.5。

56、又若原材料a增加1kg時(shí)，代表該約束方程的直線(xiàn)由移至，相應(yīng)的最優(yōu)解從(4，2)變?yōu)?4.25，1.875)，目標(biāo)函數(shù)z=4.25+31.875=14.125。比原來(lái)的增加0.125。原材料b增加1kg時(shí)，該約束方程的直線(xiàn)由移至，這時(shí)的最優(yōu)解不變。n第1章中例1的影價(jià)格及其經(jīng)濟(jì)解釋。 nyi*的值代表對(duì)第i種資源的估價(jià)影子價(jià)格。 這種估價(jià)是針對(duì)具體工廠(chǎng)的具體產(chǎn)品而存在的一種特殊價(jià)格，稱(chēng)它為“影子價(jià)格”。在該廠(chǎng)現(xiàn)有資源和現(xiàn)有生產(chǎn)方案的條件下，設(shè)備的每小時(shí)租費(fèi)為1.5元，1kg原材料a的出讓費(fèi)為除成本外再附加0.125元，1kg原材料b可按原成本出讓?zhuān)@時(shí)該廠(chǎng)的收入與自己組織生產(chǎn)時(shí)獲利相等。影子價(jià)格

57、隨具體情況而異，在完全市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí)，企業(yè)應(yīng)買(mǎi)進(jìn)該資源用于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的市場(chǎng)價(jià)高于企業(yè)影子價(jià)格時(shí)，則企業(yè)的決策者應(yīng)把已有資源賣(mài)掉。可見(jiàn)影子價(jià)格對(duì)市場(chǎng)有調(diào)節(jié)作用。2.影子價(jià)格在經(jīng)濟(jì)管理中的應(yīng)用影子價(jià)格在經(jīng)濟(jì)管理中的應(yīng)用影子價(jià)格在經(jīng)濟(jì)管理中的應(yīng)用很多（1）影子價(jià)格能指示企業(yè)內(nèi)部挖潛的方向 1）影子價(jià)格越高的資源，表明它對(duì)目標(biāo)增益影響越大，同時(shí)也表明這種資源對(duì)該企業(yè)來(lái)說(shuō)越稀缺和越貴重，企業(yè)的管理者就應(yīng)該重視對(duì)這種資源的管理，通過(guò)挖潛革新、降低消耗或及時(shí)補(bǔ)充該種資源，以保證給企業(yè)帶來(lái)較大的收益。即對(duì)影子價(jià)格大于零的資源都應(yīng)采取措施，增加投入，以保證生產(chǎn)正常

58、進(jìn)行，實(shí)現(xiàn)利潤(rùn)最大化。 2）對(duì)影子價(jià)格為零的資源，企業(yè)的管理者也不應(yīng)忽視，這種資源對(duì)該企業(yè)來(lái)說(shuō)是相對(duì)富裕的。一方面，可以向別的企業(yè)轉(zhuǎn)讓這種資源或者以市場(chǎng)價(jià)出售，以免形成積壓浪費(fèi)；另一方面，通過(guò)企業(yè)內(nèi)部的改造、挖潛和增加對(duì)影子價(jià)格大于零的資源的投入后，使原有的剩余資源又可以得到充分利用，而變?yōu)樾碌木o缺資源（變?yōu)橛白觾r(jià)格大于零）。這樣不斷調(diào)整、補(bǔ)充，真正實(shí)現(xiàn)資源的合理利用。（2）影子價(jià)格在企業(yè)經(jīng)營(yíng)決策中的作用 因?yàn)橛白觾r(jià)格不是市場(chǎng)價(jià)格，它是根據(jù)企業(yè)本身的資源情況bi、消耗系數(shù)a ij和產(chǎn)品的利潤(rùn)cj 計(jì)算出來(lái)的一種價(jià)格，是新增資源所創(chuàng)造的價(jià)值，是邊際價(jià)格。不同的企業(yè)，即使是相同的資源（例如鋼材），

59、其影子價(jià)格也不一定相同。就是同一企業(yè)，在不同的生產(chǎn)周期，資源的影子價(jià)格也不完全一樣。因此，企業(yè)的決策者可以把本企業(yè)資源的影子價(jià)格與當(dāng)時(shí)的市場(chǎng)價(jià)格進(jìn)行比較。1）當(dāng)i種資源的影子價(jià)格高于市場(chǎng)價(jià)格時(shí)，則企業(yè)可以買(mǎi)進(jìn)該種資源；2）當(dāng)某種資源的影子價(jià)格低于市場(chǎng)價(jià)格時(shí)（特別是當(dāng)影子價(jià)格為零時(shí)），則企業(yè)可以賣(mài)出該種資源，以獲得較大的利潤(rùn)。3）隨著資源的買(mǎi)進(jìn)和賣(mài)出，它的影子價(jià)格也將發(fā)生變化，直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。所以我們說(shuō)影子價(jià)格又是一種機(jī)會(huì)成本，它在決定企業(yè)的經(jīng)常策略中起著十分重要的作用。 式中： cj表示單位j種產(chǎn)品的價(jià)值（或利潤(rùn)） m aijyii=1 表示生產(chǎn)第j種產(chǎn)品

60、所消耗的各項(xiàng)資源的影子價(jià)格的總和，它可以稱(chēng)為第j種產(chǎn)品的隱含成本隱含成本， 檢驗(yàn)數(shù)j 稱(chēng)作是第j種產(chǎn)品的相對(duì)價(jià)值系數(shù)相對(duì)價(jià)值系數(shù)。 mj = cj cbb-1pj = cj aijyi (j= 1,2,n). i=1由于（3）影子價(jià)格在新產(chǎn)品開(kāi)發(fā)決策中的應(yīng)用企業(yè)在新產(chǎn)品投產(chǎn)之前，可以用影子價(jià)格，通過(guò)分析產(chǎn)品使用資源的經(jīng)濟(jì)效果，以決定新產(chǎn)品是否應(yīng)該投產(chǎn)。0，產(chǎn)品b所能提供的單件利潤(rùn)大于其隱含成本，產(chǎn)品值得投產(chǎn) 產(chǎn)品單件消耗資源 a b影子價(jià)格鋼材煤機(jī)時(shí)1 22 13 4032/76/7單件利潤(rùn)（萬(wàn)元） 10 18 例maxz = 10 x1 + 18x2; 5 x1 + 2x2 170; 2x1