【公式求解】线性规划(3)

SciPy的scipy.optimize模块提供了一个求解线性规划的函数linprog。这个函数集中了求解线性规划的常用算法,如单纯形法和内点法,会根据问题的规模或用户的指定选择算法进行求解。

例:求解线性规划问题
$ min \quad z = -x_{1}+4x_{2} $
$ s.t. \begin{cases}
-3x_{1}+x_{2} \leq 6 \\
x_{1}+2x_{2} \leq 4 \\
x_{2} \geq -3
\end{cases}
$

1
2
3
4
5
6
7
8
9
10
11
from scipy.optimize import linprog

c = [-1,4]
A = [[-3,1], [1,2]]
b = [6,4]
bounds = ((None,None),(-3,None)) # x1,x2

res = linprog(c,A,b,None,None,bounds)

print('目标函数的最小值:', res.fun)
print('最优解为:', res.x)

例:求解线性规划问题
$ max \quad z = x_{1}-2x_{2}-3x_{3} $
$ s.t. \begin{cases}
-2x_{1}+x_{2}+x_{3} \leq 9 \\
-3x_{1}+x_{2}+2x_{3} \geq 4 \\
4x_{1}-2x_{2}-x_{3} = -6 \\
x_{1} >= -10, x_{2} >= 0
\end{cases}
$
首先化为SciPy中标准形(max变min,符号取反;$\geq $变$\leq $,符号取反)
$ min \quad w = -x_{1}+2x_{2}+3x_{3} $
$ s.t. \begin{cases}
-2x_{1}+x_{2}+x_{3} \leq 9 \\
3x_{1}-x_{2}-2x_{3} \leq -4\\
4x_{1}-2x_{2}-x_{3} = -6 \\
x_{1} >= -10, x_{2} >= 0
\end{cases}
$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from scipy.optimize import linprog

c = [-1,2,3]
A = [[-2,1,1], [3,-1,-2]]
b = [[9],[-4]]

# 等式部分
Aeq = [[4,-2,-1]]
beq = [-6]

# 决策变量限制条件
LB = [-10,0,None]
UB = [None,None,None]
bounds = tuple(zip(LB,UB)) # x1,x2

res = linprog(c,A,b,Aeq,beq,bounds)

print('目标函数的最小值:', res.fun)
print('最优解为:', res.x)

例:加工一种食用油需要精炼若干种原料油并把它们混合起来。原料油的来源有两类共5种:植物油VEG1、植物油VEG2、非植物油OIL1、非植物油OIL2、非植物油OIL3。购买每种原料油的价格(英磅/吨)如下表所示,最终产品以150英磅/吨的价格出售。

原料油 VEG1 VEG2 OIL1 OIL2 OIL3
价格 110 120 130 110 115

植物油和非植物油需要在不同的生产线上进行精炼,每月能够精炼的植物油不超过200吨,非植物油不超过250吨。在精炼过程中重量没有损失,精炼费用可忽略不计。最终产品要符合硬度的技术条件,按照硬度的计量单位,它必须为3~6.假定硬度的混合是线性的,而材料的硬度如下表所示。

原料油 VEG1 VEG2 OIL1 OIL2 OIL3
硬度值 8.8 6.1 2.0 4.2 5.0

为使利润最大化,应该怎样指定它的月采购和加工计划。

解:设$x_{1},x_{2},…,x_{n}$为每月需要采购的5种原料油吨数,$x_{6}$为每月加工的成品油吨数。
(1)目标函数是使净利润
$z = -110x_{1}-120x_{2}-130x_{3}-110x_{4}-115x_{5}+150x_{6}$
达到最大值
(2)约束条件分为如下4类
i、精炼能力限制
植物油的精炼能力限制:$x_{1}+x_{2} \leq 200 $
非植物油的精炼能力限制:$x_{3}+x_{4}+x_{5} \leq 250 $
ii、硬度限制
硬度上限的限制:$8.8x_{1}+6.6x_{2}+2.0x_{3}+4.2x_{4}+5.0x_{5} \leq 6x_{6} $
硬度下限的限制:$8.8x_{1}+6.6x_{2}+2.0x_{3}+4.2x_{4}+5.0x_{5} \geq 3x_{6} $
iii、均衡性限制
$x_{1}+x_{2}+x_{3}+x_{4}+x_{5} = x_{6} $
iiii、非负性限制
$x_{i} \geq 0 \quad i=1,2,…,6 $
(3)综上所述,建立如下的线性规划模型
$ max \quad z = -110x_{1}-120x_{2}-130x_{3}-110x_{4}-115x_{5}+150x_{6} $
$ s.t. \begin{cases}
x_{1}+x_{2} \leq 200 \\
x_{3}+x_{4}+x_{5} \leq 250 \\
8.8x_{1}+6.6x_{2}+2.0x_{3}+4.2x_{4}+5.0x_{5} \leq 6x_{6} \\
8.8x_{1}+6.6x_{2}+2.0x_{3}+4.2x_{4}+5.0x_{5} \geq 3x_{6} \\
x_{1}+x_{2}+x_{3}+x_{4}+x_{5} = x_{6} \\
x_{i} \geq 0 \quad i=1,2,…,6
\end{cases}
$
利用Python软件求解上述线性规划模型时,需要将其改写为Python的标准形
$ min \quad w = 110x_{1}+120x_{2}+130x_{3}+110x_{4}+115x_{5}-150x_{6} $
$ s.t. \begin{cases}
x_{1}+x_{2} \leq 200 \\
x_{3}+x_{4}+x_{5} \leq 250 \\
8.8x_{1}+6.6x_{2}+2.0x_{3}+4.2x_{4}+5.0x_{5}-6x_{6} \leq 0 \\
-8.8x_{1}-6.6x_{2}-2.0x_{3}-4.2x_{4}-5.0x_{5}+3x_{6} \leq 0 \\
x_{1}+x_{2}+x_{3}+x_{4}+x_{5}-x_{6} = 0 \\
x_{i} \geq 0 \quad i=1,2,…,6
\end{cases}
$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from scipy.optimize import linprog

c = [110,120,130,110,115,-150] # 目标向量
A = [[1,1,0,0,0,0], [0,0,1,1,1,0],[8.8,6.1,2.0,4.2,5.0,-6],[-8.8,-6.1,-2.0,-4.2,-5,0.3]]
b = [[200],[250],[0],[0]]

# 等式部分
Aeq = [[1,1,1,1,1,-1]]
beq = [0]

res = linprog(c,A,b,Aeq,beq)

print('目标函数的最小值:', res.fun)
print('最优解为:', res.x)
0%