線性規(guī)劃之單純形法實驗指導

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

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

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

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

5、,則轉(zhuǎn)到其它頂點上去 重復這一過程。用數(shù)學軟件matlab的命令lp可以求解一股的線性規(guī)劃間題在求解時，需要將間題化為matlab要求的如下標準形式nun z = ct x(ax<b° ie0 <x<&對于例1小口標函數(shù)最大值問題，為了用matlab命令直接求解，應轉(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)計算機運行后的數(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) .使用控制變量的初始點進行迭代格式：x=lp(f, a, b, vlb, vub, xo)(4) .由a和b定義的約束條件中前n

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

8、quot;由于原問題不是matlab所規(guī)定的標準形式，將原問題轉(zhuǎn)化為等價的線性規(guī)劃問 題min z =5 x 3 a2工宀/3500%"5005兔 +2x210000 譏mo用matlab求解線性規(guī)劃命令求解時所需的數(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)計算結(jié)果為ans = 10002500所以，這一問題的最優(yōu)決策是取變量xl = 1000垃二 2500在不退岀matlab

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

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

11、0, 5000)line(2000, 0, 0, 5000)可得圖形圖2由圖2可知，需要分別求出第一條直線與第三條直線交點，第二條直線與第三條 直線交點。用求解線性方程組的左除命令1 1； 5 23500； 100001 0； 5 21500； 10000可得交點m3 (1000, 2500),佬3 (1500, 1250),由此得可行域?qū)亩噙呅谓?點坐標如下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的坐標代入目標函數(shù)得zmax=5 x1000 + 3x 2500二 12500為了在可行域圖上畫出直線5力 + 3a2 = 12500的圖形。首先計算出該直線在坐標軸上的截距分別為:12500/5和12500/3。使 用兩點繪直線命令line(12500/5, 0, 0, 12500/3)得直線的圖形如圖3所示，直線與可行域多邊形相切。切點正好是可行域的一個 角點，該角點的坐標m3(1000, 2500)就是原問題的最優(yōu)解。一般的生產(chǎn)計劃問題可作如一 f描述

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

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

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

16、00噸，從乙城調(diào)岀蔬菜1100噸，分別供應畀地1700噸,e地1100噸，c地200噸，地100噸，每噸運費（元）如下表5地地c地地甲城2125715乙城51513715為了確定運費最省的調(diào)撥計劃，用力1,力2,力3,力4分別表示從甲城調(diào)往力, b, c, 四地的蔬菜量；用垃1,疋2,疋3,疋4分別表示從乙城調(diào)往昇，b, c, 四地的蔬菜量。目標函數(shù)（即總運費）可以表示為f 二21/11+25力2+7力3+15x14+51x21+51/22+37/23+15/24因為甲城和乙城共調(diào)岀蔬菜3100噸，而力地、地、c、地、地一共需要蔬菜也 是3100噸，所以這是產(chǎ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顯然運輸量應滿足非負性約束條件"j 2 0, i=l, 2； j= 1, 2, 3, 4實際問題需要求目標函數(shù)f的極小值，由此得數(shù)學模型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ù)學模型。由于決策變量是二維數(shù)組，matlab 的標準形式規(guī)定線性規(guī)劃問題的決策變量為一維數(shù)組（向量）。做變量代換，令 y - x. y2 - xl2, y3 二 %13, y4 二 %14 y5 二 x21,瑋二 x21, y7 二 x21, y8 二 x21所以，目標函數(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在約束條件中，只有等式約束條件和非負約束條件。這不由于一般的matlab規(guī) 定的標準形式，用lp命令求解時，必須注明由外和方定義的約束條件中前六個 為等式約束條件。根據(jù)lp命令使用格式，需要用

20、更多參數(shù)。所以，在使用命令 時不僅要給出控制變量的下界，還需要給出控制變量的上界。因為產(chǎn)地的蔬菜供 應量最大值為 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) 最后得計算結(jié)果y 1/18014398509482110001/197902556028729100這說明第四、五、七個控制變量應取值為0,即一組最優(yōu)解為yl 二 1700 吆二 100 y3 二 200 図二 0拓=0 j6 = 1000= 0 j8 = 100為了求出最優(yōu)解的目標函數(shù)f - ct y的值，不退iw matlab環(huán)境

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