




如果您无法下载资料,请参考说明:
1、部分资料下载需要金币,请确保您的账户上有足够的金币
2、已购买过的文档,再次下载不重复扣费
3、资料包下载后请先用软件解压,在使用对应软件打开
第页共NUMPAGES14页 科目运筹学班级姓名学号时间 题号一二三四五总分分数一、(25分)给出下列线性规划的最优单纯形表,如表1所示。其中分别为第一、第二约束方程中的松弛变量。 表1 →58600基()541002-188011-1100-2-2-3 试分析下列各种条件下最优解(基)的变化: 目标函数中变量的系数由6变为10; 约束条件右端项由变为; 在原线性规划的约束条件上,增加约束条件:。其最优解是否变化?如变化,求出最优解。 二、(25分)表2中给出了一个运输问题,回答下列问题: 1、求解运输问题的初始基可行解的方法有哪几种,都是什么? 2、对于已经求得的初始可行解进行最优性检验有几种方法,都是什么?运输规划的基可行解最优的条件是什么? 3、利用最小元素法求下列运输问题的初始基可行解,并检验该初始基可行解的最优性。 表2 销地 产地产量 3 1 711 9 43 2 1010 8 57 4 9销量3656 三、(20分)用Gomory割平面法求解如下整数规划问题,已知该整数规划的松弛问题的最优单纯形表如表3,其中分别为第一、第二约束方程中的松弛变量。 表3 →1100CBXBb13/410-1/41/417/4013/41/400-1/2-1/2 v4 2 v2 四、(10分)应用Dijkstra算法求图1中的网络从到的最短路径(只需在图上标号并指出最短路径)。 v1 v6 v3 v5 3 5 2 4 2 4 2 图1 五、(20分) 图2 要求:(1)用图上计算法计算图2中各事项的时间参数,各工作的时间参数以及时差; (2)指出该网络图的关键路径。 试题答案 一、(25分)给出下列线性规划的最优单纯形表,如表1所示。其中分别为第一、第二约束方程中的松弛变量。 表1 →58600541002-188011-1100-2-2-3试分析下列各种条件下最优解(基)的变化: (1)目标函数中变量的系数由6变为10; 约束条件右端项由变为; 在原线性规划的约束条件上,增加约束条件:。其最优解是否变化?如变化,求出最优解。 解:(1)题意即为由6变为10,此时最优单纯形表1变为下表: →581000541002-18801【1】-11002-2-3这时原方案已不再是最优方案,再经过一次迭代,得到最终单纯形表: →581000541002-1108011-110-200-5由最终单纯形表可得,此时最优解变为: ,目标函数最优值变为:。 (2)题意即为由12变为30,此时最优单纯形表1中的列向量将变为: 。 最终单纯形表由表1变为下表:(2分) →586005401002-18-10011【-1】100-2-2-3这时原方案已不是最优方案,用对偶单纯形法再迭代一次,得到最终单纯形表: →581000520122010100-1-11-10-2-40-5由最终单纯形表可得,此时最优解变为: ,目标函数最优值变为: (3)增加新约束条件:后,原最优解不满足新约束条件,即16>13不成立,故原最优解会发生变化。(1分) 新约束加入松弛变量标准化:,置于表1得下表: →586000541002-1088011-11001321300100-2-2-30将基变量,,所对应的列向量变为单位向量,经计算得下表 →586000541002-1088011-1100-3002【-3】1100-2-2-30 再利用对偶单纯形法计算得下表:(3分) →58600052104/30-1/32/389011/302/3-1/30100-2/31-1/3-1/300-10/30-11/3-2/3用对偶单纯形法求出新的最优解为: ,目标函数最优值变为:。 二、(25分)表2中给出了一个运输问题,回答下列问题: 1、求解运输问题的初始基可行解的方法有哪几种,都是什么? 2、对于已经求得的初始可行解进行最优性检验有几种方法,都是什么?运输规划的基可行解最优的条件是什么? 3、利用最小元素法求下列运输问题的初始基可行解,并检验该初始基可行解的最优性。 表2 销地 产地产量 3 1 711 9 43 2 1010 8 57 4 9销量36561、答:求解运输问题初始基可行解有三种方法:最小元素法、西北角法和沃格尔法。 2、答:初始基可行解的最优性检验有两种方法,它们是:闭回路法以及位势法。最优条件是所有检验数都非负。(3分) 3、解:此问题是一个产销平衡问题,应用最小元素法求得的初始基可行解如下表: 销地 产地产量 3 64 1 3 37 4 9销量3656下面应用闭回路法或位势法计算得各个空格的检验为: 。 此时还存在负检验数,该初始

ys****39
实名认证
内容提供者


最近下载