运筹学复习资料

..运筹学复一单形法表、工量根知〕线性规划解的情况唯一最优解多重最解、无界解无解。其中行域无界并不意味着标函数无界。无界可行域对应着解的情况有：唯一最优解、多重最优解、无界解。有界可行域对应唯一最优解和多重最优解两种情况。线性规划解得根本性质有足线性规划约束条件的可行解可行域成一个凸多边形；凸多边形的顶点〔极点〕与根本可行解一一对应〔即一个根本可行解对应一个顶点划问题假设有最优解，那么最优解一定在凸多边形的某个顶点上取得。单纯形法解决线性规划问题时换基迭代过程中基的非基变量的选择要利用比值法个方法是保证进基后的单纯型依然在解上可行基迭代要求除了进基的非基变量外，其余非基变量全为零。检验最优性的一个方法是在目标函数中非基变量表示基变量求检验数全部小于等于零。“x由0变到45/2时x首先变为0故x为退出基变量。〞这句话是最133小比值法的一种通俗的说法，但是很有意义。这里x为进基变量x为出基变1量方程化为每个方程只含一个基变量表示成非基变量的函数。单纯型原理的矩阵描述。在单纯型原理的表格解法中一个有趣的现象就是纯型表中的某一列的组成的列向量等于它所在的单纯型矩阵的最初的基矩阵的m*m阵与其最初的那一列向量的乘积。.

.最初基变量对应的基矩阵的逆矩阵。这个样子：

10-3

258

'P0102218所有的检验数均小于或等于零最优解是如果出现非基变量的检验数为，那么有无穷多的最优解，这时应该继续迭代。解的结果应该是：*

*1

X*2

〕说明：最优解有时不唯一，但最优值唯一；在实际应用中，有多种方案可供选择；当问题有两个不同的最优解时，问题有无穷多个最优解。无最优解的情况就是应进基的量所对应的的系数部小于零假设存在某个且所的<0那么不存在有界最优解。jij人为地构造一个单位矩阵来充当初始可行基单纯形迭代将它们逐个地从基变量中替换出来设经过基的变换变量中不再有非零人工变量，这表示问题有解假设在最终表当所有C-z0，而在中还有个非jj人工变，这表示无行解。大原理核心：打破原来的约束，再设法恢复。大M法根本思想：假定人工变量在基变量中的价值系数为一个绝对值很大的-(M>>0,对极小化问题M),这样只要基变量中还存在人工变,目函数就不可能实现极值。两阶段法原理一阶段是据给定的问题构造其辅助问题原问题求初始根本可行解上人工变量后求的就是人工变量退出助问题是人工变量之和的最小值必须为零。.

Bi***.Bi***.第二阶段是将第一阶段求出的最优解为第二阶段的初始根本可行解后在原问题的目标函数下进展优化，以决定原问题的最优解。注：单纯形法中每一步运算只能用矩阵初等行变换；表中第3(b列的数总应保持非负〔当所有检验数均非正〔〕时，得到最优单纯形表。假设直接对目标求最，要求所有检验数均非负；纯形表存在非基变量对应的检验数为零时无穷多解；关于退化循环如果在一个根本可行解的基变量中至少有一个分量=0i…

)，那么称此根本可行解是退化的根本可行解。一般情况下，退化的根本可行解〔极点〕是由假设干个不同的根本可行解〔极点〕在特殊情况下合并成一个根本可行极点形成的化的构造对单纯形迭代会造成不利的影响。可能出现以下情况：①进展进基、出基变换后，虽然改变了基，但没有改变根本可行解〔极点数当然也不会改良。进展假设干次基变换后，才脱离退化根本可行解〔极点根本可行解〔极点增加迭代次数，使单纯形法收敛的速度减慢。②在特殊情况下，退化会出现基的循环，一旦出现这样的情况迭代将永远停留在同一极点上法求得最优解。二、对偶题和灵敏度析对偶问题的根本性质：对偶问题的对偶问题，是原问题；假设X是问题(的一可行解，

是问题的一个可行解，那么:CX

。假设

*

分别为问题和问题的可行解，且

*

=Y

b那么X

*

和Y

分别为问题和问题.

BP.的最优解假设问(P)的标函值上界，那么题(D)无可解；假问题(D)的标函数W无下界，那问题(P)无可解。偶定理假设问题(P)和问题D〕一有优解，么另一个问也一定最优解，且标函数相等。由对偶定理可知题的最终单纯表中可直接得到其对偶问题的最优解。在两个互为对偶的线性规划中，可任选一个进展求解。假设*分别为问题和问题的可行解，且*=*；那么*和Y*别为问题和问题的最优解。用对偶质重新解释纯形法单纯形法：在整个迭代过程中，始终保持该问题解的可行性〔即满足b

问题的互补解初始时并不满足可行性条即检验数不完全部小于等于行性完全消失〔即满足jjj对偶问题同时到达最优。

〕时，原问题和对偶单纯形法：在整个迭代过程中，始终保持其对偶问题解的可行性〔即jjj

解并不满足可行性条全部大于等于0当不可行性完全消失〔即满足优。对偶单纯形法步骤：

〕时，原问题和对偶问题同时到达最列出初始单纯形表，保证所有的检验数

检验：假设满足

b0

，那么获得最优解，否那么下一步;基变换首先确定退出基变量定进入基变量新的根本可行解。返回到〔.

jaji.jaji.影子价格〔对偶问题的经济解释〕三种资源

*

=(7/2,0,1/2)剩余量分别目标函数：W+0×80+1/2×90=经济意义：反映了资源与总收益之间的关系，即当第i资源每增加一个单位时，在其他条件不变的情况下，该资源对目标值的奉献就是。i灵敏度分析研究线性规划中，

aijij

的变化对最优解的影响。目标函数系数C〔价格〕变化的灵敏度分析：C的变化导致检验数的变化，如果新的检验数小于等于零么原来的解依然是最优解果新的检验数大于零，那么新的问题还没有取到最优解，还需要进一步运算才行。N判断是否继续的标准。结论：c是非基变量的系数，则c改变量ii在范最优解不变iiic是变量在ii

是maxjaij

|aij

Pminij

|aij

PNj

对于基变量的变化，变化值如果小于检验数的相反数，那么最优解不变。基便量系数发生改变将改变所有变量检验数。增加一个新变量的灵敏度分析果该行的检验数为小于等于零么新变量为非基变量，此表到达最优。反之，就要迭代求解。如何求检验数很重要，要用到第一章中的知识。

与比较要了解各项的含义。增加一个新约束的灵敏度分析解代入新的约束中新约束，那么原最优解不变设不满足新约束么原最优解改变新增的约束条件添入最终的单纯形表中，并增加一个基变量，继续迭代。添加新约束后，有时要.

..对原问题所对偶单纯形法且要消元构造单位阵矩阵新约条件的数项至少多少时不影原最优？对偶单纯法非常重要三.运问运输问题的一般描述某种物资有产地A1A2,,Am其产量分别为…另外有n个地B1B2,…销量分别为…,bn从AiBj的单位运费为Cij(i=1,2,…,m;j=1,2,…,n)问应如何组织调运才能使总运费最低。产销平衡运输问题模型特点：由平衡条件易知个方程线性相关，而任意m+n–1个程线性无关；基变量的个数为–非基变量的个数为––1〕有无限多方案；系数矩阵只包括有产销不平衡问题，a的和大于的和，为产大于销的问题。解决运输问题应该运用运输单纯型法，步骤是：〕确定初始根本可行解〔初始方案最小元素法和元素差额法。最小元素法出运输表中x位置暂先空着表中找出单位运价最小ij者C，取x=min{a，b}把x的值填在相应的格内假设有几个单位运价同时到ktktktkt达最小，就任取其中之一a>b划去第t列，第k行的产量调整为a-b；ktkt如果a<b划去第kt的销量调整为b果=b划去第t列kkttkkt行的产量调整为，或划去第k，第t的销量调整为〕检验〔计算所有非基变量x的检验数〕——位势法。ij位势法字分解为行位u列位vijijij.

ij

0.0.〔数字格出v过和计算出非基变量的检验数。ijij通常令u方程组行列的位势值中基变量检验数为C+v1ijij最优性条件非基变量检验数均大于等于满足此条件转〕基变换〔方案改良闭回路〔几何〕法：从空格〔非基变量所在格〕出发，沿垂直或水平方向前进前进的过程中可穿过数字格可穿过空格某个适当的数字格内转弯样假设干次转向后回到出发点，形成一个闭回路。可以证一个空格都有并且只有一条闭回路〔存在且唯一可能是矩形、也可能是曲折的多边形。然后确定进基变量和退基变量基变量就是检验数小于0的空格基变量是从该进基变量出发，运用闭回路法，在转角处，从起点开场标“、“-、“+、〞，标-〞的量中，最小的一个退基，减去运输量值，其余的标+的加上该运输量值，标“〞的减去该运输量值。产销不平衡问题：要虚设一个行或列，这里，(1)数字格〔基变量〕的个数为果缺少数字必须添补救(2)当最终表中某个非基变量检验数为，说明该问题有两个根本可行解均为最优解。四.目规和数划目标规划分为单目标规划目标规划目标规划中有级别一样的目标规划和具有优先级目标规划。假设利润目标为百元称之为预定目标，实际完成的量与预定目标之间可能出现偏差，通常用d+〕表示，称为偏差变量。其中表示超过预定指标的局部表示未到达预定指标的局部。在客观条件.

--+----+------+.下，最终完成的结果可能出现以下三种情况：①dd=0说明超额完成预定指标；②>0,d=0说明未到达预定指标；③=d=0说恰好完成预定指标。在新的规划问题中要添加一个目标约束标约束的形式由其具体要完成的目标表示，比方，原来的线性规划的目标函数6x现在的新1的线性规划中就要添加这样的目标约束：8x+1

dd。意思就是：尽量2到达这个目标，如果达不到，加上一个便可以到达了。目标规划中，重要特征如下：①增加了目标约目标中只出现偏差变量且为求极小化问题；③d×d单目标规划求解：用单纯形法求满意解注意求极小化问题最优性条件是检验数全部大于等于零。多目标规划求解中级别一样的多目标规划的数学模型：实利润目标〔百元

产品产量不多于

，

这时设dd(i=1,2)别为超过目标值的局ii部，及未完成目标值的局部。目标函数是+d12目标约束是：6x+d-和x+d-11112这里语句利润为122元能达不到这个数，所以，尽量达不到的负偏差变量要小。的产量不多于即便多于也没关系，但是正偏差变量要尽量小。因此，得目标函数。多目标规划求解中具有优先级的多目标规划数学模型:充分利用设备有效1台时，不加班；产品产量不多于4；实现利润130百元2最重要的是1，在和3完不成的情况下，也要优先保证完成。但是，并不是说，号完成之后，2号和号才能完成。在实际生活中，也有.

----------；--.号未完成但是和完成的情况。模型约束：2x+d-d60①1x+d-d=②22++d-=130③13+④1x，d,12ii目标函数：P+Pd+Pd11133在这里，目标是正负偏差量之和，就是取要恰好到达之意。图解法求解目标规划：按照上面的规划，可以有以下步骤

根据系统约束④确定可行域〔2〕不考虑偏差，即：d=d=0，后按顺序作ii出目标约束相应的直线标出>0,>0的方向序找出该目标ii的满意解。目标规划的目标定的第i个标=+-；ii〔2〕决策人不希望超过预定的第i目标，=+策人希望超过预i定的第i个目标，=-i

。整数规划性规划中要求决策变量全部或局部为整数为以下整数规划所有决策变量x(j=1,2,…均取整数；混合整数规:局部决策变量取整数；j0-1数规划所有决策变量只取0或1，这类变量又称为逻辑变量。经典方法是分支定界法和割平面法。分支定界法步骤：先不考虑变量的整数约束，求解相应的线性规划；分支：如果求解某一个值并非整数，那么就予以分支，比方，由于x，x均1.

3/.3/.不满足整数条件，故可由x或x进展分枝，使x满足：x≤3或将121113<x<4的非整数局部割掉，于是问题B分成了两个子问题B,B，然后分别求11出其最优解B最优解:X*1/3最优解X*=141122定界：问题〔〕已获得整数最优解，可将Z=14作为问题〔的下界，22同时将=140

3/4

作为问题〔的上界。可以断定Z=14≤Z<=142

；返回续对B中的x进展分枝x满足xx122间的非整数局部割掉。于是问题又分成了两个子问题和再分别求出其最优解。234割平面法步骤：不考虑其整数条用单纯形法求解相应的线性规划问题，求出最终单纯形表；构造约束〔割平面单纯形表中，任意选择一个非整数变量〔如x变量所在行的方程式：x+1/2x–1/2x=5/2，将各变量的系22数及常数项分解为整数与非负分数和将系数整数变量移方程左端系数为分数变量移到方式右端，x-2=1/2-〔1/2x+1/2x24束为：1/2-+1/2x3将约束化为方程，填入到最终单纯形表中，继续求问题的最优解。用对偶单纯性法求解。分派问题使用0-1整数规划的一种特殊类型，但是由于它的形式比拟特殊，所以有自己特殊的解法。有n项任务,指派n个人广义)完成第i个人完成第j项任务的效率为C(i=1,2,…,n;j=1,2,…；求每个人只能承当一项任务,且每一项任务都有一ij.

..个人个来承当；问如何分派可以使总的效率到达最高为效率矩阵。ij建立数学模型：，分派第i个人去承当第j项任务；，不分派第i个人去承当第j项任务。要求每人只能承当一项工作，每项工作只能由一个人来承当。它是特殊的规划；它是m=n=1的特殊运输问题；它的所有可行ij解的个数为同解性原理：如果在效率矩阵〔C〕的第i〕行〔列〕加〔减〕ij一个常数k那么新效率矩阵与原效率矩阵有一样的最优解。i匈牙利解法：化简效率矩阵：使其每行、每列至少有一个零元素；检验：用尽可能少的直线去覆盖所有的零元素，当覆盖线的条数n时0可转入〔〕确定最优方案当n时转入下一步(继续化简；0移动零元素未被直线覆盖的元素中找出最小元不在覆盖线上的元素减去这个最小元，在两覆盖线交点上加上这个最小元，其他元素不变。具体步骤：变换指派问题的费用矩阵其在各行各列都出现0元素先每行元素减去该行的最小元素，然后每列减去该列的最小元素；进展试指派〔画○元素最少的行或列开场，圈出一个0元素，用○表示，然后划去该○所在的行和列中的其余0素，用表示，依次类推。假设矩阵中的eq\o\ac(○,的)eq\o\ac(○,)个数等于n么得最优解设矩阵中的○的个数<n么进展第三步；做能复盖所有0素的最小直线集合没有○的行打√号打√号的行.

..上所有素的列打√号对打√号的列上所有○的行打√号复以上步骤直到得不出新的打√号为止打√号的行画横线√号的列画纵线，所得到的直线既是复盖所有素的最小直线集合；在没有被直线复盖的元素中找出最小元素打√号的列加上这个元素√号的行减去这个元素。求最大效率的问题，求最小效率的问题，都很重要。五.矩对我们称具有对策行为的模型为对策模型或