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

1、32021年10月28日 線性規(guī)劃的一般模型；線性規(guī)劃的一般模型； 線性規(guī)劃解的概念與理論；線性規(guī)劃解的概念與理論； 線性規(guī)劃的求解方法；線性規(guī)劃的求解方法； 線性規(guī)劃的軟件求解方法；線性規(guī)劃的軟件求解方法； 線性規(guī)劃的應(yīng)用案例分析。線性規(guī)劃的應(yīng)用案例分析。 42021年10月28日每種資源的擁有量每種資源的擁有量和每種產(chǎn)品所消耗和每種產(chǎn)品所消耗的資源量，以及單的資源量，以及單位產(chǎn)品的利潤(rùn)如下位產(chǎn)品的利潤(rùn)如下表，試問(wèn)如何安排表，試問(wèn)如何安排生產(chǎn)計(jì)劃使得該企生產(chǎn)計(jì)劃使得該企業(yè)獲利最大業(yè)獲利最大? 1. 問(wèn)題的提出問(wèn)題的提出52021年10月28日), 2 , 1(0), 2 , 1(. .max

2、11njxmibxat sxczjnjijijnjjj 1. 問(wèn)題的提出問(wèn)題的提出62021年10月28日 2 .線性規(guī)劃模型的一般形式線性規(guī)劃模型的一般形式 72021年10月28日 3 .線性規(guī)劃模型的標(biāo)準(zhǔn)型線性規(guī)劃模型的標(biāo)準(zhǔn)型 0),(. .(min)maxXbXAtsXCz標(biāo)標(biāo)準(zhǔn)準(zhǔn)化化方方法法：82021年10月28日（1）解：）解： 1 .線性規(guī)劃解的概念線性規(guī)劃解的概念0),(. .(min)maxXbXAtsXCz92021年10月28日 1. 線性規(guī)劃解的概念線性規(guī)劃解的概念（2）基）基102021年10月28日 1. 線性規(guī)劃解的概念線性規(guī)劃解的概念0.max1XbxPtsX

3、Cznjjj（4）基可行解：）基可行解：滿(mǎn)足非負(fù)約束條件的基解稱(chēng)為基滿(mǎn)足非負(fù)約束條件的基解稱(chēng)為基可行解?？尚薪狻＃?）可行基：）可行基：對(duì)應(yīng)于基可行解的基稱(chēng)為可行基。對(duì)應(yīng)于基可行解的基稱(chēng)為可行基。112021年10月28日 2 、線性規(guī)劃解的基本理論、線性規(guī)劃解的基本理論 定理定理3 （1）如果線性規(guī)劃問(wèn)題的可行域有界，）如果線性規(guī)劃問(wèn)題的可行域有界，則問(wèn)題的最優(yōu)解一定在可行域的頂點(diǎn)上達(dá)到。則問(wèn)題的最優(yōu)解一定在可行域的頂點(diǎn)上達(dá)到。（2）如果線性規(guī)劃問(wèn)題的可行域有無(wú)界，則問(wèn)題）如果線性規(guī)劃問(wèn)題的可行域有無(wú)界，則問(wèn)題可能無(wú)最優(yōu)解；若有最優(yōu)解也一定在可行域的某個(gè)可能無(wú)最優(yōu)解；若有最優(yōu)解也一定在可行域

4、的某個(gè)頂點(diǎn)上達(dá)到。頂點(diǎn)上達(dá)到。122021年10月28日 1、單純形法的基本思想、單純形法的基本思想 尋求問(wèn)題的一個(gè)基可行解尋求問(wèn)題的一個(gè)基可行解( (即可行域的頂點(diǎn)即可行域的頂點(diǎn)) )；檢查該基可行解是否為最優(yōu)解；如果不是，則設(shè)法檢查該基可行解是否為最優(yōu)解；如果不是，則設(shè)法再求另一個(gè)沒(méi)有檢查過(guò)的基可行解再求另一個(gè)沒(méi)有檢查過(guò)的基可行解, ,如此進(jìn)行下去如此進(jìn)行下去, ,直到得到某一個(gè)基可行解為最優(yōu)解為止。直到得到某一個(gè)基可行解為最優(yōu)解為止。 現(xiàn)在要解決的問(wèn)題：現(xiàn)在要解決的問(wèn)題： （1)1)如何求出第一個(gè)基可行解？如何求出第一個(gè)基可行解？ （2)2)如何判斷基可行解是否為最優(yōu)解？如何判斷基可行解

5、是否為最優(yōu)解？ （3)3)如何由一個(gè)基可行解過(guò)渡到另一個(gè)基可行如何由一個(gè)基可行解過(guò)渡到另一個(gè)基可行解？解？ 2、線性規(guī)劃的、線性規(guī)劃的MATLAB求解求解132021年10月28日MATLAB(Matrix Laboratory)的基本含義是矩的基本含義是矩陣實(shí)驗(yàn)室；陣實(shí)驗(yàn)室； 它是由美國(guó)它是由美國(guó)MathWorks公司研制開(kāi)發(fā)的一套高公司研制開(kāi)發(fā)的一套高性能的基數(shù)值計(jì)算、信息處理、圖形顯示等于一體性能的基數(shù)值計(jì)算、信息處理、圖形顯示等于一體的可視化數(shù)學(xué)工具軟件。的可視化數(shù)學(xué)工具軟件。142021年10月28日 MATLAB的優(yōu)化工具箱的優(yōu)化工具箱(Optimization toolbox)，

6、它的它的基本功能基本功能： (1) 求解線性規(guī)劃和二次規(guī)劃問(wèn)題；求解線性規(guī)劃和二次規(guī)劃問(wèn)題； (2) 求解無(wú)約束條件非線性規(guī)劃的極小值問(wèn)題；求解無(wú)約束條件非線性規(guī)劃的極小值問(wèn)題； (3) 求解帶約束條件非線性規(guī)劃極小值問(wèn)題；求解帶約束條件非線性規(guī)劃極小值問(wèn)題； (4) 求解非線性方程組；求解非線性方程組； (5) 求解帶約束約束的線性最小二乘問(wèn)題；求解帶約束約束的線性最小二乘問(wèn)題； (6) 求解非線性最小二乘逼近和曲線擬合問(wèn)題求解非線性最小二乘逼近和曲線擬合問(wèn)題.152021年10月28日應(yīng)用應(yīng)用MATLAB優(yōu)化工具箱中的函數(shù)優(yōu)化工具箱中的函數(shù)linprog來(lái)求來(lái)求解線性規(guī)劃問(wèn)題，要求線性規(guī)劃

7、模型化為統(tǒng)一的解線性規(guī)劃問(wèn)題，要求線性規(guī)劃模型化為統(tǒng)一的基本模型：基本模型：162021年10月28日x=linprog(C,A1,b1,A2,b2)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)；x=linprog(C,A1,b1,A2,b2,x1,x2,opt)x=linprog(C,A1,b1,A2,b2,x1,x2,opt)； % 設(shè)置可選參數(shù)值，而不是采用缺省值設(shè)置可選參數(shù)值，而不是采用缺省值x=linprog(C,A1,b1,A2,b2,x1,x2,x0,op

8、t)x=linprog(C,A1,b1,A2,b2,x1,x2,x0,opt)； % x0 x0為初始解，缺省值為為初始解，缺省值為0.0.172021年10月28日x,fv=linprog()x,fv=linprog()； 要求返回目標(biāo)函數(shù)值要求返回目標(biāo)函數(shù)值x,fv,ef=linprog()x,fv,ef=linprog()；要求返回程序結(jié)束標(biāo)志要求返回程序結(jié)束標(biāo)志x,fv,ef,out=linprog()x,fv,ef,out=linprog()； 要求返回程序的優(yōu)化信息要求返回程序的優(yōu)化信息x,fv,ef,out,lambda=linprog()x,fv,ef,out,lambda=l

9、inprog()； 要求返回在程序停止時(shí)的拉格朗日乘子要求返回在程序停止時(shí)的拉格朗日乘子182021年10月28日LINGO(Linear Interactive and General Optimizer )的基的基本含義是交互式的線性和通用優(yōu)化求解器本含義是交互式的線性和通用優(yōu)化求解器它是美國(guó)芝加哥大學(xué)的它是美國(guó)芝加哥大學(xué)的 Linus Schrage 教授于教授于1980年開(kāi)發(fā)了一套用于求解最優(yōu)化問(wèn)題的工具包，后來(lái)經(jīng)年開(kāi)發(fā)了一套用于求解最優(yōu)化問(wèn)題的工具包，后來(lái)經(jīng)過(guò)完善成何擴(kuò)充，并成立了過(guò)完善成何擴(kuò)充，并成立了LINGO SYSTEM INC 3、線性規(guī)劃的、線性規(guī)劃的LINGO解法解法1

10、92021年10月28日 LINGO功能功能：求解線性規(guī)劃、二次規(guī)劃、：求解線性規(guī)劃、二次規(guī)劃、非線性規(guī)劃、目標(biāo)規(guī)劃、圖論與網(wǎng)絡(luò)優(yōu)化、整數(shù)非線性規(guī)劃、目標(biāo)規(guī)劃、圖論與網(wǎng)絡(luò)優(yōu)化、整數(shù)規(guī)劃的求解，以及一些線性和非線性方程規(guī)劃的求解，以及一些線性和非線性方程(組組)、最大最小和排隊(duì)論中的最優(yōu)化問(wèn)題求解等最大最小和排隊(duì)論中的最優(yōu)化問(wèn)題求解等 202021年10月28日 LINGO的特色的特色：它允許優(yōu)化模型中的決策變量為整數(shù)，即可它允許優(yōu)化模型中的決策變量為整數(shù)，即可以求解整數(shù)規(guī)劃，而且執(zhí)行速度快以求解整數(shù)規(guī)劃，而且執(zhí)行速度快求解線性和非線性?xún)?yōu)化問(wèn)題的簡(jiǎn)易工具求解線性和非線性?xún)?yōu)化問(wèn)題的簡(jiǎn)易工具LING

11、O內(nèi)置了一種建立最優(yōu)化模型的語(yǔ)言，內(nèi)置了一種建立最優(yōu)化模型的語(yǔ)言，可以簡(jiǎn)便地表達(dá)大規(guī)模問(wèn)題，可以簡(jiǎn)便地表達(dá)大規(guī)模問(wèn)題，212021年10月28日222021年10月28日數(shù)數(shù)據(jù)據(jù)段段集集合合段段目標(biāo)目標(biāo)約束約束232021年10月28日242021年10月28日 1、合理下料問(wèn)題、合理下料問(wèn)題(1)(1)問(wèn)題的提出：?jiǎn)栴}的提出：某單位需要加工制作某單位需要加工制作100100套套工架，每套工架需用長(zhǎng)為工架，每套工架需用長(zhǎng)為2.92.9米，米，2.12.1米和米和1.51.5米米的圓鋼各一根。已知原材料長(zhǎng)的圓鋼各一根。已知原材料長(zhǎng)7.47.4米，現(xiàn)在的問(wèn)米，現(xiàn)在的問(wèn)題是如何下料使得所用的原材料最

12、??？題是如何下料使得所用的原材料最省？7.4m2.9m2.1m1.5m252021年10月28日 模型模型分析分析: :在每一根原材料上各一根截取在每一根原材料上各一根截取2.92.9米，米，2.12.1米和米和1.51.5米的圓鋼做成一套工架，每根原米的圓鋼做成一套工架，每根原材料剩下料頭材料剩下料頭0.90.9米，要完成米，要完成100100套工架，就需要套工架，就需要用用100100根原材料，共剩余根原材料，共剩余9090米料頭。米料頭。 7.4m2.9m2.1m1.5m0.9m262021年10月28日7.4m2.9m2.1m1.5m0.9m2.9m1.5m1.5m1.5m2.9m2.

13、9m0.1m1.5m2.9m2.1m2.1m0.3m2.1m2.1m1.5m0.2m1.5m2.1m1.5m0.8m1.5m1.5mABCDEFx1x2x3x4x5x6272021年10月28日282021年10月28日 用用MATLAB求解模型求解模型問(wèn)題的MATLAB程序: C=0, 0.1, 0.2, 0.3, 0.8;C=0, 0.1, 0.2, 0.3, 0.8; b1=0, 0, 0, 0, 0; b1=0, 0, 0, 0, 0;b2=100, 100, 100;b2=100, 100, 100;A1=-1,0,0,0,0;0,-1,0,0,0;0,0,-1,0,0; A1=-1

14、,0,0,0,0;0,-1,0,0,0;0,0,-1,0,0; 0,0,0,-1,0;0,0,0,0,-1; 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;A2=1,2,0,1,0;0,0,2,2,1;3,1,2,0,3; x, fv=linprog(C, A1, b1, A2, b2) x, fv=linprog(C, A1, b1, A2, b2)292021年10月28日 用用LINGO求解模型求解模型0,100323100221002s.t.9 . 08 . 03 . 02 . 01 . 00min654321653216

15、5436421654321xxxxxxxxxxxxxxxxxxxxxxxxxz302021年10月28日 用用LINGO求解模型求解模型某投資公司擬制定今后五年的投資計(jì)劃，初某投資公司擬制定今后五年的投資計(jì)劃，初步考慮下面的四個(gè)投資項(xiàng)目：步考慮下面的四個(gè)投資項(xiàng)目：AB 2、連續(xù)投資問(wèn)題、連續(xù)投資問(wèn)題312021年10月28日問(wèn)題問(wèn)題: 現(xiàn)有投資金額現(xiàn)有投資金額100萬(wàn)元，如何使得第五年萬(wàn)元，如何使得第五年年末能夠獲得最大的利潤(rùn)。年末能夠獲得最大的利潤(rùn)。CD 2、連續(xù)投資問(wèn)題、連續(xù)投資問(wèn)題322021年10月28日 年份項(xiàng)目12345Ax11x21x31x41Bx32Cx23Dx14x24x34

16、x44x54332021年10月28日第第1 1年：年：將將100100萬(wàn)元資金全部用于項(xiàng)目萬(wàn)元資金全部用于項(xiàng)目A A和項(xiàng)目和項(xiàng)目D D的的投資，即投資，即10000001411 xx342021年10月28日352021年10月28日362021年10月28日連續(xù)投資問(wèn)題的數(shù)學(xué)模型連續(xù)投資問(wèn)題的數(shù)學(xué)模型:372021年10月28日MODEL:MODEL: sets: sets:row/1.5/; row/1.5/; arrange/1.4/;arrange/1.4/;link(row,arrange):c,x;link(row,arrange):c,x;endsetsendsetsdata:

17、 data: 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; 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; enddataenddataOBJOBJmaxmax= =sumsum(link(i,j):c(i,j)(link(i,j):c(i,j)* *x(i,j);x(i,j);x(1,1)+x(1,4)=1000000;x(1,1)+x(1,4)=1000000;-1.06-1.06* *x(1,4)+x(2,1)+x(2,3)+x(2,4)=0;x(

18、1,4)+x(2,1)+x(2,3)+x(2,4)=0;-1.15-1.15* *x(1,1)-1.06x(1,1)-1.06* *x(2,4)+x(3,1)+x(3,2)+x(3,4)=0;x(2,4)+x(3,1)+x(3,2)+x(3,4)=0;-1.15-1.15* *x(2,1)-1.06x(2,1)-1.06* *x(3,4)+x(4,1)+x(4,4)=0;x(3,4)+x(4,1)+x(4,4)=0;-1.15-1.15* *x(3,1)-1.06x(3,1)-1.06* *x(4,4)+x(5,4)=0;x(4,4)+x(5,4)=0;x(3,2)=400000;x(3,2)

19、=400000;x(2,3)=300000;x(2,3)=0;);for(link(i,j):x(i,j)=0;);ENDEND 用用LINGO求解模型求解模型382021年10月28日問(wèn)題的連續(xù)投資方案：?jiǎn)栴}的連續(xù)投資方案：第第1年：項(xiàng)目年：項(xiàng)目A為為716981.1元和項(xiàng)目元和項(xiàng)目D為為283018.9元元第第2年：項(xiàng)目年：項(xiàng)目C的投資金額為的投資金額為300000元，元，第第3年：項(xiàng)目年：項(xiàng)目A的投資為的投資為424528.3元和項(xiàng)目元和項(xiàng)目B為為400000元，元，第第5年：投資項(xiàng)目年：投資項(xiàng)目D的金額為的金額為488207.5。第第5年年末該公司擁有總資金為年年末該公司擁有總資金為1437500元，即收益元，即收益率為率為43.75%。 392021年10月28日402021年10月28日 3、南水北調(diào)水指標(biāo)分配問(wèn)題、南水北調(diào)水指標(biāo)分配問(wèn)題 南水北調(diào)中線工程建成后，預(yù)計(jì)南水北調(diào)中線工程建成后，預(yù)計(jì)2010年年調(diào)水年年調(diào)水量為量為110億立方米，主要用來(lái)解決京、津