數學實驗第五講

————線性規劃2023/2/3122023/2/31．理解優化模型的三個要素:決策變量，目標函數和約束條件；２．掌握用MATLAB優化工具箱求解線性規劃的方法；３．體驗由實際問題建立線性規劃模型的全過程。實驗目的一,優化問題的普遍性以及引例1，無處不在的優化每一個人，高致總統首相，總裁經理，平民百姓，無不在做決策：該做什么，該怎么做，才能有最好的效果?甚至自然中的動植物，也時刻面臨這樣的問題.類似的問題，還廣泛的存在于無機世界中.2023/2/33一,優化問題的普遍性以及引例看看下面的例子分別屬于哪一類？a)證券的投資組合；b)國家經濟發展戰略；c)產品規格、性能設計；d)球形的水滴；e)狼群的集體捕食；f)好的購物方案；g)物質分子結構；

h)生物的身體構造；i)乘務組排班表;j)光傳播路徑:直線,反射,折射課堂作業：和你的同桌討論還有什么方面需要優化的。2023/2/34一,優化問題的普遍性以及引例2,一些成功的優化例子：“最優人員安排”為美國航空每年節約兩千萬美元.

“改進的出貨流程”每年為YellowFreight公司節約一千七百多萬美元.“改進的卡車分派”為

Reynolds公司每年節約七百萬美元.最優全局供應鏈為數字設備行業節約超過三億美元.重建的

NorthAmericaOperations,ProctorandGamble減少20%的工廠,每年節約兩億美元.大阪的Hanshin高速的最優安排每年節約一千七百萬人小時.2023/2/35

為說明最優化的價值,建立了專門的網站,列舉了哪些公司的什么問題,運用最優化方法節約和增加了多少金額.

有可選的行業,考察的方面,受益的方式,希望同學們各選擇其中的一個,提一份報告,以說明最優化的價值.2023/2/36一,優化問題的普遍性以及引例Google上相關搜索的結果：Searchphrasenumberofhits（英文）短語點擊數（中文）“optimizethesupplychain”1,160,000優化供應鏈414,000“optimize(the)return”2,490,000優化回報453,000“optimalexperience”32,400,000最優經歷“optimalinvestment”8,320,000優化投資8,250,000“optimalsystem”84,200,000優化系統13,800,000“optimaldecision”28,800,000最優決策2,890,000“optimizeyourPC”3,300,000優化你的PC“optimalchoice”25,800,000最優選擇10,900,000“optimaldesign”77,300,000優化設計1,270,000“optimalhealth”31,900,000優化健康還有如:優化產業結構2,830,000優化人員結構3,110,000同學們有沒有發現,英文和中文短語間有很大的不同,原因可能是什么?2023/2/37一,優化問題的普遍性以及引例3,相關的幾句格言：Wasteneithertimenormoney,butmakethebestuseofboth.--BenjaminFranklinObviously,thehighesttypeofefficiencyisthatwhichcanutilizeexistingmaterialtothebestadvantage.--JawaharlalNehruItismoreprobablethattheaveragemancould,withnoinjurytohishealth,increasehisefficiencyfiftypercent.--WalterScott請同學翻譯上面的句子，你喜歡那一句？你有什么好的表述？2023/2/38引例1,動物飼料配置問題

美國一家公司以專門飼養并出售一種實驗用的動物而聞名。這種動物的生長對飼料中的三種營養成分特別敏感，即蛋白質、礦物質和維生素。需要的營養量蛋白質：70克礦物質：3克維生素：9.1毫克

現有五種飼料，公司希望找出滿足動物營養需要使成本達到最低的混合飼料配置。2023/2/39飼料蛋白質(克)礦物質(克)維生素(毫克)1(x1)2(x2)3(x3)4(x4)5(x5)需要量0.302.001.000.601.80700.100.050.020.200.0530.050.100.020.200.089.1每一種飼料每磅所含的營養成分每種飼料每磅的成本飼料12345成本(美元)0.020.070.040.030.052023/2/310引例2:供應與選址

某公司有6個建筑工地要開工，每個工地的位置（用平面坐標a，b表示，距離單位：千米）及水泥日用量d噸由下表給出。目前有兩個臨時料場位于A(5,1),B(2,7)，日儲量各有20噸。假設從料場到工地均有直線道路相連，（1）試制定每天的供應計劃，即從A、B兩料場分別向各工地運送多少噸水泥，使總的噸千米數最小。a1.258.750.55.7537.25b1.250.754.7556.57.75d35476112023/2/311二,優化問題建模的基本步驟介紹

在我們的生活中,始終有這樣的問題:為了一定的目的做一些事情,我們可能要考慮有哪些重要的因素,這些因素和要完成的目標之間有什么樣的關系.也就是說,我們在做一個決定時,會注意下面的三個要點:目的是什么?有哪些重要的因素?這些因素和你的目標之間有什么樣的關系?2023/2/312二，優化問題的表述目標函數對應決策者而言,對其有利的程度必須定量的測度,在商業應用中，有效性的測度經常是利潤或者成本,但對于政府，更經常的使用投入產出率來測度.

表示有效性測度的經常稱為目標函數.目標函數要表出測度的有效性,必須說明測度和導致測度改變的變量之間的關系.系統變量分為決策變量和參數.決策變量是指能由決策者直接控制的變量.而參數是指不能由決策者決定的量.實際上，數學模型很少有能表達變量和有效性測度之間的精確關系的.實際上，運籌學分析者的任務就是找出對測度有最重要影響的變量然后找出這些變量和測度之間的數學關系.這個數學關系也就是目標函數.2023/2/313二，優化問題的表述決策變量和參數我們稱對應決策者可控的量稱為決策變量,決策變量的取值確定了系統的最終性能,也是決策者采用決策的依據.在系統中還有一些量,它不能由決策者所控制,而是由系統所處的環境所決定,我們稱之為參數.2023/2/314二，優化問題的表述約束條件

約束條件就是決策變量和參數之間的關系.約束集界定決策變量可以取某些值而不能取其他的值.比如對應生產問題,任何活動中,時間和物品不能為負數.當然,也有一些優化問題不帶約束條件,我們稱之為無約束優化問題.而在實際問題中,決策變量帶有約束是普遍的.2023/2/315三,優化問題的分類優化問題的分類可以從幾個方面進行:1,從變量取值的連續和離散可以分成:連續優化,離散優化和混合優化2,從問題的線性非線性可以分為:線性規劃和非線性規劃3,從變量是確定性和隨機性可以分為:隨機規劃和確定性問題.2023/2/316JohnVonNeumann

約翰·馮·諾依曼(1903－1957),美藉匈牙利人.20世紀最杰出的數學家之一,被譽為”計算機之父”,”博弈論之父”.被認為是數學規劃的三大創始人之一.以下的三個人物和線性規劃的出現有重要的關系.2023/2/317GeorgeB.Dantzig

GeorgeB.Dantzig(1914-2005),美國人,線性規劃單純形法的創始人,被譽為”線性規劃之父”.美國科學院三院院士,美國軍方數學顧問,教授.并以其名字設立Dantzig獎.數學規劃的三大創始人之一.發現算法時非常年輕,以至到日本時,人們以為”線性規劃之父”是個老人,而對他無人問津.2023/2/318LeonidVitalyevichKantorovichKantorovich(1912-1986)蘇聯人,著名數學家和經濟學家,教授,年僅18歲獲博士學位.因在經濟學上提出稀缺資源的最優配置獲諾貝爾獎.線性規劃對偶理論的提出者,數學規劃的三大創始人之一.2023/2/319非線性規劃問題在實踐中也是及其常見的.標志著這一學科的產生的奠基性工作由美國的數學家Tucker和Kuhn在1952年的一篇文章.該文章給出了非線性規劃問題的必要條件和充分條件,后來成為Kuhn-Tucker條件.這為非線性規劃問題的求解算法的提出提供了理論基礎和算法的基本思路.相關的規劃問題,比如多目標規劃,決策論等等.2023/2/32021規劃模型利潤材料工時人力單耗

甲乙丙

x1x2x3限額材料工時工人231321.5325343640利潤(元/件)432生產計劃問題max目標函數約束條件決策變量x1,x2,x32023/2/322單耗

甲乙丙

x1x2x3限額材料工時工人231321.5325343640利潤(元/件)432生產計劃問題規劃模型利潤材料工時人力2023/2/323生產計劃問題maxcTxs.t.Ax≤b

x≥0矩陣形式：利潤材料工時人力線性規劃模型2023/2/324min(max)cTxs.t.Ax≤b,(或Ax

=b)

x≥0(或a≤x≤b)標準形式其中：x∈Rn，A∈Rm×n，b∈Rm，c∈Rn線性規劃2023/2/325Ⅰ2X1+X2=40X1+2X2=50

X1

X2abcd可行點可行域凸多面體v內點邊界點頂點vB線性規劃解的若干概念線性規劃模型maxz=5x1+3x2s.t.2x1+x2≤40

x1+2x2≤50x1，x2≥02023/2/326線性規劃解的圖示線性規劃模型maxz=5x1+3x2s.t.2x1+x2≤40

x1+2x2≤50x1，x2≥02X1+X2=40X1+2X2=50

X1

X2a20x1=10,x2=2025問:什么樣的問題可以使用圖解法?你從圖中得到什么啟示?P=0P=50P=1102023/2/3求解LP的特殊情形Maxz=3x1+x2s.t.-x1+x2≤2----L1

x1-2x2≤2----L23x1+2x2≤14----L3

x1，x2≥0x1x2L2L1L30x1x2L2L1L30x1x2L2L10x1x2L2L1L30z=c②無最優解①無可行解③最優解不唯一2023/2/327線性規劃的基本性質可行域線段組成的凸多邊形目標函數等值線為直線最優解凸多邊形的某個頂點LP的基本性質：可行域存在時，必是凸多面體；可行解對應于可行域中的點；最優解存在時，必在可行域的頂點取得。LP的通常解法是單純形法。超平面組成的凸多面體等值線是超平面凸多面體的某個頂點2維n維2023/2/32829

Matlab中求解線性規劃的命令為:linprog,解決的線性規劃的標準格式為：

mincTx

x∈Rns.t.A·x<=b

Aeq·x=beqVLB≤x≤VUB

其中，A,b,c,x,Aeq,beq,VLB,VUB等均表示矩陣,特別b,c,x,beq,VLB,VUB為列矩陣。

MATLAB軟件求解2023/2/330命令linprog的基本調用格式

如果沒有等式約束,就在相應位置輸入空數組[],不等式約束和上下界也類似.最后的輸入項若沒有,則可省略.

x=linprog(c,A,b,Aeq,beq,VLB,VUB)等式約束決策變量上下界不等式約束目標函數最優解MATLAB軟件求解2023/2/331還可以增加輸出

[x,fval,exitflag,output]=linprog(c,A,b,…）最優值>0：收斂=0:到最大迭代次數時都還未收斂<0：infeasible或方法失敗迭代次數和算法類型MATLAB軟件求解2023/2/332

看一個小例子

程序:c=-[5,3]’;A=[2,1;1,2];b=[40,50]’;L=[0,0];[x,fmin]=linprog(c,A,b,[],[],L);Pmax=-fminx1=x(1),x2=x(2)

輸出結果:

Pmax=110,x1=10,x2=20.

模型:

maxP=5X1+3X2s.t.2X1+X2≤40X1+2X2≤50X1≥0,X2≥0

MATLAB軟件求解2023/2/3

美國一家公司以專門飼養并出售一種實驗用的動物而聞名。這種動物的生長對飼料中的三種營養成分特別敏感，即蛋白質、礦物質和維生素。需要的營養量蛋白質：70克礦物質：3克維生素：9.1毫克

現有五種飼料，公司希望找出滿足動物營養需要使成本達到最低的混合飼料配置。鳥類飼養問題2023/2/333飼料蛋白質(克)礦物質(克)維生素(毫克)1(x1)2(x2)3(x3)4(x4)5(x5)需要量0.302.001.000.601.80700.100.050.020.200.0530.050.100.020.200.089.1每一種飼料每磅所含的營養成分每種飼料每磅的成本飼料12345成本(美元)0.020.070.040.030.052023/2/334建立數學模型決策變量：在混合飼料中，每天所需第j種飼料的磅數xj，j=1，2，3，4，5；②約束條件：蛋白質：0.30x1+2x2+x3+0.6x4+1.8x5≥70

礦物質：0.10x1+0.05x2+0.02x3+0.2x4+0.05x5≥3

維生素：0.05x1+0.1x2+0.02x3+0.2x4+0.08x5≥10自然約束條件：xi≥0③確定目標：混合飼料的成本最低

0.02x1+0.07x2+0.04x3+0.03x4+0.05x5→min2023/2/335完整的線性規劃模型：min0.02x1+0.07x2+0.04x3+0.03x4+0.05x5s.t.0.30x1+2x2+x3+0.6x4+1.8x5≥700.10x1+0.05x2+0.02x3+0.2x4+0.05x5≥30.05x1+0.1x2+0.02x3+0.2x4+0.08x5≥10

xj≥0j=1,2,3,4,5;mincTxs.t.Ax≥b

x≥0歸納：返回2023/2/336linprogmincTxs.t.Ax≤bAeqx≤beqlb≤x≤ubSolvealinearprogrammingproblemwherec,x,b,beq,lb,andubarevectorsandAandAeqarematrices.調用格式:x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Aeq,beq,lb,ub)x=linprog(f,A,b,Aeq,beq,lb,ub,x0)x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)[x,fval]=linprog(...)[x,fval,exitflag]=linprog(...)[x,fval,exitflag,output]=linprog(...)[x,fval,exitflag,output,lambda]=linprog(...)2023/2/337原油生產計劃原油類別買入價(元/桶)買入量(桶/天)辛烷值(%)硫含量(%)A45≤5000120.5B35≤500062.0C25≤500083.0汽油類別賣出價(元/桶)需求量(桶/天)辛烷值(%)硫含量(%)甲703000≥10≤1.0乙602000≥8≤2.0丙501000≥6≤1.01:1加工費:4元/桶能力:<=14000桶/天I:安排生產計劃，在滿足需求的條件下使利潤最大2023/2/338決策變量：目標：甲(3000)乙(2000)丙(1000)A/45X1X2X3B/35X4X5X6C/25X7X8X9約束：總利潤最大

需求限制；原料限制；含量限制；非負限制2023/2/339含量限制非負限制原料限制需求限制約束2023/2/340總盈利：126000元c=[45 45 45 35 35 35 25 25 25];a1=[1 0 0 1 0 0 1 0 0;0 1 0 0 1 0 0 1 0;0 0 1 0 0 1 0 0 1];a2=[1 1 1 0 0 0 0 0 0;0 0 0 1 1 1 0 0 0;0 0 0 0 0 0 1 1 1;-12 0 0 -6 0 0 -8 0 0;0 -12 0 0 -6 0 0 -8 0;0 0 -12 0 0 -6 0 0 -8;0.5 0 0 2 0 0 3 0 0;0 0.5 0 0 2 0 0 3 0;0 0 0.5 0 0 2 0 0 3];b1=[30002000 1000];b2=[50005000 5000 -30000 -16000 -6000 3000 4000 1000];v1=zeros(1,9);[xf]=linprog(c,a2,b2,a1,b1,v1)z=356000-f甲(3000)乙(2000)丙(1000)A/452400800800B/35000C/2560012002002023/2/341II:通過廣告增加銷售(1元廣告費：增加10桶銷售)決策變量：目標：甲(3000+)乙(2000+)丙(1000+)A/45X1X2X3B/35X4X5X6C/25廣告銷售X7X103000+10X10X8X112000+10X11X9X121000+10X12約束：總利潤最大需求限制；原料限制；產量限制；含量限制；非負限制2023/2/342含量限制非負限制產量限制原料限制需求限制約束2023/2/343總盈利：287750元c=[4949493939392929 29 -699 -599 -499];a1=[10 01 0 0 1 0 0-10 00;01 00 1 0 0 1 00-100;00 10 0 1 0 0 10 0-10];a2=[1 1 1 0 0 0 00000 0;0 0 0 1 1 1 00000 0;0 0 0 0 0 0 11100 0;-12 0 0 -6 0 0 -800100 00;0 -12 0 0 -6 0 0-80 0 800;0