數學建模-線性規(guī)劃

數學建模--線性規(guī)劃第1頁，課件共70頁，創(chuàng)作于2023年2月

線性規(guī)劃問題的提出線性規(guī)劃的基本概念線性規(guī)劃的數學模型繼續(xù)返回一線性規(guī)劃問題及其數學模型第2頁，課件共70頁，創(chuàng)作于2023年2月問題的提出例:生產計劃問題第3頁，課件共70頁，創(chuàng)作于2023年2月產品I產品2如何安排生產使利潤最大？第4頁，課件共70頁，創(chuàng)作于2023年2月決策變量（Decisionvariables）目標函數（Objectivefunction）約束條件（Constraintconditions）可行域（Feasibleregion)最優(yōu)解（Optimalsolution)基本概念問題中要確定的未知量，表明規(guī)劃中的用數量表示的方案、措施，可由決策者決定和控制。它是決策變量的函數指決策變量取值時受到的各種資源條件的限制，通常表達為含決策變量的等式或不等式。滿足約束條件的決策變量的取值范圍可行域中使目標函數達到最優(yōu)的決策變量的值第5頁，課件共70頁，創(chuàng)作于2023年2月是問題中要確定的未知量，表明規(guī)劃中的用數量表示的方案、措施，可由決策者決定和控制。第1步-確定決策變量設——I的產量——II的產量——利潤第6頁，課件共70頁，創(chuàng)作于2023年2月第2步--定義目標函數MaxZ=x1+x2決策變量第7頁，課件共70頁，創(chuàng)作于2023年2月

MaxZ=2x1+3x2系數第2步--定義目標函數第8頁，課件共70頁，創(chuàng)作于2023年2月對我們有何限制?第9頁，課件共70頁，創(chuàng)作于2023年2月第3步--表示約束條件

x1+2x2

84x1

164x2

12x1、x2

0第10頁，課件共70頁，創(chuàng)作于2023年2月該計劃的數學模型

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

x2第11頁，課件共70頁，創(chuàng)作于2023年2月線性規(guī)劃問題的共同特征一組決策變量X表示一個方案,一般X大于等于零。約束條件是線性等式或不等式。目標函數是線性的。求目標函數最大化或最小化第12頁，課件共70頁，創(chuàng)作于2023年2月

線性規(guī)劃模型的一般形式第13頁，課件共70頁，創(chuàng)作于2023年2月線性規(guī)劃模型建立步驟從實際問題中建立數學模型一般有以下三個步驟；1.根據影響所要達到目的的因素找到決策變量；

2.由決策變量和所在達到目的之間的函數關系確定目標函數；

3.由決策變量所受的限制條件確定決策變量所要滿足的約束條件。第14頁，課件共70頁，創(chuàng)作于2023年2月1.線性規(guī)劃的標準形式：用單純法求解時，常將標準形式化為：2.線性規(guī)劃的基本算法——單純形法二.線性規(guī)劃的基本算法——單純形法第15頁，課件共70頁，創(chuàng)作于2023年2月引入松弛變量x3,x4,x5,將不等式化為等式,即單純形標準形:顯然A的秩ran(A)=3,任取3個線性無關的列向量,如P3P4P5稱為一組基,記為B.其余列向量稱為非基,記為N.第16頁，課件共70頁，創(chuàng)作于2023年2月于是f=cBxB+cNxN,Ax=BxB+NxN=b,則xB=B-1b-B-1NxN,f=cBB-1b+(cN–cBB-1N)xN

若可行基進一步滿足:cN–cBB-1N≥0,即:cBB-1N-cN≤0則對一切可行解x,必有f(x)≥cBB-1b,此時稱基可行解x=(B-1b,0)T為最優(yōu)解.

3.最優(yōu)解的存在性定理將A的列向量重排次序成A=(B,N),相應x=(xB,xN)T,c=(cB,cN)基對應的變量xB稱為基變量,非基對應的變量xN稱為非基變量.定理如果線性規(guī)劃(1)有最優(yōu)解，那么一定存在一個基可行解是最優(yōu)解.第17頁，課件共70頁，創(chuàng)作于2023年2月4.基可行解是最優(yōu)解的判定準則檢驗數因為Ax=BxB+NxN=b,得xB=B-1b-B-1NxN,而f=cBxB+cNxN,故f=cBB-1b+(cN–cBB-1N)xN

第18頁，課件共70頁，創(chuàng)作于2023年2月5.基可行解的改進第19頁，課件共70頁，創(chuàng)作于2023年2月改進方法：返回第20頁，課件共70頁，創(chuàng)作于2023年2月練習建立LP數學模型一、有兩個煤廠A、B，每月分別供應三個居民區(qū)X、Y、Z。求運費最少的方案。供需平衡第21頁，課件共70頁，創(chuàng)作于2023年2月1、LINGO使用簡介LINGO軟件是美國的LINDO系統(tǒng)公司（LindoSystemInc）開發(fā)的一套用于求解最優(yōu)化問題的軟件包.LINGO除了能用于求解線性規(guī)劃和二次規(guī)劃外，還可以用于非線性規(guī)劃求解以及一些線性和非線性方程（組）的求解.LINGO軟件的最大特色在于它允許優(yōu)化模型中的決策變量為整數，而且執(zhí)行速度快.LINGO內置了一種建立最優(yōu)化模型的語言，可以簡便地表達大規(guī)模問題，利用LINGO高效的求解器可快速求解并分析結果，這里簡單介紹LINGO的使用方法.

LINGO可以求解線性規(guī)劃、二次規(guī)劃、非線性規(guī)劃、整數規(guī)劃、圖論及網絡優(yōu)化和排隊論模型中的最優(yōu)化問題等.一個LINGO程序一般會包含集合段、數據輸入段、優(yōu)化目標和約束段、初始段和數據預處理段等部分，每一部分有其獨特的作用和語法規(guī)則，讀者可以通過查閱相關的參考書或者LINGO的HELP文件詳細了解，這里就不展開介紹了.

三.線性規(guī)劃軟件求解第22頁，課件共70頁，創(chuàng)作于2023年2月LINGO的主要功能特色為：既能求解線性規(guī)劃問題，也有較強的求解非線性規(guī)劃問題的能力；輸入模型簡練直觀；運算速度快、計算能力強；內置建模語言，提供幾十個內部函數，從而能以較少語句，較直觀的方式描述大規(guī)模的優(yōu)化模型；將集合的概念引入編程語言，很容易將實際問題轉換為LINGO模型；并且能方便地與Excel、數據庫等其他軟件交換數據.

第23頁，課件共70頁，創(chuàng)作于2023年2月第一步：啟動Lingo屏幕顯示如下：標記LINGO的外窗口是主框架窗口，主框架窗口的上面包含所有的命令菜單和命令工具欄；標記LINGOMODEL-LINGO1的子窗口是一個新的、空白的模型窗口。第24頁，課件共70頁，創(chuàng)作于2023年2月第二步：在模型窗口中輸入模型model:max=2*x1+3*x2;4*x1+3*x2<10;3*x1+5*x2<12;endMax2x1+3x2St.4x1+3x2<=103x1+5x2<=12x1≥0x2≥0第25頁，課件共70頁，創(chuàng)作于2023年2月第三步：求解模型

1)選擇菜單

LINGO|Solve

或者按工具欄的

第26頁，課件共70頁，創(chuàng)作于2023年2月

2)LINGO開始編譯模型，如有語法錯誤將返回一個錯誤的消息并指明錯誤出現的位置；如果通過編譯,LINGO將激活Solver運算器尋求模型的最優(yōu)解；3)首先出現solverstatus窗口，其作用是監(jiān)控solver的進展和顯示模型的維數等信息；第27頁，課件共70頁，創(chuàng)作于2023年2月第28頁，課件共70頁，創(chuàng)作于2023年2月4)計算完成后出現SolutionReport窗口顯示模型解的詳細信息；第29頁，課件共70頁，創(chuàng)作于2023年2月SolutionReport窗口Globaloptimalsolutionfoundatiteration:2Objectivevalue:7.454545VariableValueReducedCostx11.2727270.000000x21.6363640.000000RowSlackorSurplusDualPrice17.4545451.00000020.0000000.9090909E-0130.0000000.5454545（對目標函數而言）第30頁，課件共70頁，創(chuàng)作于2023年2月LINGO的語法規(guī)定、運算符及函數：（1）求目標函數的最大值或最小值分別用MAX=…或MIN=…來表示；（2）每個語句必須以分號“；”結束，每行可以有許多語句，語句可以跨行；（3）變量名稱必須以字母（A~Z）開頭，由字母、數字（0~9）和下劃線所組成，長度不超過32個字符，不區(qū)分大小寫；（4）可以給語句加上標號，例如[OBJ]MAX=200*X1+300*X2；（5）以驚嘆號“！”開頭，以分號“；”結束的語句是注釋語句；（6）如果對變量的取值范圍沒有作特殊說明，則默認所有決策變量都非負；（7）LINGO模型以語句“MODEL：”開頭，以“END”結束，對于比較簡單的模型，這兩個語句可以省略.(8)可以用<表示<=；用>表示>=；

Lingo無嚴格小于，欲使a<b，可以適當選取小的正常數e表示成a+e<b，第31頁，課件共70頁，創(chuàng)作于2023年2月(9)LINGO編輯器用藍色顯示LINGO關鍵字;

綠色顯示注釋

;其他文本用黑色

匹配的括號用紅色高亮度顯示(10)標準運算符算術運算符：^*/+-邏輯運算符：

#EQ##NE#(相等，不等）為真

#GE##GT#（左邊大于或等于，左邊大于）為真

#LE##LT#（左邊小于或等于，左邊小于）為真

#NOT##AND##OR#（取反，取交（積），取并（和）)第32頁，課件共70頁，創(chuàng)作于2023年2月(11).變量界定函數lingo變量默認域為非負實數@free(variable)

取消默認域，使變量可以取任意實數@gin(variable)限制變量取整數值@bin(variable)限制變量取值為0，1@bnd(low,variable,up)限制變量于一個有限的范圍第33頁，課件共70頁，創(chuàng)作于2023年2月例題1：某工廠在計劃期內要安排生產A、B兩種產品，已知生產單位產品所需設備臺時及對甲、乙兩種原材料的消耗，有關數據如表1.1.問：應如何安排生產計劃，使工廠獲利最大？產品資源AB可利用資源設備128臺時甲4016公斤乙0412公斤單位利潤2元3元建立線性規(guī)劃問題的數學模型，用LINGO求出最優(yōu)解并做相應的分析.第34頁，課件共70頁，創(chuàng)作于2023年2月問題1.1設計劃生產A,B兩種產品分別為x1,x2，則建立線性規(guī)劃問題數學模型模型：maxS=2x1+

3x2在LINGO的MODEL窗口內輸入如下模型：model:max=2*x1+3*x2;x1+2*x2<=8;4*x1<=16;4*x2<=12;end第35頁，課件共70頁，創(chuàng)作于2023年2月選菜單Lingo|Solve(或按Ctrl+S),或用鼠標點擊“求解”按紐，如果模型有語法錯誤，則彈出一個標題為“LINGOErrorMessage”(錯誤信息)的窗口，指出在哪一行有怎樣的錯誤，每一種錯誤都有一個編號（具體含義可查閱相關文獻或LINGO的Help）.改正錯誤以后再求解，如果語法通過，LINGO用內部所帶的求解程序求出模型的解，然后彈出一個標題為“LINGOSolverStatus”（求解狀態(tài)）的窗口，其內容為變量個數、約束條件個數、優(yōu)化狀態(tài)、耗費內存、所花時間等信息，點擊Close關閉窗口，屏幕上出現標題為“SolutionReport”（解的報告）的信息窗口，顯示優(yōu)化計算（線性規(guī)劃中換基迭代）的步數、優(yōu)化后的目標函數值、列出各變量的計算結果.求解結果：第36頁，課件共70頁，創(chuàng)作于2023年2月Globaloptimalsolutionfoundatiteration:5Objectivevalue:14.00000VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPrice114.000001.00000020.0000001.50000030.0000000.125000044.0000000.000000第37頁，課件共70頁，創(chuàng)作于2023年2月該報告說明：運行5步找到全局最優(yōu)解，目標函數值為14，變量值分別為x1=4,x2=2.“ReducedCost”的含義是需縮減成本系數或需增加利潤系數（最優(yōu)解中取值非零的決策變量的ReducedCost值等于零）.“Row”是輸入模型中的行號，目標函數是第一行；“SlackorSurplus”的意思是松弛或剩余，即約束條件左邊與右邊的差值，對于“≤”的不等式，右邊減左邊的差值為Slack（松弛），對于“>=”的不等式，左邊減右邊的差值為Surplus（剩余），當約束條件兩邊相等時，松弛或剩余的值等于零.“DualPrice”的意思是對偶價格（或稱為影子價格），上述報告中Row2的松弛值為0，表明生產甲產品4單位、乙產品2單位，所需設備8臺時已經飽和，對偶價格1.5的含義是：如果設備增加1臺時，能使目標函數值增加1.5.報告中Row4的松弛值為4，表明生產甲產品4單位、乙產品2單位，所需原材料乙8公斤還剩余4公斤，因此增加原材料乙不會使目標函數值增加，所以對偶價格為0.第38頁，課件共70頁，創(chuàng)作于2023年2月用MATLAB優(yōu)化工具箱解線性規(guī)劃minz=cX

1、模型：命令：x=linprog（c，A，b）2、模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式：存在，則令A=[]，b=[].第39頁，課件共70頁，創(chuàng)作于2023年2月3、模型：minz=cX

VLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）

[2]x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）

注意：[1]若沒有等式約束:,則令Aeq=[],beq=[].[2]其中X0表示初始點4、命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標函數值fval.第40頁，課件共70頁，創(chuàng)作于2023年2月解編寫M文件xxgh1.m如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];b=[850;700;100;900];Aeq=[];beq=[];vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

ToMatlab(xxgh1)第41頁，課件共70頁，創(chuàng)作于2023年2月

投資的收益和風險四.線性規(guī)劃應用舉例第42頁，課件共70頁，創(chuàng)作于2023年2月(二)、基本假設和符號規(guī)定第43頁，課件共70頁，創(chuàng)作于2023年2月(三)、模型的建立與分析1.總體風險用所投資的Si中最大的一個風險來衡量,即max{qixi|i=1，2,…n}4.模型簡化：第44頁，課件共70頁，創(chuàng)作于2023年2月第45頁，課件共70頁，創(chuàng)作于2023年2月(四)、模型1的求解

由于a是任意給定的風險度，到底怎樣給定沒有一個準則，不同的投資者有不同的風險度。我們從a=0開始，以步長△a=0.001進行循環(huán)搜索，編制程序如下：第46頁，課件共70頁，創(chuàng)作于2023年2月a=0;while(1.1-a)>1c=[-0.05-0.27-0.19-0.185-0.185];Aeq=[11.011.021.0451.065];beq=[1];A=[00.025000;000.01500;0000.0550;00000.026];b=[a;a;a;a];vlb=[0,0,0,0,0];vub=[];[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);ax=x'Q=-valplot(a,Q,'.')，axis([00.100.5])，holdona=a+0.001;endxlabel('a'),ylabel('Q')ToMatlab（xxgh5）第47頁，課件共70頁，創(chuàng)作于2023年2月計算結果：第48頁，課件共70頁，創(chuàng)作于2023年2月(五)、結果分析返回4.在a=0.006附近有一個轉折點，在這一點左邊，風險增加很少時，利潤增長很快。在這一點右邊，風險增加很大時，利潤增長很緩慢，所以對于風險和收益沒有特殊偏好的投資者來說，應該選擇曲線的拐點作為最優(yōu)投資組合，大約是a*=0.6%，Q*=20%，所對應投資方案為:

風險度收益x0x1x2x3x40.00600.201900.24000.40000.10910.22123.曲線上的任一點都表示該風險水平的最大可能收益和該收益要求的最小風險。對于不同風險的承受能力，選擇該風險水平下的最優(yōu)投資組合。2.當投資越分散時，投資者承擔的風險越小，這與題意一致。即:

冒險的投資者會出現集中投資的情況，保守的投資者則盡量分散投資。1.風險大，收益也大。第49頁，課件共70頁，創(chuàng)作于2023年2月實驗作業(yè)某廠生產甲乙兩種口味的飲料,每百箱甲飲料需用原料6千克,工人10名,可獲利10萬元;每百箱乙飲料需用原料5千克,工人20名,可獲利9萬元.今工廠共有原料60千克,工人150名,又由于其他條件所限甲飲料產量不超過8百箱.問如何安排生產計劃,即兩種飲料各生產多少使獲利最大.進一步討論:1)若投資0.8萬元可增加原料1千克,問應否作這項投資.2)若每百箱甲飲料獲利可增加1萬元,問應否改變生產計劃.返回第50頁，課件共70頁，創(chuàng)作于2023年2月圖解法線性規(guī)劃問題求解的幾種可能結果由圖解法得到的啟示2線性規(guī)劃的圖解法繼續(xù)返回第51頁，課件共70頁，創(chuàng)作于2023年2月例1的數學模型

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

x2第52頁，課件共70頁，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2x1+2x2

=8(0,4)(8,0)

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

04x1

=164x2

=12圖解法第53頁，課件共70頁，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0x2

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

=84x1

=164x2

=12可行域圖解法第54頁，課件共70頁，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0x1+2x2

=84x1

=164x2

=12可行域BCDEA圖解法第55頁，課件共70頁，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0x2

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

=84x1

=164x2

=12BCDEA2x1+3x2=6圖解法第56頁，課件共70頁，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0x2

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

=164x2

=12BCDEAx1+2x2=84x1=16最優(yōu)解(4,2)圖解法第57頁，課件共70頁，創(chuàng)作于2023年2月圖解法求解步驟由全部約束條件作圖求出可行域；作目標函數等值線，確定使目標函數最優(yōu)的移動方向；平移目標函數的等值線，找出最優(yōu)點，算出最優(yōu)值。第58頁，課件共70頁，創(chuàng)作于2023年2月線性規(guī)劃問題求解的

幾種可能結果(a)唯一最優(yōu)解

x26—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1第59頁，課件共70頁，創(chuàng)作于2023年2月(b)無窮多最優(yōu)解6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1線性規(guī)劃問題求解的

幾種可能結果第60頁，課件共70頁，創(chuàng)作于2023年2月(c)無界解

MaxZ=x1+x2

-2x1+x2

4

x1-x2

2

x1、x2

0

x2x1線性規(guī)劃問題求解的

幾種可能結果第61頁，課件共70頁，創(chuàng)作于2023年2月(d)無可行解

MaxZ=2x1+3x2x1+2x2

84x1

164x2

12

-2x1+x24x1、x2

0可行域為空集線性規(guī)劃問題求解的

幾種可能結果第62頁，課件共70頁，創(chuàng)作于2023年2月圖解法的幾點結論:

（由圖解法得到的啟示）可行域是有界或無界的凸多邊形。若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點得到。若兩個頂點同時得到最優(yōu)解，則其連線上的所有點都是最優(yōu)解。解題思路：找出凸集的頂點，計算其目標函數值，比較即得。第63頁，課件共70頁，創(chuàng)作于