线性规划与单纯形法.ppt

《线性规划与单纯形法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划与单纯形法线性规划（LP：LinearProgramming）规划论中的静态规划解决有限资源的最佳分配问题求解方法：图解法单纯形解法线性规划简介1939年苏联的康托洛维奇（H.B.Kahtopob）和美国的希奇柯克（F.L.Hitchcock）等人就在生产组织管理和制定交通运输方案方面首先研究和应用一线性规划方法。1947年旦茨格等人提出了求解线性规划问题的单纯形法，为线性规划的理论与计算奠定了基础。随着电子计算机的出现和日益完善，规划论得到迅速的发展，可用电子计算机来处理成千上万个约束条件和变量的大规模线性规划问题，从解决技术问题的最优化，到工

2、业、农业、商业、交通运输业以及决策分析部门都可以发挥作用。线性规划问题的三个要素决策变量决策问题待定的量值称为决策变量。决策变量的取值要求非负。约束条件任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。约束条件是决策方案可行的保障。LP的约束条件，都是决策变量的线性函数。目标函数衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。有的目标要实现极大，有的则要求极小。1线性规划问题及其数学模型例某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时和原料A、B的消

3、耗量如下表。该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排生产计划能使该厂获利最多？这个问题可以用下面的数学模型来描述，设计划期内产品Ⅰ、Ⅱ的产量分别为x1，x2，可获利润用z表示，则有：MaxZ=2x1+3x2x1+2x2≤84x1≤164x2≤12x1,x2≥01.1问题的提出又例靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，两工厂之间有一条流量为每天200万m3的支流（见图）。第一化工厂每天排放污水2万m3，第二化工厂每天排放污水1.4万m3。污水从工厂1流到工厂2前会有20%自然净化。根据环保要求

4、，河水中污水的含量应不大于0.2%。而工厂1和工厂2处理污水的成本分别为1000元/万m3和800元/万m3。问两工厂各应处理多少污水才能使处理污水的总费用最低？设工厂1和工厂2每天分别处理污水x1和x2万m3，则有：Minz=1000x1+800x2(2-x1)/500≤0.002[0.8(2-x1)+1.4-x2]/700≤0.002x1≤2,x2≤1.4x1,x2≥0以上两例都有一些共同的特征：⑴用一组变量表示某个方案，一般这些变量取值是非负的。⑵存在一定的约束条件，可以用线性等式或线性不等式来表示。⑶都有一个要达到的目标，可以用决策变量的线性函数

5、来表示。满足以上条件的数学模型称为线性规划模型。线性规划模型的一般形式如下：其中：cj为价值系数；aij为技术系数；bi为限额系数；xj为非负变量图解法即是用图示的方法来求解线性规划问题。一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。1.2线性规划的图解法可行域的确定例:数学模型为maxZ=3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.x1=82x2=123x1+4x2=36x1x248123690ABC(4,6)D五边形OABCD内(含边

6、界)的任意一点(x1，x2)都是满足所有约束条件的一个解，称之可行解。满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。最优解的确定Z=30Z=42Z=15目标函数Z=3x1+5x2代表以Z为参数的一族平行线。x1=82x2=123x1+4x2=36x1x248123690ABC(4,6)D等值线：位于同一直线上的点的目标函数值相同。最优解：可行解中使目标函数最优(极大或极小)的解由线性不等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。可行域有有限个顶点。设规划问题有n个变量，m个约束，则顶点的个

7、数不多于Cnm个。目标函数最优值一定在可行域的边界达到，而不可能在其内部。几点说明解的可能性x1=82x2=123x1+4x2=36x1x248123690ABC(4,6)D上例的数学模型变为maxZ=3x1+4x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.Z=24Z=36Z=12唯一最优解：只有一个最优点。多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）例如maxZ=3x1+2x2-2x1+x2≤2x

8、1-3x2≤3x1≥0,x2≥0-2x1+x2=2x1-3x2=3x2123-