第二章作业的参答考案.doc

第二章作业的参考答案 4、将下面的线性规划问题化成标准形式 解：将max 化为 min，用代替，则 令，则 将线性不等式化成线性等式，则可得原问题的标准形式 5、用图解法求解下列线性规划问题： （1） 解：图2.1的阴影部分为此问题的可行区域。将目标函数的等值线（为常数）沿它的负法线方向移动到可行区域的边界上。于是交点就是该问题的最优解，其最优值为36。 12、对于下面的线性规划问题，以为基写出对应的典式。 解：先将方程组中基变量的系数向量化成单位向量 利用线性方程组的典式，把用表示，再带入目标函数，则可得原问题相应于基的典式 16、用单纯形法求解下列线性规划问题： (1) 解：将此问题化成标准形式 以为基变量，可得第一张单纯形表为 RHS 2 1 -1 0 0 0 0 3 1 1 1 0 0 60 1 -1 2 0 1 0 10 1 1 -1 0 0 1 20 以为进基变量，为离基变量旋转得 RHS 0 3 -5 0 -2 0 -20 0 4 -5 1 -3 0 30 1 -1 2 0 1 0 10 0 2 -3 0 -1 1 10 以为进基变量，为离基变量旋转得 RHS 0 0 0 -35 0 0 1 1 -1 -2 10 1 0 0 15 0 1 0 5 所以最优解为，最优值为-35。 注：用单纯形法求解线性规划问题的步骤 Ⅰ、将问题化成标准形式； Ⅱ、找出初始解； Ⅲ、写出第一张单纯形表，并化成典式； Ⅳ、判定和迭代。 ① 判定：1 最优解（检验数向量）；2 问题无界（某个非基变量的检验数，且在典式中的系数向量） ② 迭代步骤： 1 确定进基变量 （检验数向量中最大的正分量）； 2 确定转轴元 （进基变量所在的这一列中的正分量与右端向量中对应元素比值最小的）； 3 确定离基变量 （转轴元所在的这一行对应的基变量）； 4 迭代计算（利用初等行变换，将转轴元变为1，转轴元所在的这一列其它元素全部变为0）； 5 用进基变量 代替离基变量 。 （3） 解：在第三个等式两端同乘以-1，并以为基变量可得其单纯形表为 RHS -1 1 -1 0 -1 1 0 0 0 0 3 0 1 1 0 6 0 1 2 -1 0 0 0 10 1 0 0 0 0 -1 0 0 0 0 1 0 0 1 1 6 将第0行的元素化为检验数可得 RHS 0 0 0 1 0 1 0 -4 0 0 3 0 1 1 0 6 0 1 2 -1 0 0 0 10 1 0 0 0 0 -1 0 0 0 0 1 0 0 1 1 6 由于的检验数，并且在典式中的系数向量，所以问题无界。 17、用两阶段法求解下列线性规划问题： （2） 解：将此问题化为标准形式 添加人工变量得到辅助问题 以为基变量，可得辅助问题的单纯形表为 RHS -2 -4 0 0 0 0 0 0 0 0 0 -1 -1 0 2 -3 -1 0 1 0 2 -1 1 0 -1 0 1 3 把所在的这一行的元素化成检验数 RHS -2 -4 0 0 0 0 0 1 -2 -1 -1 0 0 5 2 -3 -1 0 1 0 2 -1 1 0 -1 0 1 3 以为进基变量，为离基变量旋转得 RHS 0 -7 -1 0 1 0 2 0 -1 0 4 1 0 0 1 0 -1 1 4 所以，辅助问题的最优解为，其最优值为。因此，原问题没有可行解。 （4） 解：将此问题化成标准形式 添加人工变量得到辅助问题 以为基变量，可得辅助问题的单纯形表为 RHS 2 -4 5 -6 0 0 0 0 0 0 0 -1 -1 0 1 4 -2 8 1 0 2 -1 2 3 4 0 1 1 把所在的这一行的元素化成检验数 RHS 2 -4 5 -6 0 0 0 0 6 1 12 0 0 3 1 4 -2 8 1 0 2 -1 2 3 4 0 1 1 以为进基变量，为离基变量旋转得