[理学]运筹学清华大学第三版习题集

《[理学]运筹学清华大学第三版习题集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、求解下述LP问题解：依据单纯形理论，有以下计算：（1）令为基变量、为非基变量，可得，解得，代入目标函数，得。此时得到的解为，。由、可知，取正值可使z增大。若令取正值且仍为0，由，可得，这说明最大可以达到3，此时将变为0，成为非变量。（2）令为基变量、为非基变量，可得，解得，目标函数变为。此时得到的解为，。由可知，取正值可使z增大。若令取正值且仍为0，由，可得，这说明最大可以达到2，此时将变为0，成为非基本变量。（3）令为基变量、为非基变量，可得解，。此时，可知此时应让取正值，即进入基变量。经过类似检查，可知应让变成非基变量。（4）令为基变量，为非基变量，可得解，。

2、此时，达到最优点。上述过程可以编制表格计算，这就是单纯形法。例1.9分别用图解法、单纯形法求解例1.8的LP问题，并指出单纯形法迭代的每一步相当于图形上的哪个顶点。解：原问题可等价转化为：图解如下：可知，目标函数在B(4,2)处取得最大值，故原问题的最优解为，目标函数最大值为。用单纯形法求解原问题时，单纯形表如下：230000812100401640010－0120[4]00132300002[1]010－1/220164001043301001/4－2000－3/4221010－1/2－0800－41[2]43301001/41200－201/4241001/4

3、00400－21/2132011/2－1/8000－3/2－1/80原问题的最优解为，目标函数最大值为。单纯形法的寻找路径为：→→→与图解法对照，寻找相当于O(0,0)→D(0,3)→C(2,3)→B(4,2)。例1：用单纯形法求解下述LP问题。，解：首先将原问题转化为线性规划的标准型，引入松弛变量、，可得：构造单纯形表，计算如下：34000402110400301[3]01103400030[5/3]01-1/3184101/3101/3305/300-4/3318103/5-1/54401-1/52/500-1-1由此可得，最优解为，目标函数值为。例2：用单纯

4、形法求解下述LP问题。解：引入松弛变量、，化为标准形式：构造单纯形表，计算如下：2.510001535105010[5]20122.5100090[19/5]1－3/545/192.5212/501/55000－1/2145/19015/19－3/192.520/1910－2/195/19000－1/2由单纯形表，可得两个最优解、，所以两点之间的所有解都是最优解，即最优解集合为：，其中。例2b用单纯形法求解下述线性规划解：引入松弛变量、和，列单纯形表计算如下：1－2300008－2181001041－3[10]0101/3081－1－40011－23000024/

5、5-14/517/501-4/5032/5[1/10]-3/10101/1004048/57/5-11/5002/5148/77/10-11/1000-3/1000160-528120141-310010040[2]-140-1101-70-1002600-71-1/25/211010-110-1/23/2－2201-70-1/21/20000-1/2-1/2故，原问题的最优解为，，其中。例3：用单纯形法求解下述LP问题。解：构造单纯形表计算如下：－3－4000402110400301[3]0110－3－400030[5/3]01－1/318－4101/3101/

6、330－5/3004/3－318103/5－1/5－4401－1/5－2/50011故，最优解为，目标函数值为。例4：某个求解最大值的线性规划问题用单纯形法计算时得到下表：f2c10e02-1－501－103a－300－41bd00－30其中，a,b,c,d,e,f是未知数，原问题中要求各变量为非负。问a,b,c,d,e,f满足什么条件时，有下面各解成立？（1）不是基可行解；（2）是唯一最优解；（3）有无穷多最优解；（4）是退化的基本可行解；（5）无界解；（6）是可行解但非最优解，只有可以进基且出基变量必为第3个基变量。解：（1）f<0（2）f>=0,b<0,d<

7、0（3）f>=0,b=0,d<=0或f>=0,b<=0,d=0（4）f=0,b<=0,d<=0（5）f>=0,d>0,c<0（6）f>=0,b>0,d<=0,f/2>3/a例1.10用大M法求解下述LP问题解：先将原问题化为标准型，引入松弛变量，得：再引入人工变量、，得：构造单纯形表计算如下：23－50－M－M－M71110107－M10[2]－51－10153M+23-4M2M-5-M00－M20[7/2]1/21/21－1/24/7251－5/21/2－1/201/2－07M/2+8M/2-6M/2+10-3M/2-134/7011/71/72/7-1/724

8、5/710