LinearProgramming-1

前言

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

第一部分 建模与求解实践

建立模型步骤

  1. 设未知数 $\Longrightarrow$ 问题的未知数是什么?
  2. 目标函数 $\Longrightarrow$ 以什么准则进行决策?
  3. 约束方程 $\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. $$

In [39]:
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. $$

In [40]:
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. $$

In [41]:
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. $$

In [42]:
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多个的情况)作为“约束条件”,然后建立一个目标函数,并对目标函数求极值。

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

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

目标函数

$$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$ :每个未知量的范围

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

◎ 欢迎参与讨论,请在这里发表您的看法、交流您的观点。