第五版运筹学基础与应用-大题模拟试题及答案

第五版运筹学基础与应用-大题模拟试题及答案某工厂生产甲、乙、丙三种产品，需要消耗A、B、C三种资源。已知各产品的单位资源消耗量、单位利润以及资源的每日可用限量如下：生产单位甲产品需要消耗A资源3单位、B资源2单位、C资源1单位，获利4千元；生产单位乙产品需要消耗A资源1单位、B资源2单位、C资源3单位，获利3千元；生产单位丙产品需要消耗A资源2单位、B资源4单位、C资源2单位，获利5千元。每日资源限量A为60单位，B为80单位，C为60单位。由于市场需求限制，甲产品的日产量不得超过12单位。请建立该问题的线性规划数学模型，并用单纯形法求解该工厂每日的最优生产计划及最大利润。同时，写出该线性规划问题的对偶问题，并从对偶变量的角度解释各资源的影子价格及其经济意义。建立数学模型。设决策变量,,ms.t将上述模型化为标准型，引入非负松弛变量,,ms.t应用单纯形法进行求解。初始基变量为,,,，初始基可行解为=(0,0,0,60,80,60,12，目标函数值=0。计算非基变量的检验数=−，其中经过第一次迭代后，基变量变为,,{2+此时目标函数Z=100+1.5+0.5−1.25。计算检验数：=1.5,=0.5,经过第二次迭代后，基变量变为,,{+0此时目标函数Z=115+0−0.25−原线性规划问题的对偶问题模型为：ms.t根据对偶理论的互补松弛性定理，已知原问题最优解中，非零变量为=10,=15,=20,=2，对应于对偶问题中的前两个约束和后两个约束均为紧约束（等式成立），即3+2++=4和2+4+某公司有三个产地,,供应某种物资给四个销地,,,。各产地的产量、各销地的需求量以及从产地到销地的单位运价如下矩阵和向量所示。产量分别为：生产7吨，生产4吨，生产9吨。需求量分别为：需要3吨，需要6吨，需要5吨，需要6吨。由于总产量20吨大于总需求量20吨，此时产销平衡。各产地到销地的单位运价表（百元/吨）为：到,,,的运价分别为3,11,3,10；到,,,的运价分别为1,9,2,8；到,,,的运价分别为7,4,10,5。要求用表上作业法求出使总运费最少的调运方案，并给出详细求解过程及最优解的总运费。首先，这是一个产销平衡的运输问题，不需要增加虚设的产地或销地。使用最小元素法（或伏格尔法）寻找初始基可行解。观察单位运价表，寻找最低的运价。最小运价为=1（到）。需求3吨，产量4吨，分配=min(4,3)=3在剩余的运价中寻找最小值，为=2（到）。剩余1吨，需要5吨，分配=min(1,5)=1继续寻找剩余运价的最小值，为=3（到）。产量7吨，还需要4吨，分配=min(7,4)=4剩余运价中最小值为=5（到）。产量9吨，需要6吨，分配=min(9,6)=6剩余运价中最小值为=4（到）。剩余3吨，需要6吨，分配=min(3,6)=3最后只剩=11（到）。剩余3吨，需要3吨，分配=min(3,3)=3为了检验该初始解是否为最优解，需要使用位势法求出各非基变量的检验数。设产地,,的位势分别为,,，销地,,,的位势分别为,,由+==3由+==11由+==2由+==1由+==4由+==5计算非基变量的检验数=−======由于存在=−2,=−寻找以为起点的闭回路。从出发，沿水平或垂直方向前进，遇到基变量才转弯，直到回到起点。闭回路为：→→→（因为为空，这里重新检查基变量。实际上，闭回路应通过现有的基变量。现有基变量：,,,,,。从出发的闭回路为→→→→→→。但这不符合闭回路的简单定义。重新寻找：→→→进行闭回路调整，奇数顶点加上θ，偶数顶点减去θ。得到新的调运方案：=1,=4+1=5,再次使用位势法进行检验。重新设定位势。对于新基变量，有方程组：++++++取=0，则=3,=11。由+11=4，得=−7。由+=计算所有非基变量的检验数：======仍然存在负检验数=−2和=−2。选取作为换入变量。寻找闭回路：→→→（空，错误）。正确的闭回路是→→→进行调整：=0+2=2,=再次进行位势检验。基变量方程：++++++取=0，则=3,=3。由+3=1，得=−2。由+=计算非基变量检验数：======所有非基变量的检验数均大于或等于0，说明当前解已达到最优。最优调运方案为：运往2吨，运往5吨；运往1吨，运往3吨；运往6吨，运往3吨。最小总运费为Z=2×3+5×3+1某企业拟将五台同型号的高精度加工设备分配给下属的三个车间A,B,C。各个车间分配到不同数量的设备后，能够为企业带来的额外利润增量如下表所示：车间A分配0台利润增量为0，分配1台为3，2台为7，3台为9，4台为12，5台为13；车间将问题划分为三个阶段，阶段变量k=1,状态变量表示第k阶段初期初分配给第k到第3个车间的设备总数。初始状态=5。决策变量表示分配给第k个车间的设备数量。允许决策集合为()=状态转移方程为=−，表示分配给第k阶段指标函数(,)表示在第k阶段分配台设备给第k个车间所获得的利润增量。根据题意，(,)为车间A的利润，(,)为车间B最优指标函数()表示在状态下，将剩余设备分配给第k到第3个车间所能获得的最大总利润。逆序递推方程（贝尔曼方程）为：(边界条件为()首先进行第三阶段（车间C）的计算，此时k=3。状态变量可以取值0,1,2,3,4,5。因为这是最后一个阶段，所有剩余设备全部分配给车间C，即=。所以(当=0时，=0，(0当=1时，=1，(1当=2时，=2，(2当=3时，=3，(3当=4时，=4，(4当=5时，=5，(5接着进行第二阶段（车间B）的计算，此时k=2。状态变量可以取值0,1,2,3,4,5。决策变量可以取0到之间的整数。根据递推方程()=当=0时，只能为0。(0)=当=1时，可以取0或1。若=0，利润为(若=1，利润为(故(1)=当=2时，可以取0,1,2。若=0，利润为0若=1，利润为5若=2，利润为10故(2)=当=3时，可以取0,1,2,3。若=0，利润为0若=1，利润为5若=2，利润为10若=3，利润为11故(3)=当=4时，可以取0,1,2,3,4。若=0，利润为0若=1，利润为5若=2，利润为10若=3，利润为11若=4，利润为11故(4)=ma当=5时，可以取0,1,2,3,4,5。若=0，利润为0若=1，利润为5若=2，利润为10若=3，利润为11若=4，利润为11若=5，利润为11故(5)=最后进行第一阶段（车间A）的计算，此时k=1。初始状态=5。决策变量可以取0到5之间的整数。根据递推方程若=0，利润为(若=1，利润为(若=2，利润为(若=3，利润为(若=4，利润为(若=5，利润为(比较上述结果，最大利润(5)=ma根据最优决策进行回溯，寻找最优策略。第一种方案：当=0时，分配给车间A0台设备。此时剩余设备=5−0=5。在(5)的计算中，最优决策为=2，即分配给车间B2台设备。剩余设备=第二种方案：当=2时，分配给车间A2台设备。此时剩余设备=5−2=3。在(3)的计算中，最优决策为=2，即分配给车间B2台设备。剩余设备=因此，该企业有两种最优分配方案：一是车间A分配0台，车间B分配2台，车间C分配3台；二是车间A分配2台，车间B分