線(xiàn)性規(guī)劃模型目標(biāo)函數(shù)

線(xiàn)性規(guī)劃1.線(xiàn)性規(guī)劃內(nèi)容一、線(xiàn)性規(guī)劃模型二、線(xiàn)性規(guī)劃模型的標(biāo)準(zhǔn)形式三、用matlab解線(xiàn)性規(guī)劃2.線(xiàn)性規(guī)劃所解決的問(wèn)題具有以下共同的特征：2.存在一定的限制條件（即約束條件），這些限制條件是關(guān)于未知數(shù)的一組線(xiàn)性等式或線(xiàn)性不等式來(lái)表示。1.每一個(gè)問(wèn)題都用一組未知數(shù)（x1

，x2

，…，xn

）表示某一方案；這些未知數(shù)的一組定值就代表一個(gè)具體方案。由于實(shí)際問(wèn)題的要求，通常這些未知數(shù)取值是非負(fù)的。3.有一個(gè)目標(biāo)要求，稱(chēng)為目標(biāo)函數(shù)。目標(biāo)函數(shù)可表示為一組未知數(shù)的線(xiàn)性函數(shù)。根據(jù)問(wèn)題的需要，需求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。一、線(xiàn)性規(guī)劃模型3.一般的線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型：

目標(biāo)函數(shù)(線(xiàn)性函數(shù)）：

Min(max)z=c1x1

+c2x2

+…+cnxn

約束條件(s.t.)：

a11x1+a12x2+…+a1nxn(≥)b1a21x1+a22x2+…+a2nxn(≥)b2

...am1x1+am2x2

+…+amnxn

(≥)bm

x1

，x2

，…，xn

≥0

式中()可以是關(guān)系符號(hào)：>,<,=,≥,≤中的任意一個(gè)（線(xiàn)性等式或線(xiàn)性不等式）。一、線(xiàn)性規(guī)劃模型4.線(xiàn)性規(guī)劃模型的求解：圖解法單純形法matlab軟件求解。以下介紹幾種常見(jiàn)的線(xiàn)性規(guī)劃問(wèn)題。

5.問(wèn)題一：任務(wù)分配問(wèn)題：某車(chē)間有甲、乙兩臺(tái)車(chē)床，可用于加工三種工件.假定這兩臺(tái)車(chē)床的可用臺(tái)時(shí)數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車(chē)床加工單位數(shù)量不同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表.問(wèn)怎樣分配車(chē)床的加工任務(wù)，才能既滿(mǎn)足加工工件的要求，又使加工費(fèi)用最低？引例16.解

設(shè)在甲車(chē)床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車(chē)床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,可建立以下線(xiàn)性規(guī)劃模型：目標(biāo)函數(shù)：約束條件：7.問(wèn)題二：某廠(chǎng)每日8小時(shí)的產(chǎn)量不低于1800件.為了進(jìn)行質(zhì)量控制，計(jì)劃聘請(qǐng)兩種不同水平的檢驗(yàn)員.一級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度25件/小時(shí)，正確率98%，計(jì)時(shí)工資4元/小時(shí)；二級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度15件/小時(shí)，正確率95%，計(jì)時(shí)工資3元/小時(shí).檢驗(yàn)員每錯(cuò)檢一次，工廠(chǎng)要損失2元.為使總檢驗(yàn)費(fèi)用最省，該工廠(chǎng)應(yīng)聘一級(jí)、二級(jí)檢驗(yàn)員各幾名？解設(shè)需要一級(jí)和二級(jí)檢驗(yàn)員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗(yàn)員的工資為：因檢驗(yàn)員錯(cuò)檢而造成的損失為：引例28.故目標(biāo)函數(shù)為：約束條件為：9.線(xiàn)性規(guī)劃模型目標(biāo)函數(shù)：

約束條件：

注：本問(wèn)題應(yīng)還有一個(gè)約束條件：x1、x2取整數(shù).故它是一個(gè)整數(shù)線(xiàn)性規(guī)劃問(wèn)題.這里把它當(dāng)成一個(gè)線(xiàn)性規(guī)劃來(lái)解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解.若用線(xiàn)性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專(zhuān)門(mén)的方法求解.10.問(wèn)題三：投資決策問(wèn)題某公司擬在某市東、西、南三區(qū)建立門(mén)市部，擬議中有7個(gè)位置（點(diǎn)）Ai(i=1,2,…,7)可供選擇。規(guī)定東區(qū)在A1、A2、A3三個(gè)點(diǎn)中至多選兩個(gè)。西區(qū)A4、A5兩個(gè)點(diǎn)中至少選一個(gè)。南區(qū)A6、A7兩個(gè)點(diǎn)中至少選一個(gè)。并知道如果選用Ai點(diǎn)，則投資為bi元，估計(jì)每年可獲利為ci元，但投資總額不得超過(guò)B元。問(wèn)應(yīng)該選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大？解設(shè)則投資決策問(wèn)題歸結(jié)為一個(gè)線(xiàn)性規(guī)劃模型：引例311.故目標(biāo)函數(shù)為：約束條件為：s.t.這是一個(gè)0-1規(guī)劃問(wèn)題12.幾個(gè)問(wèn)題都是典型的最值問(wèn)題。其中，“Min或Max”是英文單詞“Minimize或Maximize”的縮寫(xiě)，含義為“最小化或最大化”；“s.t.”是“subjectto”的縮寫(xiě)，表示“受約束于…”。線(xiàn)性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，應(yīng)用很廣。線(xiàn)性規(guī)劃問(wèn)題可以描述為求一組非負(fù)變量，這些非負(fù)變量在一定線(xiàn)性約束的條件下，使一個(gè)線(xiàn)性目標(biāo)函數(shù)取得極大（極小）值的問(wèn)題。由于式中的目標(biāo)函數(shù)與約束條件均為線(xiàn)性函數(shù)，故被稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題。13.線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)形式

目標(biāo)函數(shù)：

Minz=c1x1

+c2x2

+…+cnxn

約束條件：

a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2

...am1x1+am2x2

+…+amnxn=bm

x1，x2，…，xn≥0二、線(xiàn)性規(guī)劃模型的標(biāo)準(zhǔn)形式14.線(xiàn)性規(guī)劃的一般形式

目標(biāo)函數(shù)：

Min(max)z=c1x1

+c2x2

+…+cnxn

約束條件：

a11x1+a12x2+…+a1nxn(≥)b1a21x1+a22x2+…+a2nxn(≥)

b2

...am1x1+am2x2

+…+amnxn

(≥)

bm

x1，x2，…，xn≥0

式中()可以是關(guān)系符號(hào)：>,<,=,≥,≤中的任意一個(gè)。二、線(xiàn)性規(guī)劃模型的標(biāo)準(zhǔn)形式15.實(shí)際問(wèn)題中的優(yōu)化模型x是決策變量f(x)是目標(biāo)函數(shù)gi(x)0是約束條件數(shù)學(xué)規(guī)劃線(xiàn)性規(guī)劃(LP)二次規(guī)劃(QP)非線(xiàn)性規(guī)劃(NLP)純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃(MIP)整數(shù)規(guī)劃(IP)0-1整數(shù)規(guī)劃一般整數(shù)規(guī)劃連續(xù)規(guī)劃優(yōu)化模型的分類(lèi)16.線(xiàn)性規(guī)劃標(biāo)準(zhǔn)型的特點(diǎn)：1、目標(biāo)函數(shù)是Min（最小化）；2、約束條件為等式；3、決策變量為非負(fù)數(shù)；4、右端常數(shù)要求為非負(fù)數(shù)。17.三、用matlab解線(xiàn)性規(guī)劃基本用法用MATLAB優(yōu)化工具箱求解線(xiàn)性規(guī)劃時(shí)不要求一定化為標(biāo)準(zhǔn)形，而是要求化為如下形式：

下一頁(yè)18.線(xiàn)性規(guī)劃的矩陣表示19.用MATLAB解線(xiàn)性規(guī)劃minz=cX

1.模型：命令：x=linprog（c,A,b）

[x,fval]=linprog

(…)返回最優(yōu)解ｘ及ｘ處的目標(biāo)函數(shù)值fval2.模型：minz=cX

命令：x=linprog（c，A，b，A1,b1）注意：若沒(méi)有不等式：存在，則令A(yù)=[]，b=[].20.3.模型：minz=cX

V1≤X≤V2命令：[1]x=linprog（c，A，b，A1,b1,V1，V2）

[2]

x=linprog（c，A，b，A1,b1,V1，V2,X0）

注意：[1]若沒(méi)有等式約束:,則令A(yù)1=[],b1=[]。若v1=zeros(2,1),表示2行1列的零矩陣。[2]其中X0表示初始點(diǎn)21.解編寫(xiě)M文件xxgh1.m如下：c=[-0.4,-0.28,-0.32,-0.72,-0.64,-0.6];

A=[0.01,0.01,0.01,0.03,0.03,0.03;0.02,0,0,0.05,0,0;0,0.02,0,0,0.05,0;0,0,0.03,0,0,0.08];

b=[850;700;100;900];

A1=[];b1=[];

v1=[0;0;0;0;0;0];v2=[];[x,fval]=linprog(c,A,b,A1,b1,v1,v2)22.Optimizationterminatedsuccessfully.x=1.0e+004*3.50000.50003.00000.00000.00000.0000fval=-2.5000e+00423.例2用MATLAB解線(xiàn)性規(guī)劃問(wèn)題24.解

Matlab程序如下:c=[-2,-1,1];A=[1,4,-1;2,-2,1];b=[4;12];A1=[1,1,2];b1=6;v1=[0,0,-inf];v2=[inf,inf,5];[x,z]=linprog(c,A,b,A1,b1,v1,v2)運(yùn)行后得到輸出Optimizationterminatedsuccessfully.x=4.66670.00000.6667z=-8.666725.例3

用MATLAB求解線(xiàn)性規(guī)劃問(wèn)題解首先轉(zhuǎn)化為求最小值問(wèn)題26.Matlab程序如下c=[-2,-3,5];A=[-2,5,-1];b=-10;A1=[1,1,1];b2=[7];v1=[0,0,0];[x,z]=linprog(c,A,b,A1,b1,v1)運(yùn)行后得到輸出x=6.42860.57140.0000z=-14.5714鍵入s=-z運(yùn)行后得到原問(wèn)題的目標(biāo)函數(shù)最大值s=14.571427.解:編寫(xiě)M文件xxgh2.m如下：

c=[6,3,4];A=[0,1,0];b=[50];Aeq=[1,1,1];beq=[120];vlb=[30,0,20];vub=[];

[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)28.Optimizationterminatedsuccessfully.x=30.000050.000040.0000fval=490.000029.例5：任務(wù)分配問(wèn)題：某車(chē)間有甲、乙兩臺(tái)車(chē)床，可用于加工三種工件.假定這兩臺(tái)車(chē)床的可用臺(tái)時(shí)數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車(chē)床加工單位數(shù)量不同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表.問(wèn)怎樣分配車(chē)床的加工任務(wù)，才能既滿(mǎn)足加工工件的要求，又使加工費(fèi)用最低？30.解

設(shè)在甲車(chē)床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車(chē)床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,可建立以下線(xiàn)性規(guī)劃模型：目標(biāo)函數(shù)：約束條件：

解答31.s.t.

問(wèn)題32.編寫(xiě)如下:c=[13,9,10,11,12,8];A=[0.4,1.1,1,0,0,0;0,0,0,0.5,1.2,1.3];b=[800;900];A1=[1,0,0,1,0,0;0,1,0,0,1,0;0,0,1,0,0,1];b1=[400,600,500];vl=zeros(6,1);v2=[];[x,fval]=linprog(c,A,b,A1,b1,v1,v2)33.結(jié)果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲機(jī)床上加工600個(gè)工件2,在乙機(jī)床上加工400個(gè)工件1、500個(gè)工件3，可在滿(mǎn)足條件的情況下使總加工費(fèi)最小為13800.34.例6：某廠(chǎng)每日8小時(shí)的產(chǎn)量不低于1800件.為了進(jìn)行質(zhì)量控制，計(jì)劃聘請(qǐng)兩種不同水平的檢驗(yàn)員.一級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度25件/小時(shí)，正確率98%，計(jì)時(shí)工資4元/小時(shí)；二級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度15件/小時(shí)，正確率95%，計(jì)時(shí)工資3元/小時(shí).檢驗(yàn)員每錯(cuò)檢一次，工廠(chǎng)要損失2元.為使總檢驗(yàn)費(fèi)用最省，該工廠(chǎng)應(yīng)聘一級(jí)、二級(jí)檢驗(yàn)員各幾名？解設(shè)需要一級(jí)和二級(jí)檢驗(yàn)員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗(yàn)員的工資為：因檢驗(yàn)員錯(cuò)檢而造成的損失為：35.線(xiàn)性規(guī)劃模型：目標(biāo)函數(shù)：

36.編寫(xiě)如下：c=[40;36];A=[-5-3];b=[-45];Aeq=[];beq=[];vlb=zeros(2,1);vub=[9;15];%調(diào)用linprog函數(shù)：[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)37.結(jié)果為：x=9.00000.0000fval=360即只需聘用9個(gè)一級(jí)檢驗(yàn)員.

注：本問(wèn)題應(yīng)還有一個(gè)約束條件：x1、x2取整數(shù).故它是一個(gè)整數(shù)線(xiàn)性規(guī)劃問(wèn)題.這里把它當(dāng)成一個(gè)線(xiàn)性規(guī)劃來(lái)解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解.若用線(xiàn)性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專(zhuān)門(mén)的方法求解.返回38.習(xí)題1.建立下列線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型（1）某工廠(chǎng)生產(chǎn)A、B、C三種產(chǎn)品，三種產(chǎn)品對(duì)于材料費(fèi)用、勞動(dòng)力和電力的單位消耗系數(shù)，資源限量和單位產(chǎn)品價(jià)格如表1.1