最优化理论与方法(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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。