运筹学复习重点.ppt

运筹学复习要点一、线性规划问题的标准型1、为了方便讨论和制定统一的算法，规定线性规划问题的标准型：总结：标准型有以下规定：①目标函数求极大；②所有限定系数③所有变量都要求非负；④约束条件里的约束方程都应是等式。2、非标准型线性规划问题非标准型线性规划问题：不符合标准形式的线性规划问题。非标准型线性规划模型的几种情况（详见笔记）例1.3将下列线性规划问题的规划模型化为标准型。解题步骤：二、表解形式的单纯形法(1)建立初始单纯形表：包括决策变量、基变量及其价值系数，以及约束方程组的增广矩阵。(2)找出初始可行基：在增广矩阵中寻找单位子矩阵形式的可行基，进而得到相应的基变量。(3)计算,其中是基变量的价值系数,进而计算检验数。若全部，则该解为最优解；若中有小于0的，则说明该解不是最优解，转下步.(4)迭代接下步。(5)寻找新的可行基，重复(3)-(4)步。例：用单纯形法解下列线性规划问题。解：引入松弛变量将其化为标准型：利用单纯形法的表解形式求解过程如下：三、对偶问题非对称线性规划的对偶问题若原问题不是对称形式，首先将其化为等价的对称形式的线性规划问题，然后按原问题与对偶问题之间的对应关系，写出其对应的对偶问题。用矩阵形式表示，对称形式下原问题与其对偶问题的对比如下：四、工作指派问题工作指派问题是这样一类问题：有n个人和n件事，已知第i个人做第j件事的费用为要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最少。对于工作指派问题，一般用匈牙利法进行求解。匈牙利法的计算步骤(1)如有n项任务，则列出一个n阶矩阵表格。(2)变换矩阵：先对各行元素分别减去本行中的最小元素，再对各列元素分别减去本列中最小元素，使得每一行和每一列都出现0元素。(3)在变换矩阵中找最优解：在矩阵中寻找n个位于不同行不同列的0元素。找最优解的具体方法：由有0元素最少的行（或列）开始，圈出一个0元素，用◎表示，然后划去同行同列的其他元素。如能找到n个位于不同行不同列的0元素，则得到了最优解；若找不到，则转下步。(4)画0元素的最少覆盖线：要用最少的覆盖线将矩阵表格中的所有0元素都覆盖住。如果覆盖线的条数少于矩阵的阶数，说明找不到最优解，要转下步（继续变换矩阵，使0元素增加）。如果覆盖线的条数等于矩阵的阶数，则说明可以从矩阵表格的0元素中找出最优解。画最少覆盖线的具体方法：①对没有◎的行打√；②对打√的行中，所有有0元素的列打√；③对打√的列中，对有◎的行打√；④重复②、③步直到得不出新的打√的行和列；⑤对没有打√的行画横线，对打√的列画纵线，这些横线和纵线就是能把全部0元素都覆盖的最少覆盖线。(5)变换矩阵，增加0元素。具体方法是：①在没被直线覆盖的元素中找出最小元素；②对没被直线覆盖的各元素减去这个最小元素；③被两条直线覆盖的各元素都加上这个最小元素。(6)重复第(3)步找最优解，如能找到则结束；否则重复(4)-(5)步。五、最短路问题1、什么是最短路问题在有向图中，寻找一条从始点到终点的路，该路的权之和最小。2、求解最短路问题的算法(1)狄克斯托算法狄克斯托于1959年提出了求解最短路问题的标号法，该算法适用于各边上的权都大于0的情况。狄克斯托算法采用标号法，有两种标号：T标号和P标号。P标号为永久性标号，给点标P表示从起点到点的最短路权，P标号不再改变。T标号为临时标号，给点标T表示从起点到点的估计最短路权的上界，是一种临时标号，所有没有得到P标号的点都要标T标号。算法每一步都把某一点的T标号改为P标号，当终点得到P标号时，算法结束。狄克斯托算法的具体步骤：①给起点以P标号：，其余各点均给T标号，。②若点为刚得到P标号的点，考虑以点为始点的所有弧段，且为T标号。对的T标号进行如下的更改：③比较所有具有T标号的点，把最小者改为P标号。当同时存在多个最小者时，可同时改为P标号。若全部点均为P标号则停止；否则转②继续算法。补充：（1）无论是T标号还是P标号，