运筹学复习大纲
运筹学课程的知识体系
吴思杰 计算生物所
运筹学是系统工程的最重要的理论基础之一。运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”故有人称之为最优化技术。运筹学在工商管理中的应用涉及几个方面：生产计划，运输问题，人事管理，库存管理，市场营销，财务和会计，另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。
运筹学的具体内容包括：规划论（包括线性规划、非线性规划、整数规划和动态规划）、图论、决策论、对策论、排队论、存储论、可靠性理论等。
对于规划问题，来源于生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益。当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大.）规划问题数学模型有三个要素:1.决策变量，2.目标函数，3.约束条件。接下来将介绍规划论中的线性规划、非线性规划、整数规划和动态规划。
线性规划
线性规划：
运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。
线性规划的特征：
（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；
（2）问题的约束条件是一组多个决策变量的线性不等式或等式。
线性回归的数学模型：
线性规划问题的求解方法：
1）图 解 法:两个变量、直角坐标 个变量、立体坐标。其优点：只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。缺点是只适用于两个变量。
2）单纯形法：适用于任意变量、但必需将一般形式变成标准形式
线性规划问题的标准形式：
)21(j 0 )21(i )( Z (min) max 1
1n x m b x a x c j n j i j ij n j j
j ?=≥?=≥?=≤=∑
∑==
特点：
(1) 目标函数求最大值（有时求最小值）
(2) 约束条件都为等式方程，且右端常数项b i 都大于或等于零
(3) 决策变量x j 为非负。
具体步骤：
(1)将问题化为标准型，加入松驰变量x 3、x 4则标准型为:
(2)求出线性规划的初始基可行解，列出初始单纯形表。
(3)进行最优性检验：如果表中所有检验数 ，
则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。
(4)从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表
确定换入基的变量。选择
，对应的变量x j 作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：
，其对应的x k 作为换入变量。
确定换出变量。根据下式计算并选择θ ，选最小的θ对应基变量作为换出变量。 用换入变量xk 替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。
(5)重复(3)、(4)步直到计算结束为止。
单纯形法的进一步讨论：人工变量法：通过引入人工变量获得初始可行基。
解的判别：
(1)唯一最优解判别：最优表中所有非基变量的检验数非零,则线 规划具有唯一最优解。
(2)多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。
(3)无界解判别：某个λk >0且a ik ≤０（i =1，2,…,m ）则线性规划具有无界解。
(4)无可行解的判断：当用大M 单纯形法计算得到最优解并且存在Ri >0时，则表明原线性规划无可行解。
(5)退化解的判别：存在某个基变量为零的基本可行解。
3）对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。 对偶单纯形法基本思路：
找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断X B 是否可行（X B 为非负），若否，通过变换基解，直到找到原问题基可行解（即X B 为非负），这时原问题与对偶问题同时达到可行解，则可得最优解。
线性规划的限制：
一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。
(1)要求解问题的目标函数能用数值指标来反映，且为线性函数。
(2)存在着多种方案。
(3)要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。 m i n j x b x a t s x c Z j n j i j ij n
j j
j ,,2,1,,2,1,0.max 11 =?????=≥==∑∑==0≤j σ}0|max{>=j j k σσσ0>j σ?
?????>=θ0min ik ik i L a a b
线性规划在管理中的应用：
人力资源分配问题，生产计划问题，套裁下料问题，配料问题。
运输规划问题
运输问题:
在经济建设中，经常碰到大宗物资调运问题。如煤，钢铁，木材，粮食等物资，在全国有若干个生产基地，根据已有的交通网，应如何制订调运方案，将这些物质运到各消费地点，而总运费最小。这一类问题的属于特殊的线性规划问题，它们的约束方程组的系数矩阵具有特殊的结构，具有比单纯形法更为简便的求解方法。
运输规划问题的数学模型:
A 1、 A 2、…、 A m 表示某物资的m 个产地；
B 1、B 2、…、B n 表示某物质的n 个销地；a i 表示产地A i 的产量； b j 表示销地B j 的销量； c ij 表示把物资从产地A i 运往销地B j 的单位运价。设 x ij 为从产地A i 运往销地B j 的运输量，得到下列一般运输量问题的模型：
变化：
(1)有时目标函数求最大。如求利润最大或营业额最大等；
(2)当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)；
(3)产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。
运输问题求解方法：
运输问题属于特殊的线性规划问题，它们的约束方程组的系数矩阵具有特殊的结构，具有比单纯形法更为简便的求解方法：表上作业法。表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。
表上作业法计算中的问题：
∑∑===m i n j ij ij x c z 11
min ?????????==≥====∑∑==n j m i x n
j b x m i a x t s ij j m i ij n j i ij ,,1;,,1,0,,1,,1.11
(1)若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取σij <0中最小者对应的变量为换入变量。
(2)无穷多最优解：产销平衡的运输问题必定存最优解。如果非基变量的σij ＝0，则该问题有无穷多最优解。
运输问题的应用：
生产与储存问题，产销不平衡的运输问题
目标规划
目标规划：
目标规划是在线性规划的基础上，为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支。由于现代化企业内专业分工越来越细，组织机构日益复杂，为了统一协调企业各部门围绕一个整体的目标工作，产生了目标管理这种先进的管理技术。目标规划是实行目标管理的有效工具，它根据企业制定的经营目标以及这些目标的轻重缓急次序，考虑现有资源情况，分析如何达到规定目标或从总体上离规定目标的差距为最小。
线性规划模型相比于目标规划存在的局限性：
(1)要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。
(2)只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。
(3)线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。
(4)线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。
因此，针对这种缺陷，在应对目标规划问题中，进行如下改善：
(1)设置偏差变量，用来表明实际值同目标值之间的差异。
d +——超出目标的偏差，称正偏差变量
d -——未达到目标的偏差，称负偏差变量
正负偏差变量两者必有一个为0。
当实际值超出目标值时： d+>0, d-=0;
当实际值未达到目标值时： d+=0, d->0;
当实际值同目标值恰好一致时： d+=0, d-=0;
故恒有d+×d-=0
(2)统一处理目标和约束。
对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。
对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。
若希望甲的产量不低于乙的产量，即不希望d ->0,用目标约束可表为:
若希望甲的产量低于乙的产量，即不希望d ＋>0,用目标约束可表为:
若希望甲的产量恰好等于乙的产量，即不希望d ＋>0,也不希望d ->0用目标约束可表为:
?????=-+-+--0}min{21d d x x d ?????=-+-+-+0
}min{21d d x x d ??
???=-+-++--+0}min{21d d x x d d
(3)目标的优先级与权系数
在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P 1,P 2,…表示。对于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。
目标规划数学模型：
其中：g k 为第k 个目标约束的预期目标值， 和
为p l 优先因子对应各目标的权系数。
目标规划求解方法：
1）图解法：
图解法适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。
图解法解题步骤：
(1)将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）的直线方程分别标示于坐标平面上。
(2)确定系统约束的可行域。
(3)在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向
(4)求满足最高优先等级目标的解
(5)转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解
(6)重复(5)，直到所有优先等级的目标都已审查完毕为止
(7)确定最优解和满意解。
2）单纯形法
整数规划
整数规划：
在前面讨论的线性规划问题中，有些最优解可能是分数或者小数，对对于某些具体的问题，常要求解答必须是整数的情形。例如，所求解是机器的台数，完成工作的人数或者装货的车数等。这类问题需要将决策变量限制为整数规划。
要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余???????????=≥=≥=≥=≤==-++=-+==+-==++--∑
∑∑∑)2.1( 0 .n)1.2(j 0)2.1( ).()2.1(
)(min 1
111
K k d d x m i b x a K k g d d x c d d P Z k k j n j i j ij n j k k k j kj L l K k k lk k lk l ωω-lk ω+lk ω
下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。
整数线性规划数学模型：
整数线性规划问题的种类：
1）纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。
2）混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。
3）0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。
整数规划问题的求解方法：
分支定界法和割平面法
分支定界法的解题步骤：
(1)求整数规划的松弛问题最优解；
若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步；
(2)分支与定界：
任意选一个非整数解的变量x i ，在松弛问题中加上约束：
x i ≤[x i ] 和 x i ≥[x i ]+1
组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。
检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max ）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝，再检查，直到得到最优解。
整数规划问题的应用：
指派问题：
在生活中经常遇到这样的问题，某单位需要完成n 项任务，恰好有n 个人可承担这些任务。由于每人的专长不同，各人完成任务不同，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n 项任务的总效率最高，这类问题称为指派问题。
指派问题的数学模型的标准形式：
设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i 个人去做第j 件工作的效率（ 时间或费用）为C ij (i=1.2…n;j=1.2…n)并假设C ij ≥0。问应如何分配才能使总效率（ 时间或费用）最高？
设决策变量 指派问题的数学模型为：
?????=≥===∑
∑==且部分或全部为整数 n)1.2(j 0)2.1(
)min 或(max 11
j n
j i j ij n j j j x m i b x a x c Z Z ),...,2,1,(件事j 个人做第i 不指派第0件事j 个人做第i 指派第1n j i x ij =?
??=???????????======∑∑∑∑====)..2.1,1(或0取)..2.1(
1)..2.1(
1min 1
1
11n j i x n j x n i x x c Z ij n
i ij n j ij n i n j ij
ij
指派问题的求解方法：
匈牙利法
克尼格定理 :
如果从分配问题效率矩阵[a ij]的每一行元素中分别减去(或加上)一个常数u i，从每一列中分别减去(或加上)一个常数v j，得到一个新的效率矩阵[b ij]，则以[b ij]为效率矩阵的分配问题与以[a ij]为效率矩阵的分配问题具有相同的最优解。
指派问题的求解步骤：
1) 变换指派问题的系数矩阵(cij)为(bij)，使在(bij)的各行各列中都出现0元素，即
a.从(cij)的每行元素都减去该行的最小元素；
b.再从所得新系数矩阵的每列元素中减去该列的最小元素
2) 进行试指派，以寻求最优解。
在(b ij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(x ij)中的元素为1，其余为0，这就得到最优解。
找独立0元素，常用的步骤为：
从只有一个0元素的行开始，给该行中的0元素加圈，记作◎。然后划去◎所在列的其它0元素，记作?；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。
从只有一个0元素的列开始（画?的不计在内），给该列中的0元素加圈，记作◎；然后划去◎所在行的0元素，记作?，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。
若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，比较这行各0元素所在列中0元素的数目，选择0元素少这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。
若◎元素的数目m 等于矩阵的阶数n（即：m＝n），那么这指派问题的最优解已得到。若m < n, 则转入下一步。
3) 用最少的直线通过所有0元素。其方法：
对没有◎的行打“√”；
对已打“√”的行中所有含?元素的列打“√”；
再对打有“√”的列中含◎元素的行打“√”；
重复①、②直到得不出新的打√号的行、列为止；
对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。
4) 变换矩阵(b ij)以增加0元素
在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第2步。
匈牙利法的条件是：模型求最小值、效率c ij≥0。
当遇到各种非标准形式的指派问题时，处理方法是先将其转化为标准形式，然后用匈牙利法来求解。
指派问题的延伸应用：
1）大化指派问题
处理方法：设m为最大化指派问题系数矩阵C中最大元素。令矩阵B＝（m-c ij）nn则以B为系数矩阵的最小化指派问题和原问题有相同的最优解。
2）不平衡的指派问题
当人数m大于工作数n时，加上m－n项虚拟工作.
当人数m小于工作数n时，加上n－m个人
3）一个人可做几件事的指派问题
若某人可做几件事，则将该人化作相同的几个“人”来接受指派，且费用系数取值相同。4）某事一定不能由某人做的指派问题
将该人做此事的效率系数取做足够大的数，可用M表示。
非线性规划
非线性规划：
非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。在科学管理中，很多实际问题其目标函数或约束条件很难用线性函数表达。如果目标函数或约束条件中含有非线性函数，就称这种规划问题为非线性规划问题。由于非线性规划问题的复杂性，非线性规划目前还没有适于各种问题的一般算法，各个方法有自己特定的适用范围。
非线性规划的一般数学模型：
min f(x)
s.t. g i(x)≥0i＝1,…,m
h j(x)＝0 j＝1,…,p
其中x＝(x1，…,x n)属于定义域D，
非线性规划的求解方法：
1）一维最优化方法：
指寻求一元函数在某区间上的最优值点的方法。这类方法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最优化方法有黄金分割法、切线法和插值法。
①黄金分割法又称 0.618法。它适用于单峰函数。其基本思想是：在初始寻查区间中设计一列点，通过逐次比较其函数值，逐步缩小寻查区间，以得出近似最优值点。
②切线法又称牛顿法。它也是针对单峰函数的。其基本思想是：在一个猜测点附近将目标函数的导函数线性化，用此线性函数的零点作为新的猜测点，逐步迭代去逼近最优点。
③插值法又称多项式逼近法。其基本思想是用多项式（通常用二次或三次多项式）去拟合目标函数。
此外，还有斐波那契法、割线法、有理插值法、分批搜索法等。
2）无约束最优化方法：
指寻求n元实函数f在整个n维向量空间R n上的最优值点的方法。这类方法的意义在于：虽然实用规划问题大多是有约束的，但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解。
无约束最优化方法大多是逐次一维搜索的迭代算法。这类迭代算法可分为两类。一类需
要用目标函数的导函数,称为解析法。另一类不涉及导数，只用到函数值,称为直接法。这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向,沿这个方向进行一维寻查,得出新的近似点。然后对新点施行同样手续，如此反复迭代，直到满足预定的精度要求为止。根据搜索方向的取法不同，可以有各种算法。属于解析型的算法有：①梯度法：又称最速下降法。这是早期的解析法，收敛速度较慢。②牛顿法：收敛速度快，但不稳定，计算也较困难。③共轭梯度法：收敛较快，效果较好。④变尺度法：这是一类效率较高的方法。其中达维登-弗莱彻-鲍威尔变尺度法，简称 DFP法，是最常用的方法。属于直接型的算法有交替方向法（又称坐标轮换法）、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等。
3）约束最优化方法：
常用的约束最优化方法有 4种。①拉格朗日乘子法：它是将原问题转化为求拉格朗日函数的驻点。②制约函数法：又称系列无约束最小化方法，简称SUMT法。它又分两类，一类叫惩罚函数法，或称外点法；另一类叫障碍函数法，或称内点法。它们都是将原问题转化为一系列无约束问题来求解。③可行方向法：这是一类通过逐次选取可行下降方向去逼近最优点的迭代算法。如佐坦迪克法、弗兰克－沃尔夫法、投影梯度法和简约梯度法都属于此类算法。④近似型算法：这类算法包括序贯线性规划法和序贯二次规划法。前者将原问题化为一系列线性规划问题求解，后者将原问题化为一系列二次规划问题求解。
非线性规划特殊情况:
凸规划，二次规划，几何规划
1）凸规划：这是一类特殊的非线性规划。在前述非线性规划数学模型中，若f是凸函数，诸gi都是凹函数,诸hj都是一次函数，则称之为凸规划。所谓f是凸函数,是指f有如下性质：它的定义域是凸集,且对于定义域中任意两点x和y及任一小于1的正数α，下式都成立：
f((1-α)x +αy)α≤(1-α)f(x)+αf(y)
将上述不等式中的不等号反向即得凹函数的定义。所谓凸集，是指具有如下性质的集合：连结集合中任意两点的直线段上的点全部属于该集合。
对于一般的非线性规划问题，局部解不一定是整体解。但凸规划的局部解必为整体解，而且凸规划的可行集和最优解集都是凸集。
2）二次规划一类特殊的非线性规划。它的目标函数是二次函数，约束条件是线性的。求解二次规划的方法很多。较简便易行的是沃尔夫法。它是依据库恩－塔克条件，在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、毕尔法、凯勒法等。
3）几何规划一类特殊的非线性规划。它的目标函数和约束函数都是正定多项式（或称正项式）。几何规划本身一般不是凸规划，但经适当变量替换，即可变为凸规划。几何规划的局部最优解必为整体最优解。求解几何规划的方法有两类。一类是通过对偶规划去求解；另一类是直接求解原规划，这类算法大多建立在根据几何不等式将多项式转化为单项式的思想上。
动态规划
动态规划：
动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。
1、阶段：
把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。
2、状态：表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态，描述过程状态的变量称为状态变量s k 。
3、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。
4、多阶段决策过程：无后效性(马尔可夫性)
5、策略：是一个按顺序排列的决策组成的集合。
6、指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为指标函数。 动态规划方法：
1、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。
2、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的.
3、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。
最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。”也就是说，一个最优策略的子策略也是最优的。
动态规划解决方法：
逆推法，顺推法
动态规划应用：
资源分配问题，生产与存储问题，背包问题，复合系统工作可靠性问题，排序问题，设备更新问题，货郎担问题。
图与网络优化
图论：
图论是应用十分广泛的运筹学分支，它已经广泛地应用在物理学，化学，控制论，信息论，科学管理，电子计算机等各个领域。在实际生活，生产和科学研究中，有很多问题可以用图论的理论和方法来解决。例如，在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快友好。通讯网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。
图论中图是由点和边构成，可以反映一些对象之间的关系。
一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。
图的定义：
若用点表示研究的对象，用边表示这些对象之间的联系，则图G 可以定义为点和边的集
合，记作：
其中: V ——点集 E ——边集 },{E V G
树：无圈的连通图即为树。
性质1：任何树中必存在次为1的点。
性质2：n 个顶点的树必有n-1 条边。
性质3：树中任意两个顶点之间，恰有且仅有一条链。
性质4：树连通，但去掉任一条边，必变为不连通。
性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。
图的最小支撑树：
如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。
求树的方法：破圈法和避圈法
赋权图中求最小树的方法：破圈法和避圈法
图与网络分析应用：
1）最短路问题：
就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 .
有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。 求最短路有两种算法:
逐次逼近算法
狄克斯屈拉(Dijkstra)标号算法：
狄克斯屈拉(Dijkstra)标号算法的基本思路：
若序列{ v s ,v 1…..v n-1,v n }是从v s 到v t 间的最短路，则序列{ v s ,v 1…..v n-1 } 必为从v s 到v n-1的最短路。
步骤：
求网络图的最短路，设图的起点是v s ,终点是v t ,以v i 为起点v j 为终点的弧记为 (i, j) 距离为d ij
P 标号(点标号)：b (j) —起点v s 到点v j 的最短路长；
T 标号(边标号)： k(i,j )=b (i )+d ij ，
1. 令起点的标号；b (s )＝0。
2. 找出所有v i 已标号v j 未标号的弧集合 B={(i , j )} 如果这样的弧不存在或v t 已标号则计算结束；
3. 计算集合B 中弧k (i ，j )=b (i )+d ij 的标号
4. 选一个点标号 在终点v l 处标号b(l), 返回到第2步。
算法适用条件：
Dijkstra 算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。
2）网络最大流问题：
许多系统包含了流量问题。例如，公路系统中有车辆流，控制系统中有信息流，供水系{}
,),(|),(min )(B j i j i k l b j
∈=
统中有水流，金融系统中有现金流等。对于这些问题，需要求解其网络的最大流。 网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。
（1）容量网络：队网络上的每条弧(v i ,v j )都给出一个最大的通过能力，称为该弧的容量，简记为c ij 。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。
（2）网络的最大流
是指网络中从发点到收点之间允许通过的最大流量。
（3）流与可行流
流是指加在网络各条弧上的实际流量，对加在弧(v i ,v j )上的负载量记为f ij 。若f ij =0，称为零流。
（4）增广链
在网络的发点和收点之间能找到一条链，在该链上所有指向为s →t 的弧，称为前向弧，
记作μ+,存在f
（5）截量与截集
截是指容量网络中的发点和收点分割开，并使s →t 的流中断的一组弧的集合。截容量是组成割集合中的各条弧的容量之和，用 表示。
定理2 在网络中s →t 的最大流量等于它的最小割集的容量，
即： v ＊ (f ) = c ＊(V, V ′)
定理3 网络N 中的流 f 是最大流当且仅当N 中不包含任何增广链
网络最大流问题求解方法：
网络最大流的标号算法
基本思想：
由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。
基本方法：
(1)找出第一个可行流，（例如所有弧的流量f ij =0。）
(2)用标号的方法找一条增广链：
a.首先给发点s 标号(∞),标号中的数字表示允许的最大调整量。
b.选择一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：
如果弧的起点为vi ，并且有fij 如果弧的方向指向vi ，并且有fji>0，则vj 标号(fji) (3)重复第(2)步，可能出现两种结局： 标号过程中断，t 无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V,未标号的点集合为V ′,(V,V ′)为网络的最小割。 t 得到标号，反向追踪在网络中找到一条从s 到t 得由标号点及相应的弧连接而成的增广链。继续第(4)步 (4)修改流量。 (5)擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何增广链，计算结束。 ∑ ∈=),(),(),(),(V V j i j i v v c V V c 皮革厂租用厂库安排 刘梦瑶 12211222 一、研究目的及问题表述 （一）研究目的：在生活中，厂商通常面临货物存储问题，有时便需要租借仓库进行货物存储，而租金也会随着租借时间的长短而有所改变。这时我们就可以运用运筹学算出最优的租借方案，使租金最小，减少存储成本。 （二）1、问题表述：广东黄埔区的某皮革代理商需要寻租可存储采购到的皮革的仓库，并在广州58同城网上找到了位于黄埔区中心地带的具有6000平方米的高标准仓库。出租商原定价1.2元/平方米/天，后经协商，双方同意如下：租期为两个月可打九折，3个月打八折，4个月打七折，5个月打6.5折。 2、皮革代理商根据经验预测租赁期间所需仓库大小，其预测结果如下： 第一个月2000平方米；第二个月3000平方米 第三个月2500平方米；第四个月3500平方米 第五个月1600平方米 将租赁合同设为每月初办理，每月签订合同份数不限，每份所选租期不限。 求租金最小。 3、将各方条件汇表如下 （三）数据来源：在58同城网上找到相关的仓库租赁信息，其中发现位于黄埔区中心地带，107国道旁有高标准仓库招租，并标明其有6000平方米的仓库可供出租，1.2元/平方米/天。经过在网上联系该出租商，了解到其出租价格为按天数算的短期出租，若存储时间长，可另外折扣。于是我便假定租期为两个月可打九折，3个月打八折，4个月打七折，5个月打6.5折。而由于能力有限，尚未查出有公司或厂商具体需要租借仓库并有具体租借时长与租借大小的数据资料，于是按照课本题目例子，假定了如上的皮革代理商与其的租借要求。 二、方法选择及结果分析 （一）方法选择：该问题的目标能为求租金最小，可用线性函数描述该目标的要求，且有多个方案可选。达到目标具有一定的约束条件，且这些条件可用 第一章线性规划1、 由图可得：最优解为 2、用图解法求解线性规划： Min z=2x1+x2 ? ? ? ? ? ? ? ≥ ≤ ≤ ≥ + ≤ + - 10 5 8 24 4 2 1 2 1 2 1 x x x x x x 解： 由图可得：最优解x=1.6,y=6.4 Max z=5x 1+6x 2 ? ?? ??≥≤+-≥-0 ,23222212 121x x x x x x 解： 由图可得：最优解Max z=5x 1+6x 2, Max z= + ∞ Maxz = 2x 1 +x 2 ????? ? ?≥≤+≤+≤0,5242261552121211x x x x x x x 由图可得：最大值?????==+35121x x x ， 所以?????==2 3 21x x max Z = 8. 12 12125.max 2328416412 0,1,2maxZ .j Z x x x x x x x j =+?+≤? ≤?? ≤??≥=?如图所示，在（4，2）这一点达到最大值为2 6将线性规划模型化成标准形式： Min z=x 1-2x 2+3x 3 ????? ??≥≥-=++-≥+-≤++无约束 321 321321321,0,05232 7x x x x x x x x x x x x 解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中x 3’≥ 0,x 3’’≥0 Max z ’=-x 1+2x 2-3x 3’+3x 3’’ ????? ? ?≥≥≥≥≥≥-=++-=--+-=+-++0 ,0,0'',0',0,05 232 '''7'''543321 3215332143321x x x x x x x x x x x x x x x x x x x 1. 用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还 是 无可行解。 max Z = X i + X 2 6x i +10x 2 "20 * 5兰x 1兰10 【3乞X 2乞8 惟一最优解 最优点(10, 6)最优值Z 二16 戸 5 si = 10 / 2. 将下述线性规划问题化成标准形式。 min Z = -3x ^ 4X 2 - 2x ^ 5x 4 M x 1 - x 2 + 2x 3 - X 4 = -2 为中 X 2 — X3 + 2x 4 兰 14 （1） j - 2x 1 + 3x 2 + X 3 - X 4 A 2 1x1, x2, x3 H 0,x4无约束 解：令 z' = —Z ，X 4 =X 4 — x ； max z^ 3X ] - 4x ^ 2X 3 - 5x 4 5x 4 [—4X ] + X 2 - 2X 3 + x 4 - x ； = 2 j X ] + X 2 - X 3 + 2x 4 - 2x 4 十 X 5 = 14 |- 2x 1 + 3x 2 + X 3 - X 4 + x 4 - X e = 2 _X 1，X 2，X 3，X 4，X 4，X 5，X 6 k 0 3. 分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应 、 、 1 、 1 ^2=? 0X|+1O Z 2-12O 护 ____________ 寸 v/ max Li 10 图解法中的可行域的哪个顶点。 max =10x 2014年4月高等教育自学考试 运筹学基础试题 课程代码：02375 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题1分，共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.线性规划单纯形法求解时，若约束条件是小于或等于(≤)不等式，则应当在每个不等式中引入一个 A.基变量 B.非基变量 C.松弛变量 D.剩余变量 2.对于供求不平衡的运输问题，若需求量大于供应量，为了转化为供求平衡的运输问题，我们往往虚设一个 A.供应点 B.需求点 C.仓库 D.运输渠道 3.对计划项目进行核算、评价，然后选定最优计划方案的技术，称为 A.网络计划技术 B.计划评核术 C.关键路线法 D.单纯形法 4.在网络图中，两个活动之间的交接点，称之为 A.线路 B.结点(事项) C.活动 D.流量 5.网络图中，正常条件下完成一项活动可能性最大的时间，称为 A.作业时间 B.最乐观时间 C.最保守时间 D.最可能时间 6.在一个网络中，根据问题的需要，我们可以在图的点旁或边旁标上数，这个数也可称之为 A.树 B.杈 C.枝叉 D.最小枝叉树 7.单纯形法作为一种简单解法，常用于求解线性规划的 A.多变量模型 B.两变量模型 C.最大化模型 D.最小化模型 8.对科学发展趋势的预测属于 A.微观经济预测 B.宏观经济预测 C.科技预测 D.社会预测 9.在固定成本中，由所提供的生产能力所决定的费用，称之为 A.总成本 B.可变成本 C.预付成本 D.计划成本 10.每一个随机变量和相关的某个范围内累计频率序列数相应，这个累计频率数称之为 A.随机数 B.随机数分布 C.离散的随机变量 D.连续的随机变量 11.在接受咨询的专家之间组成一个小组，面对面地进行讨论与磋商，最后对需要预测的课题得出比较一致的意见，这种定性预测方法是 A.指数平滑预测法 B.回归模型预测法 C.专家小组法 D.特尔斐法 12.风险条件下的决策是 A.存在一个以上的自然状态，但决策者具有提供将概率值分配到每个可能状态的信息 B.决策者知道所面对的部分自然状态 C.决策者面对的只有一种自然状态，即关于未来的状态是完全确定的 D.决策者所面对的是，存在一个以上的自然状态，而决策者不了解其它状态，甚至不完全了解如何把概率(可能性)分配给自然状态 学习运筹学的总结与心得体会古人云“夫运筹帷幄之中，决胜千里之外”，怀着对运筹学的憧憬与崇拜之情，这学期我选择了运筹学这门课程。通过学习，我知道了运筹学是一门具有多科学交叉特点的边缘科学，是一门以数学为主要工具，寻求各种问题最优方案的优化学科。 经过一个学期的学习，我们应该熟练地掌握、运用运筹学的精髓，用运筹学的思维思考问题，即：应用分析、试验、量化的方法，对实际生活中的人力、财力、物力等有限资源进行合理的统筹安排。本着这样的心态，在本学期运筹学课程将结束之际，我对本学期所学知识作出如下总结。 一、线性规划 线性规划解决的是：在资源有限的条件下，为达到预期目标最优，而寻找资源消耗最少的方案。而线性规划问题指的是在一组线性等式或不等式的约束下，求解一个线性函数的最大或最小值的问题。其数学模型有目标函数和约束条件组成。 解决线性规划问题的关键是找出他的目标函数和约束方程，并将它们转化为标准形式。解决线性规划问题的主要方法有：图解法、单纯型法、两阶段法、对偶单纯型法、计算机软件求解等方法。简单的设计2个变量的线性规划问题可以直接运用图解法得到。但是往往在现实生活中，线性规划问题涉及到的变量很多，很难用作图法实现，但是运用单纯形法记比较方便。单纯形法的发展很成熟应用也很广泛，在运用单纯形法时，需要先将问题化为标准形式，求出基可行解，列出单纯形表，进行单纯形迭代，当所有的变量检验数不大于零，且基变量中不含人工变量，计算结束。将所得的量的值代入目标函数，得出最优值。 利用单纯形表我们可以（1）直接找出基本可行解与对应的目标函数值；（2）通过检验数判断原问题解的性质以及是否为最优解。 每一个线性规划问题都有和它伴随的另一个问题，若一个问题称为原问题，则另一个称为其对偶问题，原问题和对偶问题有着非常密切的关系，以至于可以根据一个问题的最优解，得出另一个问题的最优解的全部信息。 对偶问题有：对称形式下的对偶问题和非对称形式下的对偶问题。非对称形式下的对偶问题需要将原问题变形为标准形式，然后找出标准形式的对偶问题。因为对偶问题存在特殊的基本性质，所以我们在解决实际问题比较困难时可以将其转化成其对偶问题进行求解。 在解决线性规划问题时，我们往往会在求出最优解后，对问题进行灵敏度分 全国2013年4月高等教育自学考试 运筹学基础试题 课程代码：02375 一、单项选择题(本大题共15小题，每小题1分，共15分) 1．必须运用定性和定量两种方法才能制定的决策，称为 A.多阶段决策 B.多元决策 C.混合性决策 D.满意决策 2．根据历史数据和资料，应用数理统计方法来预测事物的未来，或者利用事物发展的因果关系来预测事物的未来，属于（） A.经济预测 B.科技预测 C.定性预测 D.定量预测 3．专家小组法适用于 A.长期预测 B.中期预测 C.短期预测 D.定量预测 4．符合下列条件的决策：（1）有一个明确的决策目标；（2）存在多个（两个以上）可行方案；（3）存在多个不以人们主观意志为转移的自然状态，并且每个自然状态可以估算出它的概率值；（4）不同可行方案在不同状态下的收益值或损失值可以定量计算出来。这种决策类型属于 A.确定条件下决策 B.风险条件下决策 C.不确定条件下决策 D.乐观条件下决策 5．根据库存管理理论，约占全部存货单元数的60%，但它们的年度需用价值却只占该企业全部存货年度需用价值的10%，这类存货单元称为 A.A类存货单元 B.B类存货单元 C.C类存货单元 D.主要存货单元 6．线性规划模型结构中，实际系统或决策问题中有待确定的未知因素，称之为 A.变量 B.目标函数 C.约束条件 D.线性函数 7．图解法中，可行解区内满足目标函数的解称之为 A.可行解 B.基础解 C.最优解 D.特解 8．线性规划单纯形法求解时，若约束条件是等于或大于某确定数值，则应当在每个不等式中引入一个 A.基变量 B.非基变量 C.松驰变量 D.剩余变量 9.对于供求平衡的运输问题，表上作业法是在平衡表的基础上首先求出一个 A.供求方案 B.最终调运方案 C.初始调运方案 D.最优调运方案 10.在计划项目的各项错综复杂的工作中，抓住其中的关键活动进行计划安排的方法，称之为 A.网络计划技术 B.计划评核术 C.关键路线法 D.单纯形法 11.从网络的始点开始，顺着箭线的方向，到达网络终点的一条连线，称之为 A.线路 B.作业 C.活动 D.流向 12.在图论中，表示对象之间的某种特定的关系，通常 A.用线表示 B.用点表示 C.用树表示 D.用枝叉树表示 13．马尔柯夫过程是俄国数学家马尔柯夫于 A.20世纪初发现的 B.第二次世界大战期间发现的 C.19世纪中叶发现的 D.20世纪30年代发现的14．总额随着企业产品产量的增减而变化的费用，称之为 A.固定成本 B.可变成本 C.预付成本 D.计划成本 15．如果一个随机变量允许在某个给定的范围内任意取值，则它就是一个 秋季流行服饰与衣料的准备（五人） 目从办公室的十层大楼里，凯瑟琳·拉里俯视着下面忙忙碌碌的人流，在充塞着黄色出租车的街道以及乱放着一些买热狗的摊位的人行道上，成群的纽约人来来往往，好不热闹。在这闷热的暑天里，她注视着各类女性的穿衣时尚，心里想的却是这些人在秋季将会选择怎样的款式。这并非是她的一时的灵感，而是她工作的重要的一部分因为她拥有并经营着一家妇女精品时装公司――时尚隧道（TrendLines）公司。 今天对她来说是很重要的，因为她将与生产部经理泰德·罗森碰面，一起商讨下一个月秋季生产线的生产计划，特别是在一定的生产能力的基础上确定要各种服装的生产量。制定下个月的周密的生产计划对于秋季的销售是至关重要的，因为这些产品在9 月份将会上市，而妇女们通常在服装一上市时就会购买大部分的秋天的服饰。 凯瑟琳回转身，走到宽大的玻璃台旁去看铺上面的大量的资料及设计图。她扫视着6个月以前就设计出来的服装图样，各种样式所需要的材料，以及在时装展上通过消费者调研取得的各种样式的需求预测。现在，她还记得当时是如何设汁图样并将样品在纽约，米兰和巴黎的服装展上展出，那些天可真是既兴奋而又痛苦。最后，她付给六个设计者的总酬金为$860,000。除此外，每次时装展的费用为$2,700,000，包括雇用职业模特、发型师、化妆师，以及衣服的裁制与缝纫、展台背景的设计、模特的走步与排练、会场的租用。 她研究着衣服的样式和所需的材料。秋季的服装包括职业装和休闲装，而每种服装的价格是由衣服的质量、材料的成本、人工成本、机器成本，以及对该产品的需求与品牌的知名度等因素来确定的。 她知道已经为下个月采购了下面的这些材料：羊毛45,000码、开司米28,000码、丝绸18,000码、人造纤维30,000码、天鹅绒20,000码、棉布30,000码。各种材料的价格如下图所示： 多余的材料（不包括下脚料）可以运回给衣料供应商，并得到全额的偿还。 凯瑟琳知道生产丝绸上衣和棉汗衫会产生相当的多余边料。每件丝绸上衣和每件棉汗衫分别需要2 码的丝绸和棉布，而其中分别有0.5 码的边料。她不希望浪费这些衣料，因此打算利用矩形的丝绸和棉布的边料来生产丝绸女背心和棉的迷你裙。这样，每生产一件丝绸上衣就可以生产一件丝绸女背心。同样，每生产一件棉汗衫就可以生产一件迷你裙。要注意的是，生产背心和迷你裙并不一定需要首先生产相应数量的丝绸上衣和棉汗衫。 需求的预测表明其中一些产品的需有限的。天鹅绒的裤子和衬衫因为是一时的流行，预测分别只能销售5,500 和6,000件。公司不会生产超过预计需求的产品数量，因为，一旦该式样不再流行，就很难再卖出去。并且，因为公司并不需要满足所有的需求，所以，公司可以生产少于需求数量的产品。开司米汗衫因为价格较高，预计也只能销出4,000。丝绸上衣和背心的需求也是有限的，因为很多女性认为丝绸较难护理。公司预计大约可销出12,000的丝绸上衣和15,000丝绸背心。 预测表明羊毛裤，剪裁考究的衬衫，羊毛夹克的需很大的，因为这些是职业行头的必需品。羊毛裤和羊毛夹克的需求分别为7,000和5,000。凯瑟琳认为必须满足该部分60%的需求，以保持客户的品牌忠诚度，为以后的业务考虑。尽管剪裁考究的衬衫的需无法预测的，凯瑟琳认为必须至少生产2 , 800件。 a ．泰德打算说服凯瑟琳不生产天鹅绒衬衫，因为，这种流行服装的需很少的。而它的固定设计费用和其他成本高达$ 500,000，销售该样式的净贡献（售价－材料成本－人工成本）必须能够抵消总成本，他认为，即便是满足了最大的需求，该产品也不能产生一点的利润。你认为泰德的观点如何？ 解：净贡献=6000×（200－1.5×12－160）=132000<500000 由上式得，泰德的观点正确的，因为根据软件求解的结果，最优生产计划中X10的最优解为0，因此最好不要生产天鹅绒衬衫。 运筹学课程总结 总结内容： 一、运筹学简述 （一）运筹学定义 （二）运筹学工作步骤 （三）运筹学的应用 二、运筹学相关理论与方法 （一）线性规划 （二）运输问题 （三）目标规划 （四）整数规划 （五）动态规划 三、运筹学应用案例分析（用matlab求解） 一、运筹学简述 （一）运筹学的定义 运筹学是一门应用科学，至今还没有统一且确切的定义。莫斯和金博尔曾对运筹学的定义是：“为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。”它强调科学方法，以量化为基础。 另一定义是：“运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。” 中国百科全书给出的定义是：“运筹学是用数学方法研究经济、民政和国防等部门在内外环境约束的条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案。” 如论如何定义，都表明着，运筹学是为提供最优化方法、最佳解决方案的科学。 （二）运筹学的工作步骤 1、建立数学模型：认清目标和约束； 2、寻求可行方案：求解； 3、评估各个方案：解的检验、灵敏度分析等； 4、选择最优方案：决策； 5、方案实施：回到实践中； 6、后评估：考察问题是否得到完满解决。 （三）运筹学的应用 运筹学在各个领域的应用非常广泛，主要有以下几个方面： 1、生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等； 2、库存管理：多种物资库存量的管理，库存方式、库存量等； 3、运输问题：确定最小成本的运输线路、物资的调拨、运输、工具的调度 全国2004年4月高等教育自学考试 运筹学基础试题 课程代码：02375 第一部分选择题（共15分） 一、单项选择题（更多科目请访问https://www.wendangku.net/doc/0416487710.html,/zikao.htm）（本大题共15小题， 每小题1分，共15分） 1．下列向量中的概率向量是（ A ） A．（0.1,0.4,0,0.5）B．（0.1,0.4,0.1,0.5） C．（0.6,0.4,0,0.5）D．（0.6,0.1,0.8,-0.5） 2．当企业盈亏平衡时，利润为（ C ） A．正B．负C．零D．不确定 3．记M为产品价格，V'为单件可变成本，则边际贡献等于（ B ） A．M+V'B．M-V'C．M*V'D．M/V' 4．在不确定的条件下进行决策，下列哪个条件是不必须具备的（ A ） A．确定各种自然状态可能出现的概率值B．具有一个明确的决策目标 C．可拟订出两个以上的可行方案 D．可以预测或估计出不同的可行方案在不同的自然状态下的收益值 5．下列说法正确的是（ C ） A．期望利润标准就是现实主义决策标准 B．最小最大决策标准是乐观主义者的决策标准 C．确定条件下的决策只存在一种自然状态 D．现实主义决策标准把每个可行方案在未来可能遇到最好的自然状态的概率定为1 6．下述选项中结果一般不为0的是（ D ） A．关键结点的结点时差B．关键线路的线路时差 C．始点的最早开始时间D．活动的专用时差 7．时间优化就是在人力、材料、设备、资金等资源基本上有保证的条件下，寻求最短的工程周期。下列方法中不能正确缩短工程周期的是（ D ） A．搞技术革新、缩短活动，特别是关键活动的作业时间 B．尽量采用标准件、通用件等 C．组织平行作业D．改多班制为一班制 8．一般在应用线性规划建立模型时要经过四个步骤： （1）明确问题，确定目标，列出约束因素（2）收集资料，确定模型 （3）模型求解与检验（4）优化后分析 以上四步的正确顺序是（ A ） A．（1）（2）（3）（4）B．（2）（1）（3）（4） C．（1）（2）（4）（3）D．（2）（1）（4）（3） 9．求解需求量小于供应量的运输问题不需要做的是（ D ） A．虚设一个需求点B．令供应点到虚设的需求点的单位运费为0 C．取虚设的需求点的需求量为恰当值D．删去一个供应点 10．以下各项中不属于运输问题的求解程序的是（ B ） A．分析实际问题，绘制运输图B．用单纯形法求得初始运输方案 C．计算空格的改进指数D．根据改进指数判断是否已得最优解11．若某类剧毒物品存货单元占总存货单元数的10%，其年度需用价值占全部存货年度需用价值的15%，则由ABC分析法应称该存货单元为（ A ）存货单元。 A．A类B．B类C．C类D．待定 案例四监理公司人员配置问题 某监理公司侧重于国家大中型项目的监理。每项工程安排多少监理工程师进驻工地，一般是根据工程的投资、建筑规模、使用功能、施工的形象进度、施工阶段来决定，监理工程师的配置数量随着变化。由于监理工程师从事的专业不同，他们每人承担的工作量也是不等的。有的专业一个工地就需要三人以上，而有的专业一人则可以兼管三个以上的工地。因为从事监理业的专业多达几十个，仅以高层民用建筑为例就涉及到建筑学专业、工民建（结构）专业、给水排水专业、采暖通风专业、强电专业、弱电专业、自动控制专业、技术经济专业、总图专业、合同和信息管理专业等，这就需要我们合理配置这些人力资源。为了方便计算，我们把所涉及的专业技术人员按总平均人数来计算，工程的施工形象进度按标准施工期和高峰施工期来划分。通常标准施工期需求的人数教容易确定。但高峰施工期就比较难确定了，原因有两点： （1）高峰施工期各工地不是同时来到，是可以事先预测的，在同一个城市里相距不远的工地，就存在着各工地的监理工程师如何交错使用的运筹问题。 （2）各工地总监在高峰施工期到来的时候要向公司要人，如果每个工地都按高峰施工期配置监理工程师的数量，将造成极大的人力资源浪费。 因此，为了达到高峰施工期监理工程师配置数量最优，人员合理地交错使用，遏制人为因素，根据历年来的经验对高峰施工期的监理工程师数量在合理交错发挥作用的前提下限定了范围。另经统计测得，全年平均标准施工期占7个月，人均年成本4万元；高峰施工期占5个月，人均年成本7万元。 标准施工期所需监理工程师如表1所示。 表1 另外在高峰施工期各工地所需监理工程师的数量要求如下： 第1和第2工地的总人数不少于14人； 第2和第3工地的总人数不少于13人； 第3和第4工地的总人数不少于11人； 第4和第5工地的总人数不少于10人； 第5和第6工地的总人数不少于9人； 第6和第7工地的总人数不少于7人； 第7和第1工地的总人数不少于14人。 问题： （1）高峰施工期公司最好配置多少个监理工程师 （2）监理工程师年耗费的总成本是多少 运筹学基础课后习题答案 [2002年版新教材] 第一章导论 P5 1.、区别决策中的定性分析和定量分析，试举例。 定性——经验或单凭个人的判断就可解决时，定性方法 定量——对需要解决的问题没有经验时；或者是如此重要而复杂，以致需要全面分析（如果涉及到大量的金钱或复杂的变量组）时，或者发生的问题可能是重复的和简单的，用计量过程可以节约企业的领导时间时，对这类情况就要使用这种方法。 举例：免了吧。。。 2、. 构成运筹学的科学方法论的六个步骤是哪些？ .观察待决策问题所处的环境； .分析和定义待决策的问题； .拟定模型； .选择输入资料； .提出解并验证它的合理性（注意敏感度试验）； .实施最优解； 3、．运筹学定义： 利用计划方法和有关许多学科的要求，把复杂功能关系表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供数量根据 第二章作业预测P25 1、. 为了对商品的价格作出较正确的预测，为什么必须做到定量与定性预测的结合？即使在定量预测法诸如加权移动平均数法、指数平滑预测法中，关于权数以及平滑系数的确定，是否也带有定性的成分？ 答：（1）定量预测常常为决策提供了坚实的基础，使决策者能够做到心中有数。但单靠定量预测有时会导致偏差，因为市场千变万化，影响价格的因素很多，有些因素难以预料。调查研究也会有相对局限性，原始数据不一定充分，所用的模型也往往过于简化，所以还需要定性预测，在缺少数据或社会经济环境发生剧烈变化时，就只能用定性预测了。（2）加权移动平均数法中权数的确定有定性的成分；指数平滑预测中的平滑系数的确定有定性的成分。 2.、某地区积累了5 个年度的大米销售量的实际值（见下表），试用指数平滑法，取平滑系数α= 0.9，预测第6年度的大米销售量（第一个年度的预测值，根据专家估计为4181.9千公斤） 年度 1 2 3 4 5 大米销售量实际值 （千公斤）5202 5079 3937 4453 3979 。 答： F6=a*x5+a(1-a)*x4+a(1-a)~2*x3+a(1-a)~3*x2+a(1-a)~4*F1 F6=0.9*3979+0.9*0.1*4453+0.9*0.01*3937+0.9*0.001*5079+0.9*0.0001*4181.9 1. 2. 3.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。 ?? ???≤≤≤≤≤++=8 3105120106max 21212 1x x x x x x z 2.将下述线性规划问题化成标准形式。 （1）?????? ?≥≥-++-≤+-+-=-+-+-+-=无约束 4,03,2,12321422245243min 43214 32143214 321x x x x x x x x x x x x x x x x x x x x z 解：令z z -='，' '4' 44x x x -= ???????≥=-+-++-=+-+-+=-+-+-+-+-=0,,,,,,23214 2222455243'max 6 5''4'43216' '4'43215''4'4321''4'4321' '4'4321x x x x x x x x x x x x x x x x x x x x x x x x x x x x x z 3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。 ??? ??≥≤+≤++=0,825943510max 2 121212 1x x x x x x x x z 解：①图解法： ②单纯形法：将原问题标准化： ??? ??≥=++=+++=0,,,825943510max 4213 212 1x x x x x x x x x x x x z C j 10 5 θ 对应图解法 单纯型法步骤：转化为标准线性规划问题；找到一个初始可行解，列出初始单纯型表；最优性检验，求cj-zj ，若所有的值都小于0，则表中的解便是最优解，否则，找出最大的值的那一列，求出bi/aij ，选取最小的相对应的xij ，作为换入基进行初等行变换，重复此步骤。 4.写出下列线性规划问题的对偶问题。 （1）()()()?? ???? ?????==≥===== ∑∑∑∑====n j m i x n j b x m i a x t s x c z ij j m i ij i n j ij m i n j ij ij ,,1;,,10 ,,1,,1..min 11 11 ()?????==≤++=+=+=∑∑无约束 j i ij j m i n i m j j m i i i y x n j m i c y y t s y b y a w ,,,1;,,1..max 1 1 管理运筹学lindo案例分析 ⑻Lindo的数据分析及习题 用该命令产生当前模型的灵敏性分析报告：研究当目标函数的费用系数和约束右端项在什么围（此时假定其它系数不变）时，最优基保持不变。灵敏性分析是在求解模型时作出的，因此在求解模型时灵敏性分析是激活状态，但是默认是不激活的。为了激活灵敏性分析，运行LINGO|Options…，选择General Solver Tab , 在Dual Computations 列表框中，选择Prices and Ranges 选项。灵敏性分析耗费相当多的求解时间，因此当速度很关键时，就没有必要激活它。 下面我们看一个简单的具体例子。 例5.1某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示： 用DESKS TABLES和CHAIRS分别表示三种产品的生产量，建立LP模型。 max=60*desks+30*tables+20*chairs; 8*desks+6*tables+chairs<=48; 4*desks+2*tables+1.5*chairs<=20; 2*desks+1.5*tables+.5*chairs<=8; tables<=5; 求解这个模型，并激活灵敏性分析。这时，查看报告窗口（Reports Window）,可以看到如下结果。Global optimal solution found at iteration:3 Objective value:280.0000 Variable Value Reduced Cost DESKS 2.0000000.000000 TABLES0.000000 5.000000 CHAIRS8.0000000.000000 Row Slack or Surplus Dual Price 1280.0000 1.000000 224.000000.000000 30.00000010.00000 40.00000010.00000 5 5.0000000.000000 “ Global optimal solution found at iteration: 3 ”表示 3 次迭代后得到全局最优解。 a Objective value:280.0000 ”表示最优目标值为280。“Value”给出最优解中各变量的值：造2个书桌（desks）, 0 个餐桌（tables ）, 8 个椅子（chairs ）。所以desks、chairs 是基变量（非0）, tables 是非基变量（0 ）。 “ Slack or Surplus ”给出松驰变量的值： 第1行松驰变量=280 （模型第一行表示目标函数，所以第二行对应第一个约束） 第2行松驰变量=24 第3行松驰变量=0 第4行松驰变量=0 第5行松驰变量=5 “ Reduced Cost ”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时，目 标函数的变化率。其中基变量的reduced cost 值应为0, 对于非基变量X j,相应的reduced cost 值 表示当某个变量X j 增加一个单位时目标函数减少的量（ max 型问题）。本例中：变量tables 对应的 1.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。 ?? ???≤≤≤≤≤++=8 3105120106max 21212 1x x x x x x z 2.将下述线性规划问题化成标准形式。 （1）?????? ?≥≥-++-≤+-+-=-+-+-+-=无约束 4,03,2,12321422245243min 43214 32143214 321x x x x x x x x x x x x x x x x x x x x z 解：令z z -='，' '4'44x x x -= ???????≥=-+-++-=+-+-+=-+-+-+-+-=0,,,,,,23214 2222455243'max 6 5''4'43216' '4'43215' '4'4321''4'4321' '4'4321x x x x x x x x x x x x x x x x x x x x x x x x x x x x x z 3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应 图解法中的可行域的哪个顶点。 ??? ??≥≤+≤++=0,825943510max 2 121212 1x x x x x x x x z 解：①图解法： ②单纯形法：将原问题标准化： ??? ??≥=++=+++=0,,,825943510max 4 3214213 212 1x x x x x x x x x x x x z C j 10 5 0 0 θ 对应图解法中的点 C B B b x 1 x 2 x 3 x 4 0 x 3 9 3 4 1 0 3 O 点 0 x 4 8 [5] 2 0 1 8/5 σj 0 10 5 0 0 0 x 3 21/5 0 [14/5] 1 -3/5 3/2 C 点 10 x 1 8/5 1 2/5 0 1/5 4 σj -16 0 1 0 -2 5 x 2 3/2 0 1 5/14 -3/14 B 点 10 x 1 1 1 0 -1/7 2/7 σj 35/2 -5/14 -25/14 最优解为（1,3/2,0,0），最优值Z=35/2。 2018年4月高等教育自学考试 运筹学基础试卷 课程代码：02375 请考生按规定用笔将所有试卷的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试卷卷上。 一、单项选择题(本大题共15小题，每小题1分，共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.线性规划单纯形法求解时，若约束条件是小于或等于(≤)不等式，则应当在每个不等式中引入一个 A.基变量 B.非基变量 C.松弛变量 D.剩余变量 2.对于供求不平衡的运输问题，若需求量大于供应量，为了转化为供求平衡的运输问题，我们往往虚设一个 A.供应点 B.需求点 C.仓库 D.运输渠道 3.对计划工程进行核算、评价，然后选定最优计划方案的技术，称为 A.网络计划技术 B.计划评核术 C.关键路线法 D.单纯形法 4.在网络图中，两个活动之间的交接点，称之为 A.线路 B.结点(事项) C.活动 D.流量 5.网络图中，正常条件下完成一项活动可能性最大的时间，称为 A.作业时间 B.最乐观时间 C.最保守时间 D.最可能时间 6.在一个网络中，根据问题的需要，我们可以在图的点旁或边旁标上数，这个数也可称之为 A.树 B.杈 C.枝叉 D.最小枝叉树 7.单纯形法作为一种简单解法，常用于求解线性规划的 A.多变量模型 B.两变量模型 C.最大化模型 D.最小化模型 8.对科学发展趋势的预测属于 A.微观经济预测 B.宏观经济预测 C.科技预测 D.社会预测 9.在固定成本中，由所提供的生产能力所决定的费用，称之为 A.总成本 B.可变成本 C.预付成本 D.计划成本 10.每一个随机变量和相关的某个范围内累计频率序列数相应，这个累计频率数称之为 A.随机数 B.随机数分布 C.离散的随机变量 D.连续的随机变量 11.在接受咨询的专家之间组成一个小组，面对面地进行讨论与磋商，最后对需要预测的课题得出比较一致的意见，这种定性预测方法是 A.指数平滑预测法 B.回归模型预测法 C.专家小组法 D.特尔斐法 12.风险条件下的决策是 A.存在一个以上的自然状态，但决策者具有提供将概率值分配到每个可能状态的信息 B.决策者知道所面对的部分自然状态 C.决策者面对的只有一种自然状态，即关于未来的状态是完全确定的 D.决策者所面对的是，存在一个以上的自然状态，而决策者不了解其它状态，甚至不完全了解如 武城万事达酒水批发案例分析 导言：每个企业都是为了赚取利润，想要赚取更多的利润就要想办法节约自己的成本，那怎么节约自己的成本呢？运筹学是一门用纯数学的方法来解决最优方法的选择安排的学科。运输是配送的必需条件，但是怎么才能让武城万事达酒水批发厂在运输问题是节约运输成本呢？我们就运用运筹学的方法来进行分析。我们对他原来的运输路线进行调查，计算原来需要的运输成本，对它的运输方式我们进行研究然后确定新的运输路线为他节约运输成本。 一、案例描述 武城万事达酒水批发有四个仓库存储啤酒分别为1、2、3、4,有五个销地A、B、C、D、E，各仓库的库存与各销售点的销售量（单位均为t)，以及各仓库到各销售地的单位运价（元/t）。半年中，1、2、3、4仓库中分别有300、400、500、300吨的存量，半年A、B、C、D、E五个销售地的销量分别为170、370、500、340、120吨。且从1仓库分别运往A、B、C、D、E五个销售地的单位运价分别为300、350、280、380、310元，从2仓库分别运往A、B、C、D、E五个销售地的单位运价分别310、270、390、320、340元，从3仓库分别运往A、B、C、D、E五个销售地的单位运价分别290、320、330、360、300元，从4仓库分别运往A、B、C、D、E五个销售地的单位运价分别310、340、320、350、320元。具体情况于下表所示。求产品如何调运才能使总运费最小？ 仓库 A B C D E 存量 销地 1 300 2 400 3 500 4 300 150销量170 370 500 340 120 武城万事达酒水批发原来的运输方案： E销售地的产品从1仓库供给，D销售地的产品全由2仓库供给，C销售地全由3仓库供给，A、B销售地产品全由4仓库供给。 即：产生的运输费用为Z1 Z1=310*120+320*340+330*500+340*370+310*170=489500 二、模型构建 1、决策变量的设置 设所有方案中所需销售量为决策变量X ij（i=1、2、3、4，j=A、B、C、D、E），即： 方案1：是由仓库1到销售地A的运输量X1A 方案2：是由仓库1到销售地B的运输量X1B 方案3：是由仓库1到销售地C的运输量X1C 运筹学案例 分析 指导老师： 班级： 姓名： 学号： 个人学习时间优化分配 设计总说明（摘要） 合理的安排时间方案，采取最优化的时间组合，有利于我们充分发挥各个时间阶段的学习效益。同时可以使我们的学习符合日常行为及自身特点，不仅使时间得到有效安排，也使得我们的身心得到和谐。此次，研究分配一天中四个阶段四门课程的学习时间，就是根据学生的身心特点，和各阶段对各课程学习的收获程度，采取获得程度量化的方法，设计出一个最优的时间组合方案，从而获得最大的收获效益。即获得学习的最大价值。 在这个过程中要将运筹学的各种理论知识与具体实际情况相结合。首先是确定所要研究的问题，考虑所需要的各种数据，根据实际需求确定所需要的数据和模拟量化的数据。将数据整理形成分析和解决问题的具体模型。其次对已得模型利用计算机进行求解，得出方程的最优解。最后结合所研究问题的实际背景，对模型的解进行评价、分析以及调整，并对解的实施与控制提出合理化的建议。 关键词：时间优化，线性规化，最优解，获得效益最大 目录 1．绪论 1.1研究的背景 (3) 1.2研究的主要内容与目的 (3) 1.3研究的意义 (3) 1.4研究的主要方法与思路 (3) 2．理论方法的选择 2.1 所研究的问题的特点 (4) 2.2 拟采用的运筹学理论方法的特点 (4) 2.3 理论方法的适用性及有效性论证 (5) 3．模型的建立 3.1 基础数据的确定 (5) 3.2 变量的设定 (6) 3.3目标函数的建立 (6) 3.4 限制条件的确定 (6) 3.5 模型的建立 (7) 4 .模型的求解及解的分析 4.1 模型的求解 (7) 4.2 解的分析与评价 (9) 5 .结论与建议 5.1 研究结论 (11) 5.2 建议与对策 (11) 运筹学(胡运权)第五版课后答案-运筹作业 47页1.1b 用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解47页1.1d 无界解 1 2 3 4 5 4 3 2 1 - 1 -6 -5 -4 -3 -2 X2 X1 2x1- -2x1+3x 1 2 3 4 4 3 2 1 X1 2x1+x2=2 3x1+4x2= X 1.2（b） 约束方程的系数矩阵A= 1 2 3 4 2 1 1 2 P1 P2 P3 P4 基 基解 是否可行解目标函数值X1 X2 X3 X4 P1 P2 -4 11/2 0 0 否 P1 P3 2/5 0 11/5 0 是43/5 P1 P4 -1/3 0 0 11/6 否 P2 P3 0 1/2 2 0 是 5 P2 P4 0 -1/2 0 2 否 P3 P4 0 0 1 1 是 5 最优解A=(0 1/2 2 0)T和(0 0 1 1)T 49页13题 设Xij为第i月租j个月的面积 minz=2800x11+2800x21+2800x31+2800x41+4500x12+4500x22+4500x32+6000x1 3 +6000x23+7300x14 s.t. x11+x12+x13+x14≥15 x12+x13+x14+x21+x22+x23≥10 x13+x14+x22+x23+x31+x32≥20 x14+x23+x32+x41≥12 Xij≥0 用excel求解为： ( ) 用LINDO求解： LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION V ALUE运筹学案例分析
《运筹学》课后习题答案
大学运筹学课程知识点总结
运筹学基础
(完整版)学习运筹学的体会与心得
高等教育自学考试运筹学基础习题汇总
《管理运筹学》案例分析报告模版
运筹学课程总结
运筹学基础历年考题汇总
运筹学案例分析题
运筹学基础课后习题答案
大学运筹学课程知识点总结
管理运筹学lindo案例分析报告
大学运筹学课程知识点总结
运筹学基础
运筹学案例分析报告文案
运筹学案例分析
运筹学(胡运权)第五版课后答案-运筹作业