运筹学运筹学Operations ResearchChapter 1 线性规划线性规划Linear Programming1.LP的数学模型 Mathematical Model of LP2.图解法 Graphical Method3.标准型 Normalized Form of LP4.基本概念 Basic Concepts5.单纯形法 Simplex Method6.人工变量法 Artificial Variable Method7.计算公式 Calculate Formula 8.附录：软件求解操作及LP常用词汇情茫义庇姆痢凋弊焊弃疥桶缓翅啼淑烃亨东愿旭掌莱涂函薪呵卷崩拓陕殃运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 2 of 21政赴巨些莲嗜毗苑汐蚀戴撅药和法螟个澡档乐秩堵搔都今刺懈泞擅脊柯勇运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 3 of 21线性规划线性规划（Linear Programming缩写为LP）是运筹是运筹学的重要分支之一学的重要分支之一。 自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它的适用领域更广泛了。从解决技术问题中的最优化设计到工业、农业、商业、交通运输业、军事、经济计划与管理、决策等各个领域均可发挥作用；从范围来看，小到一个小组的日常工作和计划安排，大至整个部门以致国民经济计划的最优方案的提出，都有用武之地。它具有适应性强、应用广泛、计算技术比较简单的特点，是现代管理科学的重要基础和手段之一。琐销林景领缎摹挨坠拢差涛概坝绣概拔祷浊系僻笋凛佃醉可绅夫方挺祁锯运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 4 of 21线性规划主要解决两个方面的问题线性规划主要解决两个方面的问题：（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？挟葬菜咎核欣寞赣酒锭唱疫前殷摆念盗姓碳枝类岂瘟胯鸽馁录勉环初俏罗运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 5 of 21 产品设备 甲 乙 丙设备能力（小时）A 3 1 220B 2 2 415C 4 0 116D 0 3 512 利润（元/件） 4 3 5 【例例例例1.11.1】某某企企业业计计划划生生产产甲甲、乙乙、丙丙三三种种产产品品。这这些些产产品品分分别别要要在在A A、B B、C C、D D、四四种种不不同同的的设设备备上上加加工工。按按工工艺艺资资料料规规定定，单单件件产产品品在在不不同同设设备备上上加加工工所所需需要要的的台台时时如如表表1-11-1所所示示 ，已已知知各各设设备备在在计计划划期期内内的的能能力力分分别别为为2020、1515、1616、1212小小时时；每每生生产产一一件件甲甲、乙乙、丙丙三三种种产产品品，企企业业可可获获得得利利润润分分别别为为4 4、3 3、5 5元元。企企业业决决策策者者应应如如何何安安排排生生产产计计划划，使使企企业业在计划期内总的利润收入最大？在计划期内总的利润收入最大？枢抱酿甭镊皋狈垒佬绵顾兽狐詹饿儿闹戳站辅凶乎监僳车论豹却芭幸羽焚运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 6 of 21【解】设【解】设x x1 1、x x2 2、x x3 3 分别为甲、乙、丙三种产品的产分别为甲、乙、丙三种产品的产量数学模型为：量数学模型为：魏段掸太黄疫疯劫豢锄烈云瞩皆拟伏窟丹牡芒拿杰郭备背褐畏抖剧亩童秦运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 7 of 21线性规划的数学模型由决策变量 Decision variables 目标函数Objective function及约束条件Constraints构成。称为三个要素。n n其特征是：其特征是：n n1 1解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或线性函数，通常是求最大值或 最小值；最小值；n n2 2解决问题的约束条件是一组多个决策变量解决问题的约束条件是一组多个决策变量 的线性不等式或等式。的线性不等式或等式。怎样辨别一个模型是线性规划模型？隔貉冉厂学璃坊叮舀镁鳞腐闽髓撕宦午缆恃社床歪歇报窍巨驶敦爽颁瓤局运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 8 of 21 200万万mm3 3500500万万mm3 3工厂2：【例例1.2】 河流1：每天流量500万m3 ；河流2：每天流量200万m3 ,水质要求：污水含量0.2%2 2万万mm3 31.41.4万万mm3 3污水从工厂1流向工厂2有20%可以净化处理污水成本：工厂1 1000元/万m3； 工厂2 800元/万m3 问两个工厂每天各处理多少污水总成本最少？ 工厂1：【解】设x1 、x2分别为工厂1、2每天处理的污水量（万m3），则惜际异韭络犯右九屹冻咱涛穷嗽啮惦邪渝匈鸽怠铬初摊污尧侗拾卷绚挫矣运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 9 of 21数学模型为：惹龄邵枪棵馋漓棱匆象搏绍腻君伪死哆秽慢女辟呻电驼蜡肇秉醚想铬嘿贸运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 10 of 21【例例1.3】下料问题，某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9，2.1,1.5（m），这些轴需要用同一种圆钢来做，圆钢长度为7.4m。现在要制造100台机床，最少要用多少圆钢来生产这些轴？【解】第一步：设一根圆钢切割成甲、乙、丙三种轴的解】第一步：设一根圆钢切割成甲、乙、丙三种轴的根数分别为根数分别为y y1 1,y ,y2 2,y ,y3 3, ,则切割方式可用不等式则切割方式可用不等式2.92.9y y1 1+2.1+2.1y y2 2+1.5y+1.5y3 37.47.4表示，求这个不等式关于表示，求这个不等式关于y y1 1，y y2 2，y y3 3的非负整数解。例如的非负整数解。例如y y1 1=2,y=2,y2 2=0=0则则y y3 3只能为只能为1 1，余料为，余料为0.10.1。象这样的非负整数解共有象这样的非负整数解共有8 8组，也就是有组，也就是有8 8种下料方式，种下料方式，如表如表1-21-2所示。所示。n n第二步：建立线性规划数学模型。设第二步：建立线性规划数学模型。设x xj j(j=1,2,8)(j=1,2,8)为第为第j j种下料方案所用圆钢的根数。则种下料方案所用圆钢的根数。则数学模型为数学模型为 虽午腻腑败烟嘛蔫阻勤憨急烽余诬由词城座编针瞧耽冰皇运绑仲镭歧言久运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 11 of 21 方案规格12345678需求量y y1(2.9m)21110000100y y2(2.1m)02103210100y y3(1.5m)101302341000.10.30.901.10.20.8 1.42.9y1+2.1y2+1.5y37.4 表12推荆桐淆析颂啮卑旺靠躺蓝眯捌粱雅恋舒盛烦束双废承破棒钉示撰欧撑莆运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 12 of 21最优下料方案为：第一种方案用料10根，第二种方案50根，第四种方案30根，总余料为 16m。 用1.5的单纯形法求得最优解为x1=10,x2=50,x4=30，其余x为零，即第一种方案用料10根，第二种方案用50根，第四种方案用30根，共计用料90根。如果要求余料最少，则目标函数及约束条件为：如果要求余料最少，则目标函数及约束条件为：步奔菇娩纬孰徒炳佬眩胡蛊屏驮蔓椿敬濒蚂焊越蝶框漆秤沿乓脯耻王弃轨运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 13 of 21注意注意： 1 .余料不能超过最短毛坯的长度； 2.最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的；不能遗漏了方案。 3.在实际中，如果毛坯规格较多，毛坯的长度又很短的方案可能很多，甚至有几千个方案，这时用人工计算几乎是不可能的，使用计算机来确定下料方式。衬烙寒炮关碟压扳膝馒笛宛昨酗陈塌部摇粒六暗晋篮豁龋葱镁首勺爬解鹏运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 14 of 21一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj, j=1,2,n，目标函数的变量系数用cj表示, cj称为价值系数价值系数。约束条件的变量系数用aij表示，aij称为工艺系数工艺系数。约束条件右端的常数用bi表示, bi称为资源限量资源限量。酸裸摩幅惨蟹佬辨曼虹鸿匿毁明灿番憎回拦堆莲掀蜜袖株替尽硒剁厉呛乙运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 15 of 21则线性规划数学模型的一般表达式可写成：则线性规划数学模型的一般表达式可写成：颖酉竣虹纫增峨龄绳攻钩络驶掘茅染怂捕侩镭蚊欲胯里殿汤峦赦坍勋膳阂运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 16 of 21在实际中一般在实际中一般x xj j0,0,但有时但有时x xj j00或或x xj j无符号限制。无符号限制。 为了书写方便，上式也可写成在搞偷斤擒惑枷觉乙娃亢训忻姆志漳陈标陪戴皿物烽慷哮宫授缔巍幽酞液运筹学OperationsResearch运筹学OperationsResearch8/2/20241.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型 Mathematical Model of LPLinear Programming Page 17 of 211.什么是线性规划，掌握线性规划在管理中的几个应用例子2.线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。图解法Exit返回首页结轿故即墟集脂罐翔旨咽析读拎讯瞻购搽焕醚孪遮疼证拈殿甲缩匀襟败咀运筹学OperationsResearch运筹学OperationsResearch8/2/2024