最优化理论与方法（2）---单纯形方法

2023-12-23 18:39:38

文章目录

1. 线性规划

1.1 基本介绍

在这里插入图片描述

?把握住两点：最小化和等号。
?如果问题是最大化max，则加负号，求其最小就是原来的最大。
?如果约束条件是不等式，则需要加入松弛变量。 ≤ ≤ ≤ 则需要加上松弛变量； ≥ ≥ ≥ 则需要减去松弛变量；比如下面这个例子：

在这里插入图片描述

在这里插入图片描述

1.2 最优基本可行解

?从代数的角度考虑如下：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

2. 表格形式单纯形方法

2.1 基本知识引入

?注：因为 X N X_N XN? 最后我们取为 0 0 0，所以 C B B ? 1 b C_BB^{-1}b CB?B?1b 是目标取值。

在这里插入图片描述

在这里插入图片描述

2.2 求解步骤

?1. 最终的单纯形表格，所有的判别数都小于 0 0 0，基变量 B ? 1 b B^{-1}b B?1b 都大于0。

?2. 先选进基变量，再选离基变量。方法：找出判别数为正的列(进基变量)；用最后一列与前面列进行比值，找比值为正且最小的(离基变量)；之后进行主元消去一行一行计算就可。

2.3 例题1

在这里插入图片描述
在这里插入图片描述

2.4 例题2

在这里插入图片描述

3. 单纯形法的进一步讨论

3.1 无界解

在这里插入图片描述

在这里插入图片描述

3.2 多个解

在这里插入图片描述

在这里插入图片描述

文章来源:https://blog.csdn.net/m0_62881487/article/details/135140199
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。