基于网络流的飞行员人力资源规划模型
飞行员人力资源规划是航空公司人力资源部门的主要任务之一，同时也是保障公司航班正常运行和提高利润的重要因素之一。需要航空公司建立科学的人力资源规划，有步骤地针对航班任务的短期乃至长期需求对飞行员进行合理安排，保证各个岗位对人员的需求能够得到恰当的满足。如果任何一个岗位人员储备不够充分，其填补需要花费较长的周期，这样会在一个时期内造成飞行员人手紧张，对机组排班调度带来巨大压力，甚至直接影响航班的正常运行。反过来说，若在各个岗位储备人员过多，虽然能够充分保证生产需求，但是却会造成成本的大量增加，也会影响公司的利润。
鉴于此，需要首先根据公司的发展远景、航班规模预测、飞行员月飞行小时数量标准、合理的人机比等因素确定未来飞行员的数量，进而根据与现有数量的差值，得出飞行员需求数量，然后有计划、有步骤地进行飞行员的培养和训练，使得在每一年度飞行员的数量能够满足公司航班的需求，同时保证成本的可行性。
本章主要研究如何建立人力资源流动规划，满足航空公司飞行员人力资源需求。首先介绍航空公司人力资源管理的特点，以及人力资源规划的主要内容与目标。然后根据该特点，基于网络流理论建立航空公司人力资源规划模型，并探讨了该模型的算法。最后给出一个算例。
4.1 问题背景
航空公司的人力资源问题要考虑以下方面：
1、航空公司有737、747、767、777等多种机型执行飞行任务，同时每种机型又分为副驾驶、正驾驶、机长等不同级别的岗位。一般而言，每位飞行员按照其技术水平担当某种机型某个岗位的工作，不能够同时跨机型跨岗位担任飞行任务。
2、与其他行业的专业技术职称晋升类似，飞行员可以在满足一定技术水平要求的基础上，通过相应的训练程序，按规定进行本机型内的岗位升级或转到其它机型的某种岗位上去。这也是当某种机型的某个岗位发生人员需求时的主要解决方法。
3、一般而言，升级或者转机型要求飞行员在原岗位上有一定的飞行经历，因而一个飞行员不能连续两年都发生升级或者转机型的情况。
4、有些飞行员因年龄、身体等方面的原因在未来退出飞行工作。
5、航空公司每年可以采取从飞行学院招收毕业生、从其它航空公司调入等方式进行人员补充，我们统称为外部人力资源库。但是按照规定，他们只能补充到规定的某几种机型的某几类岗位上。
6、根据规定，每位飞行员每年都要参加一定量的常规训练。若进行升级、转机型等流动，还要参加针对性的训练。除此之外，还有应急训练、特殊项目训练等多种训练内容。而训练资源是有限的。其中，用于训练新进飞行员的资源数量第二年不少于第一年。
7、为了保证飞行队伍的稳定性，一般采取的措施是尽量减少飞行员的岗位流动。
以上是在研究航空公司人力资源规划时需要考虑的实际背景。假设航空公司已经制定了未来两年的飞机购入计划，因而可以根据生产任务、飞行员飞行时间限制规定、人机比等因素求得明、后两年各机型各岗位人员需求数量。本章将主要讨论在训练资源有限的限定条件下，如何安排飞行员在各机型、各岗位的流动规划，以满足明、后两年的人员需求，同时使人员变动达到最小，以保证岗位的稳定性。
4.2 人力资源规划
人力资源规划[45,95]又称人力资源计划，是指为实施企业的发展战略，完成企业的生产经营目标，根据企业内外部环境和条件的变化，运用科学的方法对企业人力资源的需求和供给进行预测，制定相应的政策和措施，从而使企业人力资源供给和需求达到平衡，实现人力资源合理配置，有效激励员工的过程。狭义的人
力资源规划是指企业从战略规划和发展目标出发，根据其内外部环境的变化，预测企业未来发展对人力资源的需求，以及为满足这种需求所提供的人力资源的活动过程。实质上它是企业各类人员需求的补充规划。
人力资源规划的总目标是：确保企业各类工作岗位在适当的时机，获得适当的人员，实现人力资源的最佳配置，最大限度地开发和利用人力资源潜力，有效地激励员工，保持智力资本竞争优势。人力资源规划是人力资源部门所有活动的起点[1]。当缺乏人力资源规划或者规划不足时，可能导致职位空缺或冗余，造成效率上的损失或者成本上的增加，企业的收益必将受损。
人力资源规划要考虑到为了实现组织目标所需要的人员数量、质量、结构等多维因素[44]。数量方面，主要是探求现有的人力资源数量是否与企业机构的所需数量相匹配；质量方面，是指现有工作人员的受教育程度及所受的培训状况，关键是工作知识和工作能力的高低；结构方面，主要是研究企业机构人员搭配是否合理高效。
按照规划的用途与时间幅度，人力资源规划可以分为三个层次：
1、战略层：一般是指5年或5年以上的长期规划，主要内容是根据企业的战略目标预测未来企业对人力资源的需求，估计远期企业内部人力资源状况，协调需求与供给。
2、战术层：2－5年规划，属于中期规划，其内容包括对企业现有员工的数量、素质情况的分析、需求数量的预测，通过内外部供给情况确定净需求量。
3、作业层：是短期的规划，包括人员审核、招聘、提升与调动、组织变革、培训与发展、工资与福利、劳动关系等操作的具体行动方案。
如图4.1所示。
图4.1 人力资源分类图
其中研究对人力资源的需求主要考虑的因素包括生产需求、经济状况、技术水平、财务资源、企业营业额、企业成长、管理哲学与技巧等方面，研究对人力资源的供给主要考虑的因素包括人口变化、经济形势、政府政策、竞争、劳动力教育情况、劳动力流动性、失业比率等等。企业要达到对人力资源需求与供给的平衡，可以针对人力资源短缺或冗余分别采用全职、兼职、返聘或者临时聘用、临时解雇、降职、退休等方法。如图4.2所示。
图4.2 人力资源需求、供给与平衡图
在本章中，将主要从战术层面讨论航空公司的人力资源规划问题。对于航空公司多种机型多类岗位的人力资源的需求预测问题，在本文不作具体研究，假设是已知的。本文主要研究如何建立人力资源流动规划，满足航空公司飞行员人力资源需求。
4.3 飞行员人力资源规划模型
在第一章中阐述了目前人力资源规划常用的几种方法。其中，德尔菲法与回归分析等方法的主要作用是进行人员供应与需求预测。马尔可夫概率矩阵通过研究过去人力资源变动的规律，来推测未来人力变动的趋势，同时给出人员流动方案。它要求转移概率是稳定的，不受任何外部因素的影响。然而未来的人员需求随机性相当大，过去人力资源的变动规律未必能够与未来的人员需求相一致，其偏差会对飞行员人力结构造成巨大影响，导致人员紧张或富余。控制论方法采用各类人员之间的转换比率，研究各类岗位的人员变动。这种方法与马尔可夫概率矩阵类似，需要通过历史数据对该比率进行估计。这同样会与未来需求之间产生
差距。而线性规划方法能较好的描述各岗位的人员数量以及人员流动。本节将根据飞行员人员流动的特点进行针对性的研究。
根据上一节的描述可以看出，若将每一年各机型各岗位看作若干产地，将第二年各机型各岗位看作若干销地，将训练所使用的资源看作成本，那么飞行员人力资源规划问题在本质上是与运输问题类似的。因而，可以采用网络流理论研究该问题。由于本问题涉及3年的飞行员人力资源状况，显而易见，需要把每年的状况作为一个层次，进行分层研究。这里有两种研究方法：其一是以每位飞行员为研究对象，研究其每年在机型岗位上的流动；其二是以各机型岗位为研究对象，研究其每年人员的流入流出数量。前者比较形象地反映了飞行员的升级转机型路径，具体到每一位飞行员的实际状况；后者没有具体到每一位飞行员的状况，但是较好地反映了各机型岗位的供应与需求状态。显然，在这里，后一种方法更加符合本问题的研究。
我们将三年的各机型岗位状况分别用顶点集表示，每个顶点表示某种机型某个岗位在某年的人员需求状况，另外，对于外部人力资源库以及未来不执行飞行任务的人员集合，同样用顶点表示。网络中的弧表示从某个岗位向另一个岗位的人员流动，每条弧上定义一位飞行员发生该项流动而参加训练所使用的资源数量。那么该网络的可行流即为人力资源规划问题的可行解。我们的目标是在网络中求解人力资源规划问题的最优解。如图4.3所示。
我们将目前、明年及后年各机型各岗位的状况分别用顶点集合V 、/V 、//
V 表示。不同的字母表示各种机型，字母的下标表示各类岗位，各年的情况用上标进行区分。如果按照规定，两个岗位之间允许存在人员流动，则用一条弧e 从转出岗位指向转入岗位来表示；各弧的权表示分配给该流动的训练资源量。如图4.3所示。具体如下：
{}s b a a V ,,,,,121 =：目前各机型各岗位的状况；其中：
i x ：机型x 的岗位i ，如737机型的副驾驶岗位；
i x M ：点i x 的赋值，表示该机型该岗位目前拥有的人数，该数值可由统计数据得出，是已知的；
s ：公司今年的外部人力资源库；
{}
///1/
2/1/,,,,,,s t b a a V =：明年各机型各岗位的状况。其中：
/j x ：机型x 的岗位j ；
/j
x N ：点/j x 的赋值，表示该机型该岗位明年的需求人数，如前所述，我们假
设该数值可由预测方法给出；
/t ：明年不执行飞行任务的人员集合（包括退休等情况）；
/s ：公司明年的外部人力资源库；
{}
//////1//2//1//,,,,,,s t b a a V =：后年各机型各岗位的状况；其中：
//j x ：机型x 的岗位j ；
//j
x L ：点//j x 的赋值，表示该机型该岗位后年的需求人数，如前所述，我们假
设该数值可由预测方法给出；
//t ：后年不执行飞行任务的人员集合（包括退休等情况）。
从目前向明年发生的人员流动表示如下：
/j
i y x e ：从V 中任意一点i x 到/V 中任意一点/j y 的弧，表示按照规定，可以从机型x 的岗位i 向机型y 的岗位j 进行人员流动；
/j
i y x f ：/j
i y x e 上的流动数量，其上下限分别为/j
i y x F ，0。
/j
i y x e 分为以下几种情况：
/j
i x x e ：从V 中i x 到/V 中/j x 的弧，由于机型没有发生变化，岗位发生变化，
因而表示升级的情况；
/j
i y x e ：从V 中i x 到/V 中/j y 的弧，由于机型发生变化，因而表示转机型的情
况；
/i
i x x e ：从V 中i x 到/V 中/i x 的弧，表示机型岗位都没有发生变化，仍从事原工作的情况；
/i
sx e ：从V 中s 到/V 中/i x 的弧，表示从外部人力资源库补充人员到机型x 的
岗位i 的情况；
/t x i
e ：从V 中i x 到/V 中/t 的弧，表示机型x 的岗位i 的某些飞行员明年不执
行飞行任务的情况。
相应的，有：
j
i x x j
i x x j
i x x /j
i y x f ：/j
i y x e 上的流动数量，其上下限分别为/j
i y x F ，0；
/i
i x x f ：/i
i x x e 上的流动数量，其上下限分别为/i
i x x F ，0；
/i
sx f ：/i
sx e 上的流动数量，其上下限分别为/i
sx F ，0；
/t x i
C ：/t x i
e 上的流动数量，假设是公司已知的。
类似的，有从明年向后年发生的人员流动：
///j
i
y x e ：从/V 中任意一点/i x 到//V 中任意一点//j y 的弧，表示按照规定，可以
从机型x 的岗位i 向机型y 的岗位j 进行人员流动；
///j
i
y x f ：///j
i
y x e 上的流动数量，其上下限分别为///j
i
y x F ，0。
///j
i
y x e 分为以下几种情况：
///j
i
x x e ：从/V 中/i x 到//V 中//j x 的弧，由于机型没有发生变化，岗位发生变化，
因而表示升级的情况；
///j
i
y x e ：从/V 中/i x 到//V 中//j y 的弧，由于机型发生变化，因而表示转机型的
情况；
///i
i
x x e ：从/V 中/i x 到//V 中//i x 的弧，表示机型岗位都没有发生变化，仍从事
原工作的情况；
///i
x s e ：从/V 中/s 到//V 中//i x 的弧，表示从外部人力资源库补充人员到机型x
的岗位i 的情况；
///t x i
e ：从/V 中/i x 到//V 中//t 的弧，表示机型x 的岗位i 的某些飞行员后年不
执行飞行任务的情况。
相应的，有：
///j
i
x x f ：///j
i
x x e 上的流动数量，其上下限分别为///j
i
x x F ，0；
///j
i
y x f ：///j
i
y x e 上的流动数量，其上下限分别为///j
i
y x F ，0；
///i
i
x x f ：//
/i
i
x x
e 上的流动数量，其上下限分别为///i
i x x F ，0；
i
x s i
x s i
x s ///t x i
C ：///t x i
e 上的流动数量，依然假设是目前公司已知的。
对于训练资源，有：
/j
i y x Q ：对于从i x 到/j y 的流动，公司拥有的训练资源；
/j
i y x q ：每位飞行员从i x 到/j y 的流动所需要花费的训练资源数量（包括升级、
转机型、新进以及岗位不变的情况）；
///j
i
y x Q ：对于从/i x 到//j y 的流动，公司拥有的训练资源；
///j
i
y x q ：每位飞行员从/
i x 到//j y 的流动所需要花费的训练资源数量
（包括升级、转机型、新进以及岗位不变的情况）；
Q ：公司拥有的训练资源总量。
下面讨论网络流上的数量关系。对于目前的每种机型的各个岗位，即顶点集
V 中的任意一点i x ，由图4.1可知，其现有人员明年可能有升级、转机型、不执
行飞行任务等多种去向，即：
///t x y y x x i
j
j
i i C f M +=∑ V x i ∈∀ （4.1）
对于明年每种机型的各个岗位，即顶点集/V 中任意一点/j y ，分别从其需求和去向进行分析。其需求可能由多种方式满足，包括从目前本机型的较低岗位升级而来、从其它机型转来或者从外部人力资源库引进，即
///j
i
j i j
sy x y x y f f N +=∑ //V y j ∈∀ （4.2）
其去向与目前类似，后年可能有升级、转机型、不执行飞行任务等多种去向，即：
/////
////t y x x y y j
i i j j
C f N +=∑ //V y j ∈∀ （4.3）
对于后年每种机型的各个岗位，即顶点集//V 中任意一点//j y ，其需求可能由多种方式满足，包括从明年本机型的较低岗位升级而来、从其它机型转来或者从外部人力资源库引进，即
////
/////j
i j
i
j y s x y x y f f L +=∑ //
//V y j ∈∀ （4.4） 同时，今年发生升级或转机型的人员明年不再参加人员流动，即
/////////i
i i i j
j
i x x x x y y x f f f
≤-∑ //
V x i ∈∀ （4.5）
为了保持各机型各岗位人员的稳定性，规定一个比例p ，至少有此比例的人员应继续留在该岗位上。即
i i
i x x x M p f ⨯≥/ V x i ∈∀ （4.6）
////i
i
i
x x x N p f ⨯≥ //
V x i ∈∀ （4.7）
同时还需要考虑训练资源的有限性，在每一条发生人员流动的弧上（不包括流向/t 、//t 的弧）有
///j i j i j i y x y x y x Q q f ≤ //,V y V x j i ∈∈∀ （4.8）
/////////j
i
j
i
j
i
y x y x y x Q q f ≤ //
//
//,V y V x j i ∈∈∀ （4.9）
用于新进飞行员训练的资源数量，第二年不少于第一年，有
∑∑≤///////j
j
j
j
y y s y sy Q Q
（4.10）
所有流动耗费的训练资源总量不超过公司拥有的资源量Q ，有
Q Q
i
j
j
i x y y x ≤∑∑// （4.11） Q Q
i
j
j
i x y y x ≤∑∑/
///// （4.12）
在满足以上约束条件的情况下，航空公司的目标是在满足航班生产对飞行员数量需求的前提下，使得两年中人员变动最小。即
∑∑-+-////////
//)()(min j
j
j j i i
i i
y y y y x x x x f L f N （4.13）
由式（4.1）—（4.13），我们得到飞行员人力资源规划模型：
⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪
⎪⎩
⎪
⎪
⎪⎪⎪⎪⎪
⎪⎪⎪
⎪⎪⎪⎨
⎧≤≤≤∈∈∀≤∈∈∀≤∈∀⨯≥∈∀⨯≥∈∀≤-∈∀=+∈∀=+∈∀=+∈∀=+-+-∑∑∑∑∑∑∑∑∑∑∑∑∑////////////
//////////////////////////////////////////////////////
////
//////
///////
////////
///,,..)
()(min i j j
i i j j i j
j j j j
i j i j i j
i j i j i i
i i i i i i i i i j
j
i j
j i j i j
j i i j j i
j j
i i j
i
j i i j
j
j j
i
i i
x y y x x y y x y y s y sy j i y x y x y x j i y x y x y x i x x x i x x x i x x x x y y x j y y s x y x j y t y x x y j y x sy y x i x y t x y x x y y y
y x x x Q Q Q Q Q Q V
y V x Q q f V y V x Q q f V x N p f V x M p f V x f f f V y L f f V y N C f V y N f f V
x M C f t s f L f N （4.14）
商学院 课程实验报告 课程名称 运筹学 专业班级 金融工程班 姓 名 指导教师 成 绩 2018年 9 月 20日 学号：
表2 所需营业员统计表 星期一二三四五六日需要人数300 300350400480600 550 3.建立线性规划模型 设x j（j=1，2，…，7）为休息2天后星期一到星期日开始上班的营业员数量，则这个问题的线性规划问题模型为 minZ=x1+x2+x3+x4+x5+x6+x7 {x1+x4+x5+x6+x7≥300 x1+x2+x5+x6+x7≥300 x1+x2+x3+x6+x7≥350 x1+x2+x3+x4+x7≥400 x1+x2+x3+x4+x5≥480 x2+x3+x4+x5+x6≥600 x3+x4+x5+x6+x7≥550 x≥0,j=1,2,…,7 （二）操作步骤 1.将WinQSB安装文件复制到本地硬盘，在WinQSB文件夹中双击setup.exe。 图1 WinQSB文件夹 2.指定安装软件的目标目录，安装过程中输入用户名和单位名称（任意输入），安装完毕之后，WinQSB菜单自动生成在系统程序中，熟悉软件子菜单内容和功能，掌握操作命令。
图2 目标目录 3.启动线性规划和整数规划程序。点击开始→程序→WinQSB→Linear and Lnteger Programming，屏幕显示如图3所示的线性规划和整数规划界面。 图3 线性规划 4.建立新问题或打开磁盘中已有文件。按图3所示操作建立或打开一个LP问题，或点击File→New Problem建立新问题。点击File→Load Problem打开磁盘中的数据文件，点击File→New Problem，出现图4所示的问题选项输入界面。 图4 建立新问题
1.用单纯形法求解下述问题，并指出问题的解属于哪一类。 2.分别用大M 法和两阶段法求解下列线性规划问题，并指出解属于哪一类 3.已知线性规划问题： （a ）写出其对偶问题； （b ）已知原问题最优解为X*=（1,1,2,0）。试根据对偶理论，直接求成对偶问题的最优解。 ?????? ?≥≥≥≤++≤+-≤++-++=3,2,117220441322..46max 321321321321321x x x x x x x x x x x x t s x x x z ()?? ???? ?=≥=-+≤+≥++++=3,2,105421823..54max 32121321321j x x x x x x x x x t s x x x z j 123412412343413 min 86362336..2 2 0(1,,4) j z x x x x x x x x x x x s t x x x x x j =+++?++≥? +++≥?? +≥??+≥??≥=?
4.已知线性规划问题 其最优解为x 1=-5,x 2=0,x 3=-1. （a ）求k 的值； （b ）写出并求其对偶问题的最优解。 5.对于下述线性规划问题 已知最优解中的基变量为x 3,x 1,x 5,且已知 求：根据上述信息确定三种资源各自的影子价格 6.已知线性规划问题 当t 1=t 2=0时，求解得最终单纯形表如下表所示： 当t 1=t 2=0时，求解得最终单纯形表如下表所示： x 1 x 2 x 3 x 4 x 5 x 3 5/2 ? 1 ? ??? ??≥≤≤-+-=++-+-=无约束 321 3213213 21,0,06 4..22min x x x kx x x x x x t s x x x z ??? ?? ? ?=≥≤++++≤++++≤++++++++=)5,,1(0)3(180323)2(270234)1(1803332..93648max 5432154321543215 4321 j x x x x x x x x x x x x x x x x t s x x x x x z j 资源资源资源 ???? ? ?????----=???? ? ?????-103 2 396131127 131 2 1423131 ()??? ??=≥+=++++=++++++++=)5,,1(03..00max 2 253232221212 14313212111543322111 j x t b x x a x a x a t b x x a x a x a t s x x x c x c x t c z j
前进电器厂生产A,B,C三种产品，有关资料如表： 在资源限量及市场容量条件下，如何安排生产使获利最多。（只写出线性规划数学模型，不要求求解） 二、 考虑下面的线性规划问题: 其计算机求解的结果如下 **********************最优解如下************************* 目标函数最优值为 : 18.5 变量最优解相差值 ------- -------- -------- x1 8.5 0 x2 1.5 0 x3 0 6.5 x4 0 4 约束松弛/剩余变量对偶价格 ------- ------------- -------- 1 5 0 2 0 2 3 0 3.5
目标函数系数范围: 变量下限当前值上限 ------- -------- -------- -------- x1 0 2 无上限 x2 -3 1 无上限 x3 无下限 -1 5.5 x4 无下限 1 5 常数项数范围: 约束下限当前值上限 ------- -------- -------- -------- 1 无下限 2 7 2 -1 4 无上限 3 0 3 无上限 根据上图回答下列问题： 1.请指出其最优解及其最优目标函数值。 2.约束条件2对偶价格为多少？对其含义给予解释。 3.目标函数中的系数在什么范围内变化时，其最优解不变？ 4.第一个约束条件常数项从2增加到6，目标函数值是否发生改变？为什么？ 5.当目标函数的系数由2降为1，的系数由1降为-1，最优解是否发生改 变？请用百分之一百法则进行判断。 三、 某公司在三个地方有三个分厂，生产同一种产品，其产量分别为300箱、400箱、500箱.需要供应四个地方的销售，这四地的产品需求分别为400箱、250箱、350箱、200箱.三个分厂到四个销售地的单位运价如下表所示
运筹学（第3版）习题答案 第1章线性规划 P36 第2章线性规划的对偶理论 P74 第3章整数规划 P88 第4章目标规划 P105 第5章运输与指派问题P142 第6章网络模型 P173 第7章网络计划 P195 第8章动态规划 P218 第9章排队论 P248 第10章存储论P277 第11章决策论P304 第12章 多属性决策品P343 第13章博弈论P371 全书420页 第1章 线性规划 1.1工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示． 表1－23 产品 资源 A B C 资源限量 材料(kg) 1.5 1.2 4 2500 设备(台时) 3 1.6 1.2 1400 利润(元/件) 10 14 12 根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130.试建立该问题的数学模型,使每月利润最大． 【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为 1231231 23123123max 1014121.5 1.2425003 1.6 1.21400 150250260310120130,,0 Z x x x x x x x x x x x x x x x =++++≤⎧⎪++≤⎪⎪≤≤⎪⎨ ≤≤⎪⎪≤≤⎪≥⎪⎩ 1.2建筑公司需要用5m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格 及数量如表1－24所示： 表1－24 窗架所需材料规格及数量 型号A 型号B 每套窗架需要 材料 长度（m ） 数量(根) 长度(m) 数量(根) A 1：2 2 B 1：2.5 2 A 2：1.5 3 B 2：2 3 需要量（套） 300 400
基于网络流的飞行员人力资源规划模型 飞行员人力资源规划是航空公司人力资源部门的主要任务之一，同时也是保障公司航班正常运行和提高利润的重要因素之一。需要航空公司建立科学的人力资源规划，有步骤地针对航班任务的短期乃至长期需求对飞行员进行合理安排，保证各个岗位对人员的需求能够得到恰当的满足。如果任何一个岗位人员储备不够充分，其填补需要花费较长的周期，这样会在一个时期内造成飞行员人手紧张，对机组排班调度带来巨大压力，甚至直接影响航班的正常运行。反过来说，若在各个岗位储备人员过多，虽然能够充分保证生产需求，但是却会造成成本的大量增加，也会影响公司的利润。 鉴于此，需要首先根据公司的发展远景、航班规模预测、飞行员月飞行小时数量标准、合理的人机比等因素确定未来飞行员的数量，进而根据与现有数量的差值，得出飞行员需求数量，然后有计划、有步骤地进行飞行员的培养和训练，使得在每一年度飞行员的数量能够满足公司航班的需求，同时保证成本的可行性。 本章主要研究如何建立人力资源流动规划，满足航空公司飞行员人力资源需求。首先介绍航空公司人力资源管理的特点，以及人力资源规划的主要内容与目标。然后根据该特点，基于网络流理论建立航空公司人力资源规划模型，并探讨了该模型的算法。最后给出一个算例。 4.1 问题背景 航空公司的人力资源问题要考虑以下方面： 1、航空公司有737、747、767、777等多种机型执行飞行任务，同时每种机型又分为副驾驶、正驾驶、机长等不同级别的岗位。一般而言，每位飞行员按照其技术水平担当某种机型某个岗位的工作，不能够同时跨机型跨岗位担任飞行任务。
2、与其他行业的专业技术职称晋升类似，飞行员可以在满足一定技术水平要求的基础上，通过相应的训练程序，按规定进行本机型内的岗位升级或转到其它机型的某种岗位上去。这也是当某种机型的某个岗位发生人员需求时的主要解决方法。 3、一般而言，升级或者转机型要求飞行员在原岗位上有一定的飞行经历，因而一个飞行员不能连续两年都发生升级或者转机型的情况。 4、有些飞行员因年龄、身体等方面的原因在未来退出飞行工作。 5、航空公司每年可以采取从飞行学院招收毕业生、从其它航空公司调入等方式进行人员补充，我们统称为外部人力资源库。但是按照规定，他们只能补充到规定的某几种机型的某几类岗位上。 6、根据规定，每位飞行员每年都要参加一定量的常规训练。若进行升级、转机型等流动，还要参加针对性的训练。除此之外，还有应急训练、特殊项目训练等多种训练内容。而训练资源是有限的。其中，用于训练新进飞行员的资源数量第二年不少于第一年。 7、为了保证飞行队伍的稳定性，一般采取的措施是尽量减少飞行员的岗位流动。 以上是在研究航空公司人力资源规划时需要考虑的实际背景。假设航空公司已经制定了未来两年的飞机购入计划，因而可以根据生产任务、飞行员飞行时间限制规定、人机比等因素求得明、后两年各机型各岗位人员需求数量。本章将主要讨论在训练资源有限的限定条件下，如何安排飞行员在各机型、各岗位的流动规划，以满足明、后两年的人员需求，同时使人员变动达到最小，以保证岗位的稳定性。 4.2 人力资源规划 人力资源规划[45,95]又称人力资源计划，是指为实施企业的发展战略，完成企业的生产经营目标，根据企业内外部环境和条件的变化，运用科学的方法对企业人力资源的需求和供给进行预测，制定相应的政策和措施，从而使企业人力资源供给和需求达到平衡，实现人力资源合理配置，有效激励员工的过程。狭义的人
实验报告 课程名称：运筹学导论 实验名称：线性规划问题实例分析 专业名称：信息管理与信息系统 指导教师：刘珊 团队成员：邓欣(20112111) 蒋青青(20114298) 吴婷婷(20112124) 邱子群(20112102) 熊游(20112110) 余文媛(20112125) 日期：2013-10-25 成绩：___________ 1．案例描述 南部联盟农场是由以色列三个农场组成的联合组织。该组织做出了一个关于农场农作物的种植计划，如下：
每一个农场的农业产出受限于两个量，即可使用的灌溉土地量和用于灌溉的水量。数据见下表： 适合本地区种植的农作物包括糖用甜菜、棉花和高粱。这三种作物的差异在于它们每亩的期望净收益和水的消耗量不同。另外农业部门已经制定了南部联盟农场作物总亩数的最大配额，见下表： 作物的任何组合可以在任何农场种植，技术部门的任务是找出一个种植方案使南部联盟农场的净收益最大化。 2.建立模型 决策变量为Xi(i=1,2,……,9),表示每个农场每种作物的种植量。 MAX Z=1000(X1+X2+X3)+750(X4+X5+X6)+250(X7+X8+X9) 约束条件： （1）每一个农场使用的土地 X1+X4+X7≤400
X2+X5+X8≤600 X3+X6+X9≤300 (2)每一个农场的水量分布 3X1+2X4+X7≤600 3X2+2X5+X8≤800 3X3+2X6+X9≤375 (3)每一种作物的总种植量 X1+X2+X3≤600 X4+X5+X6≤500 X7+X8+X9≤325 非负约束Xi≥0 , i=1,2, (9) 3.计算机求解过程 步骤1.生成表格
习题二 2.1 写出下列线性规划问题的对偶问题 (1) max z ＝10x1＋x2＋2x3(2) max z ＝2x1＋x2＋3x3＋x4 st. x1＋x2＋2 x3≤10 st. x1＋x2＋x3 ＋x4≤5 4x1＋x2＋x3≤20 2x1－x2＋3x3＝－4 x j≥0 （j＝1,2,3）x1－x3＋x4≥1 x1，x3≥0，x2，x4无约束 (3) min z ＝3x1＋2 x2－3x3＋4x4(4) min z ＝－5 x1－6x2－7x3 st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15 x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤20 2x1－3x2－7x3 －4x4＝2＝x1－x2－x3＝－5 x1≥0，x4≤0，x2，，x3无约束x1≤0，x2≥0，x3无约束 2.2 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化： （1）问题的第k个约束条件乘上常数λ（λ≠0）； （2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上； （3）目标函数改变为max z＝λCX（λ≠0）； 'x代换。 （4）模型中全部x1用3 1 2.3 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4 st. x1＋2x2＋x4≥3 3x1＋x2＋x3＋x4≥6 x3 ＋x4＝2 x1 ＋x3 ≥2 x j≥0（j＝1,2,3,4） (1) 写出其对偶问题； (2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。 2.4 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量 st. 2x1 ＋x3＋x4≤8 y1 2x1＋2x2＋x3＋2x4≤12 y2 x j≥0（j＝1,2,3,4） 其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。 2.5 考虑线性规划问题max z＝2x1＋4x2＋3x3 st. 3x1＋4 x2＋2x3≤60 2x1＋x2＋2x3≤40 x1＋3x2＋2x3≤80 x j≥0 （j＝1,2,3） （1）写出其对偶问题 （2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解； （3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的
课程名称:《运筹学》 一、判断题(共404小题） 1、1957年，我国从“夫运筹帷之中，决胜于千里之外”这句话中摘取运筹两字，将Operations Research译作运筹学。(A) 2、答案：(B)。运筹学的英文名字是Operations management。 3、答案：(B)。我国第一个运筹学研究小组于1976年在中科院力学所成立 4、答案：(B)。线性规划的标准形式为求极小值。 5、答案：(A)。满足线性规划所有约束条件的各变量的一组值称为线性规划问题的可行解。 6、答案：(A)。设函数f(x),g(x)是上关于x的凸函数，则h(x)=max{f(x),g(x)}也是关于x的凸函数。 7、答案：(B)。两个图若没有公共边，则称它们是不相交的 8、答案：(B)。目标函数和约束函数都是关于变量的非线性函数才是非线性规划 9、答案：(A)。从求解极小点的整体过程来说，最速下降法未必最快。 10/答案：(B)。图解法提供了求解线性规划问题的通用方法 11、答案：(A)。《运筹学学报》的前身是《运筹学杂志》。（） 12、答案：(B)。《运筹学杂志》是国际运筹学联盟的一个主要刊物。（） 13、答案：(A)。运筹学是一门优化科学。（） 14、答案：(A)。运筹学是以数学为主要工具的。（） 15、答案：(A)。运筹学是系统工程的主要理论基础。（） 16、答案：(B)。运筹学主要是理论研究，不关注实用性。（） 17、答案：(A)。理论和应用的发展相互促进促使了运筹学的发展。（） 18、答案：(A)。机器等待维修问题属于排队问题。（） 19、答案：(B)。运筹学的研究领域已确定了，不会再出现新的领域了。（） 20、答案：(B)。运筹学独立于其他学科。（） 21、答案：(A)。运筹学所说的模型都是数学模型。（） 22、答案：(A)。 运筹学是一种将定性和定量相结合的方法。（） 23、答案：(A)。运筹学分散融化于其他学科，并结合其他学科一起发展。（） 24、答案：(A)。运筹学的发展进一步依赖于计算机的应用和发展。（） 25、答案：(A)。田忌赛马的故事是对策论的一个例子。() 26、1005510,答案：(B)。运筹学研究问题是从系统的观点出发，研究局部的性问题。（） 27、1005710,答案：(A)。电话服务的问题属于排队论的应用。（） 28、1005810,答案：(B)。我国第一个运筹学研究小组于1976年在中科院力学所成立。（） 29、1005910,答案：(A)。任一行列式的行数与列数相等。（） 30、1006010,答案：(A)。矩阵的行数与列数可以不同。（） 31、2002110,答案：(A)。 线性规划所有可行解的集合构成可行域。 32、2002210,答案：(A)。使线性规划的目标函数达到最优值的可行解称为线性规划的最优解。 33、2002310,答案：(B)。基解都是可行的。 34、2002410,答案：(B)。线性规划是指该问题的目标函数是决策变量的线性
第 4 次课 2学时 本次课教学重点： 会用运筹学软件、能分析运筹学软件的输出结果 本次课教学难点： 分析输出结果 ，百分百法则 本次课教学内容： 第三章 线性规划问题的计算机求解 随书软件为“管理运筹学”2.0版（Window 版），是1.0版（DOS 版）的升级版。它包括：线性规划、运输问题、整数规划（0-1整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共15个子模块。 第一节 “管理运筹学”软件的操作方法 软件使用演示：（演示例1） 例1. 目标函数：2110050x x Z Max += 约束条件：t s . 30021≤+x x 400221≤+x x 2502≤x 0,021≥≥x x 第一步：点击“开始”→ “程序”→ “管理运筹学2.0”，弹出主窗口。 第二步：选择所需子模块，点击主窗口中的相应按钮。本题中选用“线性规划”方法。点击按钮
弹出如下界面： 第三步：点击“新建”按钮，输入数据。本题中共有2个变量，3个约束条件，目标函数取MAX 。点击“确定”后，在表中输入j ij i b a c ,,等值，并确定变量的正负约束。输入数值后的界面如下。 第四步：点击“解决”按钮，得出计算结果。本题的运行结果界面如下。
第二节 “管理运筹学”软件的输出信息分析 一、分析运行结果 本题中目标函数的最优目标值 27500=z ，最优解250,5021==x x 1、相差值表示相应的决策变量的目标系数需要改进的数量，使得决策变量为正值，当决策变量已为正数时，相差数为零。 2、 松弛/剩余变量的数值表示还有多少资源没有被使用。如果为零，则表示与之相对应的资源 已经全部用上。 3、对偶价格表示其对应的资源每增加一个单位，将增加多少个单位的最优值。 4、目标函数系数范围表示最优解不变的情况下，目标函数的决策变量系数的变化范围。当前值是指当前的最优解中的系数取值。 5、常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变化时，与其对应的约束条件的对偶价格不变。当前值是指现在的取值。 以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变，只有一个系数变化的基础上得出的！ 二、当有多个系数变化时，需要进一步讨论。 百分之一百法则：对于所有变化的目标函数决策系数（约束条件右边常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解）。 * 允许增加量 = 上限 —现在值 c 1 的允许增加量为 100 —50 = 50 b 1 的允许增加量为 325 - 300 = 25 * 允许减少量 = 现在值 - 下限 c 2 的允许减少量为 100 - 50 = 50 b 3 的允许减少量为 250 - 200 = 50 * 允许增加的百分比 = 增加量 / 允许增加量 * 允许减少的百分比 = 减少量 / 允许减少量
第一章、 线性规划和单纯形法 1.1 线性规划的概念 一、线性规划问题的导出 1．(引例) 配比问题——用浓度为45%和92%的硫酸配置100t 浓度为80%的硫酸。 取45%和92%的硫酸分别为x1和x2t, 则有： 求解二 元一次方程组得解。 目的相同，但有5种不同浓度的硫酸可选（30%，45%，73%， 85%，92%）会出现什么情况？ 设取这5种硫酸分别为 x1、x2、x3、x4、x5 t, 则有： ?? ??=++++=++++1008.092.085.073.045.03.0100 5432154321x x x x x x x x x x 请问有多少种配比方案？为什么？哪一种方案最好？ 假设5种硫酸价格分别为：400，700，1400，1900，2500元/t ，则有： 2. 生产计划问题 如何制定生产计划，使三种产品总利润最大？ 考虑问题： ?? ??=+=+1008.092.045.0100 2121x x x x ??? ??=≥?=++++=++++++++=5,,2,1,01008.092.085.073.045.03.0100..25001900140070040054321543215 4321 j x x x x x x x x x x x t s x x x x x MinZ j
（1）何为生产计划？ （2）总利润如何描述？ （3）还要考虑什么因素？ （4）有什么需要注意的地方（技巧）？ （5）最终得到的数学模型是什么？ 二、线性规划的定义和数学描述（模 型） 1．定义：对于求取一组变量xj (j =1,2,......,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。 2.配比问题和生产计划问题的线性规划模型的特点： 用一组未知变量表示要求的方案，这组未知变量称为决策变量； 存在一定的限制条件，且为线性表达式； 有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线性表达式，称之为目标函数； 对决策变量有非负要求。 3．LP 的数学描述(数学模型)： （1）一般形式 ????? ????≥≥=≤+++≥=≤++≥=≤++++++=0,,,),(),(),(..)(2122112 2222121112121112211n m n mn m m n n n n n n x x x b x a x a x a b x a x a x a b x a x a x a t s x c x c x c Z Min Max 或 ??? ??=≥≤++≤++++=3,2,1,09743..32321321321j x x x x x x x t s x x x MaxZ j
第四章 运筹学模型 本章教学重点是： 线性规划模型 目标规划模型 运输模型及其应用 图论模型 最小树问题 最短路问题 最大流问题与最小割 复习要求 1．进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵。 2．进一步理解数学模型的作用与特点。 本章复习重点是线性规划模型、运输问题模型和目标规划模型。具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单。运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单。你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求。目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型。这是主要的考虑方向。另外，关于图模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型。这之前恐怕要善于将一个实际问题转化为图模型。还有一个最小数的问题，该如何把一个网络中的最小数找到。另外在个别场合可能会涉及一笔划问题。 1．营养配餐问题的数学模型为 或更简洁地表为 其中的常数C j 表示第j 种食品的市场价格，a ij 表示第j 种食品含第i 种营养的数量，b i 表示人或动物对第i 种营养的最低需求量. 例1 医院为病人配制营养餐，要求每餐中含有铁不低于50单位，蛋白质不低于40单位，钙不低于42单位．假设仅有两种食品A 和B 可供配餐，相关数据见下表．试问，如何购买两种食品进行搭配，才能即使病人所需营养达到需求，又使总花费最低？ 解：设购买食品A 和B 依次为x 1和x 2（kg ），则有 营养最低要求满足： 10x 1+5x 2≥50 （铁含量） 5x 1+8x 2≥40 （蛋白质含量） 6x 1+5x 2≥42 （钙含量） 总花费数记为Z ，则有数学模型 s .t .⎪⎪⎩⎪⎪⎨⎧≥≥+≥+≥+0 ,) 3.3(,4256)2.3(,4085)1.3(,5051021212121x x x x x x x x 用图解法求解上述问题． 首先以x 1,x 2为坐标轴，建立平面直角坐标系（如图3-10），由于x 1,x 2均非负，故只画出了第一象限．
运筹学模型 源于第二次世界大战期间的运筹学研究，有效地解决了如何将有限的资源分配于各项军事活动，以取得最优的战争效果等重大军事决策问题，为盟军取得二战的胜利作出了不可磨灭的贡献。战后，该项技术不但在军事科学上不断发展，在工农业生产、科学实验、工程技术、经济管理和社会科学中都有着广泛的应用和发展。特别是计算机技术的引入，更使得运筹学的研究和应用如虎添翼，一些大规模或超大规模的决策变量和约束条件问题的求解也变成了现实。 运筹学的分支较多，这里我们只介绍线性规划、整数规划、动态规划等方面的运筹学应用和模型，读者通过学习解决这些运筹学问题的思想和方法，而对运筹学模型的建立、应用和求解有更深的认识。 一、线性规划模型 1．线性规划数学模型的一般形式 例1．农作物的生产安排问题 1）问题的提出 以色列的某社区联盟，其农业生产受农田面积和灌溉配水量的限制，其资料如表4.1所示 表4.1 适合该地区种植的农作物有甜菜、棉花和栗子，其每英亩的期望净收益、用水量及可种植的最大面积如表4.2所示 表4.2
试问，该社区联盟应如何安排这三种农作物的生产，方使总的收益最大？ 2）假设与分析 决策变量)9,,2,1( =j x j 分别表示这三个社区三种农作物的种植面积（见表4.3所示）。 表4.3 则该问题的线性规划模型为： 目标函数 )(100)(300)(400 m ax 987654321x x x x x x x x x z ++++++++= 约束条件为： 非负性： )9,,2,1( 0 =≥i x i 土地约束： 300600 400963852741≤++≤++≤++x x x x x x x x x 水资源约束： 37523800 2360023963852741≤++≤++≤++x x x x x x x x x
运筹学第三版课后习题答案 运筹学是一门研究如何在有限资源下做出最优决策的学科。它涉及到数学、统计学、经济学等多个学科的知识，可以应用于各个领域，如物流管理、生产调度、供应链优化等。而《运筹学》第三版是一本经典的教材，它系统地介绍了运筹学的基本概念、方法和应用。本文将针对该教材的课后习题进行解答，帮助读者更好地理解和掌握运筹学的知识。 第一章：线性规划 1. 习题1.1：求解线性规划问题的常用方法有哪些？ 答：求解线性规划问题的常用方法包括单纯形法、对偶理论、整数规划等。其中，单纯形法是最常用的方法，它通过迭代寻找目标函数值最小（或最大）的解。 2. 习题1.2：什么是线性规划的对偶问题？如何求解线性规划的对偶问题？答：线性规划的对偶问题是指通过原始问题的约束条件构造一个新的问题，该问题的目标是最大化（或最小化）原始问题的目标函数值。求解线性规划的对偶问题可以使用对偶理论，通过将原始问题转化为对偶问题的等价形式，再利用对偶问题的特性进行求解。 第二章：整数规划 1. 习题 2.1：什么是整数规划问题？与线性规划问题有何不同？ 答：整数规划问题是指决策变量的取值必须为整数的线性规划问题。与线性规划问题相比，整数规划问题的解空间更为有限，求解难度更大。整数规划问题在实际应用中常常涉及到资源的离散分配、路径选择等问题。 2. 习题2.2：列举几个整数规划问题的应用场景。
答：整数规划问题的应用场景包括生产调度、物流路径优化、设备配置等。例如，在生产调度中，需要确定每个生产批次的数量和时间，以最大化产能利用率和最小化生产成本。 第三章：动态规划 1. 习题3.1：什么是动态规划？它的基本思想是什么？ 答：动态规划是一种通过将问题划分为多个子问题，并保存子问题的解来求解原问题的方法。其基本思想是利用子问题的解构建全局最优解，从而避免重复计算和提高求解效率。 2. 习题 3.2：动态规划在哪些问题中有应用？ 答：动态规划在最短路径问题、背包问题、序列比对等问题中有广泛的应用。例如，在最短路径问题中，可以通过动态规划求解从起点到终点的最短路径，从而实现最优路径规划。 通过以上习题的解答，我们对运筹学的基本概念、方法和应用有了更深入的了解。运筹学作为一门综合性的学科，可以帮助我们在面对复杂的决策问题时，通过数学建模和优化方法找到最优解。掌握运筹学的知识，不仅可以提高决策的准确性和效率，还可以为企业的发展和社会的进步做出贡献。因此，学习和应用运筹学是非常重要的。希望读者通过本文的内容，对运筹学有更全面的认识，并能够在实际问题中灵活运用。
第2章线性规划 ２.５ ａ. ｂ. 需要制定的决策：确定在两家公司中各按多少比例投资 决策的约束条件:投资的资金数额不能超过可用于投资的资金、花费的时间不能多于寻找一份有意义的夏季工作的时间 决策的总体绩效测度指标：投资这两家公司的总利润 c. 约束条件的定量表述 设投资公司1的比重为a，公司２的比重为b 则应满足的条件为4０0a+５00b＜=6０0 50０0ａ＋4０0０ｂ<=60０0 a>=0 ｂ>=０ ｄ. e. 这个电子表格模型是一个线性规划模型，它具有以下特征: ①需要制定一系列关于活动水平的决策,因此可变单元格被用来显示这些水平，投资两个公司的比重,同时决定资金、时间的投入及带来的总利润。 ②这些活动的水平可以取能够满足多个约束条件的任何数值(包括小数值）,本问题受投资资金和可用于投资的时间的限制。 ③每一个约束条件都描述了一种对活动水平可行值得限制,约束条件的左边往往是一个输出单元格，中间是一个数学符号(＜=、>=或=),右边是数据单元格(ＤE为输出单元格,F为<=符号,ＧH为数据单元格） ④活动水平决策以输入到目标单元格的一个总体绩效测度指标为基础，其目标是最大化单元格,这由绩效指标的性质（本题是求利润的最大化,这一目标被输入目标单元格Ｈ8） ⑤每个输出单元格（包括目标单元格)的Exceｌ公式可以表达为一个SＵＭPRＯDUCT函数，其中加总的每一项都是一个数据单元格与一个可变单元格的乘积。 ｆ.
代数模型 选择投资两家公司的利润最大化,Ｐ=4500a＋４500b 满足所有下列约束条件:40０a+500b<=６0０ 5００0a+40０0ｂ<=6000 a>=0 b＞=0 g． 代数形式：决策变量ａ、b ;电子表格形式 目标函数:4500a+4500b 非负约束ａ>=0和b>=0 函数约束:其他约束条件 参数:代数模型中的常数（在数据单元格中的数字） 电子表格形式：决策变量：图中的B７和Ｃ7 目标函数：SUMＰRＯDUCT（B3:C3,Ｂ７:C7） 非负约束:B７>=0和Ｃ7>=０ 函数约束:SＵMPRODUCT(B5：C5,B7:C7) SUMＰRODＵCT(B6：C6,Ｂ7：Ｃ7) h．图解法 可见,总期望利润为6000美元 i. 线性规划图解和敏感性分析
第3次作业 一、填空题（本大题共10分，共 5 小题，每小题 2 分） 1. 最小树是 ______ 最小的树（无圈连通图）。 2. ______ 是对有些问题的机理尚未了解清楚，若能搜集到与此问题密切有关的大量数据，或通过某些试验获得 ______ ，这就可以用统计分析法建模。 3. 在运输问题的调运表中，凡能排成非学历平台形式的变量集合，称为一个闭合路，其中诸变量称为该闭回路的 ______ 4. 最小树的求解方法： ______ 和 ______ 5. 线性规划问题适合解决诸如 ______ 、 ______ 、 ______ 等 二、简答题（本大题共25分，共 5 小题，每小题 5 分） 1. 隐枚举法的基本思想 2. 模型的基本特征。 3. 线性规划适合解决哪些类型的实际问题有： ______ 、 ______ 、 ______ 4. 模型检验化的结果？ 5. 分支定界法的基本思想 三、综合分析题（本大题共45分，共 3 小题，每小题 15 分） 1. 某公司拟铺设海上油管,要求将海上六口油井连通，仅 1号油井与海岸相连， 距离为5海里。已知，海上六口油井间的距离如下表1。试问，应如何铺设油 2. 某物流中心拟选择一条从A地到F地的运输线路，可供选择路线及各点间的距离如下图；试问：应如何选择路线使总距离最短（单位运输成本为一常数，
同时也是使总成本最小）？ 3. 一网络拟铺设社区管网,要求将六栋居民楼连通，仅 1号居民楼与总线相连，距离为10公里。已知，六栋居民楼的距离如下表。试问，应如何铺设管网使铺设总长最短？ 四、论述题（本大题共20分，共 2 小题，每小题 10 分） 1. 应用《运筹学》的知识，结合自己的实际构造一案例。 2. 请结合所学的线性规划的概念特点和求解步骤，对日常生活中的某一问题进行建模分析 答案： 一、填空题（10分，共 5 题，每小题 2 分） 1. 参考答案： 权重之和 解题方案： 评分标准： 1空1分 2. 参考答案： 数据分析法大量数据
《运筹学》线性规划部分练习题 一、思考题 1.什么是线性规划模型，在模型中各系数的经济意义是什么？ 2 .线性规划问题的一般形式有何特征？ 3.建立一个实际问题的数学模型一般要几步？ 4.两个变量的线性规划问题的图解法的一般步骤是什么？ 5.求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6.什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7•试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8•试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9.在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10.大M法中，M的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问 题呢？ 11 •什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继 续第二阶段？ 二、判断下列说法是否正确。 1.线性规划问题的最优解一定在可行域的顶点达到。 2.线性规划的可行解集是凸集。 3.如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4.线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的 范围一般将扩大。 5 .线性规划问题的每一个基本解对应可行域的一个顶点。 6.如果一个线性规划问题有可行解，那么它必有最优解。 7.用单纯形法求解标准形式（求最小值）的线性规划问题时，与j' 0对应的变量都可 以被选作换入变量。 8 .单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一 个基变量的值是负的。 9.单纯形法计算中，选取最大正检验数二k对应的变量x k作为换入变量，可使目 标函数值得到最快的减少。 10 . 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形 表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1.某公司计划在三年的计划期内，有四个建设项目可以投资：项目I从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120%，每年又可以重新将所获本利纳入投资计划；项目n需要在第一年初投资，经过两年可收回本利150% , 又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目川需要在第二年年初投资，经过两年可收回本利160%，但用于该项目的最大投资额 不得超过15万元；项目"需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有 30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2.某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示： 表2—1
《运筹学》 第一章线性规划 规划问题的数学模型由三个要素组成：（1）变量（决策变量）（2）目标函数（3）约束条件 如果规划问题模型中，决策变量的取值是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则称该类规划问题的数学模型为 线性规划的数学模型。 例：将下述线性规划化为标准形式32132min x x x z +-=⎪⎪⎩ ⎪ ⎪ ⎨⎧≥≤-=++-≥+-≤++无约束321321321321,0,052327x x x x x x x x x x x x 解：令33 311 ,,x x x x x z z ''-'=-='-=' 54332100332m a x x x x x x x z ++''+'-+'=' ⎪⎪⎩ ⎪⎪⎨ ⎧≥''''=''+'--'-=-''-'+-'-=+''-'++'-0,,,,,522327543321332153321 43321 x x x x x x x x x x x x x x x x x x x x 注：4x ——松弛变量 5x ——松弛变量（剩余变量） 可行域的性质 线性规划的可行域是凸集 凸集：如果C 中任意两个点连线上的所有点也都在C 中，称C 为凸集。 线性规划的最优解在顶点上 定理1：若线性规划问题存在可行解，则问题的可行域是凸集 定理2：线性规划问题的基可行解，对应线性规划问题的可行域（凸集）的顶点 定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解 例：用单纯形法求解线性规划问题 P 3，P 4，P 5是单位矩阵，对应的基变量是 x 3，x 4，x 5 。令非基变量 x 1，x 2 等于零，即找到一个基可 ⎪⎪⎩⎪⎪ ⎨⎧≥=++=++=+-0 5 24 2615 5 5152142132x x x x x x x x x 5 43210002max x x x x x z ++++=
第 5 次课 2学时 本次课教学重点： 建立数学模型 本次课教学难点： 建立数学模型 本次课教学内容： 第四章线性规划在工商管理中的应用 第一节人力资源分配的问题 例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员? 解：设x i( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数：Min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件：s.t. x1 + x2 + x3 + x4 + x5≥28 x2 + x3 + x4 + x5 + x6≥15 x3 + x4 + x5 + x6 + x7≥24 x4 + x5 + x6 + x7 + x1≥25 x5 + x6 + x7 + x1 + x2≥19 x6 + x7 + x1 + x2 + x3≥31 x7 + x1 + x2 + x3 + x4≥28 x1,x2,x3,x4,x5,x6,x7≥0 例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？
解：设x i ( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数：Min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件：s.t. x1 + x2 + x3 + x4 + x5 ≥28 x2 + x3 + x4 + x5 + x6 ≥15 x3 + x4 + x5 + x6 + x7 ≥24 x4 + x5 + x6 + x7 + x1 ≥25 x5 + x6 + x7 + x1 + x2 ≥19 x6 + x7 + x1 + x2 + x3 ≥31 x7 + x1 + x2 + x3 + x4 ≥28 x1,x2,x3,x4,x5,x6,x7 ≥0 第二节生产计划的问题 例3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？ 解：设x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。 求x i 的利润：利润= 售价- 各成本之和 产品甲全部自制的利润=23-(3+2+3)=15 产品甲铸造外协，其余自制的利润=23-(5+2+3)=13