《管理运筹学》由会员分享，可在线阅读，更多相关《管理运筹学（16页珍藏版）》请在金锄头文库上搜索。
1、管理运筹学课程学习指导资料编写：彭盈适用专业：土木工程管理适用层次：专升本（业余）四川大学网络教育学院二 00 三年 10 月管理运筹学课程学习指导资料编写：彭盈审稿：审批：本课程学习指导资料根据该课程教学大纲的要求，参照现行采用教材管理 运筹学（郭耀煌主编，西南交通大学出版社，2001 年）以及课程学习光盘，并 结合远程网络业余教育的教学特点和教学规律进行编写，适用于工程管理专业专 科升本科学生。第一部分 课程的学习目的及总体要求一、 课程的学习目的教学目的是使学生掌握运筹学的主要模型；初步掌握如何将实际问题形成运 筹学的模型的方法和技巧，并能解决一些简单的实际问题。二、 课程的总体要求较深
2、入的了解线性规划、运输问题、动态规划、图与网络分析等运筹学分枝 学科的概念、原理和方法，培养学生的自学能力、创造性思维能力及综合运 用运筹学知识分析和解决实际问题的能力。第二部分 课程学习的基本要求及重点难点内容分析第一章 绪论1 本章学习要求：了解运筹学简史、主要内容及主要特点第二章 线性规划（一）1 本章学习要求：（1）应熟悉的内容：理解线性规划的意义，理解学习规划的一般形式， 理解线性规划问题中的基本概念：可行解，基可行解，最优解， 基，可行基，凸集，凸组合，顶点等。（2）应掌握的内容：掌握线性规划问题的标准形式；掌握解线性规划 问题的图解法；掌握解线性规划问题的单纯形法及其最优性检验
3、与解的判别方法；能用线性规划方法求解实际问题。（3） 应熟练掌握的内容：熟练掌握如何将线性规划一般问题化为标准形式；熟练准确的用单纯形法列表求解线性规划问题及其最优性 检验与解的判别方法。2本章重点难点分析：如何将线性规划一般问题化为标准形式；线性规划问题的单纯形法及其最优性检验与解的判别方法。3 本章典型例题（案例）分析1） 将下列线性规划问题化为标准形式，并列出初始单纯形表。 min z = 3 x + x - 2 x1 232x + 3x - 4x 81233x - x + 3x = 6123x 0, x无约束，x 0 3333x2 0 ，其他化为标准形max（文）T 3x Bx G x
4、 2x1223“ “ “ 、广 2x G 3x Bx” G 4x G x T12122344 x G xx ” 2 xx T 812 23 53x Bx G x” 3x T 61223X , X , X ”，X , X , X 0122345再引入人工变量，问题变为max（文）T 3x x G x” 2x Mx Mx122367r2x G 3x Bx” G 4x G x T12122344 x G xx ” 2 xx x T 81223563x Bx G x” 3x Bx T 612237、X , X , X, X , X , X , X , X 012234567初始单纯形表12-M-M-3
5、-1X2-1X2-3-1-2X3-2-3-1-M-M7M-3-11-5M-20 -M02） 一极大化线性规划问题的单纯形表见下表，若各变量均为非人工变量，当a ,a ,a ,a和8各在什么范围取值时12345a 表中的解为唯一最优解；b.有多重最优解c 目标函数无上界。cjcXbXXXXXX15/2001a-15/2Xa100aaX3/2010-1/43/2cj zj000a-1/2解：a. a 0, a 0,a4=0c. a 0, a ,a 05124(3) 见书P40例1 84. 本章作业1- 1（3），1-2（3）并化为标准型，1-5（2），1-7第三章 线性规划（二）1 本章学习要求：
6、（1）应熟悉的内容：熟悉线性规划的对偶理论，理解对偶单纯形法的 原理，正确使用此方法，理解对偶问题的经济解释影子价格。 了解运输问题模型特点；理解表上作业法与单纯形法的联系。（2）应掌握的内容：掌握原问题与对偶问题的对应关系，掌握对偶问 题的基本性质，掌握对偶单纯形方法，掌握运输问题模型结构； 掌握表上作业法的基本原理；掌握产销不平衡运输问题的概念、 模型结构；掌握表上作业法求解产销不平衡时的处理方法。（3）应熟练掌握的内容：熟练的准确的写出一般形式的线性规划的对 偶问题；熟练掌握对偶问题的基本性质，并且会应用这些性质； 熟练掌握对偶单纯形方法；熟练准确地就c、b、A中的元素发生 变化来进行灵
7、敏度分析，求出新的最优；熟练运用表上作业法求 解2.本章重点难点分析：对偶问题的基本性质，并且会应用这些性质；对偶单纯形方法；运用表上作业法求解3.本章典型例题（案例）分析A 原问题化为对偶问题原问对偶问题min z = 2 x + x - x123-X + x - x = 1广123x - x + x 21 23x + x 32 3 0, x 0, x 自由1 23m a xw = y + 2 y + 3 y123J+ y 2 1 -y1+y2+y3=-1、1 自由,y2 0, y3 0（4）见书 P62，例 24；例 25。C.已知运输问题的产销平衡表与单位运价表如下表所示，用表上作业法求
8、其最优解。解：用最小元素法确定初始方案；用闭回路法求检验数。初始方案表7地销地B1B2B3B4产量A101515A20151025A355销量5151510检验数表销地B1B2B3B4产量A116415A23125A32020115销量5151510上表中仍存在负检验数，继续调整方案并计算检验数。销地B1B2B3B4产量Al(3)5(16)1015A201015(4)25A35(17)(17)(12)5销量5151510注：括号内的数字为检验数。上表中所有检验数均非负，所以为最优调运方案表。最小的运费为z 335min4. 本章作业P106：21（2）；22；24（2）；27第四章 图与网络分
9、析1.本章学习要求：（1）熟悉的内容：了解如何用图论的观点去分析解决简单的实际问题； 会用避圈法和破圈法求部分树；了解欧拉圈、欧拉图、中国邮路 问题的概念，会求解中国邮路问题。（2）掌握的内容：掌握图的基本概念；掌握树的定义、性质；掌握用 矩阵法求图中任意两点间的最短路，对应的，也会求两点间的最 长路（如果存在）；掌握可行流、可行流的流量、最大流、割、割 的容量、最小割、增广链的概念；（3）熟练掌握的内容：熟练的用标号法求有向图与无向图中从一个点 到另一个点的最短路；熟练地用 Ford-Fulkerson 标号法求最大流2 本章重点难点分析 ：用标号法求有向图与无向图中从一个点到另一个点的最短
10、路；用 Ford-Fulkerson 标号法求最大流3 本章典型例题(案例)分析(1) 用 Dijkstra 算法计算下列有向图的最短路。解：P( vi )=0T ( v ) = gj第一步：因为 (v , v )12(j =2,37)(v1,v3)(v , v )e A14v，v是T标号，则修改上个点的T标号分别为: 34T (v ) =minT(v ) P(v )+ w12 2 1 12= minto,0 + 2= 2T(v )=minT(v ) P(v )+ w 13 3113= min L,0 + 5= 5T(v ) =minT(v ) P(v )+ w14 4 1 14= min匚,
11、0 + 3= 3所有T标号中，T( V2)最小令P( V2)=2第二步：v是刚得到的P标号，考察v 22(v , v )，(v , v )e A，且 v，v 是 T 标号2 32636T (v )=minT(v ) P(v )+ w 13 3223=min 15,2 + 2= 4 T (v ) 二 mint,2+7=96所有T标号中，T（ v4）最小令P（ v4 ）=3第三步：v是刚得到的P标号，考察v44T(v )二 min It(v ) P(v )+ w 5 5445= minL,3 + 5= 8所有T标号中，T（ v3）最小，令P（ v3）=4第四步：v是刚得到的P标号，考察v33T(v
12、 )二 minT(v ) P(v )+ w 5 5335=mink,4 + 3= 7T(v )=minT(v ) P(v )+ w 16 6336= minI9,4+51=9所有T标号中，T（ v5）最小，令P（ v5）=7第五步：v是刚得到的P标号，考察v55T(v ) = minIT(v ), P(v )+ w 16 6556= minI9,7 +11=8T(v ) = minIT(v ), P(v )+ w 17 7557= mint,7 +71=14所有T标号中，T（ v6）最小，令P（ v6）=8第6步：v是刚得到的P标号，考察v66T(v ) = minIT(v ), P(v )+ w 17 7667= minI14,8+51=13T (v )=P (v )=1377至此：所有的T标号全部变为P标号，计算结束。故v 1至 V7的最短路为 13。( 2) 见书 P143 例 364本章作业P175： 32 (a)和(b)； 3-4第五章 动态规划1本章学习要求：(1) 应熟悉的内容：明确什么是多阶段的决策问题；理
