运筹学总复习.doc

运筹学总复习一、判断题1、如果一个线性规划问题无最优解，则一定也无可行解。 ( )2、单纯形法中可行性条件是指所有变量的检验数均小于等于零。 ( )3、对于发量大于收量的不平衡运输问题，可以增加一个虚拟的收点，转化为平衡的运输问题进行求解。 ( )4、如果图T是图G的支撑树，则T一定是G的支撑子图。 ( )5、对于只含有两个决策变量的线性规划问题，可用图解法求解，但所给问题需化为标准形。 ( )6、一个线性规划问题的对偶问题的对偶是原问题。 ( )7、对偶单纯形法的基本思想为，在保证可行性条件的前提下，从一个可行基转到另一个可行基，直至最优性条件也得到满足。 ( )8、在有向图中，边不重复的路叫做初等路。 ( )9、如果一个线性规划问题存在两个最优解，则一定存在无穷多最优解。 ( )10、如果图T是一棵树，则T一定是连通图。 ( )11、在无向图中，边不重复的链叫做初等链。 ( )12、如果一个线性规划问题有可行解，则一定存在最优解。 ( )13、如果一个原问题有最优解，但相应的对偶问题不一定存在最优解。 ( )14、一个线性规划问题若存在可行域S，则S一定是有界的。 ( )15、对偶问题标准形中松弛变量的个数等于原问题中决策变量的个数。 ( )16、任何运输问题都存在最优解。 ( )17、在任一无向图中，支撑树是含边数最少的连通图。 ( )18、图G有n个顶点、n1 条边，且无圈，则图G一定是树。 ( )19、线性规划问题只要有两个最优解，就一定存在无穷多个解。 ( )20、两阶段法构造的辅助问题的目标函数中含有充分大的正数M。 ( )21、运输问题中若产量及销量均为整数时，则最优解也为整数。 ( )22、有向图中弧不重复的路叫初等路。 ( )二、解答题1、 一公司计划生产产品甲与产品乙，生产产品甲与乙所需要占用设备的时间以及每件产品的利润由下列表格给出，问该公司应如何安排生产计划可使获得的利润为最大。请给出线性规划模型，并用图解法求解。（1）项目产品I产品II每天可用时间设备A设备B51361512利润（元）12（2）项目产品甲产品乙每天限用时数设备A设备B3251158利润（元）34（3）项目产品I产品II每天可用时间设备A设备B22131418利润（元）342、将下列线性规划变为标准形。（1） （2）3、写出下列线性规划问题的对偶问题。（1） （2） 4、利用单纯形法求解下列线性规划。(1) (2) 5、用人工变量法求或对偶单纯形法解下列线性规划。（1） （2） （3） （4）6、对于下列运输问题的运价表（1） （2）（3）不平衡问题：，（4）。（1）用最小元素法求初始可行调运方案。（2）求总运费最小的调运方案（要求列出位势法的各步骤）。7、求下列图的最小支撑树。3314455667V1V3V4V5V6V2211422543373V1V2V3V5V7V4V9V6V8V10（1） （2）8、用Dijkstra算法求下图中到的最短路。V4V2V1V3V5V6V7V84134433261756（1）（2）V73V62432312.53V4V2V1V5V3V4V2V1V3V5V61528212742（3）V5V3VtV4VsV1V2(4, 3)(3, 2)(10, 4) (3, 2)(8, 3)(4, 2)(7, 6)(4, 3)(1, 1)(2, 2