运筹学试卷.doc

练习卷（A） 课程： 运筹学及其应用 班级： . 学号： 姓名： 题号 一 二 三 四 五 总分 得分 一、填空题（每个空格1分，共14分） 1．线性规划模型中的附加变量有__剩余变量__和__松弛变量_两种类型，引入附加变量的目的是为了将线性规划模型___中的约束不等式变为等式_______。 2．线性规划的解可能出现四种情况：有唯一最优解、有无穷多组最优解、_____无可行解__和__无界解_____。 3．线性规划的灵敏度分析，主要研究初始单纯形表上____系数___的变化对___最优解____的影响。 4．分支定界法和割平面法的基本思路都是通过在原线性规划问题中不断__增加新的约束来缩小 可行域 ，最终得到原问题的整数最优解。 5．单纯形法与对偶单纯形法的主要区别在于：迭代过程中，前者始终保持原问题的可行性，后者始终保持对偶问题的可行性。 6．目标规划中，称为___偏差__变量，表示实际决策值超过第i个目标值__的数量。 7．根据最优化原理可以将多阶段决策问题的求解过程表示成一个_求多个单阶段问题过程。 二、判断题（判断以下结论的正确与否，并简述理由。每题2分，共16分） 1．线性规划问题中要求所有决策变量均为非负变量。 （N） 在标准型中决策变量为非负变量。 2．求解线性规划问题时，加入附加变量不需要改变目标函数。 （ Y ） 3．当可行域为无界区域时，则不可能存在最优解。 （ N ） 与目标函数有关。 4．线性规划问题的可行解同时也是基本解。 （ N ） 可行解包含基本解，但不是基本解。 5．对于极大化线性规划问题，当所有检验数时，则得到最优解。 （ n ） 人工变量为0 6．任何约束条件为不等式的线性规划问题都可以利用对偶单纯形法求解。 （N） 对偶单纯形法用来求解线性规划问题的最优值 7．割平面法中每次可供选择的切割方程不是唯一的。 （ y ） 8．目标规划中的约束条件只有目标约束。 （N ） 也有可能有绝对约束 三、计算题（共30分） 1．已知线性规划的数学模型为:： 2．写出下列线性规划问题的对偶问题模型：（7分） 3．利用分支定界法完成下列整数规划的求解过程（8分） 4．求解0－1规划问题：（7分） 四、应用题（共30分） 1．某公司计划将新开设的4家连锁商店交给4个建筑公司施工，要求每个建筑公司只能承建1家商店。设建筑公司Ai对商店Bj投标的建造费用为Cij万元（见表）。试求解： （1）对这4个建筑公司如何分配建造任务，才能使总建造费用最少？（2）所需的建造费用是多少？（8分） B1 B2 B3 B4 A1 15 18 21 24 A2 19 23 22 18 A3 26 17 16 19 A4 19 21 23 17 2．现有5台设备拟分配给三个用户，设每个用户利用设备的盈利情况如表中所示。问：如何分配这些设备，可以使盈利最大？（7分） 用户 设备台数 盈利函数 1 x1 x 12 2 x 2 6 x 2 3 x 3 4 x 3 3．某厂生产甲、乙两种产品，生产单位产品所需机器时数、劳动工时数和获利情况如表中所示。设该厂在计划期内可提供100个单位的机器时数和120个劳动工时数。 产品 机器时数 劳动工时数 利润（元） 甲 2 4 6 乙 3 2 4 该厂制定了如下目标： （1）利润超过180元；（2）充分利用机器时数；（3）尽量不增加劳动工时；（4）甲产品产量超过22件，乙产品产量超过18件。试列出该目标规划问题的数学模型。（7分） 4．某石油公司的管道网络如图所示，弧上的数字为各管道的流量（单位：万加仑/小时）。如果使用该网络从采地v1向销地v6运送石油，问每小时最多能运送多少加仑石油？（8分） 五、简答题（每题5分，共10分） 1．试根据线性规划问题的基本定理，说明单纯形法的原理。 2．试述运输问题中最小元素法和沃格尔法的区别与联系。 第 2 页 共 6 页 问题（2） x1=2, x2=2 Z2=4 （1）用大M法求该模型的最优解； （2）价值系数C3在什么范围内变化可保持最优解不变？ （8分） 6 5 5 6 4 12 8 10