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

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

，x2

，…，xn

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

目標(biāo)函數(shù)(線性函數(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)系符號：>,<,=,≥,≤中的任意一個（線性等式或線性不等式）。一、線性規(guī)劃模型4.線性規(guī)劃模型的求解：圖解法單純形法matlab軟件求解。以下介紹幾種常見的線性規(guī)劃問題。

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

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

約束條件：

注：本問題應(yīng)還有一個約束條件：x1、x2取整數(shù).故它是一個整數(shù)線性規(guī)劃問題.這里把它當(dāng)成一個線性規(guī)劃來解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解.若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門的方法求解.10.問題三：投資決策問題某公司擬在某市東、西、南三區(qū)建立門市部，擬議中有7個位置（點(diǎn)）Ai(i=1,2,…,7)可供選擇。規(guī)定東區(qū)在A1、A2、A3三個點(diǎn)中至多選兩個。西區(qū)A4、A5兩個點(diǎn)中至少選一個。南區(qū)A6、A7兩個點(diǎn)中至少選一個。并知道如果選用Ai點(diǎn)，則投資為bi元，估計每年可獲利為ci元，但投資總額不得超過B元。問應(yīng)該選擇哪幾個點(diǎn)可使年利潤為最大？解設(shè)則投資決策問題歸結(jié)為一個線性規(guī)劃模型：引例311.故目標(biāo)函數(shù)為：約束條件為：s.t.這是一個0-1規(guī)劃問題12.幾個問題都是典型的最值問題。其中，“Min或Max”是英文單詞“Minimize或Maximize”的縮寫，含義為“最小化或最大化”；“s.t.”是“subjectto”的縮寫，表示“受約束于…”。線性規(guī)劃是運(yùn)籌學(xué)的一個重要分支，應(yīng)用很廣。線性規(guī)劃問題可以描述為求一組非負(fù)變量，這些非負(fù)變量在一定線性約束的條件下，使一個線性目標(biāo)函數(shù)取得極大（極?。┲档膯栴}。由于式中的目標(biāo)函數(shù)與約束條件均為線性函數(shù)，故被稱為線性規(guī)劃問題。13.線性規(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二、線性規(guī)劃模型的標(biāo)準(zhǔn)形式14.線性規(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)系符號：>,<,=,≥,≤中的任意一個。二、線性規(guī)劃模型的標(biāo)準(zhǔn)形式15.實(shí)際問題中的優(yōu)化模型x是決策變量f(x)是目標(biāo)函數(shù)gi(x)0是約束條件數(shù)學(xué)規(guī)劃線性規(guī)劃(LP)二次規(guī)劃(QP)非線性規(guī)劃(NLP)純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃(MIP)整數(shù)規(guī)劃(IP)0-1整數(shù)規(guī)劃一般整數(shù)規(guī)劃連續(xù)規(guī)劃優(yōu)化模型的分類16.線性規(guī)劃標(biāo)準(zhǔn)型的特點(diǎn)：1、目標(biāo)函數(shù)是Min（最小化）；2、約束條件為等式；3、決策變量為非負(fù)數(shù)；4、右端常數(shù)要求為非負(fù)數(shù)。17.三、用matlab解線性規(guī)劃基本用法用MATLAB優(yōu)化工具箱求解線性規(guī)劃時不要求一定化為標(biāo)準(zhǔn)形，而是要求化為如下形式：

下一頁18.線性規(guī)劃的矩陣表示19.用MATLAB解線性規(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）注意：若沒有不等式：存在，則令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]若沒有等式約束:,則令A(yù)1=[],b1=[]。若v1=zeros(2,1),表示2行1列的零矩陣。[2]其中X0表示初始點(diǎn)21.解編寫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解線性規(guī)劃問題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求解線性規(guī)劃問題解首先轉(zhuǎ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)行后得到原問題的目標(biāo)函數(shù)最大值s=14.571427.解:編寫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ù)分配問題：某車間有甲、乙兩臺車床，可用于加工三種工件.假定這兩臺車床的可用臺時數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費(fèi)用如下表.問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？30.解

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

解答31.s.t.

問題32.編寫如下: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個工件2,在乙機(jī)床上加工400個工件1、500個工件3，可在滿足條件的情況下使總加工費(fèi)最小為13800.34.例6：某廠每日8小時的產(chǎn)量不低于1800件.為了進(jìn)行質(zhì)量控制，計劃聘請兩種不同水平的檢驗(yàn)員.一級檢驗(yàn)員的標(biāo)準(zhǔn)為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗(yàn)員的標(biāo)準(zhǔn)為：速度15件/小時，正確率95%，計時工資3元/小時.檢驗(yàn)員每錯檢一次，工廠要損失2元.為使總檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級、二級檢驗(yàn)員各幾名？解設(shè)需要一級和二級檢驗(yàn)員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗(yàn)員的工資為：因檢驗(yàn)員錯檢而造成的損失為：35.線性規(guī)劃模型：目標(biāo)函數(shù)：

36.編寫如下：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個一級檢驗(yàn)員.

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