《运筹学OR学习指导书》由会员分享，可在线阅读，更多相关《运筹学OR学习指导书（10页珍藏版）》请在金锄头文库上搜索。
1、运筹学学习指导书第一章：线性规划与单纯形法、什么是线性规划：1线性规划：研究有限资源如何合理利用的一种数学规划问题。2线性规划数学模型的一般形式：max（min） z=cx1+c2x2 + .+c nxs. tai1X1+ai2X2 + .+ a朋（=、-）b1a ,x7+a+ .+a x 03. 线性规划的标准形是：s. tmaxz=c1x1+c2x2+.+c nxa11x1+a12x2+.+a1nxn=b1am1x1+am2x2+.+am n x n=bmx1,x2,. ,xn0可写成： max z=cx ,s.t Ax=b,x20二、. 线性规划问题求解的基本定理(1) 图解法求解线性规
2、划问题 只含两个决策变量的线性规划问题，可以用图解法来求解。 理解目标函数等值线的概念；掌握解线性规划问题的重要规律(2) 线性规划问题求解的基本定理(3) 基、基解和基可行解 基变量、非基变量、基阵、基解和基可行解的概念三、单纯形法的基本步骤，1将问题化为标准形2 找出一个初始可行基，并作出单纯形表3. 若所有检验数WO,则此初始可行基是最优解，计算停止；4. 若某检验数三0,而全部厂 0，而有a 0，则按书上方法计算9，并变换得到新基;sis6. 对新基作出单纯形表，从3开始重复进行，直到得到最优解。四、人工变量法1. 大 M 法(1) 人工变量的含义(2) 大 M 法的步骤对 LP 问题
3、：maxnz=乙 c x ，jjj=1ns.t 乙 a x = b (i=l,2,.,m) ij jij=1x 三0 (j=l,2,.,n)j在每一约束方程的左边加上一个非负变量人工变量，问题变为nmax z=乙 c xjj j=1m-乙Mxn + ii=1ns.t 乙 a x + x = b (i=l,2,.,m)j jn + iij=1x 三0 (j=l,2,.,n+m) j( 3 )大 M 法的缺点2 两阶段法( 1 )什么是两阶段法对 LP 问题：nmax z =乙 c x ，jjj=1ns.t 乙 a x = b(i=l,2,.,m)ij jij=1x 三0 (j=l,2,.,n)j
4、作辅助问题：mmin w= E xn + ii=1s.tn乙 a x + x = b (i=l,2,.,m) j j n + i ij=1x 三0 (j=l,2，n+m) j2 ) 两阶段法步骤1) 由所给问题 L 构作一个辅助问题 L1 ，求出其 f * ；若 f * =0，L 有可行解，进入 3)；2 ) 若 f * 0, 则 L 无可行解，计算停止3) f *=0时，由Li的最优基获得L的可行解。(3)两阶段法与大 M 法相比有何优点？五、单纯形法的进一步讨论 1 多重最优解2 退化（1）退化的含义（2）解退化问题中出现的循环现象（3）如何避免循环现象的出现：1) 。如有几个检验数为正，
5、则应选取其中下标最小的非基变量作为入基变量。2) 如有几个比值同时达到最小，则应选取其中下标最小的基变量作为出基变量 3 无可行解4 无界可行解集六、数据包络分析(不考核)七、应用举例 了解在经济管理和工程中的应用。掌握线性规划的建模方法技巧1. 生产管理 如何在生产管理中运用线性规划求出最佳生产计划？ 如何运用线性规划求解切割问题？2. 市场销售 如何运用线性规划求出最佳销售策略？3. 金融与投资 如何运用线性规划求出最佳投资组合？4. 配料、下料 如何运用线性规划求出最佳配料组合、下料方案？5.环境保护如何运用线性规划求出最佳环境保护方案？习题：做书上 P44-48 习题中的第 1.1(1
6、)、1.4(1)、1.7(2)(4)、1.13 题； 选做 1.8、 1.9、 1.10、 1.14、 1.15 题。第二章对偶理论和灵敏度分析一、原问题和对偶问题 1什么是原始问题和其对偶问题 已知一个原问题是 max c x ,s.t AxWb,x20则其对偶问题是：min z= bTy，s.t ATy 三 cT,y三0 已知一个原问题是 min cT x , s.t Ax 三 bx20则其对偶问题是：maxbTy ,s.t ATyWcTy三02 对偶问题的解二、原始对偶关系的基本性质(1) 对偶问题的对偶就是原问题(2) 原问题有最优解时，其对偶问题也有最优解(3) 若 x,y 分别是(
7、2.1)和(2.2)的可行解,则有:ex 三 bTy(4) (2.1)和(2.2)或都有(有限的)最优解,或都没有(有限的)最优解;在第一 种情况下,两者的目标函数最优值相等。(5)定理 2.3(6)定理 2.4(7)定理 2.6三、对偶单纯形法步骤： 3将问题化为标准形4. 找出一个满足所有检验数W0的初始基，并作出其单纯形表5. 若表中一切匸三0,则初始基已是最优基，求出最优解与最优值，计算停止；否则i转入 46. 按书上方法换基，得新基7. 变换出新基的单纯形表，转入 3 开始重复进行，直到得到最优解。四、对偶变量的经济解释1. 在资源分配问题中，每种资源变化一个单位，对总利润将产生多大
8、影响？2. 什么是影子价格？3. 影子价格有什么作用？五、灵敏度分析 分析所给问题数据发生变化时，最优解、基会发生什么变化。1. 目标函数的系数发生变化时，对最优解有何影响？保持最优解不变时允许价值 系数变化范围是多少？2. 约束条件中右端系数发生变化时，对最优解、基有何影响？保持最优基不变时 允许右端系数变化范围是多少？3. 约束条件中左边系数发生变化时，如何求最优解？4. 引入新变量时，对最优解有何影响？如何求最优解？5. 引入新的约束时，对最优解有何影响？如何求最优解？习题：做书上 P77-82 习题中的第2.1(2)、2.7、2.9(2)、2.12 题 选做第 2.3、2.14题。第三
9、章 运输问题、运输模型平衡运输问题的模型：mincxij iji = 1 j =1ns.t 乙 x = a (i=l,2,.,m)ij ij=1工 x = b(j=l,2,.,n)ij ji=1x三0ijmn(乙 a = L b )ij i=1j =1二、初始基可行解的求法1 最小元素法2 Vogel 近似法三、解的最优性检验1. 闭回路法2. 位势法准则：若全部检验数0,则此基可行解已是最优解；若有负检验数存在，则进入下一_lB步。四、用闭回路法进行基变换，得到新的基可行解从“三”开始重复进行，直到得到最优解。五、不平衡运输问题1 不平衡运输问题的模型如下：minmnz= L L c x ,
10、 ij ij i=1 j =1s.tnL x = a ( i=l,2,. ,m) ij ij=1L x = b( j=l,2,.,n)ij j i=1mnx 三 0(L a 丰 L b )ij i j i=1j =12 如何求解不平衡运输问题？ 增加一个虚拟的收点或发点，其收量或发量刚好等于收发量之差，将不平衡运输问题 转化成为平衡运输问题来求解。习题：做书上P107-110习题中的第3.8(3)题；选做第 3.11 题。第四章 目标规划一、目标规划的模型1什么是目标规划？目标规划的基本思想:(1) 对每一个目标由决策者定出一个具体的目标值(2) 对每一个目标制定目标函数(3) 寻找一个使目标
11、函数和对应目标值之间偏差之和最小的解.2 线性规划与目标规划的联系与区别是什么3相同等级的目标规划(1) 相同等级的目标规划含义(2) 相同等级的目标规划问题的模型是如何的?4 有优先等级的目标规划问题(1) 有优先等级的目标规划问题的含义(2) 有优先等级的目标规划问题的模型是如何的?5 有赋权优先等级的目标规划问题(1) 有赋权优先等级的目标规划问题的含义(2) 有赋权优先等级的目标规划问题的模型是如何的？二、目标规划的解法1相同等级的目标规划问题如何求解？2有优先等级的目标规划问题是如何求解的？ 3有赋权优先等级的目标规划问题是如何求解的？习题：做书上 P124-128 习题中的第4.3
12、(1)、4.6、4.7 题。第五章 整数规划一、整数规划的应用 1什么是整数规划？什么是纯整数规划？什么是混合整数规划 2投资决策问题中如何运用整数规划？模型是：maxz=工c x ，jjj=1ns.t 乙 a x Mjj=10 x U yjj jy =0 或 1, (j=l,2,.,n)j4多重约束的选择问题中如何运用整数规划？( 1 )什么是多重约束的选择问题？( 2 )多重约束的选择问题一般模型：设一个问题中有p个约束条件工 ax b(i=l,2,.,p)ij j ij 二 1现需要其中q个被满足，但不知是哪q个。设已知：有p个常数M，对一切x都有：ii工 ax b + M(i=l,2,
13、.,p)ij jiij 二 1则 m 个约束条件要其中 q 个被满足就可表示为：工 ax b + M y(i=l,2,.,P)ij jii ij 二 1Y y = p - qii=1y =0 或 1，( i=l,2,.,p)i二、整数规划的解法-割平面法思想：(1)对给定的LP问题，先不考虑其整数条件，解此LP问题；(2) 若求出的最优解都是整数，则此解就是所要求的最优解；否则转入(3)(3) 若求出的最优解中，至少有一个基变量不是整数，而给定的LP问题要求它 是整数，则对原来的 LP 问题增加一个线性约束条件(割平面)。(4) 对增加了线性约束条件的LP问题求最优解。三、分支定界法思想：(1)对给定的LP问题，先不考虑其整数条件，解此LP问题；(2) 若求出的最优解都是整数，则此解就是所要求的最优解；否则转入(3)(3) 若求出的最优解中，至少有一个基变量不是整数，而给定的LP问题要求它 是整数，则将原来的LP问题分成几支，每支增加一个约束条件。(4) 对增加了约束条
