线性规划(Linear Programming)是数学优化的一个分支,主要关注在一组线性等式或不等式约束条件下,对某个线性目标函数进行最大化或最小化的问题。
在具体的定义下,一个线性规划问题是这样的:给定一个实向量空间 的实值线性函数,将其称为目标函数。还给定一组达到非负实值的线性约束形式的方程或不等式。线性规划的目标是找到目标函数的最大值或最小值,这些值由约束方程集(被称为线性规划问题的可行域)确定。
线性规划的标准型(或称为规范型)是把线性规划问题写成最优化问题的标准形式。一个线性规划问题的标准型如下:
最大化目标函数:
同时满足如下约束条件:
并且 .
这里, 是决策变量, 是需要优化的目标函数。系数 是目标函数的参数, 和 是约束的参数。
以上即为线性规划问题的标准型。所有的线性规划问题都可以转化为这种形式。在计算解的算法(如单纯形法)中,这种形式的问题更容易处理。
假设我们对如下标准线性规划问题进行求解:
最大化:
约束条件为:
其中, 是目标函数的系数向量, 是约束条件的矩阵, 是约束条件右边的向量, 是决策变量向量。
以下是单纯形法的步骤:
构造扩大矩阵: 将非负约束转化为等式约束
其中, 是松弛变量构成的向量, 是 的单位矩阵。在目标函数中增加项后,可以写成标准型。 构造扩大矩阵
基的选择:选择一个初始基,通常选择单位矩阵对应的列。
旋转操作:在目标函数的系数中选择一个非零系数对应的列为 。然后计算比值 ,选择最小的非负比值对应的行为 行。基于这个 元素(主元),用高斯-约旦消元法进行旋转操作。
这个过程实则是在应用线性代数中的高斯-约旦消元法来化简矩阵。"旋转"这个概念是因为在整个消元过程中,可行域的基将会不断的改变,就像在"旋转"一样,因此引入这个词来形象地描述这个过程。
值得注意的是,在单纯形法的计算过程中,一直需要保持基的可行性,也就是说在每一步旋转操作后,得到的新基仍然需要满足问题的约束条件。
检查和终止条件:如果所有目标函数的系数都小于等于零,则停止迭代,否则返回步骤3。当所有目标函数的系数都小于等于0时,我们称目标函数已经最优化。
以上是单纯形法的基本步骤,无论对于求解最大化还是最小化的线性规划问题,其主要思路都是一致的。同时,针对可能出现的退化、无解、无界等特殊情况,也需要结合具体问题分析和处理。
在单纯形法中,当在某一次基变换过程中,一个基变量的值变为零,这种情况就叫做退化。这样导致的结果通常是单纯形法入陷入循环,无法找到最优解。退化问题是线性规划解的稳定性问题之一。
这表示线性规划问题不存在可行解。一个线性规划问题可能因为系统的约束之间存在矛盾,例如,同一个决策变量在不同约束条件下取值的范围不一致等问题,导致问题无法找出满足所有约束的解,即无解。
这表示线性规划问题存在着使目标函数值可以趋近于无穷大(无穷小)的解。简单来说,如果一个最大化(或最小化)问题的解可以使目标函数的取值无限增大(或减小),那么就称这个问题是无界的。在单纯形法中,这通常发生在当问题退化时,遇到某一个变量在增大(或减小)而不影响其他变量值的情况下,会导致该变量可以无限增大(或减小),使得目标函数值无限增大(或减小)。总的来说,对应于物理或经济背景的问题通常不会出现无界解。
假设我们有一个问题,需要购买不同的食物来满足最小的营养需求。每种食物有不同的价格和营养含量。我们选择的目标是最小化购买食物的总成本。
在这个问题中:
目标函数:
约束:
更具体的,我们有如下的数据:
那么求解问题如下:
1import numpy as np
2from scipy.optimize import linprog
3
4c = [0.5, 2] # 费用函数(即面包和牛肉的价格)
5
6# 营养成分约束,注意此处为负数,因为线性规划默认求解的是小于等于约束(A_ub表示约束为小于等于)
7# 所以我们将得到的营养(能量和蛋白质)转为负数,变为小于等于约束
8A = [[-20, -100], [-10, -20]] # 面包和牛肉提供的能量和蛋白质
9
10b = [-200, -50] # 最少需要的能量和蛋白质,也转为负数
11
12bounds = [(0, None), (0, None)] # 面包和牛肉的购买量范围,我们假设至少为0,没有上限
13
14# 使用scipy库的线性规划函数求解
15res = linprog(c, A_ub=A, b_ub=b, bounds=bounds, method='simplex')
16
17# 打印最优解:总共的最低花费以及购买的食物数量
18print('最优值:', round(res.fun, 2),
19 '\nX:', np.round(res.x, 2))
1import numpy as np
2from scipy.optimize import linprog
3
4c = [0.5, 2] # 费用函数(即面包和牛肉的价格)
5
6# 营养成分约束,注意此处为负数,因为线性规划默认求解的是小于等于约束(A_ub表示约束为小于等于)
7# 所以我们将得到的营养(能量和蛋白质)转为负数,变为小于等于约束
8A = [[-20, -100], [-10, -20]] # 面包和牛肉提供的能量和蛋白质
9
10b = [-200, -50] # 最少需要的能量和蛋白质,也转为负数
11
12bounds = [(0, None), (0, None)] # 面包和牛肉的购买量范围,我们假设至少为0,没有上限
13
14# 使用scipy库的线性规划函数求解
15res = linprog(c, A_ub=A, b_ub=b, bounds=bounds, method='simplex')
16
17# 打印最优解:总共的最低花费以及购买的食物数量
18print('最优值:', round(res.fun, 2),
19 '\nX:', np.round(res.x, 2))
这段代码中首先定义了成本函数和约束,然后使用linprog函数求解。解决方案包含食物的数量和总成本。
输出结果:
1最优值: 4.17
2X: [1.67 1.67]
1最优值: 4.17
2X: [1.67 1.67]
适用于以下几个方面的问题:
优点:
缺点: