运筹学复习手册

运筹学复习一、填空题1、线性规划中，满足非负条件的基本解称为基本可行解，对应的基称为可行基线.2、性规划的目标函数的系数是其对偶问题的右端常数；而若线性规划为最大化问题，则3、对偶问题为最小化问题。

m n个变量构成基变量的充要条件是不含闭回路。

4、在运输问题模型中，15、动态规划方法的步骤可以总结为：逆序求解最优目标函数，顺序求__最优策略、最优路线和最优目标函数值。

6、工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；7、对不定步数问题，用迭代法求解，有函数迭代法和策略迭代法两种方法。

8、在图论方法中，通常用点表示人们研究的对象，用边表示对象之间的某种联系。

9、一个无圈且连通的图称为树。

10、图解法提供了求解只含有两个决策变量的线性规划问题的方法．11、图解法求解生产成本最小线性规划问题时，等成本线越往左下角移动，成本越低．12、如果线性规划问题有有限最优解，则该最优解一定在可行域的边界上上达到。

13、线性规划中，任何基对应的决策变量称为基变量．14、原问题与对偶问题是相互对应的．线性规划中，对偶问题的对偶问题是原问题．15、在线性规划问题中，若某种资源的影子价格为10，则适当增加该资源量，企业的收益将_会 (“会”或“不会”)提高．16、表上作业法实质上就是求解运输问题的单纯形法．17、产销平衡运输问题的基变量共有m+n-1个．18、动态规划不仅可以用来解决和时间有关的多阶段决策问题，也可以处理与时间无关的多阶段决策问题．19、构成动态规划模型，需要进行以下几方面的工作：正确选择阶段（k）变量，正确选择状态（Sk）变量，正确选择_ 决策（UK）变量，列出状态转移方程, 列出_阶段指标函数_，建立函数基本方程．20、动态规划方法可以用来解决和某些与时间有关的问题，但也可以用来解决和某些与时间无关的问题.在图论方法中，图是指由点与边和点与弧组成的示意图．21、网络最短路径是指从网络起点至终点的一条权之和最小的路线．简述单纯形法的计算步骤：第一步：找出初始可行解，建立初始单纯形表。

《运筹学》课程复习资料一、判断题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

[ ]2.线性规划问题的每一个基本解对应可行解域的一个顶点。

[ ]3.任何线性规划问题存在并具有惟一的对偶问题。

[ ]4.已知y i*为线性规划的对偶问题的最优解，若y i*＞0，说明在最优生产计划中第i种资源已完全耗尽。

[ ] 5.运输问题是一种特殊的线性规划问题，因而其求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。

[ ]6.动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。

[ ]7.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。

[ ]8.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。

[ ]9.对于原问题是求Min，若第i个约束是“＝”，则第i个对偶变量yi≤0。

[ ]10.用大M法或两阶段法单纯形迭代中若人工变量不能出基(人工变量的值不为0)，则问题无可行解。

[ ]11.如图中某点vi 有若干个相邻点,与其距离最远的相邻点为vj,则边[vi,vj]必不包含在最小支撑树内。

[ ]12.在允许缺货发生短缺的存贮模型中，订货批量的确定应使由于存贮量的减少带来的节约能抵消缺货时造成的损失。

[ ] 13.根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。

[ ] 14.在线性规划的最优解中，若某一变量xj为非基变量，则在原来问题中，改变其价值系数cj，反映到最终单纯形表中，除xj的检验数有变化外，对其它各数字无影响。

[ ]15.单纯形迭代中添加人工变量的目的是为了得到问题的一个基本可行解。

[ ]16.订购费为每订一次货所发生的费用，它同每次订货的数量无关。

[ ]17.一个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行方案的选择。

2024级工商管理12级物流工程专业《运筹学》复习提纲运筹学复习提纲一、运筹学概述1.运筹学的定义和发展历程2.运筹学在实际问题中的应用领域3.运筹学与管理科学的关系二、线性规划1.线性规划的基本概念和特点2.线性规划模型的建立3.线性规划问题的图形解法4.单纯形表法求解线性规划问题5.整数线性规划的求解方法三、网络图与最短路径算法1.网络图及其表示方法2.最小生成树算法3.最短路径问题的定义和求解方法4.最短路径算法的应用实例四、整数规划1.整数规划的基本概念和特点2.整数规划模型的建立3.整数规划问题的求解方法4.0-1整数规划的解法和应用实例五、动态规划1.动态规划的概念和基本思想2.动态规划的状态转移方程3.动态规划问题的求解方法4.应用实例分析六、排队论1.排队论的概念和基本假设2.排队系统基本模型3.排队系统的性能指标和评价方法4.排队论的应用实例七、决策分析1.决策分析的基本概念和决策环境2.决策树模型的建立和解析3.敏感性分析和价值分析4.决策分析的应用领域和实例八、多目标决策1.多目标决策的基本概念和目标函数形式2.多目标决策的解法和权重确定方法3.多目标决策的应用实例九、模拟仿真1.模拟仿真的概念和基本原理2.模拟仿真的建模方法和过程3.模拟仿真的应用实例十、运筹学在实际问题中的应用案例分析1.接受订单问题的运筹学方法分析2.物流配送问题的运筹学方法分析3.供应链管理中的运筹学应用案例分析4.资源调度问题的运筹学方法分析该提纲中包含了运筹学的主要概念、基本模型和解法,并结合了实际应用案例的分析,有助于理解运筹学的基本原理和应用方法。

学生可以根据提纲进行复习,并根据自己的实际情况进行重点、难点的整理和深入学习。

运筹学复习一、 填空题1、线性规划中，满足非负条件的基本解称为基本可行解，对应的基称为可行基线.2、性规划的目标函数的系数是其对偶问题的右端常数；而若线性规划为最大化问题，则3、对偶问题为最小化问题。

4、在运输问题模型中，1m n +-个变量构成基变量的充要条件是不含闭回路。

5、动态规划方法的步骤可以总结为：逆序求解最优目标函数，顺序求__最优策略、最优路线和最优目标函数值。

6、工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；7、对不定步数问题，用迭代法求解，有函数迭代法和策略迭代法两种方法。

8、在图论方法中，通常用点表示人们研究的对象，用边表示对象之间的某种联系。

9、一个无圈且连通的图称为树。

10、图解法提供了求解只含有两个决策变量的线性规划问题的方法．11、图解法求解生产成本最小线性规划问题时，等成本线越往左下角移动，成本越低．12、如果线性规划问题有有限最优解，则该最优解一定在可行域的边界上上达到。

13、线性规划中，任何基对应的决策变量称为基变量．14、原问题与对偶问题是相互对应的． 线性规划中，对偶问题的对偶问题是原问题．15、在线性规划问题中，若某种资源的影子价格为10，则适当增加该资源量，企业的收益将_会 (“会”或“不会”)提高．16、表上作业法实质上就是求解运输问题的单纯形法．17、产销平衡运输问题的基变量共有m+n-1个．18、动态规划不仅可以用来解决和时间有关的多阶段决策问题，也可以处理与时间无关的多阶段决策问题．19、构成动态规划模型，需要进行以下几方面的工作：正确选择阶段（k ）变量，正确选择状态（Sk ）变量，正确选择_ 决策（UK ）变量，列出状态转移方程, 列出_阶段指标函数_，建立函数基本方程．20、动态规划方法可以用来解决和某些与时间有关的问题，但也可以用来解决和某些与时间无关的问题.在图论方法中，图是指由点与边和点与弧组成的示意图．21、网络最短路径是指从网络起点至终点的一条权之和最小的路线．简述单纯形法的计算步骤：第一步：找出初始可行解，建立初始单纯形表。

1. 简答题（1） 运筹学的工作步骤提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及相关的参数，搜集相关资料；建立模型：即把问题中可控变量，参数，目标与约束之间的关系用模型表示出来；求解：用各种手段将模型求解，解可以是最优解，次优解，满意解。

复杂模型的求解需用计算机，解得精度要求可有决策者提出；解的检验：首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；解的控制：通过控制解的变化过程决定对解是否做一定的改变； 解的实施：是指将解用到实际中必须考虑的实际问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。

（2）退化产生原因及解决办法单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。

勃兰特规则：1.选取cj-zj ＞0中下标最小的非基变量xk 为换入变量，即k=min(j ｜cj-zj ＞0)2. 当按θ规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。

（3）对偶问题的经济解释• 这说明yi 是右端项bi 每增加一个单位对目标函数Z 的贡献。

• 对偶变量 yi 在经济上表示原问题第i 种资源的边际价值。

• 对偶变量的值 yi*所表示的第i 种资源的边际价值，称为影子价值。

∑∑=====n j mi i i j j y b x c Z 11ωiiy b Z=∂∂若原问题的价值系数Cj 表示单位产值，则yi 称为影子价格； 若原问题的价值系数Cj 表示单位利润，则yi 称为影子利润。

影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。

（4）分枝定界法步骤a) 先求出整数规划相应的LP(即不考虑整数限制)的最优解， b) 若求得的最优解符合整数要求，则是原IP 的最优解； c) 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。

《运筹学》总复习第1章线性规划及其对偶问题• 基本概念基本要素：决策变量、目标函数、约束条件线性规划定义：决策变量为可控的连续变量，目标函数和约束条件为决策变量的线性函数。

标准形式：目标函数取“max ”、约束条件取“="、约束右端项非负、决策变量非负解的概念：凡满足约束条件的决策变量的取值称为线性规划的可行解,所有可行解的集合称 为线性规划的可行域，使目标函数达到最优值的可行解称为线性规划的最优解。

•数学建模与求解建模步骤：科学选择决策变量、找出所有约束条件、明确目标要求、非负变量的选择 单纯形法与对偶单纯形法：单纯形法对偶单纯形法原规划基本解是可行解原规划基本解的检验数小于等于零无可行解解无界计算：nr b । …b9 = min{-a\a > 0] = -i- a ka以a为中心元素进行迭代以a为中心元素进行迭代计算：o = max(o . o , > 0)计算：b = min(b\b < 0)计算:两阶段法：第一阶段：添加人工变量，构造人工变量之和为最小的目标函数辅助线性规划，由松驰变量和人工变量构成初始单纯形表，进行迭代。

在最终单纯形表中如果存在人工变量，由无可行解，否则转第二阶段。

第二阶段：在第一阶段求解的最终单纯形表中去掉人工变量，目标系数恢复为标准模型的目标系数，按单纯形法继续迭代。

•练习题：1.某厂利用原料A、B生产甲、乙、丙3种产品，已知生产单位产品所需原料数、单件利2.某旅馆在不同时段所需服务员数如表所示：每班服务员从开始上班到下班连续工作8小时，为满足每班所需要的最少服务员数，这个旅3.min w = x + 2 x + 3 x1 2 3x + 2 x + 3 x = 15s.t < 2x + x + 5x = 20x > 011~34.用对偶单纯形法求解线性规划问题：min w = 5 x + 2 x + 4 x1 2 33 x + x + 2 x > 4s .t < 6 x + 3 x + 5 x > 12x1 > 02 31 1~3第2章整数规划与分配问题•0-1变量的用法及建模理解0-1变量的9种用途，其中(1)(2)(4)(8)重点掌握(1)多个取1：¥x = 1，x,= 0,或 1.j=1(2) n 中取 k ：X % = k , x - 0,或 1.j =in 中至少取k ,改为E x > k , x = 0,或1.j -i n 中最多取k , 改为Yx < k , x = 0,或 1.j -i(3)变量取离散数值：x^^^cy.vi =1 i i£y = 1, y = 0或 1i i =1⑷选甲必须选乙，选乙不一定选甲：、 <久，、, 丁或1 （5）两个约束条件只需满足一个:（8）选了甲或乙，丙就不能入选，选了丙，甲、乙都不能入选■%+ x w <1< x + x < 1 x , x , x 丙=0或 1I 0,当 x = 0⑼对f (x )= 1 k + cx ,当x > 0可表述为:匈牙利法 步骤：x + x > 2 一 y M < 3 x + 2 x < 10 + y M/ + y 2 = 1,片 y 2 = 0或 1式中：M 为任意大正数 （6）n个约束条件中满足k 个：I x + x > 2 一(1 一 y ) M或1 12一 |3x + 2x < 10 + yM ,y =2ax < 嗔yM< j =1(i = 1,2,L , n )i =1⑺若x 2 < 4，则x 5 >；否则x 2> 4，। x < 4 + y M<x 5>0-y 1M, x 2 > 4- y2Mx 5 < 3 + y 2y 1 +y 2 = y। x < 4 + yMx ： > 0 - yM 或1 5 - x 2 > 4 - (1 - y ) M 「0I f (x ) = yk + cx< y < Mx x < My1.从每行中减去最小数2.再从每列中减去最小数3.⑴先看行,从第一行开始，如该行只有一个0,给该0打A,划去该为所在列,如有两个以上0或无0,转下一行,到最后一行；（2）再看列，如该列只有一个0,给该0打A，划去该0所在行，如无0或两个以上0,转下一列；⑶重复（1）（2）,可能出现三种结局：a.有m个打A的0,令对应A号的xij=1,即为最优.b.存在0的闭回路.对闭回路上的0按顺时针编号，任取单号或双号打A，分别对打A的0都划去所在行（或都划去所在列）返回3（1）C.打A的0的数＜m转44.从未被划去的数字中找出最小数字k,对未被划去的行分别减k;对被划去的列加k,回到3练习题：1.某公司有5000万元可用于投资，有6个投资方案，其投资额、安排员工数和年利润额如要求：（1）投资额不超过5000万元；（2）至少安排150人员就业；（3）年利润额尽可能地多。

1.约束方程标准化处理： 如：⎩⎨⎧≥+≤+652432121x x x x2.线性规划问题的解： P9线性规划问题的解的判定（尤其对偶问题解的情况）。

3.线性规划问题的对偶问题转化（表2.2）：如⎪⎪⎩⎪⎪⎨⎧≤≥=----≥++≤++-+-+=无约束、，4321432143243214321 ,0024732543 3432 4323min x x x x x x x x x x x x x x x x x x x Z 对偶问题：⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤=-+-=-+≥-+-≤++-=无约束32132132132131321y 0,y 0,y 44y 4y 4y 37y 3y 3y 23y y 2y 32yy 253max y y y W 4.对偶问题的基本性质：P45－P46 重点是性质1－5。

如：已知原问题的最优解为X* =（0.0.4），Z=12 试求对偶问题的最优解？⎪⎪⎩⎪⎪⎨⎧≤≥=++≥+-≤-+++=无约束321321321321321,0,04 16 3253234max x x x x x x x x x x x x x x x Z 解：对偶问题⎪⎪⎩⎪⎪⎨⎧≤≥=++-≤+-≥++++=无约束321321321321321,0,0)3(365)2(4 3 )1(132 42min y y y y y y y y y y y y y y y W将X* =（0 . 0 . 4）代入原问题中，有下式：⎪⎩⎪⎨⎧==++>=+-<-=-+44 1 246 3220532321321321x x x x x x x x x 所以，根据互补松弛条件，必有y*1= y*2=0，代入对偶问题 （3）式， y 3 =3。

因此，对偶问题的最优解为 Y *=（0 . 0 . 3），W=12。

5.灵敏度分析：重点分析b i 的影响。

如：⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤++=0,45 802903 45 max 2121212121x x x x x x x x x x Z b 3在什么范围内变化，原最优基不变？或者给定b 的值求最优解的变化。

南京工程学院 运筹学复习提纲绪论一、运筹学的基本特征（3个） ⑴系统整体的观念 ⑵多学科的综合⑶模型方法的运用，尤其是数学模型的应用 二、运筹学的工作步骤（6步） ⑴提出与形成问题 ⑵建立模型 ⑶求解 ⑷解的检验 ⑸解的控制 ⑹解的实施线性规划部分一、最优化问题、数学规划、线性规划之间的关系二、将一般LP 转化为SLP 。

注：先满足0,0x b ≥≥ ，再看目标与约束三、线性规划单纯形法的理论基础和技术路线 ⑴凸集、顶点、（凸集的顶点）、凸组合⑵基本定理：1若LP 存在可行解，则可行域为凸集2 LP 的基可行解对应可行域的顶点3 LP 有最优解，一定存在最优基解（最优解可在某顶点找到）⑶技术路线：从某初始基可行解开始、判别是否最优。

否则转到相邻顶点（基可行解）。

如此往复，直至找到最优解。

四、LP 可能出现的四种求解结果的判别条件⑴无界解判别（Max 问题）：非基变量的检验数10,0.k k K mk k R P αδα⎡⎤⎢⎥>∈=≤⎢⎥⎢⎥⎣⎦且 ⑵无穷多最优（Max 问题）：非基变量的检验数0,0,k k R δδ≤=∈且。

⑶唯一最优解（Max 问题）：非基变量的检验数00.j j R δδ≤<∈且，且基解不退化。

（注：基解退化时，非基变量检验数不满足非正，该解也可能是最优的，这时该解对应另一个基是最优基可行解）。

⑷无可行解：当大M法中构造的LP M或二阶段法中构造的LP0问题的最优解中人工变量不全为零，则原问题无可行解五、计算题1．图解法（略）2．单纯形法（含大M法）3．对偶单纯形法（仅用于b参数变化时的灵敏度分析）4. 单纯形法与对偶单纯形法的区别在于单纯形法是在满足基解可行性的条件下通过迭代逐步满足最优性；对偶单纯形法是在基解满足对偶可行性的条件下通过迭代逐步满足可行性。

5．列对偶问题6．由互松驰定理求对偶问题的最优解（影子价格）7．灵敏度分析（b , c参数变化……）六、人工变量与附加变量的区别。

第一部分线性规划问题的求解一、两个变量的线性规划问题的图解法：㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。

定义：达到目标的可行解为最优解。

㈡图解法：图解法采用直角坐标求解：x1——横轴；x2——竖轴。

1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。

4、确定最优解及目标函数值。

㈢参考例题：（只要求下面这些有唯一最优解的类型）例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？（此题也可用“单纯形法”或化“对偶问题”用大M法求解）解：设x 1、x 2为生产甲、乙产品的数量。

max z = 70x 1+30x 2 s.t.⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+072039450555409321212121x x x x x x x x ，可行解域为oabcd0，最优解为b 点。

由方程组⎩⎨⎧=+=+72039450552121x x x x 解出x 1=75，x 2=15 ∴X *=⎪⎪⎭⎫⎝⎛21x x =（75，15）T∴max z =Z *= 70×75+30×15=5700 例2：用图解法求解⑴⑵ ⑶ ⑷ ⑸、⑹s.t.⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤+0781022122121x x x x x x x ， 解：可行解域为oabcd0，最优解为b 点。

由方程组⎩⎨⎧=+=+81022121x x x x 解出x 1=2，x 2=6 ∴X *=⎪⎪⎭⎫⎝⎛21x x =（2，6）T∴max z = 6×2+4×6=36 例3：用图解法求解⑵ ⑶ ⑷ ⑸、⑹s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤+≥+≤≤08212523421212121x x x x x x x x ， 解：可行解域为bcdefb ，最优解为b 点。