《运筹学》复习参考资料知识点及习题

第1页共30页第一部分线性规划问题的求解一、两个变量的线性规划问题的图解法概念准备定义满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义达到目标的可行解为最优解。图解法图解法采用直角坐标求解X1横轴；X2竖轴。1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；注求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。参考例题（只要求下面这些有唯一最优解的类型）例1某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示ABC利润（万元）甲乙3599537030有效总工时540450720问该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大设备消耗产品第2页共30页（此题也可用“单纯形法”或化“对偶问题”用大M法求解）第3页共30页解设X1、X2为生产甲、乙产品的数量。MAXZ70X130X2ST0723945502112XX，可行解域为OABCD0，最优解为B点。由方程组解出X175，X215720394551XX（75，15）T2XMAXZZ707530155700、第4页共30页例2用图解法求解MAXZ6X14X2ST078022112XX，解可行解域为OABCD0，最优解为B点。由方程组解出X12，X26810212XX（2，6）T1XMAXZ624636、第5页共30页例3用图解法求解MINZ3X1X2ST08215341121XX，解可行解域为BCDEFB，最优解为B点。由方程组解出X14，X2125241X54X（4，）T2XMINZ341151、第6页共30页二、标准型线性规划问题的单纯形解法一般思路1、用简单易行的方法获得初始基本可行解；2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入3；3、根据L规则确定改进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入3，直至最优解。具体做法（可化归标准型的情况）设已知MAXZC1X1C2X2CNXNSTNJXBXAAXBXAAJMMN，210212221211对第I个方程加入松弛变量XNI，I1，2，M，得到NJXBXXAABXAAJMNMMNN，210212221211列表计算，格式、算法如下第7页共30页C1C2CNMCBXBBX1X2XNMLCN1XN1B1A11A12A1NMCN2XN2B2A21A22A2NMCNMXNMBNAM1AM2AMNMZ1Z2ZNM12NM注ZJCN1A1JCN2A2JCNMAMJ，（J1，2，NM）MIIJNAC1JCJZJ,当J0时，当前解最优。注由MAXJ确定所对应的行的变量为“入基变量”；由L确定所对应的行的变量为“出基变量”，行、列0MINIKAB交叉处为主元素，迭代时要求将主元素变为1，此列其余元素变为0。例1用单纯形法求解（本题即是本资料P2“图解法”例1的单纯形解法；也可化“对偶问题”求解）MAXZ70X130X2ST0723945502112XX，解加入松弛变量X3，X4，X5，得到等效的标准模型MAXZ70X130X20X30X40X5第8页共30页ST5,21,0720394551231JXXXJ列表计算如下7030000CBXBBX1X2X3X4X5L0X354039100540/31800X445055010450/5900X5720（9）3001720/9800000070300000X330008101/3300/83750X4500（10/3）015/950/10/31570X18011/3001/980/1/32407070/30070/9020/30070/90X318000112/5130X2150103/101/670X1751001/101/670300220/35700000220/3X（75，15，180，0，0）TMAXZ707530155700第9页共30页例2用单纯形法求解MAXZ7X112X2ST031325460921XX，解加入松弛变量X3，X4，X5，得到等效的标准模型MAXZ7X112X20X30X40X5ST5,21,0303546914231JXXXJ列表计算如下第10页共30页712000CBXBBX1X2X3X4X5L0X336094100360/4900X420045010200/5400X53003（10）001300/1030000007120000X324078/100102/5240/78/102400/780X450（5/2）0011/250/5/22012X2303/101001/1030/3/1010018/512006/517/50006/50X38400178/2529/257X1201002/51/512X2240103/254/28712034/2511/3542800034/2511/35X（20，24，84，0，0）TMAXZ7201224428三、非标准型线性规划问题的解法1、一般地，对于约束条件组若为“”，则加松弛变量，使方程成为“”；若为“”，则减松弛变量，使方程成为“”。我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值，则为非标准型。可作如下处理第11页共30页由目标函数MINZ变成等价的目标函数MAX（Z）NJJXC1NJJXC1令ZZ/，MINZMAXZ/2、等式约束大M法通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价值系数为M，M是很大的正数，从原理上理解又称为“惩罚系数”。（课本P29）类型一目标函数仍为MAXZ，约束条件组与。例1MAXZ3X15X2ST01823411XX，解加入松弛变量X3，X4，得到等效的标准模型MAXZ3X15X2ST4,321,08324131JXXJ其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量X5，得到MAXZ3X15X2MX5第12页共30页ST5,21,08324131JXXXJ单纯形表求解过程如下3500MCBXBBX1X2X3X4X5L0X34（1）01004/140X41202010MX5183200118/363M2M00M3M352M0003X14101000X4120201012/26MX560（2）3016/2332M33M0M0533M003X14101004/140X4600（3）116/325X23013/201/23/2/39/2359/205/2009/20M5/2X121001/31/330X320011/31/3第13页共30页5X260101/203503/21360003/2M1X（2，6，2，0）TMAXZ325636类型二目标函数MINZ，约束条件组与。例2用单纯形法求解MINZ4X13X2ST0123642211X，解减去松弛变量X3，X4，并化为等效的标准模型MAXZ/4X13X2ST4,321,0362132JXXJ增加人工变量X5、X6，得到MAXZ/4X13X2MX5MX6ST6,21,012342641532JXXXJ第14页共30页单纯形表求解过程如下第15页共30页400MMCBXBBX1X2X3X4X5X6LMX5162（4）101016/44MX61232010112/265M6MMMMM5M46M3MM003X241/211/401/404/1/28MX64（2）01/211/214/222M3/233/4M/2MM/23/4M2M5/20M/23/4M3/43M/203X23013/81/43/81/44X12101/41/21/41/2431/85/41/85/417001/85/4M1/8M5/4X（2，3，0，0）TMINZMAXZ/（17）17第16页共30页四、对偶问题的解法什么是对偶问题1、在资源一定的条件下，作出最大的贡献；2、完成给定的工作，所消耗的资源最少。引例（与本资料P2例1“图解法”、P7例1“单纯形法”同）某工厂生产甲、乙两种产品，这些产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工时需要不同的工时，这些产品售后所能获得的利润值以及这三种加工设备因各种条件下所能使用的有效总工时数如下表ABC利润（万元）甲乙3599537030有效总工时540450720问该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大解原问题设X1、X2为生产甲、乙产品的数量。MAXZ70X130X2ST0723945502112XX，设备消耗产品第17页共30页将这个原问题化为它的对偶问题设Y1、Y2、Y2分别为设备A、B、C单位工时数的加工费。MINW540Y1450Y2720Y3ST3210059793132，IYYI用大M法，先化为等效的标准模型MAXW/540Y1450Y2720Y3ST5,21,030359793142JYYJ增加人工变量Y6、Y7，得到MAXZ/540Y1450Y2720Y3MY6MY7ST5,21,0303597931642JYYYJ大M法单纯形表求解过程如下第18页共30页54045072000MMCBXBBY1Y2Y3Y4Y5Y6Y7LMY670359101070/3MY730（9）53010130/910/312M10M12MMMMM12M54010M45012M720MM00MY660010/3（8）11/311/360/825540Y110/315/91/301/901/910/3/1/31030010/3M8M180MM/360MM/360015010/3M8M540MM/3600M/360720Y315/205/1211/81/241/81/2415/2/5/1218540Y15/61（5/12）01/241/81/241/85/6/5/122540572720135/2475/12135/275/201250135/2475/12135/2M75/2MY320/31011/61/61/61/6720450Y2212/5101/103/101/103/1036045072075157515570018000751575M15M该对偶问题的最优解是Y（0，2，0，0）T3最优目标函数值MINW（5700）5700第19页共30页五、运输规划问题运输规划问题的特殊解法“表上作业法”解题步骤1、找出初始调运方案。即在MN产销平衡表上给出MN1个数字格。（最小元素法）2、（对空格）求检验数。判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。（闭回路法）3、对方案进行改善，找出新的调运方案。（根据检验结果选择入基变量，用表上闭回路法调整即迭代计算，得新的基本可行解）4、重复2、3，再检验、再迭代，直到求得最优调运方案。类型一供求平衡的运输规划问题（又称“供需平衡”、“产销平衡”）引例某钢铁公司有三个铁矿和四个炼铁厂，铁矿的年产矿石量分别为100万吨、80万吨和50万吨，炼铁厂年需矿石量分别为50万吨、70万吨、80万吨和30万吨，这三个铁矿与四个炼铁厂的距离如下B1B2B3B4A1A2A3152033070814201232015问该公司应如何组织运输，既满足各炼铁厂需要，又使总的运输费用为最小（按吨公里计）解用“表上作业法”求解。先用最低费用法（最小元素法）求此问题的初始基础可行解炼铁距离铁矿厂第20页共30页B1B2B3B4产量S12080100708144420A2302030801253320332510A35050销量DJ50708030230230初始方案Z1520380703082020303503550（吨公里）对的初始可行解进行迭代（表上闭回路法），求最优解销地费用产地2080B1B3A1B2203030B1B3A2B250A3第21页共30页B1B2B3B4产量S120801007053814920A250308012320202510A3302050销量DJ50708030230230用表上闭回路法调整后，从上表可看出，所有检验数0，已得最优解。最优方案Z1520380850203012303201960（吨公里）解法分析如何求检验数并由此确定入基变量有数字的空格称为“基格”、打的空格称为“空格”，标号为偶数的顶点称为偶点、标号为奇数的顶点称为奇点，出发点算0故为偶点。找出所有空格的闭回路后计算它们的检验数，必须0，才偶点奇点IJIJIJCIJ得到最优解。否则，应选所有中正的最大者对应的变量XJ为入基变量进行迭代（调整）。检验后调整运输方案的办法是在空格的闭回路中所有的偶点均加上奇点中的最小运量，所有的奇点均减去奇点中的最小运量。重复以上两步，再检验、再调整，直到求得最优运输方案。类型二供求不平衡的运输规划问题销地费用产地2080B1B3A15030B2B4A23020B1B2A3第22页共30页若，则是供大于求（供过于求）问题，可设一虚销地BN1，NJJMIDS11令CI,N10，DN1，转化为产销平衡问题。若，则是供NJJMIDS11NJJMIDS11小于求（供不应求）问题，可设一虚产地AM1，令CM1,J0，SM1，转化为产销平衡问题。MINJJSD11（，2，M；，2，N）六、工作指派问题工作指派问题的数学模型假定有N项工作需要完成，恰好有N个人每人可去完成其中一项工作，效果要好。工作指派问题的特殊解法“匈牙利法”（考）解题步骤1、使系数矩阵（效率矩阵）各行、各列出现零元素。作法行约简系数矩阵各行元素减去所在行的最小元素，列约简再从所得矩阵的各列减去所在列最小元素。2、试求最优解。如能找出N个位于不同行不同列的零元素，令对应的XIJ1，其余XIJ0，得最优解，结束；否则下一步。作法由独立0元素的行（列）开始，独立0元素处画（）标记，在有（）的行列中划去（也可打）其它0元素；再在剩余的0元素中重复此做法，直至不能标记（）为止。3、作能覆盖所有0元素的最少数直线集合。作法对没有（）的行打号；对已打号的行中所有0元素的所在列打号；再对打有号的列中0元素的所在行打号；重复、直到得不出新的打号的行列为止；对没有打号的行画一横线，对打号的列画一纵线，这就得到覆盖所有0元素的最少直线数。未被直线覆盖的最小元素为CIJ,在未被直线覆盖处减去CIJ,在直线交叉处加上CIJ。4、重复2、3，直到求得最优解。第23页共30页类型一求极小值的匈牙利法（重点掌握这种基本问题）例1有甲、乙、丙、丁四个人，要派去完成A、B、C、D四项工作，他们完成的工时如下表ABCD甲乙丙丁61213410312147141316881210试问应如何分配任务可使总工时为最少解用“匈牙利法”求解。已知条件可用系数矩阵（效率矩阵）表示为（CIJ）10286347106240967182209715220971582使总工时为最少的分配任务方案为甲D，乙B，丙A，丁C此时总工时数W4371226例2求效率矩阵列约简任务工时人行约简标号甲乙丙丁ABCD第24页共30页的最优解。54326578910解5432657891032103所画（）0元素少于N，未2100321013得到最优解，需要继续变换矩阵（求能覆盖所有0元素的最少数直线集合）2100132未被直线覆盖的最小元素为CIJ1,在未被直线覆盖处减去1,在直线交叉处加上1。1024100224）（）（得最优解010类型二求极大值的匈牙利法MINZMAX（Z）标号列约简行约简标号第25页共30页（CIJ）（MCIJ）（BIJ），（CIJ）中最大的元素为MMAXZJIJIXJIJIXMJIJICJIJIC第一部分到此结束第26页共30页第二部分动态规划只要求掌握动态规划的最短路问题用“图上标号法”解决具体解题步骤请参看教材P103（这是本套资料少见的与教材完全相同的算法类型之一，务必看书掌握）学员们只有完全理解了这种作法（思路逆向追踪）才有可能做题，考试时数字无论如何变化都能作出正确求解第二部分到此结束第27页共30页第三部分网络分析一、求最小生成树（最小支撑树、最小树）问题破圈法任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。参考例题例求下图的最小生成树67941510V2V1V3V5V4V6328第28页共30页解用“破圈法”求得最小生成树为已得最小树，此时权W1245921为最小。二、最短路问题（有向图）TP标号法（狄克斯托算法）具