第2章线性规划

《第2章线性规划》由会员分享，可在线阅读，更多相关《第2章线性规划（158页珍藏版）》请在金锄头文库上搜索。

1、运 筹 学 课 件,线 性 规 划,Linear Programming,本章内容,线性规划问题的数学建模 图解法 单纯形法原理 单纯形法的计算步骤 Lingo软件求解,教学说明,教学目标：掌握LP的建模方法，熟练地使用单纯形法和Lingo软件求解LP问题 重点与难点：重点是LP的建模与解法；难点是单纯形法的原理 教学方法：配合课件和WinQSB软件，课堂讲授为主，案例研讨为辅 思考题、讨论题、作业：教材第1章习题 学时分配：8学时,线性规划的产生与发展,1939年苏联的经济学家康托洛维奇（.）在生产组织与计划中的数学方法一书中，首次用线性规划方法解决了生产组织与运输问题。 1947年美国数学

2、家G.B.Dantzig提出了线性规划的数学模型，并给出了求解该模型的单纯形法（Simplex method)。这标志着线性规划这一运筹学的重要分支的诞生。 计算机的发展促进了LP计算理论的发展，使其应用更加广泛和深入。,线性规划的应用范围,生产中的组织与计划问题 运输问题 合理下料问题 配料问题 生产布局问题 特点：在现有条件下，统筹安排，使总的经济效益最好，或者是总成本最省。,某工厂制造A、B两种产品，它们的原材料单位消耗、单位利润以及资源现有量如下表：问如何组织生产，使工厂获得最大利润？,例1：生产的组织与计划问题,产品,资源,资源消耗,11 线性规划的数学建模,建立数学模型步骤,1.假

3、设决策变量：设A、B两种产品各生产 个单位；,2.建立目标函数：利润函数是 ，求它的最大值，即,3.现有资源的限制条件：,4.决策变量必须有非负限制：,数学模型,目标函数,系统约束,非负限制,注意：目标函数和约束条件中变量的次数都是一次的，这样的模型称为线性规划数学模型。,生产计划安排问题的一般描述,资源,产品,消耗,资源现有量,单位产品利润,求解使工厂获得最大利润的生产方案。,生产计划安排问题的一般数学模型,解：设 表示生产产品 的单位数，则有如下的数学模型：,设有某种物资从A、B、C三个产地调出，运往甲、乙、丙三个需求地，其调运量及运价如下表。求运费最省的调运方案。,甲 乙 丙 调出量A

4、2 4 5 7B 1 3 4 4C 3 2 3 9调入量 6 8 6 （20）,调出,调入,运价,例2：运输问题,设 表示从i 地调往j 地的调运量,产销平衡运输问题的一般描述,产量,销量,产地,销地,运价,求解使运输总成本最低的方案。,设 表示从i 地调往j 地的调运量,产销平衡运输问题的一般模型,例3：合理搭载问题,某货船的前舱、中舱、后舱的载重分别为2 000吨、3 000吨、1 000吨，容积分别为100 000立方米、135 000立方米、30 000立方米；顾客托运的货物A、B、C的重量、体积、运费等资料已知。为了保持货船的稳定，要求三个货舱载货率必须平衡。问如何装载，使收入最大？

5、,例4：连续投资问题,某地区今后三年内可以有A、B、C、D四个项目的投资选择，总资金量为3000万元。其中项目A在三年内每年年初投资，当年年底可回收本利和为120；项目B第一年年初投资，第二年年底可回收本利和为150，但投资额不超过2000万元；项目C第二年年初投资，第三年年底可回收本利和为160，但投资额不超过1500万元；项目D第三年年初投资，当年年底可收回本利和为140，投资额不超过1000万元。问如何安排投资，使第三年年底本利和的金额最大？,12 线性规划问题解的性质, 两个变量的线性规划问题的图解法 几个基本概念： 满足所有约束条件的解称为LP问题的可行解；所有可行解的集合称为可行解

6、集。 使目标函数达到最优的可行解称为LP问题的最优解。,问题：线性规划是一个带有约束条件的极值问题，能否用微积分方法求解?,例1：用图解法求解下面的LP问题,目标函数等值线,此点为LP的最优解,max S,min S,得到这个最优解：,本问题有唯一最优解。,例2 ：用图解法解下面的线性规划,目标函数等值线,max S,min S,得到LP的最优解及目标函数最优值：,除A、B两个最优解外，AB线段上的所有点都是LP的最优解。本问题有无穷多最优解。,例3：用图解法解下面的线性规划,无界的可行解集,此题有可行解， 但无最优解,max S,min S,例4：用图解法解下面的线性规划,无可行解,本题无可

7、行解，更无最优解,有唯一最优解，这个最优解一定在可行解集合的某一顶点上达到； 有无穷多最优解，最优解充满一个线段，可以用它的两个端点作为代表； 有可行解，但无最优解； 无可行解。,小结：LP图解法有如下四种情况,线性规划问题解的关系,线性规划 问题的解,无可行解有可行解,唯一最优解,无最优解,有最优解,无穷多最优解, 线性规划问题的标准形式,将一般的LP转化为LP标准形：,规定:, 求目标函数的最大值为标准形，即目标函数为maxS 。如果问题是求 minS 时，可令 求 ，相当于求minS 。,规定:, 以等式约束为标准形。设第k 个等式为,(3) LP中所有的变量都有非负限制。如果实际问题中

8、的LP里某个变量无非负限制，可如下处理:(4) 若约束条件为等式，但右端项为负值，则在等式两边同时乘以-1即可,规定:,根据以上的规定，LP的标准形为：,两种缩写形式：,矩阵表示法：,将下列线性规划模型化为标准形,3. LP问题解的性质, 几个概念 凸集：若连接n维点集S 中任意两点 的线段仍在S 内，则称S 为凸集。即,凸集,凸集,不是凸集,极点, 极点：若凸集S 中的点x，不能成为S 中任何线段的内点，则称x为S 的极点。, 设 为LP的一个可行解，若或 的非零分量对应的A中列向量线性无关，则称它为基础可行解。由这些列向量组成的矩阵称为基矩阵，与这些列向量对应的变量称为基变量，其余的变量称

9、为非基变量。,使目标函数值达到最优值的可行解称为最优解；使目标函数达到最优值的基础可行解称为基础最优解。,可行解集,基础可行解,最优解,基础最优解,线性规划解的关系,目标函数,约束条件,行列式0 基矩阵,右边常数,=, 几个重要定理（单纯形法的理论依据）,定理1 线性规划问题的可行解集为凸集，即连接线性规划问题任意两个可行解的线段上的点仍为可行解。,定理2 可行解集S 中的点x是极点的充要条件是x为基础可行解（简单地说，凸多边形的顶点就是基础可行解）。,定理3 线性规划的目标函数的最优值，一定可在极点上达到。,13 单纯形方法(Simplex method),单纯形法的解题思路：, 用消去法解

10、LP问题,解：引入松弛变量 将其化为标准形式,2. 单纯形方法理论推导,设A是 的矩阵，且R(A)=m （m0,40,10,换出行,将3化为1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,乘以3/5后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,Z=0,Z=40,Z=70,单纯形法的计算步骤,学习要点：1. 线性规划解的概念以及3个基本定理2. 熟练掌握单纯形法的解题思路及求解步骤,例2 用单纯形法解线性规划,解：（1）化为标准形,（2）填写单纯形表：,检验数,(3)换基迭代 检验数有两种情况： 所有检验数小

11、于等于零，则基B 已是最优基，得到最优表及最优解，停止计算； 有某些检验数为正值，此表不是最优表即基B 不是最优基，则应进行换基迭代。,换基迭代的步骤：,.选取入基变量：设 则相应的非基变量 为入基变量，简称“入基”。如果j 不唯一，可选取较大的 值对应的非基变量入基。,.求主元素并确定出基变量：观察在入基变量 所对应的 中的第j 列，如果该列所有的分量均小于等于零，则该LP问题无最优解（定理）。如果该列存在正分量，则以这些正分量为分母，以这些正分量所在行中对应的基变量取值为分子，求出这些比值中的最小值，该最小值对应的基变量为出基变量，简称“出基”，出入基交叉点上的元素称为主元素或轴心项，用方

12、框将其框起来。这种求出基变量的方法称为 法则。,.换基迭代：利用矩阵的初等变换，将主元素变为1，将其所在列的其余元素变为0，得一张新单纯形表。重复上述步骤，经过有限次换基迭代，一定可得到最优解。,该表检验数全部小于等于零，称此表为最优表。其结果表示如下：,问题:表1中我们选取了 入基,如果选取 入基结果又如何呢?,路径1,路径2,结论：1.每一个单纯形表对应一个极点， 表一对应黄点；表二对应绿点；表三对应蓝点。 2.一般来说，路径不同，迭代次数可能不同。,(1)如果单纯形表中的基变量取值皆为正数，称这个基可行解为非退化解。若LP的所有基可行解都是非退化的，则LP经过有限次迭代可达到最优. (2)如果单纯形表中的基变量取值有的为零时，称为LP的退化解，此时称LP是退化的，理论上认为这种线性规划在迭代过程中可能产生循环，从而得不到最优解。为避免循环，常采用1976年R.G.Bland提出Bland法则：a.单纯形表中有若干个检验数 时，取下标号小的非基变量入基； b. 用 法则选取出基变量时，若比值相同，则选取下标号小的基变量出基。,