第三章 线性规划,第一节 线性规划的基本概念 第二节 线性规划模型的建立 第三节 线性规划模型求解 第四节 线性规划模型的应用,第三章 线性规划,1.了解线性规划问题的基本概念及其数学模型的形式。 2. 掌握线性规划模型的建立方法及应注意的问题。 3.理解线性规划图解法的基本原理。 4.掌握图解法求解线性规划模型的基本方法。 5.理解单纯形法求解线性规划问题的基本原理。 6.掌握单纯形法求解线性规划模型的基本方法。 7.掌握线性规划模型的物流应用。,本章知识点：,物流网络的确定,如图3-1所示。现有三个客户需要两种产品。有两个工厂向仓库提供产品，每个工厂都可以生产其中任何一种产品，但每种产品的单位件生产成本不同。 工厂1的生产能力有限制，可生产7万件产品1，5万件产品2；工厂2生产任何一种产品均无生产能力的限制。 每个客户由同一个仓库供货。已知仓库1的货物搬运处理成本为3元/件，该仓库如投入营运，固定成本为每年10万元，处理能力为每年12万件；仓库2的货物搬运处理成本为2元/件，固定成本为每年40万元，处理能力无限制；不存在维持仓库营运的最低数量限制。 问题是该使用哪些仓库，客户需求如何分配，各工厂向各仓库供多少货，才能使经济上总花费最小？,-导引案例-,物流网络的确定,2元/件,产品1,-导引案例-,物流网络的确定,产品,-导引案例-,物流网络的确定,要正确地回答上述问题，物流管理者需要做大量的工作，在此过程中定量分析是必不可少的，我们可以通过立恰当的混合-整数线性规划模型，可以很快得出相应的最优的物流网络布局方案。本章将为物流管理者介绍物流作业中常用的定量分析工具之一线性规划模型，主要介绍线性规划的概念、建模、求解及应用等内容。,-导引案例-,线性规划（Linear Programming,简记为LP）是运筹学的一个重要分支。1947年，美国数学家丹齐格（George Bernard Dantzig）在研究美国空军资源配置问题时，提出了求解线性规划问题的一般解法单纯形法（Simplex Method）,从而为线性规划这门学科奠定了基础，使求解大规模决策问题成为可能。50年代初，应用电子计算机求解线性规划问题又获得了成功。1960 年，前苏联学者康托洛维奇以最佳资源利用的经济计算一文获诺贝尔奖。从此线性规划方法用来解决企业的生产经营活动问题并取得了良好的效果。目前，大多数计算中心都有线性规划的商用计算机程序可供使用。线性规划已发展成为物流系统现代化管理的有力工具之一。,-第一节 线性规划的基本概念-,一、线性规划的定义及引例,在经济、管理领域中，常常会遇到这样的问题：当 一项任务确定后，应如何统筹安排才能做到用最少的 人力、物力等资源去完成？如何合理地安排使用现有 的人力、物力资源使得创造的利润（财富）最多？这 类问题通常用线性规划可以得到较好的解决。 线性规划的定义如下： 求取一组变量Xj(j=1,2,n),使之既满足线性约束条 件，又使其具有最优线性目标函数值（极大或极小 值）的一类最优化问题。,-第一节 线性规划的基本概念-,一、线性规划的定义及引例,先看一个简单的引例： 某企业现在生产三种产品分别为A、B、C，所需 原材料、工时及可得利润如表3-1所示。 表3-1 所需资源及可得利润,-第一节 线性规划的基本概念-,一、线性规划的定义及引例,若每天只能保证供应200公斤原材料，可用工时每天为150小 时，问每天如何安排生产才能使三种产品的总利润为最大？ 现行的生产方案是：生产产品A12件、产品B10件、产品C6 件，总利润为86元，工时刚好用完而原材料节余82公斤。试 问，在不改变原材料供应及可利用工时总量的限制条件下，总 利润能否再提高一些呢？答案是肯定的，用“线性规划”的方法 可以重新安排生产计划，即仅安排生产产品B，产品A和C不安 排生产，这样总利润可到100元，且原材料及可用工时全部用 完。 所以线性规划问题也可以定义为：确定一个系统有限资源的 最优分配的数学方法。其中系统就是指我们所研究的问题。,-第一节 线性规划的基本概念-,二、线性规划的数学表达式,线性规划问题的数学模型一般形式是： 求一组决策变量 、 、 的值，使得,max(或min)Z= + (3.1),s.t.,（3.2）,其中,为已知常数，式(3.1)称为目标函数，式（3.2）为约束条件，满足约束条件的（ ， ）称为可行解，用X表示；而使目标函数达到最大值的可行解（ ， ）称为最优解。,-第一节 线性规划的基本概念-,本节思考题,1.现实中有哪些经济问题可以有线性规划问题来优化？ 2.线性规划问题的数学模型由哪几部分组成？写出其一般形式的数学表达式。,-第一节 线性规划的基本概念-,