應(yīng)用MATLAB軟件求解線性規(guī)劃學(xué)習

1、應(yīng)用應(yīng)用MATLAB軟件求解軟件求解線性規(guī)劃線性規(guī)劃11minzs.t.CXAXbA XblbXub(1) MATLAB（MATrix LABoratory）的基本含義是矩陣實驗室，它是由美國MathWorks公司研制開發(fā)的一套高性能的集數(shù)值計算、信息處理、圖形顯示等于一體的可視化數(shù)學(xué)工具軟件。它是建立在向量、數(shù)組和矩陣基礎(chǔ)之上的，除了基本的數(shù)值計算、數(shù)據(jù)處理、圖形顯示等功能之外，還包含功能強大的多個“工具箱”，如優(yōu)化工具箱（optimization toolbox）、統(tǒng)計工具箱、樣條函數(shù)工具箱和數(shù)據(jù)擬合工具箱等都是優(yōu)化計算的有力工具。在這里僅介紹用MATLAB6.5優(yōu)化工具箱求解線性規(guī)劃問題

2、。 一般線性規(guī)劃問題的數(shù)學(xué)模型為 其中其中C是目標函數(shù)的系數(shù)行向量（常數(shù)）是目標函數(shù)的系數(shù)行向量（常數(shù)）, X 是是n維列維列向量（決策變量），向量（決策變量），A, A1是常數(shù)矩陣，是常數(shù)矩陣，b,b1是常數(shù)是常數(shù)向量，向量，lb,ub是是n維列向量分別表示決策變量維列向量分別表示決策變量X的下界的下界與上界。與上界。 在在Matlab優(yōu)化工具箱（優(yōu)化工具箱（Optimization Toolbox）中，）中，求解求解(1)的程序如下：的程序如下：x，fval，exitflag，output，lambda = linprog (c，A，b，Aeq，beq，lb，ub，x0，options)

3、說明：說明：(1)A是不等式約束的系數(shù)矩陣，是不等式約束的系數(shù)矩陣，b是相應(yīng)的常是相應(yīng)的常數(shù)列向量，若沒有不等式約束，則均用數(shù)列向量，若沒有不等式約束，則均用 代替；代替； (2) Aeq是等式約束的系數(shù)矩陣，是等式約束的系數(shù)矩陣，beq是相應(yīng)的常數(shù)是相應(yīng)的常數(shù)列向量，若沒有等式約束，則均用列向量，若沒有等式約束，則均用代替；代替； (3)如果某個變量無下界，則用如果某個變量無下界，則用-inf表示；如果某個變表示；如果某個變量無上界，則用量無上界，則用inf表示，若決策變量表示，若決策變量 無下界，則無下界，則lb用用代替；若決策變量代替；若決策變量 無上界，則無上界，則ub用用代替；代替；

4、 (4) x0是線性規(guī)劃的初始解，這種設(shè)計僅對中規(guī)模算是線性規(guī)劃的初始解，這種設(shè)計僅對中規(guī)模算法有效，通常可以缺省。法有效，通?？梢匀笔?。 (5) 輸出輸出 是最優(yōu)解，是最優(yōu)解，fval是最優(yōu)值。是最優(yōu)值。 (6) 輸出輸出exitflag描述了程序的運行情況，若其值大描述了程序的運行情況，若其值大于零，表示程序收斂到最優(yōu)解于零，表示程序收斂到最優(yōu)解 ；若其值等于零，；若其值等于零，表示計算達到了最大次數(shù)；若其值小于零，表示問表示計算達到了最大次數(shù)；若其值小于零，表示問題無可行解，或程序運行失敗。題無可行解，或程序運行失敗。 (7)輸出輸出output表示程序運行的某些信息，如迭代表示程序運行

5、的某些信息，如迭代次數(shù)次數(shù)(iterations)、所用算法、所用算法(algorithm)、共軛梯度、共軛梯度(cgiterations)等。等。 (8)lambda表示解處的拉格朗日乘子，其中表示解處的拉格朗日乘子，其中l(wèi)ower，upper，ineqlin，eqlin分別對應(yīng)于下界、上界、不分別對應(yīng)于下界、上界、不等式約束與等式約束。等式約束與等式約束。例3 用MATLAB解線性規(guī)劃問題123123123123123226442212005minzxxxxxxxxxs.t.xxxx,x,x （2） 解解 Matlab程序如下程序如下:c=-2,-1,1;A=1,4,-1;2,-2,1;b

6、=4;12;Aeq=1,1,2;beq=6;lb=0,0,-inf;ub=inf,inf,5;x,z=linprog(c,A,b,Aeq,beq,lb,ub)運行后得到輸出運行后得到輸出Optimization terminated successfully.x= 4.6667 0.0000 0.6667z= -8.6667例例4 用MATLAB求解線性規(guī)劃問題123123123max2357. . 25100,1,2,3izxxxxxxstxxxxi（3） 解解 首先轉(zhuǎn)化為求最小值問題123123123min2357. .25100,1,2,3izSxxxxxxstxxxxi Matlab程

7、序如下程序如下c=-2,-3,5;A=-2,5,-1;b=-10;Aeq=1,1,1;beq=7;lb=0,0,0;x,z=linprog(c,A,b,Aeq,beq,lb)運行后得到輸出運行后得到輸出x = 6.4286 0.5714 0.0000z = -14.5714鍵入鍵入 s=-z 運行后得到原問題的目標運行后得到原問題的目標函數(shù)最大值函數(shù)最大值 s=14.5714用用MATLAB求解例求解例2的程序與輸出結(jié)果為：的程序與輸出結(jié)果為：c=0.2,0.7,0.4,0.3,0.5;A=-0.3,-2,-1,-0.6,-1.8;-0.1,-0.05,-0.02,-0.2,-0.05;-0.

8、05,-0.1,-0.02,-0.2,-0.08;1,1,1,1,1;b=-60;-3;-8;52;lb=0,0,0,0,0;x,z=linprog(c,A,b,lb)Optimization terminated successfully.x = 0.0000 12.0000 0.0000 30.0000 10.0000z = 22.4000習題習題11.建立下列線性規(guī)劃問題的數(shù)學(xué)模型（1）某工廠生產(chǎn)A、B、C三種產(chǎn)品，三種產(chǎn)品對于材料費用、勞動力和電力的單位消耗系數(shù)，資源限量和單位產(chǎn)品價格如表1.1所示。問應(yīng)如何確定生產(chǎn)計劃可使得總產(chǎn)值達到最大？建立線性規(guī)劃問題的數(shù)學(xué)模型。 表表1.1 生

9、產(chǎn)計劃問題的數(shù)據(jù)生產(chǎn)計劃問題的數(shù)據(jù) 產(chǎn)品產(chǎn)品資源資源ABC資源資源限量限量材料費用（元）材料費用（元）22.54320勞動力（人天）勞動力（人天）618640電力（度）電力（度）5510750單位價格（百元單位價格（百元）6410（2）某療養(yǎng)院營養(yǎng)師要為某類病人擬訂一周的菜單?？晒┻x擇的蔬菜及其費用和所含營養(yǎng)成分的數(shù)量以及這類病人每周所需各種營養(yǎng)成分的最低數(shù)量如表1.2所示。另外，為了口味的需要，規(guī)定一周內(nèi)所用卷心菜不多于2份，其他蔬菜不多于4份。若病人每周需要14份蔬菜，問選用每種蔬菜各多少份，可使生活費用最小。建立線性規(guī)劃問題的數(shù)學(xué)模型。表表1.2 食譜問題的數(shù)據(jù)食譜問題的數(shù)據(jù)蔬菜蔬菜每份

10、蔬菜所含營養(yǎng)成分每份蔬菜所含營養(yǎng)成分費用費用（元（元/份）份）鐵鐵(mg)磷磷(mg)VA(單位單位)VC(mg)煙酸煙酸(mg)青豆青豆0.451041580.31.5胡蘿卜胡蘿卜0.4528906530.351.5花菜花菜1.05502550530.62.4卷心菜卷心菜0.42575270.150.6甜菜甜菜0.5221550.251.8土豆土豆0.57523580.81.0每周營養(yǎng)每周營養(yǎng)最低需求量最低需求量6.0325175002455.0123123 (3)1000,B BBA AA某農(nóng)場承包畝土地，因土壤等自然條件不同，?，F(xiàn)要在三類地上種植三種作物。各土地的面積、各類作物的計劃播種

11、面積以及各種作物在各種土地上的畝產(chǎn)量如表1.3所示。問應(yīng)如何因地制宜安排作物布局才使總產(chǎn)量最大？建立線性規(guī)劃問題的數(shù)學(xué)模型。播種計劃表畝產(chǎn)量表土地作物作物面積100600700500500800500850400400150300土地面積2003005001A2A3A1B2B3B3B2B1B（4）某糖果廠用原料A、B、C加工成三種不同牌號的糖果甲、乙、丙，已知各種牌號的糖果中A、B、C的含量，原料成本，各種原料的每月限制用量，三種牌號糖果的單位加工費及售價如表1.4所示，問該廠每月應(yīng)生產(chǎn)這三種牌號的糖果各多少千克，使該廠獲利最大？試建立這個問題的線性規(guī)劃數(shù)學(xué)模型。%60%15%20%60%50

12、甲乙丙原料成本(元/千克)每月限制用量（千克）A8.002000B6.002500C4.001200加工費（元/千克）2.01.61.2售價（元）13.611.49表表1.4 糖果廠生產(chǎn)計劃數(shù)據(jù)表糖果廠生產(chǎn)計劃數(shù)據(jù)表 (5)1.5yx已 知 一 個 量 依 賴 于 另 一 個 量 ， 現(xiàn) 收 集 有 數(shù) 據(jù) 如表。0.00.51.01.51.92.53.03.54.04.51.00.90.71.52.02.43.22.02.73.55.05.56.06.67.07.68.59.010.01.04.03.62.75.74.66.06.87.3xyxy表1.5 隨 變化的數(shù)據(jù)表xy求擬合以上數(shù)據(jù)的

13、直線 ，目標為使y的各個觀察值同按直線關(guān)系所預(yù)期的值的絕對偏差總和為最?。矗赫`差絕對值之和最?。＝⒕€性規(guī)劃問題的數(shù)學(xué)模型。（提示：對任意的 ，令： 那么， ）abxyi110022iiiiiiuv，iiiiiiuvuv，2.將下列線性規(guī)劃問題化成標準形無限制32121321321321, 0,306460682032. .minxxxxxxxxxxxtsxxxS(1)無限制321321321321321, 0,159761357195. .532maxxxxxxxxxxxxxtsxxxS(2)3.用圖解法求解下列線性規(guī)劃問題12121212max233624. .212,0Sxxxxst

14、xxx x(1)1212121212min4223. .33,0Sxxxxxxstxxx x(2)12121221212max393224. .6250,0Sxxxxxxstxxxx x(3)1212121212max4103121. .1,0Sxxxxxxstxxx x(4)12121212min2. .31,0Sxxxxstxxx x(5)4.試將下述問題改寫成線性規(guī)劃問題1211112m axm in,1. .0,1, 2,mmmiiiiiniiiimiaxaxaxxxxs txim(1)(2)( )(1)(2)( )()max,()() max,kkLPSLPLPSLP如果， ，都是線

15、性規(guī)劃問題： 的可行解，則它們的任意凸組合也是的可行解；如果，都是線性規(guī)劃問題：的最優(yōu)解，則它們的任意凸組合也是()的最優(yōu)解。5.xxxcx Axb xoxxxcx Axb xo*() max,0 (1)max() (2)1(3)maxLPSkSkkSkk如果是線性規(guī)劃問題：的最優(yōu)解，為某個常數(shù)，分別討論以下情況時最優(yōu)解的變化：目標函數(shù)變?yōu)?，約束條件不變；目標函數(shù)不變，約束條件變?yōu)椋荒繕撕瘮?shù)變?yōu)榧s束條件變?yōu)椤?6.xcx Axb xocxAxb cx,Axb0*0 7.max,max,()()0*SSc xx若線性規(guī)劃問題的最優(yōu)解 ，的最優(yōu)解 。 證明：cx Axb xoxc x Axb xo

16、xc8.用單純形方法求解下列線性規(guī)劃問題0,6242.2max32121321321xxxxxxxxtsxxxS(1)0,201022603.2max321321321321321xxxxxxxxxxxxtsxxxS(2)0, 0, 0242126042.61314max321321321321xxxxxxxxxtsxxxS(3)0, 0, 018216441022.46max321321321321321xxxxxxxxxxxxtsxxxS(4)9某工廠在計劃期內(nèi)要安排甲、乙兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制和每單位產(chǎn)品的獲利如表1.6。問工廠

17、應(yīng)分別生產(chǎn)甲、乙產(chǎn)品多少單位才能使工廠獲利最大？建立線性規(guī)劃問題數(shù)學(xué)模型，并用單純形方法求出最優(yōu)解。 產(chǎn)品資源甲乙資源限制設(shè)備11300臺時原料A21400千克原料B01250千克單位產(chǎn)品獲利50元100元表1.6 資源配置問題的數(shù)據(jù)10.對于線性規(guī)劃問題：0,52max432143214321xxxxxxxxxxxxS（1）求該線性規(guī)劃問題的全體基本最優(yōu)解；（2）確定任意最優(yōu)解的表達式。11.用兩階段法求解線性規(guī)劃問題。0,10527.532max321321321321xxxxxxxxxtsxxxS(1)0,52010651535.765min321321321321321xxxxxxxx

18、xxxxtsxxxS(2)12312312123min23428.326,0Sxxxxxxstxxx x x(3)123123123123123max101512539561515.25,0Sxxxxxxxxxstxxxx x x(4)12.某工廠在計劃期內(nèi)要安排甲、乙兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗，以及資源的限制和每單位產(chǎn)品的獲利如下表1.7。問工廠應(yīng)分別生產(chǎn)甲、乙產(chǎn)品多少單位才能使工廠獲利最大？對應(yīng)的最大利潤是多少？建立線性規(guī)劃問題的數(shù)學(xué)模型，并用單純形方法求出所有的基礎(chǔ)最優(yōu)解。 產(chǎn)品資源甲乙資源限制設(shè)備11300臺時原料A21400千克原料B012

19、50千克單位產(chǎn)品獲利50元50元 表1.7 資源配置問題的數(shù)據(jù)13.考慮下述線性規(guī)劃問題1 12211 1122121 1222212max. .0,0Sc xc xa xa xbsta xa xbxx12111212122213 4613 25 81225 461014ccaabaab式中，。試確定目標函數(shù)最優(yōu)值的下界與上界。14用LINGO和MATLAB求解本章習題中的線性規(guī)劃問題。123451234512345123451234512345min0.20.70.40.30.50.320.61.8600.10.050.020.20.0530.050.10.020.20.088.52,0Sx

20、xxxxxxxxxxxxxxxxxxxstxxxxxx xx xx在LINGO的MODEL窗口內(nèi)輸入如下模型：Min=0.2*x1+0.7*x2+0.4*x3+0.3*x4+0.5*x5;0.3*x1+2*x2+x3+0.6*x4+1.8*x560;0.1*x1+0.05*x2+0.02*x3+0.2*x4+0.05*x53;0.05*x1+0.1*x2+0.02*x3+0.2*x4+0.08*x58;X1+x2+x3+x4+x552; 附錄：附錄： 用用LINGO求解食譜問題。求解食譜問題。 解解 食譜問題的數(shù)學(xué)模型為食譜問題的數(shù)學(xué)模型為:求解輸出結(jié)果如下:Global optimal solution