运筹学相关问题

运筹学相关问题————————————————————————————————作者：————————————————————————————————日期：2一、某公司有6个零件加工厂，工厂之间的距离（对称）以下表（公里）。现在要在6家工厂中选一个建装置车间。加工厂123456零件重量10896861.520105——41.63035130.84012——1.35090.6600.71，若是组装一个成品需要各个加工厂的零件重量分别为1.5,1.6,0.8，1.3，0.6,0.7吨，运费为3元·吨公里，那么怎样选厂使得总运费最小？2，若是要从某一厂出发，把全部的道路巡逻一遍回到原处，应该怎样走使得总距离近来？3，若是要从某一厂出发，6个加工厂不重复的都巡逻一遍回到原处，怎样走使得总距离最近？为何？我对这个题目的理解：第一问（运输问题）和第二问（中国邮递员问题）都是会做的，运算量也不是很大，重点是第三问应该是显然的TSP问题，就这个问题，我经过查找资料知道了两种方法：一种是动向规划的解法，但这种方法计算量特别大；另一种方法是分枝定界法，从一本运筹学教材上找到的，马上距离矩阵像匈牙利算法似地办理，但是不是太理解。所以想问下老师（1）题目中说从某一厂出发，我以为可以任选一厂，求得的路线由于是循环的，所以结果应该与选哪一厂没关，想向老师求证一下（2）关于旅游商问题，不知道在老师知道的全部解法中，哪一种是最简略易于手算求解的？二、一条多品种流水线上要轮换生产n种不同样零件，假设从生产零件i变换生产零件j所需要的设备调整时间为T，列出使总的设备调整时间最小的数学模型，以给出n个零件的生产序次。并就以下5个零件给出总调整时间最小的生产序次（要求说明所使用的方法获得的生产序次是最优的）。123451——3810727——61112368——544963——13511856——关于这个题目，我以为也是TSP问题吧，但问题在于这个矩阵是非对称矩阵，所以想请问老师关于非对称矩阵，求解方法可否会有变化？那一种方法可以通用？三、某科学试验可用1,2,3三套不同样仪器中的任一套去完成，每做完一次试验后，若是下次仍用本来的仪器，则需要对该仪器进行检查整修而中止试验；假以下次换用别的一套仪器，则需要拆装仪器，也要中止试验。假设一次试验时间比任何一套仪器的整修时间都长，所以一套仪器换下来隔一次再重新使用时，不会整修而影响试验。设i仪器换成j仪器所需中止试验的时间为t，以下表所示。现要做4次试验，问应怎样安排使用仪器的序次，使总的中止试验的时间最小？Tj123110914i9121023/43658关于这个问题，我以为不是TSP问题，由于依据题目的说法，一套仪器是可以重复出现在4次试验中的，关于这个问题我的做法是用动向规划的方法，将每次试验仪器的编号作为状态变量，不知道老师怎么看？由于动向规划的题目实在是变化多端，所以其实不确定？问题整理：一、相关真题1,2008年第五题，实质是一TSP问题，即出名的旅游商问题（货郎担问题），关于这个问题诚然可以用动向规划解决，但是我试着手算了一下，完好算完最快也要分钟，特别耗时，这在考场上现实吗？我查察了大批的资料，认识到这是一个NP难问题，也就是说没有多项式算法，但是近似算法特别多，所以请问近似算法得出的结果可否正确呢？也许有没有更好的简单易算的解法？求见教;关于这个问题的另一个想法是这是一个工件排序问题，也是特别典型的一类问题，并且在2011年的试题中也有出现，所以不知道解决这种问题有没有一般的理论，可否介绍一些书本也许介绍一些理论，由于我自己找过，但是视线比较狭小，所以没找到比较好的专著。2,2009年第四题的第4小问，出现了时间坐标网络图这一观点，但是课本上并无这一观点，不单这样，正如红宝书中提到的2009年第七题的二人非零和博弈超纲，经过研究真题，我发现每年都有不同样程度的超纲内容，对待这种超纲内容应该怎样备考呢？3，2009年第六题红宝书上写着待写，应该是很难吧，下边是我的理解，希望可以商议下：我对这个题目的理解：第一问是最短路问题，但是要求出每个点的最短路尔后再乘以重量，进而比较各个点。第二问是中国邮递员问题，有奇偶点作业法即可解决，运算量也不是很大。第三问是显然的TSP问题，可以用动向规划求解，如上所言，计算量特别大，但本题的特色矩阵是对称的，不知道这一特色对解决本题有什么好的启示，希望共同商议下。4,2010年第三题，拘束条件明确写明是非负整数，也就是说这属于失散型动向规划的求解，为何红宝书中有连续型的方法求解？5,2010年第八题，红宝书上把求解过程略了，应该是求不出来吧，确立是一线性规划问题吗？刚开始我想的时候也以为是一线性规划问题，但是列出模型此后发现求解特别复杂，加上废弛变量共有22个，这在考场是不行能算出来的吧？是出题人根本就没想让我们做对呢？仍是可以转变成其余问题，比方图论等？从这个题目也可以看出历年的真题的计算量都特别大，若是你是早年的考生，我想请问下考场上的时间是怎样掌握的？可否是会做不完？并且运筹素来重申的建立模型，为何南开这么重申计算呢？仍是说那些计