首页 > 其他分享 >线性规划单纯形法精解

线性规划单纯形法精解

时间:2024-08-30 10:16:14浏览次数:12  
标签:begin end 单纯形法 线性规划 boldsymbol bmatrix array 精解 left

单纯形法(Simplex Method)是解决线性规划问题的一种高效且广泛使用的算法。由乔治·丹齐克(George Dantzig)在20世纪40年代提出,这一方法通过系统地检查可行解空间的极点,从而找到最优解。由于其计算效率高,单纯形法迅速成为线性规划问题中最重要和最常用的算法之一。它的应用范围广泛,能够有效解决实际中的大规模优化问题,因此在现代工业和经济管理中扮演着关键角色。

初始单纯形表 迭代后单纯形表

一、单纯形表的消元法建构

线性规划的标准型为

\[\begin{aligned} & \max \quad z=\boldsymbol{C} \boldsymbol{X} \\ & \left\{\begin{array}{c} \boldsymbol{A} \boldsymbol{X}=\boldsymbol{b} \\ \boldsymbol{X} \geqslant \boldsymbol{0} \end{array}\right. \end{aligned} \]

其中: \(\boldsymbol{A}\) 是 \(m \times n\) 矩阵, \(m \leqslant n\) 且秩 \(r(\boldsymbol{A})=m\) ,即 \(\boldsymbol{A}\) 中至少有一个 \(m \times m\) 满秩子矩阵。

1.1 基本可行解的代数消元(最优解判断条件)

不妨设 \(\boldsymbol{B}=\left(\begin{array}{llll}\boldsymbol{P}_1 & \boldsymbol{P}_2 & \cdots & \boldsymbol{P}_m\end{array}\right)\) 是线性规划的一个基, 将有关矩阵和向量分块,记 \(\boldsymbol{A}=(\boldsymbol{B}, N), C=\left(\boldsymbol{C}_B, \boldsymbol{C}_N\right), X=\left(\boldsymbol{X}_B, \boldsymbol{X}_N\right)^{\mathrm{T}}\) ,为求线性规划的基本最优解,先要求线性规划的基本可行解,这样就需将约束中的基变量用非基变量表示出来。
用 \(\boldsymbol{B}^{-1}\) 左乘约束方程 \(\boldsymbol{A} \boldsymbol{X}=\boldsymbol{b}\) 的两端,得

\[\boldsymbol{B}^{-1} \boldsymbol{A} \boldsymbol{X}=\boldsymbol{B}^{-1}(\boldsymbol{B}, N)\binom{\boldsymbol{X}_B}{\boldsymbol{X}_N}=\boldsymbol{B}^{-1} \boldsymbol{B} \boldsymbol{X}_B+\boldsymbol{B}^{-1} \boldsymbol{N} \boldsymbol{X}_N=\boldsymbol{B}^{-1} \boldsymbol{b} \]

\[\boldsymbol{B}^{-1} \boldsymbol{B} \boldsymbol{X}_B+\boldsymbol{B}^{-1} \boldsymbol{N} \boldsymbol{X}_N=\boldsymbol{E} \boldsymbol{X}_B+\boldsymbol{B}^{-1} \boldsymbol{N} \boldsymbol{X}_N=\boldsymbol{B}^{-1} \boldsymbol{b} \]

其中 \(\boldsymbol{E}\) 是单位矩阵。整理, 得

\[\boldsymbol{X}_B=\boldsymbol{B}^{-1} \boldsymbol{b}-\boldsymbol{B}^{-1} \boldsymbol{N} \boldsymbol{X}_N \]

将其代入目标函数中,得

\[z=\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{b}-\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{N} \boldsymbol{X}_N+\boldsymbol{C}_N \boldsymbol{X}_N=\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{b}+\left(\boldsymbol{C}_N-\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{N}\right) \boldsymbol{X}_N \]

\[z=\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{b}+\sum_{j=m+1}^n\left(c_j-\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{P}_j\right) x_j \]

非基变量 \(x_j\) 前面的系数 \(c_j-\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{P}_j\) 称为变量 \(x_j\) 的检验数,表示该变量增加或减少一个单位所引起目标函数值的变化,它可以用来判断将 \(x_j\) 变成基变量后能否改进目标函数值,以后记为 \(\sigma_j=c_j-\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{P}_j\) 。

最优解判定定理:对某基本可行解 \(\boldsymbol{X}_B=\boldsymbol{B}^{-1} \boldsymbol{b}\) 其他 \(\boldsymbol{x}_N=0\), 若所有的 \(\sigma_j=\boldsymbol{c}_{\boldsymbol{j}}\) \(-\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{P}_j \leqslant 0\) ,则该解为最优解。

1.2 基本可行解的矩阵消元

考虑线性方程组 \(\left\{\begin{array}{l}\boldsymbol{A} \boldsymbol{X}=\boldsymbol{b} \\ \boldsymbol{z}=\boldsymbol{C} \boldsymbol{X}\end{array}\right.\), 其变量为 \(\left[\begin{array}{l}\boldsymbol{X} \\ \boldsymbol{z}\end{array}\right]\), 为便于求解, 整理得方程组 \(\left\{\begin{array}{c}0 \cdot z+\boldsymbol{A} \boldsymbol{X}=\boldsymbol{b} \\ -z+\boldsymbol{C X}=\boldsymbol{0}\end{array}\right.\), 其增广矩阵见下表, 应用高斯消元法, 求解线性方程组的解。

常数项 z XB XN
b 0 B N (1-1)
0 -1 \(C_B\) \(C_N\) (1-2)

用 \(\boldsymbol{B}^{-1}\) 左乘方程组(1-1)的两端, 将 \(\boldsymbol{X}_B\) 的系数化为单位矩阵, 得下表。

常数项 z $$X_B$$ $$X_N$$
\(B^{-1} b\) 0 \(B^{-1}B=E\) \(B^{-1}N\) (1-3)
0 -1 \(C_B\) \(C_N\)

将方程组(1-3)左乘 \(-\boldsymbol{C}_B\) 加到方程(1-2)两边,消元化简得下表。

常数项 z \(X_B\) \(X_N\)
\(B^{-1} b\) 0 $$B^{-1}B=E$$ $$B^{-1}N$$
$$-C_BB^{-1}b$$ -1 $$C_B - C_BB^{-1}B = 0$$ $$C_N - C_BB^{-1}N $$ (1-4)

注意式(1-4)中基向量 \(\boldsymbol{X}_B\) 、非基向量 \(\boldsymbol{X}_N\) 的系数,它们形式相似,当前者 \(\boldsymbol{C}_B-\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{B}=0\)时,后者即为检验数 \(\boldsymbol{C}_{\boldsymbol{N}}-\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{N}\) 的矩阵形式。也就是说,用消元法将目标函数中基变量的系数化为零的同时,就会得到非基变量的检验数。事实上, \(\boldsymbol{C}_B-\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{B}\) 也可看成基向量的检验数, 应用消元法后, 当基向量的检验数化为零时, 非基变量的系数 \(\boldsymbol{C}_{\boldsymbol{N}}-\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{N}\) 就是其检验数。
从上述论述可知, 计算检验数的方法有两种:一是通过公式 \(\sigma_j=c_j-\boldsymbol{C}_B \boldsymbol{B}^{-1} \boldsymbol{P}_j\) 计算得出;二是应用消元法,将目标函数中基向量的系数都化为零时,非基向量的系数就是检验数。这也是单纯表结构的出处。

1.3 单纯形法=逆矩阵法

单纯形法的核心思想是通过变换基本变量和非基本变量,找到一个新的基本可行解,并通过比较检验数判断该解是否为最优解。在单纯形法中,每一个基本可行解都对应着一个基矩阵的逆矩阵。基矩阵是从约束条件系数矩阵中选取的列所构成的矩阵,它的逆矩阵在每次迭代中都要更新。
这个逆矩阵的求解是单纯形法消元过程的核心,因为它直接影响到新解的生成和目标函数的优化。具体来说,当我们选择一个进入基的变量并排除一个离开基的变量时,这相当于对基矩阵进行了一次列替换操作。为了保持计算的有效性,我们需要快速更新逆矩阵。这通常通过一个修正的高斯消元法来完成,使得新基的逆矩阵可以通过旧基的逆矩阵迅速计算出来。
单纯形的每次迭代,都可以使用逆矩阵来计算检验数,从而判断是否可以进一步优化目标函数。检验数的计算过程依赖于逆矩阵,因为检验数用于评估当前解的可行性及其对目标函数的影响。如果所有检验数都满足最优性条件,那么当前解就是最优解;否则,我们需要通过逆矩阵的进一步操作继续迭代。
例1:已知初始单纯形表和最终单纯形表, 试求解以下问题。
(1)在初始单纯形表中找出最优基 \(\boldsymbol{B}\) ,在最终单纯形表里找出 \(\boldsymbol{B}^{-1}\) 。
(2)完成最终单纯形表。(3) 给出最优解与最优值。

$$C_B$$ $$X_B$$ $$B^{-1}b$$ $$x_1$$ $$x_2$$ $$x_3$$ $$x_4$$ $$x_5$$ $$x_6$$
初始表 0 \(x_4\) 60 3 1 1 1 0 0
0 \(x_5\) 10 1 -1 2 0 1 0
0 \(x_6\) 20 1 1 -1 0 0 1
\(σ_j\) 2 -1 1 0 0 0
最终表 \(x_4\) -1 -2
\(x_1\) 1/2 1/2
\(x_2\) -1/2 1/2
\(σ_j\)

确定最优基和\(B^{-1}\)

  • 最优基 \(\boldsymbol{B}\):从初始基变量\(x_4\)、\(x_5\)、\(x_6\) 通过单纯形法操作,最终基变量变为\(x_4\)、\(x_1\)、\(x_2\)
  • \(B^{-1}\):通过最终单纯形表的\(x_4\)、\(x_5\)、\(x_6\)列得到 \(B^{-1}\):

\[B^{-1} = \begin{bmatrix} 1 & -1 & -2 \\ 0 & 1/2 & 1/2 \\ 0 & -1/2 & 1/2 \\ \end{bmatrix}\]

计算\(B^{-1}\)

  • 右端项\(b = \begin{bmatrix} 60 \quad 10 \quad 20 \end{bmatrix}\)

\[B^{-1}b = \begin{bmatrix} 1 & -1 & -2 \\ 0 & 1/2 & 1/2 \\ 0 & -1/2 & 1/2 \\ \end{bmatrix} \begin{bmatrix} 60 \\ 10 \\ 20 \\ \end{bmatrix} = \begin{bmatrix} 10 \\ 15 \\ 5 \\ \end{bmatrix}\]

计算最终单纯形表中的列向量
-\(x_3\)列向量计算:

  • 初始表中\(x_3\)列为\([1, 2, -1]^T\)

\[B^{-1} \begin{bmatrix} 1 \\ 2 \\ -1 \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0.5 \\ -1.5 \\ \end{bmatrix}\]

因此\(x_3\)列为\(\begin{bmatrix} 1 \quad 0.5 \quad -1.5 \end{bmatrix}^T\)。

计算检验数\(σ_j\)
目标函数为\(z = 2x_1 -x_2+x_3\)

  • 基变量的成本系数向量\(C_B = [0, 2, -1]\)
变量 $$P_j$$ $$σ_j = c_j-C_B B^{-1}P_j - $$ 计算过程
$$x_1 $$ $$ \begin{bmatrix} 0 \quad 1 \quad 0 \end{bmatrix} $$ 0 $$ 2-[0, 2, -1] \cdot \begin{bmatrix} 0 \ 1 \ 0 \end{bmatrix} = 0 $$
$$x_2$$ $$ \begin{bmatrix} 0 \quad 0 \quad 1 \end{bmatrix} $$ 0 $$-1-[0, 2, -1] \cdot \begin{bmatrix} 0 \ 0 \ 1 \end{bmatrix} = 0 $$
$$ x_3 $$ $$ \begin{bmatrix} 1 \quad 0.5 \quad -1.5 \end{bmatrix} $$ -1.5 $$1-[0, 2, -1] \cdot \begin{bmatrix} 1 \ 0.5 \ -1.5 \end{bmatrix} = -1.5 $$
$$x_4 $$ $$ \begin{bmatrix} 1 \quad 0 \quad 0 \end{bmatrix} $$ 0 $$ 0-[0, 2, -1] \cdot \begin{bmatrix} 1 \ 0 \ 0 \end{bmatrix} = 0 $$
$$ x_5$$ $$ \begin{bmatrix} -1 \quad 0.5 \quad -0.5 \end{bmatrix} $$ -1.5 $$0-[0, 2, -1] \cdot \begin{bmatrix} -1 \ 0.5 \ -0.5 \end{bmatrix} = -1.5 $$
$$ x_6 $$ $$ \begin{bmatrix} -2 \quad 0.5 \quad 0.5 \end{bmatrix} $$ -0.5 $$0- [0, 2, -1] \cdot \begin{bmatrix} -2 \ 0.5 \ 0.5 \end{bmatrix} = -0.5 $$

最终单纯形表

$$C_B$$ $$X_B$$ $$B^{-1}b$$ $$x_1$$ $$x_2$$ $$x_3$$ $$x_4$$ $$x_5$$ $$x_6$$
最终表 0 $$x_4$$ 10 0 0 1 1 -1 -2
3 $$x_1$$ 15 1 0 0.5 0 1/2 1/2
2 $$x_2$$ 5 0 1 -1.5 0 -1/2 1/2
$$σ_j$$ 0 0 -1.5 0 -1.5 -0.5

最优解与最优值

  • 最优解:\(X^*=\left[\begin{array}{llllll}15 & 5 & 0 & 10 & 0 & 0\end{array}\right]^T\)。
  • 最优值:\(z^*=25\)

二、单纯形的迭代步骤

例1:对于线性规划问题

\[\begin{array}{cc} \text { max } & 2 x_1+3 x_2 \\ \text { s.t. } & 4 x_1+x_2+x_3=16 \\ & -x_1+x_2+x_4=6 \\ & x_1, x_2, x_3, x_4>=0 \end{array} \]

其中, \(x_3\) 和 \(x_4\) 是松驰变量。

决策变量:\(\mathbf{x}=\left[\begin{array}{l}x_1& x_2 & x_3 & x_4\end{array}\right]^T\) 是决策变量向量。
目标函数: Max \(\mathbf{c}^{\top} \mathbf{x}\) 其中, \(\mathbf{c}=\left[\begin{array}{c}2\quad 3\quad 0 \quad0\end{array}\right]^T\) 为目标函数的系数向量。
约束条件: \(\mathbf{A} \mathbf{x}=\mathbf{b}\) ,其中 \(\mathbf{A}=\left[\begin{array}{cccc}4 & 1 & 1 & 0 \\ -1 & 1 & 0 & 1\end{array}\right]\) 是约束系数矩阵。
\(\mathbf{b}=\left[\begin{array}{c}16 & 6\end{array}\right]^T\) 是约束右端项向量。因此,标准型的线性规划问题可以表示为:

\[\begin{aligned} & x_B=\left[x_3, x_4\right], x_N=\left[x_1, x_2\right], N=\left[\begin{array}{cc} 4 & 1 \\ -1 & 1 \end{array}\right], B=\left[\begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array}\right], c_B=[0,0], c_N =[2,3] \end{aligned} \]

初始时令 \(x_N=[0,0]\)
**第一轮迭代: **此时 \(c_N-c_B B^{-1} N=[2,3]\) 因此选择 \(x_2\) 作为入基变量更为高效,且 \(b-N x_N=\left[\begin{array}{c}16-4 x_1-x_2 \\ 6+x_1-x_2\end{array}\right]>=0\) 故 \(x_2=6\) 并令 \(x_4=0, x_2\) 入基, \(x_4\) 出基。经过此轮迭代后,各变量如下

\[\begin{aligned} & x_B=\left[x_3, x_2\right], x_N=\left[x_1, x_4\right], N=\left[\begin{array}{cc} 4 & 0 \\ -1 & 1 \end{array}\right], B=\left[\begin{array}{ll} 1 & 1 \\ 0 & 1 \end{array}\right], c_B=[0,3], c_N =[2,0] \end{aligned} \]

**第二轮迭代: **此时 \(c_N-c_B B^{-1} N=[5,-3]\) ,选择 \(x_1\) 作为入基变量更为高效,且
\(b-N x_N=\left[\begin{array}{c}16-4 x_1 \\ 6+x_1\end{array}\right]>=0\) 故 \(x_1=4\) 并令 \(x_3=0, x_1\) 入基, \(x_3\) 出基。经过此轮迭代后,各变量如下

\[\begin{aligned} & x_B=\left[x_1, x_2\right], x_N=\left[x_3, x_4\right], N=\left[\begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array}\right], B=\left[\begin{array}{cc} 4 & 1 \\ -1 & 1 \end{array}\right], c_B=[2,3], c_N =[0,0] \end{aligned} \]

**第三轮迭代: **此时 \(c_N-c_B B^{-1} N=[-1,-2]\) 都小于 0 ,达到收敛条件,此时令 \(x_N=[0,0]\) 解得 \(x_B=[2,8]\) 最小值为28。

**例2:*求解下面线性模型


初始单纯形表

\(x_1\) \(x_2\) \(x_3\) \(x_4\) \(x_5\) \(b\) \(\theta\)
目标函数 70 30 0 0 0
约束 1 3 9 1 0 0 540
约束 2 5 5 0 1 0 450
约束 3 9 3 0 0 1 720

判断当前顶点是否是最优解
对于最大化问题,若当前目标函数中的非基变量的系数小于等于0时,则所得的解为最优解。而在当前的例子中,非基变量的系数分别为70和30,意味着在可行域内随着非基变量\(x_1\)和\(x_2\)的增大,目标函数就会继续增大,因此当前的解不是最优解。故判断当前所得的解是否为最优解时,只需判断目标函数中非基变量的系数是否小于等于0。
进基和出基变量
变量的出基与入基,在几何图像上表现为顶点的变化。入基的规则为选择使目标函数z变化最快的非基变量入基,即选择系数最大且为正数的非基变量入基,故在本例中选择\(x_1\)入基。出基的规则则需要引入一个新的量\(\theta\),\(\theta=b/a_i\)(\(a_i\)为非基变量系数,\(a_i\)的选择的是刚刚入基的非基变量的系数),选择最小的\(\theta\)出基。

\(x_1\) \(x_2\) \(x_3\) \(x_4\) \(x_5\) \(b\) \(\theta\)
目标函数 70 30 0 0 0
约束 1 3 9 1 0 0 540 180
约束 2 5 5 0 1 0 450 90
约束 3 9 3 0 0 1 720 80

第一次迭代,经过\(x_1\)入基与\(x_5\)出基的运算后,得到的结果如下所示。

\(x_1\) \(x_2\) \(x_3\) \(x_4\) \(x_5\) \(b\) \(\theta\)
\(Z\) 0 20/3 0 0 -70/9 5600
\(x_3\) 0 8 1 0 -1/3 300
\(x_4\) 0 10/3 0 1 -5/9 50
\(x_1\) 1 1/3 0 0 1/9 80

令非基变量的值为0,则得到第一次迭代的解,如下所示

\[X = \begin{pmatrix} x_1\quad x_2 \quad x_3\quad x_4 \quad x_5 \end{pmatrix} = \begin{pmatrix} 80 \quad 0 \quad 300 \quad 50 \quad 0 \end{pmatrix}^T \\ Z = 5600 \]

判断该解是否为最优解(重复第二个步骤,直到是最优解为止),显然由于非基变量\(x_2\)的系数大于0,故当前位置还不是最优解,再次重复上面步骤。

三、练习

Food Energy(能量) Protein(蛋白质) Calcium(钙) Price
Oatmeal(燕麦) 110 4 2 3
Whole milk(全奶) 160 8 285 9
Cherry pie(草莓派) 420 4 22 20
Pork with beans(猪肉) 260 14 80 19

决策变量:

  • \(x_1\):购买燕麦(Oatmeal)的数量
  • \(x_2\):购买全奶(Whole milk)的数量
  • \(x_3\):购买草莓派(Cherry pie)的数量
  • \(x_4\):购买猪肉(Pork with beans)的数量

目标函数:

最小化总价格:

\[\text{Min } Z = 3x_1 + 9x_2 + 20x_3 + 19x_4 \]

约束条件:

  • 能量需求:至少2000单位能量

\[110x_1 + 160x_2 + 420x_3 + 260x_4 \geq 2000 \]

  • 蛋白质需求:至少55单位蛋白质

\[4x_1 + 8x_2 + 4x_3 + 14x_4 \geq 55 \]

  • 钙需求:至少800单位钙

\[2x_1 + 285x_2 + 22x_3 + 80x_4 \geq 800 \]

  • 非负性约束

\[x_1, x_2, x_3, x_4 \geq 0 \]

from pulp import LpProblem, LpMinimize, LpVariable, lpSum, value, LpStatus

# 定义问题
problem = LpProblem("Minimize Cost", LpMinimize)

# 定义变量
x1 = LpVariable('x1', lowBound=0, cat='Continuous')
x2 = LpVariable('x2', lowBound=0, cat='Continuous')
x3 = LpVariable('x3', lowBound=0, cat='Continuous')
x4 = LpVariable('x4', lowBound=0, cat='Continuous')

# 目标函数
problem += 3*x1 + 9*x2 + 20*x3 + 19*x4, "Total Cost"

# 约束条件
problem += 110*x1 + 160*x2 + 420*x3 + 260*x4 >= 2000, "Energy"
problem += 4*x1 + 8*x2 + 4*x3 + 14*x4 >= 55, "Protein"
problem += 2*x1 + 285*x2 + 22*x3 + 80*x4 >= 800, "Calcium"

# 求解
problem.solve()

# 输出结果
print(f"Status: {LpStatus[problem.status]}")
print(f"Oatmeal (燕麦) units: {value(x1)}")
print(f"Whole milk (全奶) units: {value(x2)}")
print(f"Cherry pie (草莓派) units: {value(x3)}")
print(f"Pork with beans (猪肉) units: {value(x4)}")
print(f"Total minimum cost: {value(problem.objective)}")
Status: Optimal
Oatmeal (燕麦) units: 14.24428
Whole milk (全奶) units: 2.7070577
Cherry pie (草莓派) units: 0.0
Pork with beans (猪肉) units: 0.0
Total minimum cost: 67.09635929999999

总结

单纯形法是线性规划问题中的一种经典算法,它通过逐步优化,找到能够最大化或最小化目标函数的可行解。尽管单纯形法在最坏情况下可能需要指数级时间,但在实际应用中,单纯形法通常能高效地找到最优解,因此它被广泛应用于各种线性规划问题中,例如生产计划、资源分配、运输优化等。
单纯形法的直观性在于从一个顶点开始沿边界移动到另一个顶点,不断提高目标函数值,直到达到最优解。这种方法简单且易于理解,对大多数线性规划问题都能有效求解。然而,单纯形法也存在一些局限性,例如在处理退化问题时可能会出现循环,导致算法陷入无限循环的困境。为了克服这些局限性,研究者们提出了多种改进方案,如反周期规则来防止循环、对偶单纯形法来处理不可行的初始解等。此外,内点法作为一种替代算法,通过从可行域的内部逼近最优解,提供了不同于单纯形法的求解思路,并且在某些情况下表现出更好的最坏情况性能。通过这些改进和新方法的引入,线性规划问题的求解在理论和实践上都得到了极大的丰富和发展,使得我们能够解决更复杂、更大规模的问题。这些进步不仅提升了算法的效率,也拓展了线性规划在各个领域的应用范围。单纯形法及其改进方法的持续发展,确保了线性规划在优化和决策问题中的核心地位。

参考文献

  1. https://zhuanlan.zhihu.com/p/672071565
  2. python最优化算法实战---线性规划之单纯形法

在给定的营业时间内(14小时),啤酒厂需要制定一个生产计划,以最大化其收益。生产生啤需要1小时,生产黑啤需要2小时。生啤的售价为20美元/箱,黑啤的售价为30美元/箱。每日销售上限为100箱。

标签:begin,end,单纯形法,线性规划,boldsymbol,bmatrix,array,精解,left
From: https://www.cnblogs.com/haohai9309/p/18386953

相关文章

  • 线性规划单纯形求解理论
    线性规划(LinearProgramming,LP)是优化理论中用于在给定约束条件下最大化或最小化线性目标函数的一种数学方法。线性规划的最优解总是出现在可行域的顶点上,这是因为目标函数在可行域内的变化是线性的,因此在顶点处函数的值可能达到极值(最大或最小)。求解线性规划问题的常用方法之一......
  • 高等数学精解【12】
    文章目录无损压缩算法常见算法概述1.**霍夫曼编码(HuffmanCoding)**2.**Lempel-Ziv-Welch(LZW)**3.**游程编码(Run-LengthEncoding,RLE)**4.**算术编码(ArithmeticCoding)**5.**DEFLATE**6.转换编码(TransformCoding)7.预测编码(PredictiveCoding)转换编码的无损压......
  • 2024数学建模国赛准备中!!!(2——非线性规划)
    第三章 非线性规划§1非线性规划非线性规划的实例与定义如果目标函数或约束条件中包含非线性函数,就称这种规划问题为非线性规划问题。一般说来,解非线性规划要比解线性规划问题困难得多。而且,也不象线性规划有单纯形法这一通用方法,非线性规划目前还没有适于各种问题的一......
  • 抽象代数精解【13】
    文章目录有限域上的椭圆曲线Weierstrass方程的来源一、椭圆曲线理论背景二、Weierstrass一般方程的提出三、Weierstrass方程的重要性四、Weierstrass函数与Weierstrass方程的区别标准椭圆方程、椭圆曲线和Weierstrass方程的联系与区别1.标准椭圆方程的定义2.椭圆曲线......
  • 抽象代数精解【12】
    这里写目录标题群同构基础例子参考文献群同构基础设G与G′......
  • 利用Python实现供应链管理中的线性规划与资源优化——手机生产计划1
    目录写在开头1.Python与线性规划的基础2.供应链管理中的资源优化3.利用Python进行供应链资源优化3.1简单的优化实例3.2考虑多种原材料3.3多种原材料、交付时间与物流融合的情况4.规范性分析在供应链管理中的应用价值写在最后写在开头在全球供应链日益复杂的背景......
  • 非线性规划的经典例题--选址问题
    本章会介绍如何利用非线性规划解决选址问题,这个问题是文章线性规划在数学建模中的两道例题中第二道投料问题的第二小题,本章为基于这道题的基础上进行介绍,建议读者返回去看一看目录一、问题提出二、问题分析三、模型建立四、代码实现1.输入目标函数2.输入线性约束一、问题提出......
  • 【转载】网络流与线性规划 24 题刷题指南
    前言本篇博文转载自博客园ticmis的博文网络流24题,转载时做了如下改动:排版整理,规范化\(\LaTeX\)。题单中添加了洛谷题号和洛谷难度。错别字修改。内容描述稍作改动。说实话,本人很讨厌某SDN上的各个博主间互相抄来抄去的行为,这一篇是我第一次转载别人的博文,原因是......
  • 线性规划在数学建模中的两道例题
    目录一、生产决策问题1.问题分析2.模型建立(1)符号设定(2)目标函数建立(3)约束建立3.代码求解(1)输入系数向量(2)输入不等式约束(3)输入等式约束与上下界(4)进行求解二、投料问题1.问题分析2.模型建立(1)符号设定(2)目标函数建立(3)约束建立3.代码求解(1)输入系数向量(2)输入不等式约束(3)输入等式约束与上下......
  • matlab求解线性规划问题
    在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支--数学规划,而线性规划(LinearProgramming,LP)则是数学规划的一个重要分支。本章会介绍线性规划模型与matlab求解目录一、线性规划的标准形二、linprog函......