上海交大运筹学第一讲

《上海交大运筹学第一讲》由会员分享，可在线阅读，更多相关《上海交大运筹学第一讲（46页珍藏版）》请在金锄头文库上搜索。

1、运筹学课程运筹学课程上海交通大学管理学院上海交通大学管理学院于长锐于长锐电话：28516057E-mail：Operation ResearchOperation Research第一讲第一讲第一讲第一讲成绩考核方法成绩考核方法qq上课考勤：上课考勤：上课考勤：上课考勤：10%10%qq作业成绩：作业成绩：作业成绩：作业成绩：20%20%qq期末考试：期末考试：期末考试：期末考试：70%70%Operation ResearchOperation Research第一讲第一讲第一讲第一讲第一章第一章 绪论绪论Operation ResearchOperation Research第一讲第一讲第

2、一讲第一讲运筹学的由来与发展运筹学的由来与发展qq名称名称名称名称q运筹学一词的英文原名为Operations Research（缩写为O.R）q中文以前译成“运作研究”或“作业研究”或“管理数学”或“运用学”q1957年我国从“运筹帷幄之中，决胜千里之外”这句古语中摘取“运筹”二字，将O.R正是译为“运筹学”。qq运筹学的产生与发展运筹学的产生与发展运筹学的产生与发展运筹学的产生与发展Operation ResearchOperation Research第一讲第一讲第一讲第一讲q朴素的运筹学思想q田忌赛马（对策论）q丁渭修宫（网络规划）q产生于第二次世界大战时期q罗伊（A.P.Rowe）的

3、雷达防空作战系统q陆、海、空军的作战策略q军需物资的运输q发展于五、六十年代q电子计算机技术的迅速发展，解决线形规划问题的单纯型法产生；q1957年在英国牛津大学召开了第一次国际运筹学会议。 q1959年 成立国际运筹学会 (International Federation of Operations Research Societies, IFORS)q成熟于七、八十年代q运筹学用来研究一些大的复杂的系统，如城市交通、环境污染、国民经济计划等实际社会问题 q运筹学进一步细分为各个分支，专业学术团体的迅速增多，更多期刊的创办，运筹学书籍 的大量出版以及更多学校将运筹学课程纳入教学计划之中。 O

4、peration ResearchOperation Research第一讲第一讲第一讲第一讲运筹学定义运筹学定义qq各种定义各种定义各种定义各种定义q据大英百科全书释义，“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具”。q我国辞海(1979年版)中有关运筹学条目的释义为，运筹学“主要研究经济活动与 军事活动中能用数量来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到较经济较有效地使用人力物力。”q中国企业管理百科全书(1984年版)中的释义为，运筹学“应用分析、试验、量化的方法，对 经

5、济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以 实现最有效的管理。” qq归纳归纳归纳归纳q学科范围：系统科学q研究方法：定量分析、数学运算q研究目标：对系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理决策 Operation ResearchOperation Research第一讲第一讲第一讲第一讲运筹学的特点（运筹学的特点（1）qq1 1运筹学研究和解决问题的基础是最优化技术，并强调运筹学研究和解决问题的基础是最优化技术，并强调运筹学研究和解决问题的基础是最优化技术，并强调运筹学研究和解决问题的基础是最优化技术，并强

6、调系统整体最优运筹学针对研究的系统整体最优运筹学针对研究的系统整体最优运筹学针对研究的系统整体最优运筹学针对研究的 实际问题，从系统的观实际问题，从系统的观实际问题，从系统的观实际问题，从系统的观点出发，以整体点出发，以整体点出发，以整体点出发，以整体最优最优最优最优为目标，研究各组成部分的功能及其为目标，研究各组成部分的功能及其为目标，研究各组成部分的功能及其为目标，研究各组成部分的功能及其相互问的影响相互问的影响相互问的影响相互问的影响 关系，解决各组成部门之间的利害冲突，求关系，解决各组成部门之间的利害冲突，求关系，解决各组成部门之间的利害冲突，求关系，解决各组成部门之间的利害冲突，求出

7、使所研究问题达到最佳效果的解，并寻找一个最出使所研究问题达到最佳效果的解，并寻找一个最出使所研究问题达到最佳效果的解，并寻找一个最出使所研究问题达到最佳效果的解，并寻找一个最 好的行好的行好的行好的行动方案付诸实施动方案付诸实施动方案付诸实施动方案付诸实施qq2 2运筹学研究和解决问题的优势是应用各学科交叉的方运筹学研究和解决问题的优势是应用各学科交叉的方运筹学研究和解决问题的优势是应用各学科交叉的方运筹学研究和解决问题的优势是应用各学科交叉的方法，具有综合性运筹学从一开始法，具有综合性运筹学从一开始法，具有综合性运筹学从一开始法，具有综合性运筹学从一开始 就是由不同学科专长、就是由不同学科专

8、长、就是由不同学科专长、就是由不同学科专长、多方面专家经过共同协作集体努力而获得成果的现在，多方面专家经过共同协作集体努力而获得成果的现在，多方面专家经过共同协作集体努力而获得成果的现在，多方面专家经过共同协作集体努力而获得成果的现在，由于研究对象由于研究对象由于研究对象由于研究对象 的复杂性和多因索性，决定了运筹学内容的的复杂性和多因索性，决定了运筹学内容的的复杂性和多因索性，决定了运筹学内容的的复杂性和多因索性，决定了运筹学内容的跨学科性、交叉渗透性和综合性跨学科性、交叉渗透性和综合性跨学科性、交叉渗透性和综合性跨学科性、交叉渗透性和综合性 Operation ResearchOperat

9、ion Research第一讲第一讲第一讲第一讲运筹学的特点（运筹学的特点（2）qq3 3运筹学研究和解决问题的方法具有显著的系统分析特运筹学研究和解决问题的方法具有显著的系统分析特运筹学研究和解决问题的方法具有显著的系统分析特运筹学研究和解决问题的方法具有显著的系统分析特征，其各种方法的运用，几乎都需要建立数学模型和利用征，其各种方法的运用，几乎都需要建立数学模型和利用征，其各种方法的运用，几乎都需要建立数学模型和利用征，其各种方法的运用，几乎都需要建立数学模型和利用计算机进行求解可以说现在及今后，没有计算机的发展计算机进行求解可以说现在及今后，没有计算机的发展计算机进行求解可以说现在及今后

10、，没有计算机的发展计算机进行求解可以说现在及今后，没有计算机的发展就没有运筹学的发展就没有运筹学的发展就没有运筹学的发展就没有运筹学的发展qq4 4运筹学具有强烈的实践性和应用的广泛性运筹学的运筹学具有强烈的实践性和应用的广泛性运筹学的运筹学具有强烈的实践性和应用的广泛性运筹学的运筹学具有强烈的实践性和应用的广泛性运筹学的目的在于解决实际问题，它所使用目的在于解决实际问题，它所使用目的在于解决实际问题，它所使用目的在于解决实际问题，它所使用的全部假设和数学模型的全部假设和数学模型的全部假设和数学模型的全部假设和数学模型无非都是解决实际问题的工具，有助于各种经济活动和管无非都是解决实际问题的工具

11、，有助于各种经济活动和管无非都是解决实际问题的工具，有助于各种经济活动和管无非都是解决实际问题的工具，有助于各种经济活动和管理问题的解决，最终能向决策者提供建设性方案并能收到理问题的解决，最终能向决策者提供建设性方案并能收到理问题的解决，最终能向决策者提供建设性方案并能收到理问题的解决，最终能向决策者提供建设性方案并能收到实效，因此，它的应用并不受行业和部门的限制，已被广实效，因此，它的应用并不受行业和部门的限制，已被广实效，因此，它的应用并不受行业和部门的限制，已被广实效，因此，它的应用并不受行业和部门的限制，已被广泛应用于工商企业、军事部门、服务行业和经济管理部门泛应用于工商企业、军事部门

12、、服务行业和经济管理部门泛应用于工商企业、军事部门、服务行业和经济管理部门泛应用于工商企业、军事部门、服务行业和经济管理部门中中中中 Operation ResearchOperation Research第一讲第一讲第一讲第一讲模型（模型（1）qq模型定义模型定义模型定义模型定义q模型是客观世界或 现实系统的代表或抽象的描述，用以描述客观事物的某些特征和内在联系，从而表示或解释某 一系统的过程，是帮助人们认识、分析和解决实际问题的有力工具qq模型的功能模型的功能模型的功能模型的功能q1模型是现实问题某一主要方面的描述或抽象，比现实本身简单和概括使入易于认识、 理解和操作； q2模型是由与研究

13、实际问题有关的主要因素所构成，并表明这些因素的相互关系，从而能够更简明地揭示出问题的本质；q 3通过模型可以进行试验，用以分析和预测所研究事物或系统的特征及性质尤其在研究 工业系统、军事系统、政府或社会系统的最优管理或远行的问题时十分必要因为这样可以避 免由于真实对象的干扰而导致不测的风险 q4利用模型可以在相对短的时间内获得所研究问题的结果特别对一个复杂问题的研究， 利用模型，使研究者不必真的实现计划即可改变其参数，从而不必等待一段较长的时间就可以得到问题的答案Operation ResearchOperation Research第一讲第一讲第一讲第一讲qq模型的基本形式模型的基本形式模型

14、的基本形式模型的基本形式q形象模型、模拟模型及符号或数学模型qq数学模型数学模型数学模型数学模型p数学模型是将现实系统或问题中有关参数和因素及其相互关系归纳成一个或一组 数学表达式，并可以用一定的分析和计算方法进行求解，以实现反映现实系统变化规律的主要目标数学模型的一般形式模型（模型（2）Operation ResearchOperation Research第一讲第一讲第一讲第一讲运筹学模型（运筹学模型（1）qq建立运筹学模型的基本要求建立运筹学模型的基本要求建立运筹学模型的基本要求建立运筹学模型的基本要求q能完整地描述所研究的系统，以便能代替现实供我们分析研究；q模型尽量简单。qq运筹学方

15、法分析解决问题的步骤运筹学方法分析解决问题的步骤运筹学方法分析解决问题的步骤运筹学方法分析解决问题的步骤q1提出并形成问题要解问题，首先需要提出问题，明确问题的实质及关键所在，这就要求 对系统进行深入的调查和分析，确定问题的界限，选准问题的目标 q2建立模型运筹学模型是一个能有效地达到一定目标(或多个目标)行动的系统，因此， 目标一经认定，就要用数学语言描述问题，建立目标函数，分析问题所处的环境确定约束条 件，探求与问题有关的决策变量等，并选用合适的方法，建立运筹学模型 q3分析并求解模型根据所建模型的性质及其数学待征，选择适当的求解方法，并求出模型的最优解或满意解 Operation Res

16、earchOperation Research第一讲第一讲第一讲第一讲q4检验并评价模型模型分析和计算得到结果以后，尚需按照它能否解决实际问题，主要 考虑达成目标的情况，选择合适的标准，并通过一定的方法，例如灵敏度分析法、参数规划法、 相关分析法等对模型结构和一些基本参数进行评价，以检验它们是否准确无误，否则就要考 虑改换或修正模型，增减计算过程中所用到的资料或数据 q5应用或实施模型的解经过反复检查以后，最终应用或实施模型的解，就是供给决策者一套有科学依据的并为解决问题所需要的数据、信息或方案以辅助决策者在处理问题时作出正确的决策和行动方案 从运筹学模型中求出来的解不是问题的最终答案，而仅仅

17、是为实从运筹学模型中求出来的解不是问题的最终答案，而仅仅是为实从运筹学模型中求出来的解不是问题的最终答案，而仅仅是为实从运筹学模型中求出来的解不是问题的最终答案，而仅仅是为实际问题的科学处理提供了有用的、可以做为决策基础的信息！际问题的科学处理提供了有用的、可以做为决策基础的信息！际问题的科学处理提供了有用的、可以做为决策基础的信息！际问题的科学处理提供了有用的、可以做为决策基础的信息！运筹学模型（运筹学模型（2）Operation ResearchOperation Research第一讲第一讲第一讲第一讲运筹学研究的主要内容（运筹学研究的主要内容（1）qq规划理论（规划理论（规划理论（规划

18、理论（Programming TheoryProgramming Theory）q它主要研究如何有效利用有限资源，合理分配生产任务，选择最佳生产布置以及合理安排物资调运方案，以求取得最好的经济效果等问题。q主要方法：线性规划、非线性规划和动态规划等 qq网络分析理论（网络分析理论（网络分析理论（网络分析理论（Net-work Analysis Theory)Net-work Analysis Theory)q通过把研究的问题构造成网络模型， 然后再加以数学或数量的分 析，以获得最优的决策效果。它已经成功地解决了工程项目的计 划安排问题和物资运输中的最短路程问题和最大流量问题。q主要方法：关键路

19、线法、计划评审技术（统筹方法）qq库存理论（库存理论（库存理论（库存理论（Inventory TheoryInventory Theory）q研究在一定的采购、运输条件下，使材料、物资保持合适的库存水平，在保证生产或经销活动能连续进行的前提下，使材料、物资的库存总费用达到最小。q主要方法：存储数学模型Operation ResearchOperation Research第一讲第一讲第一讲第一讲运筹学研究的主要内容（运筹学研究的主要内容（2）qq排队理论（排队理论（排队理论（排队理论（Queuing TheoryQueuing Theory）q用数学方法研究如何确定最适当的服务人员和服务设施数

20、目，达到服务质量最好，服务费用最低的目的。q主要方法：确定服务模型、随机服务模型 qq决策理论（决策理论（决策理论（决策理论（Decision-making TheoryDecision-making Theory）q通过对各种客观条件可能出现的概率进行调安分析和对各种方案的经济效益进行计算，研究方案的合理选择问题，使企业能因此而获得最优的经济效果。q主要方法：风险分析、效用分析、灵敏度分析等qq对策理论（对策理论（对策理论（对策理论（Game TheoryGame Theory）q研究处于竞争状态下， 企业双方(或多方)可能采取的策略行动，每一策略行动给各方可能带来的经济损益等问题，通过数学

21、分析，确定应取哪一对策，才能使企业获益最大(或损失最小)。q 主要方法：矩阵对策模型、博弈论模型 Operation ResearchOperation Research第一讲第一讲第一讲第一讲第二章第二章 线性规划及线性规划及单纯形法单纯形法Operation ResearchOperation Research第一讲第一讲第一讲第一讲线性规划的发展线性规划的发展qq提出阶段提出阶段提出阶段提出阶段q前苏联数学家康托洛维奇在1939年著的生产组织与计划中的数学方法一 书中，首次提出了线性规划问题q美国学者希奇柯克(F.L Hitchock,1941)和柯普曼 (T. C Koopman，19

22、47) 独立提出了运输问题这类特殊的线性规划问题qq发展阶段发展阶段发展阶段发展阶段q在1947 年，美国学者丹捷倍(G.B Dantzig)提出了线性规划问题的一般解法单纯形法，为线性规 划的发展奠定了基础。qq成熟应用阶段成熟应用阶段成熟应用阶段成熟应用阶段q40多年来，随着电子计算机的发展，线性规划已广泛应用于工业、农业、 商业、交通运输、经济管理和国防等各个领域成为现代化管理的有力工具之一。 Operation ResearchOperation Research第一讲第一讲第一讲第一讲线性规划研究的几类问题线性规划研究的几类问题qq两类问题两类问题两类问题两类问题q已有一定数量的人力

23、、物质资源，研究怎样充分和合理地使用这些资源，才能使完 成酌任务量最大； (max Z)q已确定了一项任务，研究怎样合理安 排，才能使完成任务所耗费的资源量最小。(min Z) q这两类问题 是相互联系的，或者说是一个问题的两种不同提法，总的是要求 耗费最小量的资源， 完成尽可能多的任务， 获得最好的经济效 果。 qq实际应用中的分类实际应用中的分类实际应用中的分类实际应用中的分类q生产组织与计划问题、资源合理利用问题、运输问题、合理下料问题、配料问题、布局问题Operation ResearchOperation Research第一讲第一讲第一讲第一讲生产组织与计划问题（生产组织与计划问题

24、（1）qq问题描述问题描述问题描述问题描述q一个工厂或车间有各种不同类 型的设备各若干台，各种不同设备生产各种零件的效率不同，在 一个生产周期，应如何安排各设备的生产使得成全的产品总量最大。qq实例实例实例实例某车间用三种不同型号的某车间用三种不同型号的某车间用三种不同型号的某车间用三种不同型号的机床机床机床机床A1A1，A 2A 2，A3A3加工加工加工加工B1B1，B2B2两种零件。机床台数、两种零件。机床台数、两种零件。机床台数、两种零件。机床台数、生产效率生产效率生产效率生产效率( (每台机床每个工每台机床每个工每台机床每个工每台机床每个工作日完成零件的个数作日完成零件的个数作日完成零

25、件的个数作日完成零件的个数) )如表如表如表如表所示问如何合理安排机所示问如何合理安排机所示问如何合理安排机所示问如何合理安排机床的加工任务，才能使生床的加工任务，才能使生床的加工任务，才能使生床的加工任务，才能使生产的零件总数最多产的零件总数最多产的零件总数最多产的零件总数最多? ?Operation ResearchOperation Research第一讲第一讲第一讲第一讲q建立模型生产组织与计划问题（生产组织与计划问题（2）Operation ResearchOperation Research第一讲第一讲第一讲第一讲qq生产组织与规划问题的一般形式生产组织与规划问题的一般形式生产组织

26、与规划问题的一般形式生产组织与规划问题的一般形式q某工厂用机床A1,A2,Am加工B1,B2,Bn种零件，在一个生产周期内各机床可能的加工机时、工程必须完成各种零件的最小数量、各机床加工每个零件的时间（机时/个）和加工每个零件的成本（元/个）见下表。问如何安排各机床的生产任务，才能完成加工任务，又使成本最低？生产组织与计划问题（生产组织与计划问题（3）表1表2Operation ResearchOperation Research第一讲第一讲第一讲第一讲q建立模型生产组织与计划问题（生产组织与计划问题（4）Operation ResearchOperation Research第一讲第一讲第一

27、讲第一讲资源的合理利用问题（资源的合理利用问题（1）qq资源合理利用的一般形式资源合理利用的一般形式资源合理利用的一般形式资源合理利用的一般形式q某厂计划在下一个生产周期内生产B1,B2,Bn。种产品，要消耗Al,A2,Am种资源。已知每件产品所消耗的资源数、每种资源的数量限制以及每 件产品可获得的利润如下表所示。问如何安排生 产计划，才能充分利用现有资源，使获得的总利润最 大？Operation ResearchOperation Research第一讲第一讲第一讲第一讲qq建立模型建立模型建立模型建立模型资源的合理利用问题（资源的合理利用问题（2）Operation ResearchOpe

28、ration Research第一讲第一讲第一讲第一讲合理下料问题（合理下料问题（1）qq问题描述问题描述问题描述问题描述q在生产中经常会遇到这样的问题，把长度一定 的线材或板材截成尺寸不同曲零件毛坯，或在面积一定的 板材上切割形状、尺寸不同的零件毛坯在一般情况 下很难使材料完全利用，总会多出一些料头，如果恰当的搭配下料，则可以减少料头、使原材料得到充 分利用，这就是合理下料问题问题所要 解决的就是怎样组成和选择下料方案，在满足各种零件毛坯数量要求的前提下使总的原材料消耗最少 qq实例实例实例实例q现有一批某种型号的圆钢长8m。需要裁取长2.5m的毛坯100根、长1.3m的毛坯 200根，问应

29、该怎样选择下料方式，才能既满足需要，又使总的用料最少? Operation ResearchOperation Research第一讲第一讲第一讲第一讲q建立模型q下料方案分析q数学模型合理下料问题（合理下料问题（2）Operation ResearchOperation Research第一讲第一讲第一讲第一讲qq合理下料问题的一般形式合理下料问题的一般形式合理下料问题的一般形式合理下料问题的一般形式q设用某种原材料截取零件A1,A2,Am的毛 坯，根据以往的经验，在一件原材料上可以有B1,B2,Bn种不同的下料方式，每种下料方式可截得各种毛坯的个数以及每种毛坯的需要量如下表所示问应如何下料

30、，才能既满足需要又使原 材料消耗最少? 合理下料问题（合理下料问题（3）Operation ResearchOperation Research第一讲第一讲第一讲第一讲q建立模型合理下料问题（合理下料问题（4）Operation ResearchOperation Research第一讲第一讲第一讲第一讲合理配料问题（合理配料问题（1）qq合理配料问题的一般形式合理配料问题的一般形式合理配料问题的一般形式合理配料问题的一般形式q某饲养场用n种饲料B1,B2,Bn，配制成含有m种营养成分A1,A2,Am的混合饲料，各种饲料所合营养成分的数量、混合饲料对各种成 分的最低需要量以及各种饲料的单价如下

31、表所 示。问应如何配料，才能既满足需求，又使混合饲料总成本最低? Operation ResearchOperation Research第一讲第一讲第一讲第一讲q建立模型合理配料问题（合理配料问题（2）Operation ResearchOperation Research第一讲第一讲第一讲第一讲运输问题（运输问题（1）qq问题描述问题描述问题描述问题描述q在某一地区内，有某种产品的产地与销地各若干，把这种产品从各产地调运到各销地，调运方案可以很多， 应如何组织调运，才能使总的运费或运力(即总的运输吨公里 数)最少。qq实例实例实例实例q某公司下属两个工厂，生产同一种产品。产品均可运往三个中

32、心仓库去销售。已知每个工厂的产量，各仓库的销量及各工厂到每个仓库的运输单价如下表所示。问如何组织调运可使生产与运输的总费用最少? Operation ResearchOperation Research第一讲第一讲第一讲第一讲q建立模型运输问题（运输问题（2）Operation ResearchOperation Research第一讲第一讲第一讲第一讲qq运输问题的一般形式运输问题的一般形式运输问题的一般形式运输问题的一般形式q设某种物资共有m个产地A1,A2,Am，其产量分别为a1,a2,am，另有n个销地B1,B2,Bn，其销量分别为b1,b2,bn，已知由产 地Ai (i=1,2,m)

33、运往销地Bj的(j=1,2,n)的单位运价为cij，其数据如下表所示，问应如何调运，才能使总运费最省? 运输问题（运输问题（3）Operation ResearchOperation Research第一讲第一讲第一讲第一讲q建立模型运输问题（运输问题（4）Operation ResearchOperation Research第一讲第一讲第一讲第一讲运输问题（运输问题（5）Operation ResearchOperation Research第一讲第一讲第一讲第一讲布局问题（布局问题（1）qq布局问题的一般形式布局问题的一般形式布局问题的一般形式布局问题的一般形式q某农场要在n块土地B1,

34、B2,Bn上种植m种作物A1,A2,Am ，各块土地的面积、各种作物计划播种的面积以及各种作物在各块土地上的单产如下表所示。问应如何合理安排种植计划，才能使总产量最大？(假设计划播种总面积等于土地总面积，即 )Operation ResearchOperation Research第一讲第一讲第一讲第一讲q建立模型布局问题（布局问题（2）Operation ResearchOperation Research第一讲第一讲第一讲第一讲线性规划模型的建立（线性规划模型的建立（1）qq线性规划模型的特点线性规划模型的特点线性规划模型的特点线性规划模型的特点q都有一组决策变量(x1,x2,xn)，决策

35、变量的一组取值表示一个决策方案，且决策变量的取值一般都是非负的。q都有一组约束条件，约束决策变量的取值。q都有一个要达到的目标，用目标函数来表示。q目标函数和约束条件都是线性等式或线性不等式。qq线性规划问题求解的一般步骤线性规划问题求解的一般步骤线性规划问题求解的一般步骤线性规划问题求解的一般步骤q研究和明确问题的要求和条件；q设定决策变量； q选定衡量目标函数的数量指标(利润、费用、成本、产量等）q收集和确定数学模型的所有参数数据q列出目标函数的数学表达式q列出所有约束条件的线性数学表达式。Operation ResearchOperation Research第一讲第一讲第一讲第一讲qq

36、实例实例实例实例q有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如表1所示。现有三种货物待运，已知有关数据列于表2。又为了航运安全要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间载重量比例上偏差不超过15，前、后舱之间不超过10问该货轮应装载A、B、C各多少件，运费收入为最大?线性规划模型的建立（线性规划模型的建立（2）表1表2Operation ResearchOperation Research第一讲第一讲第一讲第一讲q问题分析（1）确定决策变量。 因为A、B、C三种商品在货轮的前、中、后舱均可装载，令i=1,2,3分别代表商

37、品A、B、C，用j1,2,3分别代表前、中、后舱，设决策变量xij为装于j舱位的第i种商品的数量(件). (2)确定目标函数 商品A的件数为x11+x12+x13，即装于货轮前、中、后舱商品A的件数之和，类似可得： 商品B的件数为x21+x22+x23 商品C的件数为x31+x32+x33 为使运费总收人最大，目标函数为： maxZ=1000(x11+x12+x13)+700(x21+x22+x23)+600(x31+x32+x33)线性规划模型的建立（线性规划模型的建立（3）Operation ResearchOperation Research第一讲第一讲第一讲第一讲(3)确定约束条件前、

38、中、后舱位载重限制为 线性规划模型的建立（线性规划模型的建立（4）前、中、后舱位体积限制为 A、B、C三种商品的数量限制为 Operation ResearchOperation Research第一讲第一讲第一讲第一讲 根据各舱实际载重大体应保持各舱最大允许载重量的比例关系，且前、后舱分别与中舱 之间载重量比例上偏差不超过15，前、后舱之间不超过10可得舱体平衡条件为：线性规划模型的建立（线性规划模型的建立（5） 各决策变量要求非负，即Operation ResearchOperation Research第一讲第一讲第一讲第一讲q建立模型线性规划模型的建立（线性规划模型的建立（5）Oper

39、ation ResearchOperation Research第一讲第一讲第一讲第一讲qq相关概念相关概念相关概念相关概念q可行解q满足线性规划问题约束条件的解，都称为该线性规划问题的可行解，所有可行解集合称为可行解集（或可行域）。q最优解q是目标函数达到最优值（最大值或最小值）的可行解，称为最优解。q凸多边形区域q设x1,x2为多边形区域中的两点，若两点连线上的任意一点，即ax1+（1-a)x2,(0a1)仍属于该多边形区域，则该多边形区域为凸多边形区域。q任何两个凸多边形区域的集合仍为凸多边形区域。q顶点q设x为凸多边形区域中的一点，若x不能用凸多边形区域种不同两点的线性组合来表示，则称

40、x为凸多边形区域的一个顶点。线性规划问题的图解法（线性规划问题的图解法（1）Operation ResearchOperation Research第一讲第一讲第一讲第一讲线性规划问题的图解法（线性规划问题的图解法（2）qq问题实例问题实例问题实例问题实例qq求解步骤求解步骤求解步骤求解步骤q求满足约束条件的可行域q建立直角坐标系，以x1为横轴，x2为纵轴；q确定非负约束x1 0， x2 0的各点集合，即第一象限；q确定满足约束条件2x1+3x2 100的各点集合。在坐标系中画出直线2x1+3x2 =100，该直线为边界的左下方的半平面即为满足约束条件2x1+3x2 100的各点集合；q同理，

41、确定其他各约束条件的点集合；q点集合的交叉区域即为该问题的可行域。Operation ResearchOperation Research第一讲第一讲第一讲第一讲q从可行域中找出目标函数的最优解q画目标函数的等值线；q平移等值线，在可行解区域内找到目标函数的最优解。qq线性规划问题图解法的几种特殊情况线性规划问题图解法的几种特殊情况线性规划问题图解法的几种特殊情况线性规划问题图解法的几种特殊情况q有多重最优解q将上例中目标函数由Z=6x1+4x2 变为Z=4x1+6x2 后，再用图解法进行求解q可行解区域无界q用图解法求解线性规划问题的图解法（线性规划问题的图解法（3）Operation Re

42、searchOperation Research第一讲第一讲第一讲第一讲q无可行解区域q用图解法求解qq图解法的几点讨论图解法的几点讨论图解法的几点讨论图解法的几点讨论q(1)若线性规划问题有可行解则可行解区域是一个凸多边形，它可能是有界的；也可能是无界的。q(2)若线性规划问题有最优解，则最优解可能是唯一的；也可能是无穷多个。如果是唯一的，这个最优解一定在该凸多边形的某个顶点上；如果是无穷多个，那末这些最优解一定是凸多边形的一条边界（包括此边界的两个端点）。总之，如果线性规划问题有最优解，则这个最优解一定可以在凸多边形的顶点达到。q(3)若线性规划问题有可行解，但是没有有限最优解。这时凸多边形是无界的。q(4)若线性规划问题没有可行解，即可行解集是空集，则此问题没有最优解。 线性规划问题的图解法（线性规划问题的图解法（4）