數(shù)學(xué)實(shí)驗(yàn)第五次講稿

數(shù)學(xué)實(shí)驗(yàn)第五講

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

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

“改進(jìn)的出貨流程”每年為YellowFreight公司節(jié)約一千七百多萬(wàn)美元.“改進(jìn)的卡車分派”為

Reynolds公司每年節(jié)約七百萬(wàn)美元.最優(yōu)全局供應(yīng)鏈為數(shù)字設(shè)備行業(yè)節(jié)約超過(guò)三億美元.重建的

NorthAmericaOperations,ProctorandGamble減少20%的工廠,每年節(jié)約兩億美元.大阪的Hanshin高速的最優(yōu)安排每年節(jié)約一千七百萬(wàn)人小時(shí).2023/2/35

為說(shuō)明最優(yōu)化的價(jià)值,建立了專門的網(wǎng)站,列舉了哪些公司的什么問(wèn)題,運(yùn)用最優(yōu)化方法節(jié)約和增加了多少金額.

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

美國(guó)一家公司以專門飼養(yǎng)并出售一種實(shí)驗(yàn)用的動(dòng)物而聞名。這種動(dòng)物的生長(zhǎng)對(duì)飼料中的三種營(yíng)養(yǎng)成分特別敏感，即蛋白質(zhì)、礦物質(zhì)和維生素。需要的營(yíng)養(yǎng)量蛋白質(zhì)：70克礦物質(zhì)：3克維生素：9.1毫克

現(xiàn)有五種飼料，公司希望找出滿足動(dòng)物營(yíng)養(yǎng)需要使成本達(dá)到最低的混合飼料配置。2023/2/39飼料蛋白質(zhì)(克)礦物質(zhì)(克)維生素(毫克)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每一種飼料每磅所含的營(yíng)養(yǎng)成分每種飼料每磅的成本飼料12345成本(美元)0.020.070.040.030.052023/2/310引例2:供應(yīng)與選址

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

在我們的生活中,始終有這樣的問(wèn)題:為了一定的目的做一些事情,我們可能要考慮有哪些重要的因素,這些因素和要完成的目標(biāo)之間有什么樣的關(guān)系.也就是說(shuō),我們?cè)谧鲆粋€(gè)決定時(shí),會(huì)注意下面的三個(gè)要點(diǎn):目的是什么?有哪些重要的因素?這些因素和你的目標(biāo)之間有什么樣的關(guān)系?2023/2/312二，優(yōu)化問(wèn)題的表述目標(biāo)函數(shù)對(duì)應(yīng)決策者而言,對(duì)其有利的程度必須定量的測(cè)度,在商業(yè)應(yīng)用中，有效性的測(cè)度經(jīng)常是利潤(rùn)或者成本,但對(duì)于政府，更經(jīng)常的使用投入產(chǎn)出率來(lái)測(cè)度.

表示有效性測(cè)度的經(jīng)常稱為目標(biāo)函數(shù).目標(biāo)函數(shù)要表出測(cè)度的有效性,必須說(shuō)明測(cè)度和導(dǎo)致測(cè)度改變的變量之間的關(guān)系.系統(tǒng)變量分為決策變量和參數(shù).決策變量是指能由決策者直接控制的變量.而參數(shù)是指不能由決策者決定的量.實(shí)際上，數(shù)學(xué)模型很少有能表達(dá)變量和有效性測(cè)度之間的精確關(guān)系的.實(shí)際上，運(yùn)籌學(xué)分析者的任務(wù)就是找出對(duì)測(cè)度有最重要影響的變量然后找出這些變量和測(cè)度之間的數(shù)學(xué)關(guān)系.這個(gè)數(shù)學(xué)關(guān)系也就是目標(biāo)函數(shù).2023/2/313二，優(yōu)化問(wèn)題的表述決策變量和參數(shù)我們稱對(duì)應(yīng)決策者可控的量稱為決策變量,決策變量的取值確定了系統(tǒng)的最終性能,也是決策者采用決策的依據(jù).在系統(tǒng)中還有一些量,它不能由決策者所控制,而是由系統(tǒng)所處的環(huán)境所決定,我們稱之為參數(shù).2023/2/314二，優(yōu)化問(wèn)題的表述約束條件

約束條件就是決策變量和參數(shù)之間的關(guān)系.約束集界定決策變量可以取某些值而不能取其他的值.比如對(duì)應(yīng)生產(chǎn)問(wèn)題,任何活動(dòng)中,時(shí)間和物品不能為負(fù)數(shù).當(dāng)然,也有一些優(yōu)化問(wèn)題不帶約束條件,我們稱之為無(wú)約束優(yōu)化問(wèn)題.而在實(shí)際問(wèn)題中,決策變量帶有約束是普遍的.2023/2/315三,優(yōu)化問(wèn)題的分類優(yōu)化問(wèn)題的分類可以從幾個(gè)方面進(jìn)行:1,從變量取值的連續(xù)和離散可以分成:連續(xù)優(yōu)化,離散優(yōu)化和混合優(yōu)化2,從問(wèn)題的線性非線性可以分為:線性規(guī)劃和非線性規(guī)劃3,從變量是確定性和隨機(jī)性可以分為:隨機(jī)規(guī)劃和確定性問(wèn)題.2023/2/316JohnVonNeumann

約翰·馮·諾依曼(1903－1957),美藉匈牙利人.20世紀(jì)最杰出的數(shù)學(xué)家之一,被譽(yù)為”計(jì)算機(jī)之父”,”博弈論之父”.被認(rèn)為是數(shù)學(xué)規(guī)劃的三大創(chuàng)始人之一.以下的三個(gè)人物和線性規(guī)劃的出現(xiàn)有重要的關(guān)系.2023/2/317GeorgeB.Dantzig

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

甲乙丙

x1x2x3限額材料工時(shí)工人231321.5325343640利潤(rùn)(元/件)432生產(chǎn)計(jì)劃問(wèn)題max目標(biāo)函數(shù)約束條件決策變量x1,x2,x32023/2/322單耗

甲乙丙

x1x2x3限額材料工時(shí)工人231321.5325343640利潤(rùn)(元/件)432生產(chǎn)計(jì)劃問(wèn)題規(guī)劃模型利潤(rùn)材料工時(shí)人力2023/2/323生產(chǎn)計(jì)劃問(wèn)題maxcTxs.t.Ax≤b

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

=b)

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

X1

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

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

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

X1

X2a20x1=10,x2=2025問(wèn):什么樣的問(wèn)題可以使用圖解法?你從圖中得到什么啟示?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②無(wú)最優(yōu)解①無(wú)可行解③最優(yōu)解不唯一2023/2/327線性規(guī)劃的基本性質(zhì)可行域線段組成的凸多邊形目標(biāo)函數(shù)等值線為直線最優(yōu)解凸多邊形的某個(gè)頂點(diǎn)LP的基本性質(zhì)：可行域存在時(shí)，必是凸多面體；可行解對(duì)應(yīng)于可行域中的點(diǎn)；最優(yōu)解存在時(shí)，必在可行域的頂點(diǎn)取得。LP的通常解法是單純形法。超平面組成的凸多面體等值線是超平面凸多面體的某個(gè)頂點(diǎn)2維n維2023/2/32829

Matlab中求解線性規(guī)劃的命令為:linprog,解決的線性規(guī)劃的標(biāo)準(zhǔn)格式為：

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的基本調(diào)用格式

如果沒(méi)有等式約束,就在相應(yīng)位置輸入空數(shù)組[],不等式約束和上下界也類似.最后的輸入項(xiàng)若沒(méi)有,則可省略.

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

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

看一個(gè)小例子

程序: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)

輸出結(jié)果:

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

模型:

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

MATLAB軟件求解2023/2/3

美國(guó)一家公司以專門飼養(yǎng)并出售一種實(shí)驗(yàn)用的動(dòng)物而聞名。這種動(dòng)物的生長(zhǎng)對(duì)飼料中的三種營(yíng)養(yǎng)成分特別敏感，即蛋白質(zhì)、礦物質(zhì)和維生素。需要的營(yíng)養(yǎng)量蛋白質(zhì)：70克礦物質(zhì)：3克維生素：9.1毫克

現(xiàn)有五種飼料，公司希望找出滿足動(dòng)物營(yíng)養(yǎng)需要使成本達(dá)到最低的混合飼料配置。鳥類飼養(yǎng)問(wèn)題2023/2/333飼料蛋白質(zhì)(克)礦物質(zhì)(克)維生素(毫克)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每一種飼料每磅所含的營(yíng)養(yǎng)成分每種飼料每磅的成本飼料12345成本(美元)0.020.070.040.030.052023/2/334建立數(shù)學(xué)模型決策變量：在混合飼料中，每天所需第j種飼料的磅數(shù)xj，j=1，2，3，4，5；②約束條件：蛋白質(zhì)：0.30x1+2x2+x3+0.6x4+1.8x5≥70

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

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

0.02x1+0.07x2+0.04x3+0.03x4+0.05x5→min2023/2/335完整的線性規(guī)劃模型：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.調(diào)用格式: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原油生產(chǎn)計(jì)劃原油類別買入價(jià)(元/桶)買入量(桶/天)辛烷值(%)硫含量(%)A45≤5000120.5B35≤500062.0C25≤500083.0汽油類別賣出價(jià)(元/桶)需求量(桶/天)辛烷值(%)硫含量(%)甲703000≥10≤1.0乙602000≥8≤2.0丙501000≥6≤1.01:1加工費(fèi):4元/桶能力:<=14000桶/天I:安排生產(chǎn)計(jì)劃，在滿足需求的條件下使利潤(rùn)最大2023/2/338決策變量：目標(biāo)：甲(3000)乙(2000)丙(1000)A/45X1X2X3B/35X4X5X6C/25X7X8X9約束：總利潤(rùn)最大

需求限制；原料限制；含量限制；非負(fù)限制2023/2/339含量限制非負(fù)限制原料限制需求限制約束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:通過(guò)廣告增加銷售(1元廣告費(fèi)：增加10桶銷售)決策變量：目標(biāo)：甲(3000+)乙(2000+)丙(1000+)A/45X1X2X3B/35X4X5X6C/25廣告銷售X7X103000+10X10X8X112000+10X11X9X121000+10X12約束：總利潤(rùn)最大需求限制；原料限制；產(chǎn)量限制；含量限制；非負(fù)限制2023/2/342含量限制非負(fù)限制產(chǎn)量限制原料限制需求限制約束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