北京交通大学经济管理学院nics and ManagomentSchool of EconoBaijingJiaotongUniversity管理运筹学华国伟Email:huaguowei@gmail.com北京交通大学经管学院物流管理系
管理运筹学 华国伟 Email:huaguowei@gmail.com 北京交通大学经管学院物流管理系
北京交通大学经济管理学院nics and ManagomentSchool of EconoBaijing Jiaotong University第一章线性规划(LinearProgramming)LPbituor@163.com密码：100044
第一章 线性规划 ( Linear Programming) LP bjtuor@163.com 密码: 100044
北京交通大学经济管理学院提纲nicsandManagomentStingstongount1．迭代法单纯形法2.问题的提出图解法线性规划问题的标准形式线性规划问题解的概念3.单纯形法的计算步骤基本概念几个定理北京交通大学
提 纲 1. 迭代法 2. 单纯形法 • 问题的提出 • 图解法 • 线性规划问题的标准形式 • 线性规划问题解的概念 3. 单纯形法的计算步骤 • 基本概念 • 几个定理
北京交通大学经济管理学院选代法SchoolagemenBoijingJiaotongUni·迭代法---iterative迭代是反复的意思，指循环执行、反复执行、迭代法是通过从一个初始解出发，不断用变量的旧值递推新值的过程.(改进当前解)·迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或步骤进行重复执行，在每次执行这组指令(或步骤时，都从变量的原值推出它的一个新值北京交通大学
一、迭代法 • 迭代法-iterative • 迭代是反复的意思, 指循环执行、反复执行. • 迭代法是通过从一个初始解出发, 不断用变 量的旧值递推新值的过程. (改进当前解) • 迭代算法是用计算机解决问题的一种基本方 法, 它利用计算机运算速度快、适合做重复 性操作的特点, 让计算机对一组指令(或步骤) 进行重复执行, 在每次执行这组指令(或步骤) 时, 都从变量的原值推出它的一个新值
北京交通大学经济管理学院School of EoicsandManagomentBojingJiaotong University·跟迭代法相对应的是直接法(一次解法)即一次性解决问题·一般如果可能，直接解法总是优先考虑的但当遇到复杂问题时,特别是在未知量很多，无法找到直接解法,这时可以通过迭代法求解.北京交通大学
• 跟迭代法相对应的是直接法(一次解法), 即一次性解决问题. • 一般如果可能, 直接解法总是优先考虑的. 但当遇到复杂问题时,特别是在未知量很多 , 无法找到直接解法,这时可以通过迭代法 求解
北京交通大学经济管理学院School of EosagemenBojingJiaotongUnive·最常见的迭代法是牛顿法，其他还包括最速下降法、共轭迭代法、变尺度迭代法、最小二乘法、单纯形法、遗传算法、模拟退火等等.·迭代算法的步骤：1.确定迭代变量---由旧值递推出新值的变量2.建立迭代关系式--从变量的前一个值推出下一个值的公式（或关系）3.对迭代过程进行控制---在什么时候结束迭代过程北京交通大学
• 最常见的迭代法是牛顿法. 其他还包括最速 下降法、共轭迭代法、变尺度迭代法、最 小二乘法、单纯形法、遗传算法、模拟退 火等等. • 迭代算法的步骤： 1.确定迭代变量-由旧值递推出新值的变量 2.建立迭代关系式-从变量的前一个值推出下一 个值的公式(或关系) 3.对迭代过程进行控制 -在什么时候结束迭 代过程
北京交通大学经济管理学院2.单纯形法School of Ecorics andManagomentBoijingJiaotongUniversity一、单纯形指0维中的点一维中的线段.二维中的三角形三维中的四面体.·n维空间中具有n+1个定点的多面体北京交通大学
2. 单纯形法 • 一、单纯形 指0维中的点,一维中的线段,二维中的三角形, 三维中的四面体,···, n维空间中具有n+1个定点 的多面体
北京交通大学单纯形法(Simplexmethod)-经济管理学院ochooagementBoiingJiacotongUniy的基本思想：①由LP解的性质：若有最优解，必在其可行域的顶点处达到，那么若对可行域的所有顶点进行比较，就可找出其最优解.但问题规模较大时，该做法计算量太大，不实用①单纯形法克服了这一缺点.它缩小了搜索顶点的范围：首先确定一个顶点，由此顶点出发转到下一顶点,并要求新顶点的目标函数值比前一顶点处的更优北京交通大学
二、单纯形法(Simplex method) 的基本思想： Ø由LP解的性质：若有最优解, 必在其可行域 的顶点处达到. 那么若对可行域的所有顶点 进行比较, 就可找出其最优解. 但问题规模较 大时, 该做法计算量太大, 不实用. Ø单纯形法克服了这一缺点. 它缩小了搜索顶 点的范围: 首先确定一个顶点, 由此顶点出发 转到下一顶点,并要求新顶点的目标函数值比 前一顶点处的更优
北京交通大学单纯形法(Simplex method)二、经济管理学院School of EcoiosandManagomentBojing Jiaotong University的基本思想：对于一个标准型LP问题，从一个初始基可行解出发，判断其是否为最优解，若是则结束；否则求一个与其“相邻”的、改进的基可行解。再判断这个解是否最优，若是则结束，否则再求一个改进的基可行解，…，直至得到一个基最优解，或者判定它无界（或无解）。北京交通大学
对于一个标准型 LP 问题，从一个初始基可行 解出发，判断其是否为最优解，若是则结束；否则 求一个与其“相邻”的、改进的基可行解。再判断 这个解是否最优，若是则结束，否则再求一个改进 的基可行解，.，直至得到一个基最优解，或者 判定它无界（或无解）。 二、单纯形法(Simplex method) 的基本思想：
北京交通大学经济管理学院School of EoicsandManagomentBojing Jiaotong University①单纯形法步骤：首先将模型一般形式变成标准形式,再根据标准形式,从可行域中找一个初始顶点,并判断是否最优.如果是，得最优解:如果不是,转换到另一个顶点,并使得新顶点处自标函数值更优①要解决的问题--找初始顶点？判断最优?转换到另一顶点?北京交通大学
Ø单纯形法步骤：首先将模型一般形式变成 标准形式,再根据标准形式,从可行域中找一 个初始顶点,并判断是否最优.如果是, 得最 优解;如果不是,转换到另一个顶点,并使得 新顶点处目标函数值更优. Ø要解决的问题-找初始顶点?判断最优?转换 到另一顶点?