線性規(guī)劃之單純形法實(shí)驗(yàn)指導(dǎo)

1、實(shí)驗(yàn)指導(dǎo)線性規(guī)劃一、實(shí)驗(yàn)?zāi)康牧私饩€性規(guī)劃的基本知識(shí)，熟悉應(yīng)用matlab解決線性規(guī)劃問題的一般方法。二、實(shí)驗(yàn)內(nèi)容1. 線性規(guī)劃的基木概念2. 生產(chǎn)計(jì)劃問題3. 運(yùn)輸問題三、實(shí)驗(yàn)儀器和設(shè)備1. 計(jì)算機(jī)若t臺(tái)（裝有matlab6. 5及以上版本軟件）2. 打印機(jī)四、實(shí)驗(yàn)要求1. 獨(dú)立完成各個(gè)實(shí)驗(yàn)任務(wù)；2. 實(shí)驗(yàn)的過程保存成ni文件，以備檢查；3. 實(shí)驗(yàn)結(jié)果保存成.mat文件五、實(shí)驗(yàn)原理在生產(chǎn)和經(jīng)營等管理工作中，需耍經(jīng)常進(jìn)行計(jì)劃或規(guī)劃。雖然內(nèi)容千差萬別，但 它們都有其共同點(diǎn)：在現(xiàn)有資源限制下，如何確定方案，使預(yù)期目標(biāo)達(dá)到最優(yōu)。 這口j以歸結(jié)為數(shù)學(xué)規(guī)劃問題。在這類問題中，最簡單的是線性規(guī)劃問題，即在一

2、 組線性不等式約朿下求線性目標(biāo)函數(shù)的極大或極小值問題。因?yàn)榫€性規(guī)劃問題用 數(shù)學(xué)語言描述管理工作中的實(shí)際問題，所以又被稱為數(shù)學(xué)模型。建立數(shù)學(xué)模型的 過程是，由實(shí)際問題出發(fā)，設(shè)置變量，確定目標(biāo)函數(shù)，并根拯資源條件的限制寫 出約束條件，最后給岀線性規(guī)劃問題。本章只介紹兩種典型問題的模型，生產(chǎn)計(jì) 劃問題和運(yùn)輸問題。（-）線性規(guī)劃的基本概念線性規(guī)劃問題是求決策變量在一組線性等式或線性不等式約束下，使目標(biāo)函數(shù)達(dá) 到最小或最大值的一類優(yōu)化問題。求解線性規(guī)劃問題的計(jì)算方法中最簡單的是圖解法，以下面問題為例例1求解問題max z = xl+s. t. 2力+3垃w63x1+2a2w6x 0,這是一個(gè)求函數(shù)最大值

3、問題。其中，變量力，辺，的一組值就是實(shí)際問題中的 一個(gè)決策，所以稱它們?yōu)闆Q策變量（也稱為控制變量）。決策變量是取實(shí)數(shù)值的 連續(xù)變量。函數(shù)z = xl+ a2稱為目標(biāo)函數(shù)。而不等式組2/1+3/2w63x1+2 邊 w6力20,立20稱為約束條件。在圖1中，平面坐標(biāo)系第一象限內(nèi)由直線2刃+3立 =6的左下方以及直線3力+2£ = 6的左下方的區(qū)域止是控制變量滿足約束條件 的幾何圖形。區(qū)域中的任一點(diǎn)代表控制變量滿足線性規(guī)劃約束條件的一組值%1, 邊，稱為線性規(guī)劃問題的可行解。圖1全部可行解的集合稱為可行域使線性規(guī)劃的目標(biāo)函數(shù)達(dá)到最優(yōu)值（依具休問題， 或是極大值,或是極小值）的可行解稱為線

4、性規(guī)劃問題的最優(yōu)解。在這一問題中，最優(yōu)解對(duì)應(yīng)于直線族力+貯二c中，與可行域相切的一條直線。 切點(diǎn)正好是最優(yōu)解（6/5, 6/5）,因?yàn)檫@個(gè)點(diǎn)在可行域的邊界上正好是兩直線的交 點(diǎn)，即方程組（2x3 62召 6的解力二 6/5a2=6/5用圖解法求解線性規(guī)劃問題時(shí)應(yīng)注意幾點(diǎn)1. 圖解法適用于兩個(gè)變量的線性規(guī)劃問題；2. 線性規(guī)劃問題的解有四種情況：有唯一最優(yōu)解、有無窮多最優(yōu)解、有無界解、 無可行解；3. 線性規(guī)劃問題如果有最優(yōu)解，則可行域的某個(gè)頂點(diǎn)必定是最優(yōu)解.為求最優(yōu)解, 可先計(jì)算可行域上某頂點(diǎn)的目標(biāo)函數(shù)值，再考察相鄰頂點(diǎn)處的目標(biāo)函數(shù)值是否比 它更優(yōu)，如果為否，則這個(gè)點(diǎn)就是最優(yōu)點(diǎn);如果其它點(diǎn)更優(yōu)

5、,則轉(zhuǎn)到其它頂點(diǎn)上去 重復(fù)這一過程。用數(shù)學(xué)軟件matlab的命令lp可以求解一股的線性規(guī)劃間題在求解時(shí)，需要將間題化為matlab要求的如下標(biāo)準(zhǔn)形式nun z = ct x(ax<b° ie0 <x<&對(duì)于例1小口標(biāo)函數(shù)最大值問題，為了用matlab命令直接求解，應(yīng)轉(zhuǎn)化為最小 值問題，即min z 二x x2s. t. 2x1+3勺w63/l+2%2w6力20, a220取向量ct = ( 1 1 )刃=(6 6 )eo = (00)矩陣3 2 用matlab求解線性規(guī)劃問題命令lp的下而格式 lplc. a, b, e0, el)求解該問題。輸入問題中的全

6、部數(shù)據(jù)，并調(diào)用lp命令。程序段如卜 c=-l -1；a二2 3； 3 2；b二6； 6；e0=0 0；x=7p(c, a, b, eo)計(jì)算機(jī)運(yùn)行后的數(shù)據(jù)結(jié)果為ans 二 6/56/5所以，最優(yōu)解為xl = 6/5力二 6/5這一結(jié)論與圖解法的結(jié)果是一致的。在matlab屮，常用的求解線性規(guī)劃問題的命令使用格式有以下幾種(1) .最簡單的調(diào)用格式:x二lp(c, a, b)(2) .使用控制變量的上、下界調(diào)用格式：x二lp(f, a, b, vlb, vub)(3) .使用控制變量的初始點(diǎn)進(jìn)行迭代格式：x=lp(f, a, b, vlb, vub, xo)(4) .由a和b定義的約束條件中前n

7、個(gè)為等式約束條件使用格式：x=lp(f, a, b, vlb, vub, xo, n)(-)生產(chǎn)計(jì)劃問題現(xiàn)在考慮一個(gè)生產(chǎn)計(jì)劃問題。例2某工廠生產(chǎn)甲、乙兩種同類產(chǎn)品，需要用到三種原料。兩類產(chǎn)品中每單位的產(chǎn)品對(duì)三種原料的不同的需求量數(shù)據(jù)如下表所示表1原料乙原料可供應(yīng)量第一種原料(kg)113500第二種原料(kg)101500第三種原料(kg)5210000單位產(chǎn)品利潤(元)53問如何安排生產(chǎn)使總利潤最大？ 設(shè)生產(chǎn)卬、乙各力，垃(kg),則冇如下數(shù)學(xué)模型 max z 二 5 xl + 3何*,£3500丿旺 s1500isxi 2£10000s.t.可"£&

8、quot;由于原問題不是matlab所規(guī)定的標(biāo)準(zhǔn)形式，將原問題轉(zhuǎn)化為等價(jià)的線性規(guī)劃問 題min z =5 x 3 a2工宀/3500%"5005兔 +2x210000 譏mo用matlab求解線性規(guī)劃命令求解時(shí)所需的數(shù)據(jù)結(jié)構(gòu)有亡叫-5-3f ee -0 ofi-35001500 loooofi* 1 052i用matlab求解程序段如下c=5 3； a二1 1； 1 0； 5 2；b= 3500 1500 10000；e0=0 0；ip(-c, a, b, eo)計(jì)算結(jié)果為ans = 10002500所以，這一問題的最優(yōu)決策是取變量xl = 1000垃二 2500在不退岀matlab

9、環(huán)境條件下，繼續(xù)使用命令c*ans,可得ans 二 12500這說明在制定生產(chǎn)計(jì)劃時(shí)安排甲類產(chǎn)品生產(chǎn)1000kg,乙類產(chǎn)品生產(chǎn)2500kg,可 以在原料供應(yīng)量的限制下獲得最大的生產(chǎn)利潤12500元。制定生產(chǎn)計(jì)劃表如下 表2甲乙共計(jì)計(jì)劃生產(chǎn)(kg)100025003500產(chǎn)品利潤(元)5000750012500第一種原料(kg)100025003500第二種原料(kg)100001000第三種原料(kg)5000500010000現(xiàn)在用人工計(jì)算的圖解法驗(yàn)證上面結(jié)論。為了畫岀約束條件(專3500旺 £15005罰2叼“0000對(duì)應(yīng)的三條直線圖形，需知道直線上的兩個(gè)點(diǎn)的坐標(biāo)數(shù)據(jù)。第一條直線

10、在坐標(biāo)軸 上截距分別為3500, 3500o所以第一條直線過點(diǎn)(3500, 0),(0, 3500),它們的橫坐標(biāo)和縱坐標(biāo)分別為3500, 0, 0, 3500。第二條直線過點(diǎn)(1500, 0) 與xi軸相垂直,所以它過點(diǎn)(1500, 0), (1500, 5000),它們的橫坐標(biāo)和縱坐標(biāo) 分別為1500, 1500, 0, 5000。第三條直線截距分別為10000/5和10000/2, 所以它過點(diǎn)(2000, 0), (0, 5000),它們的橫坐標(biāo)和縱坐標(biāo)分別為2000, 0, 0, 5000o輸入下面繪直線命令line(3500, 0, 0, 3500)line(1500, 1500,

11、0, 5000)line(2000, 0, 0, 5000)可得圖形圖2由圖2可知，需要分別求出第一條直線與第三條直線交點(diǎn)，第二條直線與第三條 直線交點(diǎn)。用求解線性方程組的左除命令1 1； 5 23500； 100001 0； 5 21500； 10000可得交點(diǎn)m3 (1000, 2500),佬3 (1500, 1250),由此得可行域?qū)?yīng)的多邊形角 點(diǎn)坐標(biāo)如下p0 (0, 0)pl(0, 3500)p13(1000, 2500)p23(1500, 1250)p3(1500, 0)用填充命令fill(0, 0, 1000, 1500, 1500, 0, 3500, 2500, 1250, 0

12、, 'r'), 得可行域圖形。sddo<00300020001000$001000150020002$00圖3將m3的坐標(biāo)代入目標(biāo)函數(shù)得zmax=5 x1000 + 3x 2500二 12500為了在可行域圖上畫出直線5力 + 3a2 = 12500的圖形。首先計(jì)算出該直線在坐標(biāo)軸上的截距分別為:12500/5和12500/3。使 用兩點(diǎn)繪直線命令line(12500/5, 0, 0, 12500/3)得直線的圖形如圖3所示，直線與可行域多邊形相切。切點(diǎn)正好是可行域的一個(gè) 角點(diǎn)，該角點(diǎn)的坐標(biāo)m3(1000, 2500)就是原問題的最優(yōu)解。一般的生產(chǎn)計(jì)劃問題可作如一 f描述

13、:有加種資源：力1,加，擬生產(chǎn)刀種產(chǎn)品：by,仙。生產(chǎn)第/種產(chǎn)品一個(gè)單位需用笫i種資源數(shù)量為臼i j,第i種資源的最大數(shù)量為歷,銷售一個(gè)單位 的第j種產(chǎn)品可得產(chǎn)值cj?，F(xiàn)需要制定生產(chǎn)計(jì)劃，確定各種產(chǎn)品生產(chǎn)多少，使 利用有限資源，獲取最大的收獲?？蓪⒂嘘P(guān)數(shù)據(jù)列表如下表3產(chǎn)品類 資源類blbna1all曰inblam勿nlamn伽產(chǎn)值clcn設(shè)生產(chǎn)第j種產(chǎn)品的數(shù)量為xj （j=l, 2, , n） o則向量x二（力立 ,at1） t 的一組確定的值代表一個(gè)生產(chǎn)計(jì)劃。每個(gè)產(chǎn)品最低產(chǎn)量計(jì)劃為：幻2ej。擬定 生產(chǎn)計(jì)劃使總產(chǎn)值最高。目標(biāo)函數(shù)為約束條件為藝吟勺£毎i -數(shù)學(xué)模型為例7. 2某工廠

14、制造/!、兩種產(chǎn)品，制造/!每噸用煤9噸，電4 t瓦，3個(gè)工作 h ；制造每噸用煤5噸，電5千瓦，10個(gè)工作日。制造力和每噸分別獲利7000 元和12000元，該廠有煤360噸，電力2000千瓦，工作日3000個(gè)可利用。問a. 各生產(chǎn)多少噸獲利最大。首先將數(shù)據(jù)列表如下表4ab上限煤（噸）95360電（千瓦）452000工作日（犬）3103000利潤（千元）：712設(shè)計(jì)劃生產(chǎn)a、b兩種產(chǎn)品的數(shù)量分別為力，垃（噸），獲得的總利潤為z。則目 標(biāo)函數(shù)為z = 7/1+12/2約束條件為各種資源的上限9x1+5x23604x1+5x22003x1 + 10x2300xl20, x220令如 £

15、> 200300 :05*54建立數(shù)學(xué)模型如kmax z = ctx現(xiàn)在用matlab求解線性規(guī)劃命令lp求解這一問題，注意將極大值問題轉(zhuǎn)化為極 小值問題，以便符合規(guī)定的標(biāo)準(zhǔn)形式。輸入數(shù)據(jù)和求解命令如下c二7 12a二9 5； 4 5； 3 10b二360； 200； 300e0=0 0lp（-c, a, b, eo）最后得計(jì)算結(jié)果ans 二 2024這說明取決策變量x - 20邊二24即計(jì)劃力產(chǎn)品生產(chǎn)20噸，產(chǎn)品生產(chǎn)24噸是最優(yōu)決策。（三）運(yùn)輸問題運(yùn)輸問題從數(shù)學(xué)模型上可以分為三類：產(chǎn)銷平衡運(yùn)輸問題、產(chǎn)大于銷運(yùn)輸問題、 銷大于產(chǎn)運(yùn)輸問題。本節(jié)只介紹產(chǎn)銷平衡的這一類。例3從甲城調(diào)出蔬菜20

16、00噸，從乙城調(diào)岀蔬菜1100噸，分別供應(yīng)畀地1700噸,e地1100噸，c地200噸，地100噸，每噸運(yùn)費(fèi)（元）如下表5地地c地地甲城2125715乙城51513715為了確定運(yùn)費(fèi)最省的調(diào)撥計(jì)劃，用力1,力2,力3,力4分別表示從甲城調(diào)往力, b, c, 四地的蔬菜量；用垃1,疋2,疋3,疋4分別表示從乙城調(diào)往昇，b, c, 四地的蔬菜量。目標(biāo)函數(shù)（即總運(yùn)費(fèi)）可以表示為f 二21/11+25力2+7力3+15x14+51x21+51/22+37/23+15/24因?yàn)榧壮呛鸵页枪舱{(diào)岀蔬菜3100噸，而力地、地、c、地、地一共需要蔬菜也 是3100噸，所以這是產(chǎn)銷平等的運(yùn)輸問題。由產(chǎn)地甲城和乙城

17、調(diào)出的蔬菜量得 約束條件為刃1 + %12 + 力3 + xl4 二2000疋1 +垃2 +疋3 +疋4二1100由力地、地、c地和地需要的蔬菜量得另一組約束條件xll + a21 =1700h2 + a22=1100xl3 + 疋3 二 200%14 + a24 二100顯然運(yùn)輸量應(yīng)滿足非負(fù)性約束條件"j 2 0, i=l, 2； j= 1, 2, 3, 4實(shí)際問題需要求目標(biāo)函數(shù)f的極小值，由此得數(shù)學(xué)模型min f= 2u11+25h2+713+15x14+51a21+51a22+37a23+15a24-2000 = 1100 -1700 -1100-200100xij20, i

18、=1, 2； j = 1, 2, 3, 4現(xiàn)在考慮用matlab命令求解這一數(shù)學(xué)模型。由于決策變量是二維數(shù)組，matlab 的標(biāo)準(zhǔn)形式規(guī)定線性規(guī)劃問題的決策變量為一維數(shù)組（向量）。做變量代換，令 y - x. y2 - xl2, y3 二 %13, y4 二 %14 y5 二 x21,瑋二 x21, y7 二 x21, y8 二 x21所以，目標(biāo)函數(shù)傳換為f - 21 y +25+7y3+15y4+51 5+51 yq37y7+15y8約束條件轉(zhuǎn)換為yl+72+y3 +j4 二2000y5+y7 +y8 二1100yl+y51700必+二1100y3+yl200y4+y8100由此得向量y =

19、 yl y2 y3 y y5 yl y8 tc = 21 25 7 15 51 51 37 15 7 b = 2000 1100 1700 1100 200 1007以及矩陣*1iii0000000iiii000i00a-0i000i000i000i000i00060 <0 0 0 0 00 0 0o'1000寫出線性規(guī)劃問題如下 min f - ct ys. t. a y - by 2 0在約束條件中，只有等式約束條件和非負(fù)約束條件。這不由于一般的matlab規(guī) 定的標(biāo)準(zhǔn)形式，用lp命令求解時(shí)，必須注明由外和方定義的約束條件中前六個(gè) 為等式約束條件。根據(jù)lp命令使用格式，需要用

20、更多參數(shù)。所以，在使用命令 時(shí)不僅要給出控制變量的下界，還需要給出控制變量的上界。因?yàn)楫a(chǎn)地的蔬菜供 應(yīng)量最大值為 2000 噸,故取向量 el = 2000 2000 2000 2000 2000 2000 為控制變量的上界。并取控制變量的初始值為 i4） <0 0 0 0 0 0 0 0在matlab小輸入數(shù)據(jù)和命令如下c二21 25 7 15 51 51 37 15；b = 2000； 1100； 1700； 1100； 200； 100；c0= 00000000；el 二2000 2000 2000 2000 2000 2000； i4) <0 0 0 0 0 0 0 0a二

21、1 111000 0； 0000111 1； 1 0 0 0 1 0 0 0； 1 0 0 0 1 0 0； 0 0 1 0 0 0 1 0； 0 0 0 1 0 0 0 1 y 二 7p(c, a, b, eo, el, vo, 6) 最后得計(jì)算結(jié)果y 1/18014398509482110001/197902556028729100這說明第四、五、七個(gè)控制變量應(yīng)取值為0,即一組最優(yōu)解為yl 二 1700 吆二 100 y3 二 200 図二 0拓=0 j6 = 1000= 0 j8 = 100為了求出最優(yōu)解的目標(biāo)函數(shù)f - ct y的值，不退iw matlab環(huán)境

22、，鍵入命令c*y得數(shù)據(jù)ans = 92100由此可得最優(yōu)解的口標(biāo)函數(shù)值為92100 （元），最優(yōu)解為all = 1700 a12 = 100 a13 = 200 a14 = 0a21 = 0 a22 = 1000 啟3 二 0 啟4 二 100構(gòu)造調(diào)度表如下表6蔬菜運(yùn)輸調(diào)度計(jì)劃（單位：噸）a地b地c地d地甲城010000100六、實(shí)驗(yàn)任務(wù)1.某糕點(diǎn)廠用面粉加佐料，通過電烤生產(chǎn)久兩利1餅干。已知生產(chǎn)久兩種 類型的餅干各1噸所需面粉、用屯量和所得利潤如下表而粉（噸）電（度）利潤（千元）a0. 72802. 1b0.96602.2現(xiàn)在每天只能供應(yīng)而粉3. 6噸，電260度，問如何生產(chǎn)才能獲利潤最大？3某中藥廠用當(dāng)歸作原料，制成當(dāng)歸丸和當(dāng)歸膏投入市場，生產(chǎn)一盒當(dāng)歸丸和一 瓶當(dāng)歸膏所需勞動(dòng)力（單位：小時(shí)）和原料（單位：千克）以及工廠現(xiàn)有勞動(dòng)力、 原料數(shù)