线性规划

线性规划

用线性规划的方法可以解决这一类的问题:可以表述问题为最大化或最小化某一个目标,其中包含的资源有着约束条件,而目标和约束条件都可以用线性函数来表示。

CLRS中介绍了解决线性规划的方法—单纯形算法。其中精妙的地方包括:

1.将线性规划转换为标准型。

这里有4种原因使得线性规划不是标准型:
* 目标函数可能是一个最小化,不是最大化
* 可能有的变量不具备非负性约束
* 可能有等式约束
* 可能有大于等于的约束

转换的基本方法就是:
如果是最小化,那么乘-1转换
如果是非负性,那么用x’-x”,并限制x’>=0, x”>=0来替换原有的x
如果是等式,就用>=0&&<=0来替换

经过这些巧妙的转换,就可以变为标准型了。

2.单纯形算法的基本原理就是主元的替换,那么问题就是定义谁是主元,谁被换入。

其基本思想为:
* 主元的选择是选择把目标中为正的项
* 换入的选择是在限制条件中,放大主元,选择其中最紧的约束,它限制了主元可以增大多少

3.对偶性

找到了一个方法,把原有的最大化问题转化为最小化问题,而最大化问题和最小化问题相等的时候,是最优化的解。进一步的,证明单纯型法得出的解满足对偶性,那么单纯型算法的解就是最优解。

Leave a Reply

Your email address will not be published. Required fields are marked *