《运筹学》-课件设计（公开）.ppt

安徽省十一五规划教材 二、线性规划问题的标准形式 线性规划问题的标准形具有以下特征： （1）求目标函数的最大值； （2）除非负限制外所有约束条件都是等式约束，且约束条件右端的常数项非负； （3）所有变量均有非负限制。 则线性规划问题的标准形为： (1.1.13) 安徽省十一五规划教材 如果所给的线性规划问题不符合标准形的要求，则将其适当变换化成标准形。下面从几个方面介绍标准化的方法。 1.目标函数的改写：化求最小值为求最大值 2.化不等式约束为等式约束 安徽省十一五规划教材 3.对于无非负限制的化为有非负限制 4.如果某个约束条件右端的常数项小于零，则用(-1)乘以该式两端即可。 安徽省十一五规划教材 例1.1.4 将线性规划问题 (1.1.14) 化为标准形。 安徽省十一五规划教材 (1.1.14)化为标 准形(1.1.15) （1.1.15） 若记 安徽省十一五规划教材 可将线性规划问题（1.1.13）表示成矩阵形式： (1.1.16) 或记 示成向量组合形式： (1.1.17) 安徽省十一五规划教材 安徽大学十一五规划教材 运筹学 主讲人 ×××教授 安徽省十一五规划教材 第0章 绪论 安徽省十一五规划教材 §0.1运筹学及其发展简史 一、萌芽时期 二、兴起时期 三、蓬勃发展时期 §0.2运筹学的主要分支 §0.3运筹学的特点及分析问题的一般过程 安徽省十一五规划教材 第1章 线性规划及其扩展§1.1 线性规划问题及模型 1.1.1 线性规划问题建模举例 引例 某铁器加工厂要制作100套钢架，每套钢架要用长为2.9米、2.1米和1.5米长的圆钢各一根，已知原料的长度为7.4米。如果要生产100套钢架，应如何下料，才能使得所用原材料最省？ 分析：对于每一根长为7.4米的原料，截成2.9米、2.1米和1.5米长的圆钢，可以有若干种下料方式，把它截成我们需要的长度，有以下8种下料方式(表1.1.1)： 安徽省十一五规划教材 表1.1.1 下料方式及每种类型的数目 1.4 0.8 0.2 1.1 0 0.9 0.3 0.1 余料 100 4 3 2 0 3 1 0 1 1.5米 100 0 1 2 3 0 1 2 0 2.1米 100 0 0 0 0 1 1 1 2 2.9米 需要量 长度 下料方式 安徽省十一五规划教材 下料方式是从大到小、从长到短的顺序考虑的。 1.若只考虑用方式下料，需要用料100根，没有经过任何优化。 2.若采用木工师傅的下料方法：先下最长的、再下次长的、最后下短的(见表1.1.2)，共需原料96根。动一下脑筋，就可以比用方式下料节约用料4根，降低成本，但这仍然不是最好的下料方法。 100 101 100 96 合计 2 2 0 1 48 0 0 12 0 99 0 33 50 0 100 50 1.5米根数 2.1米根数 2.9米根数 下料根数 下料方式 表1.1.2 木工师傅的下料情况 安徽省十一五规划教材 3.若要我们安排下料，暂不排除8种下料方式中的任何一种，通过建立数学模型进行求解，寻找最好的下料方案。 2.9米、2.1米和1.5米圆钢的数量均不低于100根，即： 因此，可以建立以下数学模型: 安徽省十一五规划教材 通过对(1.1.1)求解得到： 通过建立数学模型求解，得到的结果是最优的。这个模型就是线性规划模型。 安徽省十一五规划教材 下料问题是在经济和管理中经常遇到的问题，引例是条材下料问题、此外还有板材下料问题（如五金厂生产保险柜的下料、服装厂下料等）或者更复杂的下料问题。请考虑一下，下料方式能不能用计算机来设计更合理？本问题能不能将目标函数确定为余料最少，为什么？这都是值得读者思考的问题。 在生产管理和经营活动中，经常考虑这样一类问题：如何合理地利用有限的人力、物力和财力等资源，以便得到最好的经济效果——成本最小或收益最大。下面分四个方面介绍典型的建立线性规划模型的方法。 安徽省十一五规划教材 一、合理下料问题 例1.1.1 设用某种材料（条材或板材）下零件 的毛坯，根据经验，在一件原料上有 种不同的下 料方式，每种合理的下料方式可得各种毛坯个数及各种零件的需要量如表1.1.3。问：应怎样安排下料方式，使得既能满足需要，又使得用料最省？ 表1.1.3 一般下料问题的基本数据 … … … … … … 零件需要量 … 零件规格 下料方式 安徽省十一五规划教材 (1.1.2) 安徽省十一五规划教材 或者 (1.1.3) 安徽省十一五规划教材 通过上述分析，建立线性规划问题数学模型主要考虑以下