运筹学第五章

运筹学第五章Tag内容描述：<p>1、运筹学,赵明霞山西大学经济与管理学院,2020/4/26,2,第五章整数规划,整数规划的数学模型割平面法分支定界法0-1整数规划指派问题应用,2020/4/26,3,3,求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。在整数规划中:如果所有的变量都为非负整数，则称为纯整数规划问题；如果只有一部分变量为非负整数，则称之为混合整数规。</p><p>2、第五章 整数规划,5.1 整数规划实例及一般模型 5.2 分支定界法 5.3 0-1整数规划 5.4 指派问题,5.1.1 整数规划实例,例5.1某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下表所示。,甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大？,解 设x1、x2分别为甲、乙两种货物托运的件数，建立模型,3,整数规划问题的松弛问题,xj部分或全部取整数,5.1.2 整数规划的一般模型,整数规划的类型,纯整数规划：xj全部是整数 混合整数规划： xj部分是整数 0-1型整数规划：xj = 0或1,xj部分或全。</p><p>3、第五章 动态规划(Dynamic programming),1.引言 研究多阶段决策问题 R.E.Bellman 1951年提出动态规划。 1957年出版Dynamic Programming 应用：最优调度、资源分配 最优路径、最优控制 设备更新、库存问题, 2.多阶段决策问题,例. 某产品从A城运至F城，其间要经过若干 个城镇和若干条道路，路线结构如图所示， 图中给出了每段道路的运费（元），试选 择一条合理的运输路线，使总运费最小？,分析：方案 ：AB1C1E1F 运费：26元 方案 : AB3C3E3F 运费：22元 方案 : AB2C1E2F 运费：18元 最优方案：方案, 3.基本概念,1.阶段和阶段变量 阶段：过程。</p><p>4、第五章 图论与网络分析,图的基本概念 最小支撑树问题 最短路径问题,学习目标,图论起源哥尼斯堡七桥问题,结论：每个结点关联的边数均为偶数。,问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？,图的基本概念,哈密尔顿回路问题：环球旅行遊戏,欧拉回路：每边经过一次且仅一次的回路 哈密尔顿回路：每个点经过一次且仅一次的回路,问题：游戏者从任一城市出发，寻找一条可经过每个城市一次且仅一次，在回到原出发点的路?,图的基本概念,定义1：由点和边组成，记作G=(V，E)，其中 V=v1，v2，vn为结点的。</p><p>5、第5章 整数规划,在求解线性规划问题时，得到的最优解可能是分数或小数，但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题,称为整数规划(Integer Programming)或简称IP。,第一节 整数规划的数学模型及解的特点,引例,某厂拟用火车装运甲、乙两种货物集装箱，每 箱的体积、重量、可获利润以及装运所受限制如下：,问两种货物各装运多少箱，可使获得利润最大？,此例可解得x1=4.8,x2=0，凑整为x1=5,x2=0，这就破坏了条件(2)，因而不是可行解；如截断小数变为x1=4,x2=0，这当然满足所有约束条件，但不是最优解，因为对x1=4。</p>