算法设计与分析——线性规划——单纯形算法

算法设计与分析——线性规划——单纯形算法

引用

CSDN

1.

https://blog.csdn.net/Blackoutdragon/article/details/117772833

单纯形算法是线性规划中一种重要的求解方法，通过迭代优化逐步逼近最优解。本文将详细介绍单纯形算法的基本概念、核心思想和具体步骤，并通过实例演示算法的操作过程。

题目描述

基本知识

• 基本可行解：约束条件中，某个约束以等号满足的可行解称为线性规划问题的基本可行解。

• 线性规划的基本定理：

• 如果线性规划有基本最优解，则其必定是基本可行解。

• 注意：基本可行解不一定是基本最优解，但是基本最优解，一定是基本可行解。

单纯形算法的基本概念

• 特点：

• 只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加。

• 一般经过不大于m或者n次迭代就可以求得最优解（m等式的数量，n是变量的数量）。

• 标准线性规划问题：当线性规划问题中没有不等式约束，而只有等式约束和变量非负约束，称该线性规划问题具有标准形式。

• 约束标准型线性规划问题：标准形式的基础上，每一个等式约束中至少有一个变量的系数为正，且这个变量只在该约束中出现，这样的变量称为左端变量或者基本变量。

• 基本变量：符号为正，并且仅仅在一个等式中出现。

• 注意：任意一个线性规划问题都可以转换为约束标准星线性规划问题。

基本思想

• 将所有非基本变量都置为0，解出基本变量的值就能得到一个基本可行解。
• 注意：该基本可行解，不一定是最优解。
• 从基本可行解出发，进行一系列的基本可行解变换，求出其他的基本可行解。
• 最大的即为目标解。

具体步骤

第一步：生成一个初始单纯形表

纵坐标是基本可行解，横坐标是非基本可行解，具体的值是对应到对应约束式的系数。

注意，化成右侧的式子再进行填表

第二步：选出使目标函数增加的非基本变量作为入基变量

选择标准：z行中的正系数非基本变量都满足要求，选择Z行整数对应的非基本变量即可。

第三步：选出一个基本变量作为离基变量

• 出发点：我们希望入基变量越大越好，但是入基变量受基本变量的影响，所以我们要找到对入基变量有影响的变量进行更改。
• 选择标注：比较入基变量和基本变量的符号关系，以及大小关系。
• 符号选择：
• 入基变量所在的列与基本变量所在的行交叉处元素为负数；该元素无限制，不选
• 入基变量所在列全部都为负数，那么目标函数无界，得到问题的无界解。
• 入基变量所在列中有多个元素是正数，选择限制最大的基本变量作为离基变量（将最左边的常数列除以交叉值，就为最终的结果）。

第四步：转轴变换

横竖兑换

• 解离基变量所对应的方程，将入基变量用离基变量表示，再将其带入其他的基本变量和所在行消去其中的入基变量。生成新的单纯形表
• 离基变量对于入基变量的影响最大，限制了入基变量的增加，离基变量等于零的时候，即最小的时候，入基变量最大

第五步：转回并重复第一步

进一步改进目标函数值。不断重复上述过程，直到Z行所有的非基本变量系数都变成负值为止。

• 这一步已经新生成了一个单纯形表格，如下。目标式子中，不完全都是自变量了，还有常数。
• 下述步骤是对上述三个步骤的重复
• 在表上找一横
• 一横上找一竖
• 横竖交叉，进行交换
• 所以最大值为11

分析与总结

这个方法操作起来很简单，也很有效，考试的一个大题，不看也得看了！
最终的记忆口诀：“找一横，找一竖，横竖交叉，找一焦点”。