數(shù)模往屆2013國賽線性

線性規(guī)劃2021/7/3011、了解線性規(guī)劃的基本內(nèi)容。2、掌握用數(shù)學(xué)軟件包求解線性規(guī)劃問題。1、兩個引例。*2、線性規(guī)劃的基本算法。3、用數(shù)學(xué)軟件包求解線性規(guī)劃問題。4、作業(yè)。2021/7/302問題一(3)：2021/7/303任務(wù)分配問題：某車間有甲、乙兩臺機床，可用于加工三種工件。假定這兩臺車床的可用臺時數(shù)分別為

800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表。問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費用最低？車床類型單位工件所需加工臺時數(shù)單位工件的加工費用可用臺時數(shù)工件1工件2工件3工件1工件2工件3甲0.41.11.013910800乙0.51.21.311128900兩個引例解

設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，2021/7/3042

51

2

3在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6?？山⒁韵戮€性規(guī)劃模型：minz=13x1

+9x2

+10x3

+11x4

+12x5

+8x6x1

+

x4

=

400x

+

x

=

600x

+

x

=

500s.t.

3

60.4x

+1.1x

+

x

￡

8000.5x4

+1.2x5

+1.3x6

￡

900

ix

?

0,i

=1,

2,,6問題二(4)：2021/7/305某廠每日8小時的產(chǎn)量不低于1800件。為了進行質(zhì)量控制，計劃聘請兩種不同水平的檢驗員。一級檢驗員的標(biāo)準(zhǔn)為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標(biāo)準(zhǔn)為：速度15小時/件，正確率95%，計時工資3元/小時。檢驗員每錯檢一次，工廠要損失2元。為使總檢驗費用最省，該工廠應(yīng)聘一級、二級檢驗員各幾名？解

設(shè)需要一級和二級檢驗員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗員的工資為：8·

4

·

x1

+

8·3·

x2

=

32x1

+

24x2因檢驗員錯檢而造成的損失為：(8·

25·

2%·

x1

+

8·15·5%·

x2

)·

2

=

8x1

+12x2故目標(biāo)函數(shù)為：2021/7/306min

z

=

(32x1

+

24x

2

)

+

(8x1

+12x2

)

=

40x1

+

36x2約束條件為：18·

25·

x1

+8·15·

x2

?18008·

25·

x

￡18008·15·

x2

￡1800x1

?

0,

x2

?

0線性規(guī)劃模型：2021/7/307min

z

=

40x1

+

36x212s.t.5x1

+

3x2

?

45x

￡

9x

￡15x1

?

0,

x2

?

01.線性規(guī)劃的標(biāo)準(zhǔn)形式：2.

線性規(guī)劃的基本算法——單純形法線性規(guī)劃的基本算法——單純形法2021/7/308min

f

=

cxs.t.

Ax

=

bx

?

0用MATLAB優(yōu)化工具箱解線性規(guī)劃2021/7/3091、模型：min

z=cXs.t.

AX

￡

b命令：x=linprog（c，A，b）2,模型：min

z=cXs.t.

AX

￡

bAeq

X

=

beq命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式：AX

￡

b

存在，則令A(yù)=[

]，b=[

].3、模型：min

z=cX2021/7/3010s.t.AX

￡

bAeq

X

=

beqVLB≤X≤VUB命令：[1]

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

x=linprog（c，A，b，Aeq,beq,

VLB，VUB,

X0）,則令A(yù)eq=[],注意：[1]

若沒有等式約束:

Aeq

X

=

beqbeq=[

].[2]其中X0表示初始點

4、命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標(biāo)函數(shù)值fval.解編寫M文件xxgh1.m如下：c=[-0.4

-0.28-0.32

-0.72-0.64

-0.6];2021/7/3011A=[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

00.03

0

0

0.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)

To

Matlab

(xxgh1)z

=

0.4x1

+

0.28x2

+

0.32x3

+

0.72x4

+

0.64x5

+

0.6x6s.t.0.01x1

+

0.01x2

+

0.01x3

+

0.03x4

+

0.03x5

+

0.03x6

￡

8500.02x1

+

0.05x4

￡

7000.02x2

+

0.05x5

￡100

0.03x3

+

0.08x6

￡

900x

j

?

0

j

=1,

2,6例1

max例

2

min

z

=

6x1

+

3x2

+

4x3s.t.

x1

+

x2

+

x3

=1201x

?

3020

￡

x

￡

503x

?

20解:

編寫M文件xxgh2.m如下：c=[6

3

4];A=[0

1

0];b=[50];Aeq=[1

1

1];beq=[120];vlb=[30,0,20];vub=[];2021/7/3012[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)To Matlab

(xxgh2)23x

14

)

x

m

i

n

z

=

(

6

x

3

2x

1

3

0

x

0

￡

2

0

x

3

15

0xs

.t

.

1

2

0

1

1 1

1

0

0

x

2

￡

x

3

0.42021/7/3013S.t.

0min

z

=

(13

9

10

11

12

8

X1.1

1

0

0

0

X

￡

800

0

0

0.5

1.2

1.3

900

1

0

0

1

0 0

400

1

0

0

10

1

0

0

00

X

=

600

01

500

x1

x

2

x

，

X

=

3

?

0

x

4

x

5

x

6

改寫為：例3

問題一的解答編寫M文件xxgh3.m如下:2021/7/3014f

=

[13

9

10

11

12

8];A

= [0.4

1.1

1

0

0

00

0

0

0.5

1.2

1.3];b

=

[800;

900];Aeq=[1

0

0

1

0

00

1

0

0

1

00

0

1

0

0

1];beq=[400

600

500];vlb

=

zeros(6,1);vub=[];[x,fval]

=

linprog(f,A,b,Aeq,beq,vlb,vub)To Matlab

(xxgh3)結(jié)果:x

=0.0000600.00000.0000400.00000.0000500.0000fval

=1.3800e+004即在甲機床上加工600個工件2,在乙機床上加工400個工件1、500個工件3，可在滿足條件的情況下使總加工費最小為13800。2021/7/3015例4

問題二的解答2021/7/3016問題36

x1

min

z

=

(40)

x

2

s.t.(-5

-3

x1

￡

(-45))

x

2

改寫為：編寫M文件xxgh4.m如下：2021/7/3017c

=

[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)To Matlab

(xxgh4)結(jié)果為：2021/7/3018x

=9.00000.0000fval

=360即只需聘用9個一級檢驗員。注：本問題應(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)用專門的方