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

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

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. 确定优化目标 目标：利润最大化。

利润=高价电利润+低价电利润 P=200(u1+u2)+140(v1+v2) Step 4. 寻找约束条件

1. 电量守恒：每月发电量=每月卖出量（2个） 2. 水量守恒：

发电用水量+直接放走量+库存量=原有库存量+来水量（4个） 3. 发电能力限制：4个 4. 水库蓄水量限制：4个 5. 高价电量限制：2个 Step 5. 构成数学模型

max200(u1?u2)?140(v1?v2)s.t.400xA1?200xB1?u1?v1,400xA2?200xB2?u2?v2xA1?yA1?zA1?1900?200xB1?yB1?zB1?850?40?xA1?yA1xA2?yA2?zA2?zA1?130xB2?yB2?zB2?zB1?15?xA2?yA2

400xA1?60000,400xA2?60000200xB1?35000,200xB2?350001200?zA1?2000,1200?zA2?2000800?zB1?1500,800?zB2?1500u1?50000,u2?50000xA1,xA2,xB1,xB2,yA1,yA2,yB1,yB2,zA1,zA2,zB1,zB2,u1,u2,v1,v2?0

【实例3】有4名同学到一家公司参加三个阶段的面试：公司要求每个同学必须首先到秘书处初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是

一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）：

秘书初试 主管复试 经理面试 15 20 16 10 20 18 10 15 同学甲 13 同学乙 10 同学丙 20 同学丁 8 这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早上8:00，问他们最早何时离开公司？ Step 1. 寻求决策，即回答什么？ 1. 同学甲、乙、丙、丁的面试次序

1）同学甲、乙、丙、丁每个阶段面试的开始时间 2）先后次序 2. 离开时间 Step 2. 确定决策变量

1. 同学甲、乙、丙、丁参加第j阶段面试的开始时间ti,j； 2. 同学甲、乙、丙、丁面试结束时间：T1，T2，T3，T4 3. 离开时间：T=max{ T1，T2，T3，T4} 4. 先后次序：ri,j，0—1变量 5. 面试时间（已知）：ci,j Step 3. 确定优化目标 Min T

Step 4. 寻找约束条件

1. 单人面试先后次序约束：ti,j+ci,j≤ti,j+1，i=1,2,3,4；j=1,2 2. 每个阶段j在同一时间只能由一个同学参加面试： ti,j + ci,j - tk,j ≤ T ri,k （i,k=1,2,3；j=1,2,3；i

MinT?max{T1,T2,T3,T4}s.t.T1?t1,3?c1,3T2?t2,3?c2,3T3?t3,3?c3,3

T4?t4,3?c4,3ti,j?ci,j?ti,j?1,i?1,2,3,4;j?1,2ti,j?ci,j?tk,j?Tri,k,i,k?1,2,3,4;j?1,2,3;i?ktk,j?ck,j?ti,j?T(1?ri,k),i,k?1,2,3,4;j?1,2,3;i?kti.j?0,Ti?0i,?1,2,3,4;j?1,2,3ri,k?0or1

4．模型的理论求解方法

线性规划问题和整数规划问题是两类非常重要的数学规划问题，它们的求解方法是很多数学规划问题的求解方法的基础。 4.1 线性规划问题的单纯形法 4.1.1 一般的线性规划问题模型

min(或max)z?c1x1?c2x2???cnxns.t.AAA(1)

x?bx?b(1)(2)(2) (1.2)

(3)x?bT(3)其中x???x1,x2,?,xn??列向量。

?Rn(2)(3)b,b为，A(1),A(2),A(3)为矩阵，b(1)，4.1.2 标准的线性规划问题

minz?cxT 其中：x,c?Rn4.13 单纯形法

ms.t.Ax?bx?0,b?R,b?0,A?Rm?n 。

(1.3)

,m?nG.B.Dantzig的单纯形法（Simplex method）是一个顶点迭代算法，即从一个顶点出发，沿着凸多面体的棱迭代到另一个顶点，使目标函数值下降（至少不升），由顶点个数的有限性，可以证明经过有限次迭代一定可以求得最优解或者判定该问题无最优解，这就是单纯形法的基本思想。而几何上一个的顶点对应在代数上的一个基可行解，因此，单纯形法求解线性规划问题只需要关心基可行解。

若线性规划问题(1.3)中：A??I,N?，其中I是一个m阶单位矩阵，且

b1,b2,?,bm?0，即为

minz?c1x1?c2x2???cnxnmniim?s.t.?cbi?1??j?m?1(?cj??caii?1i,j)xj

?a1,m?1xm?1???a1,nxn?b1?x1?x2?a2,m?1xm?1???a2,nxn?b2?????????xm?am,m?1xm?1???am,nxn?bm??xj?0,j?1,2,?,n? (1.4)

则I称为线性规划问题(1.4)的一个基，而对应着基的变量

xj,j?1,2,?,m称为基变量，其余变量xj,j?m?1,m?2,?,n为非基变

量。非基变量均取值零的可行解x???b1,b2,?,bm,0,?,0??T称为基可行

解。

对于式 (1.4)，单纯形法的计算步骤如下： Step 1. 检验各非基变量x的检验系数?jj??cj??ca，若

ii,ji?1m?j?0,j?m?1?,,n，则基可行解已是最优解，计算结束；否则转入

下一步；

Step 2. 若有某个?k(?k?0)对应xk的系数向量pk?0，则此问题无

最优解，停止计算；否则转入下一步；

Step 3. 根据

blal,k?k?max?{j?|?j，确定

xk为进基变量，

???b?设xl?min?i|ai,k?0?，

?ai,k???为对应的基变量，则xl为出基变量，转入

下一步；

Step 4. 以a为主元素进行迭代（即高斯消元法），把xk所对应

l,k的列向量：

?Pk???a1,k,?,al,k,?,am,k?T???0,?,0,1,0,?,0?T

目标函数中

xk也相应消去。将基变量中xl换为xk，重复

Step1—Step4，直到终止。

?max??s.t.【示例】利用单纯形法求解线性规划问题??????w?1000x1?1500x29x1?5x2?3504x1?5x2?2002x1?5x2?150x1,x2?0。

【解】：第一步，构造初始单纯形表

引入松弛变量x3，x4,x5将原问题化成标准形式：

?min??s.t.??????z??(1000x1?1500x2)9x1?5x2?x34x1?5x22x1?5x2?x4?350?200?x5?150

x1,x2,x3,x4,x5?0该问题已经满足(1.4)，基变量为x3，x4,x5，非基变量为x1,x2。基本可行解为

x??0,0,350,20?0,，15目0TT标函数值为０，检验系数为

???1000,1500,?0,，构造初始单纯形表如下：0,0基变量 x3p1 9 4 2 p2 5 5 5 p3 1 0 0 0 p4 0 1 0 0 p5 0 0 1 0 b 350 200 150 0 x4 x5 检验数? 1000 1500 j因为?1?1000?0,?2?1500?0，所以当前解不是最优解；

第二步，选择进基变量与离基变量

?2?max{?1,?2}?1500，x2为进基变量；b3a3,2???bi??min?|ai,k?0??30???ai,k?，

第三行对应的基变量为x5，所以x5为离基变量；结果如下表：

基变量 x3 x4 ←x5 检验数? j3,2p1 9 4 2 1000 p2 ↓ p3 5 5 ⑤ 1500 1 0 0 0 p4 0 1 0 0 p5 0 0 1 0 b 350 200 150 0 第三步，以a为主元进行迭代，得新的单纯形表如下：

基变量 x3 x4 x2 jp1 7 2 0.4 p2 0 0 1 0 p3 1 0 0 0 Tp4 0 1 0 0 p5 -1 -1 0.2 b 200 50 30 检验数? 400 -300 -45000 新的基本可行解为x??0,30,200,50,0?，最优值为-45000；检验数

?1?400?0，当前解不是最优解；

第四步，重复前面的第二步，得到进基变量为x1，离基变量为x4

基变量 ↓p1 x3 ←x4 x2 jp2 0 0 1 0 p3 1 0 0 0 p4 0 1 0 0 p5 -1 -1 0.2 b 200 50 30 7 ② 0.4 检验数? 400 2,1-300 -45000 第五步，以a为主元进行迭代，得新的单纯形表如下：

基变量 x3 x1 x2 检验数? jp1 0 1 0 0 p2 0 0 1 0 p3 1 0 0 0 p4 -3.5 0.5 -0.2 -200 p5 2.5 -0.5 0.4 b 25 25 20 -100 -55000 所有检验数均小于等于零，得到最优解：

x??25,20,25,0,0?T，最优值为：55000。

4.2 整数规划问题的分支定界法

求解整数规划问题的算法有分支定界法、割平面法、分解算法、松弛算法、群论算法等。

分支定界算法（Branch and Bound Algorithm）是最常用的一种，它是1965年由R.J.Dakin发现的一种隐式枚举法。它的基本思想是反复划分可行域，定出最优值 z*的界限 z1≤z*≤z2

对于极大化问题来讲，下界 z1 即为由计算已求得的所有可行整数点中的最大目标值，上界 z2 可由松弛问题的最优值或尚未查清的子问题的最大目标值得到，分支定界法就是将一个问题（P)不断的分支为几个问题的集合，并确定新的各子问题的界限，直到求得所要求的解为止。

分支定界法解纯整数规划和混合整数规划问题 ? 首先忽略整数约束求解，求得原问题的最优解 x

? 如果决策变量 xi 本是整数要求，但是得到的结果 xi=u（不是整数），则将原问题归结为2个区域的线性规划求解，这个两个区域为分别增加约束条件

xi ≥ceil(u) 和 xi ≤floor(u)

? 然后分别都这两个规划模型重复上面的步骤，直到满足整数要求为止。 ? 再选出最优解。

【示例】利用分支定界算法求解ILP问题：

?max??s.t.????z?5x1?8x2x1?x2?65x1?9x2?45xi?0,xi?I,i?1,2.

【解】：

第一步，忽略整数约束条件，求解线性规划问题

?max??s.t.????z?5x1?8x2x1?x2?65x1?9x2?45xi?0,i?1,2.(P0)

得到最优解为：x1=2.25，x2=3.75，z*=41.25；

不是整数解，根据x2=3.75将P0划分成两个线性规划问题：

?max??s.t.????z?5x1?8x2x1?x2?65x1?9x2?45x1?0,x2?4?max??s.t.(P1) 和 ????z?5x1?8x2x1?x2?65x1?9x2?45x1?0,x2?3(P2)

第二步，分别求解（P1）和（P2），得到最优解分别为

（P1）：x1=1.8，x2=4，z*=41，不是整数解，需要进一步分支； （P2）：x1=3，x2=3，z*=39，已是整数解，此分支结束。 对问题（P1）依照x1=1.8分解成两个线性规划问题：

?max??s.t.????z?5x1?8x2x1?x2?65x1?9x2?45x1?2,x2?4?max??s.t.(P3) 和 ????z?5x1?8x2x1?x2?65x1?9x2?45x1?1,x2?4(P4)

第三步，分别求解（P3）和（P4）,得到： （P3）：不可行；

（P4）：x1=1，x2=40/9，z*=365/9；不是整数解，需要进一步分支。 对问题（P4）依照x2=40/9分解成两个线性规划问题：

?maxz?5x1?8x2??s.t.x1?x2?6?5x1?9x2?45??x1?1,x2?4?(P5)

和

?max??s.t.???x??1z?5x1?8x2x1?x2?65x1?9x2?451,x2?5(P6)

第四步，分别求解问题（P5）和（P6）,得到它们的最优解： （P5）：x1=1，x2=4，z*=37，是整数解，不需要进一步分支； （P6）：x1=0，x2=5，z*=40，是整数解，不需要进一步分支。 比较问题（P1）到（P6）所得的最优解，最终得到原问题的最优解为：

x1=0，x2=5，z*=40。

5．软件求解方法

5.1 Lindo软件求解

范围：线性规划问题、整数规划问题、二次规划问题。 特点：编程简单但使用范围小。 演示实例：

【实例1】Lindo程序如下：

min 100x1+100x2+40y1+40y2+40y3+40y4+40y5 st

x1+x2+y1>4 x1+x2+y1+y1>3 x1+x2+y1+y2+y3>4 x2+y1+y2+y3+y4>6 x1+y2+y3+y4+y5>5 x1+x2+y3+y4+y5>6

x1+x2+y4+y5>8 x1+x2+y5>8 y1+y2+y3+y4+y5<3 end gin 7

【实例2】Lindo程序如下：

max 200u1+200u2+140v1+140v2 st

400xa1+200xb1-u1-v1=0 400xa2+200xb2-u2-v2=0 xa1+ya1+za1=2100 xb1+yb1+zb1-xa1-ya1=890 xa2+ya2+za2-za1=130 xb2+yb2+zb2-zb1-xa2-ya2=15 400xa1<60000 400xa2<60000 200xb1<35000 200xb2<35000 za1>1200 za1<2000 za2>1200 za2<2000

zb1>800 zb1<1500 zb2>800 zb2<1500 u1<50000 u2<50000 end gin 16

5.2 Lingo软件求解

范围：一般数学规划问题。

特点：使用范围广但编程比Lindo复杂。 演示实例： 【实例3】

model: Sets:

Members/1..4/:TSingle;!每个同学面试结束时间; Items/1..3/:;

Times(Members,Items):c,t; Links(Members,Members):r; endsets

min=@max(Members(i):TSingle(i));

@for(Members(i):TSingle(i)=t(i,3)+c(i,3));

@for(Members(i):@for(Items(j)|j#le#2:t(i,j)+c(i,j)<=t(i,j+1)));

@for(Members(k):@for(Members(i)|i#lt#k:@for(Items(j):t(i,j)+c(i,j)-t(k,j)<=@max(Members(l):TSingle(l))*r(i,k))));

@for(Members(k):@for(Members(i)|i#le#k:@for(Items(j):t(k,j)+c(

k,j)-t(i,j)<=@max(Members(l):TSingle(l))*(1-r(i,k))))); @for(Members(i):TSingle(i)>=0);

@for(Members(i):@for(Items(j):t(i,j)>=0)); @for(Members(i):@for(Members(j):@bin(r(i,j)))); data:

c=13 15 20 10 20 18 20 16 10 8 10 15; enddata end

本文来源：https://www.bwwdw.com/article/qidh.html