资源描述：
《2011运筹学复习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹学复习题复习范围：1.单纯形法求解线性规划问题2.对偶问题及互补松弛性3.表上作业法求解运输问题4.建立整数规划模型（不求解）5.匈牙利法求解指派问题6.求网络最大流专项练习：一、单纯形法求解线性规划问题例、用单纯形法求下列线性规划问题：解：化为标准型用单纯形表进行计算Cj10500qiCB基bx1x2x3x400x3x4983410[5]20138/5cj-zj10500010x3x121/58/50[14/5]1-3/512/501/53/24cj-zj010-2510x2x13/21015/14-3/1410
2、-1/72/7cj-zj00-5/14-25/14所有非基变量的检验数全部小于零，所以此线性规划问题有唯一最优解。最优解X=（1，3/2，0，0）；最优值Z=35/2.解题步骤1.化为标准形2.列表求解Key：寻找主元（检验数最大，检验比最小）主元变为1，其余变为0.3.结论（最优解和最优值）练习题：1.2.3.4.练习题答案1.最优解X=（15/4,3/4,0,0），最优值maxz=33/42.最优解X=（2,6,2,0,0），最优值maxz=343.最优解X=（1,0,2,7,0,0），最优值maxz=124.最优
3、解X=（1,2,0,0,0），最优值maxz=8注意细节1.右端项b用于计算检验比，只有系数大于0时才计算检验比；价值系数cj用于计算检验数。2.注意自我检查：基变量一定对应到单位矩阵，其检验数一定等于0；最优表给出对偶问题的最优解，对应的最优值等于原问题的最优值。3.对矩阵的某行乘以一个较大的数，总能做到所有检验数小于0，所以不要随便通分，如练习4。二、对偶问题及互补松弛性例、给出线性规划问题：要求：(1)写出其对偶问题；(2)已知原问题的最优解为X*=（2,2,4,0），试根据对偶理论，直接求出对偶问题的最优解。解
4、：(1)对偶问题为(2)将最优解(2,2,4,0)带入原问题的约束条件，根据互补松弛性，另一方面，因为，相应的对偶问题的约束条件应取等号。所以解得从而，对偶问题的最优解为Y=（4/5,3/5,1,0）,最优值为16解题步骤1.写出对偶问题的步骤最大变最小；系数矩阵转置；≤变≥；价值系数与右端项互换。2.互补松弛性的应用Key：约束条件对应决策变量第一步：把最优解带入约束条件，约束条件取不等号，相应的决策变量等于零；第二步：最优解不为零，对应的约束条件取等号；第三步：解方程练习题：1.已知线性规划的最优解是X*=（6,2
5、,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），最优值为262.原问题的最优解X=（0,0,4
6、,4），最优值为443.对偶问题的最优解Y=（1,0,0,0,1），最优值为54.原问题的最优解X=（0,0,4,4），最优值为28注意细节写对偶问题时，不要忘了决策变量的非负约束；注意计算最优值，自我检查最优解应满足所有的约束条件，且原问题的最优值应该等于对偶问题的最优值。三、表上作业法求解运输问题1、产销平衡问题例下表为各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。销地产地B1B2B3B4产量A1A2A3413127455601884销量656320解：先用沃格尔法求初始解销地产
7、地B1B2B3B4产量行罚数A1A2A341312745560188430221152244销量6563列罚数22111111115得初始调运方案：B1B2B3B4A153A262A331下面用位势法进行检验：B1B2B3B4uiA1360A2110A3151vi1140所有检验数≥0，此时问题已达到最优解总运费minz=5*1+3*4+6*1+2*0+3*5+1*1=39解题步骤1.先用沃格尔法或者最小元素法求出初始解沃格尔法：优先供应罚数大的运输任务最小元素法：优先考虑所有任务中的最低运价。2.再用位势法或者闭回路
8、法进行检验位势法：令任意一个位势为0（不妨u1=0），计算位势和检验数：数格对应的运价等于位势和；空格对应的运价减去位势和等于检验数。3.若不是最优解，用闭回路法调整后回到第2步检验数全部大于等于零，得到最优解；调整检验数小于零的空格所对应的闭回路：以该空格为第一个奇数顶点，找出偶数顶点中最小的运输量为调整量，奇数顶点加上调整量，
