《运筹》大纲(信息与计算科学专业)

《《运筹》大纲(信息与计算科学专业)》由会员分享，可在线阅读，更多相关《《运筹》大纲(信息与计算科学专业)（69页珍藏版）》请在金锄头文库上搜索。

1、运筹学复习课考 试 题 型一、判断题二、选择题三、计算题四、建模题2Chapter 1 线性规划 Linear Programming1.1 LP的数学模型 Mathematical Model of LP 1.2 图解法 Graphical Method 1.3 标准型 Standard form of LP 1.4 基本概念 Basic Concepts 1.5 单纯形法 Simplex Method3线性规划数学模型的三个要素：决策变量 Decision variablesn1目标函数是多个决策变量的线性函数，通常是求最大值或 最小值；怎样辨别一个模型是线性规划模型？1.1 线性规划的数

2、学模型 Mathematical Model of LP4目标函数 Objective function约束条件 Constraintsn2约束条件约束条件是一组多个决策变量的线性不等式或等式x1x2O1020304010203040(15,10)最优解X=(15,10)目标函数最优值Z=85例1.71.2 图解法 The Graphical Method5246x1x2246最优解X=(3,1) 最优值Z=5(3,1)min Z=x1+2x2例1.81.2 图解法 The Graphical Method6246x1x2246X（2）（3,1）X（1）（1,3）min Z=5x1+5x2例1

3、.9有无穷多个最优解 即具有多重解,通解为01 当=0.5时 =(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 1.2 图解法 The Graphical Method7246x1x2246无界解(无最优解)max Z=x1+2x2例1.101.2 图解法 The Graphical Method8x1x2O10203040102030405050无可行解 即无最优解max Z=10x1+4x2例1.111.2 图解法 The Graphical Method9由以上例题可知，线性规划的解有4种形式：1. 有唯一最优解(例1.7例1.8)2. 有多重解(例1.9)3. 有无界解

4、(例1.10)4. 无可行解(例1.11)1、2情形为有最优解 3、4情形为无最优解1.2 图解法 The Graphical Method10max(或min)Z=c1x1+c2x2+cnxn线性规划的标准型 Standard form of LP注：本教材默认目标函数是 max11或写成下列形式：或用矩阵形式1.3 线性规划的标准型 Standard form of LP12通常X记为： 称为约束方 程的系数矩阵，m是约束方程的个数，n是决策变量的个数 ，一般情况mn，且r()m.其中:1.3 线性规划的标准型 Standard form of LP13当m=n时，基矩阵唯一，当mZ1因此

5、LP5的最优解 就是原整数规划的最优解。上述分枝过程可用下图表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x13x14LP3:X=(4.33,6)Z3=35.33x26LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x14x15无可行解x273.2.2 求解纯纯整数规规划问题问题 的割平面法Cj4300b CBXBx1x2x3x4 4 3x1 x21 00 11/4 1/81/2 3/45/2 15/4j005/81/4分离系数后改写成再通过整数“逼迫”，构造割平面方程，然后将割平面方程加入

6、上面表中继续求解取源行，得Chapter 4 目标规划 Goal Programming 4.1 目标规划数学模型 Mathematical Model of GP4.2 目标规划的图解法 The graphical method of GP目标规划的求解思路: 按事先制定的目标顺序逐项检查，尽可能使得结果达到预定目标，即使不能达到目标也使得离目标的差距最小，对应的解称为满意解 设d为未达到目标值的差值，称为负偏差变量（negative deviation variable）d +为超过目标值的差值，称为正偏差变量（positive deviation variable）, d0、d0下面建立

7、例4.1的目标规划数学模型 目 标 约 束系统约束决策变量与偏差变量目标函数、优先等级 习题4.2的再次评讲 P91Chapter 5 运输与指派问题Transportation and Assignment Problem5.1运输模型 Mathematical Model of Transportation Problems 5.2 运输单纯形法 Transportation Simplex Method 5.3 运输模型的应用 Aplication of Transportation Model 5.4 指派问题 Assignment problem 物资调运。根据各地的生产量和需要量及

8、各地之间的运输费用，如何制定一个运输方案，使总运费最小5.1 运输模型 Model of Transportation Problems5.1.1 数学模型产地销地A110A28A35B43B38B27B15354 2 3 1 6 8 232 9图5.1【例5.4】求表5-10给出的运输问题的初始基本可行解 B1B2B3B4aiA14104420A2773815A31210615bj510251050表5-105.2 运输单纯形法 Transportation Simplex Method表5-11Bj AiB1B2B3B4aiA14104420A2773815A31210615 bj5102

9、51050【解】51001510105.2 运输单纯形法 Transportation Simplex Method45产销不平衡 产销平衡问题某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个 虚设的销地 运输费用为046某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件 物品的运费如下表所示，问：应如何调运可使总运输费用 最小？解：增加一个 虚设的产地 运输费用为0产销不平衡 产销平衡问题设xij(i=1

10、,2,，m；j=1,2,n)为第i个产地到第j个销地的运量产销平衡运输问题的一般数学模型设平衡运输问题的数学模型为：5.1.2 模型特征5.1 运输模型 Model of Transportation Problems1. 运输问题存在可行解，也一定存在最优解 2. 当供应量和需求量都是整数时，则一定存在整数最优解(已证明是正确的结论) 3. 有m+n个约束，mn个变量 4. 有m+n1个基变量【定理5.3】m+n1个变量组构成基变量的充要条件是它不包含任何闭回路 .则称E为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边. 运输问题中，如果一个变量组E通过适当排列，能得

11、到下 面这种形式：x25x23B1B2B3B4B5A1 A2 A3 x35A4 x43 x11x12x31x42表53变量组 x11,x12,x42, x 43, x 23, x 25, x 35, x 31构成一个闭回路. 共8个顶点， 这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路,如表5-3所示5.1 运输模型 Model of Transportation Problems一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接.表53中的变量x 32及x33不是闭回路的顶点，只是连线的交点.5.2 运输单纯形法 Transportation Simplex Me

12、thod运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：第一步：求初始基本可行解(初始调运方案). 常用的方法有最小 元素法、元素差额法（Vogel近似法）、左上角法.第二步：求检验数并判断是否得到最优解。常用求检验的方法 有闭回路法和位势法，当非基变量的检验数ij全都非负时得到最 优解，若存在检验数lk0，则则vj标标号:jfji 当收点已得到标标号时时，说说明已找到增广链链，依据vi 的标标号反向 跟踪得到一条增广链链。当收点不能得到标标号时时，说说明不存在增 广链链，计计算结结束。第一步： 找出第一个可行流，例如所有弧的流量fij =06.3.2 Ford-

13、Fulkerson标号算法6.3 最大流问题 Maximal Flow Problem*第三步：调整流量 （1）求增广链上点vi 的标号的最小值，得到调整量 （2）调整流量得到新的可行流f1，去掉所有标号，返回到第二步从发点重新 标号寻找增广链，直到收点不能标号为止 【定理6.1】 可行流f是最大流的充分必要条件是不存在发点到收 点的增广链 6.3 最大流问题 Maximal Flow Problem 改进图方法无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端 vi已标号另一端vj未标号的边只要满足 wijfij0 则vj就可标 号（wijfij）Chapter 7

14、网络计划 Network Programming7.1 绘制网络图 Draw network plot 7.2 网络参数 Network Parameter 7.3 网络的优化 Optimization of Network运 筹 学 Operations Research 7.1 绘制网络图绘制计划网络图的注意事项： 1、紧前工序 2、点的编号(可以一边画图一边编号，也可以画完各个工序以后再编号). 各工序的结束点的编号大于开始点的编号 3、图中不允许相邻两个点之间多于一条弧 4、图中不能有缺口和回路 5、除发点和收点之外，其他各点的前后都应有弧连接 工序时间确定 工序时间不确定时，用三点估

15、计法去估计工序的加工时间三点估计法是事先估计出工序的三种可能完成时间，其期望 值就作为工序时间的估计值.三种时间是： (1)完成工序（i，j）的最短时间，称为乐观时间，记为aij (2) 完成工序（i，j）的正常时间，称为最可能时间,记为mij (3) 完成工序（i，j）的最长时间，称为悲观时间，记为bij 三种时间发生的概率分别为1/6、4/6、1/6，则工序（i，j）完成时间的期望值为：7.2 网络参数Network Parameter计算工序的最早开始时间、最早完工时间、最迟必须开始时间、最迟必须结束时间、总时差找关键工序、关键路线以及项目的完工期图75a,6111b,9c,13d,5e,16f,12h,12g,10i,8k,20j,17l,250069 91919351947475572725552474742353719623140(3)关键工序：a、c、e、h、i、j关键路线： 11(4)工程的完工时间为72天