PDF《第一章》

第一章 作业研究与软体 作业研究 资源有限、j望无穷乃是自然的天律,如何配置有限资源并做最有效的利用更 是人类社会活动的最高指导原则,也是进步的原动力.

作业研究肇始於第二次世界 大战期间,一群英国科学家投入如何有效利用有限的战争物资,产生最大效用的决 策分析研究.终战后更多学者继续投入研究,并引用到民间各行各业企业活动,这 些研究发展出许多有效的决策分析技术,而形成「作业研究」一门科学.作业研究 不仅是商学管理系所必修课程之一,近年来也是工程系所开设的重要课程,以培训 数学模式分析的管理与工程专才. 作业研究各种决策分析技术均需要冗长复杂的演算过程,使人工演算几乎变为 不可能;

目前坊间有关作业研究的著作均仅强调演算方法的论述,而缺乏演算工具 的提供或说明,使决策分析者纵有完整的企业决策模式,却因面临冗长复杂的演算 过程而踌躇不前,以致无法达成决策分析的最后目的.本书除有详细完整的作业研 究技术论述外,更撰写各种模式分析程式,以提供学习者及企业决策分析师快速精 准的演算工具.决策分析师因有分析演算工具,可考量更接近现实的分析模式,或 更多的决策方案模式,使企业更具竞争力.本章说明本书论述的各种作业研究技术 内容及各种分析程式的功能,并说明作业研究软体的安装与使用说明. 1-1 作业研究论述内容 本书共分十二章,除本章说明作业研究软体的安装与使用外,各章论述内容概 要说明如下:

第二章线性规划:图解法,线性规划为作业研究的最重要一种决策分析技术, 也是其他决策分析的基础.本章乃以两个决策变数的线性规划模式为例,说明线性 规划的模式建置步骤,并以图解法正确导入线性规划模式求解的基本观念,及各种 可能解的意义与研判.

第三章线性规划:单纯法,论述线性规划单纯法(Simplex Method)的演算法 则,各种特殊解的研判方法;

另外针对限制式中具有大於小於或等於关系式的限制 式,介绍大 M 法及两阶段法使单纯法演算更臻完整.最后说明线性规划单纯法程式 使用说明.

第四章线性规划:软体解,本章介绍微软公司试算表软体(Excel)内的规划

第一章 作业研究与软体 求解(Solver)增益集(Add-ins)及相关函数的使用说明.规划求解增益集为一个 可以求解线性规划模式、整数规划模式,及非线性规划模式的软体工具.本章主要 说明实数线性规划模式求解的参数设定、选项设定、讯息与报表解读等.另列举许 多线性规划模式以供熟悉线性规划模式的解题技术,增进规划求解增益集的使用技 术.另外规划求解增益集亦可用以搜寻目标及多方案线性规划问题.最后说明线性 规划(LP)一般解程式,使能求解任何线性规划问题.

第五章敏感度分析与对偶问题,寻求线性规划问题的最佳解固然是决策者的重 要目标,但是最佳解并不是一成不变的.最佳解可能因为市场供需变化及竞争,使 销售获利或制造成本或可用资源改变而改变.研究这些参数的变动对於最佳解的冲 击与影响称为敏感度分析(Sensitivity Analysis).本章先以图解法说明目标函数系 数或限制式右端常数的改变对於最佳解及目标函数值的影响,以建立敏感度分析的 基本观念;

再辅以如何从规划求解(Solver)的报表读取各种敏感度分析的资讯. 本章最后论述对偶问题及原始问题的转换与程式使用说明.

第六章运输问题与指派问题,运输问题与指派问题为线性规划问题的特例.本 章除论述规划求解增益集在运输问题与指派问题的应用外,并说明运输问题与指派 问题的单纯法.西北角法及最佳效用法为运输问题中求取初始解的方法,再辅以 MODI 法与踏石法以寻觅退出变数与进入变数.匈牙利法为指派问题的单纯法.本 章另附运输问题与指派问题程式使用说明.

第七章整数线性规划,说明整数线性规划的意义、分类与应用.限制决策变数 为整数或

0 与1可以更方便、有效来描述真实世界,使线性模式更接近事实.固定 开销问题(Fixed-Charged Problem)、涵盖面问题(Set-Covering Problem)、片段 式线性函数(Piecewise Linear Function)的处理及限制式 OR 关系的处理等,均为 整数规划的特殊应用.限制决策变数为整数或

0 与1反而使模式求解方法更趋复 杂;

单纯法必须经过修正才可适用,但仍相当复杂而不甚适用,因此许多特殊解法 相继研发而出.规划求解增益集仍可有效、简单的求解整数线性规划模式;

其他如 分支界限法(Branch and Bound)、隐含列举法(Implicit Enumeration)及切面法 (Cutting Plane Algorithm)均是整数规划的特殊解法.本章含有分支界限法及隐含 列举法程式及其使用说明.

第八章多准则决策规划,线性规划技术可为决策者寻觅多个决策变数在各种 限制条件下的单一准则(Single Criterion)或目标(最大利润,最小成本)的最佳 解;

但决策者可能需要同时兼顾考量多项准则(Multiple Criteria)以获得最佳的决 作业研究 策.这些多项决策准则间或有相互矛盾或竞争之问题,因此尚难获得所有准则均处 最佳状态的最佳解,技术上仅能求得多项准则的最佳妥协解决方案(Compromise Solution).多准则决策规划即是一种寻觅多准则决策问题最佳妥协解决方案的规划 技术.本章讨论目标规划(Goal Programming)与层级分析法(Analytic Hierarchy Process)两种多准则规划技术,并附有相关程式以纾解复杂的演算程序.

第九章网路模式,数学规划实务问题可以网路模式充分描述与解决.本章论述 的网路模式有最小跨越树(Minimum Spanning Tree)、最短路径(Shortest Path)、 最大流量(Maximum Flow)、最小成本网路流量(Minimum Cost Network Flow Problem, MCNFP)等问题,并附相关程式及其使用说明.

第十章计画评核术与要径法,为网路模式的一种特殊应用;

任何非常规性的任 务或专案,由於缺乏经常性的经验或牵涉许多人力、物力、财力等多方面资源的整 体配合,如何能在预定时程及预算内圆满达成任务,是一种重要的管理技术.这种 任务或专案可能大至各项国家经济建设的推展,小到公司的厂房建设、产品研发、 设备安装、个人的房屋修缮或婚丧喜庆活动筹备等,均须许多人力、部门与资源的 协助与配合.这种大型或复杂的专案已不允许单靠专案经理人的记忆来推动专案的 进行,而须以某种文件方式让相关部门t解整体进展与配合时程,造成管理上的一 大挑战. 专案经理人应该随时掌握整个专案可以完成的时间及准时完成的机率;

专案中 每一作业项目应该何时才能开始,何时必须完成,以免影响下一个工作项目的进 行;

哪些工作项目必须准时开始,准时完成,否则便影响整个专案完成时程;

哪些 工作项目可以配合资源的调用,而有一些工作开始与完成的宽裕时间及宽裕时间的 长短;

如有工作项目延迟到位,应能评估其对整个专案进程的影响,及是否需要赶 工措施、赶工所需配合资源的评量等诸问题,以便让上司t解工作的进展,让相关 部门适时的配合与支援,让下游工作人员或包商知所配合,甚至是责任厘清的根 .本章提供计画评核术与要径法相关程式,使专案管理更臻完整与简便. 第十一章动态规划,有些决策规划问题因为未能符合线性规划的比例性、可加 性、可分性等基本假设,而无法使用线性规划技术求解之.动态规划是将此类问题 的n个决策变数分成 n 个阶段(Stage)的子问题,然后先解最容易的子问题,接 著利用已被解的子问题的解,求解另一子问题,直到原问题被求解为止的一种技 术.本章论述最短(长)路径问题、背包最佳装填问题、通用资源配置问题、人力 规划问题、设备更新问题、生产计画问题、生产批量问题(Wagner-Whitin演算法及

第一章 作业研究与软体 Silver-Meal演算法)等问题并附有各问题的求解程式. 第十二章非线性规划,有些决策规划问题因为未能符合目标函数,或限制式线 性关系的基本要求,而无法使用线性规划技术求解之.非线性函数的型态及行为变 化太大,致无法获得单一解法可以适用於各类型非线性函数的非线性规划问题;

不 同类型的非线性目标函数及(或)非线性限制式函数,使非线性规划问题的解法更 为复杂且解法效率偏低.规划求解(Solver)增益集仍可用以求解一般性的非线性 规划问题.本章论述单变数非线性模式、单峰单变数函数的黄金搜寻法、二分搜寻 法、多变数函数凹凸性研判、无束约多变数非线性规划的最陡峭下降法、等式关系 非线性模式、不等式关系非线性模式、可分离规划、最适方向渐进法等的论述与程 式,最后并提供非线性规划一般解程式及其使用说明. 1-2 作业研究软体功能 作业研究软体按线性规划(LinearProgramming)、运输问题(Transportation)、指派问题(Assignment)、多准则决策分析、网路模式 (Network Model)、PERT 与CPM、动态规划(Dynamic Programming)、非线性 规划(NLP)等大类说明如下: 线性规划(Linear Programming)内有单纯法(Simplex Method)、分支界限法 (Branch and Bound)、纯0-1 整数线性规划、线性规划(LP)一般解等四个程式. 各程式功能说明如下表: 线性规划(Linear Programming) 程式名称 程式功能 单纯法(Simplex Method) 适用於决策变数全为实数,限制式可以有 =、≥、≤ 等,程式自动 研判是否需要经过两阶段法演算或仅一阶段演算即可.本程式显 示整个单纯法的第一阶段及第二阶段的全部演算过程与数,并 研判无解、无限值解、消失解、多重解或唯一解. 分支界限法(Branch and Bound) 适用於决策变数中含有整数限制的线性规划模式,本程式显示全 程变数分支与目标值界限的完整过程与数. 纯0-1 整数线性规划 适用於决策变数仅为

0 或1的纯整数线性规划模式,亦即隐含列 举法;

全程列举每一步骤的最佳组合与可行组合. 线性规划(LP)一般解 可适用於任何线性规划模式的求解,决策变数可以是实数、整数、0 或1的二元变数或任意组合,限制式当然也可以是=、≥、 ≤ 等关系式;

属最一般化的线性规划模式求解程式. 作业研究 运输问题(Transportation)内有西北角法求初始解、最佳效用法求初始解、 Solver解运输问题等三个程式.各程式功能说明如下表: 运输问题(Transportation) 程式名称 程式功能 西北角法求初始解 求解运输表的西北角法初始解. 最佳效用法求初始解 求解运输表的最佳效用法初始解. Solver 解运输问题 以试算表中的规划求解增益集求解运输问题. 指派问题(Assignment)内有 Solver 解指派问题程式.其程式功能说明如下 表: 指派问题(Assignment) 程式名称 程式功能 Solver 解指派问题 以试算表中的规划求解增益集求解指派问题. 多准则决策分析内有加权目标法(Weights Method)、优先目标法(Preemptive Method)、层级分析法(AHP)等三个程式.各程式功能说明如下表: 多准则决策分析 程式名称 程式功能 加权目标法 (Weights Method) 加权目标法乃将多个目标方程式的线性规划模式中的各个目标方程式加权变 成一个目标函数,再以线性规划求解之. 优先目标法 (Preemptive Method) 优先目标法乃将多个目标方程式的线性规划模式中的各个目标方程式,依决 策者主观的优先顺序建立不同目标函数,以线性规划模式求解之,再於原线 性规划模式中添增限制式以保证优先目标的实现;

再依次求解次要优先目 标,直到所有目标方程式均已加入线性规划模式求解. 层级分析法 (AHP) 某些决策问题的决策准则或限制条件不能以函数或方程式表示之而仅能 凭决策者的偏好、直觉来研判,则可使用层级分析法(Analytic Hierarchy Process, AHP)技术加以分析.AHP 程式依霾哒叨悦恳桓鼍霾咦荚蚋秤 一个偏好度,再对每一个决策方案,针对不同决策准则赋予偏好度(成对比 较矩阵),最后依枚瘸啥跃卣笠来渭扑愀骶霾叻桨付跃霾咦荚虻挠畔 度,及各决策方案的总优先度;

最高总优先度的决策方案则为最佳方案. 网路模式(Network Model)内有最小跨越树(Minimum Spanning Tree)、网路 弧线长排序表、最短路径代克思托(Dijkstra)演算法、Excel 解Dijkstra 试算表、 最短路径福乐得(Floyd)演算法、Excel 解Floyd 试算表、最大流量(Maximum Flow Problem)、Excel 解最大流量、最小成本网路流量问题(MCNFP)、Excel 解

第一章 作业研究与软体 MCNFP 等十个程式.各程式功能说明如下表: 网路模式(Network Model) 程式名称 程式功能 最小跨越树 (Minimum Spanning Tree) 本程式乃依钚】缭绞(Minimum Spanning Tree)演算法提供快速的 最小跨越树演算结果,显示获选的弧线及最小跨越树的总长度. 网路弧线长排序表 为便於人工推演最小跨越树演算法,本程式提供按弧线长度大小的排序 表. 最短路径代克思托 (Dijkstra)演算法 本程式依疃搪肪兜拇怂纪(Dijkstra)演算法推算网路模式中从网 路起点到任意终点的最短路径及路径总长度. Excel 解Dijkstra 试算表 依Dijkstra试算表中的网路各弧线起讫点及弧线长度,利用试算表的求 解规划增益集求解最短路径及路径总长度. 最短路径福乐得(Floyd) 演算法 本程式依疃搪肪兜母＠值(Floyd)演算法推算网路模式中从........