《运筹学作业习题》由会员分享,可在线阅读,更多相关《运筹学作业习题(8页珍藏版)》请在金锄头文库上搜索。
1、线性规划建模及单纯形法线性规划建模及单纯形法思考题思考题主要概念及内容:主要概念及内容: 线性规划模型结构(决策变量,约束不等式、等式,目标函数);线性规划标准形式;线性规划模型结构(决策变量,约束不等式、等式,目标函数);线性规划标准形式; 可行解、可行集(可行域、约束集),最优解;基、基变量、非基变量、基向量、非基可行解、可行集(可行域、约束集),最优解;基、基变量、非基变量、基向量、非基 向量;基本解、基本可行解、可行基、最优基。向量;基本解、基本可行解、可行基、最优基。 复习思考题:复习思考题: 1、线性规划问题的一般形式有何特征?、线性规划问题的一般形式有何特征? 2、建立一个实际问
2、题的数学模型一般要几步?、建立一个实际问题的数学模型一般要几步? 3、两个变量的线性规划问题的图解法的一般步骤是什么?、两个变量的线性规划问题的图解法的一般步骤是什么? 4、求解线性规划问题时可能出现几种结果,哪种结果反映建模时有错误?、求解线性规划问题时可能出现几种结果,哪种结果反映建模时有错误? 5、什么是线性规划的标准型,如何把一个非标准形式的线性规划问题转化成标准形式。、什么是线性规划的标准型,如何把一个非标准形式的线性规划问题转化成标准形式。6、试述线性规划问题的可行解、基本解、基本可行解、最优解、最优基本解的概念及、试述线性规划问题的可行解、基本解、基本可行解、最优解、最优基本解的
3、概念及 它们之间的相互关系。它们之间的相互关系。 7、试述单纯形法的计算步骤,如何在单纯形表上判别问题具有唯一最优解、有无穷多、试述单纯形法的计算步骤,如何在单纯形表上判别问题具有唯一最优解、有无穷多 个最优解、无界解或无可行解。个最优解、无界解或无可行解。 8、在什么样的情况下采用人工变量法,人工变量法包括哪两种解法?、在什么样的情况下采用人工变量法,人工变量法包括哪两种解法? 9、大、大 M 法中,法中,M 的作用是什么?对最小化问题,在目标函数中人工变量的系数取什的作用是什么?对最小化问题,在目标函数中人工变量的系数取什 么?最大化问题呢?么?最大化问题呢? 10、什么是单纯形法的两阶段
4、法?两阶段法的第一段是为了解决什么问题?在怎样的情、什么是单纯形法的两阶段法?两阶段法的第一段是为了解决什么问题?在怎样的情 况下,继续第二阶段?况下,继续第二阶段? 作业习题作业习题 1、将下列线性规划问题化为标准型、将下列线性规划问题化为标准型(1) (2) 0,953413223183622453max4214321432143214321xxxxxxxxxxxxxxxxxxxz 0, 0,152342722351232243min4214321432143214321xxxxxxxxxxxxxxxxxxxf2、(、(1)求出下列不等式组所定义的多面体的所有基本解和基本可行解(极点):)
5、求出下列不等式组所定义的多面体的所有基本解和基本可行解(极点):0,124326332321321321xxxxxxxxx(2)对下述线性规划问题找出所有基本解)对下述线性规划问题找出所有基本解,指出哪些是基本可行解指出哪些是基本可行解,并确定最优解并确定最优解. )6 , 1(0031024893631223max6153214321321jxxxxxxxxxxxxxxzj3、用图解法求解下列线性规划问题、用图解法求解下列线性规划问题(1) (2) 0,31223622max211212121xxxxxxxxxz0,155356743min21212121xxxxxxxxz4、在以下问题中,
6、列出所有的基,指出其中的可行基,基础可行解以及最优解。、在以下问题中,列出所有的基,指出其中的可行基,基础可行解以及最优解。0,44622max321321321321xxxxxxxxxxxxz5、用单纯形法求解以下线性规划问题、用单纯形法求解以下线性规划问题(1) (2)0,533223max21212121xxxxxxxxz0,12212432max3213232132xxxxxxxxxxz6、用大、用大 M 法及两阶段法求解以下线性规划问题法及两阶段法求解以下线性规划问题(1) (2) 0,132173132343max3213213221321xxxxxxxxxxxxxz 0,4522
7、33min32132121321321xxxxxxxxxxxxxxf7、某工厂生产过程中需要长度为、某工厂生产过程中需要长度为 3.1 米、米、2.5 米和米和 1.7 米的同种棒料毛坯分别为米的同种棒料毛坯分别为 200 根、根、100 根和根和 300 根。现有的原料为根。现有的原料为 9 米长棒材,问如何下料可使废料最少?米长棒材,问如何下料可使废料最少? 8、有、有 1,2,3,4 四种零件均可在设备四种零件均可在设备 A 或设备或设备 B 上加工,已知在这两种设备上分别上加工,已知在这两种设备上分别 加工一个零件的费用如下表所示。又知设备加工一个零件的费用如下表所示。又知设备 A 或
8、或 B 只要有零件加工均需要设备的启动只要有零件加工均需要设备的启动 费用,分别为费用,分别为 100 元和元和 150 元。现要求加工元。现要求加工 1,2,3,4 零件各三件。问应如何安排使零件各三件。问应如何安排使 总的费用最小。试建立线性规划模型。总的费用最小。试建立线性规划模型。9、某造船厂根据合同从当年起连续三年末各提供四条规格相同的大型客货轮。已知该、某造船厂根据合同从当年起连续三年末各提供四条规格相同的大型客货轮。已知该 厂这三年内生产大型客货轮的能力及每艘客货轮成本如下表所示:厂这三年内生产大型客货轮的能力及每艘客货轮成本如下表所示:已知加班生产时已知加班生产时,每艘客货轮成
9、本比较正常时高出每艘客货轮成本比较正常时高出 60 万元;又知造出来的客货轮若当年万元;又知造出来的客货轮若当年 不交货不交货,每艘每年积压一年造成损失为每艘每年积压一年造成损失为 30 万元。在签定合同时,该厂已积压了两艘未交万元。在签定合同时,该厂已积压了两艘未交 货的客货轮,而该厂希望在第三年未完成合同还能储存一艘备用。问该厂如何安排每年货的客货轮,而该厂希望在第三年未完成合同还能储存一艘备用。问该厂如何安排每年客货轮的生产量,在满足上述各项要求的情况下总的生产费用最少?试建立线性规划模客货轮的生产量,在满足上述各项要求的情况下总的生产费用最少?试建立线性规划模 型,不求解。型,不求解。
10、线性规划问题的对偶及灵敏度分析线性规划问题的对偶及灵敏度分析思考题思考题主要概念及内容:主要概念及内容: 对偶问题,对称形式、非对称形式;对偶定理;对偶单纯形法;灵敏度分析。对偶问题,对称形式、非对称形式;对偶定理;对偶单纯形法;灵敏度分析。 复习思考题:复习思考题: 1、对偶问题和它的经济意义是什么?、对偶问题和它的经济意义是什么? 2、简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么?、简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么? 3、什么是资源的影子价格?它和相应的市场价格之间有什么区别?、什么是资源的影子价格?它和相应的市场价格之间有什么区别? 4、如何根据原问题
11、和对偶问题之间的对应关系,找出两个问题变量之间、解及检验数、如何根据原问题和对偶问题之间的对应关系,找出两个问题变量之间、解及检验数 之间的关系?之间的关系? 5、利用对偶单纯形法计算时,如何判断原问题有最优解或无可行解?、利用对偶单纯形法计算时,如何判断原问题有最优解或无可行解? 6、在线性规划的最优单纯形表中,松弛变量(或剩余变量)、在线性规划的最优单纯形表中,松弛变量(或剩余变量) ,其经济意义是什么?,其经济意义是什么? 7、在线性规划的最优单纯形表中,松弛变量、在线性规划的最优单纯形表中,松弛变量 的检验数的检验数 ,其经济意义是什么?,其经济意义是什么? 8、关于价值系数和资源常量
12、、关于价值系数和资源常量 单个变化对线性规划问题的最优方案及有关因素将会产生单个变化对线性规划问题的最优方案及有关因素将会产生 什么影响?有多少种不同情况?如何去处理?什么影响?有多少种不同情况?如何去处理? 9、线性规划问题增加一个变量,对它原问题的最优方案及有关因素将会产生什么影响?、线性规划问题增加一个变量,对它原问题的最优方案及有关因素将会产生什么影响? 如何去处理?如何去处理? 10、线性规划问题增加一个约束,对它原问题的最优方案及有关因素将会产生什么影响?、线性规划问题增加一个约束,对它原问题的最优方案及有关因素将会产生什么影响? 如何去处理?如何去处理? 作业习题作业习题 1、写
13、出下列问题的对偶规划、写出下列问题的对偶规划2、试用对偶理论讨论下列原问题与它们的对偶问题是否有最优解、试用对偶理论讨论下列原问题与它们的对偶问题是否有最优解3、考虑如下线性规划、考虑如下线性规划(1)写出对偶规划。)写出对偶规划。 (2)用单纯形法解对偶规划,并在最优表中给出原规划的最优解。)用单纯形法解对偶规划,并在最优表中给出原规划的最优解。 (3)说明这样做比直接求解原规划的好处。)说明这样做比直接求解原规划的好处。4、用对偶单纯形方法,求解下面问题、用对偶单纯形方法,求解下面问题(1) (2)0,10536423425min321321321321xxxxxxxxxxxxf 0,28
14、24232max32132321321321xxxxxxxxxxxxxxz5、考虑下面线性规划、考虑下面线性规划0,12416482122232max654321625142132121xxxxxxxxxxxxxxxxxxz其最优单纯形表为:其最优单纯形表为: 基变量基变量1x2x3x4x5x6x3x1x6x2x0 0 1 -1 -1/4 01 0 0 0 1/4 00 0 0 -2 1/2 10 0 0 -3/2 -1/8 00 4 4 2 j0 0 0 -3/2 -1/8 0-14试分析如下问题试分析如下问题(1)分别对)分别对 进行灵敏度分析。进行灵敏度分析。jc(2)对)对 进行灵敏度分析。进行灵敏度分析。ib(3)当)当=时,求新最优解。时,求新最优解。jc(4)当)当= 时,求新最优解。时,求新最优解。ib(5)增加一个约束)增加一个约束 ,问对最优解有何影响?,问对最优解有何影响? (6)确定保持当前最优解不变的)确定保持当前最优解不变的 P1 的范围。的范围。6、已知某工厂计划生产、已知某工厂计划生产 、 、三种产品,各产品需要在甲、乙、丙设备上加工。三种产品,各产品需要在甲、乙、丙设备上加工。1A2A3A有关数据如下有关数据如下试问:试问: (1)如何充分发挥设备能力,使工厂获利最大;)如何充分发挥设备能力,使工厂获利最大; (2)若为了增加产