数学建模与线性规划模型 .pptVIP

线 性 规 划 运筹学中应用最广泛的方法之一。 运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的。 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。 引 言 历史悠久 理论成熟 应用广泛 1939 KOHTOPOBUZ “生产组织与计划中的 数学方法” “解乘数法” 1947 DANTZIG 人员轮训 任务分配 美国科学院院士 “单纯形法” 1960 “最佳资源利用的经济计算” 康托洛维奇和库伯曼斯(Koopmans)因对资源最优分配理论的贡献而获1975年诺贝尔经济学奖。 60-70年代 计算机 50约束 100变 30000约束 3000000变量 冯?诺伊曼(Von Neuman)和摩根斯坦(Morgenstern)1944年发表的 《对策论与经济行为》涉及与线性规划等价的对策问题及线性规划对偶理论 从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中比较著名的还有Simon，Samullson，Leontief，Arrow，Miller等 研究对象 有一定的人力、财力、资源条件下，如何合理安排使用，效益最高 某项任务确定后，如何安排人、财、物，使之最省 线性规划问题及其数学模型 问题的提出(二) 问题的提出(三) 图解法 线性规划问题的标准型 线性规划问题的标准型 max z=c1x1+c2x2+?+cnxn a11x1+a12x2+?+a1nxn=b1 a21x1+a22x2+?+a2nxn=b2 ?????????? am1x1+am2x2+?+amnxn=bm x1, x2, ?, xn≥0 其中，bi≥0 (i=1,2,?,m) 不符合标准型的几个方面： 线性规划问题的求解——单纯形法 基本概念 单纯形法(一) 要找到线性规划问题的最优解，只要在基本可行解中寻找就可以了。虽然基本可行解的数目是有限个（不超过Cnm个），但当m,n较大时，要用“穷举法”求出所有基本可行解也是行不通的。因此，必须寻求一种更有效的方法。 单纯形法的基本思路是：从线性规划问题的一个基本可行解开始，转换到另一个使目标函数值增大的基本可行解。反复迭代，直到目标函数值达到最大时，就得到了最优解。 为了便于单纯形法的实施，我们用单纯形表来描述线性规划问题的一个基本可行解的情况。 不妨设x1,x2,…,xm组成一组基变量，且对应一个基本可行解。用高斯消去法把等式约束和目标函数变形为 x1 +a1m+1xm+1+…+a1nxn=b1 x2 +a2m+1xm+1+…+a2nxn=b2 …　 ……………………… xm+amm+1xm+1+…+amnxn=bm -z +σm+1xm+1+…+σnxn= -z0 把其系数列成数据表即单纯形表: 单纯形法(二) 按照单纯形法的思路求解线性规划问题, 要解决三个技术问题:⑴给出第一个基本可行解; ⑵检验一个基本可行解是否是最优解; ⑶转换到另一个基本可行解. ⑴把线性规划问题变成标准型后, 观察是否每个约束方程中都有独有的、系数为1的变量. 如果是,则取这些变量作为基变量,便得到一个基本可行解; 否则,就给没有这种变量的约束条件添加一个人工变量,同时修改目标函数. (见例题) ⑵如果单纯形表最后一行中的σj都满足 σj≤0, 则对应的基本可行解是最优解; 否则就不是最优解. σj称为检验数. ⑶第一,确定换入变量. 在大于0的检验数中找最大的为σk, 对应变量xk为换入变量. 第二,确定换出变量. 取θ=min{bi/a‘ik|a’ik0}=bl/a’lk, 对应的第l行的基变量为换出变量. 第三, 旋转运算. 换入变量所在的行与换出变量所在的列交叉点的元素称为中心元素,用高斯消去法把中心元素化成1, 同列的其他