《运筹学》期末考试

《运筹学》试题样卷题号一二三四五六总分得分一、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中54,xx为松弛变量，问题的约束为形式（共8分）1x2x3x4x5x3x5/201/211/2０1x5/21－1/20－1/61/3jjzc0－４0－４－２(1)写出原线性规划问题；（4分）(2)写出原问题的对偶问题；（3分）(3)直接由上表写出对偶问题的最优解。（1分）二、求解下面运输问题。（18分）某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示：问：应如何调运，可使得总运输费最小?销地产地1B2B3B4B产量1A2A3A1089523674768252550销量15203035100答案一、对偶问题。共计8分解：（１）原线性规划问题：3211026maxxxxz0,103522132122xxxxxxx；……4分（２）原问题的对偶规划问题为：21105minyyw0,1022632121212yyyyyyy；……3分（３）对偶规划问题的最优解为：)2,4(YT。……1分二、求解运输问题。共计18分解：（1）最小元素法：（也可以用其他方法，酌情给分）设xij为由Ai运往Bj的运量（i=1,2,3;j=1,2,3,4）,列表如下：销地产地1B2B3B4B产量1231520302555252550销量15203035100……………3分所以，基本的初始可行解为：x14=25；x22=20；x24=5；X31=15；x33=30；x34=5其余的xij=0。…………3分（2）求最优调运方案：1会求检验数，检验解的最优性：11=2；12=2；13=3；21=1；23=5；32=-1…………3分2会求调整量进行调整：=5…………2分销地产地1B2B3B4B产量12315155302510252550销量15203035100…3分3再次检验…………2分4能够写出正确结论解为：x14=25；x22=15；x24=10x31=15，x32=5x33=30其余的xij=0。……1分最少运费为：535………1分。