第2章线性规划

第 1页夫运筹帷幄之中决胜于千里之外运 筹 学 课 件线 性 规 划Linear Programming第 2页本章内容o 线性规划问题的数学建模o 图解法o 单纯形法原理o 单纯形法的计算步骤o Lingo软件求解第 3页教学说明o 教学目标 ：掌握 LP的建模方法，熟练地使用单纯形法和 Lingo软件求解 LP问题o 重点与难点 ：重点是 LP的建模与解法；难点是单纯形法的原理o 教学方法 ：配合课件和 WinQSB软件，课堂讲授为主，案例研讨为辅o 思考题、讨论题、作业 ：教材第 1章习题 o 学时分配 ： 8学时 第 4页线性规划的产生与发展o 1939年苏联的经济学家康托洛维奇（.） 在 生产组织与计划中的数学方法 一书中，首次用线性规划方法解决了生产组织与运输问题。o 1947年美国数学家 G.B.Dantzig提出了线性规划的数学模型，并给出了求解该模型的单纯形法（Simplex method)。这标志着线性规划这一运筹学的重要分支的诞生。o 计算机的发展促进了 LP计算理论的发展，使其应用更加广泛和深入。第 5页线性规划的应用范围o 生产中的组织与计划问题o 运输问题o 合理下料问题o 配料问题o 生产布局问题 特点：在现有条件下，统筹安排，使总的经济效益最好，或者是总成本最省。某工厂制造 A、 B两种产品，它们的原材料单位消耗、单位利润以及资源现有量如下表：问如何组织生产，使工厂获得最大利润？例 1： 生产的组织与计划问题A B 资 源 现 有量（吨）钢 材 2 3 600煤 2 1 400单 位利 润（万元）20 5产品资源资源消耗1 1 线性规划的数学建模第 7页建立数学模型步骤1.假设决策变量：设 A、 B两种产品各生产个单位；2.建立目标函数：利润函数是 ，求它的最大值，即3.现有资源的限制条件：4.决策变量必须有非负限制：第 8页数学模型目标函数系统约束非负 限制 注意：目标函数和约束条件中变量的次数都是一次的，这样的模型称为线性规划数学模型。第 9页生产计划安排问题的一般描述资源产品消耗资源现有量单位产品利润求解使工厂获得最大利润的生产方案。第 10页生产计划安排问题的一般 数学模型解：设 表示生产产品的单位数，则有如下的数学模型：第 11页设有某种物资从 A、 B、 C三个产地调出，运往甲、乙、丙三个需求地，其调运量及运价如下表。求运费最省的调运方案。甲 乙 丙 调出量A 2 4 5 7B 1 3 4 4C 3 2 3 9调入量 6 8 6 （ 20）调出调入运价例 2：运输问题第 12页设 表示从 i 地调往 j 地的调运量第 13页产销平衡运输问题的一般描述产量销量产地销地运价求解使运输总成本最低的方案。第 14页设 表示从 i 地调往 j 地的调运量产销平衡运输问题的一般模型例 3：合理搭载问题o 某货船的前舱、中舱、后舱的载重分别为 2 000吨、 3 000吨、 1 000吨，容积分别为 100 000立方米、 135 000立方米、 30 000立方米；顾客托运的货物 A、 B、 C的重量、体积、运费等资料已知。为了保持货船的稳定，要求三个货舱载货率必须平衡。问如何装载，使收入最大？例 4：连续投资问题o 某地区今后三年内可以有 A、 B、 C、 D四个项目的投资选择，总资金量为 3000万元。其中项目 A在三年内每年年初投资，当年年底可回收本利和为120；项目 B第一年年初投资，第二年年底可回收本利和为 150，但投资额不超过 2000万元；项目 C第二年年初投资，第三年年底可回收本利和为 160，但投资额不超过 1500万元；项目 D第三年年初投资，当年年底可收回本利和为 140，投资额不超过 1000万元。问如何安排投资，使第三年年底本利和的金额最大？第 19页1 2 线性规划问题解的性质 两个变量的线性规划问题的图解法几个基本概念： 满足所有约束条件的解称为 LP问题的可行解；所有可行解的集合称为可行解集。 使目标函数达到最优的可行解称为 LP问题的最优解。 问题：线性规划是一个带有约束条件的极值问题，能否用微积分方法求解 ?第 20页例 1：用图解法求解下面的 LP问题目标函数等值线此点为 LP的最优解max Smin S第 21页得到这个最优解： 本问题有唯一最优解。第 22页例 2 ：用图解法解下面的线性规划目标函数等值线max Smin S第 23页得到 LP的最优解及目标函数最优值： 除 A、 B两个最优解外， AB线段上的所有点都是 LP的最优解。本问题有无穷多最优解。第 24页例 3：用图解法解下面的线性规划无界的可行解集 此题有可行解，但无最优解max Smin S第 25页例 4：用图解法解下面的线性规划无可行解 本题无可行解，更无最优解第 26页o 有唯一最优解，这个最优解一定在可行解集合的某一顶点上达到；o 有无穷多最优解，最优解充满一个线段，可以用它的两个端点作为代表；o 有可行解，但无最优解；o 无可行解。小结： LP图解法有如下四种情况第 27页线性规划问题解的关系线性规划问题的解无可行解有可行解唯一最优解无最优解 有最优