在有限资源（人、财、物、时间）下取得最佳经济效益--线性规划（上）

1 前言
2 第一部分建模与求解实践
3 第二部分基础概念回顾
4 第三部分线性规划模型一般形式
5 第四部分线性规划建模工具
- 5.1 $scipy.optimize.linprog$ 参数说明

前言¶

线性规划在经营管理中，经常用来解决有限资源（人、财、物、时间）的合理分配问题。

第一部分建模与求解实践¶

建立模型步骤¶

设未知数 $\Longrightarrow$ 问题的未知数是什么？
目标函数 $\Longrightarrow$ 以什么准则进行决策？
约束方程 $\Longrightarrow$ 约束条件是什么？

案例（1）产能平衡问题¶

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

未知变量 $假设生产甲机床 x_1 台，乙机床 x_2 台$

目标函数
$$max \ z=4x_1+3x_2$$

约束条件
$$ s.t.\left\{ \begin{aligned} 2x_1+x_2 \leq 10 \\ x_1+x_2 \leq 8 \\ x_2 \leq 7 \\ x_1,\ x_2\geq 0 \end{aligned} \right. $$

from scipy import optimize as op
import numpy as np
c=np.array([4,3])
A_ub=np.array([[2,1], [1,1], [0, 1]])
B_ub=np.array([10, 8, 7])
x1=(0,8)
x2=(0,7)
res=op.linprog(
      -c     # 注意这个负号，表示求负号的极小值，也即求极大值。（因为目标函数中是Max）
    , A_ub   # 如果不等式为大于等于，则要在A_ub 赋值时添加负号将其转化为小于等于
    , B_ub
    , bounds=(x1, x2)
)
print('最大总利润为：',-res.fun*1000,'元')
print('生产甲机床',res.x[0],'台', '\n生产乙机床',res.x[1],'台')

最大总利润为： 26000.0 元
生产甲机床 2.0 台 
生产乙机床 6.0 台

案例（2）产品组合问题¶

某厂生产甲、乙两种产品，使用A、B两种原料
单位甲产品消耗A、B为1、2T
单位乙产品消耗A、B为2、1T
每日可供利用的原料数量为，A：6T/日，B：8T/日
产品售价，A：3千元/T，B：2千元/T
其他市场信息：
1. 乙产品的需求量至多 5 T/日
2. 乙产品的需求量比甲产品的需求量至多大 1 T/日
求该厂产值最大的生产方案

未知变量
设甲、乙产品的产量为 $x_1$, $x_2$ T/日

目标函数
设 $Z$ 为产值，有 $Z=3x_1+2x_2$，即：$$max \ Z=3x_1+2x_2$$

约束条件
约束条件包括资源限制、市场限制、非负限制 $$ 资源限制\ \ \left\{ \begin{aligned} x_1+2x_2 \leq 6 \\ 2x_1+x_2 \leq 8 \end{aligned} \right. $$

$$ 市场限制\ \ \left\{ \begin{aligned} x_2 \leq 5 \\ -x_1+x_2 \leq 1 \end{aligned} \right. $$

$$ 非负限制\ \ \left\{ \begin{aligned} x_1，\ x_2 \geq 0 \end{aligned} \right. $$

from scipy import optimize as op
import numpy as np
c=np.array([3,2])
A_ub=np.array([[1,2], [2,1], [0, 1], [-1, 1]])
B_ub=np.array([6, 8, 5, 1])
x1=(0,3)  # 甲市场需求小于乙不超过1T，故与乙同为3T，而非生产资源限制的4T
x2=(0,3)  # A原料最大日供货量6T，单位乙产品需要消耗2T的A，故最大为3，而非市场容量的5T
res=op.linprog(-c, A_ub, B_ub, bounds=(x1, x2))
print('每日最大产值为：',-res.fun*1000,'元')
print('每日生产甲产品',res.x[0],'T', '\n每日生产乙产品',res.x[1],'T')

每日最大产值为： 12000.0 元
每日生产甲产品 3.0 T 
每日生产乙产品 1.5 T

案例（3）车辆调度问题¶

某城市在一昼夜间，室内交通需要车辆数如下：

序号	时段	车辆数
1	00-04	4
2	04-08	8
3	08-12	10
4	12-16	7
5	16-20	12
6	20-24	4

对车辆的需求在昼夜间是变化的
车辆的工作制度是一天连续工作8小时
派车时间在各时间间隔的端点
一旦派出，就连续工作8小时
求：保证需要的最小车辆数

未知变量
设各时间间隔所派出的车辆数为 $x_j,\ \ j=1, 2, ..., 6$

目标函数
$$min \ Z = x_1+x_2+x_3+x_4+x_5+x_6$$

约束条件
$$ s.t.\left\{ \begin{aligned} x_1+x_2 \geq \ \ 8 \\ x_2+x_3 \geq 10 \\ x_3+x_4 \geq \ \ 7 \\ x_4+x_5 \geq 12 \\ x_5+x_6 \geq \ \ 4 \\ x_6+x_1 \geq \ \ 4 \\ x_1,x_2,x_3,x_4,x_5,x_6 \geq \ \ 0 \end{aligned} \right. $$

from scipy import optimize as op
import numpy as np
c=np.array([1,1,1,1,1,1])
A_ub=np.array([[-1,-1,0,0,0,0], [0,-1,-1,0,0,0], [0,0,-1,-1,0,0], [0,0,0,-1,-1,0], [0,0,0,0,-1,-1], [-1,0,0,0,0,-1]])
B_ub=np.array([-8,-10,-7,-12,-4,-4])
x1=(0,12)  
x2=(0,12)  
x3=(0,12)  
x4=(0,12)  
x5=(0,12)  
x6=(0,12)  
res=op.linprog(c, A_ub, B_ub, bounds=(x1, x2, x3, x4, x5, x6))
print('每日最小车辆数：',res.fun,'辆')
print('00-04车辆数',res.x[0],'辆', '\n04-08车辆数',res.x[1],'辆', '\n08-12车辆数',res.x[2],'辆', '\n12-16车辆数',res.x[3],'辆', '\n16-20车辆数',res.x[4],'辆', '\n20-24车辆数',res.x[5],'辆')

每日最小车辆数： 26.0 辆
00-04车辆数 4.0 辆 
04-08车辆数 10.0 辆 
08-12车辆数 0.0 辆 
12-16车辆数 8.0 辆 
16-20车辆数 4.0 辆 
20-24车辆数 0.0 辆

案例（4）最小运费问题¶

$某牛奶场生产的牛奶有\ 3\ 个产地和\ 5\ 个销地，$
$各产地产量为\ 10,\ 8,\ 12$
$各销地需求量为\ 5,\ 5,\ 6,\ 6,\ 7。$
$该商品由\ i\ 产地运到\ j\ 销地的单位运价为\ c_{ij}\ 如下(单位：万元)：$

-	$S_1$	$S_2$	$S_3$	$S_4$	$S_5$
$P_1$	0.2	0.7	0.9	0.3	0.6
$P_2$	0.3	0.6	0.8	0.6	0.6
$P_3$	0.4	0.5	0.6	0.4	0.6

$求：使总运费最省的运输路线？$

未知变量
设各产地到各销地的运输量为 $x_{11},x_{12},x_{13},x_{14},x_{15},x_{21},x_{22},x_{23},x_{24},x_{25},x_{31},x_{32},x_{33},x_{34},x_{35}$

目标函数
$$ min \ Z = 0.2x_{11}+0.7x_{12}+0.9x_{13}+0.3x_{14}+0.6x_{15} +0.3x_{21}+0.6x_{22}+0.8x_{23}+0.6x_{24}+0.6x_{25} +0.4x_{31}+0.5x_{32}+0.6x_{33}+0.4x_{34}+0.6x_{35} $$

约束条件
$$ s.t.\left\{ \begin{aligned} x_{11}+x_{12}+x_{13}+x_{14}+x_{15} \leq 10 \\ x_{21}+x_{22}+x_{23}+x_{24}+x_{25} \leq \ \ 8 \\ x_{31}+x_{32}+x_{33}+x_{34}+x_{35} \leq 12 \\ x_{11}+x_{21}+x_{31} \geq \ \ 5 \\ x_{12}+x_{22}+x_{32} \geq \ \ 5 \\ x_{13}+x_{23}+x_{33} \geq \ \ 6 \\ x_{14}+x_{24}+x_{34} \geq \ \ 6 \\ x_{15}+x_{25}+x_{35} \geq \ \ 7 \\ x_{11},x_{12},x_{13},x_{14},x_{15},x_{21},x_{22},x_{23},x_{24},x_{25},x_{31},x_{32},x_{33},x_{34},x_{35} \geq \ \ 0 \end{aligned} \right. $$

from scipy import optimize as op
import numpy as np
c=np.array([0.2,0.7,0.9,0.3,0.6,0.3,0.6,0.8,0.6,0.6,0.4,0.5,0.6,0.4,0.6])
A_ub=np.array([
    [1,1,1,1,1,0,0,0,0,0,0,0,0,0,0], 
    [0,0,0,0,0,1,1,1,1,1,0,0,0,0,0], 
    [0,0,0,0,0,0,0,0,0,0,1,1,1,1,1], 
    [-1,0,0,0,0,-1,0,0,0,0,-1,0,0,0,0], 
    [0,-1,0,0,0,0,-1,0,0,0,0,-1,0,0,0], 
    [0,0,-1,0,0,0,0,-1,0,0,0,0,-1,0,0], 
    [0,0,0,-1,0,0,0,0,-1,0,0,0,0,-1,0], 
    [0,0,0,0,-1,0,0,0,0,-1,0,0,0,0,-1], 
])
B_ub=np.array([10,8,12,-5,-5,-6,-6,-7])
x11=(0,10)  
x12=(0,10)  
x13=(0,10)  
x14=(0,10)  
x15=(0,10)  
x21=(0,8)  
x22=(0,8)  
x23=(0,8)  
x24=(0,8)  
x25=(0,8)  
x31=(0,12)
x32=(0,12)
x33=(0,12)
x34=(0,12)
x35=(0,12)
res=op.linprog(c, A_ub, B_ub, bounds=(x11,x12,x13,x14,x15,x21,x22,x23,x24,x25,x31,x32,x32,x34,x35))
print('最小总成本：',res.fun*10000,'元')
print('X11:',res.x[0],'|', 'X12:',res.x[1],'|', 'X13:',res.x[2],'|', 'X14:',res.x[3],'|', 'X15:',res.x[4],'|', 
      '\nX21:',res.x[5],'|','X22:',res.x[6],'|','X23:',res.x[7],'|','X24:',res.x[8],'|','X25:',res.x[9],'|',
      '\nX31:',res.x[10],'|','X32:',res.x[11],'|','X33:',res.x[12],'|','X34:',res.x[13],'|','X35:',res.x[14],'|'
     )

最小总成本： 131999.99999999997 元
X11: 4.0 | X12: 0.0 | X13: 0.0 | X14: 6.0 | X15: 0.0 | 
X21: 1.0 | X22: 0.0 | X23: 0.0 | X24: 0.0 | X25: 7.0 | 
X31: 0.0 | X32: 5.0 | X33: 6.0 | X34: 0.0 | X35: 0.0 |

第二部分基础概念回顾¶

矩阵定义¶

数学上，一个m×n的矩阵是一个由m行n列元素排列成的矩形阵列

$$ \begin{bmatrix} 1402 & 191 \\ 1321 & 821 \\ 949 & 1437 \\ 147 & 1448 \end{bmatrix} \tag{1} $$

$$ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ \end{bmatrix} \tag{2} $$

使用 $A_{ij}$ 来获取矩阵中第 $i$ 行第 $j$ 列的数据。

如，对于矩阵(1)： $$ A_{11}=1402 \\ A_{12}=191 \\ A_{32}=1437 \\ A_{41}=147 $$

向量定义¶

向量就是 n 行 1 列的特殊矩阵

$$ y = \begin{bmatrix} 460 \\ 232 \\ 315 \\ 178 \end{bmatrix} \tag{3} $$

由于向量仅仅只有 1 列，那么通过一个变量 i 来指定获取第 i 行的数据，就很容易理解。

$$ y_i=i^{th} element $$

$$ y_1=460 \\ y_2=232 \\ y_3=315 $$

矩阵运算¶

矩阵加法¶

矩阵的加法，要求所有的矩阵的列和行都是一样的
矩阵的加法，就是将对应位置的数值相加即可

$$ \begin{bmatrix} 1 & 0 \\ 2 & 5 \\ 3 & 1 \\ \end{bmatrix}+ \begin{bmatrix} 4 & 0.5 \\ 2 & 5 \\ 1 & 1 \\ \end{bmatrix}= \begin{bmatrix} 5 & 0.5 \\ 4 & 10 \\ 4 & 2 \\ \end{bmatrix} $$

矩阵的乘法¶

矩阵的乘法，就是使用数字和矩阵相乘，矩阵的乘法对矩阵没有要求
运算法则就是将乘数与矩阵中每一个数字相乘即可

$$ 3 \times \begin{bmatrix} 4 & 0.5 \\ 2 & 5 \\ 1 & 1 \\ \end{bmatrix}= \begin{bmatrix} 12 & 1.5 \\ 6 & 15 \\ 3 & 6 \\ \end{bmatrix} $$

$$ \dfrac{1}{4} \times \begin{bmatrix} 4 & 0.5 \\ 2 & 5 \\ 1 & 6 \end{bmatrix}= \begin{bmatrix} 1 & \dfrac{1}{8} \\ \dfrac{1}{2} & \dfrac{5}{4} \\ \dfrac{1}{4} & \dfrac{3}{2} \end{bmatrix} $$

矩阵向量间的运算¶

一个 m 行 n 列的矩阵和 n 行向量相乘，最后得到就是一个 m 行的向量
$$A \times x = y$$ 运算法则是矩阵中每行的（n个）数值与向量的（n个）数值相乘后之和

$$ \begin{bmatrix} 1 & 0 & 7 & 1 \\ 2 & 5 & 9 & 2 \end{bmatrix} \times \begin{bmatrix} 2 \\ 3 \\ 1 \\ 4 \\ \end{bmatrix}= \begin{bmatrix} 2 + 0 + 7 + 4 \\ 4 + 15 + 9 + 8 \\ \end{bmatrix}= \begin{bmatrix} 13 \\ 36 \\ \end{bmatrix} $$

矩阵间的运算¶

一个 m 行 n 列的矩阵与一个 n 行 q 列的矩阵相乘
最后得到的就是一个 m 行 q 列的矩阵 $$A \times B = C$$

$$ \begin{bmatrix} 1 & 0 & 7 \\ 2 & 5 & 9 \\ \end{bmatrix} \times \begin{bmatrix} 2 & 6 \\ 5 & 9 \\ 3 & 7 \\ \end{bmatrix}= \begin{bmatrix} 1\times2 + 0\times5 + 7\times3 & 1\times6 + 0\times9 + 7\times7 \\ 2\times2 + 5\times5 + 9\times3 & 2\times6 + 5\times9 + 9\times7 \\ \end{bmatrix}= \begin{bmatrix} 2 + 0 + 21 & 6 + 0 + 49 \\ 4 + 25 + 27 & 12 + 45 + 63 \\ \end{bmatrix}= \begin{bmatrix} 23 & 55 \\ 56 & 120 \\ \end{bmatrix} $$

矩阵乘法的性质¶

矩阵乘法不满足交换律¶

$$A \times B \neq B \times A$$

$$ \begin{bmatrix} 1 & 1 \\ 0 & 0 \\ \end{bmatrix} \times \begin{bmatrix} 0 & 0 \\ 2 & 0 \\ \end{bmatrix}= \begin{bmatrix} 1\times0+1\times2 & 1\times0+1\times0 \\ 0\times0+0\times2 & 0\times0+0\times0 \\ \end{bmatrix}= \begin{bmatrix} 2 & 0 \\ 0 & 0 \\ \end{bmatrix} $$

$$ \begin{bmatrix} 0 & 0 \\ 2 & 0 \\ \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 0 & 0 \\ \end{bmatrix}= \begin{bmatrix} 0\times1+0\times0 & 0\times1+0\times0 \\ 2\times1+0\times0 & 2\times1+0\times0 \\ \end{bmatrix}= \begin{bmatrix} 0 & 0 \\ 2 & 2 \\ \end{bmatrix} $$

矩阵乘法满足结合律¶

$$ A \times B \times C =(A \times B) \times C =A \times (B \times C) $$

单位矩阵¶

$n$ 阶单位矩阵，是一个 $n\times n$ 的方形矩阵
其主对角线元素为 1，其余元素为 0
单位矩阵以 $I_n$ 表示。在某些情况下，单位矩阵可以简写为 $I$
如果 $I$ 为单位矩阵，则有 $I \times A=A \times I$

$$ I_4= \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} $$

矩阵的逆¶

$矩阵的逆，对于一个 m 行 n 列的矩阵 A，$
$如果存在A^{-1}，满足A \times A^{-1} = I （I 是单位矩阵），$
$则表示A^{-1}是A的逆。$

$$ \begin{bmatrix} 3 & 4 \\ 2 & 16 \end{bmatrix} \times \begin{bmatrix} 0.4 & -0.1 \\ -0.05 & 0.075 \\ \end{bmatrix}= \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix}= I_2 $$

不是所有的矩阵都存在逆矩阵
例如，如果一个矩阵中所有的元素全为0，则不存在逆矩阵
这样的矩阵叫做孤立矩阵

矩阵的转置¶

$设 A 为 m 行 n 列矩阵，第 i 行 j 列的元素是 a_{(i,j)}，即：A = a_{(i,j)}。$
$定义 A 的转置为这样一个 n 行 m 列矩阵 B $
$满足 B = a_{(j,i)} 即 b_{(i,j)} = a_{(j,i)} $
$B的第 i 行第 j 列元素是 A 的第 j 行第 i 列元素$

$$ A= \begin{bmatrix} 1 & 2 & 0 \\ 3 & 5 & 9 \\ \end{bmatrix} $$

$$ B=A^T= \begin{bmatrix} 1 & 3 \\ 2 & 5 \\ 0 & 9 \\ \end{bmatrix} $$

转置矩阵其他性质¶

$$ (A \pm B)^T=A^T \pm B^T \\ (A \times B)^T=B^T \times A^T \\ (A^T)^T=A \\ (KA)^T=KA^T \\ $$

第三部分线性规划模型一般形式¶

线性规划，就是有一个不等式组（变量越多可以解决的问题越复杂，在金融投资领域会遇到变量达2000多个的情况）作为“约束条件”，然后建立一个目标函数，并对目标函数求极值。

线性规划问题的模型三要素¶

可以用一组决策变量（$x_1, x_2,..., x_n$）表示某一方案
可以用一组线性等式或线性不等式表示约束条件
可以用决策变量的线性函数（目标函数）来表示目标：最大值或最小值

目标函数¶

$$max(min) \ z=c_1x_1+c_2x_2+ \dots +c_nx_n$$

约束条件¶

$$ subject \ to \ (s.t.)\left\{ \begin{aligned} a_{11}x_1+a_{12}x_2+ \dots +a_{1n}x_n \leq(=, \geq)\ b_1 \\ a_{21}x_1+a_{22}x_2+ \dots +a_{2n}x_n \leq(=, \geq)\ b_2 \\ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \ \\ a_{m1}x_1+a_{m2}x_2+ \dots +a_{mn}x_n \leq(=, \geq)\ b_m \\ x_1,\ x_2,\ \dots \ x_n\ \geq\ 0 \end{aligned} \right. $$ $ n: 变量个数 \\ m: 约束行数 \\ n+m：线性规划问题的规模 \\ c_j：价值系数 \\ b_i：右端项 \\ a_{ij}：技术系数 $

任务
在满足约束条件的所有可行解（$x_1,\ x_2,\ ...,\ x_n\ $）中，
找出使目标函数达到极值 $z$ 的决策变量值（$x_1^*,\ x_2^*,\ ...,\ x_n^*\ $），即最优解

和式模型¶

$$max\ Z(x)=\sum_{j=1}^n c_jx_j$$ $$ s.t.\ \ \left\{ \begin{aligned} \sum_{j=1}^n a_{ij}x_j \leq b_i \ \ (i=1,\ \dots , \ m) \\ x_{ij} \geq 0 \ \ (j=1,\ \dots , \ n) \\ \end{aligned} \right. $$

向量式模型¶

$$max\ Z(x)=CX$$ $$ s.t.\ \ \left\{ \begin{aligned} \sum_{j=1}^n P_jx_j \leq b \\ X \geq 0 \end{aligned} \right. $$

$$ C=(c_1,\ c_2,\ \dots ,\ c_n ) \\ X=(x_1,\ x_2, \dots ,\ x_n)^T $$

$$ P_j= \begin{bmatrix} a_{1j} \\ a_{2j} \\ \vdots \\ a_{mj} \\ \end{bmatrix} \ \ b= \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \\ \end{bmatrix} \ \ 0= \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0_n \\ \end{bmatrix} $$

矩阵式模型¶

$$max\ Z(x)=CX$$ $$ s.t.\ \ \left\{ \begin{aligned} AX \leq b \\ X \geq 0 \end{aligned} \right. $$

$$ A= \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \ \ \ \ \ \ \vdots \ \dots \ \ \\ a_{m1} & a_{m2} & \dots & a_{mn} \end{bmatrix} $$

$$ C=(c_1,\ c_2,\ \dots,\ c_n) \\ X=(x_1,\ x_2,\ \dots,\ x_n)^T \\ b=(b_1,\ b_2,\ \dots,\ b_m)^T \\ $$

第四部分线性规划建模工具¶

$scipy.optimize.linprog$ 参数说明¶

$scipy.optimize.linprog$ $( c ,\ A_{ub}=None ,\ b_{ub}=None ,\ A_{eq}=None ,\ b_{eq}=None ,\ bounds=None ,\ method='simplex' ,\ callback=None ,\ options=None )$

$c$ ：求最大值的函数的系数数组
$A_{ub}$ ：不等式未知量的系数矩阵
$B_{ub}$ ：不等式的右边
$A_{eq}$ ：其中等式的未知量系数矩阵
$B_{eq}$ ：等式右边
$bounds$ ：每个未知量的范围

这个模块只能找到线性规划的最小值，因此，如果约束条件的不等式（变量除外）中含有“大于等于”的需要修改为“小于等于”。