数学建模线性规划模型.ppt

《数学建模线性规划模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、线性规划运筹学中应用最广泛的方法之一。运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。引言历史悠久理论成熟应用广泛1939KOHTOPOBUZ“生产组织与计划中的数学方法”“解乘数法”1947DANTZIG人员轮训任务分配美国科学院院士“单纯形法”1960“最佳资源利用的经济计算”康托洛维奇和库伯曼斯(Koopmans)因对资源最优分配理论的贡献而获1975年诺贝尔经济学奖。60-70年代计算机50约束100变30000约束3000000变量冯•诺伊曼(VonNeuman)和摩

2、根斯坦(Morgenstern)1944年发表的《对策论与经济行为》涉及与线性规划等价的对策问题及线性规划对偶理论从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中比较著名的还有Simon，Samullson，Leontief，Arrow，Miller等研究对象有一定的人力、财力、资源条件下，如何合理安排使用，效益最高某项任务确定后，如何安排人、财、物，使之最省线性规划问题及其数学模型例某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时和原料A、B的消耗量如下表。该工厂每生产一件产品Ⅰ可获利

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

4、水的成本分别为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、：图解法唯一最优解无穷多最优解x1x2x1x2解无界无可行解线性规划问题如果有最优解,则最优解一定在可行域的边界上取得,特别地,一定可在可行域的顶点上取得.线性规划问题的标准型线性规划问题的标准型maxz=c1x1+c2x2++cnxna11x1+a12x2++a1nxn=b1a21x1+a22x2++a2nxn=b2am1x1+am2x2++amnxn=bmx1,x2,,xn≥0其中，bi≥0(i=1,2,,m)不符合标准型的几个方面：令xj=xj-xj，对模型中的进行变量代换。⑴目标函数为minz=c1x1+c2x2++cnxn令z=-z,变

6、为maxz=-c1x1-c2x2--cnxn⑵约束条件为a11x1+a12x2++a1nxn≤b1加入非负变量xn+1，称为松弛变量，有a11x1+a12x2++a1nxn+xn+1=b1⑶约束条件为a11x1+a12x2++a1nxn≥b1减去非负变量xn+1，称为剩余变量，有a11x1+a12x2++a1nxn-xn+1=b1⑷变量xj无约束。线性规划问题的求解——单纯形法基本概念可行解满足约束条件（包括非负条件）的一组变量值，称可行解。所有可行解的集合称为可行域。最优解使目标函数达到最大的可行解称为最优解。基本解对于有n个变量、m个约束方程的标准型线性规划问题，取其m

7、个变量。若这些变量在约束方程中的系数列向量线性无关，则它们组成一组基变量。确定了一组基变量后，其它n-m个变量称为非基变量。令非基变量都为0，解约束方程，可唯一得到基变量的值，从而得到一个满足约束方程的解，称为基本解。由此可见，一个基本解的非零分量个数不超过m个。基本可行解满足非负条件的基本解称为基本可行解。基本可行解既是基本解、又是可行解，它对应于线性规划问题可行域的顶点。单纯形法(一)要找到线性规划问题的最优解，只要在基本可行解中寻找就可以