数学建模：运筹优化类——线性规划

数学建模：运筹优化类——线性规划

引用

CSDN

1.

https://m.blog.csdn.net/qq_74301026/article/details/140833016

线性规划是运筹学中的一个重要分支，广泛应用于资源分配、生产计划、物流运输等领域。本文将从基本概念出发，通过两个具体案例，详细介绍线性规划的建模过程和求解方法。

1. 线性规划概述

线性规划（Linear Programming，简称LP）是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。它可以帮助我们在有限的资源条件下，做出最优决策，从而实现资源的合理利用。

2. 线性规划模型三要素

• 决策变量：问题中需要确定的未知量，用于表示规划问题中的方案、措施等，其取值可以由决策者控制。
• 目标函数：决策变量的函数，通常需要最大化或最小化该函数。
• 约束条件：决策变量的取值所受到的限制条件，通常用含有决策变量的等式或不等式表示。

3. 模型特点

• 优化类问题：在有限资源条件下追求最大收益。
• 线性关系：目标函数和约束条件都是决策变量的线性函数。
• 目标：求解线性目标函数的最大值或最小值。

4. 建模步骤

1. 确定决策变量：根据问题影响因素找出需要决策的变量。
2. 建立目标函数：明确决策变量与目标之间的函数关系。
3. 列出约束条件：确定决策变量所受的限制条件。

5. 案例演示

5.1 游戏升级案例

题目：某游戏中每天有100点体力，可通过反复通关A、B、C三张地图来获取经验升级。通关A图可获得20点经验，通关B图可获得30点经验，通关C图可获得45点经验，但通关地图会消耗体力，其中通关A图消耗4点体力，通关B图消耗8点体力，通关C图消耗5点体力，同时A、B、C三图每天加在一起最多通关20次，求该怎么组合通关ABC三个地图的次数来使今天获得的经验最大？

解答：

• 决策变量：设A、B、C三个地图通关的次数分别为$x_1$、$x_2$、$x_3$。
• 目标函数：设经验为$y$，则$y = 20x_1 + 30x_2 + 45x_3$。
• 约束条件：
• 消耗体力不能超过100：$4x_1 + 8x_2 + 15x_3 \leq 100$
• 三个地图最多通关20次：$x_1 + x_2 + x_3 \leq 20$
• 隐藏约束条件：$x_1, x_2, x_3 \geq 0$

用矩阵形式表示为：

$$
\begin{align*}
\text{maximize} \quad & 20x_1 + 30x_2 + 45x_3 \
\text{subject to} \quad & 4x_1 + 8x_2 + 15x_3 \leq 100 \
& x_1 + x_2 + x_3 \leq 20 \
& x_1, x_2, x_3 \geq 0
\end{align*}
$$

其中：

• $c$——目标函数的系数向量，即价值向量；
• $x$——决策向量；
• $A$——约束方程组的系数矩阵；
• $b$——约束方程组的常数向量。

编程实现：

import numpy as np
from scipy.optimize import linprog

# 目标函数系数，这里取负值，因为linprog默认进行最小优化
c = [-20, -30, -45]
# 不等式约束的系数矩阵
A_ub = [
    [4, 8, 15],
    [1, 1, 1]
]
# 不等式约束的右侧向量值b
b_ub = [100, 20]
# 定义域
bounds = [[0, None], [0, None], [0, None]]
# 求解线性规划问题
# 注意：由于linprog默认是求解最小化问题，我们通过对目标函数系数取负值来转换为最大化问题
result = linprog(c, A_ub, b_ub, bounds=bounds)
# 输出结果
print('A、B、C三图分别通关的次数为：', result.x)  # 解向量
# 目标函数的最大值是最小化问题的相反数
y = -result.fun
print('最终获得的经验为：', y)

输出结果表明，通过通关A图15次，B图5次，C图0次可以获得最大经验450点。

5.2 投资选择案例

题目：市场上有4种资产可供投资者选择，某公司有数额为M的一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这4种资产进行了评估，估算出在这一时期内购买资产的平均收益率、风险损失率等数据。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的资产中最大的一个风险来度量。此外，购买每种资产要付交易费，费率为$r_i$，并且当购买额不超过给定值$M_i$时，交易费按购买额计算（不买无须付费）。另外，假定同期银行存款利率是$r_0$（$r_0=5%$），且既无交易又无风险。

已知相关数据如下：

问：给上述公司设计投资组合方案，用给定资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，总体风险尽可能小。

解答：

• 决策变量：投资不同项目的金额$x_i$（i=1,2,...,n）。
• 目标函数：净收益Q尽可能大、总风险尽可能小。
• 约束条件：总资金M有限，每一笔投资都是非负数。

模型假设：

• 可供投资的资金数额M相当大。
• 投资越分散，总的风险越小，总体风险可用所投资的资产中最大的一个风险来度量。
• 可供选择的n+1种资产（含银行存款）之间是相互独立的。
• 每种资产可购买的数量为任意值。
• 在当前投资周期内，相关参数固定不变。
• 不考虑在资产交易过程中产生的其他费用。
• 由于投资数额M相当大，而题目设定的定额相对M很小，因此假设每一笔交易金额都大于对应定额。

模型建立：

1. 总体风险用所投资的资产中最大的一个风险来衡量，即$\max{r_1x_1, r_2x_2, ..., r_nx_n}$。
2. 购买每种资产的净收益可以简化为$(r_i - r_0 - r_i)x_i$。
3. 目标函数为：$\max Q = \sum_{i=1}^{n}(r_i - r_0 - r_i)x_i$。
4. 约束条件为：$\sum_{i=1}^{n}x_i \leq M$，$x_i \geq 0$。

这是一个多目标规划模型，可以通过给定风险界限a，将目标函数中的风险转换为约束条件$r_i x_i \leq aM$，从而简化为单目标线性规划。

模型简化：
在实际投资中，投资者承受风险的程度不一样，这时可以给定风险一个界限a，使最大的一个风险$r_i x_i \leq aM$，这样就可以将目标函数中的风险转换为约束条件$r_i x_i \leq aM$。至此，模型用一般形式表现为：

$$
\begin{align*}
\text{maximize} \quad & \sum_{i=1}^{n}(r_i - r_0 - r_i)x_i \
\text{subject to} \quad & \sum_{i=1}^{n}x_i \leq M \
& r_i x_i \leq aM \quad \forall i \
& x_i \geq 0 \quad \forall i
\end{align*}
$$

这里M取1万元，a从0开始，以步长0.001进行循环搜索，搜索至a=5%（低风险者能够接受的风险）。

编程实现：

import matplotlib.pyplot as plt
from numpy import ones, diag, c_, zeros
from scipy.optimize import linprog

# 设置matplotlib的参数使其支持LaTeX文本和字体大小
plt.rc('text', usetex=True)
plt.rc('font', size=16)

# 线性规划问题的目标函数系数
c = [-0.05, -0.27, -0.19, -0.185, -0.185]
# 线性不等式约束的系数矩阵
# 使用c_来合并数组，zeros创建一个全0的数组作为第1列，diag创建一个对角阵
A = c_[zeros(4), diag([0.025, 0.015, 0.055, 0.026])]
# 线性等式约束的系数矩阵和右侧的值
Aeq = [[1, 1.01, 1.02, 1.045, 1.065]]
beq = [1]
# 初始化参数a，以及两个用于存储结果的空列表
a = 0
aa = []
ss = []
# 循环，a的值从0开始，以0.0001的步长增加，直到0.05
while a < 0.05:
    # 创建线性不等式约束的右侧值(b)
    b = ones(4) * a

    # 执行线性规划，得到最优解
    res = linprog(c, A, b, Aeq, beq, bounds=[(0, None), (0, None), (0, None), (0, None), (0, None)])

    # 提取线性规划的解向量x和最优值Q
    x = res.x
    Q = -res.fun
    # 将当前的a值和对应的最优值Q存入列表
    aa.append(a)
    ss.append(Q)

    # a增加0.001
    a = a + 0.001

# 绘制结果，a值与最优值Q之间的关系图
plt.plot(aa, ss, 'r*')  # 使用红色星号标记数据点
# 设置坐标轴标签，其中a和Q将使用LaTeX格式显示
plt.xlabel('$a$')
plt.ylabel('$Q$', rotation=90)
# 显示图形
plt.show()

风险a与收益Q之间的关系：

由上图可以看出：

1. 风险不超过2.5%时，风险大，收益也大；
2. 在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢。所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的转折点作为最优投资组合，大约是a=0.6%，Q=2000，所对应的投资方案为：

风险度a=0.006，收益Q=2019元；
$x_1$=0元，$x_2$=2400元，$x_3$=4000元，$x_4$=1091元，$x_5$=2212元。