运筹学练习及其解答.docVIP

运筹学练习： 判断 （√）1、线性规划问题中，必须有一个要实现的目标。 （×）2、在基可行解中基变量一定为非零。 （√）3、如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 （√）4、在用单纯形法解线性规划问题时，任何一个人工变量都不应该在最优解的基变量组合中。 （×）5、如果一个线性规划问题有可行解，则它必有最优解。 （√）6、运输问题中，用闭回路法和用位势法算出的检验数是一样的。 （√）7、运输问题模型是一种特殊的线性规划模型，因而运输问题也可用单纯形法求解。 （×）8、运输问题的运价表的某一行的所有同乘以一个非零常数，其最优调运方案不变。 （√）9、运输表中给出初始基可行解后，从每一空格出发的闭回路是唯一的。 （×）10、不平衡运输问题不一定有最优解。 填空 １、线性规划是试图合理地分配各种 资源 以最优地实现某个 目标 的规划方法。 ２、标准线性规划问题的特点是：（1）要求目标函数 极大化 ，（2）约 束条件取 等式 ，（3）变量 为非负 。 ３、在线性规划问题的图解法中，如果存在最优解，则这个最优解将处于 可行域的 顶点处 。 解总运费最小的运输问题时，确定最优解的条件是：所有非基变量的 检验数均不为 负 数。 解运输问题一般采用 表上作业 法，确定检验数的方法有 闭回路法和 用位势法 简答题 1、试用图解法求解下述线性规划问题 解：先在直角坐标系中作出可行域，再作目标函数的等值线，可以看出，当目标函数的等值线平移到两直线的交点时，目标函数值最大。即，最优解为：， 2、某商场对售货员的需求情况如下表所示，为保证售货人员充分休息，每周工作五天，休息两天，并要求休息的两天是连续的。问应如何安排售货人员的作息，使其既能满足工作需要又使配备的售货人员的人数最少。建立模型（不必求解）。 时间 需售货员人数 时间 需售货员人数 星期一 15 星期五 31 星期二 24 星期六 28 星期三 25 星期日 28 星期四 19 解：设从周一至周日开始工作的售货人员人数依次为 ，可得如下数学模型 3、将下列线性规划问题化为标准型 解：令，再引进松弛变量和剩余变量，得 4、写出下面线性规划的对偶规则； 解：第二和第三约束条件两边同乘以-1，把“”变为“”，则对偶规则为： 应用题 1、下表给出了各产地和销地的产量和销量（吨），并给出了各产地到各销地的单位运价（元）： 销地 产地 1 2 3 4 产量 A 8 4 7 2 90 B 5 8 3 5 100 C 7 7 2 9 120 销量 70 50 110 80 1 、 请利用最小元素法给出初始调运方案： 销地 产地 1 2 3 4 产量 A 8 10 4 7 80 2 90 B 70 5 30 8 3 5 100 C 7 10 7 110 2 9 120 销量 70 50 110 80 22、请利用闭回路法或位势法改进上述调运方案 （1）检验数： 销 产 1 2 3 4 A 7 8 B 0 -1 C 3 2 （2）改进后的调运方案： 销地 产地 1 2 3 4 产量 A 8 40 4 7 50 2 90 B 70 5 8 3 30 5 100 C 7 10 7 110 2 9 120 销量 70 50 110 80 3、改进后的调运方案是否最优？说明理由。是。检验数非负。 销 产 1 2 3 4 A 6 9 B 1 1 C 2 4 2、用单纯形法求解线性规划问题 1、求出非基变量的检验数，并填入单纯形表中。 2、确定引入变量和退出变量。 3、完成下表的迭代，并求出最优解和最优目标函数值。 4 -4 0 -2 0 0 1 1 1 0 0 5 5 -2 -1 1 0 1 0 6 -- 0 6 2 0 0 1 21 7/2 2 -2 0 0 0 12 0 0 2/3 1 0 -1/6 3/2 -2 0 4/3 0 1 1/6 19/2 4 1 1/3 0 0 1/6 7/2 0 -8/3 0 0 -1/3 -5 引入变量是,退出变量是。 最优解是：，最优目标函数值5