2011运筹学复习题

运筹学复习题复习范围：单纯形法求解线性规划问题对偶问题及互补松弛性表上作业法求解运输问题建立整数规划模型（不求解）匈牙利法求解指派问题求网络最大流专项练习：一、单纯形法求解线性规划问题例、用单纯形法求下列线性规划问题：解：化为标准型用单纯形表进行计算Cj10500iCB基bx1x2x3x400x3x4983410[5]20138/5cj-zj10500010x3x121/58/50[14/5]1-3/512/501/53/24cj-zj010-2510x2x13/21015/14-3/1410-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.练习题答案最优解X=（15/4,3/4,0,0），最优值maxz=33/4最优解X=（2,6,2,0,0），最优值maxz=34最优解X=（1,0,2,7,0,0），最优值maxz=12最优解X=（1,2,0,0,0），最优值maxz=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），最优值为262.原问题的最优解X=（0,0,4,4），最优值为443.对偶问题的最优解Y=（1,0,0,0,1），最优值为54.原问题的最优解X=（0,0,4,4），最优值为28注意细节写对偶问题时，不要忘了决策变量的非负约束；注意计算最优值，自我检查最优解应满足所有的约束条件，且原问题的最优值应该等于对偶问题的最优值。三、表上作业法求解运输问题1、产销平衡问题例下表为各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。销地产地B1B2B3B4产量A1A2A3413127455601884销量656320解：先用沃格尔法求初始解销地产地B1B2B3B4产量行罚数A1A2A341312745560188430221152244销量6563列罚数22111111115得初始调运方案：B1B2B3B4A153A262A331下面用位势法进行检验：B1B2B3B4uiA1360A2110A3151vi1140所有检验数≥0，此时问题已达到最优解总运费minz=5*1+3*4+6*1+2*0+3*5+1*1=39解题步骤1.先用沃格尔法或者最小元素法求出初始解沃格尔法：优先供应罚数大的运输任务最小元素法：优先考虑所有任务中的最低运价。2.再用位势法或者闭回路法进行检验位势法：令任意一个位势为0（不妨u1=0），计算位势和检验数：数格对应的运价等于位势和；空格对应的运价减去位势和等于检验数。3.若不是最优解，用闭回路法调整后回到第2步检验数全部大于等于零，得到最优解；调整检验数小于零的空格所对应的闭回路：以该空格为第一个奇数顶点，找出偶数顶点中最小的运输量为调整量，奇数顶点加上调整量，偶数顶点减去调整量。练习题：1.求最优调运方案（写出min值）销地产地B1B2B3B4产量A1A2A3101656104751012910494销量52462.求最优调运方案（写出min值）销地产地B1B2B3B4产量A1A2A3324743638425523销量3322练习题答案1.总运费为1182.总运费为32注意细节对于m行n列的运输表，无论是初始解还是最优解，数格的个数应该等于m+n-1。并且数格不能形成闭回路。检查位势是否计算正确，数格处的位势和应等于数格所对应的运价运价用于计算位势，得到的解（运输量）用于调整如果计算出相同的罚数，任意选一个如果同时划掉一行及一列，则在此行此列任意选一个空格补0.始终保持数格个数为m+n-1如果空格的检验数等于0，意味着最优解不唯一。2、产销不平衡问题解题步骤1.先将产销不平衡问题化为产销平衡问题增加虚拟销地或产地；运价设为0，销量或产量等于产销不平衡的差值2.再求解新得到的产销平衡问题。例下表为各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。销地产地B1B2B3B4产量A1A2A3324743638425526销量3322解：此问题是一个产销不平衡问题，由产大于销，故增加虚拟销地B5，令销量为(5+2+6)-(3+3+2+2)=3，单位运价为0化为产销平衡问题。用沃格尔法求初始解销地产地B1B2B3B4B5产量行罚数A1A2A33247436384250005263111203111销量33223列罚数1111432110得初始调运方案：B1B2B3B4B5A123A202A3132下面用位势法进行检验：B1B2B3B4B5uiA15200A23-11-1A33-11vi32440调整-1所在的闭回路，B1B2B3B4B5A123A202A3132调整量为0，改进后的解为B1B2B3B4B5A123A220A3132下面用位势法进行检验：B1B2B3B4B5uiA15100A2142-2A32-11vi32540调整-1所在的闭回路，B1B2B3B4B5A123A220A3132调整量为1，改进后的解为B1B2B3B4B5A132A220A3321下面用位势法进行检验：B1B2B3B4B5uiA140-10A2243-3A3120vi33650调整-1所在的闭回路，B1B2B3B4B5A132A220A3321调整量为2，改进后的解为B1B2B3B4B5A1320A220A333下面用位势法进行检验：B1B2B3B4B5uiA1410A2132-2A31310vi33540所有检验数≥0，此时问题已达到最优解总运费minz=9+8+6+9=32练习题：3.求最优调运方案（写出min值）销地产地B1B2B3B4B5产量A1A2A3A41021820102065873930107106455629销量44624练习题答案3.总运费为90四、建立整数线性规划（不求解）例1、某服务部门各时段(2h为一段)需要的服务人员数如表所示，按规定，服务员连续工作8h为一班.现要求安排每个时间段开始上班的服务员人数，使服务部门服务员总人数最少？时段12345678服务员最少数目10891113853答案书上P124例1例2、某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻井费用最小。若10个井位的代号为S1,S2,S3,…S10，相应的钻井费用为C1,C2,C3,…C10，并且井位选择上要满足下列限制条件：①选择S1和S7就不能选择钻探S8；反过来也一样；②选择了S3或S4就不能选S5，反过来也一样；③在S5S6S7S8中最多只能选两个；试建立这个问题的整数规划模型。（不求解）解：令则问题可以表示为练习题：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j=1,2,…,n）。此外,由于种种原因，有三个附加条件：第一，若选择项目1，就必须选择项目2，反之不一定；第二，项目3和4中至少选择一个；第三，项目5，6和7恰好选择两个.应当怎样选择投资项目才能使总预期收益最大？练习题答案书上P124例2练习题：某公司拟在市东、西、南三区建立门市部。有7个位置点Ai（i=1，…，7）可供选择，规定：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但总投资不能超过B元，问应选择哪几个点可使年利润最大？例3、某集团公司有n个销售某种产品的零售店Bj(j=1,2,…,n)，其每年的销售量为bj(j=1,2,…,m)，现该集团公司打算在m个地点开设生产该产品的生产厂，每个地点最多只能建一个工厂，若在第i地建厂其生产能力为ai(i=1,2,…,m)，每年的固定成本为di，从工厂Ai到零售站Bj的单位运费为cij(i=1,2,…,m；j=1,2,…,n)。问应该在哪些地点选厂及做怎样的运输计划，使本年度花费最少？解：设从工厂Ai到零售店Bj每年的运输量为xij（i=1,2,…,m；j=1,2,…,n），令则该问题可以表示为练习题：工厂A1和A2生产某种物资.由于该种物资供不应求，故需要再建一家工厂.相应的建厂方案有A3和A4两个。这种物资的需求地有四个，生产能力、需求量、单位物资运费见下表。工厂A3或A4开工后,每年的生产费用估计分别为1200万元或1500万元.现要决定应该建设工厂A3或A4,才能使今后的总费用(即全部物资运费和新工厂生产费用之和)最少?B1B2B3B4生产能力A12934400A28357600A37612200A44525200需求量(kt/年)350400300150练习题答案书上P125例3练习题：书上P136例7，例8书上P1485.4，5.5解题步骤建立数学模型就是回答三个问题：1.决策变量是什么？2.目标函数是什么？3.约束条件有什么？注意细节仔细分析题意，决策变量就是题目所问的问题。变量是人数、机器设备台数或产品件数等都要求是整数，在约束条件中一定要写出整数限制！对某一个项目要不要投资，建不建厂这样选择性的决策问题，使用0-1变量，在约束条件中要再次表明变量取值0或1.遇到人员的合理安排问题（实际上是指派问题），使用双下标的0-1变量：xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。确定决策变量和目标函数后，从题目的第一句话开始考察需要满足的约束条件，不要有遗漏。五、匈牙利法求解指派问题例、求指派问题（min）（要求写出解和值）：解：变换系数矩阵：试指派：独立0元的个数小于4，试指派不成功，调整系数：重新试指派：独立0元个数为4，指派成功，最优解为；最优值为：2+4+1+8=15.解题步骤1.变换系数矩阵，目的：使每行每列中都出现零元素：原系数矩阵每行都减去该行的最小元素；新得到的系数矩阵每列减去该列的最小元素。2.试指派，目的：寻找独立0选择多的礼让选择少的，选择少的优先指派3.独立0元个数不足则变换矩阵，目的：增加新的0用最少的直线通过所有0元素（行不勾列勾）调整系数（没有划线的元素中的最小元素为我们的调整量，所有没划线的元素减去调整量，划一次线的元素不变，划两次线的元素加上调整量）4.写出最优解和最优值练习题：1.求指派问题（min）（要求写出解和值）：2.求指派问题（min）（要求写出解和值）：3.求指派问题（min）（要求写出解和值）：4.求指派问题（min）（要求写出解和值）：练习题答案1.最优解为，最优值为322.最优解为，最优值为173.最优解为，最优值为704.最优解为，最优值为22注意细节寻找独立0元素时：从只有一个0元素的行开始，给0加圈，划去同列的0；然后从只有一个0元素的列开始，总之，选