运筹学复习题 复习范围： 1. 单纯形法求解线性规划问题 2. 对偶问题及互补松弛性 3. 表上作业法求解运输问题 4. 建立整数规划模型（不求解） 5. 匈牙利法求解指派问题 6. 求网络最大流 专项练习： 一、单纯形法求解线性规划问题 例、用单纯形法求下列线性规划问题： 0,825943510max21212121xxxxxxxxz 解：化为标准型 121231241234max105349528,,,0zxxxxxxxxxxxx 用单纯形表进行计算 Cj 10 5 0 0 i CB 基 b x1 x2 x3 x4 0 0 x3 x4 9 8 3 4 1 0 [5] 2 0 1 3 8/5 cj - zj 10 5 0 0 0 10 x3 x1 21/58/5 0 [14/5] 1 -3/5 1 2/5 0 1/5 3/2 4 cj - zj 0 1 0 -2 5 10 x2 x1 3/2 1 0 1 5/14 -3/14 1 0 -1/7 2/7 cj - zj 0 0 -5/14 -25/14 所有非基变量的检验数全部小于零，所以此线性规划问题有唯一最优解。 最优解X=（ 1， 3/2， 0， 0）；最优值Z=35/2. 解题步骤 1.化为标准形 2.列表求解 Key：寻找主元（检验数最大，检验比最小） 主元变为1，其余变为0. 3.结论（最优解和最优值） 练习题： 1. 0,242615532max21212121xxxxxxxxz 2. 0,1823122452max21212121xxxxxxxxz 3. 0,,72342263542max32132132321321xxxxxxxxxxxxxxz 4. 0,,3373431131313132max321321321321xxxxxxxxxxxxz 练习题答案 1. 最优解X=（ 15/4,3/4,0,0），最优值max z=33/4 2. 最优解X=（ 2,6,2,0,0），最优值max z=34 3. 最优解X=（ 1,0,2,7,0,0），最优值max z=12 4. 最优解X=（ 1,2,0,0,0），最优值max z=8 注意细节 1. 右端项b 用于计算检验比，只有系数大于0 时才计算检验比；价值系数cj用于计算检验数。 2. 注意自我检查：基变量一定对应到单位矩阵，其检验数一定等于0；最优表给出对偶问题的最优解，对应的最优值等于原问题的最优值。 3. 对矩阵的某行乘以一个较大的数，总能做到所有检验数小于0， 所以不要随便通分，如练习4。 二、对偶问题及互补松弛性 例、给出线性规划问题： )4,3,2,1(096628342max321432214214321ixxxxxxxxxxxxxxxxzi 要求：(1)写出其对偶问题；...
