第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)品的利潤如下位產(chǎn)品的利潤如下表，試問如何安排表，試問如何安排生產(chǎn)計(jì)劃使得該企生產(chǎn)計(jì)劃使得該企業(yè)獲利最大業(yè)獲利最大? 1. 問題的提出問題的提出52021年10月28日), 2 , 1(0), 2 , 1(. .max

2、11njxmibxat sxczjnjijijnjjj 1. 問題的提出問題的提出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）基可行解：）基可行解：滿足非負(fù)約束條件的基解稱為基滿足非負(fù)約束條件的基解稱為基可行解?？尚薪?。（5）可行基：）可行基：對(duì)應(yīng)于基可行解的基稱為可行基。對(duì)應(yīng)于基可行解的基稱為可行基。112021年10月28日 2 、線性規(guī)劃解的基本理論、線性規(guī)劃解的基本理論 定理定理3 （1）如果線性規(guī)劃問題的可行域有界，）如果線性規(guī)劃問題的可行域有界，則問題的最優(yōu)解一定在可行域的頂點(diǎn)上達(dá)到。則問題的最優(yōu)解一定在可行域的頂點(diǎn)上達(dá)到。（2）如果線性規(guī)劃問題的可行域有無界，則問題）如果線性規(guī)劃問題的可行域有無界，則問題可能無最優(yōu)解；若有最優(yōu)解也一定在可行域的某個(gè)可能無最優(yōu)解；若有最優(yōu)解也一定在可行域

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

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

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

7、模型化為統(tǒng)一的解線性規(guī)劃問題，要求線性規(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)化求解器它是美國芝加哥大學(xué)的它是美國芝加哥大學(xué)的 Linus Schrage 教授于教授于1980年開發(fā)了一套用于求解最優(yōu)化問題的工具包，后來經(jīng)年開發(fā)了一套用于求解最優(yōu)化問題的工具包，后來經(jīng)過完善成何擴(kuò)充，并成立了過完善成何擴(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)化問題求解等最大最小和排隊(duì)論中的最優(yōu)化問題求解等 202021年10月28日 LINGO的特色的特色：它允許優(yōu)化模型中的決策變量為整數(shù)，即可它允許優(yōu)化模型中的決策變量為整數(shù)，即可以求解整數(shù)規(guī)劃，而且執(zhí)行速度快以求解整數(shù)規(guī)劃，而且執(zhí)行速度快求解線性和非線性優(yōu)化問題的簡易工具求解線性和非線性優(yōu)化問題的簡易工具LING

11、O內(nèi)置了一種建立最優(yōu)化模型的語言，內(nèi)置了一種建立最優(yōu)化模型的語言，可以簡便地表達(dá)大規(guī)模問題，可以簡便地表達(dá)大規(guī)模問題，212021年10月28日222021年10月28日數(shù)數(shù)據(jù)據(jù)段段集集合合段段目標(biāo)目標(biāo)約束約束232021年10月28日242021年10月28日 1、合理下料問題、合理下料問題(1)(1)問題的提出：問題的提出：某單位需要加工制作某單位需要加工制作100100套套工架，每套工架需用長為工架，每套工架需用長為2.92.9米，米，2.12.1米和米和1.51.5米米的圓鋼各一根。已知原材料長的圓鋼各一根。已知原材料長7.47.4米，現(xiàn)在的問米，現(xià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求解模型求解模型問題的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ù)投資問題、連續(xù)投資問題312021年10月28日問題問題: 現(xiàn)有投資金額現(xiàn)有投資金額100萬元，如何使得第五年萬元，如何使得第五年年末能夠獲得最大的利潤。年末能夠獲得最大的利潤。CD 2、連續(xù)投資問題、連續(xù)投資問題322021年10月28日 年份項(xiàng)目12345Ax11x21x31x41Bx32Cx23Dx14x24x34

16、x44x54332021年10月28日第第1 1年：年：將將100100萬元資金全部用于項(xiàng)目萬元資金全部用于項(xiàng)目A A和項(xiàng)目和項(xiàng)目D D的的投資，即投資，即10000001411 xx342021年10月28日352021年10月28日362021年10月28日連續(xù)投資問題的數(shù)學(xué)模型連續(xù)投資問題的數(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日問題的連續(xù)投資方案：問題的連續(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)分配問題、南水北調(diào)水指標(biāo)分配問題 南水北調(diào)中線工程建成后，預(yù)計(jì)南水北調(diào)中線工程建成后，預(yù)計(jì)2010年年調(diào)水年年調(diào)水量為量為110億立方米，主要用來解決京、津