资源描述：
《运筹学OR学习指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《运筹学》学习指导书第一章：线性规划与单纯形法一、什么是线性规划：1.线性规划：研究有限资源如何合理利用的i种数学规划问题。2.线性规划数学模型的一般形式：max(min)z=ciX/+C2X2+...^-cnxns.tanXi+ai2X2+...+ainXn<(=、>)bjQ加1X]+Clni2^2+•••+Q加nn^（=、—）bmX/fX2,...,Xn>03.线性规划的标准形是：maxz=c/X/+C2X2+...+cnxnS.td〃兀/+。/2兀2+…+Q/M"二如+°/”2%2+•…nXn—^rnX/fX2f...fXtJ>0可写成：maxz
2、=cx's.tAx=b,xNO二、.线性规划问题求解的基本定理(1)图解法求解线性规划问题只含两个决策变量的线性规划问题，可以用图解法来求解。理解H标函数等值线的概念；学握解线性规划问题的重要规律⑵线性规划问题求解的基本定理(3)基、基解和基可行解基变虽、非基变虽、某阵、基解和棊可行解的概念三、单纯形法的基本步骤，1.将问题化为标准形2.找出一个初始可行基，并作出单纯形表3.若所有检验数W0,则此初始可行基是最优解，计算停止；4.若某检验数M0,而全部石50,则此LP问题无最优解；5.若某检验数<7、>0,而有^~>0,则按书上方法计算&,并变换得到新
3、基;6.对新基作出单纯形表，从3开始重复进行，直到得到最优解。四、人工变量法1.人M法(1)人工变量的含义(1)人M法的步骤对LP问题:maxz二工CjXj'J=1s.t工QjjXj=h(i=l,2,...,m)j=i厂MO(j=l,2,...,n)在每一约束方程的左边加上一个非负变量一一人丄变量，问题变为：maxz=^c.x.j=/=1s.tAm+xn+i=bi(i=l,2,...,m)j=iXj^0(j=l,2,...,n+m)(2)人M法的缺点1.两阶段法(1)什么是两阶段法对LP问题：maxz=^CjXj'j=ls.t^Jaijxj=bj(i
4、=l,2,•…m)j=iXjNO(j=l,2,…,n)作辅助问题：minw二工x”+j1=1s.t工%jXj+xn+i=bi(i=l,2,...,m)J=iX-^0(j=l,2,...,n+m)（2）两阶段法步骤1）由所给问题L构作一个辅助问题U,求出其厂；若f*=0,L有可行解，进入3）；2）若f*>0,则L无可行解，计算停止3)f>0时，由I?的最优基获得L的可行解。(3)两阶段法与大M法相比冇何优点？五、单纯形法的进一步讨论1.多重最优解2.退化(1)退化的含义(2)解退化问题中出现的循环现象(3)如何避免循环现象的出现：Do如冇儿个检验数为正，
5、则应选取英中下标最小的非基变虽作为入基变虽。2)如有儿个比值同时达到最小，贝IJ应选取具屮下标最小的基变量作为出基变量。1.无可行解2.无界可行解集六、数据包络分析(不考核)七、应用举例了解在经济管理和工程中的应用。学握线性规划的建模方法技巧1.生产管理如何在生产管理中运用线性规划求出最佳生产计划？如何运用线性规划求解切割问题？2.市场销伟如何运川线性规划求出最佳销售策略？3.金融与投资如何运用线性规划求出最佳投资组合?4.配料、下料如何运用线性规划求出最佳配料组合、下料方案？5.环境保护如何运用线性规划求出最佳坏境保护方案？习题：做书±P44-48习
6、题中的第1.1(1)、1.4(1)、1.7⑵⑷、1.13题；选做1.8、1.9、1.10、1.14、1.15题。第二章对偶理论和灵敏度分析一、原问题和对偶问题1.什么是原始问题和其对偶问题已知一个原问题是maxcx's.tAxWb,xNO则其对偶问题是：minz=Jy，s.tATy^cy$0已知一个原问题是mincTx*s.tAx2bx20则其对偶问题是：maxbTy's.tATy^cTy201.对偶问题的解二、原始——对偶关系的基木性质(1)对偶问题的对偶就是原问题(2)原问题有最优解时，其对偶问题也有最优解(3)若x,y分别是(2.1)和(2.2
7、)的可行解,则有:cx^bTy(4)(2.1)和(2.2)或都有(有限的)最优解，或都没有(有限的)最优解;在第一种情况下，两者的R标函数最优值相等。(5)定理2.3(6)定理2.4⑺定理2.6三、対偶单纯形法步骤：2.将问题化为标准形3.找出一个满足所有检验数W0的初始基，并作出其单纯形表4.若表中一切亍20,则初始基已是最优基，求出最优解与最优值，计算停止；否则转入45.按书上方法换基，得新基6.变换出新基的单纯形表，转入3开始重复进行，直到得到最优解。四、对偶变量的经济解释1.在资源分配问题中，每种资源变化一个单位，对总利润将产生多大影响？2.什
8、么是影子价格？3.影子价格有什么作用？五、灵敏度分析分析所给问题数据发生变化时，最优解、基会发
