第10講線(xiàn)性規(guī)劃方法

數(shù)學(xué)建模方法及其應(yīng)用韓中庚編著數(shù)學(xué)建模教學(xué)片第十章線(xiàn)性規(guī)劃方法設(shè)計(jì)制作：主要內(nèi)容

第十章線(xiàn)性規(guī)劃方法32023年2月1日線(xiàn)性規(guī)劃的一般模型；線(xiàn)性規(guī)劃解的概念與理論；線(xiàn)性規(guī)劃的求解方法；線(xiàn)性規(guī)劃的軟件求解方法；線(xiàn)性規(guī)劃的應(yīng)用案例分析。

一、線(xiàn)性規(guī)劃的一般模型42023年2月1日每種資源的擁有量和每種產(chǎn)品所消耗的資源量，以及單位產(chǎn)品的利潤(rùn)如下表，試問(wèn)如何安排生產(chǎn)計(jì)劃使得該企業(yè)獲利最大?1.問(wèn)題的提出52023年2月1日

一、線(xiàn)性規(guī)劃的一般模型1.問(wèn)題的提出62023年2月1日2.線(xiàn)性規(guī)劃模型的一般形式

一、線(xiàn)性規(guī)劃的一般模型72023年2月1日3.線(xiàn)性規(guī)劃模型的標(biāo)準(zhǔn)型

一、線(xiàn)性規(guī)劃的一般模型標(biāo)準(zhǔn)化方法：82023年2月1日二、線(xiàn)性規(guī)劃解的概念與理論（1）解：1.線(xiàn)性規(guī)劃解的概念92023年2月1日

1.線(xiàn)性規(guī)劃解的概念（2）基102023年2月1日

1.線(xiàn)性規(guī)劃解的概念（4）基可行解：滿(mǎn)足非負(fù)約束條件的基解稱(chēng)為基可行解。（5）可行基：對(duì)應(yīng)于基可行解的基稱(chēng)為可行基。112023年2月1日

2、線(xiàn)性規(guī)劃解的基本理論定理3

（1）如果線(xiàn)性規(guī)劃問(wèn)題的可行域有界，則問(wèn)題的最優(yōu)解一定在可行域的頂點(diǎn)上達(dá)到。（2）如果線(xiàn)性規(guī)劃問(wèn)題的可行域有無(wú)界，則問(wèn)題可能無(wú)最優(yōu)解；若有最優(yōu)解也一定在可行域的某個(gè)頂點(diǎn)上達(dá)到。二、線(xiàn)性規(guī)劃解的概念與理論122023年2月1日

1、單純形法的基本思想三、線(xiàn)性規(guī)劃的求解方法

尋求問(wèn)題的一個(gè)基可行解(即可行域的頂點(diǎn))；檢查該基可行解是否為最優(yōu)解；如果不是，則設(shè)法再求另一個(gè)沒(méi)有檢查過(guò)的基可行解,如此進(jìn)行下去,直到得到某一個(gè)基可行解為最優(yōu)解為止?，F(xiàn)在要解決的問(wèn)題：（1)如何求出第一個(gè)基可行解？（2)如何判斷基可行解是否為最優(yōu)解？（3)如何由一個(gè)基可行解過(guò)渡到另一個(gè)基可行解？

2、線(xiàn)性規(guī)劃的MATLAB求解三、線(xiàn)性規(guī)劃的求解方法用MATLAB求解線(xiàn)性規(guī)劃模型132023年2月1日

MATLAB(MatrixLaboratory)的基本含義是矩陣實(shí)驗(yàn)室；它是由美國(guó)MathWorks公司研制開(kāi)發(fā)的一套高性能的基數(shù)值計(jì)算、信息處理、圖形顯示等于一體的可視化數(shù)學(xué)工具軟件。用MATLAB求解線(xiàn)性規(guī)劃模型142023年2月1日MATLAB的優(yōu)化工具箱(Optimizationtoolbox)，它的基本功能：(1)求解線(xiàn)性規(guī)劃和二次規(guī)劃問(wèn)題；(2)求解無(wú)約束條件非線(xiàn)性規(guī)劃的極小值問(wèn)題；

(3)求解帶約束條件非線(xiàn)性規(guī)劃極小值問(wèn)題；

(4)求解非線(xiàn)性方程組；

(5)求解帶約束約束的線(xiàn)性最小二乘問(wèn)題；

(6)求解非線(xiàn)性最小二乘逼近和曲線(xiàn)擬合問(wèn)題.用MATLAB求解線(xiàn)性規(guī)劃模型152023年2月1日應(yīng)用MATLAB優(yōu)化工具箱中的函數(shù)linprog來(lái)求解線(xiàn)性規(guī)劃問(wèn)題，要求線(xiàn)性規(guī)劃模型化為統(tǒng)一的基本模型：用MATLAB求解線(xiàn)性規(guī)劃模型162023年2月1日x=linprog(C,A1,b1,A2,b2)；x=linprog(C,A1,b1,A2,b2,x1,x2)；x=linprog(C,A1,b1,A2,b2,x1,x2,opt)；

%設(shè)置可選參數(shù)值，而不是采用缺省值．x=linprog(C,A1,b1,A2,b2,x1,x2,x0,opt)；

%

x0為初始解，缺省值為0.用MATLAB求解線(xiàn)性規(guī)劃模型172023年2月1日[x,fv]=linprog(……)；％要求返回目標(biāo)函數(shù)值[x,fv,ef]=linprog(……)；％要求返回程序結(jié)束標(biāo)志[x,fv,ef,out]=linprog(……)；％要求返回程序的優(yōu)化信息．[x,fv,ef,out,lambda]=linprog(……)；％要求返回在程序停止時(shí)的拉格朗日乘子．用MATLAB求解線(xiàn)性規(guī)劃模型182023年2月1日

LINGO(LinearInteractiveandGeneralOptimizer)的基本含義是交互式的線(xiàn)性和通用優(yōu)化求解器．

它是美國(guó)芝加哥大學(xué)的LinusSchrage教授于1980年開(kāi)發(fā)了一套用于求解最優(yōu)化問(wèn)題的工具包，后來(lái)經(jīng)過(guò)完善成何擴(kuò)充，并成立了LINGO

SYSTEMINC．

3、線(xiàn)性規(guī)劃的LINGO解法三、線(xiàn)性規(guī)劃的求解方法192023年2月1日

LINGO功能：求解線(xiàn)性規(guī)劃、二次規(guī)劃、非線(xiàn)性規(guī)劃、目標(biāo)規(guī)劃、圖論與網(wǎng)絡(luò)優(yōu)化、整數(shù)規(guī)劃的求解，以及一些線(xiàn)性和非線(xiàn)性方程(組)、最大最小和排隊(duì)論中的最優(yōu)化問(wèn)題求解等．用LINGO求解線(xiàn)性規(guī)劃模型202023年2月1日

LINGO的特色：它允許優(yōu)化模型中的決策變量為整數(shù)，即可以求解整數(shù)規(guī)劃，而且執(zhí)行速度快．

求解線(xiàn)性和非線(xiàn)性?xún)?yōu)化問(wèn)題的簡(jiǎn)易工具．

LINGO內(nèi)置了一種建立最優(yōu)化模型的語(yǔ)言，可以簡(jiǎn)便地表達(dá)大規(guī)模問(wèn)題，用LINGO求解線(xiàn)性規(guī)劃模型212023年2月1日用LINGO求解線(xiàn)性規(guī)劃模型222023年2月1日數(shù)據(jù)段集合段目標(biāo)約束用LINGO求解線(xiàn)性規(guī)劃模型232023年2月1日242023年2月1日

1、合理下料問(wèn)題四、線(xiàn)性規(guī)劃的應(yīng)用案例分析

(1)問(wèn)題的提出：某單位需要加工制作100套工架，每套工架需用長(zhǎng)為2.9米，2.1米和1.5米的圓鋼各一根。已知原材料長(zhǎng)7.4米，現(xiàn)在的問(wèn)題是如何下料使得所用的原材料最??？7.4m2.9m2.1m1.5m252023年2月1日

模型分析:在每一根原材料上各一根截取2.9米，2.1米和1.5米的圓鋼做成一套工架，每根原材料剩下料頭0.9米，要完成100套工架，就需要用100根原材料，共剩余90米料頭。

7.4m2.9m2.1m1.5m0.9m案例1:合理下料問(wèn)題262023年2月1日案例1:合理下料問(wèn)題7.4m2.9m2.1m1.5m0.9m2.9m1.5m1.5m1.5m2.9m2.9m0.1m1.5m2.9m2.1m2.1m0.3m2.1m2.1m1.5m0.2m1.5m2.1m1.5m0.8m1.5m1.5mABCDEFx1

x2x3x4x5x6272023年2月1日案例1:合理下料問(wèn)題282023年2月1日案例1:合理下料問(wèn)題

用MATLAB求解模型問(wèn)題的MATLAB程序:

C=[0,0.1,0.2,0.3,0.8]’;b1=[0,0,0,0,0]’;b2=[100,100,100]’;A1=[-1,0,0,0,0;0,-1,0,0,0;0,0,-1,0,0;0,0,0,-1,0;0,0,0,0,-1]’;A2=[1,2,0,1,0;0,0,2,2,1;3,1,2,0,3];[x,fv]=linprog(C,A1,b1,A2,b2)292023年2月1日案例1:合理下料問(wèn)題

用LINGO求解模型302023年2月1日案例1:合理下料問(wèn)題

用LINGO求解模型

某投資公司擬制定今后五年的投資計(jì)劃，初步考慮下面的四個(gè)投資項(xiàng)目：AB

2、連續(xù)投資問(wèn)題四、線(xiàn)性規(guī)劃的應(yīng)用案例分析312023年2月1日問(wèn)題:

現(xiàn)有投資金額100萬(wàn)元，如何使得第五年年末能夠獲得最大的利潤(rùn)。CD

2、連續(xù)投資問(wèn)題四、線(xiàn)性規(guī)劃的應(yīng)用案例分析322023年2月1日年份項(xiàng)目12345Ax11x21x31x41Bx32Cx23Dx14x24x34x44x54案例2:連續(xù)投資問(wèn)題332023年2月1日第1年：將100萬(wàn)元資金全部用于項(xiàng)目A和項(xiàng)目D的投資，即案例2:連續(xù)投資問(wèn)題342023年2月1日案例2:連續(xù)投資問(wèn)題352023年2月1日案例2:連續(xù)投資問(wèn)題362023年2月1日案例2:連續(xù)投資問(wèn)題連續(xù)投資問(wèn)題的數(shù)學(xué)模型:372023年2月1日MODEL:sets:row/1..5/;arrange/1..4/;link(row,arrange):c,x;endsetsdata:c=0,0,0,0,0,0,1.40,0,0,1.25,0,0,1.15,0,0,0,0,0,0,1.06;enddata[OBJ]max=@sum(link(i,j):c(i,j)*x(i,j));x(1,1)+x(1,4)=1000000;-1.06*x(1,4)+x(2,1)+x(2,3)+x(2,4)=0;-1.15*x(1,1)-1.06*x(2,4)+x(3,1)+x(3,2)+x(3,4)=0;-1.15*x(2,1)-1.06*x(3,4)+x(4,1)+x(4,4)=0;-1.15*x(3,1)-1.06*x(4,4)+x(5,4)=0;x(3,2)<=400000;x(2,3)<=300000;@for(link(i,j):x(i,j)>=0;);END案例2:連續(xù)投資問(wèn)題

用LINGO求解模型382023年2月1日問(wèn)題的連續(xù)投資方案：第1年：項(xiàng)目A為716981.1元和項(xiàng)目D為283018.9元第2年：項(xiàng)目C的投資金額為300000元，第3年：項(xiàng)目A的投資為424528.3元和項(xiàng)目B為400000元，第5年：投資項(xiàng)目D的金額為488207.5。第5年年末該公司擁有總資金為1437500元，即收益率為43.75%。案例2:連續(xù)投資問(wèn)題392023年2月1日402023年2月1日

3、南水北調(diào)水指標(biāo)分配問(wèn)題四、線(xiàn)性規(guī)劃的應(yīng)用案例分析南水北調(diào)中線(xiàn)工程建成后，預(yù)計(jì)2010年年調(diào)水量為110億立方米，主要用來(lái)解決京、津、冀、豫四省（市）的沿線(xiàn)20個(gè)大中城市的生活用水、工業(yè)用水和綜合服務(wù)業(yè)的用水，分配比例分別為40％、38％和22％．這樣可以改善我國(guó)中部地區(qū)的生態(tài)環(huán)境和投資環(huán)境，推動(dòng)經(jīng)濟(jì)發(fā)展．用水指標(biāo)的分配總原則是：改善區(qū)域的缺水狀況、提高城市的生活水平、促進(jìn)經(jīng)濟(jì)發(fā)展、提高用水效益、改善城市環(huán)境．41