运筹学(清华大学第三版)习题集.doc

求解下述LP问题 解：依据单纯形理论，有以下计算： （1）令为基变量、为非基变量，可得 ， 解得，代入目标函数，得。 此时得到的解为，。 由、可知，取正值可使z增大。 若令取正值且仍为0，由，可得，这说明最大可以达到3，此时将变为0，成为非变量。 （2）令为基变量、为非基变量，可得 ，解得，目标函数变为。 此时得到的解为，。 由可知，取正值可使z增大。 若令取正值且仍为0，由，可得，这说明最大可以达到2，此时将变为0，成为非基本变量。 （3）令为基变量、为非基变量，可得解，。 此时，可知此时应让取正值，即进入基变量。 经过类似检查，可知应让变成非基变量。 （4）令为基变量，为非基变量，可得解，。 此时，达到最优点。 上述过程可以编制表格计算，这就是单纯形法。 例1.9 分别用图解法、单纯形法求解例1.8的LP问题，并指出单纯形法迭代的每一步相当于图形上的哪个顶点。 解：原问题可等价转化为： 图解如下： 可知，目标函数在B 4, 2 处取得最大值，故原问题的最优解为，目标函数最大值为。 用单纯形法求解原问题时，单纯形表如下： 2 3 0 0 0 0 8 1 2 1 0 0 4 0 16 4 0 0 1 0 － 0 12 0 [4] 0 0 1 3 2 3 0 0 0 0 2 [1] 0 1 0 －1/2 2 0 16 4 0 0 1 0 4 3 3 0 1 0 0 1/4 － 2 0 0 0 －3/4 2 2 1 0 1 0 －1/2 － 0 8 0 0 －4 1 [2] 4 3 3 0 1 0 0 1/4 12 0 0 －2 0 1/4 2 4 1 0 0 1/4 0 0 4 0 0 －2 1/2 1 3 2 0 1 1/2 －1/8 0 0 0 －3/2 －1/8 0 原问题的最优解为，目标函数最大值为。 单纯形法的寻找路径为：→→ → 与图解法对照，寻找相当于O 0, 0 → D 0, 3 → C 2, 3 → B 4, 2 。 例1： 用单纯形法求解下述LP问题。 ， 解：首先将原问题转化为线性规划的标准型，引入松弛变量、，可得： 构造单纯形表，计算如下： 3 4 0 0 0 40 2 1 1 0 40 0 30 1 [3] 0 1 10 3 4 0 0 0 30 [5/3] 0 1 -1/3 18 4 10 1/3 1 0 1/3 30 5/3 0 0 -4/3 3 18 1 0 3/5 -1/5 4 4 0 1 -1/5 2/5 0 0 -1 -1 由此可得，最优解为，目标函数值为。 例2：用单纯形法求解下述LP问题。 解：引入松弛变量、，化为标准形式： 构造单纯形表，计算如下： 2.5 1 0 0 0 15 3 5 1 0 5 0 10 [5] 2 0 1 2 2.5 1 0 0 0 9 0 [19/5] 1 －3/5 45/19 2.5 2 1 2/5 0 1/5 5 0 0 0 －1/2 1 45/19 0 1 5/19 －3/19 2.5 20/19 1 0 －2/19 5/19 0 0 0 －1/2 由单纯形表，可得两个最优解、，所以两点之间的所有解都是最优解，即最优解集合为：，其中。 例2b 用单纯形法求解下述线性规划 解：引入松弛变量、和，列单纯形表计算如下： 1 －2 3 0 0 0 0 8 －2 1 8 1 0 0 1 0 4 1 －3 [10] 0 1 0 1/3 0 8 1 －1 －4 0 0 1 1 －2 3 0 0 0 0 24/5 -14/5 17/5 0 1 -4/5 0 3 2/5 [1/10] -3/10 1 0 1/10 0 4 0 48/5 7/5 -11/5 0 0 2/5 1 48/7 7/10 -11/10 0 0 -3/10 0 0 16 0 -5 28 1 2 0 1 4 1 -3 10 0 1 0 0 4 0 [2] -14 0 -1 1 0 1 -7 0 -1 0 0 26 0 0 -7 1 -1/2 5/2 1 10 1 0 -11 0 -1/2 3/2 －2 2 0 1 -7 0 -1/2 1/2 0 0 0 0 -1/2 -1/2 故，原问题的最优解为， ，其中。 例3：用单纯形法求解下述LP问题。 解：构造单纯形表计算如下： －3 －4 0 0 0 40 2 1