线性规划模型基本原理（LP）

在资源固定的利润最大化问题:

例题1.1 某机床厂生产甲，乙两种机床，每台销售后的利润分别为4千元和3千元。生产甲机床需要用A,B机器加工，加工时间分别为每台2小时和1小时；生产乙机床需要A,B,C三种机器加工，加工时间为每台各一小时。若每天用于加工的机器时数分别为A机器10小时，B机器8小时和C机器7小时，问该厂应生产甲，乙机床各几台，才能使总利润最大？

\[ max\quad z=4x_1+3x_2\quad (1.1)\\ (1.2)\quad\left \{ \begin{array}{lr**} 2x_1+x_2\leq 10\\x_1+x_2\leq 8\\x_2\leq 7\\x_1,x_2\geq 0 \end{array} \right. \]

变量x1，x2称之为决策变量，（1.1）式被称为问题的目标函数，(1.2)中的几个不等式是问题的约束条件，记为s.t.

\[ min\quad c^Tx\\ s.t.\quad\left \{ \begin{array}{lr**} Ax\leq b\\Aeq*x=beq\\lb\leq x\leq ub \end{array} \right. \]

其中c和x为n维列向量，A，Aeq为适当维数的矩阵，b，beq为适当维数的列向量；其中x返回的是决策向量的取值，fval返回的是目标函数的最优值，c为价值向量，A，b对应的是线性不等式约束，Aeq，beq对应的是线性等式约束，lb和ub分别对应的是决策向量的下界向量和上界向量
matlab中求解线性规划的命令为(只能求min，max加负号)：
  • [x,fval]=linprog(c,A,b)
  • [x,fval]=linprog(c,A,b,Aeq,beq)
  • [x,fval]=linprog(c,A,b,Aeq,beq,lb,ub)

\[ max\quad z=2x_1+3x_2-5x_3\\ s.t.\quad\left \{ \begin{array}{lr**} x_1+x_2+x_3=7\\2x_1-5x_2+x_3\geq 10\\x_1+3x_2+x_3\leq 12\\x_1,x_2,x_3\geq 0 \end{array} \right. \]

求解的Matlab程序如下：
1
2
3
4
5
6
c=[-2;-3;5];
a=[-2,5,-1;1,3,1];b=[-10;12];
aeq=[1,1,1];
beq=7;
[x,y]=linprog(c,a,b,Aeq,beq,zeros(3,1)); %因为c为n维列向量，这里的zeros(3,1)指的是一个行为3列为1的一个列向量，而lb=zeros(3,1)指的是x1，x2，x3都大于等于0
x,y=-y;

投资组合方案的配置问题

例题1.2 市场上有n种资产s_i(i=1,2,L,n)可以选择现用数额为M的相当大的资金做一个时期的投资。这n种资产在这一时期内购买s_i的平均收益率为r_i，风险损失率为q_i，投资越分散，总的风险越少，总体风险可用投资的s_i中最大的一个风险来度量。 购买s_i时要付交易费，费率为p_i，当购买额不超过给定值u_i时，交易费按购买u_i计算。另外，假定同期银行存款利率是r_0，既无交易费又无风险(r_0=5%)。 已知n=4时相关数据如下表1.1

试给该公司设计一种投资组合方案，即用给定资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。
符号规定：

<1>\(s_i\)表示第i种投资项目,如股票,债券等,i=0,1,L,n,其中\(s_0\)指存入银行 <2>\(r_i,p_i,q_i\),分别表示s_i的平均收益率，交易费率，风险损失率,i=0,L,n,其中\(p_0=0,q_0=0\) <3>\(u_i\)表示\(s_i\)的交易定额i=1,L,n <4>\(x_i\)表示投资项目\(s_i\)的资金,i=0,1,L,n <5>a表示投资风险度 <6>Q表示总体收益

基本假设：

<1>投资数额M相当大，为了便于计算，假设M=1 <2>投资越分散,总的风险越小 <3>总体风险用投资项目\(s_i\)中最大的一个风险来度量 <4>n+1种资产s_i之间是相互独立的 <5>在投资的这一时期内,\(r_i,p_i,q_i\)为定值,,不受意外因素的影响 <6>净收益和总体风险只受\(r_i,p_i,q_i\)影响,不受其它因素干扰

模型建立：

总体风险用所投资的s_i中最大的一个风险来衡量，即 \(max\left \{ \begin{array}{lr**} q_ix_i|i=1,2,L,n \end{array} \}\right.\\\) 购买s_i(i=1,L,n)所付交易费是一个分段函数，即 交易费=\(max\left \{ \begin{array}{lr**} p_ix_i,\quad x_i\geq u_i,\\ p_iu_i,\quad x_i\leq u_i.\\ \end{array} \right.\\\)

而题目所给定的定值u_i(单位:元)相对总投资M很少,p_iu_i更小,这样购买s_i的净收益可以简化为\((r_i-p_i)x_i\) 要使净收益尽可能大,总体风险尽可能小，这是一个多目标规划模型

目标函数和约束条件：

\[ \left \{ \begin{array}{lr**} \sum_{i=0}^{n}{(r_i-p_i)x_i}\\ min(max_{1\leq i\leq n}{(q_ix_i)}) \end{array} \right. \]

\[ \left \{ \begin{array}{lr**} \sum_{i=0}^{n}{(1+p_i)x_i}=M\\ x_i\geq 0,\quad i=0,1,...,n \end{array} \right. \]

多目标规划改成线性规划

模型1 在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险\(\frac{q_ix_i}{M}\leq a\),可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划

固定风险水平，优化收益

\(max\sum_{i=0}^{n}{(r_i-p_i)x_i}\) \[ s.t.\left \{ \begin{array}{lr**} \frac{q_ix_i}{M}\leq a\\ \sum_{i=0}^{n}{(1+p_i)x_i}=M,\quad x_i\geq 0\quad i=0,1,...,n \end{array} \right. \] 模型2 固定盈利水平，极小化风险

\(min{(max{(q_ix_i)})}\) \[ s.t.\left \{ \begin{array}{lr**} \sum_{i=0}^{n}{(r_i-p_i)x_i}\geq k\\ \sum_{i=0}^{n}{(1+p_i)x_i}=M,\quad x_i\geq 0,i=0,1,2,...,n \end{array} \right. \] 模型3投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险，收益分别赋予权重\(s(0\leq s\leq 1)\)和\((1-s)\),s称为投资偏好系数 \[ min \quad shemax{q_ix_i}-{(1-s)}\sum_{i=0}^{n}{(r_i-p_i)x_i}\\ s.t.\sum_{i=0}^{n}{(1+p_i)x_i}=M,\quad x_i\geq 0,i=0,1,2,...,n \]

模型1求解:

\[ minf=(-0.05,-0.27,-0.19,-0.185,-0.185)(x_0,x_1,x_2,x_3,x_4)^T\\ s.t.\left \{ \begin{array}{lr**} x_0+1.01x_1+1.02x_2+1.045x_3+1.065x_4=1\\ 0.025x_1\leq a\\ 0.015x_2\leq a\\ 0.055x_3\leq a\\ 0.026x_4\leq a\\ x_i\geq 0,\quad i=0,1,...,4 \end{array} \right. \]

由于a是任意给定的风险度，到底怎样没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长\(\Delta a=0.001\)进行循环搜索，编制程序如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
%clc,clear
a=0;hold on
while a<0.05
  c=[-0.05,-0.27,-0.19,-0.185,-0.185];
  A=[zeros(4,1),diag([0.025,0.015,0.055,0.026])];
  b=a*ones(4,1);
  Aeq=[1,1.01,1.02,1.045,1.065];
  beq=1;LB=zeros(5,1);
  [x,Q]=linprog(c,A,b,Aeq,beq,LB);
  Q=-Q;plot(a,Q,'*k');
  a=a+0.001;
end
xlable('a'),ylable('Q')
屏幕截图_20240116_173128
可以看出：

  • 风险越大，收益越大

  • 当投资越分散时，投资者承担的风险就越小，这与题目一致。冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资

  • 在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长越快。在这一点右边，风险增加很大时，利润增长缓慢所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的转折点作为最优投资组合，大约是a=0.6%，Q=20%，所对应投资方案为：风险度a=0.006，收益Q=0.2019，x_0=0,x_1=0.24,x_2=0.4,x_3=0.1091,x_4=0.22212

整数规划（数学规划中的变量（部分或全部）限制为整数）

  • 变量全限制为整数时，称为纯（完全）整数规划【多】
    • 原线性规划有最优解，当自变量限制为整数后，其整数规划会出现以下情况
      • 原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致
      • 当原线性规划的最优解不是整数，那当然不是限制过后整数规划的最优解（无可行解或最优解值变差）
    • 整数规划的最优解不能按照实数最优解简单取整得到(有可能不满足约束条件)
    • 纯整数规划：引进的松弛变量和剩余变量可以不要求取整数。松弛变量：解决把不等式约束变成等式约束的方法，例如，x_1+x_2<=10，引进松弛变量x_3(x_3>=0),此时原式子可以变成x_1+x_2+x_3=10(加上一个大于0的数等于10，说明没加之前小于等于10)；剩余变量:例如，x_1+x_2>=10,引进剩余变量x_3(x_3>=0)此时原式子可以变成x_1+x_2-x_3=10
  • 变量部分限制为整数的，称为混合整数规划
  • 0--1整数规划(工作安排，接力运动员非配)

合理下料问题

例题1.1设用某型号的圆钢下零件A_1,A_2,A_3,....,A_m的毛坯。在一根圆钢上下料的方式有B_1,B_2,....,B_n种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如下表所示。问怎样安排下料方式，使得既满足需要，所用的原材料又最少？

即：用B_1种下料方式每根圆钢会产生A_1种零件a_11个。A_1型号零件至少需要b_1个，A_m型号零件至少需要b_m个。
解设，模型如下：

\(x_j\)表示用\(B_j\)(j=1，2，...,n)种方式下料根数 \[ minZ=\sum_{j=1}^{n}{x_j}\\ s.t.\left \{ \begin{array}{lr**} \sum_{j=1}^{n}{a_{ij}x_j}\geq b_i\quad (i=1,2,...,m)\\ x_j\geq 0\quad (j=1,2,...,n)且为整数 \end{array} \right. \]

建厂问题

例题1.2某公司计划在m个地点建厂，可供选择的地点有A_1,A_2,...,A_m,他们的生产能力分别是a_1,a_2,...,a_m(假设生产同一件产品)。第i个工厂的建设费用为f_i(i=1,2,...,m),又有n个地点B_1,B_2,...B_n需要销售这种产品，其销量分别为b_1,b_2,...,b_n。从工厂运往销售地的单位运费为C_ij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？

解设以及模型：

\(x_{ij}\)表示从工厂运往销地的运量(i=1,2,...,m、j=1,2,...,n),又设

\(Y_i=\left \{ \begin{array}{lr**} 1\quad 在A_i建厂\\ 0\quad 不在A_i建厂 (i=1,2,...,m)\end{array} \right.\) \[ minZ=\sum\sum{c_{ij}x_{ij}}+\sum_{i=1}^{m}{f_iy_i}\\ 运输的费用+建设的费用\\ s.t.\left \{ \begin{array}{lr**} \sum_{i=1}^{m}{x_{ij}}\leq a_{ij}y_i\quad (i=1,2,...,m)\quad 从该工厂运出去的量一定小于该工厂的产量\\ \sum_{i=1}^{m}{x_{ij}\geq b_j}\quad (j=1,2,...,n)\quad 从工厂运到销售地的量要大于等于该地的销售量\\ x_{ij}\geq0,y_i=0或1\quad (i=1,2,...,m、j=1,2,...,n) \end{array} \right. \]

整数规划的一般数学模型(一般解决运输问题或者指派问题)

\[ max(min)z=\sum_{j=1}^{n}{c_jx_j}\\ s.t.\left \{ \begin{array}{lr**} \sum_{j=1}^{n}{a_{ij}x_j}\leq(\geq,=)b_i\quad (i=1,2,...,m)\\ x_j\geq，x_j为整数\quad (j=1,2,...,n) \end{array} \right. \]

分支定界算法求解整数规划

例题1.1：设整数规划问题如下

\[ max\quad z=x_1+x_2\\ s.t.\left \{ \begin{array}{lr**} 14x_1+9x_2\leq51\\ -6x_1+3x_2\leq1\\ x_1,x_2\geq0\quad 且为整数 \end{array} \right. \]

画图求解:(枚举法)

最优解是当x_1=3/2,x_2=10/3时Z=29/6

分支定界算法求解方法：

不考虑整数限制先求出相应松弛问题的最优解，

若松弛问题无可行解，则ILP无可行解

若求得的松弛问题最优解符合整数要求，则是ILP的最优解；

若不满足整数条件，则任选一个不满足整数条件的变量\(x_i^0\)来构造新的约束，添加到松弛问题中形成两个子问题

\(x_i\leq[x_i^0]\),向下取整，例如\(x_1=2.3\),则向下取整为2
\(x_i\geq[x_i^0]+1\),向上取整，例如\(x_2=3.3\),向上取整为4

依次在缩小的可行域中求解新构造的线性规划的最优解，并重复上述过程，直到子问题无解或有整数最优解

例题1.2：

\[ max\quad z=3x_1+2x_2\\ s.t.\left \{ \begin{array}{lr**} 2x_1+3x_2\leq4\\ 2x_1+x_2\leq24\\ x_1,x_2\geq0 \end{array} \right. \]

用matlab解得： \[ s.t.\left \{ \begin{array}{lr**} x_1=3.25\\ x_2=2.5\\ z=14.75 \end{array} \right. \]

先将x_1向下取整

\[ max\quad z=3x_1+2x_2\\ s.t.\left \{ \begin{array}{lr**} 2x_1+3x_2\leq4\\ 2x_1+x_2\leq24\\ x_1\leq3\\ x_1,x_2\geq0 \end{array} \right.\\ 得到：\left \{ \begin{array}{lr**} x_1=3\\ x_2=2.67\\ z=14.43 \end{array} \right. \]

不难发现，虽然x_1为整数，但是x_2=2.67,说明x_1向下取整无法得到最优解
再把x_1向上取整

\[ max\quad z=3x_1+2x_2\\ s.t.\left \{ \begin{array}{lr**} 2x_1+3x_2\leq4\\ 2x_1+x_2\leq24\\ x_1\geq4\\ x_1,x_2\geq0 \end{array} \right.\\ 得到：\left \{ \begin{array}{lr**} x_1=4\\ x_2=1\\ z=14 \end{array} \right. \]

注意：整数规划只需要决策变量为整数，也就是x_1,x_2为整数就行，不要求结果z也为整数；并且当发现x_1向上取整可以后，还需要测验x_2向上和向下取整，以确保z的最大值 \[ max\quad z=3x_1+2x_2\\ s.t.\left \{ \begin{array}{lr**} 2x_1+3x_2\leq4\\ 2x_1+x_2\leq24\\ x_1\leq3,x_2\leq2\\ x_1,x_2\geq0 \end{array} \right.\\ 得到：\left \{ \begin{array}{lr**} x_1=3\\ x_2=2\\ z=13 \end{array} \right. \]

发现z此时不是最大值，继续把x_2向上取整

\[ max\quad z=3x_1+2x_2\\ s.t.\left \{ \begin{array}{lr**} 2x_1+3x_2\leq4\\ 2x_1+x_2\leq24\\ x_1\leq3,x_2\geq3\\ x_1,x_2\geq0 \end{array} \right.\\ 得到：\left \{ \begin{array}{lr**} x_1=2.2\\ x_2=3\\ z=13.5 \end{array} \right. \]

通过比较以上发现，x_1=4,x_2=1,z=14为最优解

割平面算法求解整数规划

不考虑整数限制先求出相应松弛问题的最优解，

若松弛问题无可行解，则ILP无可行解

若求得的松弛问题最优解符合整数要求，则是ILP的最优解；

如果松弛问题的解含有非整数分量，则对松弛问题增加割平面条件：即对松弛问题增加一个线性约束，将松弛问题的可行区域割掉一块，使得非整数解恰好在割掉的一块中，但又没有割掉原问题的可行解，重复上述过程

例题1.1

\[ max\quad z=x_1+x_2\\ s.t.\left \{ \begin{array}{lr**} -x_1+x_2\leq 1\\ 3x_1+x_2\leq 4\\ x_1,x_2\geq 0\\ x_1,x_2均为整数 \end{array} \right. \]

如何确定应该切掉那一部分？引入松弛变量或剩余变量将不等式变量转化为等式变量,方法如下:

\[ max\quad z=x_1+x_2+0x_3+0x_4\quad (1)\\ s.t.\left \{ \begin{array}{lr**} -x_1+x_2+x_3=1\quad (2)\\ 3x_1+x_2+x_4=4\quad (3)\\ x_1,x_2,x_3,x_4\geq 0\\ x_1,x_2,x_3,x_4均为整数 \end{array} \right. \]

将3式子减去2式子得到下面4式子，让3式子加上3×2式子得到下面5式子：

\[ x_1-\frac{1}{4}x_3+\frac{1}{4}x_4=\frac{3}{4}\quad (4)\\ x_2+\frac{3}{4}x_3+\frac{1}{4}x_4=\frac{7}{4}\quad (5) \]

把每个式子变量的系数和常量变成一个整数加上一个分数，要求分数必须大于0，整数无要求:

\[ (1+0)x_1+(-1+\frac{3}{4})x_3+(0+\frac{1}{4})x_4=0+\frac{3}{4}\\ (1+0)x_2+(0+\frac{3}{4})x_3+(0+\frac{1}{4})x_4=\frac{7}{4} \]

整数放左边，分数放右边：

\[ x_1-x_3=\frac{3}{4}-(\frac{3}{4}x_3+\frac{1}{4}x_4)\\ x_2=\frac{7}{4}-(\frac{3}{4}x_3+\frac{1}{4}x_4)\quad(6) \]

注意:因为x_1-x_3为整数，\((\frac{3}{4}x_3+\frac{1}{4}x_4)\)（不可能为0）大于等于1，所以\(\frac{3}{4}-(\frac{3}{4}x_3+\frac{1}{4}x_4)\)一定小于0：

\[ \frac{3}{4}-(\frac{3}{4}x_3+\frac{1}{4}x_4)\leq0\\ 则:3x_3+x_4\geq3 \]

得到\(3x_3+x_4\geq3\)后，6式可以变为\(x_2=\frac{7}{4}-(\geq3)\)则：\(4x_2\leq4,x_2\leq1\)

最终得到：\(x_2\leq1\)

\[ x_i+\sum{a_{ik}x_k}=b_i\\ a_ik=[a_{ik}]+(a_{ik}-La_{ik})+f_{ik}\quad f为小数部分，La为求整数以后\\ b_i=[b_i]+(b_i-Lb_i)=[b_i]+f_i\\ x_i+\sum[a{ik}]x_k+\sum{f_kx_k}=[b_i]+f_i\\ x_i+\sum{[a_{ik}]}x_k-[b_i]=-\sum{[f_{ik}]x_k}+f_i\quad 将整数与整数，小数与小数放在一起 \]

例题1.2已知AM工厂是一个拥有四个车间的玩具生产商，该厂商今年新设计出A,B,C,D,E,F六种玩具模型，根据以前的生产情况及市场调查预测，得知生产每单位产品所需要的工时，每个车间在一季度的工时上限以及产品的预测价格，如下表所示。问：每种设计产品在这个季度各应生产多少，才能使AM工厂这个季度的生产总值达到最大？

\[ max\quad Z=20x_1+14x_2+16x_3+36x_4+32x_5+30x_6\\ s.t.\left \{ \begin{array}{lr**} 0.01x_1+0.01x_2+0.01x_3+0.03x_4+0.03x_5+0.03x_6\leq 850\\ 0.02x_1+0.05x_4\leq 700\\ 0.02x_2+0.05x_5\leq 100\\ 0.03x_3+0.08x_6\leq 900\\ x_i\geq0,且为整数,i=1,2,3,4,5,6 \end{array} \right. \]

设置每个玩具生产的数量为决策变量x_1,...,x_6,用切割平面得：

$$ min-20x_1-14x_2-16x_3-36x_4-32x_5-30x_6+0x_7+0x_8+0x_9+0x_10\

s.t.{ \[\begin{array}{lr**} 0.01x_1+0.01x_2+0.01x_3+0.03x_4+0.03x_5+0.03x_6+x_7=850\\ 0.02x_1+0.05x_4+x_8=700\\ 0.02x_2+0.05x_5+x_9=100\\ 0.03x_3+0.08x_6+x_10=900\\ x_i\geq0,且为整数,i=1,2,3,4,5,6,...,10 \end{array}\]

. $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
%DividePlane.m
function[int x,intf]=DividePlane(A,c,b,baseVector)
%功能：用割平面法求解整数规划
%调用格式：[intx,intf]=DividePlane(A,c,b,baseVector)
%其中，A：约束矩阵;
%     c:目标函数系数向量;
%     b:约束右端向量;
%     baseVector:初始基向量;
%     intx:目标函数取最小值时的自变量值
%     intf:目标函数的最小值
sz=size(A);
nVia:sz(2);%获取有多少决策变量
n=sz(1);%获取有多少约束条件
xx=1:nVia;

if length(baseVector)~=n
    disp('基变量的个数要与约束矩阵的行数相等');
    mx=NaN;
    mf=NaN;
    return;
end

M=0;
sigma=-[transpose(c)zeros(1,(nVia-length(c)))];
xb=b;
解得：intx=35000 5000 30000 0 0 0；intf=-1250000

匈牙利算法（0-1规划问题）

投资问题：

例题1.1有600万元投资5个项目，收益如表，求最大利润方案

x_j为决策变量(j=1,2,...,5),表示投资哪个项目

\[ x_j=\left \{ \begin{array}{lr**} 1\quad 选中第j个项目投资\\ 0\quad 不选中第j个项目投资 \end{array} \right. \]

\[ max \quad Z=160x_1+210x_2+60x_3+80x_4+180x_5\\ \left \{ \begin{array}{lr**} 210x_1+300x_2+150x_3+130x_4+260x_5\leq600\\ x_1+x_2+x_3=1\\ x_3+x_4=1\\ x_5\leq x_1\\ x_1,x_2,x_3,x_4,x_5=0或1 \end{array} \right. \]

例题1.2某种工序的约束条件为：\(4x_1+5x_2\leq200\)另一种工序的约束条件是\(3x_1+5x_2\leq180\)

\[ y=\left \{ \begin{array}{lr**} 1\quad 采用原工序\\ 0\quad 采用新工序 \end{array} \right. \]

M为∞的数

\[ 4x_1+5x_2\leq200+(1-y)M\\ 3x_1+5x_2\leq180+yM \]

互斥约束的推广：

从下述p个约束条件中恰好选择q个约束条件：
\(\sum_{j=1}^{n}{a_{ij}x_j}\leq b_i(i=1,2,...,p)\)
新增一个决策变量y_i

\[ y_i=\left \{ \begin{array}{lr**} 0\quad 选第i个约束条件\\ 1\quad 不选第i个约束条件 \end{array} \right. \]

\[ \left \{ \begin{array}{lr**} \sum_{j=1}^{n}a_{ij}x_j\leq b_i+My_i\\ \sum_{i=1}^{p}y_i=p-q \end{array} \right. \]

固定费用问题

例题1.3服装公司租用生产线拟生产T恤，衬衫和裤子。每年可用劳动力8200h，布料8800m^2

假设：

\[ y_j=1,要租用生产线j\\ y_j=0.不租用生产线j\\ 第j种服装生产量为x_j\\ M为∞ \]

\[ max\quad Z=150x_1+220x_2+300x_3-200000y_1-150000y_2-100000y_3\\ \left \{ \begin{array}{lr**} 3x_1+2x_2+6x_3\leq 8200\\ 0.8x_1+1.1x_2+1.5x_3\leq 8800\\ x_1,x_2,x_3\leq0,且取整数\\ y_1,y_2,y_3=0或1\\ x_1\leq M_1y_1\\ x_2\leq M_2y_2\\ x_3\leq M_3y_3 \end{array} \right. \]

售价减去可变成本就是利润

指派问题

例题1.4甲乙丙丁四个人，ABCD思乡工作，要求每人只能做一项工作，每项任务只由一人完成，问如何指派总时间最短

假设：引入0-1变量x_ij

\[ x_{ij}=1:第i人做第j项工作\\ x_{ij}=0:第i人不做第j项工作\\ min\quad Z=3x_{11}+5x_{12}+8x_{13}+4x_{14}\\+6x_{21}+8x_{22}+5x_{23}+4x_{24}\\+2x_{31}+5x_{32}+8x_{33}+5x_{34}\\+9x_{41}+2x_{42}+5x_{43}+2x_{44}\\ s.t.\left \{ \begin{array}{lr**} x_{11}+x_{21}+x_{31}+x_{41}=1\\ x_{12}+x_{22}+x_{32}+x_{42}=1\\ x_{13}+x_{23}+x_{33}+x_{43}=1\\ x_{14}+x_{24}+x_{34}+x_{44}=1 \end{array} \right. \]

  • 人数和工作不等

    人少工作多：添加虚拟的”人“，代价都为0

    人多工作少：添加虚拟的工作，代价都为0

  • 一个人可以做多项工作：该人可以化为几个相同的“人”

  • 该工作一定不能由某人做：该人做该工作的代价应取足够大M

匈牙利解法的一般步骤：

第一：变换指派问题的系数(也称效率)矩阵(c_ij)为(b_ij),使在(b_ij)的各行各列中都出现0元素即，从(c_ij)的每行元素都减去该行的最小元素，再从所得新系数矩阵的每列元素中减去该列的最小元素

第二：圈0，找不同行，不同列的独立0元素，其它的0划掉

第三:试指派(独立0元素的个数不够的情况)
  • 对不含有独立0元素的行标对号，再对画对号的这一行，有被划掉的0的列标对号，再对画对号的这一列中有的独立0元素的行标对号

  • 对未标记对号的行画直线，和已经被标对号的列画直线

第四：变换矩阵，在没有被划掉的元素中找到最小值为1，对于标记对号的行减去最小值，列加上最小值（0不用进行加减），没画对号的行列不用管

例题2.1求解以下指派问题

\[ \left[ \matrix{ 3&8&2&10&3\\ 8&7&2&9&7\\ 6&4&2&7&5\\ 8&4&2&3&5\\ 9&10&6&9&10 } \right] \]

1
2
3
4
5
6
7
8
9
10
11
12
13
c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5;8 4 2 3 5;6 10 6 9 10];
c=c(:);%把矩阵c转化为向量
a=zeros(10,25)
for i=1:5 %实现循环运算
  a(i,(i-1)*5+1:5*i)=1;
  a(5+i,i:5:25)=1;
end %此循环把指派问题转化为线性规划问题
b=ones(10,1);
[x,y]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1));
X=reshape(x,5,5) %重构成5×5的矩阵
opt=y %输出
%求得最优指派方式为x_15=x_23=x_32=x_44=x_51=1,最优值为21

非线性规划模型(NP)

包含二次项及以上的项数就是非线性规划(目标函数或限制条件中有非线性)

投资决策问题

例题1.1某企业有n个项目可供选择投资，并且至少要对其中的一个项目投资。已知该企业拥有总资金A元，投资于第i，i=1，2，...，n个项目需花资金a_i元，并预计可收益b_i元，试选择最佳投资方案。
设投资变量为：

\[ x_i=\left \{ \begin{array}{lr**} 1\quad决定会投资第i个项目\\ 0\quad决定不投资第i个项目 \end{array} \right.\\ 则投资总额为\sum_{i=1}^{n}{a_ix_i},投资总收益为\sum_{i=1}^{n}{b_ix_i} \]

因为该公司至少要对一个项目投资，并且总的投资金额不能超过总资金A，故有限制条件

\[ 0<\sum_{i=1}^{n}{a_ix_i}\leq A \]

另外由于x_i只能取0或1所以还有

\[ x_i(1-x_i)=0,i=1,2,...,n \]

投资资金固定，用比值法看最合适,最佳投资方案应是投资额最小而收益最大(10万赚10万；3万赚10万的区别)，所以这个最佳投资决策问题归结为总资金以及决策变量(取0或1)的限制条件下，极大化总收益和总投资之比。(因为不考虑风险问题，所以把资金投资完的收益一定最大，所以不考虑全投资到一个)

\[ max=\frac{\sum_{i=1}^{n}{b_ix_i}}{\sum_{i=1}^{n}{a_ix_i}}\\ s.t.\left \{ \begin{array}{lr**} 0<\sum_{i=1}^{n}{a_ix_i}\leq A\\ x_i(1-x_i)=0,i=1,2,...,n \end{array} \right. \]

matlab中非线性规划的数学模型：

\[ min\quad f(x)\\ s.t.\left \{ \begin{array}{lr**} A·x\leq b\\ Aeq·x=beq\\ c(x)\leq0\\ ceq(x)=0\\ lb\leq x\leq ub \end{array} \right. \]

其中f(x)是标量函数，A，b,Aeq,beq,lb,ub是相应维数的矩阵和向量，c(x),ceq(x)是非线性向量函数
例题1.2

\[ min\quad f(x)=x_1^2+x_2^2+x_3^2+8\\ s.t.\left \{ \begin{array}{lr**} x_1^2-x_2+x_3^2\geq 0\\ x_1+x_2^2+x_3^2\leq20\\ -x_1-x_2^2+2=0\\ x_2+2x_3^2=3 x_1,x_2,x_3\geq0 \end{array} \right. \]

  • 编写M函数fun1.m定义目标函数
    1
    2
    function f=fun1(x);
    f=sum(x.^2)+8;   %1.x·2是矩阵×2;2.x^2是实数的平方;3.x.^2是矩阵中每个数的平方
  • 编写M函数fun2.m定义非线性约束条件
    1
    2
    3
    4
    5
    function[g,h]=fun2[x];
    g=[-x(1)^2+x(2)-x(3)^2
    x(1)+x(2)^2+x(3)^3-20];%非线性不等式约束
    h=[-x(1)-x(2)^2+2
    x(2)+2x(3)^2-3];%非线性等式约束
  • 编写主程序文件如下
    1
    [x,y]=fmincon('fun1',rand(3,1),[],[],[],[],zeros(3,1),[],'fun2')%rand是生成随机值有几个变量就是rand(x,1);如果有线性规划也要写，没有都标成[];zeros是生成初值里面值和rand中一样
    得到x_1=0.5522,x_2=1.2033,x_3=0.9478时，最小值y=10.6511

二次规划(若某非线性规划的目标函数是自变量的二次函数，约束条件又全是线性的，就称这种规划为二次规划)

\[ min\frac{1}{2}x^THx+f^{T}{x}\\ s.t.\left \{ \begin{array}{lr**} Ax\leq b\\ Aeq·x=beq\\ lb\leq x\leq ub \end{array} \right. \]

这里H是实对称矩阵(对角线元素随便，但其他的元素沿对角线对称)，f,b,beq,lb,ub是列向量，A，Aeq是相应维数的矩阵
matlab中求解二次规划的命令是：
1
[x,fval]=quadprog(H,f,A,b,Aeq,beqlb,ub,x_0,options)%返回值x是决策向量x的值，返回值fval是目标函数在x处的值
例题2.1

\[ min\quad f(x)=2x_1^2-4x_1x_2+4x_2^2-6x_1-3x_2\\ s.t.\left \{ \begin{array}{lr**} x_1+x_2\leq3\\ 4x_1+x_2\leq9\\ x_1,x_2\geq0 \end{array} \right. \]

1
2
3
4
5
h=[4,-4;-4,8];
f=[-6;-3];
a=[1,1;4,1];
b=[3;9];
[x,value]=quadprog(h,f,a,b,[],[],zeros(2,1))

求得x_1=1.9500,x_2=1.0500,minf(x)=-11.0250

供应与选址问题

应用例题2.2 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a,b表示，距离单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5，1)，B(2，7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连 （1）试制定每天的供应计划，即从A,B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小 （2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？

记工地的位置为(a_i,b_i),水泥日用量为d_i,i=1,...,;料场位置为(x_j,y_j)，日储量为e_j，j=1,2;从料场j向工地i的运送量为X_ij

\[ 目标函数：min\quad f=\sum_{j=1}^{2}\sum_{i=1}^{6}X_{ij}\sqrt{(x_j-a_i)^2+(y_j-b_i)^2}\\ 约束条件：\sum_{j=1}^{2}{X_{ij}=d_i},i=1,2,...,6\\ \sum_{i=1}^{6}{X_ij}\leq e_j,j=1,2 \]

约束条件：1.每天从两个料场运送到每个工地的用料要等于该建筑工地的水泥日用量 2.每天从每个料场运送到各个建筑工地的用料要小于该料场的日存储量
当用临时料场时决策变量为：X_ij;当不用临时料场时决策变量为：X_ij,x_j,y_j
使用临时料场的情形：
使用两个临时料场A(5,1),B(2,7)求从料场j向工地i的运送看为X_ij，在各个工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小

\[ X_{11}=X_1,X_{21}=X_2,X_{31}=X_{3},X_{41}=X_4,X_{51}=X_5,X_{61}=X_6\\ X_{12}=X_7,X_{22}=X_{8}X_{32}=X_9,X_{42}=X_{10},X_{52}=X_{11},X_{62}=X_{12} \]

\[ min\quad f=\sum_{j=1}^{2}\sum_{i=1}^{6}{aa(i,j)}X_{ij}\quad 其中i=1,2,...,6;j=1,2\\ aa(i,j)=\sqrt{(x_j-a_i)^2+(y_j-b_i)^2} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
clear
a=[1.25 8.75 0.5 5.75 3 7.25];
b=[1.25 0.75 4.75 5 6.5 7 75];
d=[3 5 4 7 6 11];
x=[5 2];
y=[1 7];
e=[20 20];
for i=1:6
  forj=1:2
    aa(i,j)=sqrt((x(j)-a(i))^2+(y(j)-b(i))^2));
  end
end
CC=[aa(:,1);aa(:,2)]';
A=[1 1 1 1 1 1 0 0 0 0;0 0 0 0 0 0 1 1 1 1 1 1 ];
B=[20;20];
Aeq=[1 0 0 0 0 0 1 0 0 0 0 0 %从第1，2料场运到工地1的料
     0 1 0 0 0 0 0 1 0 0 0 0 
     0 0 1 0 0 0 0 0 1 0 0 0
     0 0 0 1 0 0 0 0 0 1 0 0 
     0 0 0 0 1 0 0 0 0 0 1 0
     0 0 0 0 0 1 0 0 0 0 0 1 ];
beq=[d(1);d(2);d(3);d(4);d(5);d(6)];
VLB=[0 0 0 0 0 0 0 0 0 0 0 0];
VUB=[];
x_0=[1 2 3 0 1 0 0 1 0 1 0 1];
[xx,fval]=linprog(CC,A,B,Aeq,beq,VLB,VUB,x_0)
使用两个新建料场的情况,此时为非线性规划(目标函数中非线性，约束条件还是线性的)

\[ X_{11}=X_1,X_{21}=X_2,X_{31}=X_{3},X_{41}=X_4,X_{51}=X_5,X_{61}=X_6\\ X_{12}=X_7,X_{22}=X_{8}X_{32}=X_9,X_{42}=X_{10},X_{52}=X_{11},X_{62}=X_{12}\\ x_1=X_{13},y_1=X_{14},x_2=X_{15},y_2=X_{16} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function f=liaoch(x)
a=[1.25 8.75 0.5 5.75 3 7.25];
b=[1.25 0.75 4.75 5 6.5 7.75];
d=[3 5 4 7 6 11];
e=[20 20];
f1=0;
for i=1:6
  s(i)=sqrt((x(13)-a(i))^2+(x(14)-b(i)^2);
  f1=s(i)*x(i)+f1;
end
f2=0;
for i=7:12
  s(i)=sqrt((x(15)-a(i-6))^2+(x(16)-b(i-6))^2);
  f2=s(i)*x(i)+f2;
end
f=f1+f2;
%主程序
x_0=[3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499]';
A=[1 1 1 1 1 1 0 0 0 0 0 0 
   0 0 0 0 0 0 1 1 1 1 1 1 ];
B=[20;20];
Aeq=[1 0 0 0 0 0 1 0 0 0 0 0 %从第1，2料场运到工地1的料
     0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 
     0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0
     0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
     0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0
     0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0];
beq=[3 5 7 6 11]';
vlb=[zeros(12,1);-inf;-inf;-inf;-inf];
vun=[];
[x,fval,exitflag]=fmincon('liaoch',x_0,A,B,Aeq,beq,vlb,vub)

层次分析法求解

  • 用于最佳方案的选取(选择运动员，选择地址)
  • 用于评价类问题(评价水质情况，评价环境)
  • 用于指标体系的优选(兼顾科学和效率)
构造判断矩阵(成对比较):用1~9标度方法给出

C1(景色)，C2(费用),C3(居住),C4(饮食),C5(旅途)是五个准则，以下来比较各准则对目标的重要性

但是不难发现，上图存在成对比较不一致的情况：C1:C2=1:2;C1:C3=4:1所以按道理C2:C3=8:1，但是图示为7：1。注意：这里允许不一致，但要确定不一致的允许范围。称满足a_ij·a_jk=a_ik,i,j,k=1,2,...,n的正互反阵A称为一致阵,上图为不一致阵

1.层次单排序及其一致性检验

一致性检验是为了判断在什么程度下的不一致是可允许的范围内
定理：n阶一致阵的唯一非零特征根为n

定理：n阶正互反阵A的最大特征根\(\lambda\geq n\),当且仅当\(\lambda=n\)时A为一致阵

定义一致性指标：CI=\(\frac{\lambda-n}{n-1}\),CI=0，有完全的一致性，CI接近于0，有满意的一致性，CI越大，不一致越严重。为衡量CI的大小，引入随机一致性指标RI。方法为随机构造500个成对矩阵

\(RI=\frac{CI_1+CI_2+...+CI_{500}}{500}\)

一般当一致性比率\(CR=\frac{CI}{RI}<0.1\),认为A的不一致程度在被允许的范围内
例题1.1“选择旅游地”中准则层对目标层的权向量及一致性检验

\[ \left[ \matrix{ 1&1/2&4&3&3\\ 2&1&7&5&5\\ 1/4&1/7&1&1/2&1/3\\ 1/3&1/5&2&1&1\\ 1/3&1/5&3&1&1 } \right] \]

最大特征根\(\lambda=5.073\),权向量\(w=(0.263,0.475,0.055,0.090,0.110)^T\),一致性性指标\(CI=\frac{5.073-5}{5-1}=0.018\)随机一致性指标RI=1.12（查表）。一致性比率CR=0.018/1.12=0.016<0.1,通过一致性检验

2.正互反阵最大特征根和特征向量的简化计算

和法----取列向量的算数平均

\[ A=\left[ \matrix{ 1&2&6\\ 1/2&1&4\\ 1/6&1/4&1 } \right]\\ 列向量归一化,让每一列按比例缩小到列和等于1：1/(1+1/2+1/6)=0.6\\ \left[ \matrix{ 0.6&0.615&0.545\\ 0.3&0.308&0.364\\ 0.1&0.077&0.091 } \right]\\ 求行和归一化：每行加起来除以每行元素数\\ \left[ \matrix{ 0.587\\ 0.324\\ 0.089 } \right]=\omega\\ \]

\[ A\omega= \left[ \matrix{ 1.769\\ 0.974\\ 0.268 } \right]\\ A\omega=0.587*1+0.3234*2+0.089*6\\ A\omega=\lambda \omega\\ \lambda=\frac{1}{3}(1.769/0.587+0.974/0.324+0.268/0.089)=3.009 \]

3.层次总排序及其一次性检验

  • 计算某一层次所有因素对于最高层(总目标)相对重要性的权值，称为层次总排序
  • 这一过程是从最高层次到最低层次依次进行的

A层m个因素A_1,A_2,...,A_m对总目标Z的排序为：a_1,a_2,...，a_m;B层n个因素对上层A中因素为A_j的层次单排序为：b_1j,b_2j,...,b_nj(j=1,2,...,m);B层的层次总排序为：B_1=a_1*b_11+a_2*b_12+...+a_m*b_1m

则层次总排序的一致性比率为：

\[ CR=\frac{a_1CI_1+a_2CI_2+...+a_mCI_m}{a_1RI_i+a_2RI_2+...+a_mRI_m} \]

当CR<0.1满足

例题1.1记第2层(准则)对第一层(目标)的权向量为\(w^{(2)}=(0.263,0.475,0.055,0.090,0.110)^T\)同样求第三层(方案)对第二层每一元素(准则)的权向量:(准则层5件，方案层3件)

\[ 方案层对C_1(准则)的成对比较阵\\ B_1=\left[ \matrix{ 1&2&5\\ 1/2&1&5\\ 1/5&1/2&1 } \right]\\ 方案层对C_2(费用)的成对比较阵\\ B_2=\left[ \matrix{ 1&1/3&1/8\\ 3&1&1/3\\ 8&3&1 } \right]\\ ...\\ 方案层对C_5的成对比较阵\\ B_5=... \]

\[ 最大特征根\lambda_1=3.005,\lambda_2=3.002,...\\ 权向量\omega_1^{(3)}=(0.595,0.277,0.219)\\ \omega_2^{(3)}={0.082,0.236,0.682}\\ ... \]

方案p1对目标的组合权重为：\(0.595*0.263+0.082*0.475+0.055*0.429+0.090*0.633+0.110*0.166=0.300\)
方案层对目标的组合权向量为\((0.300,0.246,0.456)^T\)
例题1.2设某学校数学建模教练根据实际需要，拟从报名参赛的20名队员的基本条件的量化情况。请根据这些条件对20名队员进行综合评价，从中选出15名综合素质较高的优秀队员

这是一个半定性的题目(1)建立层次结构图：第一层为目标层，选拔优秀参赛队员(2)准则层，选拔优秀队员需要考虑的6个因素，依次为学科知识竞赛成绩，思维敏捷度，知识面宽广度，写作能力，计算机应用能力，协作能力(3)第三层为方案层：参选的20名队员

根据假设，构造准则层C对目标层O的两两比较矩阵 \[ \left[ \matrix{ 1&2&3&4&5&6\\ 1/2&1&2&3&4&5\\ 1/3&1/2&1&2&3&4\\ 1/4&1/3&1/2&1&2&3\\ 1/5&1/4&1/3&1/2&1&2\\ 1/6&1/5&1/4&1/3&1/2&1 } \right]\\ 和法计算最大特征向量和特征根为:\\ \lambda_{max}=6.1232\\ \omega^{(2)}=(0.3794,0.2488,0.1604,0.10240.0655,0.0434)^T\\ 一致性指标为:CI^{(2)}=0.0246,随机性指标RI^{(2)}=1.24\\ 一致性比率:CR^{(2)}=0.0198<0.1,通过一致性检验 \]

根据表1和模型假设，构造方案层P中20个队员对准则层C中各个因素C_k的两两比较

\[ B_k=(b_{ij}^{(k)})_{20×20},其中b_{ij}^{(k)}=\frac{r_i^{(k)}}{r_j^{(k)}},(ij=1,2,...,20,k=1,2,...,6) \]

显然，所有的B_k均为一致阵(一致阵的最大特征根=n)，于是B_k的最大特征根为：

\[ \lambda_{max}^{(k)}=20,CI_k=0,CR_k=0 \]

B_k的任意一列向量都是\(\lambda_{max}\)的特征向量，将其归一化得到方案层P对C_k的权重向量\(\omega_k^{(3)}\).于是，方案层对准则层的权重向量矩阵：

\[ W^{(3)}=[\omega_1^{(3)},\omega_2^{(3)},...,\omega_6^{(3)}]\\ 一致性比率为CR_k=0(k=1,2,...6),通过一致性检验 \]

方案层对目标层的组合权向量为： \[ \omega^{(3)}=W^{(3)}\omega^{(2)}=(0.00498,0.0474,0.0490,0.0513,\\0.0497,0.0517,0.0526,0.0504,\\0.0450,0.0464,0.0480,0.0523,\\0.0535,0.0511,0.0496,0.0505,\\0.05310.0500,0.0506,0.0481)^T\\ 组合一致性指标CI^{(3)}=0，组合一致性比率为：\\ CR^{(3)}=CR^{(2)}+\frac{CI^{(3)}}{RI^{(3)}}=0.0198<0.1 \]