运筹学课程总结

运筹学课程总结总结内容：一、运筹学简述（一）运筹学定义（二）运筹学工作步骤（三）运筹学的应用二、运筹学相关理论与方法（一）线性规划（二）运输问题（三）目标规划（四）整数规划求解）五）动态规划三、运筹学应用案例分析（用matlab求解）、运筹学简述（一） 运筹学的定义运筹学是一门应用科学，至今还没有统一且确切的定义。莫斯和金博尔曾对运筹学的定义是：“为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。”它强调科学方法，以量化为基础。另一定义是：“运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。'中国百科全书给出的定义是：“运筹学是用数学方法研究经济、民政和国防等部门在内外环境约束的条件下合理分配人力、 物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案。”如论如何定义，都表明着，运筹学是为提供最优化方法、最佳解决方案的科学。（二） 运筹学的工作步骤龜改型修模1建立数学模型：认清目标和约束;2、寻求可行方案：求解;3、 评估各个方案：解的检验、灵敏度分析等;4、 选择最优方案：决策；5、方案实施：回到实践中;6、后评估：考察问题是否得到完满解决。（三）运筹学的应用运筹学在各个领域的应用非常广泛，主要有以下几个方面：1、生产计划：生产作业的计划、日程表的编排、合理下料、 配料问题、物料管理等；2、 库存管理：多种物资库存量的管理，库存方式、库存量等；3、运输问题：确定最小成本的运输线路、物资的调拨、运输、工具的调度以及建厂地址的选择等；4、人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配建立人才评价体系等；5、市场营销：广告预算、媒介选择、定价、产品开发与销售、计划制定等6财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等；7、设备维修、更新，项目选择、评价，工程优化设计与管理等、运筹学相关理论与方法一)线性规划1简述线性规划是运筹学的一个重要分支，它是现代科学管理的重要手段之一，在合理利用一定规格的原材料、不同成分原材料的合理配比、运输方案的优化选择以及劳动力安排等方面有非常广泛的应用。线性规划问题一般包括两个方面的问题，即求最大值(max)和求最小值(min)。2、线性规划的数学模型结构(1)变量：决策系统中或实际问题中有待确定的未知因素；(2)目标函数：决策者对决策问题目标的数学描述，变量的线性函数；(3)约束条件：实现目标的限制因素，变量的线性等式或线性不等式，一般为：大于或等于(》)、等于(=)和小于或等于(《)。线性规划数学模型的一般形式为：目标函数max(min)z=clxl+c2x.H—+cnx目标函数(71]x1+al2x2+-+ [如兀i+a22X2+…+如斗< (='>)*27 > 束条%叫、+叫+…+amnXV(=，件>)bmm片工“〉(V)0.free -〒价值系数，口旷技术系数，歼限额茶数。3、线性规划问题的求解方法1)图解法图解法这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。（2）单纯形法单纯形法对于多变量的线性规划问题，是一种常用解法。它是通过一系列数学迭代过程，逐步求得线性规划问题的最优解。单纯形法常见形式有两种：大M法和两阶段法。利用单纯形法求解线性规划问题可以分两种：求最大值和求最小值。①单纯形法的基本思路②单纯形法的基本求解步骤：引入辅助变量，将现行规划模型转换成标准形式；确定基础可行解，列出初始单纯形表；确定迭代变量，进行迭代变换。（3）对偶单纯形法对偶单纯形法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯形法。它和单纯形法的主要区别在于：单纯形法在整个迭代过程中，始终保持原问题的可行性，即常数列》0,而检验数由负分量逐步变为全部》0,即同时得到原问题和对偶问题的最优解。对偶单纯形法则是在整个迭代过程中，始终保持对偶问题的可行性，即全部检验数》0,而常数列由有负分量逐步变为全部》0,即同时得到原问题和对偶问题的最优解。（二）运输问题1简述一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。2、运输问题的数学模型结构（1）决策变量；（2）约束条件；（3）目标函数在产销平衡的条件下，运费最小的调运方案的数学模型为:mnminz_''CijXjijji4j*mEXj=bjj=1,2，…,nins.t.«送X.=ai=1,2，…,mjjijXj>0j②当产大于销时，v-bj运费最小的数学模型为:②当产大于销时，v-bj运费最小的数学模型为:iAn为Xjjjm送 Xijij(i=12,m)(j72,..,n)iXjKoj③当产小于销时，’•imna占 jdjdbj,数学模型为:nZX.■a.,j力(i：二1,2,,m)mzX..b,lj=bi=1X..-0ij(j==1,2,,n)它针对3、运输问题的求解方法：表上作业法表上作业法是一种求解运输问题的特殊的方法，其实质是单纯形法,运输问题变量多，结构独特的情况，大大简化了计算过程的求解方法表上作业法的基本思路和步骤：它针对①找出初始基可行解。方法有：西北角法、最小元素法、伏格尔法。最优解的判别。方法有，闭回路法、位势法(确定初始基可行解C得到新的基可哲解(确定初始基可行解C得到新的基可哲解J（确定变量）i广*代「沿回路调整运量确定离基变量）当产销不平衡时，这时就需要通过增加一个假象仓库或者假象生产地来化成产销平衡的问题。（三）线性目标规划i简述目标规划是线性规划的一种特殊应用，能够处理单个主目标与多个目标并存，以及多个主目标与多个次目标并存的问题，在现有的资源条件下，在多个目标中去寻求满意解，使得实际目标完成的总体结果与事先制定目标的差距最小。2、目标规划的数学模型目标函数：minz目标函数：minz=EP正㈣+创帀力LK丨=1kz!「门送Ck.X.+d厂一dk+=gk,k=1,K.二kjj k …，j满足约束条 比na.乂兰（二，耳b,i m件： jd：jjXjAO,j=:，…,n血匸血，k=：,2,33、求解方法：图解法和单纯形法四）整数规划1简述整数规划指整数线性规划，即要求部分变量或全部变量为整数的线性规划分为纯整数规划与混合整数规划两大类2、整数规划的一般形式max（min）z-'cjxjj4n'ajXj乞（=,_）b（i=1,,m）jXj-0 （j", ,m）xj中部分或全部取整数3、整数规划的求解方法（1） 分支定界法：用于解纯整数或混合的整数规划。步骤：分支：将原问题分为两个子问题；定界：确定最优目标范围以减少搜索次数。（2） 割平面法通过增加新的约束来切割可原问题伴随规划的可行域，使它在不断缩小的过程中，将原问题的整数最优解逐渐暴露且趋于可行域极点的位置，这样就有可能用单纯形法求出。步骤：a用单纯形法解松弛问题，得到最优单纯形表；b.求一个割平面方程，加到最优单纯形表中，用对偶单纯形法继续求解；若没有得到整数最优解，则继续作割平面方程，转第二步。（五）动态规划1、简述动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。动态规划是求解某类问题的一种方法，是考查问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。动态规划应用广泛，可以用来解决最优路劲问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题等等，所以它是现代企业管理中的一种重要的决策方法。2、动态规划方法的基本思想（1）动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件。要做到这一点，必须先将问题的过程分成几个相互联系的阶段，恰当地选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每个子问题的求解中，均利用了前面的子问题的最优化结果，依次进行，最后一个问题所得的最优解，就是整个问题的最优解。（2） 在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与改段的最优选择答案一般是不同的。（3） 在整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线。三、运筹学应用案例举例（一）线性规划应用案例分析某棉纺织厂需要拟定一种针织纱的混棉配方方案。已知原棉共有品种6个,他们的物理性能、单价、质量指标等如下表所以。现要求在满足质量指标的前提下，拟定一个新的配棉方案（各种原棉在混棉中所占的百分比），使混棉的成本最低。项目原棉品种质量要求A1A2A3A4A5A6品质1200270260210230250》230品质2600550610580660590》580品质3130100601008080《100品质4151716131616《15单价（元/千克）300300330310300300最小混用上限（％）202015202520解：1、设定变量设方案中各种原棉的配比为Xi，其中i=1,2,3,4,5,6,即表示上表中所列的原棉品种A1，A2，A3，A4，A5，A6的百分比，共6个变量。2、 确定目标函数设新方案的混棉单位成本为C,则C=300XI+300X2+330X3+310X4+300X5+300X63、 建立约束条件（1）品质指标的约束：①品质指标约束1:200XI+270X2+260X3+210X4+230X5+250X6》230②品质指标约束2:600x1+550x2+610x3+580x4+660x5+590x6》580品质指标约束3:130xi+100x2+60x3+100x4+80x5+80x6《100品质指标约束4:15x1+17x2+16x3+13x4+16x5+16x6《16(2)配比比例的约束条件：配比之和为100%X1+X2+X3+X4+X5+X6=100%各种原棉配比的比例上限：X1《20%；X2《20%；X3《15%；X4《20%；X5《25%；X6《20%xi>0(i=1,2,3,4,5,6)贝U,该线性规划的数学模型为：MinC=300x什300x2+330x3+310x4+300x5+300x6200xi十270x2十260xA210x4+230x5+250x6X2301 2 4 5 6600x1+550x2+610x3+580x4+660x5+590x6>580130x1+100x2+60x3+100x4+80x5+80x6<10015X1+17x2+16x3+13x4+16x5+16x6兰16X1+X2+X3+X4+X5+X6=1刃_0.2X2兰0.2X3兰0.15X4兰0.2X5兰0.255X6兰0.2/1,X2,X3,X4,X5,X6Z0用matlab求解该线性规划问题：1、输入下列数据系数矩阵：A=〔-200-270-260-210-230-25Q-600-550-610-580-660-590；130100601008080151716131616100000;010000;001000；000100;000010；000001〕02系数矩阵：Aeq=〔111111〕⑶成本矢量:f=〔300；300；330；310；300；300〕(4)右端矢量:b=〔-230；-580；100；16；0.2；0.2；0.15；0.20.25；(5)右端矢量:beq=〔1(6)变量下界:lb=〔0;0;0;0;0;0;0〕2、调用函数〔x,fva,exitflag〕=linprog(f,A,b,Aeq,beq,lb,〔〕)输入的命令为：»A=[-2Q0-270-260-210-23Q-250;-500-550-610-5S0-660-590:13010Aeq=[lII1I1]f=|[300;300:330;310:300:300]b=[-230;-580;100;16;0.2;0.2;0.15;0.2;0.25;0,21beq=[l]lb=[000000][x3fvaljexitflag]=linprog(fAjb,Aeq,beq,lbj,[]j得出结果：当x满足xi=0.2,X2=0.2,X3=0,X4=0.15,X5=0.25,x6=0.2时，成本最低，且成本C=301.5运输问题应用案例分析某地有三个有色金属矿A1、A2、A3，生产同一种金属矿石，A1矿的年产量为100万千克，A2矿为80万千克，A3矿为50万千克。矿石全部供应四个冶炼厂，B1厂的全部需求量为50万千克，B2为70万千克，B3为80万千克，B4为30万千克。总产量恰好等于总需求量，矿石由各矿山运到冶炼厂的单位运价见下表。如何安排运输，使各矿山的矿石运到冶炼厂，满足各厂的需要，且总运费最小？运价表 单位：元/千克B1B2B3B4A11.520.33A270.81.42A31.20.322.5解：该问题为产销平衡的运输问题，需要制定最优运输计划使总运输费最小1、设定变量设Xjj表示第i个矿山运到第j个冶炼厂的矿石量(万千克)，见下表所列B1B2B3B4r产量A1X11X12X13X14100

A2X21X22X23X2480A3X31X32X33X3450"jTFf日.需要量507080302302、确定目标函数问题的目标是求总运输费用最小，设Z表示总运输费用，则MinZ=1.5Xii+2Xi2+0.3Xi3+3Xi4+7X2i+0.8X22+1.4X23+2X24+1.2X3i+0.3X32+2X33X33+2.5X343、确定约束条件X1什X12+X13+X14=100X21+X22+X23+X24=80X31+X32+X33+X34=50X11+X21+X31=50X12+X22+X32=70X13+X23+X33=80X14+X24+X34=30Xij》0,i=1,2,3;j=1,2,3,4该运输问题的数学模型为：MinZ=1.5X11+2X12+0.3X13+3X14+7X21+0.8X22+1.4X23+2X24+1.2X31+0.3X32+2X332X33+2.5X34X1什X12+X13+X14=100X21+X22+X23+X24=80X31+X32+X33+X34=50X11+X21+X31=50X12+X22+X32=70X13+X23+X33=80X14+X24+X34=30Xij》0,i=1,2,3;j=1,2,3,4用matlab求解该运输问题输入命令：f=[1.520.3370.81.421.20.322.5]Aeq=[111100000000100010001000010001000100001000100010000100010001]beq=[100805050708030]lb=[000000000000][x,fval,exitflag,output,lambda]=linprog(f,[],[],Aeq,beq,lb)输出数据为：x-20.00000,000080