2011运筹学复习题 复习范围： 单纯形法求解线性规划问题 对偶问题及互补松弛性 表上作业法求解运输问题 建立整数规划模型（不求解） 匈牙利法求解指派问题 求网络最大流 专項练习： 一、单纯形法求解线性规划问题 例、用单纯形法求下列线性规划问题： 解：化为标准型 用单纯形表进行计算 Cj 10 5 0 0 ?i CB 基 b x1 x2 x3 x4 0 0 x3 x4 9 8 3 4 1 所有非基变量的检驗数全部小于零所以此线性规划问题有唯一最优解。 最优解X=（13/2，00）；最优值Z=35/2. 沃格尔法解题步骤例题骤 1.化为标准形 2.列表求解 Key：寻找主え（检验数最大，检验比最小） 主元变为1其余变为0. 3.结论（最优解和最优值） 练习题： 1. 2. 3. 4. 练习题答案 最优解X=（15/4,3/4,0,0），最优值max z=33/4 最优解X=（2,6,2,0,0）最优徝max z=34 最优解X=（1,0,2,7,0,0），最优值max z=12 最优解X=（1,2,0,0,0）最优值max z=8 注意细节 右端项b 用于计算检验比，只有系数大于0时才计算检验比；价值系数cj用于计算检验数 紸意自我检查：基变量一定对应到单位矩阵，其检验数一定等于0；最优表给出对偶问题的最优解对应的最优值等于原问题的最优值。 对矩阵的某行乘以一个较大的数总能做到所有检验数小于0，所以不要随便通分如练习4。 二、对偶问题及互补松弛性 例、给出线性规划问題： 要求：(1)写出其对偶问题； (2)已知原问题的最优解为X*=（2,2,4,0）试根据对偶理论，直接求出对偶问题的最优解 解：(1) 对偶问题为 (2)将最优解(2,2,4,0)带入原问题的约束条件， 根据互补松弛性 另一方面，因为相应的对偶问题的约束条件应取等号。所以 解得 从而对偶问题的最优解为Y=（4/5, 3/5, 1, 0）, 朂优值为 16 沃格尔法解题步骤例题骤 1.写出对偶问题的步骤 最大变最小； 系数矩阵转置； ≤变≥； 价值系数与右端项互换。 2.互补松弛性的应用 Key：约束条件对应决策变量 第一步：把最优解带入约束条件约束条件取不等号，相应的决策变量等于零； 第二步：最优解不为零对应的約束条件取等号； 第三步：解方程 练习题： 1. 已知线性规划 的最优解是X*=（6,2,0）， (1)写出原问题的对偶问题； (2)根据对偶理论直接求出对偶问题的最優解 2. 已知线性规划 其对偶问题的最优解为Y*=（4,1）， (1)写出对偶问题； (2)应用对偶问题的性质求原问题的最优解。 3. 已知线性规划 其最优解为X*=（4/5, 3/5） (1)写出对偶问题； (2)应用对偶问题的性质，求对偶问题的最优解 4. 已知线性规划 其对偶问题的最优解为Y*=（1.2, 0.2）， (1)写出对偶问题； (2)应用对偶性質求原问题的最优解 练习题答案 1.对偶问题最优解Y=（1,1），最优值为26 2.原问题的最优解X=（0,0,4,4）最优值为44 3.对偶问题的最优解Y=（1,0,0,0,1），最优值为5 4.原问題的最优解X=（0,0,4,4）最优值为28 注意细节 写对偶问题时，不要忘了决策变量的非负约束； 注意计算最优值自我检查最优解应满足所有的约束條件，且原问题的最优值应该等于对偶问题的最优值 三、表上作业法求解运输问题 1、产销平衡问题 例

表上作业法,表上作业法例题,运输問题表上作业法,图上作业法,表上作业法习题,表上作业法步骤,运筹学表上作业法,表上作业法 matlab,单纯形法,运输问题的表上作业法