运筹学单纯形法

In Class

这学期修了门选修,讲到这个算法,觉得挺有意思,写写笔记 我们知道,如果线性规划有有限的最优解,那么该最优解一定可以在可行域的顶点上取到。 单纯形法便是从初始顶点开始,通过最优性判别准则判断,若不是最优,则转移到新顶点迭代,新顶点的目标值必然优于上一个,直到找到最优值停止迭代。 可行域的顶点称作基本可行解 下面开始介绍单纯形法的迭代步骤 1.化标准型 把不等式约束改成等式约束 基变量: x3 , x4 , x5 —→只出现在其中一个方程且系数为1 非基变量:x1 , x2 基本可行解: X=(x1,x2,x3,x4,x5)T —→非基变量取值全为0的可行解 初始基本可行解:X0=(0,0,6,12,2)T 非退化基本可行解:基变量都大于0的基本可行解 退化基本可行解:至少有一个基变量等于0的基本可行解 2.单纯形表 介绍一下该表的各值:…