当前位置：首页 > news >正文

山东省建设项目备案证明网站咸宁公司网站建设

news 2025/9/17 7:07:02

山东省建设项目备案证明网站,咸宁公司网站建设,ps软件下载中文版免费下载,狠抓措施落实目录 0. 简介 1. 单纯形算法解析 1.1 基本概念及原理解析 1.1.1 线性规划标准形式 1.1.2 线性规划典范形式 1.1.3 凸组合和凸锥组合 1.1.4 极点和极方向 1.1.5 线性规划可行域的表示 1.1.6 线性规划基本定理 1.1.7 基本解与基本可行解 1.1.8 关于“退化” 1.2 “判…

0. 简介

1. 单纯形算法解析

1.1 基本概念及原理解析

1.1.1 线性规划标准形式

1.1.2 线性规划典范形式

1.1.3 凸组合和凸锥组合

1.1.4 极点和极方向

1.1.5 线性规划可行域的表示

1.1.6 线性规划基本定理

1.1.7 基本解与基本可行解

1.1.8 关于“退化”

1.2 “判优”规则

1.3 “改进”规则

1.4 “初始点”确定方法

1.4.1 两阶段法

1.4.2 大M法

1.5 单纯形算法中的几个问题

1.6 单纯形算法计算步骤图

2 单纯形算法计算案例

3 参考资料

0. 简介

单纯形算法（simplex method）是求解线性规划模型的一种通用方法。

线性规划模型具有三个要素：

决策变量
目标函数
约束条件

线性规划模型具有这样的特点：

决策变量相互独立且连续变化
目标函数是线性函数
约束条件是线性不等式组

例：一个企业“生产计划”的线性规划模型如下

$\begin{align*} max \quad & z = 50x_1+80x_2\\ s.t. \quad & 0.5x_1 + 2x_2 \leq 40 \\ &x_1+1.5x_2 \leq 45\\ &x_1,x_2 \geq0 \end{align}$

$max$ 是指目标函数极大化，maximum的缩写，如果目标函数极小化则用 $min$ , minimize的缩写。 $s.t.$ 是subject to的缩写，表示受限制于，其后跟约束条件。上述模型中约束条件前两条表示资源约束，最后一条表示决策变量的非负约束。

一般来说，对于生产计划这类问题，可用如下线性规划模型近似表示

$\begin{align*} max \quad &\sum_{j=1}^{n}c_j x_j&\\ s.t. \quad &\sum_{j=1}^n a_{ij}x_j\leq b_i, i=1,2,\cdots ,m,&\\ &x_j \geq 0, j=1,2,\cdots ,n. \end{align}$

当然线性规划模型可以远比以上模型复杂，需要根据具体问题特征进行建模。下面介绍求解线性规划模型的单纯形算法。

1. 单纯形算法解析

单纯形算法遵循“初始点——判优——改进”的优化模式。我们首先讨论“判优”，然后讨论“改进”，最后讨论“初始点”。

1.1 基本概念及原理解析

为了方便后续的讨论，需要先了解一些线性规划的表示形式、可行域、以及线性规划可行解的刻画等内容

1.1.1 线性规划标准形式

定义1： 线性规划的标准形式（standard form）是指满足如下四个条件的线性规划模型：

（1）所有决策变量的取值是非负的；

（2）除决策变量非负约束外的其他约束是等式约束；

（3）模型中目标函数需要极大化（也可以要求极小化）；

（4）等式约束中常数项位于等号的右端（称为右端项，right hand side）

例：一个线性规划模型的标准形式

线性规划模型标准形式的一般表达为

线性规划模型标准形式的矩阵表达为

$\begin{align*} max \quad & z=\boldsymbol{c}^{\rm T}\boldsymbol{x}\\ s.t. \quad & \boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}\\ & \boldsymbol{x}\geq0 \end{}$

1.1.2 线性规划典范形式

定义2： 线性规划的典范形式（canonical form）是指满足如下四个条件的线性规划模型：

（1）所有决策变量的取值是非负的；

（2）除决策变量非负约束外的其他约束是等式约束，并且右端项是非负的；

（3）模型中目标函数需要极大化（也可以要求极小化）；

（4）在等式约束中存在一组与等式约束个数相等的决策变量，它们的系数构成系数矩阵的一个单位子矩阵。

例：一个线性规划模型的典范形式

线性规划模型典范形式的一般表达为

1.1.3 凸组合和凸锥组合

定义3： 给定 $m$ 个向量 $\boldsymbol{x^1,x^2,\cdots,x^m} \in \mathbb{R}^n$ 以及满足 $\sum_{i=1}^m \alpha_i =1$ 的非负实数 $\alpha_i \geq0, i=1,2,\cdots,m,$ 我们将向量 $\alpha_1 \boldsymbol{x^1}+\alpha_2 \boldsymbol{x^2}+\cdots+\alpha_m \boldsymbol{x^m}$ 称为 $\boldsymbol{x^1,x^2,\cdots,x^m}$ 的凸组合（convex combination），如果仅仅要求组合系数 $\alpha_i \geq0, i=1,2,\cdots,m,$ 那么向量 $\alpha_1 \boldsymbol{x^1}+\alpha_2 \boldsymbol{x^2}+\cdots+\alpha_m \boldsymbol{x^m}$ 称为 $\alpha_1 \boldsymbol{x^1}+\alpha_2 \boldsymbol{x^2}+\cdots+\alpha_m \boldsymbol{x^m}$ 的凸锥组合（convex conical combination）,也称为非负线性组合。

这里回顾一下线性规划的标准形式的矩阵表达式（这里我们要求目标函数极小化）

$\begin{align*} min \quad & z=\boldsymbol{c^{\rm{T}}x}\\ s.t. \quad & \boldsymbol{\rm{A}}\boldsymbol{x}=\boldsymbol{b}\\ & \boldsymbol{x}\geq \boldsymbol{0} \end{align}$

其中系数矩阵 $\boldsymbol{\rm{A}}\in\mathbb{R}^{m \times n}$ ，右端项 $\boldsymbol{b} \in \mathbb{R}^m$ ，目标函数的梯度向量 $\boldsymbol{c} \in \mathbb{R}^n$ ，决策变量 $\boldsymbol{x} \in \mathbb{R}^n$ 。线性规划的可行域实际上是由右端项 $\boldsymbol{b}$ 相对于系数矩阵 $\mathbf{A}$ 的列向量的凸锥组合系数 $\boldsymbol{x}$ 构成的。

定义4：设集合 $S \subseteq \mathbb{R}^n$ ，若 $\forall \boldsymbol{x}^1,\boldsymbol{x}^2 \in S$ 和 $\forall \alpha \in [0,1]$ ，有 $\alpha \boldsymbol{x}^1+(1-\alpha) \boldsymbol{x}^2 \in S$ ，则称 $S$ 为一个凸集（convex set）。