【优化数学模型】1. 基于Python的线性规划问题求解_python 线性规划求解

---

一、线性规划问题

1.概述

线性规划(Linear Programming, LP) 是解决最优化问题的工具之一，也是运筹学的重要分支。

运筹学(Operations Research) 是一门研究人类对各种广义资源的运用及筹划活动的新兴学科，其目的在于了解和发现这种运用及筹划活动的基本规律，以便更有效发挥有限资源的效益，从而达到总体或全局有效或平衡的目标。

1947年，美国数学家G.B.Dantzig及其同事提出了求解线性规划的单纯形法及其有关理论，为线性规划这一学科的建立奠定了理论基础。1979年苏联数学家哈奇扬的椭球算法和1984年美籍印度数学家H.Karmarkar算法的相继问世，使得线性规划的理论更加完备、成熟，实用领域更加宽广。

线性规划涉及的实际问题多种多样，包括生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力问题、最优设计问题等，这些问题虽然出自不同的行业，有着不同的实际背景，但都是属于如何计划、安排、调度的问题，即如何物尽其用、人尽其才的问题。

2.三要素

最优化问题往往具有三个基本要素，即决策变量、目标函数和约束条件，也被称为优化模型的三要素。

1. 决策变量：是决策者可以控制的因素，在规划模型中，用一组决策变量来表示某一方案或措施，即描述所要做出的决策，可由决策者决定和控制。例如根据不同的实际问题，决策变量可以选为药品或器械的产量、医疗物资的运量及工作的天数等。
2. 目标函数：是以函数形式来表示决策者追求的目标，表示决策者希望实现的目标。按问题的不同，要求目标函数实现最大化或最小化，在前面加上max或min来表示，目标函数也是衡量方案优劣的标准。例如目标可以是利润最大或成本最小等。对于线性规划，目标函数要求是线性的。
3. 约束条件：是决策变量需要满足的限定条件，通常表示为一组含有决策变量的等式或不等式，是决策方案可行的保障。对于线性规划，约束条件是一组线性等式或不等式。

二、示例：药厂生产问题

假设一家药厂可以生产两种药品，称为“药品A”和“药品B”。

生产每种药品都需要材料和劳动力。销售每种药品都会产生收入。

所需单位材料和劳动力投入，以及收入如下表所示：

一家药厂药构建一个生产计划，使用 30 个单位的材料和 20 个单位的劳动力，以使其收入最大化。该问题可以表述为：

  max ⁡ x 1 , x 2 z = 3 x 1 + 4 x 2  subject to  2 x 1 + 5 x 2 ≤ 30 4 x 1 + 2 x 2 ≤ 20 x 1 , x 2 ≥ 0

$$\begin{array}{cl}\ \max _{x_1, x_2} & z=3 x_1+4 x_2 \\ \text { subject to } & 2 x_1+5 x_2 \leq 30 \\ & 4 x_1+2 x_2 \leq 20 \\ & x_1, x_2 \geq 0\end{array}$$  maxx1​,x2​​ subject to ​z=3x1​+4x2​2x1​+5x2​≤304x1​+2x2​≤20x1​,x2​≥0​

三、使用 Python 绘图求解线性规划问题

1.绘制约束条件

fig, ax = plt.subplots(figsize=(8, 6))
ax.grid()

ax.hlines(0, -1, 17.5)
ax.vlines(0, -1, 12)
ax.plot(np.linspace(-1, 17.5, 100), 6-0.4*np.linspace(-1, 17.5, 100), color="c")
ax.plot(np.linspace(-1, 5.5, 100), 10-2*np.linspace(-1, 5.5, 100), color="c")
ax.text(1.5, 8, "$2x_1 + 5x_2 \leq 30$", size=12)
ax.text(10, 2.5, "$4x_1 + 2x_2 \leq 20$", size=12)
ax.text(-2, 2, "$x_2 \geq 0$", size=12)
ax.text(2.5, -0.7, "$x_1 \geq 0$", size=12)
1
2
3
4
5
6
7
8
9
10
11

2.绘制可行域

feasible_set = Polygon(np.array([[0, 0],
                                 [0, 6],
                                 [2.5, 5],
                                 [5, 0]]),
                       color="cyan")
ax.add_patch(feasible_set)
1
2
3
4
5
6

3.绘制目标函数

ax.plot(np.linspace(-1, 5.5, 100), 3.875-0.75*np.linspace(-1, 5.5, 100), color="orange")
ax.plot(np.linspace(-1, 5.5, 100), 5.375-0.75*np.linspace(-1, 5.5, 100), color="orange")
ax.plot(np.linspace(-1, 5.5, 100), 6.875-0.75*np.linspace(-1, 5.5, 100), color="orange")
ax.arrow(-1.6, 5, 0, 2, width = 0.05, head_width=0.2, head_length=0.5, color="orange")
ax.text(5.7, 1, "$z = 3x_1 + 4x_2$", size=12)
1
2
3
4
5

4.绘制最优解

ax.plot(2.5, 5, "*", color="black")
ax.text(2.7, 5.2, "Optimal Solution", size=12)

plt.show()
1
2
3
4

绘制图像如下：

• 其中，蓝色区域是满足所有约束条件的可行域。
• 平行的橙色线是收入线。
• 药厂的目标即找到平行的橙色线以达到可行域的上边界。
• 可行域与最高橙色线的交点就是最优集合。在此示例中，最优集合是点 。

四、使用 scipy.optimize 软件包求解线性规划问题

scipy.optimize 软件包提供了 linprog 函数来求解线性规划问题，形式如下：

min ⁡ x c ′ x  subject to  A u b x ≤ b u b A e q x = b e q l ≤ x ≤ u

$$\begin{array}{cl} \min _x & c^{\prime} x \\ \text { subject to } & A_{u b} x \leq b_{u b} \\ & A_{e q} x=b_{e q} \\ & l \leq x \leq u \end{array}$$ minx​ subject to ​c′xAub​x≤bub​Aeq​x=beq​l≤x≤u​

原示例可转化为以下等同的标准形式：

min ⁡ x 1 , x 2 − ( 3 x 1 + 4 x 2 )  subject to  2 x 1 + 5 x 2 + s 1 = 30 4 x 1 + 2 x 2 + s 2 = 20 x 1 , x 2 , s 1 , s 2 ≥ 0

$$\begin{aligned} \min _{x_1, x_2} & -\left(3 x_1+4 x_2\right) \\ \text { subject to } & 2 x_1+5 x_2+s_1=30 \\ & 4 x_1+2 x_2+s_2=20 \\ & x_1, x_2, s_1, s_2 \geq 0 \end{aligned}$$ x1​,x2​min​ subject to ​−(3x1​+4x2​)2x1​+5x2​+s1​=304x1​+2x2​+s2​=20x1​,x2​,s1​,s2​≥0​

1.导入库

import numpy as np
from scipy.optimize import linprog
import matplotlib.pyplot as plt
from matplotlib.patches import Polygon
1
2
3
4

2.输入目标函数参数和约束条件

• 对于每个不等式约束，生成一个松弛变量。
• 松弛变量的向量是一个二维 NumPy 数组。

# 目标函数参数
c_ex1 = np.array([3, 4])

# 约束条件
A_ex1 = np.array([[2, 5],
                  [4, 2]])
b_ex1 = np.array([30,20])
1
2
3
4
5
6
7

3.求解

# 求解
res_ex1 = linprog(-c_ex1, A_ub=A_ex1, b_ub=b_ex1)

res_ex1
1
2
3
4

输出结果如下：

        message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
        success: True
         status: 0
            fun: -27.5
              x: [ 2.500e+00  5.000e+00]
            nit: 2
          lower:  residual: [ 2.500e+00  5.000e+00]
                 marginals: [ 0.000e+00  0.000e+00]
          upper:  residual: [       inf        inf]
                 marginals: [ 0.000e+00  0.000e+00]
          eqlin:  residual: []
                 marginals: []
        ineqlin:  residual: [ 0.000e+00  0.000e+00]
                 marginals: [-6.250e-01 -4.375e-01]
 mip_node_count: 0
 mip_dual_bound: 0.0
        mip_gap: 0.0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

最优方案为：药厂生产 2.5 个单位的药品A 和 5 个单位的药品B，这产生了 27.5 的最大收入值。

---

参考文献

1. https://scipy.org/
2. J. N. Bertsimas, D. & Tsitsiklis. Introduction to linear optimization. Athena Scientific, 1997.