优化问题中的数学规划模型

优化问题中的数学规划模型

1．优化问题及其一般模型

优化问题是人们在工程技术、经济管理和科学研究等领域中最常遇到的问题之一。例如：

设计师要在满足强度要求等条件下选择材料的尺寸，使结构总重量最轻；公司经理要根据生产成本和市场需求确定产品价格，使所获利润最高；调度人员要在满足物质需求和装载条件下安排从各供应点到需求点的运量和路线，使运输总费用最低；投资者要选择一些股票、债券下注，使收益最大，而风险最小等等。

一般地，优化模型可以表述如下：

minz?f(x)s.t.gi(x)?0，i=1,2,?,m (1.1)

这是一个多元函数的条件极值问题，但是许多实际问题归结出的这种优化模型，其决策变量个数n和约束条件个数m一般较大，并且最优解往往在可行域的边界上取得，这样就不能简单地用微分法求解，数学规划就是解决这类问题的有效方法。

2．数学规划模型分类

“数学规划是运筹学和管理科学中应用及其广泛的分支。在许多情况下，应用数学规划取得的如此成功，以致它的用途已超出了运筹学的范畴，成为人们日常的规划工具。”[H.P.Williams.数学规划模型的建立]。

数学规划包括线性规划、非线性规划、整数规划、几何规划、多目标规划等，用数学规划方法解决实际问题，就要将实际问题经过抽

象、简化、假设，确定变量与参数，建立适当层次上的数学模型，并求解。

3．建立数学规划模型的步骤

当你打算用数学建模的方法来处理一个优化问题的时候，首先要确定寻求的决策是什么，优化的目标是什么，决策受到那些条件的限制（如果有限制的话），然后用数学工具（变量、常数、函数等）表示它们，最后用合适的方法求解它们并对结果作出一些定性、定量的分析和必要的检验。

Step 1. 寻求决策，即回答什么？必须清楚，无歧义。 阅读完题目的第一步不是寻找答案或者解法，而是…… Step 2. 确定决策变量

第一来源：Step 1的结果，用变量固定需要回答的决策 第二来源：由决策导出的变量（具有派生结构） 其它来源：辅助变量（联合完成更清楚的回答） Step 3. 确定优化目标

用决策变量表示的利润、成本等。 Step 4. 寻找约束条件

决策变量之间、决策变量与常量之间的联系。 第一来源：需求； 第二来源：供给； 其它来源：辅助以及常识。 Step 5. 构成数学模型

将目标以及约束放在一起，写成数学表达式。

【实例1】：某储蓄所每天的营业时间是上午9:00到下午5:00。根据经验，每天不同时间段所需要的服务员数量如下：

时间段（时） 9-10 10-11 11-12 12-1 1-2 2-3 3-4 4-5 服务员数量 4 3 4 6 5 6 8 8 储蓄所可以雇佣全时和半时两类服务员。全时服务员每天报酬100元，从上午9:00到下午5:00工作，但中午12:00到下午2:00之间必须安排1小时的午餐时间。储蓄所每天可以雇佣不超过3名的半时服务员，每个半时服务员必须连续工作4小时，报酬40元。问该储蓄所应如何雇佣全时和半时两类服务员？ Step 1：需要回答什么？

1. 雇佣的全时雇员数量和半时雇员数量；

2. 半时雇员开始上班时间？（最早9:00，最晚1:00） 3．费用是多少？ Step2：决策变量？

1．全时雇员数量：x；

2．每个时间开始时雇佣的半时雇员数量：yi，i=1,2,…,5 3．清楚吗？漏掉了什么？全时雇员需要午餐。 4．全时雇员数量分解：12点就餐：x1；1点就餐：x2

注意：x1，x2为由决策导出的变量。

Step3：目标函数

目标：支付报酬最少

支付报酬=全时员工报酬+半时员工报酬 Z=100(x1+x2)+40(y1+y2+y3+y4+y5) Step4：约束条件

需求：服务员数量约束(8个)；

供方约束：半时雇员约束：y1+y2+y3+y4+y5≤3； 常规约束：非负整数。 Step5：数学模型

Min100(x1?x2)?40(y1?y2?y3?y4?y5)s.t.x1?x2?y1?4x1?x2?y1?y2?3x1?x2?y1?y2?y3?4x2?y1?y2?y3?y4?6

x1x1?x2x1?x2x1?x2?y2?y3?y4?y5?5?y3?y4?y5?6?y4?y5?8?y5?8?

y1?y2?y3?y4?y5?3x1,x2,y1,y2,y3,y4,y5?Z?{0}【实例2】：某电力公司经营两座发电站，发电站分别位于两个水库

水源 A水库 A上，位置如下图所示：

已知发电站可以将水库A的1万立方米的水转换为400千度电能，发电站B只能将水库B的

发电站 A水源B水库 B1万立方米的水转换为200千度电能。发电站A、B每个月的最大发电能力分别是60000千度、35000千度。每个月最多有50000千度电能够

发电站 B以200元/千度的价格售出，多余的电能只能够

以140元/千度的价格售出。水库A、B的其它有关数据如下（单位：万立方米）：

水库最大蓄水量 水库 A 水库 B 2000 1500 40 15 800 850 水源流入水量 本月 200 下月 130 水库最小蓄水量 水库目前蓄水量 1200 1900 请你为该电力公司制定本月和下月的生产经营计划。 Step 1. 寻求决策，即回答什么？

1. 水库A、B本月和下月发电量（可以用水量表示）； 2. 电力公司的收益。 Step 2. 确定决策变量

1. 水库A、B本月和下月用于发电的水量：xA1，xA2，xB1，xB2

2. 收益导出决策变量：

本月和下月高价售电量：u1，u2； 本月和下月低价售电量：v1，v2；

3. 辅助决策变量（水库安全运行）：

本月和下月水库直接放走的水量：yA1，yA2，yB1，yB2； 本月和下月结束时水库的水量：zA1，zA2，zB1，zB2； Step 3. 确定优化目标 目标：利润最大化。