运筹学（广东外语外贸大学）

现代管理科学的重要基础和手段经济和管理的重要工具具有适用性强,应用面广的特点广东外语外贸大学GuangdongUniversityofForeignStudies课程目的我们学习这门课程的目的是要树立优化思想,认识运筹学对实现管理的科学化和现代化的重要意义和作用,掌握运筹学的基本思想和方法,并能结合相关软件的使用解决管理中的实际问题。运筹学主导教材和主要参考书主导教材:《管理运筹学》（第2版）,韩伯棠编著,高等教育出版社。主要参考书:ll></a>.《运筹学》（修订版）,钱颂迪主编,清华大学出版社;.《数据模型与决策》（第11版）,DavidR.Anderson,etc.,侯文华等译，机械工业出版社;.《运筹学教程》,胡运权主编,清华大学出版社.《运筹学模型与方法教程》,程理民等,清华大学出版社;.《运筹学应用案例集》，胡运权主编,清华大学出版社;.《运筹学模型与方法教程例题分析与解题》，刘满凤等,清华大学出版社;.《运筹学方法及其微机实现》,汪遐昌,电子科技大学出版社。主要参考期刊及网站《运筹与管理》,中国运筹学会《运筹学学报》，中国运筹学会《系统工程理论与实践》,中国系统工程学会《系统工程》，湖北省系统工程学会中国运筹学会运筹学网络资源导航OperationsResearchEuropeanJournalofOperationalResearchhttp://J/is/Navigation/Mathematics/operations.htmhttp://.ors43x/a>/第一章绪论§1决策、定量分析与管理运筹学§2运筹学的分支§3运筹学在工商管理中的应用§4学习运筹学必须使用相应的计算机软件,必须注重于学以致用的原则第一章绪论“运筹学”的释义运筹学（OperationalResearch（英式）；OperationsResearch（美式））直译为“运作研究”、“作业研究”或“运用研究”,简称0R。中文“运筹”二字取自《史记??高祖本记》中,刘邦“夫运筹帷幄之中，决胜于千里之外,吾不如子房”。运筹学是ー门决策科学,优化科学。第一章绪论我国古代运筹思想运用的典故.“田忌赛马”“田忌赛马”是家喻户晓的历史故事。战国时齐威王与齐相田忌赛马,双方各出三匹马比赛,每胜…场赢得一千金。由于王府的马比相府的马好,所以田忌每次比赛都要输掉三千金。后来田忌的谋士孙膑献了一计:在每次开赛前要求对方先报马名,由此区分对方参赛的是上马、中马还是下马;然后以自己的上马对对方的中马、自己的中马对对方和下马、自己的下马对对方的上马。这样,两胜・负反而赢得一千金。第一章绪论我国古代运筹思想运用的典故.晋国公重建皇城晋国公重建皇城的施工方案,体现了运筹学的朴素思想。要使重建工程的各个エ序,在时间、空间上彼此协调,环环相扣,就需要运用行列式的相关知识,进行精确计算.点击图连接相关网页第一章绪论运筹学的产生和发展运筹学作为ー门系统的科学,产生的背景为第二次世界大战。主要用于解决如何在与德军的对抗中最大限度地杀伤敌人,减少损失。二战期间英国为解决空袭的早期预警,作好反侵略战争准备,积极进行‘‘雷达”的研究。但随着雷达性能的改善和配置数量的增多,出现了来自不同雷达站的信息以及雷达站同整个作战系统的协调配合问题。第一章绪论1938年7月,波得塞(Bawdsey)雷达站的负责人罗伊(A.P.Rowe)提出立即进行整个防空作战系统运行的研究,并用“OperationalResearch"ー词作为这方面研究的描述,这就是OR名词的起源。1940年9月英国成立了由物理学家布莱克特(P.M.S.Blackett)领导的第一个运筹学小组，后来发展到每ー个英军指挥部都成立运筹学小组。1942年美国和加拿大也都相继成立运筹学小组。这些小组在确定扩建舰队规模、开展反潜艇战侦察和组织有效对敌轰炸等方面作了大量研究,为取得反法西斯战争的胜利及运筹学有关分支的建立作出了贡献。第一章绪论运筹学在第二次世界大战中成功运用的例子:如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等。典型战例:.不列颠之战.盟军封锁直布罗陀海峡第一章绪论不列颠之战1941年,希特勒为了实施在英伦三岛登陆的计划,命令德国空军轮番对英国进行狂轰滥炸。当时英国皇家空军以ー比七的数量劣势迎战,为此需要尽可能地保持飞机处于飞行状态。于是,空军司令部规定保持70%的飞机在天上巡逻。但是,英军很快发现要保持这么高的飞行比例有困难,因为飞机的被击落的、有需要维修的,飞行员也有伤亡。这ー决策的后果是在空中飞行的飞机数量越来越少。第一章绪论不列颠之战究竟保持多大比例的飞机在巡逻才能持久作战呢?OR小组的专家纷纷研究这个问题,这个问题最后被生物学家康顿解决了。他根据计算生物平均寿命的方法,运用飞机飞行时间、维修时间、空战特点和飞机被落击伤状况等数据,得出的结论是:只要保持35%的飞机在飞行状态,就能使全部飞机的飞行战斗时间最多。这・研究成果为取得不列颠之战的胜利作出了贡献。盟军封锁直布罗陀海峡（猎潜战例）1944年初,为帮助美国海军在连接大西洋和地中海的直布罗陀海峡封锁过往的德军潜艇,美军OR小组的约翰•佩芝姆博士提出了一种“屏障巡逻”飞行战术。第一章绪论盟军封锁直布罗陀海峡（猎潜战例）在深水航道的最窄处划出ー个4英里长、1英里宽的长方形,两架飞机保持在长方形两边线的对称位置上，同时以115英里/小时的速度绕长方形飞行。这样,在长方形上的每一点,每隔3分钟就有ー架飞机巡逻通过。潜艇通过这个区域时,巡逻的飞机至少有两次机会去发现它。就这样,在2月24日到3月16日短短三个星期内,ー个巡逻机中队击沉击伤德军潜艇3艘,自己无一伤亡。第一章绪论第一章绪论二战以后,运筹学得到了快速的发展,形成了许多分支,并且计算机的应用极大地推动了运筹学的应用与普及。运筹学有广泛应用运筹学不仅在军事上,而且在生产、决策、运输、存储等经济管理领域有着广泛的应用。第一章绪论运筹学的定义运筹学是运用分析，试验,量化的方法,对经济管理系统中人、财、物（时间）等有限资源,进行统筹安排,为决策者提供有依据的最优方案（满意方案），以实现最有效地管理。——《中国企业管理百科全书》《辞海》对运筹学解释为:“二十世纪四十年代开始形成的一门科学，主要研究经济活动与军事活动中能用数量来表达的有关运用,筹划与管理方面的问题,它根据问题的要求,通过数学的分析与运算，作出综合性的合理的安排,以达到较经济、较有效地使用人カ、物力。近年来,它在理论与应用方面都有较大发展。其主要分支有规划论、对策论、排队论及质量控制等。”第一章绪论运筹学的特点⑴科学性:运筹学是以研究事物内在规律,并从定量分析的角度探求更好地解决问题的•门科学。第一章绪论运筹学的特点⑵应用性:运筹学既对各种经营进行创造性的科学研究,又涉及到组织的实际管理问题,它具有很强的实践性，最终应能向决策者提供建设性意见,并应收到实效;第一章绪论运筹学的特点⑶多学科的交叉性、综合性:运筹学研究中吸收了来自不同领域的经验,并被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题,故其应用不受行业、部门之限制;第一章绪论运筹学的特点⑷系统性和最优性:它以整体最优为目标,从系统的观点出发,力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解,寻求最佳的行动方案,所以它也可看成是ー门优化技术,提供的是解决各类问题的优化方法。策、定量分析与管理运筹学决策的定义ーー现代管理科学创始人,诺贝尔奖金获得者世界著名经济学家西蒙（H.A.Simon）：管理就是决策。—原中国社会科学院副院长于光远:决策就是作决定。ー为了实现一定目标,运用科学的理论和方法,系统地分析主、客观条件,在掌握大量有关信息的基础上,提出若干预选方案并从中选择出最优方案（满意方案）的分析判断过程（科学的决策）。1.1决策、定量分析与管理运筹学决策方法定性分析方法——借助决策者的知识、经验、分析和判断能力等进行决策的方法。定量分析方法——量化决策问题并建立数学模型进行决策的方法。定性与定量相结合的分析方法学习运筹学能够培养和提高定量分析能力解决问题与制定决策明确问题确定目标提出方案分析方案选择方案实施方案分析结果解决问题决策决策结果评估各个方案:解的检验、灵敏性分析等。确定目标或评估方案的标准执行此方案:回到实践中进行后评估：考察问题是否得到圆满解决.不满意检查运筹学的分支线性规划整数（线性）规划目标规划图与网络模型排序与统筹方法存储论决策分析排队论对策论动态规划预测・非线性规划、多目标规划、随机规划、模糊规划等运筹学在工商管理中的应用生产计划:生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等;库存管理:多种物资库存量的管理,库存方式、库存量等;运输问题:确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等;人事管理:对人员的需求和使用的预测,确定人员编制、人员合理分配,建立人オ评价体系等;运筹学在工商管理中的应用市场营销:广告预算、媒介选择、定价、产品开发与销售计划制定等；财务和会计:预测、贷款、成本分析、定价、证券管理、现金管理等;***设备维修、更新,项目选择、评价,工程优化设计与管理等;§1.3运筹学在工商管理中的应用由国际运筹与管理科学协会(INFORMS)和它的管理科学实践学会(CollegeforthePracticeoftheManagementSciences)主持评奖的负有盛名的弗兰茨•厄德曼(FranyEdlman)奖,就是为奖励优秀的运筹学在管理中的应用的成就设立的,该奖每年举行ー次,在对大量富有竞争力的入闱者进行艰苦的评审后,一般有六位优胜者获奖。关于这些获奖项目的文章都在第二年发表在著名刊物Interface的第一期上,下面列表就是发表在Interface期刊的ー些获奖项目。更优的服务1ーレ1993安装统计销售预测和成品库存管理系统,改进客户服务Merit青铜制品公司第一年7.5亿1-2/2000重组全球供应链,保持最小库存的同时满足客户需求IBM1亿1-M994进行上千个国内航线的飞机优化配置来最大化利润Delta航空公司1500万更多年收入101998制定最优铁路时刻表并调整铁路日运营量法国国家铁路2亿1-M997重新设计北美生产和分销系统以降低成本并加快了市场进入速度宝洁公司生产率提高50%以上11/1975第二部分通过战略调整,缩短维修机器的反应时间,改进维修人员的生产率施乐公司380万17/1981控制成品库存（制定最优再订购点和订购量,确保安全库存）标准品牌公司4.06亿,更多销售1ーレ1990优化商业用户的电话销售中心选址AT&T4000万121987优化商业区和办公楼销售程序荷马特发展公司7000万1-7/1987优化炼油程序及产品供应、配送及营销Citgo石油600万1-y1986满足乘客需求前提下,以最低成本进行订票及安排机场工作班次联合航空公司每年节支（美元）Interface应用组织运筹学方法使用情况（美1983）运筹学方法在中国使用情况（随机抽样）运筹学的发展趋势面向问题服务行业中的应用金融服务业信息、电信服务业医院管理后勤（Logistics）全球供应链管理电子商务:集成特性§1.3运筹学在工商管理中的应用运筹学的发展趋势运筹学与行为科学结合群决策和谈判对策理论多层规划合理性分析随机和模糊OR问题本身的不确定性人类知识的局限性§1.3运筹学在工商管理中的应用运筹学的发展趋势软计算面向强复杂系统的计算、实时控制、知识推理智能算法:模拟退火、遗传算法、人工神经网络、戒律算法等系统仿真IT对运筹学的影响MIS,DSS,MRP-II,CIMS,ERPORDept.->Dept.OfOR&IS§1.3运筹学在工商管理中的应用§1.4学习管理运筹学必须使用相应的计算机软件,必须注重于学以致用的原则学习运筹学要结合实际的应用,不要被ー些概念、理论的困难吓倒。学习运筹学要把注意力放在“结合实际问题建立运筹学模型”和“解决问题的方案或模型的解”两头,中间的计算过程尽可能让计算机软件去完成。本书附有运筹学教学软件,使用方法很简单。学员必须尽快学会使用这个运筹学教学软件,并借助它来学好本课程。学习运筹学是为了用于实践,解决实际问题。以前重视人工计算是因为没有计算机,现在有了就应该好好利用。谢谢大家第一章绪论广东外语外贸大学GuangdongUniversityofForeignStudies的提出解法解法的灵敏度分析第二章线性规划的图解法第二章线性规划的图解法解决以下两类问题资源一定 产出最大（产出:如产量、销售量、利润等）任务一定 投入最小（投入:如资金、人员、时间、原材料等）线性规划（Linearprogram,LP）在工商管理,生产计划安排,交通运输,财贸工作等各项经济活动中，如何应用科学的方法统筹安排，合理利用资源（包括人力、物力、财力等资源）,并使其经济效益达到最优,这些正是现代社会生产规模日益扩大以及各部门和各系统之间的关系日益复杂所面临的新问题。1939年前苏联数学家康托洛维奇提出了生产组织与计划中的线性规划（LinearProgramming简写为:LP）模型，为以上问题的解决提出了一种可行的方法。四十年代末旦茨基和查恩斯等人提出的线性规划问题求解方法一单纯形法,为线性规划的理论和应用奠定了基础,这些都是线性规划的最卓著的开创性工作。§2.1线性规划问题的提出线性规划是研究在线性不等式或等式的限制条件下,使得某ー个线性目标函数取得最大（或最小）的问题。常见的线性规划问题有：（―）运输问题（二）生产的组织与计划问题（三）合理下料问题（四）配料问题（五）布局问题（六）分派问题线性规划研究的内容和问题§2.1线性规划问题的提出线性规划与其它现代技术或方法相结合产生新的定量分析的技术已成为当前出现的ー个极为重要的发展趋势。特别是随着计算机的出现,线性规划与计算机结合形成的应用软件已成为了流行的“商业工具”。据美国商业和科学计算中心的研究可知,线性规划的计算机应用软件已获得了数十亿的经济效益,有很高的市场价值。预计在下ー个十年里,线性规划与计算机的分界线将会逐渐消失，并将脱离各自原来的领域,组合成更通用和应用面更广泛的应用科学的形式。线性规划发展前景§2.1线性规划问题的提出另一方面,以线性规划为基础而发展起来的多部门的线性规划,多时期的线性规划,模糊线性规划,随机线性规划,以及整数规划,非线性规划,目标规划等等,为现代管理中各类实际问题的解决提供了科学的方法。目前线性规划的理论研究仍十分活跃,其应用前景也越来越广阔,它已成为国家重点推广的现代管理方法之…。线性规划发展前景§2.1线性规划问题的提出例1.某工厂在计划期内要安排I、II两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表:问题:エ厂应分别生产多少单位I、II产品才能使工厂获利最多?问题分析:如何安排I、II两种产品的生产使得エ厂获利最大?设定决策变量:设I、II产品的产量分别为xl,x2目标:获利最大的利润制约条件：生产能力和原材料的供给量例1.某工厂在计划期内要安排I、II两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制,如下表:问题:エ厂应分别生产多少单位i、n产品才能使工厂获利最多?线性规划模型（I、H产品的产量分别为xl,x2）：目标函数:Maxz=50xl+100x2约束条件:s.t. xl+x2W3002x1+x2く400x2く250xl,x2三0LP模型三要素•决策变量ー约束条件（线性等式或线性不等式）・目标函数（线性函数,最大化或最小化）§2.1线性规划问题的提出生产组织与决策问题例2.某汽车エ厂可生产大轿车和载重汽车,已知生产每辆汽车所用的钢材均为2吨,该厂每年供应的钢材为1600吨,生产能力为每2.5小时生产ー・辆载重汽车,每5小时生产ーー辆大汽车,工厂全年有效工时为2500小时;已知供应给该厂大轿车用的座椅每年可装配400辆。据市场调查,出售ー辆大轿车可获利4千元,出售ー辆载重车可获利3千元。问在这些条件下,如何安排生产使得エ厂获利最大?§2.1线性规划问题的提出分析：问题是如何安排生产使得エ厂获利最大?设大轿车和载重车的产量分别为xl和x2（辆）,则34利润（千元??辆）（吨??辆）2.5（小时??辆）载重车1600（吨）2500（小时??年）提供量4002（吨??辆）5（小时??辆）大轿车装配座椅（辆??年）钢材生产能力项目产品解:原材料的限制:工时的限制:大轿车座椅的限制:非负限制:分析：问题是如何安排生产使得エ厂获利最大?3利润（千元??辆）22.5（小时??辆）载重车16002500（小时??年）提供量40025（小时??辆）大轿车装配座椅（辆??年）钢材（吨）生产能力项目产品目标:利润最大因此该问题的数学模型为:目标函数约束条件§2.1线性规划问题的提出实际问题LP模型最优解线性规划问题的提出建模过程.理解要解决的问题,了解解题的目标和条件;.定义决策变量（xl,x2，…，xn）,每ー组值表示-•个方案;.用决策变量的线性函数形式写出目标函数,确定最大化或最小化目标;.用ー组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件一般形式目标函数: Max（Min）z=clxl+c2x2+•••+cnxn约束条件:s.t.allxl+al2x2+•••+alnxnく（=,2）bla21xl+a22x2+…+a2nxnく（ラ2）b2amixl+am2x2+,,,+amnxnW(ラ2)bmxl,x2,•••,xn20线性规划问题的提出2.2图解法例1.目标函数：Maxz=50x1+100x2约束条件：xl+x2W300(A)2x1+x2く400(B)x2.250(〇xl20 (D)(E)x220(E)得到最优解:xl=50,x2=250最优目标值z=27500对于只有两个决策变量的线性规划问题,可以在平面直角坐标系上作图表示线性规划问题的有关概念,并求解。下面通过例1详细讲解其方法:100元50元单位产品获利250千克10原料B400千克12原料A300台时11设备资源限制III§2.2图解法(1)分别取决策变量XI,X2为坐标向量建立直角坐标系。在直角坐标系里,图上任意一点的坐标代表了决策变量的ー组值,例1的每个约束条件都代表ー个半平面。x2xlX220X2=0x2xlXl^OX1=O§2.2图解法（2）对每个不等式（约束条件）,先取其等式在坐标系中作直线,然后确定不等式所决定的半平面。100200300100200300xl+x2<300xl+x2=3001001002002xl+x2く4002xl+x2=400300200300400§2.2图解法（3）把五个图合并成一个图,取各约束条件的公共部分,如图2-1所示。100x2く250x2=250200300200300xlx2x2=0xl=0x2=250xl+x2=3002xl+x2=400图2-1(4)目标函数z=50xl+100x2,当z取某ー固定值时得到一条直线,直线上的每一点都具有相同的目标函数值,称之为“等值线”。平行移动等值线,当移动到B点时,z在可行域内实现了最大化。A,B,C,D,E是可行域的顶点,对有限个约束条件则其可行域的顶点也是有限的。xlx2z=20000=50xl+100x2图2-2z=27500=50xl+100x22=0=50x1+100x2z=10000=50xl+100x2CBAD图解法的运算步骤0xlx2别以L.P.模型中的两个变量为横轴和竖轴建立平面直角坐标系（例如可以以例1中的xl为横轴,以x2为竖轴）。2图解法2.2图解法例1.maxZ=xl+3x2s.t.xl+x2く6・xl+2x2く8xl20,x220可行域64-860xlx22.在所建立的平面坐标系中画出约束条件所围成的区域图形ーー可行（解集）域（thefeasibleregion）,并将其用阴影表示出来。例1.maxZ=xl+3x2s.t.xl+x2く6・xl+2x2く8xl20,x220可行域640xlx2Z=xl+3x2=03.画出目标函数的图形（通常可画出当目标函数值为零时的（基准）目标函数图）,确定目标函数平行移动的方向,并沿目标函数直线的法向用小箭头标出。§2.2图解法.将（基准）目标函数直线沿所标示的方向平行移动直至可行域的边界,若这时目标函数的直线与可行域的边界点或边界线重合,则其重合点或重合线段上的点即为此L.P.问题的最优解,当重合部分为一点,则该点的坐标即为原L.P.的唯一解，当重合部分为一条线段时,则该线段上的任一点的坐标即为原L.P.的解,这时原L.P.问题有无穷多个解;否则,原LP.问题无解。2.2图解法xl+2x2=8可行域目标函数等值线最优解64860xlx2目标函数基准线Z=xl+3x2=0Pxl+x2=6设点P的坐标为（xl,x2）,则可由以下方程解得xl,x2：xl+x2=6-xl+2x2=8解得:xl=明x2=14/3maxZ=xl+3x2maxZ=xl+3x2最优值为: maxZ=xl+3x2=转+3X14/3=4^3-xl+2x2=8可行域目标函数等值线最优解64860xlx2目标函数基准线Z=xl+3x2=0Pxl+x2=6故最优解为: xl=钻,x2=14/3§2.2图解法例2.求解L.P.问题:maxZ=xl+x2s.t.xl+x2W6・xl+2x2W8xl20,x220解:以xl为横轴,以x2为竖轴建立直角坐标系,并根据题意画图。maxZ=xl+x2xl+x2=6可行域目标函数等值线最优解64-860xlx2目标函数基准线Z=xl+x2=0PQ-xl+2x2=8由图可知例2的目标函数在线段PQ上任一点处均取最大值,原问题有无穷多个最优解。设点P的坐标为(xl,x2),则可解得点P的坐标为(利,1%)。故原问题的一ー个最优解为:xl=明，x2=l转其最优值为:maxZ=xl+3x2=*+1必=6例3.§2.2图解法maxZ=xl+x2s.t.2xl-x222-xl+2x2く8x!20,x220目标函数等值线-810xlx2Z=xl+x2=0可行域目标函数无上界,无最优解例4.解法minZ=xl+x2s.t.2xl-x222・xl+2x2W8xlNO,x2さ0-24-810xlx2Z=xl+x2=0可行域最优解目标函数等值线§2.2图解法重要结论:如果线性规划有最优解,则一定有一个可行域的顶点对应一个最优解;无穷多个最优解。如例3,线段PQ上的所有点都代表了最优解;无界解。即可行域的范围延伸到无穷远,目标函数值可以无穷大或无穷小,如例4。一般来说,在实际问题中,这说明模型有错,忽略了一些必要的约束条件;无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x221200,则可行域为空域,不存在满足约束条件的解,当然也就不存在最优解了。§2.2图解法练习.maxZ=-xl+2x2s.t.xl<3xl-x220xl20,x220可行域30xlx2Z=-xl+2x2=0解得P点坐标为:xl=3,x2=3最优值为:maxZ=3最优解P线性规划模型一般形式目标函数: Max(Min)z=clxl+c2x2+...+cnxn约束条件:s.t.allxl+al2x2+…+alnxn<(=,2)bla21xl+a22x2+ +a2nxnW(=,2)amixl+am2x2+,,,+amnxnく（ラユ）bmxl,x2,…,xn20标准形式目标函数: Maxz=clxl+c2x2+…+cnxn约束条件:s.t.allxl+al2x2+…+alnxn=bla21xl+a22x2+...+a2nxn=b2amixl+am2x2+...+amnxn=bmxl,x2,…,xn20,bi20§2.3图解法的灵敏度分析§2.3图解法的灵敏度分析灵敏度分析:建立数学模型和求得最优解后,研究线性规划的•个或多个参数(系数)ci,aij,bj变化时,对最优解产生的影响。3.1目标函数系数ci的灵敏度分析考虑例1的情况,显然,ci的变化只影响目标函数等值线的斜率。z=0=50x1+100x2目标函数z=50xl+100x2在z=x2(x2=z斜率为〇)到z=xl+x2(x2=-xl+z斜率为ー1)之间时，原最优解xl=50,x2=250仍是最优解。一般情况:z=clxl+c2x2写成斜截式:x2=-(cl/c2)xl+z/c2目标函数等值线的斜率为:-(cl/c2),当ー1??-(cl/c2)??0(*)时,原最优解仍是最优解。z=0=50xl+100x2§2.3图解法的灵敏度分析假设产品H的利润100元不变,即c2=100,代到式(*)并整理得0 ??cl??100假设产品I的利润50元不变,即cl=50,代到式（*）并整理得50 ??C2??+??假若产品I、II的利润均改变,则可直接用式（*）来判断。§2.3图解法的灵敏度分析假设产品I、II的利润分别为60元、55元,贝リ-2??-（60/55）??-1那么,最优解为z=xl+x2和z=2xl+x2的交点:xl=100,x2=200§2.3图解法的灵敏度分析3.2约束条件中右边系数bj的灵敏度分析当约束条件中右边系数bj变化时,线性规划的可行域也变化,可能引起最优解的变化。考虑例1的情况:假设设备台时增加10个台时,即bl变化为310,这时可行域扩大,最优解为x2=250和xl+x2=310的交点xl=60,x2=250〇xl+x2=310最优解§2.3图解法的灵敏度分析变化后总利润ー变化前总利润=增加的利润（50X60+100X250）-（50X50+100X250）=500500/10=50元说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润,称为该约束条件的对偶价格。§2.3图解法的灵敏度分析假设原料A增加10千克时,即b2变化为410,这时可行域扩大,但最优解仍为x2=250和xl+x2=300的交点xl=50,x2=250〇2xl+x2=410此变化对总利润无影响,该约束条件的对偶价格为〇.解释:原最优解没有把原料A用尽,有5千克的剩余，因此增加10千克值增加了库存,而不会增加利润。z=0=50xl+100x2最优解§2.3图解法的灵敏度分析在一定范围内,当约束条件右边常数增加1个单位时（1）若约束条件的对偶价格大于0I则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于0,则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于〇,则最优目标函数值不变。作业第二章作业:P23.2.（1）、（2）、（5）；P25.6.（1）-（4）第三章线性规划问题的计算机求解广东外语外贸大学GuangdongUniversityofForeignStudies运筹学第三章线性规划问题的计算机求解§1“管理运筹学”软件的操作方法§2“管理运筹学”软件的输出信息分析第三章线性规划问题的计算机求解随书软件为“管理运筹学”2.0版（Window版）,是1.0版（DOS版）的升级版。它包括;线性规划、运输问题、整数规划（0-1整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法,共15个子模块。§1“管理运筹学”软件的操作方法1.软件使用演示:（演示例1）第一步:点击“开始”->；“程序”->；"管理运筹学2.0”,弹出主窗口.例1.目标函数:Maxz=50xl+100x2约束条件:s.t.TOC\o"1-5"\h\zxl+x2く300 (A)2xl+x2く400 (B)x2く250 (C)xl20 (D)x2N0 (E)§1“管理运筹学”软件的操作方法第二步：选择所需子模块,点击主窗口中的相应按钮。本题中选用“线性规划”方法。点击按钮弹出如下界面：例1.目标函数:Maxz=50xl+100x2约束条件：s.t.TOC\o"1-5"\h\zxl+x2く300 (A)2xl+x2W400 (B)x2く250 (C)xl20 (D)x220 (E)§1“管理运筹学”软件的操作方法第三步:点击“新建”按钮,输入数据。本题中共有2个变量,4个约束条件,目标函数取MAX。点击“确定”后,在表中输入Cj,bi和aij等值,并确定变量的正负约束。输入数值后的界面如下。例1.目标函数:Maxz=50xl+100x2约束条件:TOC\o"1-5"\h\zxl+x2W300 (A)2xl+x2く400 (B)x2く250 (C)xl20 (D)x2N0 (E)“管理运筹学”软件的操作方法第四步:点击“解决”按钮,得出计算结果。本题的运行结果界面如下。相差值表示相应的决策变量的目标系数需要改进的数量,使得决策变量为正值,当决策变量已为正数时,相差数为零。例1.目标函数：Maxz=50xl+100x2约束条件：s.t.TOC\o"1-5"\h\zxl+x2<300 (A)2xl+x2W400 (B)x2W250 (C)xl20 (D)x220 (E)松弛/剩余变量的数值表示还有多少资源没有被使用。如果为零,则表示与之相对应的资源已经全部用上。例1.目标函数：Maxz=50xl+100x2约束条件:TOC\o"1-5"\h\zxl+x2<300 (A)2xl+x2<400 (B)x2<250 (C)xlNO (D)x220 (E)对偶价格表示其对应的资源每增加一・个单位,将增加多少个单位的最优值。例1.目标函数:Maxz=50xl+100x2约束条件:s.t.TOC\o"1-5"\h\zxl+x2<300 (A)2xl+x2<400 (B)x2く250 (C)xlNO (D)x220 (E)目标函数系数范围表示最优解不变的情况下,目标函数的决策变量系数的变化范围.当前值是指当前的最优解中的系数取值.例1.目标函数：Maxz=50xl+100x2约束条件：s.t.TOC\o"1-5"\h\zxl+x2く300 (A)2xl+x2W400 (B)x2<250 (C)xl20 (D)x220 (E)常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变化时,与其对应的约束条件的对偶价格不变。当前值是指现在的取值。例1.目标函数:Maxz=50xl+100x2约束条件:s.t.TOC\o"1-5"\h\zX1+X2く300 (A)2xl+x2W400 (B)x2<250 (C)xl20 (D)x2川 (E)”管理运筹学”软件的输出信息分析第五步:分析运行结果。以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变,只有一个系数变化的基础上得出的!2.当有多个系数变化时,需要进•步讨论。百分之一百法则:对于所有变化的目标函数决策系数(约束条件右边常数值),当其所有允许增加的百分比与允许减少的百分比之和不超过100%时,最优解不变(对偶价格不变,最优解仍是原来几个线性方程的解)。§2“管理运筹学”软件的输出信息分析允许增加量=上限ー现在值cl的允许增加量为100-50=50bl的允许增加量为325-300=25允许减少量=现在值一下限c2的允许减少量为100-50=50b3的允许减少量为250-200=50允许增加的百分比=增加量/允许增加量允许减少的百分比=减少量/允许减少量例:cl变为74,c2变为78,则（74-50）/50+（100-78酒〇=92%故最优解不变。b!变为315,b3变为240,则（315-300）/25+（250-240）/50=80%故对偶价格不变（最优解仍是原来儿个线性方程的解）。§3.2“管理运筹学”软件的输出信息分析在使用百分之一百法则进行灵敏度分析时,要注意:1）当允许增加量（允许减少量）为无穷大时,则对任意增加量（减少量），其允许增加（减少）百分比均看作〇;2）百分之一百法则是充分条件，但非必要条件;也就是说超过100%并不一定变化；3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下,只有重新求解。§3.2“管理运筹学”软件的输出信息分析下面用“管理运筹学”软件来分析第二章的例2,其数学模型如下目标函数;Minf=2x1+3x2约束条件:s.t.xl+x22350xl 21252x1+x2く600xl,x220从上图可知,当购进原材料A2503原料B100t时,购进成本最低,为800万元。§3.2“管理运筹学”软件的输出信息分析在松弛/剩余变量栏中,约束条件2的值为125I它表示对原料A的最低需求，即对A的剩余变量值为125;同理可知约束条件1的剩余变量值为〇;约束条件3的松弛变量值为0.在对偶价格栏中,约束条件3的对偶价格为1万元,也就是说如果把加工时数从600小时增加到601小时,则总成本将得到改进,由800万减少到フ99万。也可知约束条件1的对偶条件为ー4万元,也就是说如果把购进原料A的下限从125t增加到126t,那么总成本将加大,由800万增加到804万。当然如果减少对原料A的下限,那么总成本将得到改进。在常数项范围・栏中,知道当约束条件1的常数项在300—475范围内变化,且其他约束条件不变时，约束条件1的对偶价格不变;当约束条件2的常数项在负无穷到250范围内变化,而其他约束条件的常数项不变时，约束条件2的对偶价格不变,仍为0:当约束条件3的常数项在475—700内变化,而其他约束条件的常数项不变时,约束条件3的对偶价格不变,仍为1。§3.2“管理运筹学”软件的输出信息分析注意:当约束条件中的常数项增加一个单位时,最优目标函数值增加的数量称之为影子价格。在求目标函数最大时,当约束条件中的常数项增加一个单位时,目标函数值增加的数量就为改进的数量，所以影子价格等于对偶价格;在求目标函数值最小时,改进的数量就是减少的数量,所以影子价格即为负的对偶价格。§3.2”管理运筹学”软件的输出信息分析注意:2.“管理运筹学”软件可以解决含有100个变量50个约束方程的线性规划问题,可以解决工商管理中大量的问题。如果想要解决更大的线性规划问题，可以使用由芝加哥大学的L.E.Schrage开发的Lindo计算机软件包的微型计算机版本Lindo/PCo第三章线性规划问题的计算机求解第四章线性规划在工商管理中的应用广东外语外贸大学GuangdongUniversityofForeignStudies运筹学第四章线性规划在工商管理中的应用§!人力资源分配的问题;§2生产计划的问题;§3套裁下料问题;§4配料问题;§5投资问题。§!人力资源分配的问题例1.某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下:设司机和乘务人员分别在各时间段ー开始时上班,并连续工作八小时,问该公交线路怎样安排司机和乘务人员,既能满足工作需要,又配备最少司机和乘务人员?解:设xi表示第i(i=l,2,…，6)班次时开始上班的司机和乘务人员数,建立数学模型:目标函数：Minz=xl+x2+x3+x4+x5+x6约束条件: s.t.xl+x6260xl+x2270x2+x3260x3+x4250x4+x5220x5+x6230xl,x2,x3,x4,x5,x620302:00—6:002022:00—2:0055018:00—22:0046014:00-18:0037010:00—14:002606:00—10:001所需人数时间班次*****************ム支角年女口下ー******************目标函数最优值为:150变量最优解相差值X1600x2100x3500x400x5300x601§2生产计划的问题例3.某公司面临ー个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品,都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作,亦可以自行生产,但产品丙必须本厂铸造才能保证质量。数据如表。问:公司为了获得最大利润,甲、乙、丙三种产品各生产多少件?甲、乙两种产品的铸造中,由本公司铸造和由外包协作各应多少件?161823产品售价（元/件）223装配成本（元/件）312机加工成本（元/件）65外协铸件成本（元/件）453自产铸件成本（元/件）100002装配エ时（小时/件）12000846机加工エ时（小时/件）80007105铸造エ时（小时/件）限制丙乙甲解:设xl,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数,x4,x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求xi的利润:利润=售价-各成本之和1823产品售价（元/件）223装配成本（元/件）3机加工成本（元/件）65外协铸件成本（元/件）453自产铸件成本（元/件）10000223装配エ吋（小时/件）12000846机加工エ时（小时/件）80007105铸造エ时（小时/件）资源限制丙乙甲产品甲全部自制的利润=23-（3+2+3）=15产品甲铸造外协,其余自制的利润二23-(5+2+3)=13产品乙全部自制的利润二18-(5+1+2)=10产品乙铸造外协,其余自制的利润二18-(6+1+2)=9产品丙的利润二16-(4+3+2)=7可得至Uxi(i=l,2,3,4,5)的利润分别为15,10,7,13,9元.161823产品售价(元/件)223装配成本(元/件)312机加工成本(元/件)65外协铸件成本(元/件)453自产铸件成本(元/件)1000022装配エ时（小时/件）12000846机加工エ时（小时7件）80007105铸造エ时（小时/件）资源限制丙乙甲通过以上分析,可建立如下的数学模型:目标函数:Max15x1+10x2+7x3+13x4+9x5约束条件:5x1+10x2+7x3W80006x1+4x2+8x3+6x4+4x5く!20003x1+2x2+2x3+3x4+2x5W10000xl,x2,x3,x4,x520161823产品售价（元/件）223装配成本（元/件）机加工成本（元/件）65外协铸件成本（元/件）453自产铸件成本（元/件）10000223装配エ时（小时/件）12000846机加工エ时（小时7件）80007105铸造工时（小时7件）资源限制丙甲思考题:当产品的售价因市场的变化而发生变化时,应怎样处理?当该公司的生产能力提高时,应如何进行分析?要求:运用计算机软件进行计算、分析后回答。§3套裁下料问题al32??amCllC12 ...ClnC21 C22 ...C2n??????CmlCm2...CmnAlA2??Am零件需要量BlB2...Bn各方式的零件个下料方式零件名称 数例.设用某原材料做零件A1,A2,…,Am的毛坯,若在一件原材料上有Bl,B2，…,Bn种不同的下料方式,每种方式可得到各种毛坯个数及每种零件需要量如下表所示。问如何安排下料方式使既能满足要求,又能使用的原材料最少。ala2??amCll C12 ... ClnC21 C22 ... C2n??????CmlCm2...CmnAlA2??Am零件需要量BlB2...Bn各方式的零件个下料方式零件名称 数分析:零件Ai按B1方式下料按B2方式下料按Bn方式下料Cil个Ci2个Cin个ai解:设用Bj种方式下料的原材料数为xj,则这ー问题的数学模型为:目标函数约束条件所用原材料数量最少Ai零件总数不能少于ai原材料不能是负数、分数套裁下料问题例5.某工厂要做100套钢架,每套用长为2.9m,2.1m,1.5m的圆钢各ー根。已知原料每根长7.4m,问:应如何下料,可使所用原料最省?解:共可设计下列8种下料方案,见下表设xl,-,x8分别为上面8种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数:Minxl+x2+…+x8约束条件: xl+2x2 +x4 +x621002x3+2x4+x5+x6+3x721003x1+x2+2x3 +3x5+x6 +4x82100xl,x2,…，x820运用软件《管理运筹学2.0》求解以上模型：思考题：如果计算得到的结果不是整数,即最优方案中所需各种型号的园钢的根数不是整数，应怎样处理?是否可进行四舍五入,四舍五入后的结果是否还是最优方案?在线性规划中,对决策变量增加整数的要求会引出什么问题?要求：查找有关资料并阅读整数规划的章节进行思考。套裁下料问题用“管理运筹学”软件计算得出最优下料方案:按方案1下料30根;按方案2下料:L0根;按方案4下料50根,即:xl=30;x2=10;x3=0;x4=50;x5=x6=x7=x8=0；只需90根原材料就可制造出100套钢架。注意:在建立此类型数学模型时,约束条件用大于等于号比用等于号要好。因为有时在套用ー些下料方案时可能会多出ー根某种规格的圆钢,但它可能是最优方案。如果用等于号,这ー方案就不是可行解了。配料问题例6.某工厂要用三种原料1,2,3混合调配出三种不同规格的产品甲、乙、丙,数据如右表。问：该厂应如何安排生产,使利润收入为最大?25不限丙35原材料1不少于25%,原材料2不超过50%乙50原材料1不少于50%,原材料2不超过25%甲单价（元/kg）规格要求产品名称3560325651001单价(元ノkg)每天最多供应量原材料名解:设xij表示第i种(甲、乙、丙)产品中原料j的含量。这样我们建立数学模型时,要考虑:对甲:xll,X12,X13；xll^0.5(xll+xl2+xl3), xl2^0.25(xll+xl2+xl3)对乙:x21,x22,x23；x2120.25(x21+x22+x23),x22W0.5(x21+x22+x23)对丙:x31,x32,x33!没限制,即无约束条件。对于原料1： xll, x21, x31； (xll+x21+x31)<100对于原料2： X12, x22, x32； (xl2+x22+x32)<100对于原料3： X13, x23, x33； (xl3+x23+x33)W60约束条件：规格要求4个;供应量限制3个。目标：利润最大,利润=收入一原料支出,故有:目标函数:Maxf=50(xll+xl2+xl3)+35(x21+x22+x23)+25(x31+x32+x33)-65(xll+x21+x31)-25(xl2+x22+x32)-35(xl3+x23+x33)=-15x11+25x12+15x13-30x21+10x22-40x31-10x33通过整理,得到以下模型：目标函数：Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33约束条件：s.t.0.5xll-0.5X12-0.5xl320（原材料1不少于50%）-0.25x11+0.75x12-0.25x13く〇（原材料2不超过25%）0.75x21-0.25x22-0.25x2320（原材料1不少于25%）-0.5X21+0.5x22-0.5x23W0（原材料2不超过50%）X11+x21+x31く100（供应量限制）X12+x22+x32く100（供应量限制）X13+x23+x33く60（供应量限制）xij2〇,i=l,2,3;j=l,2,3思考题:如果实际问题的情况,目标函数或约束条件不可用线性函数描述将会延拓出什么问题?进ー步,当实际问题的条件是不确定的或不清晰的,又将如何分析和考虑?有兴趣可查阅和了解非线性规划、模糊线性规划等内容。练习1学校准备为学生添加营养餐,每个学生每月至少需要补充60单位的碳水化合物,40单位的蛋白质和35单位的脂肪。已知两种营养品每斤:AB含量:TOC\o"1-5"\h\z碳水化合物 5 2蛋白质 3 2脂肪 5 1单价 1.5 0.7问题:买A和B分别多少斤既满足学生营养需要又省钱?目标函数:mins=x+y约束条件: x+y260x+ y>40x+ y235变量:非负条件: x20,y20§5投资问题例8.某部门现有资金200万元,今后五年内考虑给以下的项目投资。已知:项目A：从第一年到第五年每年年初都可投资,当年末能收回本利110%;项目B：从第一年到第四年每年年初都可投资,次年末能收回本利125%,但规定每年最大投资额不能超过30万元;项目C:需在第三年年初投资,第五年末能收回本利140%,但规定最大投资额不能超过80万元；项目D:需在第二年年初投资，第五年末能收回本利155%,但规定最大投资额不能超过100万元。据测定每万元每次投资的风险指数如下表,问:a)应如何确定这些项目的每年投资额,使得第五年年末拥有资金的本利金额为最大?b)应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小?解;1)确定决策变量:连续投资问题设xij(i=1〜5,j=1〜4)表示第i年初投资于A(j=l)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量:AX11x21x31 x41x51BX12x22x32 x42Cx33Dx242)约束条件:第•年:A当年末可收回投资,故第一年年初应把全部资金投出去，于是xll+X12=200；第二年:B次年末オ可收回投资,故第二年年初有资金1.1x11,于是x21+x22+x24=1.1x11；第三年：年初有资金!.1x21+1.25x12,于是x31+x32+x33=1.1x21+1.25x12第四年:年初有资金!.1x31+1.25x22,于是x41+x42=1.1x31+1.25x22第五年:年初有资金!.1x41+1.25x32»于是X51=1.1x41+1.25x32B、C、D的投资限制:xi2W30(i=l、2、3、4),x33W80,x24く1003)目标函数及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.X11+X12=200x21+x22+x24=l.lxll；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi2く30(i=l、2、3,4),x33く80,x24W100,xij20(i=l,2,3,4,5；j=1,2,3,4,)b)所设变量与问题a相同,目标函数为风险最小,有:Minf=xll+x21+x31+x41+x51+3(xl2+x22+x32+x42)+4x33+5.5x24b)在问题a的约束条件中加上“第五年末拥有资金本利在330万元”的条件,于是模型如下:Minf=xll+x21+x31+x41+x51+3(xl2+x22+x32+x42)+4x33+5.5x24s.t.xll+xl2=200x21+x22+x24=l.lxll；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；xi2く30(i=l,2,3,4),x33く80,x24く100x51+1.25x42+1.4x33+1.55x242330xijN0(i=1,2,3,4,5；j=1,2,3,4)本章结束第四章线性规划在工商管理中的应用广东外语外贸大学GuangdongUniversityofForeignStudies统筹安排成本最低第五章运输问题1运输模型2运输问题的计算机求解3运输问题的应用§4・运输问题的表上作业法例1、某公司从两个产地Al、A2将物品运往三个销地Bl、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?运输模型解:产销平衡问题:总产量=总销量设xij为从产地Ai运往销地Bj的运输量,得到下列运输量表:Minf=6x11+4x12+6x13+6x21+5x22+5x23产地Al运出的运输量等于其产量:xll+xl2+xl3=200产地A2运出的运输量等于其产量:x21+x22+x23=300运到销地Bl的运输量等于其需求量：xll+x21=150运到销地B2的运输量等于其需求量：xl2+x22=150运到销地B3的运输量等于其需求量：X13+X23=200运输量非负: xij20(i=l,2；j=l,2,3)§1运输模型整理得:s.t.xll+X12+X13=200x21+x22+x23=300xll+x21=150X12+x22=150X13+x23=200xij20（i=l、2；j=l、2、3）§1运输模型一般运输模型:产销平衡Al>A2、…、Am表示某物资的m个产地;Bl>B2、…、Bn表示某物质的n个销地;ai表示产地Ai的产量;bj表示销地Bj的销量;cij表示把物资从产地Ai运往销地Bj的单位运价。设xij为从产地Ai运往销地Bj的运输量,得到下列一般运输量问题的模型:运输问题及其数学模型bnb2bl销量BnB2Bl销地产地AmA2Alama2al产量产销平衡运价§1运输模型bnb2bl销量BnB2Bl销地产地AmA2Alama2al产量cmncm2cmlc2nc22c21clncl2ell求使总的运输费用最小的调运方案?ブン:销平衡表运输问题及其数学模型§1运输模型产地Ai发量之和等于其产量销地Bj收量之和等于其销量运量不能为负数运输问题线性规划模型总费用最小§1运输模型运输问题网络图2321341s2=27s3=19d3=12d4=13sl=14供应量供应地运价需求量需求地6753842759106运输模型运输问题线性规划模型供应地约束需求地约束运输模型§2运输问题的计算机求解将上述问题用以下运价表:134121322销量1910953272482145761产量321销地产地§2 运输问题的计算机求解运行管理运筹学计算机软件:点击运输问题模块§2 运输问题的计算机求解点击新建输入3输入4选择Min点击确定§2 运输问题的计算机求解136734121322销量191095327248214产量321销地产地§2 运输问题的计算机求解点击解决§2 运输问题的计算机求解思考题:运输问题的特点是什么?既然运输问题是线性规划的ー种特殊情况,为什么不用线性规划的方法求解?要求:对以上例子分别应用计算机软件的线性规划模块和运输问题的模块进行计算、分析后回答。§2 运输问题的计算机求解例2、某公司从两个产地Al、A2将物品运往三个销地Bl、B2、B3I各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?解:增加一个虚设的销地运输费用为0.§2运输问题的计算机求解例3、某公司从两个产地Al、A2将物品运往三个销地Bl、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?解:增加一个虚设的产地运输费用为0思考题在例3中,即某公司从两个产地Al、A2将物品运往三个销地Bl、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,如果增加条件:B3的需求不能满足则需以高价（每单位10元）在本地购买,问:应如何调运可使总运输费用最小?500650200200250销量300556A2200646A1产量B3B2B1思考题在例3中,即某公司从两个产地Al、A2将物品运往三个销地Bl、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,如果增加条件:B3的需求不能满足则需以高价（每单位10元）在本地购买,问:应如何调运可使总运输费用最小?650200200250销量15010MMA3300556A2200646Al产量B3B2Bl§2运输问题的计算机求解§2运输问题的计算机求解§3 运输问题的应用ー、产销不平衡的运输问题例4、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨,由河北临城、山西盂县两处煤矿负责供应,价格、质量相同。供应能カ分别为1500、4000吨,运价为:由于需大于供,经院研究决定一区供应量可减少0-300吨,二区必须满足需求量,三区供应量不少于1500吨,试求总费用为最低的调运方案。解:根据题意,作出产销平衡与运价表:这里M代表一个很大的正数，其作用是强迫相应的x31、x33、X34取值为〇〇§3 运输问题的应用应用运筹学软件计算得：§3 运输问题的应用ー、产销不平衡的运输问题例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同,有关数据如下表：试求总费用为最低的化肥调拨方案。解:根据题意,作出产销平衡与运价表:最低要求必须满足,因此把相应的虚设产地运费取为M,而最高要求与最低要求的差允许按需要安排,因此把相应的虚设产地运费取为0〇对应4"的销量50是考虑问题本身适当取的数据,根据产销平衡要求确定D的产量为50.210210501030702030销量500M0M0MD5023201919C60151519131414B50171722131616A产量4”4'321"1'思考题考虑・运输问题,有关产品的单位运价（元/千克）如下表所示,假设Al、A2处产品要求全部运走,A3处产品就地储存的费用为每千克16元,试写出该问题的产销平衡表。55 60需求量（千克）403065TOC\o"1-5"\h\z35 2315 3428 33A1A2A3供应量（千克）Bl B2销地产地§3 运输问题的应用思考题该问题的产销平衡表为:55 60 20需求量（千克）403065TOC\o"1-5"\h\z35 23 M15 34 M28 33 16A3供应量（千克）Bl B2 B3销地产地§3运输问题的应用§3运输问题的应用二、生产与储存问题例6、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同ー规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货,每台每积压ー个季度需储存、维护等费用0.15万元。试求在完成合同的情况下,使该厂全年生产总费用为最小的决策方案。11.310411.030311.135210.8251单位成本（万元）生产能力（台）季度解:把第i季度生产的柴油机数目看作第i个生产厂的产量;把第j季度交货的柴油机数目看作第j个销售点的销量;成本加储存、维护等费用看作运费。可构造下列产销平衡问题:1001003020251510销量10011.30MMM430011.1511.00MM335011.4011.2511.10011.2511.1010.9510.801产量D4321季度季度设xij为第i季度生产的第j季度交货的柴油机数目,则交货:1001003020251510销量10011.30430011.1511.00MM335011.4011.2511.10M225011.2511.1010.9510.801产量D4季度X11+X12+X13+X14く25x22+x23+x24く35X33+X34く30X44W10TOC\o"1-5"\h\zxll =10X12+X22 =15xl3+x23+x33 =25xl4+x24+x34+x44=20生产:目标函数:Minf=10.8xll+10.95xl2+ll.lxl3+11.25xl4++11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44§3 运输问题的应用三、转运问题:在原运输问题上增加若干转运站。运输方式有:产地??转运站、转运站??销地、产地??产地、产地??销地、销地??转运站、销地??产地等。例8、腾飞电子仪器公司在大连和广州有两个分厂生产同一・种仪器,大连分厂每月生产400台,广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近,公司同意大连分厂向青岛直接供货,运输费用如图,单位是百元。问应该如何调运仪器,可使总运输费用最低?图中1ー广州、2一大连、3ー上海、4ー天津、5-南京、6ー济南、7ー南昌、8一青岛。应该如何调运仪器,可使总运输费用最低?图中1-广州、2一大连、3ー上海、4-天津、5ー南京、6ー济南、フー南昌、8一青岛。大连上海天津销量产量青岛上海天津南京济南南昌青岛运价表260040010001000100010002001503503003MMMM31MMM2636M0广州济南大连上海天津南京南昌青岛6004001000100023MMMM31MMM40M2636M04465广州大连上海天津1000 1000200 1503503001000 1000200 150350300销量产量上海天津南京济南南昌青岛运价表3运输问题的应用例9、某公司有Al、A2、A3三个分厂生产某种物资,分别供应Bl、B2、B3、B4四个地区的销售公司销售。假设质量相同,有关数据如下表,试求总费用为最少的调运方案。运输问题的应用假设:.每个分厂的物资不一定直接发运到销地,可以从其中几个产地集中一起运;.运往各销地的物资可以先运给其中几个销地,再转运给其他销地;.除产销地之外,还有儿个中转站,在产地之间、销地之间或在产地与销地之间转运。运价如下表:31264765810B42241023B31218584911B2244271Bl21212323T4428121324T3725T26482231132T151047323A38231A2103113341231AlB4B3B2BlT4T3T2T1A3A2Al解:把此转运问题转化为・般运输问题:.把所有产地、销地、转运站都同时看作产地和销地;.运输表中不可能方案的运费取作M,自身对自身的运费为〇;.Ai产量为20+原产量,销量为20;Ti:产量、销量均为20；Bi:产量为20,销量为20+原销量,其中20为各点可能变化的最大流量;.对于最优方案,其中xii为自身对自身的运量,实际上不进行运作。扩大的运输问题产销平衡与运价表:2402625262320202020202020销量2003126476B420302422241023B3201201M8584911B22001142713Bl2062M10212323T4204232M4T32072541101M51T2206482232T1295104732M10M3A32482912M53M01A231133412310Al产量B4B3B2BlT4T3T2T1A3A2Al谢谢大家返回首页作业第一次作业:P152、1第二次作业:P153、3第三次作业:P153、2第六章整数规划广东外语外贸大学GuangdongUniversityofForeignStudies运筹学第六章整数规划§1整数规划的图解法§2整数规划的计算机求解§3整数规划的应用*§4整数规划的分枝定界法整数规划是ー类要求变量取整数值的数学规划,可分成线性和非线性两类。整数线性规划（IntegerLinearProgramming,简记为ILP）问题研究的是要求变量取整数值时,在ー组线性约束条件下ー个线性函数最优问题,是应用非常广泛的运筹学的ー个重要分支。应用实例:•项目投资问题 ・工作分配问题•选址问题 •背包问题第六章整数规划根据变量的取值情况,整数线性规划又可以分为纯整数规划（所有变量取整数）,混合整数规划（部分变量取整数），0-1整数规划（变量只取。或1）等。求整数解的线性规划问题,不是用四舍五入法或去尾法对线性规划的非整数解加以处理就能解决的。整数线性规划ー些基本算法的设计是以相应线性规划的最优解为出发点而发展出来的。整数规划是数学规划中一个较弱的分支,目前有成熟的方法解线性整数规划问题,而非线性整数规划问题,还没有好的办法。第六章整数规划§1整数规划的图解法例1. 某公司拟用集装箱托运甲、乙两种货物,这两种货物每件的体积、

重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件,问两种货物各托运多少件,可使获得利润最大货物每件体积（立方米）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140§1整数规划的图解法解:设xl、x2分别为甲、乙两种货物托运的件数,建立模型。目标函数:Maxz目标函数:Maxz=2x1+3x2约束条件:s.t.195xl+273x2W13654x1+ 40x2W140xl《4xl,x220,为整数。如果去掉最后ー个约束,就是ー个线性规划问题.货物每件体积（立方米）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140§1整数规划的图解法利用图解法,得到线性规划的最优解为xl=2.44,x2=3.26,目标函数值为14.66〇由图表可看出,整数规划的最优解为xl=4,x2=2,目标函数值为14。195x1+273x2=13654xl+40x2=1404231123x2xl§1整数规划的图解法对于整数规划,易知有以下性质:性质1:任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值;任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。§2分支定界法以及计算机求解分枝定界法步骤:求解与IP相应的LP问题,可能会出现下面几种情况:若所得的最优解的各变量恰好取整数,则这个解也是原整数规划的最优解,计