1-1 線性規(guī)劃-問題、模型與圖解法

1、11-1 1-1 線性規(guī)劃線性規(guī)劃- -問題、模型及圖解法問題、模型及圖解法2線性規(guī)劃的發(fā)展線性規(guī)劃的發(fā)展n20世紀(jì)世紀(jì)30年代年代 前蘇聯(lián)數(shù)學(xué)家康特洛維奇前蘇聯(lián)數(shù)學(xué)家康特洛維奇 提出提出解乘數(shù)法解乘數(shù)法(1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng))n1947 美國空軍數(shù)學(xué)顧問美國空軍數(shù)學(xué)顧問 丹捷格丹捷格 線性規(guī)劃線性規(guī)劃 單單純形法純形法n馮馮. 諾依曼諾依曼 對偶理論對偶理論 庫恩庫恩 塔克塔克 蓋爾蓋爾 嚴(yán)格證明嚴(yán)格證明3概要概要n1 問題描述問題描述n2 建模建模n 2.1 建模三要素建模三要素 n 2.2 一般形式一般形式 2.3 標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式n3 模型求解模型求解n 3.1圖解

2、法圖解法n 3.1.1 方法步驟方法步驟n 3.1.2 解的幾種情況解的幾種情況n 3.2 基本概念與理論基本概念與理論n 3.3 單純形法單純形法 n 3.3.1 單純形法的一般思路單純形法的一般思路+例子例子n 3.3.2 單純形表結(jié)構(gòu)單純形表結(jié)構(gòu)+例子例子n 3.3.3 單純形法的計(jì)算步驟單純形法的計(jì)算步驟n 4n 3.4 大大M法法n 3.5 兩階段法兩階段法n4 幾種特殊情況幾種特殊情況n 4.1 無可行解無可行解n 4.2 無界解無界解n 4.3 多重最優(yōu)解多重最優(yōu)解n 4.4 進(jìn)基變量的相持進(jìn)基變量的相持n 4.5 出基變量的相持出基變量的相持51 1 問題描述問題描述-線性規(guī)劃

3、經(jīng)典問題線性規(guī)劃經(jīng)典問題 生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時(shí)數(shù)如下表所示：每件產(chǎn)品占用的機(jī)時(shí)數(shù)（小時(shí)/件）產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙產(chǎn)品丁設(shè)備能力（小時(shí)）設(shè)備A1.51.02.41.02000設(shè)備B1.05.01.03.58000設(shè)備C1.53.03.51.05000利潤（元/件）5.247.308.344.1862 2 建模建模 2.1 2.1 建模三要素建模三要素變量變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 約束條件約束條件（1）理解要解決的問題，了解解題的目標(biāo)和條件；）理解要解決

4、的問題，了解解題的目標(biāo)和條件；（2）定義決策變量（）定義決策變量（ x1 ，x2 ， ，xn ），每一組），每一組值表示一個(gè)方案；值表示一個(gè)方案；（3）用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)，確）用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；定最大化或最小化目標(biāo)；（4）用一組決策變量的等式或不等式表示解決問題）用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件過程中必須遵循的約束條件712341234123412341234max5.247.38.344.181.51.02.41.020001.05.01.03.58000. .1.03.03.51.05000,0z

5、xxxxxxxxxxxxstxxxxx x x xSchool of BusinessECUSTn習(xí)題：營養(yǎng)配餐問題習(xí)題：營養(yǎng)配餐問題q假定一個(gè)成年人每天至少需要從食物中攝取假定一個(gè)成年人每天至少需要從食物中攝取3000大大卡的熱量、卡的熱量、55克蛋白質(zhì)和克蛋白質(zhì)和800毫克的鈣。市場上只有毫克的鈣。市場上只有豬肉、雞蛋、大米和白菜四種食品可供選擇，它們每豬肉、雞蛋、大米和白菜四種食品可供選擇，它們每公斤所含的熱量和營養(yǎng)成分以及市場價(jià)格見下表。請公斤所含的熱量和營養(yǎng)成分以及市場價(jià)格見下表。請問如何選擇才能在滿足營養(yǎng)的前提下，使購買食品的問如何選擇才能在滿足營養(yǎng)的前提下，使購買食品的費(fèi)用最小？

6、費(fèi)用最??？School of BusinessECUST每公斤食物營養(yǎng)表序號食品名稱熱量(大卡)蛋白質(zhì)(克)鈣(毫克)價(jià)格(元)1豬肉100050400142雞蛋8006020063大米9002030034白菜200105002300055800School of BusinessECUST營養(yǎng)配餐問題建模營養(yǎng)配餐問題建模n決策變量：決策變量：qxj 每天購入第每天購入第j種食品的公斤數(shù)種食品的公斤數(shù)n目標(biāo)函數(shù)：每天的食品采購成本最小目標(biāo)函數(shù)：每天的食品采購成本最小n約束條件：滿足每天的營養(yǎng)要求約束條件：滿足每天的營養(yǎng)要求q(1) 滿足每天至少滿足每天至少3000大卡的熱量要求大卡的熱量要求1

7、234m i n14632zxxxx123410008009002003000 xxxxSchool of BusinessECUSTq(2) 滿足每天至少攝入55克蛋白質(zhì)的營養(yǎng)要求q(3) 滿足每天至少攝入800毫克鈣的營養(yǎng)要求q非負(fù)約束：采購量不能為負(fù)值12345060201055xxxx1234400200300500800 xxxx1234, , ,0 x x x xSchool of BusinessECUST營養(yǎng)配餐問題的數(shù)學(xué)模型12341234123412341234m i n14632100080090020030005060201055.400200300500800, ,

8、,0zxxxxxxxxxxxxstxxxxx x x xSchool of BusinessECUST2.2 線性規(guī)劃的一般線性規(guī)劃的一般形式形式n線性規(guī)劃問題是求一個(gè)線性函數(shù)(目標(biāo)函數(shù))在滿足一組線性等式或不等式條件下極值的數(shù)學(xué)問題的統(tǒng)稱。n線性規(guī)劃問題的一般特征：q(1) 有一組有待決策的變量(決策變量)，一般表示為x1, x2, ., xn，變量組的每一組取值對應(yīng)于某一種決策方案，根據(jù)實(shí)際問題，通常要求變量取非負(fù)值，即0,1,2,ixinSchool of BusinessECUSTq(2) 每個(gè)問題中存在若干個(gè)約束條件，約束條件可用決策變量的線性等式或線性不等式來表達(dá)。q(3) 每個(gè)問

9、題中有一個(gè)目標(biāo)函數(shù)，這個(gè)目標(biāo)函數(shù)可表示為決策變量的線性函數(shù)。要求這個(gè)目標(biāo)函數(shù)在滿足約束條件下實(shí)現(xiàn)最大化或最小化n將約束條件及目標(biāo)函數(shù)都是決策變量線性函數(shù)的數(shù)學(xué)規(guī)劃問題稱為線性規(guī)劃(LP, linear programming)School of BusinessECUST121121212212m ax m i n, ,. . . , ,. . . , ,. . . ,. . ., ,. . . ,nnnmnmzf x xxgx xxbgx xxbstgx xxb 一般的數(shù)學(xué)規(guī)劃模型112211112211211222221122. . .( , )( , ).( , )0,(1,2,m ax

10、 m i n, )nnnnnnmmm nnmjzcxc xc xa xa xa xba xa xa xbsta xaxaxbxjn 線性規(guī)劃模型線性規(guī)劃模型的一般形式12,nx xx12,nc cc1112,mnaaa通常稱 為決策變量， 為價(jià)值系數(shù)， 為技術(shù)系數(shù), 為資源限制系數(shù)。12,mb bbSchool of BusinessECUST112211112211211222221122. . .( , )( , ).( , )0,(1,2,m ax m)i n, nnnnnnmmm nnmjzc xc xc xa xa xa xba xa xa xbstaxaxaxbxjn1m ax(m

11、 i n)njjjzc x11 201 2( , )(, ,. . . , ).(, ,. . . , )nijjijja xbimstxjn 可簡寫為：School of BusinessECUST向量式112211112211211222221122. . .( , )( , ).( , )0,(1,2,m ax m)i n nnnnnnmmm nnmjzc xc xc xa xa xa xba xa xa xbstaxaxaxbxjn1212, ,. . . ,:，nnxxCc ccXxm ax m i nzC X1P2PnPb1 122( , ).0 nnP xP xP xbstXSc

12、hool of BusinessECUST矩陣式11121212221212. . ., ,. . ,:. .nnnmmm naaaaaaAP PPaaa1P2PnPm ax(m i n)zC X0( , ).A XbstX 系數(shù)矩陣右端常數(shù)School of BusinessECUST2.3 線性規(guī)劃模型的標(biāo)準(zhǔn)形式線性規(guī)劃模型的標(biāo)準(zhǔn)形式LP模型的標(biāo)準(zhǔn)型為：1 122m ax. . .nnzcxc xc x11 11221121 1222221 12201 2. . . . . . . . . . . .,(, ,. . . , )nnnnmmm nnmja xa xa xba xa xa x

13、bsta xaxaxbxjn其中右端常數(shù)項(xiàng) , 0ib), 2 , 1(mi(1) 目標(biāo)函數(shù)為求最大值目標(biāo)函數(shù)為求最大值(2) 約束條件均為等式，約束條件均為等式，且右端為非負(fù)常數(shù)且右端為非負(fù)常數(shù)(3) 決策變量均為非負(fù)決策變量均為非負(fù)值值School of BusinessECUSTm axzC X10.njjjP xbstX用向量表示時(shí)，標(biāo)準(zhǔn)型可寫為：用矩陣形式，可表示為：m axzC X0.A XbstXSchool of BusinessECUST非標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式n(1) 目標(biāo)函數(shù)：min maxn(2) 右端常數(shù)：bi0n(3) 約束：不等式約束 等式約束q =q =n(4)變量：

14、不滿足非負(fù)條件 滿足非負(fù)條件q0 0q無符號限制(自由變量) 0School of BusinessECUSTn(1) 目標(biāo)函數(shù)：min max若目標(biāo)函數(shù)為nnxcxcxcZ2211min引進(jìn)新的目標(biāo)函數(shù),ZZ則Z的最小值即為ZZZ maxmin從而目標(biāo)函數(shù)變換為：nnxcxcxcZ2211max的最大值，即：School of BusinessECUSTn(2) 右端常數(shù)：bi0q若約束條件中某線性方程式的常數(shù)項(xiàng) bi 為負(fù)數(shù)，則將該線性方程式兩端乘以-1即可，但需注意不等式變號。School of BusinessECUSTn(3) 約束：不等式約束 等式約束q = ：在不等式左邊加上一個(gè)

15、非負(fù)變量(松弛變 量)，將不等式變?yōu)榈仁?。q = ：在不等式左邊減去一個(gè)非負(fù)變量(剩余變 量)，將不等式變?yōu)榈仁?。School of BusinessECUSTn簡例：將LP模型12max33Zxx12122102601 2.(, )ixxstxxxi化為標(biāo)準(zhǔn)型。解：對10221 xx引入變量(松弛變量), 03x 使得式變?yōu)椋?02321xxx對式1226xx引入變量(剩余變量), 04x 使得式變?yōu)椋?2426xxxSchool of BusinessECUST于是將原LP模型化為標(biāo)準(zhǔn)形式：12max33Zxx1231242102601 2 3 4., , ,ixxxstxxxxiScho

16、ol of BusinessECUSTn(4)變量：不滿足非負(fù)條件 滿足非負(fù)條件q0 0：x 0 ,令x= -x, 則x 0,用變量x 替換xq無符號限制(自由變量) 0：nx無符號限制,令x=xx,其中x,x0。用變量x和x替換xSchool of BusinessECUSTn例將下列LP模型：123min23 Zxxx123123123123723250.,xxxxxxstxxxx xx化為標(biāo)準(zhǔn)型。無符號限制School of BusinessECUSTSchool of BusinessECUST12333312121433533334521272323250.m a,x, ,zxxxx

17、xxxxxxxxxxxx xxxxstxxx x 313 3 模型求解模型求解 3.13.1圖解法圖解法( (線性規(guī)劃問題的幾何特征線性規(guī)劃問題的幾何特征) ) School of BusinessECUSTn3.1.1 兩個(gè)決策變量線性規(guī)劃模型圖解法的基本步驟兩個(gè)決策變量線性規(guī)劃模型圖解法的基本步驟：q(1) 建立以x1, x2為坐標(biāo)軸的直角坐標(biāo)系，畫出線性規(guī)劃問題的可行域；q(2) 任取z = z0, 畫出對應(yīng)的目標(biāo)函數(shù)直線, 將該直線在可行區(qū)域內(nèi)平行移動(dòng)，構(gòu)成目標(biāo)函數(shù)的等值線簇；q(3) 目標(biāo)函數(shù)值最優(yōu)的等值線與可行域的交點(diǎn)(若存在)即為問題的最優(yōu)解?？尚杏颍簼M足所有約束條件的解的集合，

18、即所有約束條件共同圍成的區(qū)域。School of BusinessECUSTn例 用圖解法求下列線性規(guī)劃問題的最優(yōu)解Max Z= 3x1 +5 x2 s.t. 2 x1 16 2x2 10 3x1 +4 x2 32 x1 0, x2 02x1=162x2=103x1+4x2=32x1x248103590ABCDSchool of BusinessECUST2x1 =162x2 =10 x1x248103583x1 +4 x2 =320ABCD目標(biāo)函數(shù)目標(biāo)函數(shù) Z= 3x1 +5 x2 代表以代表以 Z 為參數(shù)的一族平行線。為參數(shù)的一族平行線。Z=30Z=37Z=15最優(yōu)解：4,5X35(1) 惟一最優(yōu)解惟一最優(yōu)解max z= x1+3x2 s.t. x1+x26 -x1+2x28 x1,x20123456xz=0z=3z=6z=9z=12z=15.3013456約 束 條 件 （ 1）約 束 條 件 （ 2）C-1-8-2-3-4-5-6-7x213.1.2 線性規(guī)劃問題解的幾種情況線性規(guī)劃問題