问题描述

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

数学建模

设该厂生产x1x_1台甲机床,生产x2x_2台乙机床,获得总利润zz

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

则导出如下数学模型

max z=4000x1+3000x2s.t.={2x1+x210x1+x28x27x1,x20max \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 fTxs.t.={AxbAeqx=beqlbxubmin \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,ubf,x,beq,lb,ub均为列向量,A,AeqA,Aeq为矩阵

调用形式
1
[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)
输入变量
  • ff为目标函数的系数向量
  • A为不等式约束的左侧系数矩阵
  • b为不等式约束的右侧常数向量
  • Aeq为等式约束的系数矩阵
  • beq为等式约束右侧的常数向量
  • lb为决策变量下界向量
  • ub为决策变量上界向量
输出变量
  • x为最优解向量
  • fval为目标函数的最优值
具体实例

将原题目转化为

min (40003000)T(x1x2)s.t.={(211101)(x1x2)(1087)(00)(x1x2)\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}

编写程序如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
% 目标函数系数列向量
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为目标函数的最小值

1
2
3
4
5
6
7
8
9
10
11
12
Optimal solution found.


x =

2.0000
6.0000


fval =

-26000

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

Python求解

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)
输出结果
1
2
3
4
5
6
7
8
    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.])

模型转化

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

可以转化为线性规划的问题