理论

基本思想

一个简单的问题线性规划就是要找到最大(或最小)值的简单吗函数受到一定的约束。一个例子可能是一个工厂生产两种商品。在任何生产运行,工厂生产x₁第一个类型和x₂第二。如果利润在第二种类型是在第一个两次,然后x₁+ 2x₂代表了总利润。这个函数x₁+ 2x₂被称为目标函数。

显然,如果工厂将其最高利润将整个生产能力第二种类型的商品。然而,在实际情况下,这是不可能的;一组约束等因素引入的可用性的机器时间,劳动力和原材料。例如,如果第二种类型的商品需要的原材料是有限的,这样可以在不超过5批,然后x₂必须小于或等于5;也就是说,x₂≤5。如果第一个商品需要另一种类型的材料限制八每批,然后x₁≤8。如果x₁和x₂花同等的时间和机器时间可以允许最多10在一个批处理,x₁+x₂必须小于或等于10;也就是说,x₁+x₂≤10。

其他两个约束是,x₁和x₂每个必须大于或等于零,因为它是不可能让一个负数;也就是说,x₁≥0和x₂≥0。问题是要找到的值x₁和x₂的利润是最大的。任何解决方案都可以用一对数字(x₁,x₂);例如,如果x₁= 3,x₂= 6,解决方案是(3、6)。这些数字可以表示为点标注在两个轴,如图所示图。在这图沿水平轴代表的距离x₁,沿着垂直的代表x₂。因为上面给出的约束,可行的解决方案必须属于某个明确的区域图。例如,约束x₁≥0意味着点代表可行的解决方案或右边的撒谎x₂轴。同样,约束x₂≥0意味着他们还躺在以上x₁轴。整个组约束的应用给出了可行解集,由一个多边形由有界的交叉线x₁= 0,x₂= 0,x₁= 8,x₂= 5,x₁+x₂= 10。例如,三件商品的生产x₁和四个的x₂是一个可行的解决方案从点(3,4)位于这一地区。找到最好的解决方案,但是,目标函数x₁+ 2x₂=k在图上绘制一些吗价值的k说,k= 4。这个值是由破碎的表示行在图中。作为k增加,产生一系列平行线的行吗k= 15只接触约束集在点(5,5)。如果k进一步增加,的值x₁和x₂会之外的可行的解决方案。因此,最好的解决方案是,在每个商品的数量相等。这并非巧合出现最优解在一个顶点,或“该地区的极端点,”。这永远是适用于线性问题,虽然可能不是最优的解决方案独特的。因此,解决这些问题可以减少寻找这极端点(点)收益率为目标函数最大的价值。