1-1第一讲规划模型

第一讲规划模型

本讲介绍的规划模型是一类有着广泛应用的确定性的系统优化模型。这类规划问题，模型规范，建模直接，激发想象；模型求解方法典型，实用面宽广。掌握这类规划问题的数学建模、是建模者必须具备的基本建模素养。

规划模型的应用极其广泛，其作用已为越来越多的人所重视。随着计算机的逐渐普及，它越来越急速地渗透于工农业生产、商业活动、军事行为、核科学研究的各个方面，为社会节省的财富、创造的价值无法估量。

在数模竞赛过程中，规划模型是最常见的一类数学模型。从历年全国大学生数模竞赛试题的解题方法统计结果来看，规划模型共出现了近20次，占到了近50%，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解。

下面首先讨论静态系统的优化问题，介绍线性规划、整数规划、目标规划和非线性规划；然后讨论动态系统的多阶段优化问题。

线性规划问题及其数学模型

线性规划模型

线性规划是运筹学的重要分支之一。一般认为，运筹学的主要分支有规划论(包括线性规划、非线性规划、动态规划等)、排队论、对策论(亦称博奕论)与决策分析、图论、存贮论、模型论等分支．线性规划只是运筹学中研究较早，理论比较完整、应用最广的一个分支。

1．线性规划问题

在生产管理和经营活动中，经常提出一类问题，即如何合理地利用有限的人力、物力等资源、以便得到最好的经济效益。先来看两个实例。

问题1拟定生产计划问题

问题提出某工厂生产甲、乙两种产品．这两种产品都需要在A，B，C三种不同设备上加工，每吨甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润值以及这三种加工设备在计划期内能提供的有限台时数均列于下表中．如何安排生产计划，即甲、乙两种产品各生产多少吨，可使该厂所获利润最大?

设备 每吨产品的加工台时

有限台时数

甲 乙 A 3 4 36

B 5 4 40

C 9 8 76

利润（千元/吨） 32 30 求最大利润

模型建立设计划期内甲、乙两种产品的产量分别为x1吨、x2吨(x1，x2称为决策变量)，该厂的目标是在不超过二种设备总有限台时数的条件下，确定产量x1及x2，以获得最大利润，用Z表示利润．则有目标函数：

Max Z = 32*x1 + 30*x2

由于设备A，B，C在计划期内的有效台时数分别为36．40，76，可以得出限制产量的条件，即约束条件；

3*x1+4*x2<=36 (设备A对产量的限制)

5*x1+4*x2<=40 (设备B对产量的限制)，

9*x1+8*x2<=76 (设备C对产量的限制)，

x1，x2≥0 (产量不能为负值)．

问题2 运输问题

问题提出 两个煤厂A1和A2每月进煤数量分别为60t和100t，联合供应三个居民区(Bl，B2，B3)。三个居民区每月对煤的需求量依次为50t、70t、40t，煤厂Al离居民区BI，B2，B3的距离分别为10 km、5km、6km，煤厂A2离居区民区BI，B2，B3的距离分别为4km，8km,12km．问如何分配供煤量使得运输量(t·km)达到最小?

模型准备：将上述条件用表格形式表示有

B1 B2 B3 供给

A1 10 5 6 60

A2 4 8 12 100

需求 50 70 40

模型建立 分配供煤量优劣的指标为运输量，设为Z，用xij表示Ai(I=1,2)煤厂提供给Bj(j＝1，2，3)居民区的煤量，则该问题的数学模型为

目标函数； minZ＝lOx11＋5x12＋6x13＋4x21＋8x22＋12x23

约束条件：)()3,2,1;2,1(,0)(40)(70)(50)(100)(6032313222121211122322211131211运煤量不能为负的需求煤量的需求煤量的需求煤量的供煤量的供煤量jixBxxBxxBxxAxxxAxxxij

2．线性规划问题的特点和数学模型

从以上两例可以看出，它们都属于一类优化问题．它们的共同持点是：

(1)每一个问题都用一组决策变量(x1，x2，……，xn)表示某一方案：这组决策变量的值就代表一个具体的方案．一般这些变量的取值是非负的。

(2)存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示．

(3)都有一个要求达到的目标，它可以用决策变量的线性函数来表示，这个函数称为目标函数．按问题的不同，要求目标函数实现最大化或最小化。

满足以上三个条件的数学模型称为线性规划问题的数学模型，其一般形式为

目标函数：nnxcxcxcZ2211max(min)

约束条件（或s.t.）：nixbxaxaxabxaxaxabxaxaxaimnmnmmnnnn,2,1,0),(),(),(22112222212111212111

约束条件常用英文缩写s.t.表示，而约束条件的最后一式又称为变量的非负性。

线性规划主要应用目标函数求最值的情况，在以下各方面有广泛的应用：

(1)在某一企业内部，如何配合产品的销售时间，使各部门的原料、产品的存储，分配的数量等最为合理；

(2)在某企业生产的产品数量(或产值)固定时，如何在现有设备、人力、原料等条件限制下，合理组织生产，使经济效益最高；

(3)在某一地区的交通网(公路网或铁路网)中，如何合理地组织运输，使总运费最小；

(4)当市场上产品(或原料)价格变动时，对于这些变化，企业如何做出最优决策；

(5)合理下料问题：利用某种类型的原料下料时，如何达到既满足需求，又使废料最少；

(6)配料问题．生产某类由各种原料配制的产品(如混合饲料等)时，如何满足规定的质量标准，又使产品的成本最低；

(7)库存问题，在仓库的容量及其它限制条件下，确定库存物资的品种、数量、期限，使得库存放益最高；

(8)在投入产出模型中，引进某一目标函数，制定最优的企业(或地区)经济计划。

二、线性规划问题的解法

图解法只适用于两个变量的简单线性规划问题。这种解法比较简单，也有助于几何直观地理解线性规划问题。这里不做介绍。

软件解法：规划模型的求解常用软件求解，主要有Excel,Lingo,Matlab等，这里用Lingo求解。

问题一：

Max Z = 32x1 + 30x2

3x1+4x2≤36 (设备A对产量的限制)

5x1+4x2≤40 (设备B对产量的限制)，

9x1+8x2≤76 (设备C对产量的限制)，

x1，x2≥0 (产量不能为负值)．

在Lingo中输入模型，注意书写格式：

1， 目标函数的变量Z不写；程序不分大小写；

2， 每行以分号结束；

3， 加、减、乘、除等运算符号一个都不能少；

4， “<”号等同于“≤”号，“>”号等同于“≥”号； 5， 所有函数均要加以前缀“@”符号；

6， 注释语句用感叹号“!”开头；

7， 非负约束是软件的缺省设置，可以不输入。

请看演示：

程序：

Max = 32*x1 + 30*x2;

3*x1+4*x2<36;

5*x1+4*x2<40;

9*x1+8*x2<76;

结果为： Global optimal solution found.

Objective value: 282.6667

Infeasibilities: 0.000000

Total solver iterations: 3

Variable Value Reduced Cost

X1 1.333333 0.000000

X2 8.000000 0.000000

Row Slack or Surplus Dual Price

1 282.6667 1.000000

2 0.000000 1.166667

3 1.333333 0.000000

4 0.000000 3.166667

即经过3步迭代，得到全局最优解为X1=1.333，X2=8.0。

最大利润为282.6667，设备A，C的资源(加工台时数)全部用完，设备B尚余1.33333台时数，

若需要加班生产，即增加设备的台时数，设备A每增加1小时，可增加利润1.16667千元；设备B因有剩余1.33333，故增加设备B的台时数对利润没有影响；设备C每增加1小时，可增加利润3.166667千元。

对问题二，有Lingo程序：

min=10*x11+5*x12+6*x13+4*x21+8*x22+12*x23;

x11+x12+x13=60; x21+x22+x23=100; x11+x21=50; x12+x22=70;

x13+x23=40;

求解结果为：

Global optimal solution found.

Objective value: 940.0000

Infeasibilities: 0.000000

Total solver iterations: 1

Variable Value Reduced Cost

X11 0.000000 9.000000

X12 20.00000 0.000000

X13 40.00000 0.000000

X21 50.00000 0.000000

X22 50.00000 0.000000