线性规划及单纯形法

《线性规划及单纯形法》由会员分享，可在线阅读，更多相关《线性规划及单纯形法（152页珍藏版）》请在金锄头文库上搜索。

1、运筹学重庆师范大学经济与管理学院 熊膺绪论l1、运筹学的定义及名称的由来l2、运筹学在工商管理中的应用l3、运筹学的主要内容l4、应用运筹学解决问题的过程运筹学的定义l运筹学（Operations Research） 系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”l故有人称之为最优化技术。中国企业管理百科全书中国企业管理百科全书：“ “运筹学应用分析、试验、量化的运筹学应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排方

2、法，对经济管理系统中人、财、物等有限资源进行统筹安排 ，为决策者提供有依据的最优方案，以实现最有效的管理。，为决策者提供有依据的最优方案，以实现最有效的管理。” ”运筹学名称的由来l英文原名:Operations Research（缩写为O.R.） 直译为“运用研究”、“作业研究”l据研究内容取名为“管理数学”：运筹学涉及的主要领域是管理问题，研究的基本手段是建立数学模型，并比较多地运用各种数学工具。l1957年取名“运筹学”：史记.高祖本纪“夫运筹帷幄之中，决胜于千里之外”运筹学在工商管理中的应用l生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。l库存管理：多种物资库

3、存量的管理，库存方式、库存量等。l运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。l人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。运筹学在工商管理中的应用l市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。l财务和会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。l其他： 设备维修、更新，项目选择、评价，工程优化设计与管理等。运筹学的主要内容l（1）数学规划l线性规划、非线性规划、整数规划、动态规划、目标 规划l（2）组合优化l最优计数问题、网络优化、排序问题、统筹图l（3）随机优化l对策论、排队论、

4、库存论、决策分析、可靠性分析先修课：高等数学，基础概率、线性代数 特点：系统整体优化；多学科的配合；模型方法的应用应用运筹学解决问题的过程l运筹学技术与方法的应用可以让决策者在面临较为复杂且不确定的决策环境时，在保持自身判断及偏好一致的条件下，进行辅助决策，但注意，不是代替决策者进行决策。规定 目标 和 明确 问题收集 数据 和 建立 模型求解 模型 和 优化 方案检验 模型 和 评价 方案方案 实施 和 不断 改进解决问题制定决策第1章 线性规划与单纯形法l运筹学的一个主要的分支是数学规划。l数学规划研究：在一些给定的条件（约束条件）下，求所考察函数（目标函数）在某种意义下的极值（极小或极大

5、）问题。l例如：在经济决策中，经常会遇到诸如在有限的资源（人、原材料、资金等）情况下，如何合理安排生产，使效益达到最大；或者给定具体的任务，如何统筹安排现有资源，能够完成给定的任务，使花费最小这类问题。l在这章，我们重点介绍的是应用最为广泛的线性规划问题。第一章 线性规划与单纯形法l一、线性规划模型实例l二、线性规划问题的数学模型l三、求解线性规划模型的图解法l四、单纯形法l五、单纯形法的进一步讨论l六、作业一、线性规划模型实例（问题的提出）l例1-1（生产计划问题）l某企业计划生产I、II两种产品。这两种产品都要分别在 A、B、C、D四个不同设备上加工。l按工艺资料规定，生产每件产品I需占用

6、各设备分别为2 、1、4、0 h，生产每件产品II需占用设备分别为2、2、 0、4h。已知各设备计划期内用于生产两种产品的能力分 别为12、8、16、12h。l又知每生产一件I企业能获得2元利润，每生产一件产品 II企业能获得3元利润。l问该企业应如何安排生产，才能使总的利润最大。一、线性规划模型实例（问题的提出）设备 产品ABCD 利润 （元/件）I21402II22043生产能力（h）1281612表1-1问题分析：（1）问题的目标是什么？ 合理安排生产，实现利润最大化（2）利润与哪些因素有关？ 产量和单位产量的利润l问题分析：l（1）问题的目标是什么？ l（2）利润与哪些因素有关？ l（

7、3）单位利润最大的II产品，那么我们就仅生产II产品，是否可行？不可行，原因是各设备生产II产品的能力是有限的，仅仅生产II产品，设备的生产能力还有剩余。结论是两种产品都要进行生产。l（4）两种产品的产量会受到什么限制条件呢？各种设备的生产能力，即占用各种设备的工时。l（5）要决策的问题是：I产品生产多少？II产品生产多少？才能实现利润最大化呢？一、线性规划模型实例（问题的提出）l例1-1【解】：l设x1和x2分别表示I、II两种产品在计划期内的产量 。l因设备A在计划期内的有效时间为12h，不允许超过，因 此建立不等式方程： 2x1+2x212l同理对设备B、C、D也可以列出类似的不等式方程

8、x1+2x28 4x116 4x212l建立各种设备允许的情况下，企业总的利润收入方程： z= 2x1+3x2按工艺资料规定，生产每件产品I需占用各设备分别为2、1、4、0h；生产每件产品II需占用设备分别为2、2、0、4h；已知各设备计划期内用于生产两种产品的能力分别为12、8、16、12h一、线性规划模型实例（问题的提出）l因此，该实例的问题可以归结为如下的数学模型。回忆：回忆： 数学规划研究：在一些给数学规划研究：在一些给定的条件（定的条件（约束条件约束条件）下）下 ，求所考察函数（，求所考察函数（目标函目标函 数数）在某种意义下的）在某种意义下的极值极值 （极小或极大）（极小或极大）问

9、题问题。 如何理解如何理解“ “线性规划线性规划” ”？一、线性规划模型实例（问题的提出）l例1-2（能源利用问题）l假设某电厂以甲、乙、丙三种煤作为燃料煤，已知这三种煤的含硫量、发热量及价格，见表1-2。现在要将上述三种煤混合燃烧，按锅炉要求，发热量不能低于17000kJ/t；按环保要求，含硫量不能超过0.025%。问应按什么比例将煤混合，才能使混合煤的价格最低？建立其数学模型。一、线性规划模型实例（问题的提出）电厂 含硫量（%） 发热量（kJ/t）价格（元/t）甲0.011600080乙0.052000070丙0.031800076表1-2分析：问题的目标是什么？ 通过三种煤的组合实现混合

10、煤的价格 最低问题目标实现的约束条件是什么？ 含硫量和发热量一、线性规划模型实例（问题的提出）l例1-2求解：l设单位混合煤中甲、乙、丙三种煤的组合比例为x1：x2：x3l因为是组合比例，所以有x1+x2+x3=1，且为非负。l考虑约束条件：含硫量和发热量 有16000x1+20000x2+18000x3170000.01x1+0.05x2+0.03x30.025l该问题的目标是在满足上述约束条件下使每吨混合煤的价格最低，用z来表示价格，则：z=80x1+70x2+76x3一、线性规划模型实例（问题的提出）l例1-2求解：l因此，该问题的数学模型为：目标函数约束条件一、线性规划模型实例（问题的

11、提出）l例1-3 （运输问题）l假设某电力系统有三个火电厂B1、B2、B3，它们每月需燃料煤分别为10、20、25万t。供应这三个电厂燃料煤的煤矿有三个，即A1、A2、A3，它们每月分别可供该电力系统燃料煤15、25、15万t。已知各煤矿到各电厂的运输距离（单位km），如表1-3所示。问如何确定调运方案，使总的运输量（总万吨公里数）最少？建立数学模型。一、线性规划模型实例（问题的提出）电厂运距(km) 煤矿B1B2B3A180100120A27012090A310080150表1-3l分析：l问题是什么？ 如何确定调运方案，使总的运输量（总万吨公里数） 最少！l调运方案如何理解？ A1分别向B

12、1、B2、B3三个电厂输送多少万t煤炭？ A2分别向B1、B2、B3三个电厂输送多少万t煤炭？ A3分别向B1、B2、B3三个电厂输送多少万t煤炭？l总的运输量（总万吨公里数）如何计算？ 各个煤矿向各个电厂输送的煤的吨数输送的距离之 和。l有哪些约束条件？ 各火电厂的煤炭需要量和各煤矿的煤炭供给量l例1-3 【解】：l设煤矿Ai（i=1，2，3）每月供给电厂Bj（j=1，2，3）燃料煤xij万t。l该问题的目标是在满足供需平衡的条件下使总运输量最少。设z表示总运输量，则该运输问题的数学模型为：l自己动手试一试：l某工厂要生产两种新产品：门和窗。经测算，每生产一扇门需要在车间1加工1小时、在车间

13、3加工3小时；每生产一扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时，车间3为18小时。已知每扇门的利润为300元，每扇窗的利润为500元。而且根据经市场调查得到的这两种产品的市场需求状况可以确定，按当前的定价可确保所有新产品均能销售出去。问该工厂如何安排这两种产品的生产计划，才能使总利润最大？l自己动手试一试【解】l两种新产品的有关数据如表：车间单位产品的生产时间 （小时）每周可获得的生产时间 （小时）门窗11042021233218单位利润（ 元）300500l自己动手试一试【解】l设x1为每周门的产量（扇），x2为每周窗的产量（

14、扇）。l线性规划模型如下：二、线性规划问题的数据模型l规划问题的数学模型包含三个组成要素：l（1）决策变量，指问题中要确定的未知量l（2）目标函数，指问题所要达到的目标要求，表示为决策变量的函数l（3）约束条件，指决策变量取值时应满足的一些限制条件，表示为含决策变量的等式或不等式l如果在规划问题的模型中，决策变量为可控变量，且取值是连续的，目标函数及约束条件都是线性的，这类模型叫做线性规划模型。二、线性规划问题的数据模型l1、线性规划模型的一般表达形式l（1）一般形式决策变量及各类系数之间的对应关系二、线性规划问题的数据模型l1、线性规划模型的一般表达形式l（1）一般形式l模型的简写形式为：二

15、、线性规划问题的数据模型l1、线性规划模型的一般表达形式l（1）一般形式l（2）向量形式二、线性规划问题的数据模型l1、线性规划模型的一般表达形式l（1）一般形式l（2）向量形式l（3）矩阵形式A为约束方程组（约束 条件）的系数矩阵。二、线性规划问题的数据模型l2、线性规划模型的标准形式l为了研究问题的方便，规定线性规划问题的标准形 式为：l2、线性规划模型的标准形式l对标准形式的说明：l（1）标准形式的线性规划模型中的要求l 目标函数为求最大值（有些文献规定是求最小值）；l 约束条件全为等式，约束条件右端常数项bi全为非负值；l 变量xj的取值全为非负值。l2、线性规划模型的标准形式l（2）

16、非标准形式的线性规划问题转化为标准形式的方法l 目标函数为求最小值l只需令z=-z，则目标函数转化为l 约束条件为不等式l当约束条件为“”时，例如 2x1+2x212l可令x3=12- 2x1-2x2或者2x1+2x2+x3=12。l显然，x30，称x3为松弛变量。 l2、线性规划模型的标准形式l（2）非标准形式的线性规划问题转化为标准形式的方法l 约束条件为不等式l当约束条件为“”时，例如 10x1+12x218l可令x4=10x1+12x2-18或者10x1+12x2-x4=18。l显然，x40，称x4为剩余变量。l松弛变量和剩余变量在实际问题中分别表示未被利用的资源数和短缺的资源数，均未转化为价值和利润。因此在目标函数中，松弛变量和剩余变量的系数均为零。 l2、线性规划模型的标准形式l（2）非标准形式的线性规划问题转化为标准形式的方法l 目标函数为求最小值l 约束条件为不等式l 无约束变量。