数学规划模型|线性规划|整数规划

规划模型的概念

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

规划模型的数学描述

将一个优化问题用数学式子来描述，即求函数
$$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)$这个函数，在一组等式和一组不等式的约束下，来取最大值或最小值
x → 决策变量 f ( x ) → 目标函数 x ∈ 可行域

$$\begin{array}{} x \to 决策变量 \\ f(x) \to 目标函数 \\ x \in 可行域 \end{array}$$ x→决策变量f(x)→目标函数x∈可行域​

整理一下
一个规划问题的数学模型可表示为 m i n ( o r m a x ) u = f ( x ) x ∈ Ω s . t . h i ( x ) = 0 , i = 1 , 2 , 3 , … , m . g j ( x ) ≤ 0 ( g j ( x ) ≥ 0 ) , j = 1 , 2 , … , p .

$$\begin{array}{} 一个规划问题的数学模型可表示为 \\ min(or\quad max)u=f(x)\quad x\in \Omega \\ s.t.\quad 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}$$ 一个规划问题的数学模型可表示为min(ormax)u=f(x)x∈Ωs.t.hi​(x)=0,i=1,2,3,…,m.gj​(x)≤0(gj​(x)≥0),j=1,2,…,p.​

• $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$，均为线性函数，则称该模型为线性规划模型
m a x ( 或 m i n ) z = c 1 x 1 + c 2 x 2 + ⋯ + c n x n s . t . { a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n ( ≤ = ≥ ) b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n ( ≤ = ≥ ) b 2 … a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n ( ≤ = ≥ ) b m x j ≥ 0 ( j = 1 , 2 , … , n )

$$\begin{array}{} max(或min)z=c_{1}x_{1}+c_{2}x_{2}+\dots+c_{n}x_{n} \\ s.t.\quad \left\{\begin{matrix} a_{11}x_{1}+a_{12}x_{2}+\dots+a_{1n}x_{n}(\le=\ge)b_{1} \\ a_{21}x_{1}+a_{22}x_{2}+\dots+a_{2n}x_{n}(\le=\ge)b_{2} \\ \dots \\ a_{m1}x_{1}+a_{m2}x_{2}+\dots+a_{mn}x_{n}(\le=\ge)b_{m} \end{matrix}\right. \\ x_{j}\ge 0(j=1,2,\dots,n) \end{array}$$ max(或min)z=c1​x1​+c2​x2​+⋯+cn​xn​s.t.⎩ ⎨ ⎧​a11​x1​+a12​x2​+⋯+a1n​xn​(≤=≥)b1​a21​x1​+a22​x2​+⋯+a2n​xn​(≤=≥)b2​…am1​x1​+am2​x2​+⋯+amn​xn​(≤=≥)bm​​xj​≥0(j=1,2,…,n)​

• 把目标函数写成线性表达式
• $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$$

线性规划模型的求解

简单线性规划模型的求解

对于一般只有两个决策变量的简单线性规划模型，可以通过图解法进行求解
l 1 : x 1 + x 2 = 50 l 2 : 12 x 1 + 8 x 2 = 480 l 3 : 3 x 1 = 100 l 1 : x 1 = 0 , l 5 : x 2 = 0

$$\begin{array}{} 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}$$ l1​:x1​+x2​=50l2​:12x1​+8x2​=480l3​:3x1​=100l1​:x1​=0,l5​:x2​=0​

在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
1
2
3
4
5
6
7
8

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

加工奶制品求解

model:
max=72*x1+64*x2;
x1+x2<50;
12*x1+8*x2<480;
3*x1<100;
end
1
2
3
4
5
6

最优解是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
D E M : 需求量 R P : 正常生产的产量 O P : 加班生产的产量 I N V : 库存量

$$\begin{array}{} DEM:需求量 \\ RP:正常生产的产量 \\ OP:加班生产的产量 \\ INV:库存量 \end{array}$$ DEM:需求量RP:正常生产的产量OP:加班生产的产量INV:库存量​

• 目标函数
  $$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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

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

整数规划和0-1规划

整数规划问题的基本描述

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

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

整数规划的数学描述

m i n ( o r m a x ) u = f ( x ) x ∈ Ω s . t . h i ( x ) = 0 , i = 1 , 2 , 3 , … , m . g j ( x ) ≤ 0 ( g j ( x ) ≥ 0 ) , j = 1 , 2 , … , p . 其中决策变量 x 为整数，或者为 0 ， 1

$$\begin{array}{} min(or\quad max)u=f(x)\quad x\in \Omega \\ s.t.\quad 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}$$ min(ormax)u=f(x)x∈Ωs.t.hi​(x)=0,i=1,2,3,…,m.gj​(x)≤0(gj​(x)≥0),j=1,2,…,p.其中决策变量x为整数，或者为0，1​
在Lingo编程中，决策变量为整数一般用$@gin(x)$表示；而0-1决策变量用$@bin(x)$表示

建设计划问题

设A、B两种类型的基地各建设$x_1,x_2$个
m a x   z = 20 x 1 + 10 x 2 s . t . { 2000 x 1 + 5000 x 2 ≤ 13000 5 x 1 + 4 x 2 ≤ 24 x 1 ≥ 0 , x 2 ≥ 0 且为整数

$$\begin{array}{} max\ z=20x_{1}+10x_{2} \\ s.t. \left\{\begin{matrix} 2000x_{1}+5000x_{2}\le 13000 \\ 5x_{1}+4x_{2}\le 24 \\ x_{1}\ge 0,x_{2} \ge 0且为整数 \end{matrix}\right. \end{array}$$ max z=20x1​+10x2​s.t.⎩ ⎨ ⎧​2000x1​+5000x2​≤130005x1​+4x2​≤24x1​≥0,x2​≥0且为整数​​

人员安排问题

因为每个服务员的工作时间会跨过4个时段
为使服务部门服务员总数最少
设前五个时段安排的服务员各为$x_1,x_2,x_3,x_4,x_5$
m i n   z = x 1 + x 2 + x 3 + x 4 + x 5 s . t . { x 1 ≥ 8 x 1 + x 2 ≥ 10 x 1 + x 2 + x 3 ≥ 7 x 1 + x 2 + x 3 + x 4 ≥ 6 x 2 + x 3 + x 4 + x 5 ≥ 9 x 3 + x 4 + x 5 ≥ 12 x 4 + x 5 ≥ 5 x 5 ≥ 2 x j ≥ 0 , j = 1 , 2 , 3 , 4 , 5 且为整数

$$\begin{array}{} min\ z=x_{1}+x_{2}+x_{3}+x_{4}+x_{5} \\ \\ s.t. \left\{\begin{matrix} 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{matrix}\right. \end{array}$$ min z=x1​+x2​+x3​+x4​+x5​s.t.⎩ ⎨ ⎧​x1​≥8x1​+x2​≥10x1​+x2​+x3​≥7x1​+x2​+x3​+x4​≥6x2​+x3​+x4​+x5​≥9x3​+x4​+x5​≥12x4​+x5​≥5x5​≥2xj​≥0,j=1,2,3,4,5且为整数​​

混合泳接力队的选拔

总共有120种组合方式
设甲是否蝶泳为$x_{11}$，是否仰泳为$x_{12}$，是否蛙泳为$x_{13}$，是否自由泳为$x_{14}$
以此类推
x i j = { 0 1 x_{ij}=\left\{

$$\begin{matrix} 0 \\ 1 \end{matrix}$$ \right. xij​={01​取1表示，第i个人。去游第j种泳姿，取0表示第i个人，不游第j种泳姿

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

$$\begin{array}{} 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}$$ x11​+x12​+x13​+x14​≤1x21​+x22​+x23​+x24​≤1x31​+x32​+x33​+x34​≤1x41​+x42​+x43​+x44​≤1x51​+x52​+x53​+x54​≤1​
对泳姿的约束：每个项目必须有一个运动员参加
$$\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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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(...)
1
2
3
4
5

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

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

模型1
M i n   z = c X s . t .   A X ≤ b

$$\begin{array}{} Min\ z=cX \\ s.t.\ AX\le b \end{array}$$ Min z=cXs.t. AX≤b​
目标和约束都是矩阵形式
只有不等式约束
$$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)
1
2

x0表示初始点

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

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

例子

m a x   z = 0.4 x 1 + 0.28 x 2 + 0.32 x 3 + 0.72 x 4 + 0.64 x 5 + 0.6 x 6 s . t . { 0.01 x 1 + 0.01 x 2 + 0.01 x 3 + 0.03 x 4 + 0.03 x 5 + 0.03 x 6 ≤ 850 0.02 x 1 + 0.05 x 4 ≤ 700 0.02 x 2 + 0.05 x 5 ≤ 100 0.03 x 3 + 0.08 x 6 ≤ 900 x j ≥ 0 j = 1 , 2 , … , 6

$$\begin{array}{} max\ z=0.4x_{1}+0.28x_{2}+0.32x_{3}+0.72x_{4}+0.64x_{5}+0.6x_{6} \\ s.t. \left\{\begin{matrix} 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 0\quad j=1,2,\dots,6 \end{matrix}\right. \end{array}$$ max z=0.4x1​+0.28x2​+0.32x3​+0.72x4​+0.64x5​+0.6x6​s.t.⎩ ⎨ ⎧​0.01x1​+0.01x2​+0.01x3​+0.03x4​+0.03x5​+0.03x6​≤8500.02x1​+0.05x4​≤7000.02x2​+0.05x5​≤1000.03x3​+0.08x6​≤900xj​≥0j=1,2,…,6​​

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)
1
2
3
4
5
6
7
8
9

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

任务分配问题

m i n   z = ( 13 9 10 11 12 8 ) X s . t .   ( 0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3 ) X ≤ ( 800 900 ) ( 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 ) X = ( 400 600 500 ) , X = ( x 1 x 2 x 3 x 4 x 5 x 6 ) ≥ 0

$$\begin{array}{} min\ z=\begin{pmatrix} 13&9&10&11&12&8 \end{pmatrix} X\\ s.t.\ \begin{pmatrix} 0.4 & 1.1 &1&0&0&0 \\ 0&0&0&0.5&1.2&1.3 \\ \end{pmatrix} X\le\begin{pmatrix} 800 \\ 900 \end{pmatrix} \\ \begin{pmatrix} 1&0&0&1&0&0 \\ 0&1&0&0&1&0 \\ 0&0&1&0&0&1 \end{pmatrix} X=\begin{pmatrix} 400 \\ 600 \\ 500 \end{pmatrix}, X=\begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \\ x_{6} \end{pmatrix}\ge 0 \end{array}$$ min z=(13​9​10​11​12​8​)Xs.t. (0.40​1.10​10​00.5​01.2​01.3​)X≤(800900​) ​100​010​001​100​010​001​ ​X= ​400600500​ ​,X= ​x1​x2​x3​x4​x5​x6​​ ​≥0​

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)
1
2
3
4
5
6
7
8

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(...)
1
2
3
4
5

intcon，用来指定整数变量

Matlab优化工具箱简介

输入

输出