运筹学复习资料

运筹学复习一、单纯形方法（表格、人工变量、基础知识）线性规划解的情况：唯一最优解、多重最优解、无界解、无解。其中，可行 域无界，并不意味着目标函数值无界。无界可行域对应着解的情况有：唯一最优解、多重最优解、无界解。有界可 行域对应唯一最优解和多重最优解两种情况。线性规划解得基本性质有：满足线性规划约束条件的可行解集（可行域）构 成一个凸多边形；凸多边形的顶点（极点）与基本可行解一一对应（即一个基本 可行解对应一个顶点）；线性规划问题若有最优解，则最优解一定在凸多边形的 某个顶点上取得。单纯形法解决线性规划问题时，在换基迭代过程中，进基的非基变量的选择 要利用比值法，这个方法是保证进基后的单纯型依然在解上可行。换基迭代要求 除了进基的非基变量外，其余非基变量全为零。检验最优性的一个方法是在目标函数中，用非基变量表示基变量。要求检验 数全部小于等于零。“当x由0变到45/2时，x首先变为0,故x为退出基变量。”这句话是最1 3 3 小比值法的一种通俗的说法，但是很有意义。这里， x 为进基变量， x 为出基变 13 量。将约束方程化为每个方程只含一个基变量，目标函数表示成非基变量的函数。单纯型原理的矩阵描述。在单纯型原理的表格解法中，有一个有趣的现象就是，单纯型表中的某一列 的组成的列向量等于它所在的单纯型矩阵的最初的基矩阵的 m*m 矩阵与其最初 的那一列向量的乘积。最初基变量对应的基矩阵的逆矩阵。这个样子：所有的检验数均小于或等于零，有最优解。但是如果出现非基变量的检验数为 0，则有无穷多的最优解，这时应该继续迭代。解的结果应该是：X*= aX *+（1-a）X * （0=a0,且所有的a 0,对于极小化问题用+M）,这样只要基变量中还存在人工变量，目标函数 就不可能实现极值。两阶段法原理：第一阶段是据给定的问题构造其辅助问题，为原问题求初始 基本可行解。加上人工变量后，要求的就是人工变量退出，辅助问题是人工变量 之和的最小值必须为零。第二阶段是将第一阶段求出的最优解，作为第二阶段的初始基本可行解，然 后在原问题的目标函数下进行优化，以决定原问题的最优解。注意：单纯形法中1每一步运算只能用矩阵初等行变换；2. 表中第3列（b列）的数总应保持非负（三0）；3. 当所有检验数均非正（W0）时，得到最优单纯形表。若直接对目标求最 h,要求所有检验数均非负；4当最优单纯形表存在非基变量对应的检验数为零时，可能存在无穷多解；5 .关于退化和循环。如果在一个基本可行解的基变量中至少有一个分量 xB=0 （i=l,2,m），则称此基本可行解是退化的基本可行解。一般情况下，退 化的基本可行解（极点）是由若干个不同的基本可行解（极点）在特殊情况下合 并成一个基本可行解（极点）而形成的。退化的结构对单纯形迭代会造成不利的 影响。可能出现以下情况：进行进基、出基变换后，虽然改变了基，但没有改变 基本可行解（极点），目标函数当然也不会改进。进行若干次基变换后，才脱离 退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代次 数，使单纯形法收敛的速度减慢。在特殊情况下，退化会出现基的循环，一旦 出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。二、对偶问题和灵敏度分析对偶问题的基本性质：对偶问题（D）的对偶问题，是原问题（P）;若X/是问题 （P）的一可行解，Y/是问题（D）的一个可行解，则有:CXWY/b。若X*,Y*分别为问 题（P）和问题（D）的可行解，且CX*=Y*b ；则X*和Y*分别为问题（P）和问题（D）的最 优解。若问题（P）的目标函数值Z无上界，则问题（D）无可行解；若问题（D）的目标函数值W无下界，则问题（P）无可行解。对偶定理：若问题（P）和问题（D） 之一有最优解，则另一个问题也一定有最优解，且目标函数值相等。由对偶定理可知，从原问题的最终单纯表中可直接得到其对偶问题的最优 解。在两个互为对偶的线性规划中，可任选一个进行求解。若X*,Y*分别为问题（P）和问题（D）的可行解，且CX*=Y*b；则，X*和Y*分别为 问题（P）和问题（D）的最优解。用对偶性质重新解释单纯形法。单纯形法：在整个迭代过程中，始终保持该问题解的可行性（即满足b，= B-ib 0），而其对偶问题的互补解初始时并不满足可行性条件（即检验数不 完全部小于等于0）;当不可行性完全消失（即满足尢-CBB-1P W0）时，原问题 j j B j 和对偶问题同时达到最优。对偶单纯形法：在整个迭代过程中，始终保持其对偶问题解的可行性（即 尢=c-c严.W0）,而该问题的初始解并不满足可行性条件（即不完全部大于等于 j j B j0）;当不可行性完全消失（即满足b，= B -ib 0 ）时，原问题和对偶问题同时达 到最优。对偶单纯形法步骤：列出初始单纯形表，保证所有的检验数九=C - CBB-iP 0，则获得最优解，否则下一步；基变换首先确定退出基变量，其次决定进入基变量， 然后求新的基本可行 解。返回到（2）。影子价格（对偶问题的经济解释）三种资源A、B、C，价格为丫*=（7/2,0,1/2），三种资源剩余量分别为 （0,25/2,0）,目标函数：W =7/2X45 +0X80 +1/2X90 = 405/2。经济意义：反映了资源与总收益之间的关系，即当第i种资源每增加一个单 位时，在其他条件不变的情况下，该资源对目标值的贡献就是 y 。i灵敏度分析研究线性规划中，2（叽的变化对最优解的影响。目标函数系数c （价格）变化的灵敏度分析：c的变化导致检验数的变化， 如果新的检验数小于等于零，则原来的解依然是最优解；如果新的检验数大于零， 那么新的问题还没有取到最优解，还需要进一步运算才行。CN -CBB-iN 0是判断 是否继续的标准。结论1若c是非基变量的系数，则 当c的改变量iiAc在范围Ac -九内时，最优解不变i i i结论2：若c是基变量的系数，则当2的改变量Ac在范围iiiZ-、max-j | a 0, P e N Ac min-j | a b划去第t列，第k行的产量调整为a-b ；k tk t如果a0,d-=0表明超额完成预定指标； d-0,d+=0表明未达到预定指标；d+ =d- =0表明恰好完成预定指标。在新的规划问题中，需要添加一个目标约束，目标约束的形式由其具体要完 成的目标表示，比如，原来的线性规划的目标函数是MaxZ=8x + 6x，现在的新 12 的线性规划中就要添加这样的目标约束： 8x + 6x +d-d+= 140 。意思就是：尽量12 达到这个目标，如果达不到，加上一个便可以达到了。目标规划中，重要特征如下：增加了目标约束 目标中只出现偏差变量 且为求极小化问题；d+Xd-=O。单目标规划求解：用单纯形法求满意解,注意求极小化问题最优性条件是检 验数全部大于等于零。多目标规划求解中级别相同的多目标规划的数学模型：实现利润目标122（百元)，产品A的产量不多于10,这时设：d+,d-(i=l,2)分别为超过目标值的部分, ii及未完成目标值的部分。目标函数是minZ=d -+d +12目标约束是： 8x + 6x+d- d+=122 和 x +d -d +=10。1 2 1 1 1 2 2 这里,分析一下语句,实现目标利润为122百元,但是有可能达不到这个数,所以，尽量达不到的负偏差变量要小。A的产量不多于10,即便多于10,也没 关系,但是正偏差变量要尽量小。因此,得目标函数。多目标规划求解中具有优先级的多目标规划数学模型：P ：充分利用设备有 1效台时，不加班；P：产品B的产量不多于4； P：实现利润130 (百元)。 23最重要的是1号,在2号和3号完不成的情况下,也要优先保证1号完成。但是,并不是说, 1号完成之后, 2号和3号才能完成。在实际生活中,也有 1号未完成但是2号和3号完成的情况。模型约束： 4x + 2x+ d- - d+ = 601 2 1 1x + d- - d+ = 42228x + 6x+ d- - d+ = 13012332x + 4x0,d-0的方向；(3)按优先顺序找出该目标ii的满意解。目标规划的目标：(1)决策人希望恰好实现预定的第i个目标，MinZ二d + +i d-； (2)决策人不希望超过预定的第i个目标，MinZ二d +； (3)决策人希望超过 ii预定的第 i 个目标， minZ=d-。i整数规划：线性规划中要求决策变量全部或部分为整数。分为以下，纯整数 规划:所有决策变量x (j=1,2,n)均取整数；混合整数规划:部分决策变量取整 j数； 0-1整数规划：所有决策变量只取0或1，这类变量又称为逻辑变量。经典方法是分支定界法和割平面法。分支定界法步骤：先不考虑变量的整数约束，求解相应的线性规划； 分支：如果求解某一个值并非整数，那么就予以分支，比如，由于 x， x12 均不满足整数条件，故可由X (或X )进行分枝，使X满足：X 3或X三4,1 2 1 1 1将3 x4的非整数部分割掉，于是问题B分成了两个子问题B,B，然后分别1 0 1 2求出其最优解，B 最优解:X*二（3, 8/3）, Z =14i/3, B 最优解 X*二（4, 1）, Z =14；1 1 1 2 2 2定界：问题（B）已获得整数最优解，可将Z=14作为问题（A）的下界，同 22时将Z =143/4作为问题（A）的上界。可以断定Z=14W Z Z =143/4；0 2 0返回到（2）继续对B中的x进行分枝，使x满足：x W2或x三3将2x1 2 2 2 2 23 之间的非整数部分割掉。于是问题B又分成了两个子问题B和B再分别求出其最优解。234割平面法步骤：不考虑其整数条件,用单纯形法求解相应的线性规划问题，求出最终单纯形表；构造 Gomory 约束（割平面）：在最终单纯形表中，任意选择一个非整数变量（如x ），写出该变量所在行的方程式：x + 1/2x - 1/2x =5/2，将各变量的系数 2234及常数项分解为整数与非负真分数之和；再将系数为整数的变量移到方程式左端，系数为分数的变量移到方程式右端，x - x -2=1/2- （ 1/2x+1/2x ）。求得2434Gomory 约束为：1/2- （1/2x +1/2x ）W034将Gomory约束化为方程，填入到最终单纯形表中，继续求问题的最优解。用对偶单纯性法求解。分派问题使用0-1整数规划的一种特殊类型，但是由于它的形式比较特殊，所以有自己特殊的解法。有n项任务，指派n个人（广义）去完成，第i个人完成第j项任务的效率为C （i=1,2,n；j=1,2,n）；要求每个人只能承担一项任务，并且每一项任务都 ij有一个人个来承担；问如何分派可以使总的效率达到最高。（C ）为效率矩阵。ij建立数学模型： 1，分派第 i 个人去承担第 j 项任务； 0，不分派第 i 个人去 承担第 j 项任务。要求每人只能承担一项工作，每项工作只能由一个人来承担。它是特殊的 0-1 规划；它是 m=n， a=b=1 的特殊运输问题；它的所有可行解 ij的个数为 n！。同解性原理：如果在效率矩阵（C ）的第i （i=1,2,n）行（列）加（减） ij一个常数 k ，那么新效率矩阵与原效率矩阵有相同的最优解。i匈牙利解法：化简效率矩阵：使其每行、每列至少有一个零元素；检验：用尽可能少的直线去覆盖所有的零元素，当覆盖线的条数 n=n 时,0 可转入（4）确定最优方案,当 nn 时转入下一步（3）继续化简；0 移动零元素：在未被直线覆盖的元素中找出最小元，对不在覆盖线上的元素减去这个最小元，在两覆盖线交点上加上这个最小元，其他元素不变。具体步骤：变换指派问题的费用矩阵，使其在各行各列都出现 0 元素，首先每行元素减 去该行的最小元素，然后每列减去该列的最小元素；进行试指派（画O）,从含0元素最少的行或列开始，圈出一个0元素，用O 表示，然后划去该O所在的行和列中的其余0元素，用X表示，依次类推。若矩 阵中的O的个数等于n,则得最优解，若矩阵中的O的个数n，则进行第三步；做能复盖所有0元素的最小直线集合：对没有O的行打丁号、对打丁号的行 上所有0元素的列打丁号、再对打丿号的列上所有O的行打丁号、重复以上步骤 直到得不出新的打丁号为止，对没有打丁号的行画横线，所有打丁号的列画纵线， 所得到的直线既是复盖所有0元素的最小直线集合；在没有被直线复盖的元素中找出最小元素，让打丁号的列加上这个元素，打 丁号的行减去这个元素。求最大效率的问题，求最小效率的问题，都很重要。五. 矩阵对策我们称具有对策行为的模型为对策模型或对策。对策模型的种类可以千差万 别，但本质上都必须包括三个基本要素：局中人，一场竞争或斗争称为一局对策，一局对策中的决策者称为该局对策 的局中人（只有两个局中人，称为两人对策；两人以上称为多人对策）。策略，一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为 一个策略。策略的全体称为策略集，策略集可以是有限或无限的。若策略集为有 限集称为有限对策，否则称为无限对策。参加对策的每个局中人del）都有自 己的策略集，一般，每一局中人的策略集中至少应包括两个策略。局中人I策略 集合：S1=a，a，-, a ，局中人II策略集合：S2二B ,B ,，B a ,12m12n iB 称为局势。j策略不能只理解为局中人的一个“动作”。某局中人在一个对策中的一个策 略，是指他为对付其他局中人而采取的一个从头到尾的整个行动方案。赢得函数或称支付函数（简称支付） ,在一局对策中，当局势给定以后，就 用一个数来表示得失（或输赢），显然，这种“得失”或“输赢”是局势的函数， 称为支付函数。s是第i个局中人的一个策略，则n个局中人的策略组S= （s ,i1 s -s ）称为一个局势。当局势出现后，对策结果也就确定了，即对任一局势S, 2n局中人i可能得到一个赢得H。显然H是局势S的函数，称为第i个局中人的赢 得函数（支付函数）。齐王赛马中，局中人集合I=1, 2齐王的策略集用a , a , a ,a ,1 2, 3 4a ，a 表示田忌的策略集用 B ，B ，B ，B ，B ，B 表示 , 这样齐王5 6 1 2, 3 4 5 6的任一策略a和田忌的任一策略B ,就决定了一个局势S ,如果a =（上、中、ijij1下）、B =（上、中、下）则在局势S下齐王的赢得值为H （S ） =3。田忌的1 11 1 11 赢得值为H (S ) =-3。2 11 零和对策：若在一局对策中,全体局中人的支付总和为 0,则将该对策称为零 和对策,否则称为非零和对策。有限二人零和对策也称为矩阵对策。