运筹学25-27资料

《运筹学基础》复习要点一、基本概念与理论1．任意多个凸集的交集还是凸集。

2．任意多个凸集的并集不一定是凸集3．给定1R b ∈及非零向量n R a ∈，称集合}|{b x a R x H Tn=∈=是nR 的一个超平面。

4．由超平面}|{b x a R x H Tn=∈=的两个半平面}|{b x a R x H T n ≥∈=+和}|{1b x a R x H T n ≤∈=都是凸集。

5．设S 是凸集，S x ∈。

若对任何z y S z S y ≠∈∈,,，以及任何10<<λ，都有z y x )1(λλ-+≠，则称x 为S 的顶点。

6．如果一个LP 问题无界，则它的对偶问题必无可行解。

7．设w x ,分别为原始LP 问题、对偶问题的可行解，若b w x c T T =，则原始LP 问题、对偶问题的最优解分别为w x ,。

8.可行解x 是基本可行解的充分必要条件是x 的正分量，所对应的A 中列向量线性无关。

9.写出LP 问题的对偶问题0..min ≥≥⎪⎩⎪⎨⎧x b Ax x c t s T的对偶问题是： 0..min ≥≤⎪⎩⎪⎨⎧w c w A w b t s TT10．设一个标准形式的LP 问题的基为B ，右端向量为b ，则对应的基本解是⎪⎪⎭⎫⎝⎛=-01b B x 。

11．线性规划问题的可行域是凸集。

12．设线性规划问题LP 为0..min ≥=⎪⎩⎪⎨⎧x b Ax t s x c T B 为一个基，对应的典式为0..min 111≥=+⎪⎩⎪⎨⎧-=---x b B Nx B x t s x b B c z N B T TB ζ 其中),0(1T N TB Tc N B c -=-ζ。

13.线性规划问题的规范形式为0..min ≥≥⎪⎩⎪⎨⎧x b Ax x c t s T14. 线性规划问题的标准形式为0..min ≥=⎪⎩⎪⎨⎧x b Ax t s xc T15.线性规划问题的一般形式为⎪⎪⎪⎩⎪⎪⎪⎨⎧+==≥+=≥==n q j x qj x m p i b x a p i b x a t s x c j ji Ti i Ti T ,,1,,2,10,,1,,2,1..min 为自由变量16.对线性规划问题，关于它的解分三种情况：问题无解、问题无界和问题有最优解。

《运筹学》复习资料整理总结1. 建立线性规划模型的步骤。

确定决策变量 确定目标函数 确定约束条件方程2. 线性规划问题的特征。

都有一个追求的目标，这个目标可表示为一组变量的线性函数，按照问题的不同，追求的目标可以为最大，也可以为最小。

问题中有若干个约束条件，用来表示问题中的限制或要求，这些约束条件可以用线性等式或线性不等式表示。

问题中用一组决策变量来表示一种方案。

3. 线性规划问题标准型的特征。

4. 化标准型的方法。

123123123123min z 2+223-8340,0,x x x x x x x x x x x x =+-+=⎧⎪-+-≤⎨⎪≤≥⎩为自由变量123123123123min z 2+223-634,0,x x x x x x x x x x x x =+-+=⎧⎪-+-≥⎨⎪≥⎩为自由变量5. 基本解：令其余的变量取值为0，则得到Ax=b 的一个解y,称此解为线性规划问题的基本解。

6. 基本可行解：若基本解y 满足y ≥0,则称这个解为基本可行解。

7. 可行解：满足约束条件的解x=（x1、x2、……xn ）T 称为线性规划问题的可行解。

8. 最优解：函数达到最优的可行解叫做最优解。

9.图解法适合于变量个数为2个的线性规划问题。

10.单纯形法解线性规划问题如何确定初始基本可行解。

（1）约束条件为≤，先加入松弛变量x1、x2……xm后变为等式，取松弛变量为基本变量（2）约束条件为=，先加入人工变量xm+1、xm+2……xm+n，人工变量价值系数为m（3）约束条件为≥，先加入多于变量xn+1、xn+2……xm+n后变为等式，在添加人工变量xn+m+111.单纯形法最优解的检验准则。

（1）若基本可行解x’对应的典式的目标函数中非基变量的系数全部满足cN-cBB-1Pj≤0,则基本可行解x’为原问题的最优解。

（2）若基本可行解x’对应的典式的目标函数中所有非基变量的系数满足cN-cBB-1Pj≤0,且有一非基变量的系数满足Ck-Zk=0,则原问题有无穷多组最优解12.对目标函数为极小（min）型的线性规划问题，用单纯形法解的三种处理方法。

30个运筹学的解题方法与技巧1. 线性规划：解决在一定约束条件下最大化或最小化线性目标函数的问题。

常用方法有单纯形法、对偶理论和分解算法等。

2. 整数规划：处理决策变量取整数值或只能取整点值的线性规划问题。

常用方法有分支定界法、割平面法等。

3. 动态规划：通过将原问题分解为相互重叠的子问题，解决具有重叠子问题和最优子结构性质的问题。

4. 图论方法：用于解决最短路、最小生成树、最小割、最大流等问题，常用算法有Dijkstra 算法、Prim算法、Ford-Fulkerson算法等。

5. 网络优化：解决运输、分配和布局等问题，常用方法有运输问题算法、分配问题算法等。

6. 排队论：研究等待队列的结构和特性，以及服务机构的工作规律。

主要模型有M/M/1、M/M/c等。

7. 存储论：研究如何科学地管理物资库存，以最低的费用保证生产和销售需要。

常用模型有不允许缺货模型、一次性订货模型等。

8. 决策分析：根据已知信息评估不同行动方案的效果，从而选择最优方案。

常用方法有期望值法、决策树法等。

9. 对策论：研究竞争、对抗和冲突问题的数学模型，常用方法有Nash均衡、优势策略和必胜策略等。

10. 随机规划：处理具有随机性的决策问题，常用的求解方法有期望值法、机会约束规划和贝叶斯决策等。

11. 多目标规划：解决具有多个冲突目标的优化问题，常用的求解方法有主要目标法、权衡法和分层序列法等。

12. 非线性规划：处理目标函数或约束条件非线性的优化问题，常用的求解方法有梯度法、牛顿法等。

13. 启发式方法：采用直观和经验的方法求解问题，如遗传算法、模拟退火算法等。

14. 数学仿真：通过建立数学模型并模拟实际情况，评估不同方案的性能和效果。

15. 多属性决策分析：处理具有多个评估属性的决策问题，常用的求解方法有多属性效用理论、层次分析法等。

16. 模拟退火算法：一种启发式优化算法，通过模拟固体退火过程来寻找全局最优解。

17. 遗传算法：模拟生物进化过程的优化算法，通过遗传、交叉和变异等操作寻找最优解。

运筹学课程一单选题 (共170题，总分值170分 )1. 约束矩阵A中任何一组m个线性无关的列向量构成的子矩阵称为该问题的一个( )（1 分）A. 基B. 最优解C. 基本解D. 基向量2. 线性规划的标准型中P称为( )（1 分）A. 技术向量B. 价值向量C. 资源向量D. 约束矩阵3. 决策问题的构成要素不包含（）（1 分）A. 决策者B. 策略C. 收益D. 约束4. 去掉整数约数条件后得到的线性规划称为原整数规划的（）（1 分）A. 松弛问题B. 增益问题C. 对偶问题D. 反问题5. X、Y分别是原问题和对偶问题的可行解，且，则X、Y分别是原问题和对偶问题的( ) （1 分）A. 基本可行解B. 最优解C. 基本解D. 不知6. A是m×n矩阵，则共有多少个非基向量( )（1 分）A. m×nB. mC. nD. n-m7. 约束矩阵A中任何一组m个线性无关的列向量构成的子矩阵称为该问题的一个( ) （1 分）A. 基B. 最优解C. 基本解D. 基向量8. 在排队系统的符号表示[A/;/;]:[;/E/F]中,A对应的是（）（1 分）A. 顾客到达的时间间隔B. 分布服务时间的分布C. 服务台数D. 顾客源总体数目9. 下面不属于决策类型的是（）（1 分）A. 战略决策B. 非常决策C. 静态决策D. 动态决策10. Kruskal算法属于哪种思路的方法（）（1 分）A. 破圈B. 避圈C. 智能搜索D. 枚举11. 不属于按问题性质和条件分类的决策类型是（）（1 分）A. 确定性决策B. 非确定决策C. 连续性决策D. 风险性决策12. 哪个不是常用的存贮策略有（）（1 分）A. T－循环策略B. （s，S）策略C. （s，Q）策略D. （T，s，S）策略13. 线性规划在转化标准型时，转换约束条件时新增非负变量称为( )（1 分）A. 决策变量B. 松弛变量C. 资源变量D. 凸变量14. 线性规划问题的可行域是( ) （1 分）A. 四边形B. 凸集C. 不规则形D. 任意集15. 对于无后效性的多阶段决策过程，系统由阶段k到阶段k＋1的状态转移方程是（）（1 分）A.B.C.D.16. 1947年谁得到了线性规划的单纯形法( )（1 分）A. ErlangB. HarrisC. ShewhartD. Dantzig17. 图G中既无环又无平行边，则称作（）（1 分）A. 有向图B. 简单图C. 初级图: 子图18. 在排队系统的符号表示[A/B/C]:[D/E/F]中,A对应的是（）。

运筹学案例集常州宝菱重工机械有限公司孔念荣收集整理运筹学的一些典型性应用•合理利用材料问题：如何在保证生产的条件下，下料最少•配料问题：在原料供应量的限制下，如何获取最大收益•投资问题：从投资项目中选取最佳组合，使投资回报最大•产品生产计划：合理利用人力、物力、财力等，使获利最大•劳动力安排：用最少的劳动力来满足工作的需要•运输问题：如何制定最佳调运方案，使总运费最少一、生产计划问题案例1（2-4）、某工厂用A、B、C、D四种原料生产甲、乙两种产品，生产甲和乙所需各种原料的数量以及在一个计划期内各种原料的现有数量见下表所示。

又已知每单位产品甲、乙的售价分别为400元和600元，问应如何安排生产才能获得最大收益？已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？案例3（2-25）、某公司面临一个是外包协作还是自行生产的问题。

该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。

甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量，数据如下表所示。

问题：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？案例4（2-28）、永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。

设有两种规格的设备A1、A2能完成A工序；有三种规格的设备B1、B2、B3能完成 B 工序。

Ⅰ可在A、B的任何规格的设备上加工；Ⅱ可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工，数据如下表所示。

问题：为使该厂获得最大利润，应如何制定产品加工方案？案例5、某造纸厂用原材料白坯纸生产原稿纸、笔记本和练习本三种产品。

该厂现有工人100人，每月白坯纸供应量为3万公斤。

已知工人的劳动生产率为：每人每月生产原稿纸30捆，或生产日记本30打，或练习本30箱。

第一章线性规划1．1将下述线性规划问题化成标准形式1)min z＝－3x1＋4x2－2x3＋5 x4－x2＋2x3－x4＝－24xst. x1＋x2－x3＋2 x4 ≤14－2x1＋3x2＋x3－x4 ≥2x1，x2，x3≥0，x4无约束2)min z ＝2x1－2x2＋3x3＋x2＋x3＝4－xst. －2x1＋x2－x3≤6x1≤0 ，x2≥0，x3无约束1．2用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。

1)min z＝2x1＋3x24x1＋6x2≥6st2x1＋2x2≥4x1，x2≥02)max z＝3x1＋2x22x1＋x2≤2st3x1＋4x2≥12x1，x2≥03)max z＝3x1＋5x26x1＋10x2≤120st5≤x1≤103≤x2≤84)max z＝5x1＋6x22x1－x2≥2st－2x1＋3x2≤2x1，x2≥01．3找出下述LP问题所有基解，指出哪些是基可行解，并确定最优解（1）min z＝5x1－2x2＋3x3＋2x4x1＋2x2＋3x3＋4x4＝7st2x1＋2x2＋x3 ＋2x4＝3x1，x2，x3，x4≥01．4 分别用图解法与单纯形法求解下列LP 问题，并对照指出最优解所对应的顶点。

1) maxz ＝10x 1＋5x 23x 1＋4x 2≤9 st 5x 1＋2x 2≤8 x 1，x 2≥02) maxz ＝2x 1＋x 2 3x 1＋5x 2≤15 st 6x 1＋2x 2≤24 x 1，x 2≥01．5 分别用大M 法与两阶段法求解下列LP 问题。

1) minz ＝2x 1＋3x 2＋x 3 x 1＋4x 2＋2x 3≥8 st 3x 1＋2x 2 ≥6 x 1，x 2 ，x 3≥02) max z ＝4x 1＋5x 2＋ x 3. 3x 1＋2x 2＋ x 3≥18 St. 2x 1＋ x 2 ≤4x 1＋ x 2－ x 3＝53) maxz ＝ 5x 1＋3x 2 +6x 3 x 1＋2x 2 －x 3 ≤ 18 st 2x 1＋x 2 －3 x 3 ≤ 16 x 1＋x 2 －x 3＝10 x 1，x 2 ，x 3≥01231231231231234)max 101512539561515.25,,0z x x x x x x x x x st x x x x x x =++++≤⎧⎪-++≤⎪⎨++≥⎪⎪≥⎩1．61.7某班有男生30人，女生20人，周日去植树。

运筹学[填空题]1用改进单纯形法求解以下线性规划问题。

[填空题]2已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见表，试将空白处数字填上。

参考答案：[填空题]3判断下列说法是否正确，并说明为什么？（1）如线性规划问题的原文题存在可行解，则其对偶问题也一定存在可行解。

（2）如线性规划的对偶问题无可行解，则原问题也一定无可行解。

（3）如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划问题一定有有限最优解。

参考答案：（1）错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在；（2）错误，对偶问题没有可行解，原问题可能有可行解也可能有无界解；（3）错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能有无界解；[填空题]4设线性规划问题1是：又设线性规划问题2是：参考答案：把原问题用矩阵表示：原问题和对偶问题的最优函数值相等，所以不等式成立，证毕。

[填空题]5已知线性规划问题 用单纯形法求解，得到最终单纯形表如表所示，要求： （1）求a 11，a 12，a 13，a 21，a 22，a 23，b 1，b 2的值； （2）c 1，c 2，c 3的值；参考答案：初始单纯形表的增广矩阵是：最终单纯形表的增广矩阵为C 2是C 1作初等变换得来的，将C 2作初等变换，使得C 2的第四列和第五列的矩阵成为C 2的单位矩阵。

有：[填空题]6试用对偶单纯形法求解下列线性规划问题。

参考答案：（1）取w=-z，标准形式：最优解：X=（21/13，10/13，0，0）T目标函数最优值为31/13。

（2）令：w=-z，转化为标准形式：原问题最优解：X=（3，0，0，0，6，7，0）T目标函数最优值为9。

[填空题]7现有线性规划问题先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？（1）约束条件1的右端常数20变为30；（2）约束条件2的右端常数90变为70；（3）目标函数中x3的系数变为8；（4）x1的系数向量变为；（5）增加一个约束条件2x1+3x2+5x3≤50；（6）将约束条件2变为10x1+5x2+10x3≤100。