《运筹学完整教案.docx》由会员分享，可在线阅读，更多相关《运筹学完整教案.docx（81页珍藏版）》请在课桌文档上搜索。
1、第一章线性规划与单独形法1、教学计划第T次谋坤时授课章节绪论：第一章第I节、第2节、第3节授课方式c7理论课讨论课。实验课口习题课O其他课堂教学目的及要求了解线性规划模型的背景、掌握建模方法以及线性规划的标准形式。掌握两个决策变量线性规划问题可行域（凸集）、最优解的位置；了解无解（无界解，无可行解）、有解（唯解.无穷名个解）的n何育义C课堂教学重点及难点点：线性规划的数学侵型及其标准形。在数学模型中,要求熟悉矩阵形式；在标准形中,要求学生掌握非标准形式的几种具体情形及其相应的标准化方法：如何用几何的万法求两个决策变量的线性规划问题的最优解。难点：线性规划的基本概念,例如基、基安泰、基解、基可行
2、解和可行基；多个最优解如何表示。教学过程教学过程教学方法及手段31运筹学模型，运筹学发展历史与现状,研究方法；考核方法与教学大纲等。1.1 线性规划问题及其数学模型线性规划的数学模型：变量的确定、约束条件与目标函数。1.2 线性规划同建的标准形式线性规划的标准形式及非标准形式的标准化处理。13或性规划问题的解基、基变量，基解、基可行解和可行基。多媒体讲解实例讲解2R课一时授课生节第一章第4节授课方式CN理论课讨论课口实验课。习题课其他课堂教学目的及要求掌握单纯形法思想以及具体操作过程。课堂教学重点及难点点：单纯彩法迭代过程：（1）换入基变量的确定；（2）换出基变量的确定；（3）判定当前解已经最
3、优。难点：单纯形法思想。教学过程教学过程教学方法及手段1单独形法单纯形数表的构造，要注感代数形式和表格形式的一一对应性。单纯形法迭代过程：（1）换入基变量的确定；（2）换出基变量的确定；（3）判定当前解已经最优。多媒体讲解实例讲解授课至节第一章第5节授课方式。、理论课口讨论课。实验课。习题课0其他课堂教学目的及要求掌握人工变量法的基本思想以及大M法和两阶段法的求解。课堂教学重点及难点点：人工变量法的基本思想。难点：大M法和两阶段法的求解。教学过程教学过程教学方法及手段15单触形法的进一步讨论及小结人工变量法的思想,大M法和两阶段法的求解思路和步骡。单纯形法小结多媒体讲解实例讲解2,课件1.1线
4、性规划问题及其数学模型然性规划模型的建立就是将现实问题用数学的语言表达出来。例1:某工厂要安樗生产【、Il两种产品，每华位产品生产所需的设备、材料消耗及其利润如下表所示。问应如何安樗生产计划使工厂获利最多?IIl设备I28台时原材料4O16kgA原材料BO412kg单位产品的利润（元）23解：设生产产品I、H的数量分别为X和X2首先,我们的目标是要荻得最大利润,即maxz2x3xI2其次，该生产计划受到一系列现实条件的约束，设备台时约束：生产所用的束备台时不得超过所拥育的得备台驹1.即x2x812原材料约束：，生产族用的两种原材号A,-R不得超过的用有的原材粮总数.04x16I4x122非负约
5、束：生而的用品数的需为乐免的T即X,xOI2由此可指该问题的数学规划模型：maxz2x3xI2X2x8I24x164,122XKOI2总结:线性规划的一般建模步骤如下：(O确定决策变量确定决策变量就是将问题中的未知量用变量来表示，如例1中的X和、2。确定决策变量是建立数学规划模型的关键所在。(2)确定目标函数确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。(3)确定约束条件福现实的约束用数学公式表示出来。线性规划数学模型的特克(1)有一个追求的目标,该目标可表示为一组变量的线性函数,根据问题的不同.追求的目标可以是最大化,也可以是最小化。(2)问题中的约束条件表示现实的限制,可以用
6、线性等式或不等式表示。(3)问题用一组决策变量表示一种方案,一般说来，问题有多种不同的备选方案,线性规划模型正式要在这众多的方案中找到最优的决策方案(便目标函数最大或最小I从选择方案的角度看,这是规划问题，从目标函数最大或最小的角度看.这是屐优化问题。1.2线性规划问题的标准形式根据问题的性质，线性规划有多种形式，目标函数有要求最大化的，也有要求最小化的；约束条件可以是或、的不等式,也可以是三？虽然决策变量一般是非负的，但也可是无约束的，即.可以在(*)取值。为了分析问题的简化，一般规定如下的标准形式：maxZCXCXCXI122nnaxax.abHI122Inn1axax.aXb211222
7、2nn2axax.白bml1m22mnnmx,x012n非标准形式转化为标准形式：(I)若目标函数要求实现最小化minz.则可令zz,可将原问题的目标函数转化为max%可。(2)若约束方程为“则可在的左边加上非负的松弛变量：若约束方程为“贝阿在“”的左边减去非负的剩余变量。(3)若存在取值无约束的变量X.则可令XXX耳EX,OkICkkkk例：将如下问题转化为标准形式：minzX2x122x3x6I2XX412XX3XIO,X无约束2解：首先，用X3x2其中XF4H其次,在第一个约束条件的左端加上非负的松弛变量弋：再次，在第二个约束条件的左端减去非负的剩余变量X；6最后,令zz,路求minz改
8、为求maxZ由此,可得标准形如下：maxz,X2x2xOxOx1345(2x3x3xx61345XXXX41346XXX3134X)XH,x,x01345613线性规划问题的解首先.符线性问题的标准形式用矩阵和向量形式表示如下:其中,C(Cf 2=nxK可行解和最优解maxz CXAX(XK,.X)T12a11aA21amlbb,h)rma12a222nmn满足约束条件的所有解X(Xl2,rr成酒线性规划问题的可行解,其中,使目标函数达到最大的可行解成为最优解。2、基和基解设A为约束方程组的mn维矩阵.其秩为m。设B为矩阵A中的mm阶非奇异子矩阵(IBP).则称B为线性规划的一个基。不妨设前m
9、个变量的系数矩阵为线性规划的一个基.则XB(X1,xZ*力对应于这个基的基变量。用高斯消去法可求得一个解该解得非零分量的数目不大于方程个数m,称X为基解。3、基可行解若基解X满足非负约束.则称其为基可行解。4、可行基对应于基可行解的基.成为可行基。1.4单纯形法一、单纯形表考察一种最简毋的形式：目标函数最大化、所有约束条件均为利用所有约束条件化为等号的方法，在每个约束条件的左谶加一个松弛变量,并整理.重新对变量及系数矩阵进行编号,得Xa X .a x bI Ijnl m 1In n xa x2 2jn I m 1ax.axmjn1m1mnn0,jINn将其与目标函数的变换形式ZCqCX2FCX
10、CXmm1inI,FXQSMn1个nnm变*m1个方程的方程组。若将Z看成不参与基变换的基变型它与XKJ1的系数仲成一个基.利用初等变换招Cf2，.G变割零，则可得ZXX.XX.Xb12mmInO1O.OaaIjn1In001.0a,n1a2n000.1aabm,m1innmmmm100.0cca.ccacbm1ii1unlnlti1Hiii1据此,可设计如下的数表CcCCCjImmInCXbXXXiXBB1m1nmcXb1aa111Ijn1In1cXb0.0aa222Zm12n2cXb01aammmm1rnnmm0.CZjjccaccamIiim1iIniini1XB列表示基变型,在这里为X
11、TXm;Cfy为基变量XiK犷X对应印价值系数；b列为约束方程的右端项；Cj行为所有变空的价值系数；i列的数字是在确定换入变量后,按规则计算后填入；最后一行为各变量的检验数，尤其要注意的是非基变量的检给教。例.求解maxz2x3x由于X1和X的检验数大于零.表明上述解不是最优解,由于X2的检验数更大.所以,先以X2为换入变量。根据规则,可确定入jijijmX.bj12n,yjiInXij*iili2rm,jxOmn个变量.mn个约束方程，但由于总产量等于总销量的关系存在，所以，独立的约束万程为mn1.因此,其可行解中的基变基个数必然是rnnIo系数矩阵：变量X的系数向量P除第i个分量和第mj个
12、为i外其余为零。jy3.2 运输何题的求解：表上作业法表上作业法实际上是单纯形法在求解运输问题时的一个简化，主要步骤：（1）找出初始基可行解：最小元素法和伏格尔（VOgeD法最小元素法：优先满足运价最小的供销关系产量（吨）A73销量（吨）3B3B4产量（吨）3107284105956BB产量（吨）j43107(3)(1)Aj7g10S9(6)(3)销量（吨）3656BIB1B3B4产至（吨）产地A437A2314A3639销（吨）3656伏格尔法：优先满足最小运价与次小运价差值最大的行、列中的最小运价所对应的供销关系.BBB3B4行差产地AI3113100A19281AS7g1051列差25I
13、3（2）求各非基变量（空格）的检验数。闭回路法：首先找到与空格对应的闭回路,规则是从要检验空格出发用水平或垂直线向前滑,碰到数字格转90度（也可不转.空格处绝不转）,最后回到出发空格形成闭回路。然后，在该空格处试着增加1单位运量,并保持平衡.在闭回路作相应的调整.调整后产量（吨）产蛋（吨）如空格AB的检验数:7*1-5*1+10*1-3*1+2*1-1*1=103I空格AB的检验数：8*1-2*1+3*I-IO*1=-I24位势法：巴)0,可得构造位势Uq12皿)和V(j1).由基变量的检验数CCjjUjV,任取Uj(i12m)、V(jjUn鼠中之T嗫可求得其他U(iVJj耳：最后,由CiVj
14、)可求得个非基变量(空格)的检晚数。BBB3B4U产地、AI3-(-8+10)11.(10.1)310IOAt19-(9-1)28-(9+0)9A37-(-8+5)4IO-(-7+5)55V-8-70(3)若存在检验数为负的空格，用闭回路法进行调整，检匏数最小的空格优先调整。调整时，以相应的空格位调入格(以它对应的非基变量为换入变量),以相应的闭回路进行调整.调入最为闭回路中数字格中所能调出量的最小者。产聿(吨)三、运输问题的特殊情况：1、多重解当非基变量的检验数为零时,会出现多重解。2、退化当在某空格处填入数值时.恰好该处供应量等于需求里.在此填入相应的数值时须同时划去一行一列.此时,必须在
15、划去的该行、该列的任意空格处添一个零。闭回路调整时,如出现两个或两个以上调出格的数值相等.此时只能选择其中一个作为调出格,另一个格中必须填零。3.3 产销不平衡的运输何闻相对于标准形式的运输问题,产销不平衡问题的求解关键在于将其转化为标准形式的运输问题,即产销平衡问题。如果是产量大于销量,则可增加一个虚拟销地,任何运往虚拟销地的产量等向于就地储存.因此,所有产地运往虚拟销地的运费为0。如果是销量大于产量,则可增加一个虚拟产地,由虚拟产地运往各销地的运量实际上就是供给的缺口,表示现实中没有实际的供给，因此,由虚拟产地运往各销地的运费为产销不平衡问题转化为产销平衡问题之后,利用表上作业法进行求解的
16、思路和步骤和前一节的内容完全相向。BBB4B5产至（吨）1131007928044105096533如果存在某些特定的约束，如某地存在一个最低的需求,则应注意该部分不能由虚拟产地供给.即,虚取产地运往该地的单位运输费用应用是一个很大的正数M”需求地区1234产里A1613221750B1413191560C192023M50D50最低需求30700IO最高需求50703060化0巴厂需求IBE(r1234,4,产量A16161322171750B14141319151560C19192023MM50DM0M0M050销虽30207030IO50第四章目标规划h教学计划第5次课4学时授课堂前第四
17、里授课方式口僧论课。讨论课口实验课口习题课。其他课堂教学目的及要求了解目标规划的数学模型、目标规划的图解法，掌握目标规划数学模型的建立方法及其单纯形解法和灵叙度分析。课堂教学重点及难点点：目标规划的数学模型特征，建立目标规划的数学模型，目标规划的单纯形法及其灵敏度分析。难点：目标规划数学模型的建立、单纯形解法及灵敏度分析。教学过程教学过程教学方法及手段4.1 目标规划的数学模型目标规划数学模型的特征4.2 目标规划的图解法两决策变量目标规划的图解法。4.3 目标规划的单触形解法及灵敏度分析目标规划的单纯形法与灵皴度分析。多媒体讲解实例讲解2、课件4.1 目标规划的数学模型前面所讲的线性规划模型
18、是在一种静态、理想环境中的最优决策行为。但现实决策的背景要复杂得多,某些约束条件、目标均是“软”的。目标规划数学模型具有下列特征：(1)对于决策目标来说，它允许一定的偏差，这直接表现为决策变量可以有某种偏差d或cl；d为正偏差变量，表示决策超过目标值的部分.d为负偏差变星.表示决策未达到目标值的部分。考虑到决策值不可能超过同时又未达到目标值,所以,dd(2)绝对约束和目标约束绝对约束是指必须严格满足的等式约束和不等式约束，如线性规划中的约束,不能满足这些条件的即为非可行解。目标约束则可将右端项视为要达到的目标,但允许发生证或负的偏差，因此在这些约束中加入正、负偏差变量。在线牲规划的硬约束中加入
19、正负偏差变(加上负差变、双去正偏差变格符号变为等号就转变为目标约未。(3)优先因子(优先等级)与权系数在现实的决策背景下，决策者往往具有多个目标,但这些目标是有主次轻重的不同。赋予优先因子,规定Pkpkl.表示k级目标比k1级具有绝对的优先权,在优先保证卜级目标时可不考虑k1级目标。权系数可区别同级目标中两个目标的差异。(4)目标规划的目标函数目标规划的目标函数由各目标约束的正负偏差变量和赋予相应的优先因子向造而成。当每一目标给定后，决策者的要求是尽可能地缗小偏离目标值。因此,目标规划的目标函数只能是mnzRdd).其基本形式有三种：要求恰好达到目标值.郎正负偏差都要求尽可能地小，此时minz
20、f(dd)要求不超过目标值.即允许达不到目标值,就是正偏差要尽可能地小,即minzf(d)要求超过目标值,即超过量不限，就是负储差要尽可能地小，此时minzf(d)4.2 目标规划的图解法与线性规划相同,具有两变量的目标规划也可以用图解法迸行求解。具体步骤与线性规划的图解法相似。4.3 目标规划的单纯形解法及灵敏度分析(1)目标规划的单纯形解法目标规划的单纯形解法与线性规划的单纯形解法基本相似,当然也具有一些独特之处：由于目标函数都市要求最小化，所以Cjzj为最优准则；非基变量的检验数中含有不同等级的优先因子,即czaPjj勾kj12.n,k12K由于Pl2P，因此，检验数的正、份取决于其中所
21、含最高优先因子的系数的正负。K例略。(2)灵敏度分析目标规划的灵敏度分析与线性规划也很相似,但还有优先因子的变化问题。当优先因子发生改变时,实际上就是将最终单纯形数表中各有优先因子对应的行向量交换位置即可.然后计算它们的检验数.看是否还需要进一步的处理。第五章整数规划1、教学计划B_6_授课章节第五章授课方式理论课讨论课口实给课习题课其他课堂教学目的及要求掌握整数规划的数学模型、特点以及求解方法：用匈牙利法求解指派问题。课堂教学重点及难点点：用匈牙利法求解指派问题。难点：用匈牙利法求解指派问题。教学过程教学过程教学方法及手段5.1 整数规划问题的提出及一般求解方法整数规划的数学模型及特点,一般
22、求解方法简介：分支定界法和割平面法。5.2 指湫问题指派问题的匈牙利法求解。2逾住多媒体讲解实例讲解5.1整数规划的数学模型的提出及一般求解方法要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。M模型为：Max（或min）z=jax（,）bi12mijijis.tXjojl2nXKiX中部分或全部取整数1 Zn若要求决策变量只能取值0我的整数施麻为31型整数线性规划。对于一般的整数规划问题,可采用分支定界法和割平面法进行求解C5.2指派问题及其应用一.指派问题的标准形式及数学模型在现实生活中,有各种性质的指派问题。例如,有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选
23、择若干个投标者来承包：有若干班级需要安排在各教室上课等等。诸如此类的问题,它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。由于指派问题的多样性，有必要定义指派问题的标准形式。Gj1,2, n), u指派问题的标准形式（以人和事为例）是管个人和“日已知鹿i个人作第J件雌费用为C要求确定人和之间的一一对应的指证方案，是完成这n件的总费用最少。为了建立标准指派问题的数学模型,引入个Gl变量:O若不指派第i人作第j事XU1若指派第i人作第j件事这样.问题的数字模型可写成nnminzcx（5.1）(5.2)(5.3)(5.4)UijiljlX1j12niJi1x1i12nJ.ijX
24、QliJUn其中，（5.1）表示每件事必优且只有一个人去做,（5.2）表示每个人必做且只做一件事。注：心指派问题是产量（a.销量（bp相等,I,j=12.n的运输问题。3有时也称C为第i个人完成第j件工作所需的资源数.称之为效率系效（或价值系数）并称矩阵C=(C)ijn nC11C21C12C 22CInC2n(5.5)CnlCn2Cnn为效率矩阵（或价值系数矩阵）。并称决策变量排成的nxn矩阵x=()X21X12X22X2n(5.6)XnlXn2Xnn为决策变矩阵（5.6）的特征是它有n个1,其它都是0。这n个1位于不同行、不同列。每一种情况为指派问题的一个可行解。关n!个解。其总的费用z=
25、CX这里的。表示两矩阵对应元素的积.然后相加。问题是：把这n个!放到X的02个位置的什么地方可使耗费的总资源最少？（解最优）例1已知效率矩阵50202300c=05674800010 00 0 1010000 0 0 1则0100x=o001)10000010都是指派问题的最优解例12/P-149：某商业公司计划开办五冢新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。己知建筑公司A(i=l,2,.5)对新商店B(1,2,.5)的建造费用的报价(万元)为C(ij=ij2,5)见表5-9。商业公司应iiij当对5家建筑公司怎样分派建筑任务，才能使总的建筑费用最少？当Ai承建Bj时i,
26、j=l,25当Aj不承建Bj时则问题的数学模型为Minz=4xll+X12+.+10x54+X555X1j125Uiis.tx1i125ji,XQIiJI25若看成运输问题,且XiF)上所述.A(4)XIl(8)X12(7)X13(15)X14(12)X151A(7)X21(9)X22(17)X23(14)X24(10)X251A(6)X31(9)X32(12)X33(8)X34X351A4X41(7)X42(14)X43(6)X44(10)X451N(6)X51(9)X52(12)X53(IO)X54X551所选的公司数111115当然,第一行的1应放在（1.1）位置.此位置同时是第一列的费
27、用最小。但一般情况下没有这么好。需找一适合一般的方法。二.匈牙利解法原理：虽然指派问题是一类特殊的整数规划问题.又是特殊的o规划问题和特殊的运输问题.因此,它可以用多种相应的解法来求解。但是,这些解法都没有充分利用指派问题的特殊性质,有效地减少计算量。1955年.库恩（W.WKuhn）提出了匈牙利法。定Ell:设指派问题的效率矩阵为C=（C）,若将该矩阵的某一行（或某一列）的各个元素都减去统一常数t（I可ijnn正可负）.得到新的效率矩阵C（C）.则以C为效率矩阵的新的指派问题与原指派问题的最优解相同。但其最优解jnn比原最优解之减少1.7证明：设式（5.1）（5.4）为原指派问题。现在C矩阵的第k行个元素东减去同一常数I.记新的指派问题的目标优数为乙.则有Z= ex =jjil jlili jlnnnnCX+CX=CX+（ct）xUUKjkjijijkjk
