桂电运筹学A复习题.doc

复习题一、填空题（每空1分，共15分）1、若线性问题有可行解，则可行域是 。2、若线性规划有最优解，则一定有 是最优的。3、任何线性问题在于都有惟一的 。4、互为对偶的两个线性规划若一个有无界解，则另一个必 。5、在每个单纯形表中，原问题的这个基本可行解与对偶问题的基本解对应的各自的目标函数值 。6、计划评审技术和关键路线法最适用于 的工程项目。7、增加一个约束条件，在实际问题中相当于增添 。8、表上作业法是 了单纯形法，二者在原理上完全相同。9、要求变量的取值为整数称之为 问题。10、目标规划问题的模型结构与线性规划问题的模型结构 。二、名词解释（共15分）1、数学模型：（2分）2、建立数学模型（3分）3对偶单纯形法（3分）4、表上作业法：（2分）5、分枝定界法：（2分）三、简答题（共45分）1、线性规划的数学模型包括哪三个部分？（3分）2、简述图解法的步骤。（5分）3、求解线性规划问题时最终可能出现哪几种结果？（4分）4、简述单纯形法列表计算的步骤。（6分）5、经济与管理问题要满足什么条件，才能归结为线性规划的模型？（4分）6、简述灵敏度分析的步骤。（5分）7、简述参数线性规划问题的求解步骤。（4分）四、综合应用题（共25分）1、有一份文件要分别译成英文、日文、德文、俄文四种文字，现交给甲、乙、丙、丁四个人去完成，因专长不同，他们完成翻译不同文字所需时间（h）如下表，若每人只能完成翻译一种文字，而每种文字也只能交给其中某一个人来完成，试计算如何分配任务才能使四人完成任务所需时间最少。（8分）人工甲乙丙丁译成英文42410译成日文3443译成德文7385译成俄文84262、一条流水线有5个岗位，分别完成某产品装配的五道工序。现分配甲、乙、丙、丁、戊5个工人去操作，由于每人专长不同，各个工人在不同岗位上的生产效率不一样，具体数字如下表所示。试分析如何分配每个工人的操作岗位，使这条流水线的生产能力为最大。（8分）单位：件/min工位工人甲23417乙34256丙25341丁52325戊376243、某公司打算在3个不同的地区设置4个销售点。根据市场预测部门估计，在不同的地区设置不同数量的销售店，每月可得到的利润如下表所示。试分析如何设置销售店，才能使每月获得的总利润最大？其值为多少？（9分）润售店区地利零01234101625303220121721223010141617一、填空题 共15分，每空1分。1、若线性问题有可行解，则可行域是凸集。P132、若线性规划有最优解，则一定有基本可行解是最优的。P143、任何线性问题在于都有惟一的对偶问题。P2044、互为对偶的两个线性规划若一个有无界解，则另一个必无可行解。P495、在每个单纯形表中，原问题的这个基本可行解与对偶问题的基本解对应的各自的目标函数值恒相等。P526、计划评审技术和关键路线法最适用于一次性的工程项目。P1607、增加一个约束条件，在实际问题中相当于增添一道工序。P648、表上作业法是简化了单纯形法，二者在原理上完全相同。P869、要求变量的取值为整数称之为整数规划问题。P9610、目标规划问题的模型结构与线性规划问题的模型结构基本相同。二、名词解释 共15分。1、数学模型：就是用数学的方法对研究对象的数量关系所进行的定量的描述。（2分）P32、建立数学模型（3分）P373对偶单纯形法（3分）P574、表上作业法：利用产销平衡表和单位运价表直接求解数学模型的方法。（2分）P785、分枝定界法：通过放松模型中对变量的整数限制，求相应的线性规划模型最优解。（2分）P97三、简答题 共45分。1、线性规划的数学模型包括哪三个部分？（3分）P3答：1、决策变量；2、目标函数；3、约束条件。2、简述图解法的步骤。（5分）P8答：1、建立平面直角坐标系，确定可行域；2、给定目标函数一个值，画出相应等值线，确定优化方向；3、平移目标函数的等值线，确定最优解。3、求解线性规划问题时最终可能出现哪几种结果？（4分）P10-11答：1、有惟一一个最优解；2、有无穷多个最优解；3、有可行解，但没有最优解（无界解）；4、无可行解。4、简述单纯形法列表计算的步骤。（6分）P22-23将所给的线性规划问题化成标准形式、选出初始可行基、列单纯形表、最优性检验、确定主元素、得出下一个单纯形表。5、经济与管理问题要满足什么条件，才能归结为线性规划的模型？（4分）P38要求解的目标能用某种效益指标度量其大小，而且能用线性函数来表示这个目标；存在多种可采取的方案；要达到的目标是在一定约束条件下实现的，这些条件可用线性等式或不等式描述。6、简述灵敏度分析的步骤。（5分）P61将参数的变化通过计算反映到最终表上来；检查改变后的最终表是否符合单纯形表的结构要求，或是否符合对偶单纯形表的结构要求；检查原问题是否仍为可行解；检查对偶问题是否仍为可行解；按表列出情况得出结论或决定继续计算的步骤。7、简述参数线性规划问题的求解步骤。（4分）P66-67令参数=0，求解得到最终单纯形表；将参数的变化反映到最终单纯形表中去；设值逐步增大，观察原问题与对偶问题解的变化，看哪一个首先出现非可行解。四、综合应用题 共25分1、有一份文件要分别译成英文、日文、德文、俄文四种文字，现交给甲、乙、丙、丁四个人去完成，因专长不同，他们完成翻译不同文字所需时间（h）如下表，若每人只能完成翻译一种文字，而每种文字也只能交给其中某一个人来完成，试计算如何分配任务才能使四人完成任务所需时间最少。（8分）P110-111人工甲乙丙丁译成英文42410译成日文3443译成德文7385译成俄文8426解：使每行均出现元素：找出每行最小的元素，然后从行的各个元素中减去该行最小的元素： 得 使每列均出现元素：从变化后的效率矩阵的每列找出最小元素，该列上各元素减去这个最小元素： 得 最优解为：甲译俄文，乙译日文，丙译英文，丁译德文，所用最少时间为28h。2、一条流水线有5个岗位，分别完成某产品装配的五道工序。现分配甲、乙、丙、丁、戊5个工人去操作，由于每人专长不同，各个工人在不同岗位上的生产效率不一样，具体数字如下表所示。试分析如何分配每个工人的操作岗位，使这条流水线的生产能力为最大。（8分）P218 6.8题单位：件/min工位工人甲23417乙34256丙25341丁52325戊37624解：划去小于或等于2的数得新表D1D1=再从D1划去小于或等于3的数，又得一新表D2D2=重复以上步骤得D3D3=从D3中可得出甲只能干V，丙只能干II，IV只能由乙干（乙可干的V已由甲干），I只能由丁干（丁可干的V已由甲干），戊只能干III（戊可干的II已由丙干）3、某公司打算在3个不同的地区设置4个销售点。根据市场预测部门估计，在不同的地区设置不同数量的销售店，每月可得到的利润如下表所示。试分析如何设置销售店，才能使每月获得的总利润最大？其值为多少？（9分）P224 8.5润售店区地利零01234101625303220121721223010141617将问题分为3个阶段，k=1，2，3；决策变量xk表示分配给第k个地区的销售点数；状态变量为sk表示分配给第k个至第3个地区的销售点总数；状态转移方程：sk+1=skxk，其中s1=4；允许决策集合：Dk（sk）=xk|0xksk阶段指标函数：gk（xk）表示xk个销售点分配给第k个地区所获得的利润；最优指标函数fk（sk）表示将数量为sk的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：k=3时，g3（x3） f3(s3) x3* 0123400001101012141423161634 1717 4 k=2时，g2(x2)+f3(s2x2) f2(s2) x2* 01234000010+1012+012120+1412+1017+022130+1612+1417+1021+02724 0+17 12+16 17+14