运筹学案例分析.doc

某测绘队在年计划内准备安排 1 :2000和 1 :5000此恻尺地形图的航测内业生产。 该测绘队所具备的生产能力为： 电算加密工序3600工天， 测图仪器工序有效工天2000工天，编图工序为3000工天。每幅 1:2000地形图生产的计划定额为：加密 9工天(包括部分平坦地区的特征点) ，测圆4工天，编图3工天，单位产品产值270元幅。每幅 1：5000地形图生产的计划定额为:加密 4工天,测图5工天，编图10工天 ，单位产品产值 460元幅。 根据以上资料确定使总产值指标为最大的生产计划。 其数学模型建立如下： 设： 1：2000地形 图的计划产量为 X1 幅 ；1：5000地形 图的计划产量为 X2 幅。 希望获得的最大总产值 目标函数为： Z max= 270 x1+ 460x2 根据确定的变量， 约束条件为： 9 X l + 4 X2 3600 4 X1 + 5X2 2000 3 X1 +1 0 X2 3000 X10 X20 这是一个比较简单的线性规划数学模型，化为标准形式用单纯形法即可计算求得最优解。 但如果约束条件不是这样，比如该测绘队的生产能力： 电算加密工序远大于3600工天，要求至少要工作3600工天,测图工序仪器有效工天只能是2000工天，少于2 00 0工天要浪费资源 ，多于2000工天又不可能。那么，这一线性规划问题的数学模型将建立成如下形式:Zmax = 270 X1+460 X2 9 X1 + 4 X2 3600 4 X1 + 5X2 2000 3 X1 + 10X2 3000 X1 0 X2 0此时，线性规划问题的结束条件有“=”式或“”式， 这意味着将原问题化为标准形式后，约束条件的系数矩阵中不包含有单位矩阵，无法计算。因此 ，要引入人工变量， 即人 为地构造一个单位基矩阵。具体做法是在不等式左端先减去一个大于等于0的剩余变量(也可理解为松驰变量),化为等式后再添一个人工变量。据此，将前面的数学模型化为标准形式， 在约束条件中分别添加橙驰变量、剩余变量和人工变量，得到以下形式的约束条件 ： 9 X1+ 4 X2-X3 + X4 = 3600 4 X1 + 5X2 +X5 =2000 3 X1 + 10X2 +X6 = 3000 X1、X2、X3、X4、X5、X6 0用两阶段法解线性规划问题的第一阶段是先求解目标函数中只包古人工变量的线性规划问题。令目标函数中其它变量的系数为 0 ，人工变量的系数取某个正的常数(本题取1 ) ，保持原问题约束条件不变的情况下， 用单纯形法求出这个目标函数极小化时的解。很明显， 在第一阶段中， 当人工变量取值为 0时，目标函数值也为0 ，此时的最优解就是原线性规划问题的一个可行解如果第一阶段求解结果最优解的目标函数值不为 0 ，亦即最优解的基变量中古有人工变量，这说明原线性规划问题无可行解。当第一阶段求解结果表明所解线性规划问题有可行解时，第二阶段是在原问题中去除人工变量 ，并从这一可行解(即第一阶段最 优解)出发，用单纯形法求出问题的最优解。前倒用两阶段法求解时，第一阶段的线性规划问题可写为： Wmin=X4+X5 9 X1+ 4 X2-X3 + X4 = 3600 4 X1 + 5X2 +X5 =2000 3 X1 + 10X2 +X6 = 3000 X1、X2、X3、X4、X5、X6 0用单纯形法求解见下表： 第二阶段是将上表中的人工变量X4和 X5去除，此时目标函数改为:Z=270 X1+ 460 X2 + 0 X3 + 0 X6 再接着上表计算下去:本例只迭代一次，所有的检验数均0 。 原线性规划问题的最优解为：X1 = 360 (幅) X2 = 124 (幅) 。 目标函数 Z=270 X1+ 460 X2 = 270360 +450124 =154240 (元)采用两阶段法求线性规划问题最优解时，重要的是要明确晦 一阶段的任务及其内在联系。首先要求出线性规划问题的可行解。如果有基本可行解而且是单位矩阵可直接转入第二阶段，否则要引入人工变量，并求得初始可行解。如果第一阶段最优解目标函数值不为 0 ， 则原问题无可行解，