运筹学 刁在筠 部分作业的参考答案C2.pdf

运筹学 参考解答 第 1 页 共 14 页 第二章第二章 线性规划线性规划 73 P 4 将下面的线性规划问题化成标准形式将下面的线性规划问题化成标准形式 123 123 123 1 2 max2 236 23 03 16 xxx stxxx xxx x x 解 解 将 max 化为 min 3 x 用 45 xx 代替 则 1245 1245 1245 1 2 45 min2 23 6 2 3 03 16 0 xxxx stxxxx xxxx x x x x 令 22 1xx 则 1245 1245 1245 1 2 45 min12 2 1 3 6 2 1 3 03 07 0 xxxx stxxxx xxxx x x x x 将线性不等式化成线性等式 则可得原问题的标准形式 1245 12456 12457 18 29 12456789 min221 2334 24 3 7 0 xxxx stxxxxx xxxxx xx xx x x xx x xx x 73 P 5 用图解法求解下列线性规划问题 1 12 12 1 2 min3 20 612 2 xx stxx x x 解 解 图2 1的阴影部分为此问题的可行区域 将 目标函数的等值线 12 3xxc c为常数 沿它的 负法线方向 13 T 移动到可行区域的边界上 于是交点 T 812就是该问题的最优解 其最优 值为 36 75 P 16 用单纯形法求解下列线性规划问题 用单纯形法求解下列线性规划问题 等值线 20 12 8 X1 o X2 法线方向 图 2 1 运筹学 参考解答 第 2 页 共 14 页 1 123 123 123 123 min2 360 210 20 0 1 2 3 j zxxx stxxx xxx xxx xj 解 将此问题化成标准形式标准形式 123 1234 1235 1236 min2 360 210 20 0 1 2 3 4 5 6 j zxxx stxxxx xxxx xxxx xj 以 456 x x x为基变量 可得第一张单纯形表为 以 1 x为进基变量 5 x为离基变量旋转得 以 2 x为进基变量 6 x为离基变量旋转得 1 x 2 x 3 x 4 x 5 x 6 x RHS z 21 1 0 000 4 x 31 1 1 0060 5 x 1 1 2 0 1010 6 x 11 1 0 0120 1 x 2 x 3 x 4 x 5 x 6 x RHS z 03 5 0 20 20 4 x 04 5 1 3030 1 x 1 1 2 0 1010 6 x 02 3 0 1110 1 1 注意单纯形表的格式 2 注意单纯形表的格式 2 要用记号把转轴元标出来 3 要用记号把转轴元标出来 3 要记住在单纯形表的左边 用 进基变量代替离基变量 要记住在单纯形表的左边 用 进基变量代替离基变量 注 零行元素的获得 先将目标函 数化成求最小值的形式 再把所有变 量移到等式左边 常数移到等式右 边 则变量前的系数为零行对应的元 素 注 零行元素的获得 先将目标函 数化成求最小值的形式 再把所有变 量移到等式左边 常数移到等式右 边 则变量前的系数为零行对应的元 素 运筹学 参考解答 第 3 页 共 14 页 所以最优解为 15 5 0 Tx 最优值为 35 用单纯形法求解线性规划问题的步骤 1 用单纯形法求解线性规划问题的步骤 1 将问题化成标准形式 2 将问题化成标准形式 2 找出初始解 3 找出初始解 3 写出第一张单纯形表 并化成典式 4 写出第一张单纯形表 并化成典式 4 判定和迭代 判定和迭代 判定 最优解 检验数向量判定 最优解 检验数向量0 问题无界 某个非基变量 问题无界 某个非基变量 k x 的检验数的检验数0 k 且 且 k x 在典式中的系数向量在典式中的系数向量 0 k A 迭代步骤 确定进基变量 迭代步骤 确定进基变量 k x 检验数向量 检验数向量 T 中最大的正分量 确定转轴元 中最大的正分量 确定转轴元 rk a 进基变量所在的这一列中的正分量与右端向量中对应元 素比值最小的 确定离基变量 进基变量所在的这一列中的正分量与右端向量中对应元 素比值最小的 确定离基变量 r x 转轴元所在的这一行对应的基变量 迭代计算 利用初等行变换 将转轴元变为 1 转轴元所在的这一列其它元素 全部变为 0 用进基变量 转轴元所在的这一行对应的基变量 迭代计算 利用初等行变换 将转轴元变为 1 转轴元所在的这一列其它元素 全部变为 0 用进基变量 k x代替离基变量 代替离基变量 r x 3 12356 356 234 16 3 min 3 6 2 10 0 x zxxxxx stxxx xxx xx 67 x6 0 1 2 3 4 5 6 7 j x xj 解 在第三个等式两端同乘以 1 并以 5217 x x x x为基变量可得其单纯形表为 1 x 2 x 3 x 4 x 5 x 6 x RHS z 00 2 1 0 2 1 2 3 35 4 x 00 1 1 1 2 10 1 x 10 2 1 0 2 1 2 1 15 2 x 01 2 3 0 2 1 2 1 5 运筹学 参考解答 第 4 页 共 14 页 将第0行的元素化为检验数可得 由于 4 x的检验数01 4 并且 4 x在典式中的系数向量0 0 0 1 0 4 T A 所 以问题无界 75 P 17 用两阶段法求解下列线性规划问题 用两阶段法求解下列线性规划问题 2 12 12 12 12 min24 232 3 0 zxx stxx xx xx 解 解 将此问题化为标准形式 12 123 124 1234 min24 23 2 3 0 zxx stxxx xxx xxx x 添加人工变量 65 x x得到辅助问题 1 x 2 x 3 x 4 x 5 x 6 x 7 x RHS z 11 1 0 11 0 0 5 x 00 3 0 11 0 6 2 x 01 2 100 0 10 1 x 10 0 0 0 1 0 0 7 x 00 1 0 01 1 6 1 x 2 x 3 x 4 x 5 x 6 x 7 x RHS z 00 0 1 01 0 4 5 x 00 3 0 11 0 6 2 x 01 2 100 0 10 1 x 10 0 0 0 1 0 0 7 x 00 1 0 01 1 6 注 必须先将线性方程 组和目标函数化成典 式 再用单纯形方法开 始判定 迭代 注 必须先将线性方程 组和目标函数化成典 式 再用单纯形方法开 始判定 迭代 运筹学 参考解答 第 5 页 共 14 页 56 1235 1246 123456 min 23 2 3 0 gxx stxxxx xxxx xx x xx x 以 65 x x为基变量 可得辅助问题的单纯形表为 把g所在的这一行的元素化成检验数 以 1 x为进基变量 5 x为离基变量旋转得 所以 辅助问题的最优解为 1 0 0 0 0 4 Tx 其最优值为 40g 因此 原问题没有 可行解 1 x 2 x 3 x 4 x 5 x 6 x RHS z 2 4 0 00 00 g 00 0 0 1 10 5 x 2 3 1 01 02 6 x 11 0 10 13 1 x 2 x 3 x 4 x 5 x 6 x RHS z 2 4 0 0000 g 1 2 1 1005 5 x 2 3 1 0102 6 x 11 0 1013 1 x 2 x 3 x 4 x 5 x 6 x RHS z 0 7 1 01 02 g 0 2 1 2 1 1 2 1 04 1 x 1 2 3 2 1 0 2 1 01 6 x 0 2 1 2 1 1 2 1 14 运筹学 参考解答 第 6 页 共 14 页 4 1234 1234 1234 1234 max2456 42 8 2 23 41 0 zxxxx stxxxx xxxx xxx x 解 将此问题化成标准形式 1234 1234 1234 1234 min2456 42 8 2 23 41 0 zxxxx stxxxx xxxx xxx x 添加人工变量 65 x x得到辅助问题 56 12345 12346 123456 min 42 8 2 23 4 1 0 gxx stxxxxx xxxxx xxx xx x 以 56 x x为基变量 可得辅助问题的单纯形表为 把g所在的这一行的元素化成检验数 以 4 x为进基变量 5 x为离基变量旋转得 1 x 2 x 3 x 4 x 5 x 6 x RHS z 2 4 5 6000 g 00 0 0 1 10 5 x 14 2 8102 6 x 12 3 4011 1 x 2 x 3 x 4 x 5 x 6 x RHS z 2 4 5 6000 g 06 1 12003 5 x 14 2 8102 6 x 12 3 4011 运筹学 参考解答 第 7 页 共 14 页 以 3 x为进基变量 6 x为离基变量旋转得 所以 辅助问题的最优解为 1 0 0 0 0 0 4 T x 其最优值为0g 因此 原问题的初始 解为 0 1 0 0 0 4 T x 其第一张单纯形表为 以 1 x为进基变量 4 x为离基变量旋转得 1 x 2 x 3 x 4 x 5 x 6 x RHS z 4 11 1 2 7 0 4 3 0 2 3 g 2 3 0 4 0 2 3 00 4 x 8 1 2 1 4 1 1 8 1 0 4 1 6 x 2 3 0 4 0 2 1 10 1 x 2 x 3 x 4 x 5 x 6 x RHS z 16 65 1 0 0 16 19 8 7 2 3 g 0 0 0 0 1 1 0 4 x 32 1 2 1 0 1 32 3 16 1 4 1 3 x 8 3 0 1 0 8 1 4 1 0 1 x 2 x 3 x 4 xRHS z 16 65 1 0 0 2 3 4 x 32 1 2 1 0 1 4 1 3 x 8 3 0 1 00 运筹学 参考解答 第 8 页 共 14 页 因此 原问题的最优解为 8 0 3 0 Tx 最优值为31 76 P 18 写出下列线性规划问题的对偶规划 写出下列线性规划问题的对偶规划 123 123 123 123 123 min24 2342 263 355 0 zxxx stxxx xxx xxx x xx 为自由变量 解 解 先将此问题化成一般形式 123 123 123 123 123 min24 2342 263 355 0 zxxx stxxx xxx xxx x xx 为自由变量 所以 其对偶规划为 123 123 123 123 132 max235 221 332 4654 0 st 为自由变量 77 P 20 给定线性规划问题给定线性规划问题 13 12 23 123 min 25 1 3 2 0 zxx stxx xx x xx 记为 P 1 用单纯形算法解P 1 x 2 x 3 x 4 x RHS z 0 66 0 130 31 1 x 116 0 32 8 3 x 06 1 12 3 运筹学 参考解答 第 9 页 共 14 页 2 写出P的对偶问题D 3 写出P的互补松紧条件 并利用它们解对偶D 解 解 1 把问题 P 化为标准形式 13 124 23 1234 min 25 1 3 2 0 zxx stxxx xx x xxx 以 31 x x为基变量 可得到其单纯形表为 把第0行化成检验行 得 以 2 x为进基变量 1 x为离基变量 旋转得 根据最优化准则知 问题 P 的最优解为 5 7 0 2 4 T x 最优值为 4 7 2 将问题 P 化为一般形式 1 x 2 x 3 x 4 xRHS z 10 1 00 1 x 12 0 15 3 x 0 2 1 1 03 1 x 2 x 3 x 4 xRHS z 0 2 5 0 18 1 x 12 0 15 3 x 0 2 1 1 03 1 x 2 x 3 x 4 xRHS z 4 5 0 0 4 1 4 7 2 x 2 1 1 0 2 1 2 5 3 x 4 1 0 1 4 1 4 7 运筹学 参考解答 第 10 页 共 14 页 13 12 23 123 min 25 1 3 2 0 zxx stxx xx x xx 因此其对偶问题 D 为 12 1 12 2 1 max53 1 1 20 2 1 0 st 3 由问题 P 的最优解为 5 7 0 2 4 T x 以及互补松紧性定律可得 12 2 1 20 2 1 解得 12 1 1 4 所以 对偶问题 D 的最优解为 1 1 4 T 最优值为 4 7 35 21 77 P 22 用对偶单纯形法解下列问题用对偶单纯形法解下列问题 1 123 123 123 min234 23 234 0 1 2 3 i zxxx stxxx xxx xi 解 解 引入剩余变量将原问题标准化 123 1234 1235 min234 23 234 0 1 2 3 4 5 i zxxx stxxxx xxxx xi 再将约束条件两边同时乘以 1 得 123 1234 1235 min234 23 234 0 1 2 3 4 5 i zxxx stxxxx xxxx xi 以 45 x x为基变量 可得其单纯形表为 注 若问题存在一个基本解 并且该解 的检验数向量小于等于零 则可使用对 偶单纯形方法 特别地 要将问题典式 化 注 若问题存在一个基本解 并且该解 的检验数向量小于等于零 则可使用对 偶单纯形方法 特别地 要将问题典式 化 运筹学 参考解答 第 11 页 共 14 页 以 5 x为离基变量 1 x为进基变量 旋转得 以 4 x为离基变量 2 x为进基变量 旋转得 根据最优化准则知 原问题的最优解为 T x 0 5 2 5 11 最优值为 5 28 用对偶单纯形方法求解线性规划问题的步骤 1 用对偶单纯形方法求解线性规划问题的步骤 1 将问题化成标准形式 2 将问题化成标准形式 2 找出初始解 3 找出初始解 3 写出第一张单纯形表 并化成典式 4 写出第一张单纯形表 并化成典式 4 判定和迭代 判定 最优解 右端向量 判定和迭代 判定 最优解 右端向量0 b 没有可行解 某个 没有可行解 某个 0 r b 并且在 典式中 并且在 典式中 r b所在的这一行内没有负分量 迭代步骤 确定离基变量 所在的这一行内没有负分量 迭代步骤 确定离基变量 r x 右端向量最小的负分量 右端向量最小的负分量 1 x 2 x 3 x 4 x 5 x RHS z 2 3 4 0 00 4 x 1 2 1 1 0 3 5 x 21 3 0 1 4 1 x 2 x 3 x 4 x 5 x RHS z 0 4 1 0 1 4 4 x 0 2 5 2 1 1 2 1 1 1 x 1 2 1 2 3 0 2 1 2 1 x 2 x 3 x 4 x 5 x RHS z 0 0 5 9 5 8 5 1 5 28 2 x 0 1 5 1 5 2 5 1 5 2 1 x 1 0 5 7 5 1 5 2 5 11 运筹学 参考解答 第 12 页 共 14 页 确定转轴元 确定转轴元 rk a 离基变量所在的这一行中的负分量与 离基变量所在的这一行中的负分量与 T 中对应元素 比值最小的 确定进基变量 中对应元素 比值最小的 确定进基变量 k x 转轴元所在的这一列对应的非基变量 迭代计算 利用初等行变换 将转轴元变为 1 转轴元所在的这一列其它元素 全部变为 0 用进基变量 转轴元所在的这一列对应的非基变量 迭代计算 利用初等行变换 将转轴元变为 1 转轴元所在的这一列其它元素 全部变为 0 用进基变量 k x代替离基变量 代替离基变量 r x 2 123 123 13 23 min32 6 4 3 0 1 2 3 i zxxx stxxx xx xx xi 解 解 先将原问题标准化 123 1234 135 236 min32 6 4 3 0 1 2 3 4 5 6 i zxxx stxxxx xxx xxx xi 在第2 3个等式的两端同乘以 1 并以 45 xx为基变量 可得其单纯形表为 以 5 x为离基变量 1 x为进基变量 旋转得 1 x 2 x 3 x 4 x 5 x 6 x RHS z 3 2 1 0 000 4 x 11 1 1 006 5 x 10 1 0 10 4 6 x 0 1 1 0 01 3 运筹学 参考解答 第 13 页 共 14 页 以 6 x为离基变量 2 x为进基变量 旋转得 所以 原问题没有可行解 78 P 23 考虑第20题中的线性规划 P 利用问题 P 的最优单纯形表继续求解下列问题 1 1 c由1变为 4 5 解 因为只有非基变量 1 x的价值系数 1 c由1变为 4 5 故只需要在问题 P 的最优单纯形 表中 把 1 x的检验数按如下规则改变 1 4 5 1 4 5 1111 cc 得到新问 题的单纯形表如下 以 1 x为进基变量 2 x为离基变量 旋转得 1 x 2 x 3 x 4 x 5 x 6 x RHS z 0 2 4 0 3012 4 x 01 2 1 102 1 x