规划模型的概念

如何来分配有限资源，从而达到人们期望目标的优化分配数学模型，它在数学建模中处于中心地位。
这类问题一般可以归结为数学规划模型，规划模型的应用极为广泛，其作用已为越来越多的人所重视
规划模型是数学建模竞赛中最常见的一类数学模型

规划模型的数学描述

将一个优化问题用数学式子来描述，即求函数
$$u=f(x)x=(x_1,x_2,\dots ,x_n)$$
$x$是一个向量
在约束条件
$$h_i(x)=0,i=1,2,3,\dots ,m$$
m个等式和
$$g_j(x)\le 0(g_j(x)\ge 0),j=1,2,\dots ,p$$
p个不等式

$u=f(x)$这个函数，在一组等式和一组不等式的约束下，来取最大值或最小值
$$\begin{array}{c}x\to 决策变量\\ f(x)\to 目标函数\\ x\in 可行域\end{array}$$

整理一下
$$\begin{array}{c}一个规划问题的数学模型可表示为\\ min(ormax)u=f(x)x\in \Omega \\ s.t.h_i(x)=0,i=1,2,3,\dots ,m.\\ g_j(x)\le 0(g_j(x)\ge 0),j=1,2,\dots ,p.\end{array}$$

• $u=f(x)$是目标函数
• $x$是决策变量
• $h(x)和g(x)$分别为等式约束和不等式约束，统称为约束条件
• s.t.就是subject to，受约束于的意思

规划模型的分类

1. 根据是否存在约束条件
   1. 有约束问题
   2. 无约束问题
2. 根据决策变量的性质
   1. 静态问题
   2. 动态问题
3. 根据目标函数和约束条件表达式的性质
   1. 线性规划
   2. 非线性规划
   3. 二次规划
   4. 多目标规划
4. 根据决策变量的允许值
   1. 整数规划(0-1)
   2. 实数规划

建立规划模型的一般步骤

1. 确定决策变量
2. 确定目标函数的表达式
3. 寻找约束条件

线性规划模型

线性规划模型的一般形式

若在如下的模型中，$f(x),h_i(x),g_i(x),i=1,2,\dots ,m,j=1,2,\dots ,p$，均为线性函数，则称该模型为线性规划模型
$$\begin{array}{c}max(或min)z=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n\\ s.t.\{\begin{array}{c}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n(\le =\ge )b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n(\le =\ge )b_2\\ \dots \\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n(\le =\ge )b_m\end{array}\\ x_j\ge 0(j=1,2,\dots ,n)\end{array}$$

• 把目标函数写成线性表达式
• $x_j$是决策变量
• 约束条件里不管是等式还是不等式，都是线性函数
  • 如同线代里的线性方程组
• 如果$x_j$不是实数取值，是整数取值，又称为整数线性规划

建立线性规划模型的通常步骤

1. 确定决策变量：
   是模型要确定的未知变量，最重要的参数，是决策者解决实际问题的控制变量
2. 确定目标函数：
   目标函数决定线性规划问题的优化方向，是重要的组成部分。
   实际问题的目标可表示为决策变量的一个线性函数，并根据实际问题的优化方向求其最大化或最小化
3. 确定约束方程：
   通过约束方程来描述和反映一系列客观描述条件或环境的限制，这些限制通过一系列线性等式或不等式方程组来描述
4. 变量取值限制：
   一般情况下，决策变量取正值(或负值)。因此，模型中应有变量的非负约束即$x_j\le 0$。

任务分配问题

• 决策变量，设甲车床，生产工件1$x_1$件，生产工件2$x_2$件，生产工件3$x_3$件，乙车床，生产工件1$x_4$件，生产工件2$x_5$件，生产工件3$x_6$件
• 目标函数是希望加工费用最低
  $$minz=13x_1+9x_2+10x_3+11x_4+12x_5+8x_6$$
• 约束条件：台时的限制和加工工件数量的限制
  $$\begin{array}{c}0.4x_1+1.1x_2+1.0x_3\le 800\\ 0.5x_4+1.2x_5+1.3x_6\le 900\\ x_1+x_4=400\\ x_2+x_5=600\\ x_3+x_6=500\\ x_1,x_2,x_3,x_4,x_5,x_6\ge 0\end{array}$$
  解
  设在甲车床上加工工件1、2、3的数量分别为$x_1,x_2,x_3$，在乙车床上加工工件1、2、3的数量分别为$x_4,x_5,x_6$，可建立以下线性规划模型
  $$\begin{array}{c}minz=13x_1+9x_2+10x_3+11x_4+12x_5+8x_6\\ s.t.\{\begin{array}{c}{x}_1+x_4=400\\ x_2+x_5=600\\ x_3+x_6=500\\ 0.4x_1+1.1x_2+1.0x_3\le 800\\ 0.5x_4+1.2x_5+1.3x_6\le 900\\ x_i\ge 0,i=1,2,\dots ,6\end{array}\end{array}$$

加工奶制品的生产计划

• 决策变量，这50桶里面，多少桶生产$A_1$多少桶生产$A_2$
  $x_1$桶生产$A_1$，$x_2$桶，生产$A_2$
• 目标函数：$A_1$获利$24\cdot 3x_1$，$A_2$获利$16\cdot 4x_2$
  $$maxz=72x_1+64x_2$$
• 约束条件：
  牛奶供应的限制，每天50桶
  $$x_1+x_2\le 50$$
  劳动时间的限制，每天480工时
  $$12x_1+8x_2\le 480$$
  $A_1$每天最多生产100公斤
  $$3x_1\le 100$$
  非负约束
  $$x_1,x_2\ge 0$$

线性规划模型的求解

简单线性规划模型的求解

对于一般只有两个决策变量的简单线性规划模型，可以通过图解法进行求解
$$\begin{array}{c}{l}_1:x_1+x_2=50\\ l_2:12x_1+8x_2=480\\ l_3:3x_1=100\\ l_1:x_1=0,l_5:x_2=0\end{array}$$

在B(20,30)取得最优解
目标函数和约束条件是线性函数，可行域为直线段围成的凸多边形，目标函数的等值线为直线
最优解一定在凸多边形的某一个顶点取得

线性规划模型的软件求解

有许多求解数学规划模型的多种软件，如Matlab，Lingo，Excel，其中Lingo编程简单，易于操作，求解速度快，是求解规划模型的主要手段

Lingo编程入门

Lingo主要功能特色

1. 既能解决线性规划问题，也有较强的求解非线性规划问题的能力
2. 输入模型简练直观
3. 运行速度快，计算能力强
4. 内置建模语言，提供几十个内部函数，从而能以较少语句，较直观的方式描述较大规模的优化模型
5. 将集合概念引入编程语言，很容易将实际问题转换为Lingo模型
6. 能方便地与Excel、数据库等其他软件交换数据

需要注意的几个基本问题

1. 尽量使用实数优化，减少整数约束和整数变量
2. 尽量使用光滑优化，减少非光滑约束的个数
   尽量少使用绝对值，符号函数，变量求最大最小值，四舍五入，取整函数
3. 尽量使用线性模型，减少非线性约束和非线性变量的个数
4. 合理设定变量上下界，尽可能给出变量初始值
5. 模型中使用的参数数量级要适当(小于$10^3$)

需要注意的几个方面

1. 正确阅读求解报告Solution Report
2. 了解敏感性分析Range Report
3. 集合的应用SETS
4. 正确理解求解状态窗口Solver Status
5. 学会设置基本的求解选项OPTIONS
6. 掌握与外部文件的基本接口方法

Lingo编程中的重要细节

1. 代码需要始终在英文半角状态下输入
2. Lingo编程中，一般$<$等同于$\le$，$>$等同于$\ge$
3. 除了程序头尾以及其他内置语句(model,end,sets,endsets,data,enddata)外，其他语句均需要以分号结尾
4. 注释语句用$!$开始，分号结束
5. Lingo默认状态下决策变量均为非负变量、
6. Lingo在代码编译时，可以先按照集合段，目标段，约束段，逐段编译，完全编译通过后通过菜单"Lingo-Generate-Display model"来查看代码实现的模型
7. Lingo代码错误最典型的是index错误，即变量下标的索引出错

Lingo求解

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

目标函数值是14458.18
总共迭代次数2

加工奶制品求解

model:
max=72*x1+64*x2;
x1+x2<50;
12*x1+8*x2<480;
3*x1<100;
end

最优解是z=3360，x1是20，x2是30
Row表示代码中的四个式子

• 1对应3360，表示max取到了3360
• 2对应0，表示50牛奶都被用来生产
• 3对应0，表示480个工时全部被用来生产
• 4对应40，表示100里面含有40的余量
  原料无剩余，时间无剩余，加工能力剩余40
  资源剩余为0的约束称为紧约束

Dual Price 影子价格
最优解下，资源增加1单位，效益的增量

• 48表示牛奶增加1单位，利润增长48
• 2表示工时增加1单位，利润增长2
• 0表示加工能力增长不影响利润

35元可以买到一桶牛奶，买吗？
35<48，所以应该买

可聘用临时工人，付出的工资最多是每小时几元？
应该<2

规划模型的Lingo多段式编程

1. 集合段(SETS)
2. 目标与约束段
3. 数据段(DATA)：对集合的属性输入必要的常数数据
   格式
   属性=常数列表
   常数列表中的数据用逗号分开，也可以用空格分开
   变量名=？，运行时赋初值
4. 初始段(INIT)：赋初值
5. 计算段(CALC)：预处理
   

每个季度都有，需求量，正常生产400，加班生产450，库存费用20
$$\begin{array}{c}DEM:需求量\\ RP:正常生产的产量\\ OP:加班生产的产量\\ INV:库存量\end{array}$$

• 目标函数
  $$min\sum _{I=1}^4[400RP(I)+450OP(I)+20INV(I)]$$
• 约束条件

1. 能力限制
   $$RP(I)\le 40,I=1,2,3,4$$
2. 产品数量平衡方程
   $$\begin{array}{c}INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I),I=1,2,3,4\\ INV(0)=10\end{array}$$
   本季度的库存，等价于上个季度的库存+本季度正常生产+本季度的加班生产-本季度的需求
3. 变量的非负约束

MODEL:
//集合段
SETS:
	QUARTERS/1,2,3,4/:DEM,RP,OP,INV;
ENDSETS
//目标段
MIN=@SUM(QUARTERS:400*RP+450*OP+20*INV);
	//约束段
@FOR(QUARTERS(I):RP(I)<40);
@FOR(QUARTERS(I)|I#GT#1:
	INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););
INV(1)=10+RP(1)+OP(1)-DEM(1);
//数据段
DATA:
	DEM=40,60,75,25;
ENDDATA
END

I#GT#1，对I的取值进行限制，表示I大于1，I可以取2，3，4

结果表示生产总费用最小为78450

整数规划和0-1规划

整数规划问题的基本描述

要求全部或部分决策变量为整数的规划
分类：

1. 纯整数规划
2. 0-1整数规划
3. 混合整数规划
   求解：
   满足整数要求的条件下确定达到的总体最优目标的最佳组合。其解为离散解

整数规划的数学描述

$$\begin{array}{c}min(ormax)u=f(x)x\in \Omega \\ s.t.h_i(x)=0,i=1,2,3,\dots ,m.\\ g_j(x)\le 0(g_j(x)\ge 0),j=1,2,\dots ,p.\\ 其中决策变量x为整数，或者为0，1\end{array}$$
在Lingo编程中，决策变量为整数一般用$@gin(x)$表示；而0-1决策变量用$@bin(x)$表示

建设计划问题

设A、B两种类型的基地各建设$x_1,x_2$个
$$\begin{array}{c}maxz=20x_1+10x_2\\ s.t.\{\begin{array}{c}2000x_1+5000x_2\le 13000\\ 5x_1+4x_2\le 24\\ x_1\ge 0,x_2\ge 0且为整数\end{array}\end{array}$$

人员安排问题

因为每个服务员的工作时间会跨过4个时段
为使服务部门服务员总数最少
设前五个时段安排的服务员各为$x_1,x_2,x_3,x_4,x_5$
$$\begin{array}{c}minz=x_1+x_2+x_3+x_4+x_5\\ \\ s.t.\{\begin{array}{c}{x}_1\ge 8\\ x_1+x_2\ge 10\\ x_1+x_2+x_3\ge 7\\ x_1+x_2+x_3+x_4\ge 6\\ x_2+x_3+x_4+x_5\ge 9\\ x_3+x_4+x_5\ge 12\\ x_4+x_5\ge 5\\ x_5\ge 2\\ x_j\ge 0,j=1,2,3,4,5且为整数\end{array}\end{array}$$

混合泳接力队的选拔

总共有120种组合方式
设甲是否蝶泳为$x_{11}$，是否仰泳为$x_{12}$，是否蛙泳为$x_{13}$，是否自由泳为$x_{14}$
以此类推
$$x_{ij}=\{\begin{array}{c}0\\ 1\end{array}$$取1表示，第i个人。去游第j种泳姿，取0表示第i个人，不游第j种泳姿

总共有20个决策变量，最终取1的只有四个，其他的都取0
表格里的成绩用$C_{ij}$来表示
混合泳接力总成绩
$$\sum _{i=1}^5\sum _{j=1}^4{C}_{ij}{x}_{ij}$$
对运动员的约束：每个运动员最多参加一个项目
$$\begin{array}{c}{x}_{11}+x_{12}+x_{13}+x_{14}\le 1\\ x_{21}+x_{22}+x_{23}+x_{24}\le 1\\ x_{31}+x_{32}+x_{33}+x_{34}\le 1\\ x_{41}+x_{42}+x_{43}+x_{44}\le 1\\ x_{51}+x_{52}+x_{53}+x_{54}\le 1\end{array}$$
对泳姿的约束：每个项目必须有一个运动员参加
$$\begin{array}{c}{x}_{11}+x_{21}+x_{31}+x_{41}+x_{51}=1\\ x_{12}+x_{22}+x_{32}+x_{42}+x_{52}=1\\ x_{13}+x_{23}+x_{33}+x_{43}+x_{53}=1\\ x_{14}+x_{24}+x_{34}+x_{44}+x_{54}=1\end{array}$$

目标函数：
$$minz=\sum _{i=1}^5\sum _{j=1}^4{C}_{ij}{x}_{ij}$$
约束条件：
每人最多入选泳姿之一
$$\sum _{j=1}^4{x}_{ij}\le 1i=1,\dots ,5$$
每种泳姿有且只有1人
$$\sum _{i=1}^5{x}_{ij}\le 1j=1,\dots ,4$$
$$x_{ij}=\{\begin{array}{c}0\\ 1\end{array}$$

Lingo求解

MODEL:
sets:
	person/1..5/;
	position/1..4/;
	link(person,position):c,x;
endsets
data:
c=66.8,75.6,87,58.6,
57.2,66,66.4,53,
78,67.8,84.6,59.4,
70,74.2,69.6,57.2,
67.4,71,83.8,62.4;
enddata
min=@sum(link:c*x);

@for(person(i):@sum(position(j):x(i,j))<1);
@for(position(j):@sum(person(i):x(i,j))=1);

@for(link: @bin(x));
END

Matlab求解线性规划问题及优化工具箱

有关求解线性规划问题的命令

主要Matlab命令

X=linprog(c,A,b,Aeq,beq)
X=linprog(c,A,b,Aeq,beq,vlb,vub)
X=linprog(c,A,b,Aeq,beq,vlb,vub,x0)
X=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options)
[x,fval,exitflag,output]=linprog(...)

linprog基本函数
括号中的是输入项

用Matlab优化工具箱解线性规划

模型1
$$\begin{array}{c}Minz=cX\\ s.t.AX\le b\end{array}$$
目标和约束都是矩阵形式
只有不等式约束
$$x=linprog(x,A,b)$$

• c是目标函数的系数
• A是约束不等式的系数矩阵
• b是约束不等式的右单项
• x是输出的最优解
  模型2
  $$\begin{array}{c}Minz=cX\\ s.t.\{\begin{array}{c}AX\le b\\ Aeq\cdot X=beq\end{array}\end{array}$$
  $$x=linprog(x,A,b,Aeq,beq)$$
  模型3
  $$\begin{array}{c}Minz=cX\\ s.t.\{\begin{array}{c}AX\le b\\ Aeq\cdot X=beq\\ VLB\le X\le VUB\end{array}\end{array}$$

X=linprog(c,A,b,Aeq,beq,vlb,vub)
X=linprog(c,A,b,Aeq,beq,vlb,vub,x0)

x0表示初始点

[x,fval]=linprog(...)

返回最优解x及x处的目标函数值fval

例子

$$\begin{array}{c}maxz=0.4x_1+0.28x_2+0.32x_3+0.72x_4+0.64x_5+0.6x_6\\ s.t.\{\begin{array}{c}0.01x_1+0.01x_2+0.01x_3+0.03x_4+0.03x_5+0.03x_6\le 850\\ 0.02x_1+0.05x_4\le 700\\ 0.02x_2+0.05x_5\le 100\\ 0.03x_3+0.08x_6\le 900\\ x_j\ge 0j=1,2,\dots ,6\end{array}\end{array}$$

c=[-0.4 -0.28 -0.32 -0.72 -0.64 -0.6];
A=[0.01 0.01 0.01 0.03 0.03 0.03;
0.02 0 0 0.05 0 0;
0 0.02 0 0 0.05 0;
0 0 0.03 0 0 0.08];
b=[850;700;100;900];
Aeq=[];beq=[];
vlb=[0;0;0;0;0;0];vub=[];
[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

matlab只求解最小的情况，如果要求解最大，需要加一个负号，把整个目标函数转化为最小

任务分配问题

$$\begin{array}{c}minz=\left(\begin{array}{cccccc}13& 9& 10& 11& 12& 8\end{array}\right)X\\ s.t.\left(\begin{array}{cccccc}0.4& 1.1& 1& 0& 0& 0\\ 0& 0& 0& 0.5& 1.2& 1.3\end{array}\right)X\le \left(\begin{array}{c}800\\ 900\end{array}\right)\\ \left(\begin{array}{cccccc}1& 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 1& 0\\ 0& 0& 1& 0& 0& 1\end{array}\right)X=\left(\begin{array}{c}400\\ 600\\ 500\end{array}\right),X=\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\\ x_6\end{array}\right)\ge 0\end{array}$$

f=[13 9 10 11 12 8];
A=[0.4 1.1 1 0 0 0
0 1 0 0 1 0
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)

zeros表示一个列向量，六行一列的0

用Matlab工具箱解整数或0-1规划

X=intlinprog(c,intcon,A,b,Aeq,beq)
X=intlinprog(c,intcon,A,b,Aeq,beq,vlb,vub)
X=intlinprog(c,intcon,A,b,Aeq,beq,vlb,vub,x0)
X=intlinprog(c,intcon,A,b,Aeq,beq,vlb,vub,x0,options)
[x,fval,exitflag,output]=intlinprog(...)

intcon，用来指定整数变量

Matlab优化工具箱简介

输入

输出