运筹学复习资料

考试范围第一章线性规划及单纯形法第二章对偶问题第三章运输问题第五章整数规划第一章线性规划及单纯形法线性规划问题的一般数学模型代数方程矩阵和向量的形式线性规划问题的标准形式上述模型的简写形式为：代数方程矩阵和向量的形式价值向量资源向量决策变量向量系数矩阵mn系数矩阵的列向量线性规划问题的标准形式其中常数项标准化⑴若目标函数为（2）若约束条件为不等式，分为两种情况讨论：加入松弛变量加入剩余变量（3）对于决策变量非负的要求，分为两种情况讨论：①非正变量②自由变量线性规划问题的几个重要性质解的可能性：唯一最优解、无穷多最优解、无界解、无可行解；若线性规划问题的可行解存在，则可行域是一个凸集；若线性规划问题的最优解存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。线性规划图解法适用于：2个决策变量线性规划求解的单纯形法解的几个重要概念：最优解、可行解、基解、基可行解、退化解解与解之间的关系退化解是不是基可行解？

非可行解可行基可行解解

基解线性规划求解的单纯形法基（B）：约束方程的m×n阶系数矩阵A的秩为m，且m<n。则，B是A中mm阶的满秩子矩阵。（或：B由A中m个线性无关的列向量所组成）基的数目不超过基与解的对应关系基解基可行基基可行解最优基基最优解线性规划问题求解——单纯形法代数法表格法线性规划问题求解的步骤标准化；初始基可行解的确定最优性检验基变换进基变量出基变量小结初始化最优性检验迭代（Iteration）最优？yesSTOPno初始基可行解的确定当前的基可行解是否最优？包括三个步骤：1、确定进基变量（进基）2、确定出基变量（出基）3、对新基可行解的求解（高斯消元）单纯形表的格式CjC1C2…Cn

θiCBXBbx1

x2….xn

C1

C2…Cmx1x2…xmb1b2…bma11a12…a1na21a22…a2n………am1am2…amnθ1θ2…θm

σjσ1σ2…σn迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。如何求得B-1?见P157表格单纯形法的计算步骤①将线性规划问题化成标准型②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表；③计算各非基变量xj的检验数j=Cj-CBPj

′，若所有j≤0，则问题已得到最优解，停止计算，否则转入下步；④在大于0的检验数中，若某个k所对应的系数列向量Pk′≤0，则此问题是无界解，停止计算，否则转入下步；表格单纯形法的计算步骤⑤换基：根据max{j｜j＞0}=k原则，确定xk为换入变量(进基变量)（进基）；确定xL为换出变量。建立新的单纯形表，此时基变量中xk取代了xL的位置。(出基)⑥以aLk′为枢轴元素进行迭代，把xk所对应的列向量变为单位列向量，即aLk′变为1，同列中其它元素为0，（高斯消元），转第③步表格单纯形法的几种特殊情况（1）唯一最优解在最终单纯形表中所有非基变量j<0时，该线性规划问题具有唯一解（2）无穷多最优解在最终单纯形表中，存在非基变量的检验数j=0，则表明可以找到另一个顶点（基可行解）目标函数值也达到最大。（让这个非基变量进基，继续迭代，得另一个最优解）表格单纯形法的几种特殊情况（3）无界解无出基变量：即，存在某个j>0，且Pj≤0（4）无可行解：采用人工变量法时，最终表中人工变量仍没有置换出去人工变量法高斯变换中，如果资源列向量出现负数，则采用人工变量法。通过换基，最好使得人工变量成为非基变量。有两种方法：大M法两段法人工变量法——大M法两段法人工变量法——两段法大M法对偶单纯形法对偶单纯形法的优点：无需人工变量思路：始终保持对偶问题可行。初始表原问题不可行，经过变换，对偶问题和原问题均可行，从而得到最优解。最优性检验标准：常数列是否都≥0对偶单纯形法对偶单纯形法的步骤：初始表检验行≤0；常数列可以有<0确定出基变量确定进基变量如果主行所有的a元素>0，说明原问题无可行解。第二章对偶问题原问题对偶问题3个约束2个变量2个约束3个变量原问题对偶问题一般规律≤≤...≤maxmin≥对偶问题原问题≥≥对称形式的对偶问题非对称形式的对偶问题

原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题）对偶问题的基本性质1、对称性：对偶问题的对偶是原问题2、弱对偶性：原问题的目标值是对偶问题目标值的下界；对偶问题的目标值是原问题目标值的上界（P）无界＝>（D）无可行解；（D）无界＝>（P）无可行解；（P）可行而（D）不可行＝>（P）无界；（D）可行而（P）不可行＝>（D）无界。PD最优无界不可行最优不可行无界原问题（P）与对偶问题（D）解的关系对偶问题的基本性质3、最优性如果，原问题的目标值=对偶问题目标值则，此解既是原问题的最优解，也是对偶问题的最优解4、对偶性（强对偶性）若原问题有最优解，则对偶问题一定具有最优解，且它们最优解的目标函数值相等对偶问题的基本性质5、互补松弛性在线性规划问题的最优解中：

如果对应某一约束条件的对偶变量值非零，则该约束条件取严格等式；

反之，如果约束条件取严格不等式，则其对应的对偶变量一定是零。松

紧（等式）紧松对偶问题的基本性质6、单纯形表上基解对应关系当采用单纯形法求LP问题时，迭代的每一步在得到原问题的一个基本可行解的同时，检验行上同时得到对偶问题的一个基解。对应关系为：原问题对偶问题决策变量剩余变量松弛变量决策变量解的经济学解释——影子价格1、影子价格是一种边际价格2、反映资源的稀缺程度一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用解的经济学解释——影子价格3、检验数的经济意义—第j种产品的产值—生产第j中产品所消耗各项资源的影子价格的总和。（即隐含成本）可见，产品产值>隐含成本可生产该产品；否则，不安排生产。——检验数的经济意义灵敏度分析研究内容：

研究线性规划中，的变化，增加变量以及增加约束条件对最优解的影响。研究方法：图解法对偶理论分析仅适用于含2个变量的线性规划问题在单纯形表中进行分析研究的目的：最优性不变，及其条件最优性改变，用原始单纯形法，找出新最优解要求：对单纯形法思路的理解非常透彻，计算非常熟练第三章运输问题标准型（产销平衡）运输问题的数学模型平衡运输问题必有可行解，也必有最优解

销地产地产量销量运价表运输问题约束条件的系数矩阵运输问题是一个具有m×n个变量和n+m个等型约束的线性规划问题约束条件的系数矩阵是：n+m行，m×n列运输问题约束方程组的系数矩阵是一个只有0和1两个数值的稀疏矩阵，其中1的总数为2×m×n个约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次约束条件系数矩阵的秩是m+n-1。即运输问题的基变量总数是m+n-1系数矩阵的列向量表示即：表上作业法来求解运输问题计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案,Goto2确定初始可行解的方法最小元素法西北角法沃格尔(Vogel)法解的最优性检验的方法1闭回路法2对偶变量法，也称为位势法解的改进（用闭回路法调整）选择进基变量的原则：即选择非基变量中检验数最小的一个进基。在进基格点所对应的闭回路上，定义顶点的序号：自进基格点起选定一个方向（比如顺时针方向），依次为第一格、第二格、…在奇数格点上增加调整量，在偶数格点上减少调整量。调整量取闭回路上的最小值运输问题，解的可能性多重解若在最优解中，某个非基变量的检验数为零退化解基变量取值为0产销不平衡的运输问题若产大于销，增加一个假想的销地若销大于产，增加一个虚拟的产地相应的运价设为0第五章整数规划整数规划问题的类型求解整数规划的方法整数规划问题的类型纯整数线性规划混合整数线性规划0-1型线性规划求解整数规划的方法分支定界法割平面法分支定界法分支松弛问题的最优解不符合整数要求，构造两个约束条件从而形成两个分枝，即两个后续问题。定界若某个分支的解满足整数约束，那么他的目标值可作为后续分支的过滤条件（以提高搜索效率），把这个叫做“定界”对于最大值问题，“下界”割平面法增设一个新的约束条件（割平面方程）割平面约束的构造选择具有最大分数部分的非整分量所在行构造割平面约束割平面约束的构造方法Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4j00-1/4-1/40-1型整数规划0-1型整数规划模型的构造0-1型整数规划的解法0-1型整数规划模型的构造互斥问题固定费用问题工件排序问题一些典型的技巧肯定的决策否定的决策0-1逻辑变量一般取值互斥问题的大M法（Mx）否定的决策肯定的决策一些典型的技巧利用0-1变量构造任意整数一些典型的技巧互斥问题X1+x2=1决策变量的互斥约束方程的互斥一般地，若需要从p个约束条件中恰好选择q个约束条件，则可用引入p个0-1向量若选择第i个约束条件若不选择第i个约束条件那么，约束条件组就可用达到这个目的。因为上述约束条件组保证了在p个0-1变量中有p-q个为1，q个为0。凡取0值的yi对应的约束条件即为原约束条件，而取1的yi对应的约束条件无效。0-1型整数规划的解法隐枚举法例求解0-1整数规划解求解过程可以列表表示(x1,x2,x3)Z值约束条件（abcd）过滤条件(0,0,0)0√√√√Z≥0(0,0,1)5√√√√Z≥5(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8√√√√Z≥8abcd(x1,x2,x3)Z值约束条件（abcd）过滤条件(1,1,0)1(1,1,1)6接上表所以，最优解（x1,x2,x3）T=(1,0,1)T,maxZ=8由于采用上述算法，实际只作了20次运算。指派问题指派问题模型的构造