运筹学 第2版 课件全套 杨瑞娜 绪论、线性规划-随机规划

JournalonComputing

绪论教材：《运筹学》，徐渝，李鹏翔和郑斐峰著中国人民大学出版社；《运筹学》，甘应爱，田丰等著，清华大学出版社01“OR”是什么？03“OR”有什么？“OR”能做什么？0204我们“学什么”？CONTENTS05应该“怎么学”？回答五个问题：PART01什么是运筹学？“运筹帷幄之中，决胜千里之外”西汉初年，天下已定，汉高祖刘邦在洛阳南宫举行盛大的宴会，喝了几轮酒后，他向群臣提出一个问题：“我为什么会取得胜利？而项羽为什么会失败？”高起等认为高祖派有才能的人攻城略地，给立大功的人加官奉爵，所以能成大事业。而项羽恰恰相反，有人不利，立功不奖，贤人遭疑，所以他才失败。汉高祖刘邦听了，认为他们说的有道理，但是最重要的原因是能用人。他称赞张良说：“夫运筹帷幄之中，决胜千里之外，吾不如子房。”意思是说，张良坐在军帐中运用计谋，就能决定千里之外战斗的胜利。这说明张良心计多，善用脑，善用兵。

什么是运筹学？东北航空公司正在考虑购买新型长途、中途、短途喷气客机。每架长途客机的购买成本是6700万美元，每架中途客机的购买成本是5000万美元，每架短途客机的购买成本是3500万美元。董事会已经为本次购买批准了最多15亿美元的金额。不考虑购买何种机型，公司希望每架飞机都能飞行尽可能多的距离以发挥最大的能力。公司估计(减去资本收回成本后)，每架长途客机年净利润能实现420万美元，每架中途客机年净利润能实现300万美元，每架短途客机年净利润能实现230万美元。如果你是公司的管理层，你应该如何制定购买计划以实现利润最大化？什么是运筹学？如何才能作出一个满意的决策？决策是管理者的主要工作内容什么是运筹学？两类决策方法定性方法定量方法什么是运筹学？运筹学——OR（OperationsResearchorOperationalResearch）系统工程最重要的理论基础之一，在美国有人把运筹学称之为管理科学(ManagementScience)。运筹学所研究的问题，可简单地归结为一句话:“依照给定条件和目标，从众多方案中选择最佳方案“，故有人称之为最优化技术。什么是运筹学？制定决策管理者运用合理的分析来改善决策的制定运筹学由一支综合性的队伍，采用科学的方法，为一些涉及到有机系统（人-机）的控制系统问题提供解答，为该系统的总目标服务的学科。

——钱学森等什么是运筹学？运用科学方法来解决工业、商业、政府、国防等部门里有关人力、机器、物资、金钱等大型系统的指挥或管理中所出现的复杂问题的一门学科。其目的是“帮助管理者以科学方法确定其方针和行动”。

——英国运筹学会（世界上最早的运筹学会）运筹学是应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型而获得最优决策的科学。

——近代一些运筹学工作者什么是运筹学？PART02运筹学的三个来源1、军事两次世界大战期间的军事运筹研究2、管理生产中的组织与计划问题3、经济冯·诺依曼宏观经济优化的控制论模型运筹学的三个来源第一次世界大战期间1914-1915兰彻斯特的若干军事论文研究战争的胜负同兵力多寡、火力强弱之间的关系；爱迪生解决反潜战的“战术对策演示盘”反潜战的研究项目：汇编各项典型统计数据，用于选择回避或击毁潜艇的最佳方法，使用“战术对策演示盘”解决免受潜艇攻击的问题；运筹学的三个来源军事大西洋反潜战——Morse（莫尔斯）小组的重要工作1942年麻省Morse教授应美国大西洋舰队反潜战官员Baker（贝克）舰长的请求担任反潜战运筹组的计划与监督工作，其最出色的工作之一是协助英国打破了德国对英吉利海峡的海上封锁，研究所提出的两条重要建议是：

运筹学的三个来源军事第二次世界大战期间将反潜攻击由反潜舰艇投掷水雷改为飞机投掷深水炸弹，起爆深度由100米改为25米左右，即当德方潜艇刚下潜时攻击效果最佳；运送物资的船队及护航舰艇的编队由小规模、多批次改为大规模、少批次，从而减少了损失率；运筹学的三个来源军事丘吉尔采纳Morse的建议打破德国封锁重创德国潜艇部队Morse同时获得英国及美国战时最高勋章运筹学的三个来源军事定量化系统化方法迅速发展采集真实的实际数据多学科密切协作解决方法渗透着物理学思想二战时期军事运筹学的特点运筹学的三个来源军事管理科学的特点与学派科学性与艺术性古典学派、行为学派、系统学派、数理学派

古典管理学派对运筹学发展产生的影响寻求一些方法，使人们自愿地联合与协作，保持个人的首创精神和创造能力，达到增加效率的目的。运筹学的三个来源管理动作研究与泰勒工作制切削效率与车速、进刀量等因素的数学关系——优选问题提出管理的基本原则，研究了机构设置、权限、工厂布局、计划等问题刺激性工资制举世闻名用于生产活动分析和计划安排的甘特横道图--

发展成为统筹方法运筹学的三个来源管理近三十年经济数学和运筹学互相影响，相互促进，共同发展Vonneumann(冯．诺伊曼)的开创性工作近代博弈论创始人之一，1944年与Morgenstern(摩根斯坦)合作发表《博弈论与经济行为》一书，将经济活动中的冲突、协调、平衡分析题量化处理，解决了一些基本问题，如下棋、玩扑克牌等室内游戏中竞赛者之间的讨价还价，交涉，结伙，利益分配等行为方式的类似性。领导研究的电子计算机成为OR的技术实现支柱之一。慧眼识人最早肯定扶持当时未满30岁的Dantzig从事的以单纯形法为核心的线性规划研究。运筹学的三个来源经济PART03运筹学发展简史1、萌芽时期2、早期研究3、形成与发展时期4、现代运筹学

三、

运筹学

发展

简史

运筹学发展简史1、萌芽时期朴素的OR思想自古有之例1、春秋战国时期的孙膑斗马术

例2、都江堰工程(“鱼嘴”分水堤，“飞沙堰”溢洪道和“宝瓶口”进水口)

例3、宋真宗重建皇宫的方案例4、沈括《梦溪笔谈》中记录的战例运筹学发展简史2、早期研究《经济表》——1758年一次大战期间（1914.8~1918.11）的军事运筹研究、兰彻斯特的若干军事论文·博弈论与投入产出——经济平衡理论的基础生产组织与计划——《生产组织与计划中的数学方法》康特洛维奇运筹学发展简史3、形成与发展时期二战中OR逐步形成独立学科：欧战中英国的“布莱克特杂技班”提高对敌船的沉击率分析德国以V1导弹进攻伦敦的目的性盟军对日作战中最优化投放鱼雷的战略研究军事、经济全面动员，促进OR各个分支的全面研究运筹学发展简史战后军事活动分析转向经济发展47年单纯形法研究成功，LP走向成熟，OR进入工业管理运筹学发展简史50~60年代走向成熟标志：队伍壮大，成立学会，创办刊物，高校开课军事运筹学面向未来要求大量理论成果问世，系统专著出版各个分支得到充实、完善运筹学发展简史4、现代运筹学计算机的崛起使OR进入飞速发展期LP算法的研究带动各个分支理论与方法的更大发展新领域新方法不断萌发应用范围更加广泛运筹学发展简史PART04走向成熟的运筹学1、各个分支充实完善形成体系确定性模型数学规划线性规划整数规划非线性规划动态规划几何规划参数规划多目标规划组合优化图论与网络分析优选与统筹方法随机性模型对策论排队论（随机服务系统）可靠性理论库存论搜索论计算机随机模拟决策论走向成熟的运筹学从整体优化的角度出发，使用科学方法具有整体性观点科学方法：使用的人员是一支综合性队伍研究解决问题的一般过程如下：走向成熟的运筹学提出界定问题确定问题构造OR模型问题导向适当选择优化求解过程模型求解进行解的评价检查模型的有效性提供决策支持考察执行情况走向成熟的运筹学

使用的数学方法——代数、分析、概率统计、组合分析、具有一定实验性质的模拟方法，大量使用计算机与其他学科的交融渗透——计算机科学、行为科学、控制论、管理科学、系统分析与系统工程等

走向成熟的运筹学2.运筹学方法论1947年Dantzig提出单纯形法50-56年LP对偶理论诞生1951年Kuhn-Tucker(库恩-塔克)定理奠定非线性规划理论基础(将多个位移约束简化为单一位移约束(称为最临界位移约束),建立位移约束下的优化设计准则)1954年网络流理论建立1955年创立随机规划1958年创立整数规划及割平面解法1958年求解动态规划的Bellman原理发表1960年Dantzig-Wolfe建立大LP分解算法走向成熟的运筹学3.大量理论成果问世4.日益广泛的应用领域①运用分析理论——用于分配、选址、资源最佳利用、设备最佳运行等；②竞争理论——用于体育比赛、产品竞争、投标、宏观金融博弈分析、经济博弈等；③随机服务理论——用于研究拥挤和排队现象，如：电话呼唤、CPU运行和程序的排队、防空武器系统的评价，计算机科学和技术及通讯网络，供应链管理等。走向成熟的运筹学④前沿与热点在“数字地球”的关键技术中寻求OR的切入点（大规模科学计算，海量存储，高精度卫星图象，宽带网，互操作）复杂巨系统与计算机模拟生物信息学中的OR方法DP引入生物分子序列比较，预测外显子和内含子寻找基因、启动子和序列对齐等隐藏统计规律的隐马氏过程方法走向成熟的运筹学DNA分子生物计算机经济博弈论与宏观金融博弈分析现代物流与供应链管理现代优化算法禁忌搜索模拟退火遗传算法人工神经网络模糊OR与随机OR现代军事OR走向成熟的运筹学平时训练（红蓝军对抗）医疗后送系统的计算机仿真计算机模拟军事演习电子对抗（海湾战争中Karmarkar算法的运用）运筹学发展现代军事运筹学PART05运筹学的影响运筹学的影响改善全世界大量组织的效率提高国家的经济生产力促进商业运作的规范性节约大量稀有的资源为运筹与管理科学实践者颁发的最负盛名的奖项是弗兰茨·厄德曼(FranzEdelman)奖，该奖是全球运筹和管理科学界的最高工业应用奖，被广泛誉为工业工程界的“诺贝尔”。自设立以来，英特尔、先正达、惠普、通用汽车、摩托罗拉等国际一流的科技企业，以及联合国粮食计划署等机构都曾荣膺过此奖项。2021年开始，弗兰兹·厄德曼奖连续三年出现“中国面孔”，这也打破了该奖项四十余年的记录。华为、阿里巴巴、联想等中国科技企业都曾先后入围。2023年1月18日，运筹学与管理科学学会（INFORMS）正式公布了2023年弗兰兹·厄德曼奖（FranzEdelmanAward）最终入围名单，全球共有六家企业获得决赛资格。其中，华为、美团等进入六强名单，成为入围决赛的中国科技企业代表。

运筹学的影响2021年，京东集团自主研发的无人仓调度算法应用最终入围弗兰兹·厄德曼奖名单。基于京东物流无人仓技术团队的深入研究，该算法可以实现复杂的多智能体任务分配和路径规划，在毫秒内求解百亿级复杂度的优化问题并给出最优解，最终形成规模化的机器人调度系统。目前，在京东物流遍布全国的仓储体系中，无人仓算法技术已成为“标配”，京东自营商品超500万SKU，库存周转天数仅34天，无人仓算法为这一世界级水平数字的实现提供了重要技术支撑。基于数智化社会供应链，京东正与众多合作伙伴推动中国社会化物流成本在十年内降至10%以内，比肩欧美等发达国家。运筹学的影响2022年，阿里巴巴供应链与运筹优化技术凭借集成预测、库存、价格推荐的优化决策算法及其在新零售场景的实践成果，成功闯入了总决赛六强。阿里巴巴已连续两年（2021，2022）入围弗兰兹·厄德曼总决赛，是最近20年来唯一一家连续两年入围该奖项总决赛的公司，也是当年唯一入围的中国公司，代表了中国在供应链技术和运筹科学应用中的杰出贡献。运筹学的影响2023年，美团凭借智能决策分析平台，一同入围FranzEdelman奖决赛圈。它背后的技术、解决的问题，你我虽然感受不到，但在日常中都会用到。它背后的技术价值也是奖项最为重视的几个方面。第一、有先进技术：美团基于高效路径优化算法和业内首创的城市级万人万单秒级匹配调度技术，可以实现在极其复杂环境下的高效调度。第二、有广泛落地：美团每日即时订单超过6000万个，配送“智能决策平台”已覆盖至全国2800个城市。第三、带来社会影响：如今美团已成为国民级应用，而“外卖买万物”成为更多人的生活习惯，此前在疫情期间，美团还为保供需提供支持。运筹学的影响2023年，华为云凭借走在行业前列的云资源调度技术和优异的市场表现入围决赛六强。这是该奖项设立50余年来，全球首次有云计算公司凭借调度技术入围。云资源利用率最优且保证服务质量是业界公认的云资源调度难题，华为云在云资源调度技术上处于业界领先队列，针对媒体网络资源调度难题，通过一系列创新算法应对挑战，实现媒体网络利用率优化超过30%；同时，提高了QoS服务质量，两年内业务规模增长10倍。运筹学的影响PART06运筹学的应用仓储物流中心选择与物资运输问题运筹学的应用划分消防站片区划分问题运筹学的应用排课问题?运筹学的应用外卖配送问题运筹学的应用理财与投资问题运筹学的应用人力资源管理与任务分配问题运筹学的应用PART07课程目的与要求通过讲授、讨论、平时作业、考试、课程设计(《运筹学实践》)等教学环节&正确理解运筹学方法论，掌握运筹学整体优化思想；&掌握线性规划、整数规划、动态规划、网络模型和非线性规划等基本模型的功能和特点，熟悉其建模条件、步骤及相应的技巧，能根据实际背景抽象出适当的运筹学模型；课程目的与要求&熟练掌握各种模型特别是确定性模型的求解方法，并能对求解结果作简单分析；&掌握与基本模型有关的基本概念及基本原理，做到思路清晰、概念明确；&接触本领域的新发展，具有初步运用运筹学思想和方法分析、解决实际问题的能力和创新思维与应用的意识；课程目的与要求课堂讲授与讨论——启发式、提问交流式、随堂（或集中）讨论式；作业；考核与成绩（结构化记分方式）；闭卷考试

70%

平时作业

30%课程目的与要求教学内容

线性规划整数规划动态规划图与网络分析非线性规划（选讲）课程目的与要求课程目的与要求要求和希望转变观念、加强沟通、相互配合、共同探索教与学的创新之路；放得开、坐得住、勤思考、多动手，努力把握逻辑思维和非逻辑思维相互紧密配合的思维艺术，培养自己的创造性思维；遵守纪律、排除干扰、勤奋踏实、积极实践、提高效率。课程目的与要求几点学习建议

1、制定一张严格的时间表，按课内外1：2的比例安排；2、充分发挥小组团队学习作用，互帮互学,相互鼓励与督促；3、留心处处皆学问，对于学习中的问题与灵感要随时记录、不断积累；4、压力促成长，坚持扎扎实实地独立完成作业，积极参与小组讨论，认真完成课程设计，你会体会到成功的喜悦和受益的欢乐。课程目的与要求只要耕耘，就会有收获。祝大家学有所成，取得优异成绩！课程目的与要求JournalonComputing第一章线性规划01线性规划问题及其标准形式03线性规划问题的单纯形方法线性规划问题的图解法及其解的性质0204线性规划问题的建模与应用CONTENTSPART01线性规划问题及其标准形式线性规划问题及其标准形式突发公共卫生事件下的人员排班问题年初，某市出现了一场意想不到的大型传染性疾病流行，城市的每个角落都笼罩着紧张和焦虑。卫生健康部门迅速行动，紧急抽调医护人员，组织辖区内所有居民进行呼吸道样本采集以用于检测，希望借此控制疫情的蔓延。为了充分利用有限的医护人员资源与高效组织采集工作，卫生健康部门经过精确计算，确定了周一到周日每天进行检测所需的医护人员数量分别为：300,300,450,450,500,700和650。线性规划问题及其标准形式但是，在如此繁重的工作任务下，他们也深知医护人员需要得到充分的休息才能保持身心健康和高效工作。因此，他们采取了排班制度，规定每周连续工作5天后必须休息2天，并且进行轮流休息的安排。然而，正当卫生健康部门认为一切就绪时，他们却面临一个新的问题：如何安排每天值班的医护人员人数，使得其既能满足医疗工作需求，又尽量减少医护人员之间的流动，从而降低感染风险呢？一、线性规划问题的导出现实社会活动中，常常遇到两类问题：若要以最少的资源消耗来完成一项确定的任务，如何统筹安排？—如何使成本最小！在既定资源条件下，如何配置它们，能使完成的任务量最大？—如何使效益最大！线性规划问题及其标准形式引例1—配比问题

用浓度为45％和92％的硫酸配置100吨浓度为80％的硫酸。取45％和92％的硫酸分别为x1吨和x2吨，则有：求解二元一次方程组，得解。两个未知数两个方程线性规划问题及其标准形式

如果目的相同，但若有5种不同浓度的硫酸可选（30％，45％，73％，85％，92％）会出现什么情况呢？取这5种硫酸分别为x1,x2,x3,x4,x5吨，则

问：（1）有多少种配比方案？为什么？（2）何为最好？（最优的标准是什么？）5个未知数两个方程线性规划问题及其标准形式5种硫酸价格分别为：400，700，1400，1900，2500元／吨，则有：观察：目标函数和约束条件有什么特点？目标函数是线性的；约束条件是线性的；为什么叫线性规划？线性规划问题及其标准形式引例2—生产计划问题某工厂生产A、B、C三种产品，每吨利润分别为2000元，3000元，3000元。生产单位产品所需要的工时及原材料如表1－1所示。若供应的原材料每天不超过9吨，所能利用的劳动力日总工时为3个单位。问：如何制定日生产计划，使三种产品总利润最大？线性规划问题及其标准形式线性规划问题及其标准形式线性规划问题及其标准形式如何制定生产计划，使三种产品总利润最大？何为生产计划？总利润如何描述？还要考虑什么因素？有什么需要注意的地方（技巧）？最终得到的数学模型是什么？问题讨论线性规划问题及其标准形式引例3-伟恩德公司案例—产品组合问题伟恩德公司总裁约翰·希尔对杰姆小组开发的两种新产品很有信心，一种是8英尺的铝框玻璃门，另一种是4英尺×6英尺的双把木框窗。公司有三个工厂，玻璃门需要工厂1和工厂3的生产能力，木框窗需要工厂2和工厂3的生产能力。已知工厂加工两种新产品需要的工时数据和预测的单位利润。线性规划问题及其标准形式线性规划问题及其标准形式管理部门需要考虑：1）公司是否应该生产这两种新产品？2）如果生产，两种新产品的生产组合如何？每周分别生产多少数量？线性规划问题及其标准形式伟恩德公司产品组合问题的数据线性规划问题及其标准形式需要回答的三个问题：1）要做出的决策是什么？2）在做出这些决策上有哪些约束条件？3）这些决策的全部绩效测度是什么？1）要做的决策是两种产品的生产率（每周生产多少）2）对决策的约束条件是两种产品在相应工厂里每周生产时间不能超过每个工厂可得到的生产时间。3）对这些决策的全部绩效测度是这两种产品的总利润。线性规划问题及其标准形式设两种产品每周分别生产x1件和x2件。目标函数：总利润最大约束条件：两种产品在相应工厂里每周生产时间不能超过每个工厂可得到的生产时间。引例4-利博公司广告组合问题

利博(Profit&Gambit)公司生产家用的清洁产品，这是一个高度竞争的市场，公司为了增加市场份额连续挣扎多年。管理层决定集中在下列三个主要产品上实行一个大规模的新的广告运动。一种喷雾去污剂一种新的液体洗涤剂一种成熟的洗衣粉线性规划问题及其标准形式线性规划问题及其标准形式这一广告运动会采用电视和印刷媒体。一个商业广告已经形成，要在全国的电视上做液体洗涤剂的广告来帮助推出这一产品。印刷媒体的广告将用来促销所有三种产品，包括消费者可用来以低价购买产品的象征性优惠券。管理部门已经设定了广告运动的最低目标：(1)喷雾去污剂必须再增加3％的市场份额；(2)新的液体洗涤剂必须在洗涤剂市场上获得18％的份额；(3)洗衣粉占洗涤剂市场的份额必须增加4％。线性规划问题及其标准形式上表显示了在各自的媒体上做一单位广告的相应产品市场份额的估计增加额。（一个单位是指利博公司通常采用的一个广告标准批量，但其他数量也是允许的。）在电视一列中洗衣粉的增加份额为－1％的原因是新的液体洗涤剂的电视商业广告会带走一些洗衣粉的销售额。表中最后一行显示了两种媒体中每一种媒体上做广告的单位成本。

管理部门的任务是：若要以最低的总成本达到市场份额的目标要求，那么在每种媒体上做多少钱的广告？线性规划问题及其标准形式若用百分数，就都用百分数；否则，就两边同乘100。数学模型线性规划问题及其标准形式对于求取一组变量，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划（LinearProgramming）。1.线性规划的定义与数学描述（模型）线性规划问题及其标准形式对决策变量有非负要求。用一组未知变量表示要求的方案，这组未知变量称为决策变量；存在一定的限制条件，且为线性表达式，叫约束条件；有一个目标要求（最大化／最小化），目标表示为未知变量的线性表达式，称之为目标函数；2.引例中线性规划模型的特点：3.线性规划的数学描述（数学模型）（1）一般形式：线性规划问题及其标准形式目标函数？价值系数？约束条件？技术系数？限额系数？线性规划问题及其标准形式模型的参数是数学模型中的常数。决策变量的任何一个取值称为模型的一个解。满足所有约束条件的解称为可行解。反之，一个非可行解至少违反一个约束条件。全部可行解的集合称为可行域。使目标函数达到最大值的可行解称为最优解。该目标函数值为最优值。线性规划问题及其标准形式一般情况下，m<n.模型隐含的假设：比例性：每种经营活动对目标函数的贡献和对资源的消耗是一个常数(不存在边际效用递减效用)。可加性：决策变量是相互独立的，决策变量之间不发生关联，不允许变量之间的交叉。连续性：决策变量应取连续值。确定性：所有参数是确定的，不包含不确定因素。（2）紧缩形式线性规划问题及其标准形式（3）矩阵形式其中:线性规划问题及其标准形式（4）向量—矩阵形式：其中：线性规划问题及其标准形式线性规划问题及其标准形式1、LP标准型的概念（1）什么是LP的标准型？（2）LP标准型的特点？目标函数约定是极大化Max(或极小化Min；约束条件均用等式表示；决策变量限于取非负值；右端常数均为非负值；线性规划问题及其标准形式（3）数学表达式:

有几种形式?为什么?如何书写?2.LP问题的标准化（1）目标函数的标准化

线性规划问题及其标准形式目标函数标准化示意图线性规划问题及其标准形式（2）约束条件的标准化约束条件是“≤”类型——左边加

非负松弛变量，变为等式；约束条件是“≥”类型——左边减

非负松弛变量，变为等式；变量符号不限——引入新变量线性规划问题及其标准形式将下面的线性规划问题化为标准型：讨论：

如何下手？标准化过程排序

-------课堂练习1-2线性规划问题及其标准形式课堂练习1-2

提问、答疑、讨论

总结，看最终结果线性规划问题及其标准形式线性规划问题及其标准形式注释一：线性规划问题的标准形式是与原始形式等价的，即一个线性规划问题的最优解与其标准形式的最优解的值应该是一样的。一个问题的标准形式并不改变问题的本质，它只是改变对问题约束条件的写法。Matlab,LINDO与LINGO等中关于线性规划问题的结论显示就是这类标准化形式。线性规划问题及其标准形式注释二：在标准型中，松弛变量的系数为零，表示松弛变量是未使用的资源，不对目标函数产生任何影响。但是在实际问题中，可以出售未使用的资源，以使公司获得利润。在此情形下，松弛变量就变成表示公司可以出售多少未使用资源的决策变量。可行解：满足约束条件和非负条件的决策变量的一组取值。最优解：使目标函数达到最优值的可行解。基本解：设AX=b是含n个决策变量、m个约束条件的LP的约束方程组，B是LP问题的一个基，若令不与B的列相应的n-m个分量（非基变量）都等于零，所得的方程组的解称为方程组AX=b关于基B的基本解，简称为LP的基本解。B

对应的决策变量

令非基变量取值为零，计算出基变量取值，两者搭配构成基本解。线性规划问题解的概念和性质4.基本可行解（对应的基为可行基）：满足非负条件的基本解。

5.基本最优解（对应的基为最优基）：使目标函数达到最优值的基本可行解。最优解基本最优解线性规划问题解的概念和性质基解与基可行解有如下性质：每一个变量是非基变量或基变量，二者必居其一。基变量个数等于方程之个数。令非基变量为0，同时由方程组的右端项系数得到基变量之值。若基变量满足非负性约束，则基解就是一个基可行解。线性规划问题解的概念和性质用画图、模型制作、三维动画等方法清楚地显示其可行解、基本解、基本可行解。进一步具体计算出这些解来，说明它们之间的关系。课后小组讨论1研究约束集合线性规划问题解的概念和性质PART02线性规划问题的图解法与解的性质线性规划问题的图解法（解的几何表示）1．什么是图解法？线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解思路是：先将约束条件加以图解，求得满足约束条件的解的几何区域（可行域），然后结合目标函数的要求从可行域中找出最优解。

线性规划问题的图解法（解的几何表示）1．图解法举例

实施图解法，以求出最优生产计划（最优解）。线性规划问题的图解法（解的几何表示）由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可进行图解了

线性规划问题的图解法（解的几何表示）约束条件的图解：

每一个约束不等式在平面直角坐标系中都代表一个半平面，只要先画出该半平面的边界，然后确定是哪个半平面。

?

怎么画边界

怎么确定半平面线性规划问题的图解法（解的几何表示）如果全部的劳动工时都用来生产A产品而不生产B产品，那么A产品的最大可能产量为3吨，计算过程为：

这个结果对应着右图中的点A(3,0)，同样我们可以找到B产品最大可能生产量对应的点B(0,3)。连接A、B两点得到约束：

所代表的半平面的边界:

即直线AB。线性规划问题的图解法（解的几何表示）第二个约束条件的边界---直线CD:

线性规划问题的图解法（解的几何表示）

线性规划问题的图解法（解的几何表示）

线性规划问题的图解法（解的几何表示）

线性规划问题的图解法（解的几何表示）0123456789x1

54321x2x1（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）

线性规划问题的图解法0123456789x1

321x2x1（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）

无穷多个最优解线性规划问题的图解法0123456789x1

321x2x1（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）

无穷多个最优解线性规划问题的图解法

唯一最优解0123456789x1x2x1（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）线性规划问题的图解法例1-3：无界解

线性规划问题的图解法本例中的可行域是一个无界区域，如图中阴影区所示。虚线为目函数等值线，沿着箭头所指的方向平移可以使目标函数值无限制地增大，因此找不到最优解。这种情况通常称为无“有限最优解”或“最优解无界”。如果一个实际问题抽象成像例4这样的线性规划模型，比如是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大，解释不合理。此时应重新检查和修改模型，否则就没有实际意义。无界解

线性规划问题的图解法无界解和无可行解统称为无最优解产生无界解的原因是遗漏了约束条件。改变目标函数可能会使一个无界问题变成一个有界问题。(缺乏必要的约束条件)无可行解同目标函数无关，是因为约束条件太苛刻。（矛盾的约束条件）注释：线性规划问题的图解法综上，用图解法求解线性规划时，各种求解结果与各种类型的可行域之间的对应关系可以用下图加以描述：解的类型可行域类型唯一最优解非空有界无穷多最优解最优解无界（无“有限最优解”）无界无解（不存在可行域）空集线性规划问题的图解法注释线性规划问题的可行域非空时，它是有界或无界凸多变形。若线性规划问题存在最优解，它一定在可行域的某个顶点得到。若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即无穷多最优解。线性规划问题的图解法

线性规划问题的图解法

线性规划问题的图解法图解法小结使用条件：仅有两个至多不超过三个决策变量的线性规划。基本步骤：第一步---建立平面直角坐标系；第二步---根据约束条件和非负条件画出可行域。第三步---作出目标函数等值线（至少两条），结合目标函数优化要求，平移目标函数等值线求出最优解。图解法的优缺点：简单、直观但有局限性。图解法求解线性规划图解法的局限性(1)图解法的优点:简单、直观;(2)局限性:对仅含有两个至多不超过三个决策变量的线性规划才适于使用图解法，大多数情况下仅对含有两个决策变量的线性规划才使用图解法求解;(3)对含有三个以及三个以上决策变量的线性规划则应考虑使用更加有效的通用算法——单纯形法来进行求解。

线性规划问题的图解法用图解法求解以下的线性规划问题：课堂练习按小组分工完成：①画约束条件1,2；②画约束条件3并标明可行域；③画目标函数等值线；④说明如何得到最优解,算出相应的目标函数最优值。其他小组进行讲评。线性规划问题的图解法课堂练习(2,2)

12345x1X2

543210

C=2C=10线性规划问题的图解法

12345x1X2543210(2,2)

C=2C=10I(4,0)E(0,-2)H(6,4)G(0,4)F(-2,0)2.1基本可行解的几何意义1、讨论课堂练习

（1）如何求得基本解？

（2）观察图解法求解图，其中点I、H、G均在第一象限，它们是基本解，但不是基本可行解，这与基本可行解非负性有无矛盾？

基本可行解的几何意义

基本可行解的几何意义求解结果：H(6,4,-6,0,0)T,C(3,1,0,3,0)T,

B(2,2,0,0,2)T,D(2,0,2,4,0)T,

F(-2,0,6,0,4)T,I(4,0,0,6,-2)T,

E(0,-2,6,6,0)T,A(0,1,3,0,3)T,

G(0,4,0,-8,6)T,O(0,0,4,2,2)T;基本可行解的几何意义2、结论：

(1)基本解对应所有可行域边界及其延长线、坐标轴之间的交点；

(2)基本可行解对应可行域的顶点。线性规划解的性质

线性规划解的性质

线性规划解的性质2、线性规划问题解的性质定理：

线性规划解的性质

X是D的一个顶点<=>X的正分量所对应的系数列向量线性无关线性规划解的性质

线性规划解的性质（2）定理1-2（反证法）

线性规划解的性质

线性规划解的性质（2）定理1-2（反证法）

线性规划解的性质定理1-3若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。

线性规划解的性质

线性规划解的性质

线性规划解的性质

线性规划解的性质课后讨论：（1）读懂证明，理清思路，写出从最罗嗦的证明过渡到最简洁的证明过程（加上边注——段落大意）线性规划解的性质

LP的可行域一定是凸集，但是凸集不一定成为LP的可行域，而非凸集一定不会是LP的可行域。（为什么？能举例说明吗？）线性规划的基本可行解和可行域的顶点是一一对应的（类似于坐标与点的对应关系！）在可行域中寻找LP的最优解可以转化为只在可行域的顶点中找，从而把一个无限的问题转化为一个有限的问题。若已知一个LP有两个或两个以上最优解，那么就一定有无穷多个最优解。PART03单纯形法单纯形法图解法的局限性？

1947年G.B.Dantzig提出的单纯形法提供了方便、有效的通用算法求解线性规划。单纯形法1、顶点的逐步转移即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。一、单纯形法的基本思想单纯形法单纯形法2、顶点转移的依据？根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。因此，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。单纯形法

3.转移条件？4.转移结果？使目标函数值得到改善得到LP最优解，目标函数达到最优值（单纯形法的由来？）

单纯形法5.单纯形算法要解决的四个问题：（1）找到一个初始的基本可行解，使迭代开始；（2）如何判断一个基本可行解是否为最优解？判断准则是什么？（3）如果不是最优解，怎样找到下一个基本可行解（始终保持基的可行性），同时使目标函数取值得到改善（更大或更小）？（4）如何判断是否没有有限最优解？单纯形法二、单纯形法原理

（原材料约束）

（劳动力约束）例1-5单纯形法第一步：引入非负的松弛变量x4,x5,将该LP化为标准型单纯形法第二步：寻求初始可行基，确定基变量

第三步：写出初始基本可行解和相应的目标函数值单纯形法两个关键的基本表达式：①用非基变量表示基变量的表达式单纯形法②用非基变量表示目标函数的表达式请解释结果的经济含义——不生产任何产品，资源全部节余（x4=3，x5=9），三种产品的总利润为0！

单纯形法第四步：分析两个基本表达式，看看目标函数是否可以改善？①分析用非基变量表示目标函数的表达式

非基变量前面的系数均为正数，所以任何一个非基变量进基都能使Z值增加通常把非基变量前面的系数叫“检验数”；单纯形法②选哪一个非基变量进基？

选x1为进基变量（换入变量）问题讨论：能否选其他的非基变量进基？

任意一个

任意一个正检验数对应的非基变量

最大正检验数对应的非基变量

排在最前面的正检验数对应的非基变量×

单纯形法③确定出基变量：问题讨论

单纯形法用非基变量表示基变量的表达式

当x1增加时，x4，x5会减小，但有限度——必须大于等于0，以保持解的可行性！于是单纯形法

当x1的值从0增加到3时，x4首先变为0，此时x5=6>0因此选x4为出基变量（换出变量）。这种用来确定出基变量的规则称为“最小比值原则”（或θ原则）。如果P1≤0，会出现什么问题？

最小比值原则会失效！单纯形法

基变换新的基变量——x1,x5；新的非基变量x2,x3,x4；写出用非基变量表示基变量的表达式：

由→单纯形法⑤写出用非基变量表示目标函数的表达式:可得相应的目标函数值为Z（1）=6检验数仍有正的返回①进行讨论。单纯形法第五步：上述过程何时停止？——分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正时，当前的基本可行解就是最优解!

为什么？三、表格单纯形法：1、

初始单纯形表的建立

(1)表格结构：

单纯形法（2）表格设计依据：

将-Z看作不参与基变换的基变量，把目标函数表达式改写成方程的形式，和原有的m个约束方程组成一个具有n+m+1个变量、m+1个方程的方程组：单纯形法取出系数写成增广矩阵的形式：

-ZX1X2…XnXn+1Xn+2…Xn+mb-Z，Xn+1，…，Xn+m所对应的系数列向量构成一个基单纯形法用矩阵的初等行变换将该基变成单位阵,这时

变成0，相应的增广矩阵变成如下形式：

单纯形法（3）检验数的两种计算方法：①利用矩阵的行变换，把目标函数表达式中基变量前面的系数变为0；②使用计算公式——

增广矩阵的最后一行就是用非基变量表示目标函数的表达式,(j=1,2,…,n)就是非基变量的检验数。单纯形法2、例1-5的表格单纯形法计算过程：2330003111103/109147019/102330023111103/106036-116/3-6011-202110-14/3-1/332012-1/31/3-800-1-5/3-1/3

单纯形法

单纯形法四、单纯形法的一般描述：1、

初始可行解的确定

(1)初始可行基的确定

观察法——观察系数矩阵中是否含有现成的单位阵？

LP限制条件中全部是“≤”类型的约束

——将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；单纯形法

先将约束条件标准化，再引入非负的人工变量，以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”；然后用大M法或两阶段法求解；

线性规划限制条件都是“≥”或“=”类型的约束——单纯形法等式约束左端引入人工变量的目的使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。（注意：用非基变量表示基变量的表达式）单纯形法①如果限制条件中既有“≤”类型的约束，又有“≥”或“=”类型的约束，怎么办？构造“不完全的人造基”！

讨论②为什么初始可行基一定要选单位阵？b列正好就是基变量的取值，检验数行和b列交叉处元素也正好对应目标函数值，因此称b列为解答列单纯形法（2）写出初始基本可行解——

根据“用非基变量表示基变量的表达式”，非基变量取0，算出基变量，搭配在一起构成初始基本可行解。

2、建立判别准则：（1）两个基本表达式的一般形式就LP限制条件中全部是“≤”类型约束，新增的松弛变量作为初始基变量的情况来描述：单纯形法此时LP的标准型为单纯形法初始可行基：初始基本可行解：

单纯形法

一般（经过若干次迭代），对于基B，用非基变量表出基变量的表达式为：用非基变量表示目标函数的表达式：

单纯形法单纯形法

（2）最优性判别定理（3）无“有限最优解”的判别定理

单纯形法证明思路——构造性证明：依据用非基变量表示基变量的表达式构造一族可行解，其对应的目标函数值趋于无穷大。几何意义：沿着无界边界前进的一族可行解单纯形法举例：用非基变量表示基变量的表达式

代表两个约束条件：x2对应的系数列向量P2=（1，3）T，当前的换入变量是

X2，按最小比值原则确定换出变量：单纯形法要求：

于是：

如果x2的系数列变成P2’=（-1，0）T,则用非基变量表示基变量的表达式就变成；

可行性自然满足,最小比值原则失效,意即x2的值可以任意增大→原线性规划无“有限最优解”。单纯形法3、进行基变换（1）选择进基变量——原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善（较快增大）；

进基变量对应的系数列称为主元列。（2）出基变量的确定——按最小比值原则确定出基变量，为的是保持解的可行性；

出基变量所在的行称为主元行。主元行和主元列的交叉元素称为主元素。单纯形法思考题

这样进行基变换后得到的新解对应的系数列向量是否线性独立？

4、主元变换（旋转运算或枢运算）

按照主元素进行矩阵的初等行变换——把主元素变成1，主元列的其他元素变成0（即主元列变为单位向量）写出新的基本可行解，返回最优性检验。单纯形法单纯形法小结

求解思想－－

顶点的逐步转移，

条件是使目标函数值不断得到改善。单纯形法表格单纯形法求解步骤第一步：将LP化为标准型，并加以整理。引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。（这一步计算机可自动完成）

确定初始可行基，写出初始基本可行解单纯形法第二步：最优性检验计算检验数，检查：所有检验数是否≤0？

是——结束，写出最优解和目标函数最优值；还有正检验数——检查相应系数列≤

0？是——结束，该LP无“有限最优解”！不属于上述两种情况，转入下一步—基变换。确定是停止迭代还是转入基变换？单纯形法选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量；最小比值对应的行为主元行，主元行对应的基变量为换出变量。第三步：基变换确定进基变量和出基变量。单纯形法

利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。第四步换基迭代（旋转运算、枢运算)完成一次迭代，得到新的基本可行解和相应的目标函数值单纯形法该迭代过程直至下列情况之一发生时停止

检验数行全部变为非正值；（得到最优解）或主元列≤

0（最优解无界）

停止迭代的标志（停机准则）

依据：最优性检验的两个定理最优性判别定理；无“有限最优解”判断定理单纯形法几种特殊解的情形单纯形法1.退化解在线性规划中，当单纯形表中的基本可行解中出现一个或多个基变量等于零，或者在确定换出基变量时存在两个以上相同最小比值的情况，便称为退化，退化问题的最优解被称为退化解。这种情况通常是由于模型中存在多余的约束，导致多个基本可行解对应同一顶点。退化解的出现可能会导致单纯形法陷入循环，使得算法进展缓慢甚至无法继续进行。单纯形法1.退化解利用单纯形法求解以上线性规划问题得到的单纯性表如下：单纯形法

32000基基b084-1100201243010308410012032000

321-0.250.25001010-6023.50-2

084-1100201243010308410012032000

我们可以注意到，在迭代过程中出现了基变量为0的情况，进行了多次迭代，而基从B1，B2又返回到B1，即出现计算过程的循环，此时便出现了退化现象。单纯形法2.无穷多最优解线性规划问题的最优解有可能并非唯一，如果存在多个基本可行解（即不同的顶点）具有相同的最优目标函数值，则可以推断该线性规划问题存在无穷多个最优解。单纯形法

5050000基b50501010-105000-2115025001001-1500000-5000

单纯形法

5050000基b5010010-11005000-21150200012-10-1500000-5000单纯形法由此我们可以推得，存在无穷多最优解的判定条件是最终单纯性表中的某个非基变量的检验数为0。但是需要注意的是，这只是一个必要条件而非充要条件，由最终单纯性表中的某个非基变量的检验数为0并不能推得线性规划问题存在无穷多最优解，因为也可能存在两个不同的最优基可行解对应同一个顶点的情况，此时线性规划的最优解仍然是唯一的。PART04线性规划的应用线性规划的应用一、使用线性规划方法处理实际问题必须具备的条件

(建模条件)：1、优化条件---问题的目标有极大化或极小化的要求,而且能用决策变量的线性函数来表示。2、选择条件---有多种可供选择的可行方案，以便从中选取最优方案。3、限制条件---达到目标的条件是有一定限制的（比如，资源的供应量有限度等），而且这些限制可以用决策变量的线性等式或线性不等式表示出来。此外，描述问题的决策变量相互之间应有一定的联系，有可能建立数学关系，即这些变量之间是内部相关的。线性规划的应用二、建模步骤：

第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。

第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，以避免“遗漏”或“重复”所造成的错误。

第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加以确定。

讨论：这三步的顺序可以颠倒吗？

为什么？线性规划的应用

三、经济管理领域中几类典型的LP问题

经济管理领域中有大量的实际问题可以归结为线性规划问题来研究，这些问题背景不同，表现各异，但数学模型却有着完全相同的形式。尽可能多地掌握一些典型的模型不仅有助于深刻理解线性规划本身的理论和方法，而且有利于灵活地处理千差万别的实际问题，提高解决实际问题的能力。线性规划的应用（一）

生产组织与计划问题1.

产品计划问题2.

产品配套问题线性规划的应用1、产品计划问题

问题的一般提法：用若干种原材料（资源）生产某几种产品，原材料（或资源）供应有一定限制，要求制定一个产品生产计划，使其在一定数量的资源限制条件下能得到最大的收益。线性规划的应用

如果用，

单位产品所需资源数（如原材料、人力、时间等）、所得利润及可供应的资源总量已知，如表所示，问应如何组织生产才能使利润最大？线性规划的应用线性规划的应用设出产品的计划数，可列出这类问题的数学模型如下：

线性规划的应用一般的产品计划问题举例

例1-7某工厂生产A、B两种产品，均需经过两道工序，每生产一吨产品A需要经第一道工序加工2小时，第二道工序加工3小时；每生产一吨产品B需要经第一道工序加工3小时，第二道工序加工4小时。可供利用的第一道工序为12小时，第二道工序为24小时。生产产品B的同时产出副产品C，每生产一吨产品B，可同时得到2吨产品C而毋需外加任何费用；副产品C一部分可以盈利，剩下的只能报废。出售产品A每吨能盈利400元、产品B每吨能盈利1000元，每销售一吨副产品C能盈利300元，而剩余要报废的则每吨损失200元。经市场预测，在计划期内产品C最大销量为5吨。试列出线性规划模型，决定A、B两种产品的产量，使工厂总的利润最大。线性规划的应用

信息整理：线性规划的应用线性规划的应用数学模型：设：x1——产品A的产量，x2——产品B的产量，x3——产品C的销售量，x4——产品C的报废量。依题意，可得线性规划的应用2、产品配套问题

例1-8

某产品由两个零件I和三个零件II组成，每个零件均可由三个车间各自生产，但各车间的生产效率和总工时限制各不相同，表中给出了有关信息。试确定各车间生产每种零件的工作时间，使生产产品的件数最多。

线性规划的应用线性规划的应用例1-8有关信息表处理：线性规划的应用于是得到该问题的LP模型为：线性规划的应用

(二)

合理下料问题在加工业中，经常遇到这类问题。

问题的一般提法是：已知某种尺寸的棒料或板材，需要将其切割成一定数量既定规格的几种零件毛坯，问应如何选取合理的下料方法，使得既满足对截出毛坯的数量要求，又使所用的原材料最少（或废料最少）？线性规划的应用解决这类问题一般有两个步骤：

步骤一、按照一定的思路设法列出所有的排料方案（也称下料方案或排料图），当方案很多，甚至无法一一列出时，通常应先确定一些筛选原则，把明显不合理的方案删除，仅仅考虑剩余的为数不太多的方案；步骤二、设xi表示按第ｉ种方案下料的棒料根数（或板材块数）i=1,2,…,n，按照问题的要求建立LP模型。线性规划的应用例1-9

某厂接受了一批加工定货，客户要求加工100套钢架，每套由长2.9米、2.1米和1.5米的圆钢各一根组成。现在仅有一批长7.4米的棒料毛坯，问应如何下料，使所用的棒料根数最少？线性规划的应用

最简单的处理方法：从一根棒料上截取2.9米、2.1米和1.5米的棒料各一根，正好配成一套钢架，100套钢架总共需要100根棒料毛坯。每根棒料毛坯剩下0.9米的料头,100根毛坯总共剩90米料头。

——这是最好的办法吗？合理套裁肯定会有更好的效果。先设法列出所有的下料方案，思路如图。线性规划的应用排列下料方案思路图

线性规划的应用

设xi为按第i种方案下料的棒料根数，建立LP模型如下：线性规划的应用

（三）

合理配料问题

问题的一般提法：由多种原料配置成含有m种成分的产品，已知产品中所含各成分的需要量及每种原料的价格，同时知道各种原料中所含m种成分的数量，要求给出使产品成本最低的配料方案。如：伙食问题（也称营养问题）、饲料配比问题、化工产品中的混合问题等都属于这类问题。

线性规划的应用例1-10营养问题

要求制定既经济又合乎健康标准的食谱。一个简单的例子：现准备采购甲、乙两种食品，表中给出了已知价格及相关的营养成分。最右栏给出了按营养学标准每人每天的最低需要量。问应如何采购食品才能在保证营养要求的前提下花费最省？线性规划的应用

营养问题已知数据表线性规划的应用

线性规划的应用

营养问题适用范围：

&

运动员集训队食谱设计；

&

幼儿园、医院等特殊群体的营养配餐；

&

机关、学校、企业等企事业单位团体伙食设计；

&家庭食谱设计；线性规划的应用

对不同对象的营养要求——从营养学资料和通过医生咨询得到；

各种食品的价格——通过不同季节的市场调查获取；

一些特殊要求，比如饮食习惯、偏好等——可通过适当处理，转化为约束条件加入模型；资料获取渠道及特殊要求的处理建议：线性规划的应用

例1-11（饲料配比问题）某配合饲料厂生产以鸡饲料为主的配合饲料，现准备研制一种新的肉用仔鸡专用饲料，所用原料的营养成分和饲养标准见下表，希望这种新饲料能满足肉用仔鸡的喂养需要又使总成本尽可能低，应如何设计配比方案？线性规划的应用线性规划的应用

已知各种原料的购进价1公斤分别为:0.314(玉米)、054(豆饼)、0.22（麦麸）、1.20（鱼粉）、0.40（骨粉）、0.50（鸡促进素）元。线性规划的应用

设每100公斤饲料中配给的玉米、豆饼、麦麸、鱼粉、骨粉、鸡促进素分别为x1、x2、x3、x4、x5、x6公斤，则饲料配比即为x1：x2：x3：x4：x5：x6；于是，可建立下面的线性规划：线性规划的应用

是否可以将约束条件两边分别扩大一个倍数再进行计算？

线性规划的应用（四）

运输问题运输问题大体上可以分为四种类型：1、产销平衡的运输问题（也称物资调运问题）2、产销不平衡的运输问题3、作物布局问题4、工厂布局问题线性规划的应用类型1：产销平衡的运输问题（物资调运问题）线性规划的应用

线性规划的应用线性规划的应用

线性规划的应用

可得运输问题的数学模型如下：

类型2：产销不平衡的运输问题线性规划的应用对于产销不平衡的运输问题，可以通过将其转化为一个产销平衡的运输问题来求解。当供大于求时，可以增加一个虚拟销地，供不应求时则增加一个虚拟产地，对应的运距（或运价）均设为零，然后应用表上作业法求出最优调运方案。类型3：作物布局问题一般提法是：在若干块土地上种植若干种作物，已知各块土地的面积、作物计划播种面积及单产，问如何安排种植计划，使总产量最高？类型4：工厂布局问题线性规划的应用

作物布局问题和工厂布局问题表面上看和运输问题没有联系，但从建立的线性规划模型来看则完全类似，所以上述几类问题均归结为“运输问题”。线性规划的应用线性规划的应用例1-12甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见下表，求使总运输量最少的调运方案。线性规划的应用

线性规划的应用根据本题中的煤矿日产量约束城市需求约束，以及总运输成本最小的目标可得该问题的数学模型如下：例1-13

某油田通过输油管道向港口输送原油，中间有4个泵站，每段管道上的输送能力如图所示，已知泵站没有储存能力，求这个系统的最大输送能力。（五）最大流量问题线性规划的应用泵站4泵站3油田S泵站2泵站1码头t512

481167

10线性规划的应用

设从各点往其它点的输送量如下表所示

出发点

到达点

输送量SS泵站1泵站1泵站2泵站2泵站3泵站3泵站4泵站1泵站2泵站3码头t泵站3泵站4泵站4码头t码头tx1x2x3x4x5x6x7x8x9线性规划的应用依题意：目标函数为输送原油的总量；约束条件有两类:一类是管道上的流量约束；另一类是每个中间泵站上的平衡约束，即中间泵站上的原油流入量和流出量相等根据上述分析建立线性规划模型如下：线性规划的应用1号泵站平衡约束2号泵站平衡约束3号泵站平衡约束4号泵站平衡约束相应弧上的约束线性规划的应用（1）排班问题六、其他类型的问题线性规划的应用例1-14某快递公司新设了一个快递分拣部，处理每天送达和外寄的快递件，现需要招聘一批职工来操作机器进行分拣工作。该公司由以往的统计数据分析与经验预测得到每个时间段到达的快件数如下表所示：时段到达快件数量时段到达快件数量10点前500014点-16点800010点-12点700016点-18点750012点-14点800018点-20点6000线性规划的应用已知该分拣部共有11台机器，每台机器的分拣速度为500件/小时，每台机器各需要配一名职工。分拣部一部分为正式职工，上班时间分别为10-18点、12-20点、14点-22点，每人每天工资200元；另一部分是临时工（非正式职工），每天上班6小时，分别为12-18点、14-20点、16-22点，每天工资120元，职工上班的班次时间段如下表所示。快件处理的规则是从每个整点起可处理该整点前到达的快件数，因快件有时间性要求，凡是12点前到达的快