2012年运筹学复习

1、B2、B3、A4、C5、D6对7对8 错9 对10 对11 标准化（用对偶单纯型法解）MAX Z=-5X1 -2X2 -4X3ST-3X1-X2-2X3+X4 = -4-6X1-3X2-5X3 +X5 = -10X1…X5>=0B (-4，-10) 含负数，不是最优解确定进基MIN()=MIN(Zi/x5)=2/3 所以进基X2单纯型表迭代B (-2/3，10/3) 含负数，不是最优解再迭代一次确定离基变量MIN (X4,X2)=MIN(-2/3,-10/3)=-2/3 所以X4 为离基确定进基MIN()=MIN(Zi/x5)=2/3 所以进基X1单纯型表迭代先X2行除以A11=-1每行-AI1*X1Z’=-26/3 所以Z=26/3 X=(2/3,10/3,0,0,0)对偶问题MAX W=4Y1+10Y2ST3Y1+6Y2<5Y1+3Y2<=2Y1+5Y2<=4Y1,Y2>=0最优解就是松弛变量Y1=2 Y2=4/312题表作业法此题是产销平衡问题检验σ不能小于0A11 =4-4+3-2=1A24=9-3+4-11=-1 24不通过,不是最优解检验31，没有标记的格子A31=8-5+6-11+4-3+2=1检验22，没有标记的格子A22=10-3+4-11+6-5=1最小的σ24=-1，需要变换对奇数转角变量减去A14 ,对偶数转角变量加上A14,本身不变于是运费为2×8+2×3+4×12+5×14+6×8+11×4。

《运筹学》课程复习资料一、判断题：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.一个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行方案的选择。

《运筹学》课程综合复习资料一、判断题1.求解LP 问题时，对取值无约束的自由变量，通常令"-'=j j j x x x ，其中：0≥"'j j x x ，在用单纯形法求得的最优解中，有可能同时出现0>"'j jx x 。

答案：错2．在PERT 计算中，将最早节点时刻等于最迟节点时刻、且满足0)(),()(=--i t j i t j t E L 节点连接而成的线路是关键线路。

答案：对3．在一个随机服务系统中，当其输入过程是一普阿松流时，即有(){}()t n en t n t N P λλ-==!，则同一时间区间内，相继两名顾客到达的时间间隔是相互独立且服从参数为λ的负指数分布，即有()te t X p λλ-==.答案：对4.已知*i y 为线性规划的对偶问题的最优解，若*i y ＝０，说明在最优生产计划中第i 种资源一定有剩余。

答案：对5.用单纯形法求解单纯形表时，若选定唯一入基变量k x （检验数>0），但该列的1,2...m=i 0ik a ≤，则该LP 问题无解。

答案：对6.对偶单纯形法中，若选定唯一出基变量i x （i x <0），但i x 所在行的元素（系数矩阵中）全部大于或等于0，则此问题无解。

答案：对7.LP 问题的可行域是凸集。

答案：对8.动态规划实质是阶段上枚举，过程上寻优。

答案：对9.动态规划中，定义状态变量时应保证在各个阶段中所做决策的相互独立性。

答案：对10.目标规划中正偏差变量应取正值，负偏差变量应取负值。

答案：错11.LP问题的基可行解对应可行域的顶点。

答案：对12.若LP问题有两个最优解，则它一定有无穷多个最优解。

答案：对13.若线性规划的原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解。

答案：对14.对偶问题的对偶问题一定是原问题。

答案：对15．对于同一个动态规划问题，逆序法与顺序法的解不一样。

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．线性规划模型由下面哪几部分组成？（ABC）A决策变量 B约束条件 C目标函数 D 价值向量★考核知识点: 线性规划模型的构成.（1.1）附1.1.1（考核知识点解释）：线性规划模型的构成：实际上，所有的线性规划问题都包含这三个因素：（1）决策变量是问题中有待确定的未知因素。

例如决定企业经营目标的各产品的产量等。

（2）目标函数是指对问题所追求的目标的数学描述。

例如利润最大、成本最小等。

（3）约束条件是指实现问题目标的限制因素。

如原材料供应量、生产能力、市场需求等，它们限制了目标值所能到达的程度。

2．下面关于线性规划问题的说法正确的是（AB）A．线性规划问题是指在线性等式的限制条件下，使某一线性目标函数取得最大值（或最小值）的问题。

B．线性规划问题是指在线性不等式的限制条件下，使某一线性目标函数取得最大值（或最小值）的问题。

C．线性规划问题是指在一般不等式的限制条件下，使某一线性目标函数取得最大值（或最小值）的问题。

D．以上说法均不正确★考核知识点: 线性规划模型的线性含义.（1.1）附1.1.2（考核知识点解释）：所谓“线性”规划，是指如果目标函数是关于决策变量的线性函数，而且约束条件也都是关于决策变量的线性等式或线性不等式，则相应的规划问题就称为线性规划问题。

3．下面关于图解法解线性规划问题的说法不正确的是（ BC ）A在平面直角坐标系下，图解法只适用于两个决策变量的线性规划B 图解法适用于两个或两个以上决策变量的线性规划C 图解法解线性规划要求决策变量个数不要太多，一般都能得到满意解D 以上说法A正确，B，C不正确★考核知识点: 线性规划图解法的条件. （1.2）附 1.1.3（考核知识点解释）：线性规划图解法的条件：对于只有两个变量的线性规划问题，可以在二维直角坐标上作图.4．在下面电子表格模型中，“决策变量”的单元格地址为（ AB ）A . C12B . D12C . C4 D. D4★考核知识点: 电子表格中如何建立线性数学模型. （1.3）附1.1.4（考核知识点解释）：电子表格中的数学模型的建立：（1）要做出的决策是什么？（决策变量）；（2）在做出这些决策时有哪些约束条件？（约束条件）；（3）这些决策的目标是什么？（目标函数），将对应的问题数据放在相应的电子表格中即可.5．通常，在使用“给单元格命名”时，一般会给（ABCD ）有关的单元格命名A 公式B 决策变量C 目标函数D 约束右端值★考核知识点: 给单元格命名的原则. （1.3）附1.1.5（考核知识点解释）：给单元格命名的原则：一般给跟公式和模型有关的四类单元格命名。

《运筹学》复习题一、单项选择题1、（）运筹学的主要内容包括： [单选题] *A.线性规划B.非线性规划C.存贮论D.以上都是(正确答案)2、（）下面是运筹学的实践案例的是： [单选题] *A.丁谓修宫B.田忌赛马C.二战间，英国雷达站与防空系统的协调配合D.以上都是(正确答案)5、（）运筹学模型： [单选题] *A．在任何条件下均有效B.只有符合模型的简化条件时才有效(正确答案)C．可以解答管理部门提出的任何问题D．是定性决策的主要工具8、（）图解法通常用于求解有（）个变量的线性规划问题。

[单选题] *A.1B.2(正确答案)C.4D.510、 (D)将线性规划问题转化为标准形式时，下列说法不正确的是： [单选题] *Ａ.如为求z的最小值，需转化为求-z的最大值(正确答案)Ｂ.如约束条件为≤，则要增加一个松驰变量Ｃ.如约束条件为≥，则要减去一个剩余变量Ｄ.如约束条件为＝，则要增加一个人工变量12、（）关于主元的说法不正确的是： [单选题] *A.主元所在行称为主元行B.主元所在列称为主元列C.主元列所对应非基变量为进基变量D.主元素可以为零(正确答案)13、（）求解线性规划的单纯形表法中所用到的变换有： [单选题] *A.两行互换B.两列互换C.将某一行乘上一个不为0的系数(正确答案)D.都正确14、（）矩阵的初等行变换不包括的形式有： [单选题] *A. 将某一行乘上一个不等于零的系数B.将任意两行互换C. 将某一行乘上一个不等于零的系数再加到另一行上去D.将某一行加上一个相同的常数(正确答案)17、（）关于标准线性规划的特征，哪一项不正确： [单选题] *A.决策变量全≥0B.约束条件全为线性等式C.约束条件右端常数无约束(正确答案)D.目标函数值求最大18、（）线性规划的数学模型的组成部分不包括： [单选题] *A.决策变量B.决策目标函数C.约束条件D.计算方法(正确答案)19、（）如果在线性规划标准型的每一个约束方程中各选一个变量，它在该方程中的系数为1，在其它方程中系数为零，这个变量称为： [单选题] *A.基变量(正确答案)B.决策变量C.非基变量D.基本可行解21、 (C)关于线性规划的最优解判定，说法不正确的是： [单选题] *Ａ.如果是求最小化值，则所有检验数都小于等于零的基可行解是最优解。