数学建模-线性规划

问题描述

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

数学建模

设该厂生产$x_1$台甲机床，生产$x_2$台乙机床，获得总利润$z$，

• 生产甲机床需要使用A机器$2x_1$小时，生产乙机床需要使用A机器$x_2$小时，每天A机器使用时长不得超过10小时，故得到约束条件$2x_1+x_2 \leq 10$
• 生产甲机床需要使用B机器$x_1$小时，生产乙机床需要使用B机器$x_2$小时，每天B机器使用时长不得超过8小时，故得到约束条件$x_1+x_2 \leq 8$
• 生产甲机床不使用C机器，生产乙机床需要使用C机器$x_2$小时，每天C机器使用时长不得超过7小时，故得到约束条件$x_2 \leq 7$
• 生产的机床变量为非负数，即$x_1,x_2 \geq 0$

则导出如下数学模型

$max \space z = 4000x_1+3000x_2 \\ s.t.=\left\{\begin{array}{l} 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.$

模型求解

Matlab中求解

Matlab中规定线性规划的标准形式为

$min \space f^T \cdot x \\ s.t.=\left\{\begin{array}{l} A \cdot x \leq b \\ Aeq \cdot x = beq \\ lb \leq x \leq ub \\ \end{array}\right.$

其中，$f,x,beq,lb,ub$均为列向量，$A,Aeq$为矩阵

调用形式

[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)

输入变量

• $f$为目标函数的系数向量
• A为不等式约束的左侧系数矩阵
• b为不等式约束的右侧常数向量
• Aeq为等式约束的系数矩阵
• beq为等式约束右侧的常数向量
• lb为决策变量下界向量
• ub为决策变量上界向量

输出变量

• x为最优解向量
• fval为目标函数的最优值

具体实例

将原题目转化为

$\begin{array}{l} min \space \begin{pmatrix} -4000\\-3000 \end{pmatrix} ^T \cdot \begin{pmatrix} x_1 \\ x_2 \\ \end{pmatrix} \\ s.t.=\left\{\begin{array}{l} \begin{pmatrix} 2 & 1 \\ 1 & 1 \\ 0 & 1 \\ \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ \end{pmatrix} \leq \begin{pmatrix} 10 \\ 8 \\ 7 \\ \end{pmatrix} \\ \begin{pmatrix} 0 \\ 0 \\ \end{pmatrix} \leq \begin{pmatrix} x_1 \\ x_2 \\ \end{pmatrix} \end{array}\right. \end{array}$

编写程序如下

% 目标函数系数列向量
f = [-4000;
     -3000];

% 不等式约束系数矩阵
A = [2,1;
     1,1;
     0,1];

% 不等式约束常数列向量
b = [10;
     8;
     7];
 
% 目标解约束下界
lb = [0;
      0];

% 若不存在对应约束，则使用[]填充对应参数
[x,fval] = linprog(f,A,b,[],[],lb,[])

得到输出如下，其中，x为最优解，fval为目标函数的最小值

Optimal solution found.


x =

    2.0000
    6.0000


fval =

      -26000

PS: 注意这里的fval并不是起初建模时的最大值，而是化为标准型后的最小值，故需要取fval的绝对值得到原目标函数的最大值。

Python求解

Python下使用scipy包中的linprog函数，其传参与Matlab中的标准型相同，代码如下，

from scipy.optimize import linprog

# 目标函数系数列向量
f = [-4000,-3000]

# 不等式约束系数矩阵
A = [[2,1],
     [1,1],
     [0,1]]

# 不等式约束常数列向量
b = [10,8,7]
 
# 目标解约束下界
bounds = [
    (0, None), # x1的取值为[0,+∞]
    (0, None)  # x2的取值为[0,+∞]
]

linprog(c=f,
        A_ub=A,
        b_ub=b,
        bounds=bounds)

输出结果

    con: array([], dtype=float64)
    fun: -25999.99999996891
message: 'Optimization terminated successfully.'
    nit: 6
  slack: array([1.16955334e-11, 9.69713199e-12, 1.00000000e+00])
 status: 0
success: True
      x: array([2., 6.])

模型转化

对于一些非线性的目标函数，可通过某些手段将其转化为线性规划问题，

$$