第4章 数学规划模型
在上一章中我们看到，建立优化模型要确定优化的目标和寻求的决策。用x表示决策变量，f(x)表示目标函数。实际问题一般对决策变量x的取值范围有限制，不妨记作x∈Ω，Ω称为可行域。优化问题的数学模型可表示为
Min(或Max)f(x),x?Ω
在第3章x通常是1维或2维变量，Ω通常是1维或2维的非负域。
T实际中的优化问题通常有多个决策变量，用n维向量x?(x1,x2,?,xn)表示，目标
函数f(x)是多元函数，可行域Ω比较复杂，常用一组不等式（也可以有等式）gi(x)≤0 (i=1,2, …,m)来界定，称为约束条件。一般地，这类模型可表述成如下形式
Minz?f(x)
xs.t.gi(x)≤0,i?1,2,?,m
这里的s. t. (subject to)是“受约束于”的意思。
显然，上述模型属于多元函数的条件极值问题的范围，然而许多实际问题归结出的这种形式的优化模型，其决策变量个数n和约束条件个数m一般较大，并且最优解往往在可行域的边界上取得，这样就不能简单地用微分法求解，数学规划是解决这类问题的有效方法。
需要指出的是，本章无意涉及数学规划（或运筹学）的具体计算方法，仍然着重于从数学建模的角度，介绍如何建立若干实际优化问题的模型，并且在用现成的数学软件求解后，对结果作一些分析。
4．1 奶制品的生产和销售
企业内部的生产计划有各种不同的情况。从空间层次来看，在工厂级要根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品的生产计划，在车间级则要根据产品生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。从时间层次看，若在短时间内认为外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则就要制订多阶段生产计划。
本节选择几个单阶段生产计划的实例，说明如何建立这类问题的数学规划模型，并利用软件求解的输出对结果作一些分析。
例1 加工奶制品的生产计划
问题 一奶制品加工厂用牛奶生产A1,A2两种奶制品，1桶牛奶可以在设备甲上用
12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1，A2全部能售出。且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。试为该场制订一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题：
1) 若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？
2) 若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？
3) 由于市场需求的变化，每公斤A1的获利增加到30元，应否改变生产计划？ 问题分析 这个优化问题的目标是使每天获利最大，要作的决策是生产计划，即每天用多少桶牛奶生产A1，用多少桶牛奶生产A2（也可以是每天生产多少公斤A1，多少公斤A2），决策受到3个条件的限制：原料（牛奶）供应、劳动时间、设备甲的加工能力。按题目所给，将决策变量、目标函数和约束条件用数学符号及式子表示出来，就可得到下面的模型。
基本模型
决策变量：设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2。
目标函数：设每天获利为z元。x1桶牛奶可生产3x1公斤A1，获利24×3x1，x2桶牛奶可生产4x2公斤A2，获利16×4x2，故z?72x1?64x2。
约束条件：
原料供应 生产A1，A2的原料（牛奶）总量不得超过每天的供应，即x1?x2≤50桶；
劳动时间 生产A1，A2的总加工时间不得超过每天正式工人总的劳动时间，即
12x1?8x2≤480小时；
设备能力 A1的产量不得超过设备甲每天的加工能力，即3x1≤100； 非负约束 x1,x2均不能为负值，即x1≥0,x2≥0 综上可得
Max z?72x1?64x2 (1)
s. t. x1?x2≤50 (2)
12x1?8x2 ≤480 (3) 3x1≤100 (4) x1≥0,x2≥0 (5)
这就是该问题的基本模型。由于目标函数和约束条件对于决策变量而言都是线性的，所以称为线性规划（Linear Programming,简记作LP）。
模型分析与假设
从本章下面的实例可以看到，许多实际的优化问题的数学模型都是线性规划（特别是在像生产计划这样的经济管理领域），这不是偶然的。让我们分析一下线性规划具有哪些特征，或者说：实际问题具有什么性质，其模型才是线性规划。
·比例性 每个决策变量对目标函数的“贡献”，与该决策变量的取值成正比；每个决策变量对每个约束条件右端项的“贡献”，与该决策变量的取值成正比。
·可加性 各个决策变量对目标函数的“贡献”，与其它决策变量的取值无关；各个决策变量对每个约束条件右端项的“贡献”，与其它变量的取值无关。
·连续性 每个决策变量的取值是连续的。
比例性和可加性保证了目标函数和约束条件对于决策变量的线性性，连续性则允许得到决策变量的实数最优解。
对于本例，能建立上面的线性规划模型，实际上是事先作了如下的假设：
1) A1，A2两种奶制品每公斤的获利是与它们各自产量无关的常数，每桶牛奶加工 A1，A2的数量和所需的时间是与它们各自的产量无关的常数；
2) A1，A2每公斤的获利是与它们相互间产量无关的常数，每桶牛奶加工出A1，A2的数量
和所需的时间是与它们相互间产量无关的常数；
3) 加工A1，A2的牛奶的桶数可以是任意实数。
这3条假设恰好保证了上面的3条性质。当然，在现实生活中这些假设只是近似成立 的，比如，A1，A2的产量很大时，自然会使它们每公斤的获利有所减少。
由于这些假设对于书中给出的、经过简化的实际问题是如此明显地成立，本章下面的例题就不再一一列出类似的假设了。不过，读者在打算用线性规划模型解决现实生活中实际问题时，应该考虑上面3条性质是否近似的满足。
模型求解
图解法 这个线性规划模型的决策变量为2维，用图解法既简单，又便于直观地把握线性规划的基本性质。
将约束条件（2）~（5）中的不等号改为等号，可知它们是Ox1x2平面上的5条直线，依次记为L1~L5，如图1。其中L4，L5分别是x2轴和x2轴，并且不难判断，（2）~（5）式界定的可行域是5条直线上的线段所围成的5边形OABCD。容易算出，5个顶点的坐标为：O(0,0)，A(0,50)，B(20,30)，C(100/3,10)，D(100/3,0)。
目标函数（1）中的z取不同数值时，在图1中表示一组平行直线（虚线），称等值线族。如z?0是过O点的直线，z?2400是过D点的直线，z?3040是过点C的直线，…。可以看出，当这族平行线向右上方移动到过点B时，z?3360，达到最大值，所以B点的坐标(20,30)即为最优解：x1?20,x2?30. x2 A L1 B L4 L2 L3 C O L5 D x1 z=0 z=2 400 z=3 360 图1 模型的图解法
我们直观地看到，由于目标函数和约束条件都是线性函数，在2维情形，可行域为直线段围成的凸多边形，目标函数的等值线都为直线，于是最优解一定在凸多边行的某个顶点取得。
推广到n维情形，可以猜想，最优解会在约束条件所界定的一个凸多面体（可行域）的某个顶点取得，线性规划的理论告诉我们，这个猜想是正确的。
软件实现 求解线性规划有不少现成的数学软件，比如用LINDO软件就可以很方便地实现。在LINDO6.1版本下打开一个新文件，像书写模型（1）~（5）一样，直接输入： max 72x1+64x2
st
2)x1+x2<50
3)12x1+8x2<480 4)3x1<100 end
注：LINDO中已规定所有决策变量均为非负，故（5）式不必输入；乘号省略，式中不能有括号，右端不能有数学符号；模型中符号≤，≥用〈﹦，〉=形式输入，它们与〈，〉等效；输入文件中第1行为目标函数，2），3），4）是为了标示各约束条件，便于从输出结果中查找相应信息；程序最后以“end”结束。
将文件存储并命名后，选择菜单“Solve”并对提示“DO RANGE（SENSITIVITY）ANALYSIS?”（灵敏性分析）回答“是”，即可得到如下输出：
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE
1) 3360.000
VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000
NO. ITERATIONS= 2
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000
第4章--数学规划模型-姜启源
