数学建模——规划模型

数学建模——规划模型

一、引言如何来分配有限资源，从而达到人们期望目标的优化分配数学模型.它在数学建模中处于中心的地位.这类问题一般可以归结为数学规划模型.规划模型的应用极其广泛，其作用已为越来越多的人所重视.在数模竞赛过程中，规划模型是最常见的一类数学模型.从92-09年全国大学生数模竞赛试题的解题方法统计结果来看，规划模型共出现了18次，占到了近50%,也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解.

(一)规划模型的数学描述u f ( x)和

规划模型的一般意义

将一个优化问题用数学式子来描述，即求函数x ( x1, x2, x3,..., xn )

在约束条件 hi ( x ) 0, i 1,2,..., m.

g i ( x ) 0( g i ( x ) 0), i 1,2,..., p.决策变量目标函数可行域

下的最大值或最小值，其中

x f ( x) x

min(or max)u f ( x ) x s. t. hi ( x ) 0, i 1,2,..., m.g i ( x ) 0( g i ( x ) 0), i 1,2,..., p.

s. t .

subject to

“受约束于”之意

(二)规划模型的分类1.根据是否存在约束条件有约束问题和无约束问题。 2.根据决策变量的性质静态问题和动态问题。 3.根据目标函数和约束条件表达式的性质

线性规划，非线性规划，二次规划，多目标规划等。

(1)非线性规划(NLP)目标函数和约束条件中，至少有一个非线性函数。

min u f ( x ) x

s. t. hi ( x ) 0, i 1,2,..., m.g i ( x ) 0( g i ( x ) 0), i 1,2,..., p.

(2)线性规划(LP)目标函数和所有的约束条件都是决策变量的线性函数。

min u n

c xi 1 i

n

i

a ik x k bi, i 1, 2,..., n. s.t . k 1 x 0, i 1, 2,..., n. i

(3)二次规划问题目标函数为二次函数，约束条件为线性约束

1 n min u f ( x ) ci xi bij xi x j 2 i, j 1 i 1 n a ij x j bi, i 1, 2,..., n. s.t . j 1 x 0 .i 1, 2,..., n. i

n

4.根据决策变量的允许值整数规划(0-1规划)和实数规划。

5.根据变量具有确定值还是随机值确定规划和随机规划。

(三)建立规划模型的一般步骤 1.确定决策变量和目标变量； 2.确定目标函数的表达式； 3.寻找约束条件。

二、规划模型应用举例例1任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900,三种工件的数量分别为400、600和500,且已知用两种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？车床类型甲乙单位工件所需加工

台时数工件 1 0.4 0.5工件 2 1.1 1.2工件 3 1.0 1.3单位工件的加工费用工件 1 13 11工件 2 9 12工件 3 10 8可用台时数 800 900

解

设在甲车床上加工工件1、2、3的数量分别为x1、x2、 x3,在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：

min z 13 x1 9 x 2 10 x3 11x 4 12 x5 8 x6 x1 x4 400 x x 600 2 5 x3 x6 500 s.t. 0.4 x1 1.1x2 x3 800 0.5 x4 1.2 x5 1.3 x6 900 xi 0, i 1,2, ,6解答

Lingo求解

model: min=13*x1+9*x2+10*x3+1 1*x4+12*x5+8*x6; x1+x4=400; x2+x5=600; x3+x6=500; 0.4*x1+1.1*x2+x3<800; 0.5*x1+1.2*x2+1.3*x3<900; end

Matlab求解改写为： S.t.

min z 13 9 10 11 12 8 X0 0 800 0.4 1.1 1 0 X 0 0 0 0 . 5 1 . 2 1 . 3 900 x1 x2 x 3,X 0 x4 x 5 x 6

400 1 0 0 1 0 0 0 1 0 0 1 0 X 600 500 0 0 1 0 0 1

编写M文件xxgh3.m如下: f=[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]; Aeq=[1 0 0 1 0 0 010010 0 0 1 0 0 1]; beq=[400 600 500]; vlb= zeros(6,1); vub=[];[x,fval]= linprog(f,A,b,Aeq,beq,vlb,vub)

结果:x= 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000 fval=1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、 500个工件3,可在满足条件的情况下使总加工费最小为13800。