运筹学课程讲义
第一部分 线性规划
第一章 线性规划的基本性质
1.1 线性规划的数学模型
一、 线性规划问题的特点 胜利家具厂生产桌子和椅子两种家具。桌子售价
50 元/个，椅子售价 30 元 /个。生产桌子和椅子需木工和油漆工两种工种。生产一个桌子 需要木工 4 小时，油漆工 2小时。生产一个椅子需要木工 3 小时，油 漆工 1 小时。该厂每月可用木工工时为 120 小时，油漆工工时为 50
小时。问该厂如何组织生产才能使每月的销售收入最大？ max z 50x1 30x2
4x1 3x2 120
2x1 x2 50
x1,x2 0 例：某工厂生产某一种型号的机床。每台机床上需要 2.9m、 2.1m、
1.5m的轴，分别为1根、2根和1根。这些轴需用同一种圆钢制作， 圆钢的长度为74m。如果要生产100台机床，问应如何安排下料，才 能用料最省？
二、 数学模型的标准型
1. 繁写形式
2. 缩写形式
3. 向量形式
4. 矩阵形式 若原模型中变量 xj 有上下界，如何化为非负变量？ 三、 任一模型如何化为标准型？
1. 若原模型要求目标函数实现最大化，如何将其化为最小化问
题？
2. 若原模型中约束条件为不等式，如何化为等式？
3. 若原模型中变量 xk 是自由变量，如何化为非负变量？
1. 2 图解法
该法简单直观，平面作图适于求解二维问题。 使用该法求解线性规划问题时，不必把原模型化为标准型。
一、 图解法步骤
1. 由全部约束条件作图求出可行域
2. 作出一条目标函数的等值线
3. 平移目标函数等值线，作图求解最优点，再算出最优值 max z 5x1 6x2 7x3
x1 5x2 3x3 15
5x1 6x2 10x3 20
x1 x2 x3 5
x1 0,x2 0,x3无约束
令 x1' x1,x3 x3' x3'' ,x3' ,x3'' 0, Z 1
Z'
基于网络流的飞行员人力资源规划模型
飞行员人力资源规划是航空公司人力资源部门的主要任务之一，同时也是保障公司航班正常运行和提高利润的重要因素之一。需要航空公司建立科学的人力资源规划，有步骤地针对航班任务的短期乃至长期需求对飞行员进行合理安排，保证各个岗位对人员的需求能够得到恰当的满足。如果任何一个岗位人员储备不够充分，其填补需要花费较长的周期，这样会在一个时期内造成飞行员人手紧张，对机组排班调度带来巨大压力，甚至直接影响航班的正常运行。反过来说，若在各个岗位储备人员过多，虽然能够充分保证生产需求，但是却会造成成本的大量增加，也会影响公司的利润。
鉴于此，需要首先根据公司的发展远景、航班规模预测、飞行员月飞行小时数量标准、合理的人机比等因素确定未来飞行员的数量，进而根据与现有数量的差值，得出飞行员需求数量，然后有计划、有步骤地进行飞行员的培养和训练，使得在每一年度飞行员的数量能够满足公司航班的需求，同时保证成本的可行性。
本章主要研究如何建立人力资源流动规划，满足航空公司飞行员人力资源需求。首先介绍航空公司人力资源管理的特点，以及人力资源规划的主要内容与目标。然后根据该特点，基于网络流理论建立航空公司人力资源规划模型，并探讨了该模型的算法。最后给出一个算例。
4.1 问题背景
航空公司的人力资源问题要考虑以下方面：
1、航空公司有737、747、767、777等多种机型执行飞行任务，同时每种机型又分为副驾驶、正驾驶、机长等不同级别的岗位。一般而言，每位飞行员按照其技术水平担当某种机型某个岗位的工作，不能够同时跨机型跨岗位担任飞行任务。 2、与其他行业的专业技术职称晋升类似，飞行员可以在满足一定技术水平要求的基础上，通过相应的训练程序，按规定进行本机型内的岗位升级或转到其它机型的某种岗位上去。这也是当某种机型的某个岗位发生人员需求时的主要解决方法。
3、一般而言，升级或者转机型要求飞行员在原岗位上有一定的飞行经历，因而一个飞行员不能连续两年都发生升级或者转机型的情况。
运筹学复习重点
运筹学复习重点
第1章线性规划与单纯形法
(1) 化线形规划标准形的手法
(2) 线性规划解的概念、解的情形、解的判定
(3) 单纯形法的计算过程、迭代逻辑。
(4) 熟练运用单纯形表求解问题；若给出单纯形表，要会解读，会基于单纯形
法基本原理反推出表中一些参数。
(5) 两阶段法、大M法 第2章对偶理论和灵敏度分析
(1) 会写对偶问题，掌握对偶性质，原问题与对偶问题之间的关系。
(2) 互补松弛定理的应用：知道一个问题的最优解，求另一个问题的最优解
(3) 对偶单纯形法
(4) 当目标函数系数和右端项变化时灵敏度分析的简便方法 第3章目标规划
(1) 根据问题的特征和对多个目标的追求，通过引入偏离量，正确构建所需的
目标规划数学模型
(2) 会用图解法求目标规划的最优解或满意解 第4章整数规划
(1) 分支定界法：如何构造分支子问题，如何更新目标函数最优值上下界，何
时终止。
(2) 害IJ平面法：如何写对源约束方程；如何拆分、组装割平面方程；如何利用
对偶单纯形法继续求解 第5章无约束优化
(1) 凸函数与凸规划的定义与判别
(2) —维搜索的0.618法基本原理和迭代过程
(3) 无约束优化的最速下降法的基本原理、迭代过程 第6章约束极值优化
(1) 可行下降方向的含义、满足什么代数条件、几何意义
(2) 正确写出Kuhn-Tucker条件，理解K-T条件与最优解的关系
（3） 利用Kuhn-Tucker条件，求出K-T点和最优解。
（4） 外点法和内点法的基本原理、无约束优化目标函数的一般构造手法
第7章动态规划
（1） 动态规划的基本原理和基本方程
（2） 动态规划的逆推解法
（3） 动态规划求静态规划问题的套路
第8章图与网络优化
（1） 图的基本概念、树的基本性质、最小支撑树的求法
（2） 求最短路的Dijkstra算法
（3） 增广链的概念、用途，求网络最大流的标号法
1 第1章 线性规划
Chapter 1 Linear Programming
本章内容提要
线性规划是运筹学的重要内容。本章介绍线性规划数学模型、线性规划的基本概念以及求解线性规划数学模型的基本算法——单纯形法。
学习本章要求掌握以下内容：
线性规划模型的结构
线性规划的标准形式，非标准形式转化为标准形式
线性规划的图解以及相应的概念。包括：约束直线，可行半空间，可行解，可行域，凸集，极点，目标函数等值线，最优解
线性规划的基本概念。包括：基，基础解，基础可行解，基变量，非基变量，进基变量，离基变量，基变换
单纯形法原理。包括：基变量和目标函数用非基变量表出，检验数，选择进基变量的原则，确定离基变量的方法，主元，旋转运算
单纯形表。包括初始单纯形表的构成，单纯形表运算方法
初始基础可行解，两阶段法
退化的基础可行解
§1.1 运筹学和线性规划
1.1.1 运筹学
运筹学（Operations Research）是二十世纪三十年代二次大战期间由于战争的需要发展起来的一门学科。当时，英国组织了一批自然科学和工程科学的学者，和军队指挥员一起，研究大规模战争提出的一些问题。如轰炸战术的评价和改进、反潜艇作战研究等，研究结果在战争实践中取得了明显得效果。这些研究当时在英国称为Operational Research，直译为作战研究。战争结束以后，这些研究方法不断发展完善，并逐步形成学科理论体系，其中一些主要的理论和方法包括：线性规划，网第一章 线性规划
2 络流，整数规划，动态规划，非线性规划，排队论，决策分析，对策论，计算机模拟等。这些理论和方法在经济管理领域也得到了广泛应用，Operations Research也转义成为“作业研究”。我国将Operations Research译成“运筹学”，非常贴切地将Operations Research这一英文术语所包含的作战研究和作业研究两方面的涵义都体现了出来。
