几个组合优化问题的研究
山东大学
博士学位论文
几个组合优化问题的研究姓名：董振宁
申请学位级别：博士专业：运筹学与控制论指导教师：刘家壮
20040325
几个组合优化问题的研究
董振宁
（山东大学数学与系统科学学院，济南，２５０１００）
中文摘要
组合优化问题是运筹学中的一个重要分支，随着实践的不断发展，越来越多的新问题利用它的古典模型求解不再合适，比如最短路问题、最小费用流问题、运输问题等．因而需要对原来的古典模型进行改进，构造出新的组和优化模型，并为之设计算法．本文研究了组合优化问题中具有特殊限制的最短路问题、最小费用流同题和运输问题，共分为六章；
第一章绪论，首先介绍了组合优化问题的统一形式，由于现代大多数组合优化问题都是ⅣＰ—ｈａｒｄ的，因此我们接着介绍了ⅣＰ—ｈａｒｄ问题几种常见的处理方法，最后介绍了与本文有关的三类经典组合优化问题的模型及算法．设Ｆ是有限集，ｃ是Ｆ到实数集Ｒ的映射，即ｃ是定义在Ｆ上的一个函数．求＿，∈Ｆ，使得对于任意的Ｙ∈Ｆ，有
ｃ（Ｓ）≤ｃ（ｙ）
成立．。上述问题称为组合优化问题，简记为；求ｒａｉｎｃ（．厂）
早期的组合优化问题通常可以设计出一个方便快捷的算法求得其最优解，比如最小支撑树问题．随着实践的发展，人们遇到了很多组合优化问题都找不到多项式算法．人们将其称为ⅣＰ问题．后来，人们归结出了一类ⅣＰ—ｈａｒｄ问题，认为它们基本上不可能存在多项式时间算法．如果一个算法能够求得这些问题的最优解，则它的计算时间将会很长，以至于无法忍受．由于Ⅳ｜Ｐ—ｈａｒｄ问题无法设计出多项式算法，很多ⅣＰ—ｈａｒｄ问题又非常有应用价值，因而人们都在努力为其设计近似算法、启发式算法或者遗传算法．近似算法能够保证计算结果与最优结果相比较的差别不超过某一常数血，且Ｑ一般较小，但是算法比较复杂，在计算机上编程时比较困难；启发式算法算法通常很简单，很容易在计算机上实现，一般情况下也能够保证计算结果同最优结果差别不超过某一常数ｏ，但是ｎ相对于近似算法要大．也有一些启发式算法无法保证解的近似度，但计算结果通常都比较理想，如本文为
山东大学博￡学位论文
随机时间依赖网络上的最短路问题设计的ＥＳＰ和ＫＥＳＰ苒法，连续时间网络上的最小费用流问题的增广流算法都是启发式算法；遗传算法简称ＧＡ，是一种借鉴生物界自然选择和自然遗传机制的高度并行、随机、自适应的搜索方法，由于遗传算法的寻优过程是从大量的点构成的种群开始平行进行、逐步优化，避免了局部优化结果的产生，并且，遗传算法不要求函数满足可导性质，因此遗传算法常用来解决传统搜索方法解决不了或很难解决的问题。计算结果与最优结果差别一般也很小，但是计算时间相对较长，而且无法从理论上保证计算结果的好坏．本文为带容量限制的带固定费用的最小费用流问题设计的算法就是遗传算法。
第二章研究随机时间依赖网络上的最短路问题．在确定性网络中，最短路问题已经被深入地研究，并被证明有着广泛的用途．在这些问题中，所有边的长度都是常数，目标是寻找一条路，使其经过的边的总长度最小．Ｄｉｊｋｓｔｒａ在文献［２５】中给出了一个时间复杂性为Ｏ（ｎ２）的多项式算法．
随着实践的发展，越来越多的应用领域提出了边上的费用是随机变量的最短路问题．比如在城市交通中，由于堵车、车辆的多少、路上行人及自行车的多少都会影响到车辆的行驶速度，而这些因素又无法确定，因而汽车需要多长时间才能够通过一条街就无法提前获知。但是我们通过以往的经验或者历史资料知道通过每一条街所需８寸ｆ日－Ｉ的概率分布，这样的问题称为随机网络上的最短路问题。
根据边长被确定的早晚的不同，随机网络中的最短路问题大致分为三种情况，１９８７年【２６］Ｇ．Ａｎｄｒｅａｔｔａ便详细论述了这三种情况之间的区别．１９８６年，ＲａｎｄｏｌｐｈＷ．Ｈａｌｌ【３６］首先研究了时间依赖的随机网络上的最短路问题，但是没有给出算法。１９９８年，ＥｌｉｓｅＤ．Ｍｉｌｌｅｒ．Ｈｏｏｋｓ和ＨａｎｉＳ．Ｍａｈｍａｓｓａｎｉｆ３７］研究了边权是时间依赖的离散时间变量的网络，给出了最小可能时间的最优路径算法以及相关概率的下界，但是当路径由３条以上弧组成的时候，理论计算上的最短路实现的概率一般不大于０．０１，基本不可能实现，现实意义不大．２００２年，潭国真和高文【３８】研究了怎样区分两条路的长度的期望值的大小，由此找到的最短路以较大的概率最短，但是由于算法过于复杂，很难实现．
本文研究了随机时间依赖网络上的期望最短路及Ｋ．期望最短路问题，为之给出了极为简便的ＥＳＰ和ＫＥＳＰ算法．ＥＳＰ算法的基本思路如下：从发点
山东火学博士学位论文
１开始，以Ｅ（ｃｌ。（【）））作为边的长度，令￡…７ｅ（，）＝Ｅ（ｃ；ｌ（【）】１，以ｅ（ｏ，（ｔｉｍ：、（ｆ）））作为边（ｉＪｊ的长度，逐步计算每条边的长度，并借用Ｄｉｊｋｓｔｒａ箕法求出随机时间依赖网络上的期望最短路．
这两个算法都是启发式算法，ＥＳＰ算法的时间复杂性为０（ｎ２），ＫＥＳＰ算法的时间复杂性为ｋＯ（ｎ抖‘）。当七固定时，它们都是多项式算法。由于该算法不仅能解决弧权是离散的随机变量的期望最短路问题，而且在弧权是连续分布的随机变量的情况下，依然有效，所以该算法虽不能保证总是找到期望最短路，仍具有极大的现实意义．
第三章研究了一类带费用约束的紧急运输问题．第一节首先介绍了紧急运输问题的研究历史现状。１９４１年Ｈｉｔｃｈｃｏｃｋ［１０】建立了基本的运输问题模型．
１９９８年，ＧｅｏｒｇｅＦ．Ｌｉｓｔ在放射性危险物品运输优化模型中引入了应急问题［４７］，但他的模型意味着：事故一旦发生，总是离应急点最近的出救点参与应急，没有考虑单个出救点不能满足需求的情况．２００１年以来，刘春林等研究了单个资源供应点无法满足需求，需要多供应点组合供应的问题ｆ１２，１３１．他们还研究了运输时间为模糊数的最短路径选择问题ｆ１４，１５】。以及将出救点的最少作为目标时出救方案的选择问题［１６１．但这些研究仍是基于单个需求点的情况，没有考虑到多点同时发生紧急事件的情况．
２００１年，李珍萍［１７】研究了最短时限运输问题，在该文中提出了多供应点，多需求点的紧急情况下的资源运输问题，并给出了多项式时间算法．但该文在追求最长运输时间最短时却没有考虑费用的问题，由于实际工作中可以支配的费用总是有限的。因而本文研究了在总费用限制在一定范围之内的最短时限运输问题．
第二节提出了运输费用限定的最短时限运输问题（以下简称问题Ｉ）：在一个二分网络图上，一端为代表物资储存仓库的Ｓ，另一端为代表物资需求点的Ｔ；每条边（ｊ，Ｊ）对应一个运输费用Ｗ玎和一个运输时间ｔ¨紧急时间发生时，应如何安排运输方案，才能即使运输费用不超过∥，又能使最长的运输时间最短？
第三节首先将其转化为传统的运输问题（以下简称问题ｎ），然后讨论了问题Ｉ同问题Ⅱ的解的对应关系，主要结果有：
定理３．３．２问题ｒ的最优解一定可以在问题Ｉ的基本可行解达到，也一
山东大学博士学位论艾
定可以在问题Ⅱ的基本可行解达到。
问题Ｉ的最优解可以在问题Ⅱ的基本可千亍解处达到。则对最优解的搜索可以借鉴运输问题的表上作业法，在问题Ⅱ的基本可行解中进行搜索，但问题Ⅱ的基本可行鳃不一定是问题Ｉ的可行解，现在我们将问题转换为一个特殊的运输问题，使得其最优解总是在问题Ｉ的基本可行解处达到．设ｘ１为问题Ⅱ的可行解，在问题Ｈ中，令所有ｔ。≥ｔ（ｘ１）的边的运输费用Ⅲ：＝Ｍ，其中Ｍ为一足够大的正数，其它边的运输费用不变，由此得到新的运输闷题Ⅲ（以下简称问题Ⅲ，见第１８页）。由于问题Ⅱ与问题Ⅲ的约束矩阵相同，．所以二者有共同的可行解集，并有以下结论：
定理３．３．３假设问题Ｉ的最优解为ｘ，由Ｘ１构造的问题ｍ的最优解为Ｘ２，如其运输费用ｔｕ’（ｘ２）＝ＦＦ￡叱，』；２，＜ＩＩｆ，则ｔ（ｘ１）＞ｆ（ｘ）．
江１Ｊ＝ｌ
第四节根据定理３．３．３给出了改进的表上作业法（ＭｏｄｉｆｉｅｄＴａｂｌｅＡｌｇ小ｒＲｈｍ）：利用运输问题的表上作业法寻找最小费用运输方案Ｘ，运输时间为ｔ（ｘ），对于运输时间大于或者等于ｔ（ｘ）的边，将其运输费用调整为。。，重新利用表上作业法寻找最小费用运输方案，最优运输方案的运输费用超过Ｉ＇７，则上一次的最优运输方案即为费用不超过Ⅳ的最短时限运输方案。
第五节给出了一个实例，并用改正的表上作业法手工计算出求存储费用有限的最优储运方案，显示了该算法操作方便和收敛快速的优点．
第四章研究了连续时间网络上的最小费用流问题。第一节首先介绍了连续时间网络上的最小费用流问题的历史及现状．１９５７年，Ｆｏｒｄ和Ｆｕｌｋｅｒｓｏｎ最早提出了最大流问题ｆ１８．１９１，１９６１年，’Ｆｕ｜ｋｅｒｓｏｎ又单独研究了最小费用流问豚【２０］．自此，网络流问题分为最大流和最小费用流两个分支．在Ｆｏｒｄ和Ｆｕｌｋｅｒｓｏｎ最早提出的网络流模型中，边上的容量是固定不变的，流不能在中间点停留，而且流通过边是不需要时间的．这样的问题称为静态网络流问蹶．１９５８年，Ｆｏｒｄ和Ｆｕｌｋｅｖｓｏｎ又首先提出了动态网络流（ＤｙｎａｍｉｃＦｌｏｗ）问题，考虑了流通过边需要时间的问题．１９７９年，Ｈａｌｐｅｎ又考虑了边上的容量发生变动和流通过边需要时间的问题｛２２］．Ａｎｄｅｒｓｏｎ．Ｅ．Ｊ．等人于１９８１年提出了连续时闻网络上的最大流问题ｆ２３１，网络中弧的容量随时间变化，流可以在中间点上停留一段时间，而且中间点上可停留的流的容量是随时间变化的，称为连续时间网络流（ｃｏｎｔｉＩｌｌｌＯＵＳｎｅｔｗｏｒｋｆｌｏｗｐｒｏｂｌｅｍ）．但所有研究都是寻找最大流，本文第四章研究了连续时问网络上的最小费用流
山东大学博士学位论文
问题，研究了边上的容量是可变的。流可以在中间点停留，但中间点的存储容量是可变的，单位流经过边支付的费用也是可变的情况下，如何求解最小费用流．
第二节给出了连续时间网络上的最小费用流问题的数学模型：网络Ｎ（ｔ）＝（ＵＡ，ｏ（ｔ），６（ｔ），＂（￡）），在任意时刻ｔ∈【０，Ｔ］，边（ｉ，Ｊ）上通过单位流的费用为ｗｉｊ（ｔ），边（ｉ，ｊ）的容量限制为ｂ（ｔ），在时间【０，ｔ】内顶点Ｊ储存的流量片∑［ｈＡｔ）一ｆｊｋ（ｔ）ｌｄｔ≤ａｊ（ｔ）；如何安排流向（ｔ），使得在ｆｏ，Ｔ】时间内从发点１流到收点礼的流量Ｊ≯∑矗。（ｔ）ｄｔ＝Ｕ０，且费用Ｗ＝Ｆ∑＾Ｊ（ｔ）叫：，（ｔ）ｄ￡
Ｏ，ｎ）ＥＡ（ｉｊ）ＥＡ
最小？
第三节根据一组递推规则定义了可到达点集及到达费用（见第２４页）．第四节给出并证明了增广流的存在性定理和增广流的最优性定理：定理４．４．１（增广流的存在性定理）在网络Ｎ（ｔ）中，对于流ｆ（ｔ）如果收点ｎ在∽叫内恒可达，则可找到新的可行流，’（ｔ），使得＂（，协））＞”（，（ｔ））。
定理４．４．３（增广流的最优性定理）如果流ｆ（ｔ）是最小费用流，则按照定理４．４．１中构造增广链Ｒ的方法，沿链Ｒ增广得到的流，’（ｔ）仍然是最小费用流．
第五节根据增广流的最优性定理，我们给出了连续时间网络Ｙ（ｔ）＝（ＵＡ，ｏ（ｔ），６（ｔ），＂（ｔ））上的流值＂＝＂ｏ的最小费用流问题的增广算法：首先从一个零流开始，逐步地按照可到达点集的构造方法，搜索费用最小的增广链Ｒ，然后沿该链增广，并重复上述过程。直到流值达到Ｆｏ。
第五章研究了无容量限制的最小费用流问题．第一节简单介绍了带固定费用的最小费用流问题的研究现状。Ｆｕｌｋｅｒｓｏｎ最早提出了最小费用流问题，但是这里所考虑的费用只有可变费用，没有固定费用，而ＴｒｉｌｏｃｈａｎＳａｓｔｒｙ于１９９７年研究了无容量限制的带固定费用而没有可变费用的二物资的最小费用流问题［２４１。并给出了多项式算法。很多情况下，我们不仅要支付固定费用，还要支付可变费用．而当运输最远小于网络中边的容量，我们可以认为网络中的边上的容量是无限的．因此，我们将要研究无容量限制的既有可变费用又有固定费用的单物资和二物资的最小费用流问题。
第二节研究了无容量限制的单物资最小费用流问题．首先提出问题，给出一个无向图Ｇ＝（ＶＥ），其中ｙ为顶点集，Ｅ为边集．其中顶点ｓ和ｔ分别
ＬＵ东大学博Ｅ学位论文
称为发点和收点。对于每条边，给定一个固定费用ｕ?。，和可变费用Ｃ¨，若有Ⅲ个单位流通过边（ｉ，，）∈￡，就需要付出固定费用岫，（与流艟，ｎ无关）和可变费用ｍＣ。（与流值，ｎ成正比）。我们的目标是要寻找一个满足流守恒的从发点ｓ到收点ｔ的流值为¨的流，使得固定费用与可变费用的总和最小。这样的问题称为无容量限制的单物资最小费用流问题．然后定义了流图、流路以及流路的流值，并得到定理：
定理５．２．４无容量限制的单物资最小费用流问题必定存在只有一条流路的最优解。
根据定理５２．４得到算法５．１，以“，玉＝Ｗ；，＋Ｃ，７Ｖ作为边长，调用Ｄｉｊｋｓｔｒａ算法，寻找从ｓ到ｔ的最短有向路Ｐ，最小费用流即沿该路流动．最后证明了该算法时间复杂性为Ｏ（ｎ２）．
第三节研究了无容量限制的二物资的最小费用流闯题。首先提出问题，在无向图Ｇ＝（矿Ｅ）中，顶点ｓ。和ｔ。分别称为物资ｌ的发点和收点，顶点８２和ｔ２分别称为物资２的发点和收点。对每条边（ｉ．Ｊ）∈Ｅ，给定一个固定费用毗，和两仑可变费用司，和ｃｉ，两个可变费用分别对应于物资１和物资２．只要有流通过边（ｉ，Ｊ）∈Ｅ，不论是物资１还是物资２，或者两种物资都通过，我们都只需付出毗，的固定费用，可变费用应该等于两种物资的流量分别乘以各自对应的可变费用吐和ｃ毳之和。我们的目标是在无向图Ｇ＝（ＶＥ）上求一个流ｚ＝｛ｚｂｚ２。，），使得从ｓ?到ｔｌ的流的值为Ｋ，从ｓ２到ｔ。的流的值为Ｋ，且总的固定费用与可变费用之和最小．这样的问题称为无容量限制的二物资的最小费用流问题．然后定义了共享路、前向共享路与逆向共享路，并证明定理：、
定理５．３．２在费用图Ｗ（Ｇ）＝（ＶＥ７）中，无容量限制的：二物资最小费用流问题必存在一个只有一条共享路的最优解．
最后根据定理５，３，２得到算法５，２（见第３６页），并证明了其时间复杂性是Ｏ（ｎ３）．最后，第四节通过一个无容量限制的二物资最小费用流问题的例子演示了算法的基本思路。
第六章研究了带容量限制的最小费用流问题。在第五章考虑了无容量限制的带固定费用的最小费用流问题后，我们认为在很多情况下，运输量将会大于网络中边上的容量限制，因此我们在这里研究了带容量线制的既有固定费用又有可变费用的最小费用流问题。
山东大学博士学位论文
第二节首先提出带容量限制的带固定费用最小费用流问题，该问题同前一章研究无容量限制的单物资的最小费用流问题的区别在于每条边（ｚ．』）有一个容量限制ｂ…
假设ｘ为带固定费用的最小费用流问题的最优解（最小费用流），Ｅ７为其所经过的所有的边。下面的定理给出了最优解（最小费用流）Ｘ的一个性质：
定理６．２．１最优解Ｘ一定是在所经过的边集Ｅ’构成的子网络Ｇ’＝Ｇ（ＶＥ’）上关于可变费用Ｇ，的最小费用流．
将Ｇ＝（ＵＥ７）中所有从ｓ到ｔ的路依可变费用的大小排序为Ｐ１．Ｐ２，…，Ｐ々ｌ，设Ｇ＝（ＶＥ）中可变费用小于ｐｋｔ的从ｓ到ｔ路为一，玛．…．暝２，设Ｃ＝｛ｅ?，ｅ２，…，ｅｋｅ｝为从Ｇ＝（ＫＥ）中删除这些边后，使得路硝，凼．一．ｐ：２全部被截断且ＣｎＥ，＝９的极小边子集，于是有∥ＣＥ＼Ｃ，并记Ｅ”＝Ｅ＼Ｃ，则定理６．２．２图Ｇ”＝（ＵＥ，‘）中关于可变费用的最小费用流是带固定费用的最小费用流问题的最优解Ｘ．
根据定理６．２．２，原问题转化为寻找边集∥或者ｅ的问题。这是一个组合优化问题，因而我们可以求助于遗传算法．
第三节首先介绍了遗传算法的基本步骤，然后根据带固定费用的最小费用流问题的特点为其设计了遗传算法。第四节设计了三个实验，用计算机随机产生的算例验证了该算法的加权平均近似比不超过１．２３，１００个顶点的实例的计算时间约为９０秒，计算时间随顶点数的增加线性变化。
本文的创新点为：
１．在研究随机时闻依赖网络的最短路问题时，提出了以到达顶点的期望时间作为该顶点的到达时间。进而以相关边的期望边长作为边长，并设计出了ＥＳＰ算法；
２．提出了带费用约束的紧急运输问题，研究了该问题与传统运输问题的可行解及基本可行解之间的相互关系后，得到了：
定理３．３．２问题Ｉ的最优解一定可以在问题Ｉ的基本可行解达到，也一定可以在问题Ⅱ的基本可行解达到．
定理３．３．３假设问题Ｉ的最优解为Ｘ。由Ｘ１构造的问题ｍ的最优解为Ｘ２，如其运输费用ＷＩ（ｘ２）＝∑∑札『。Ｉ，ｚ。２＜Ｗ。则ｔ（ｘ１）＞￡｛ｘ）。
ｉ＝ｌｊ＝ｌ
３．在研究连续时间网络上的最小费用流问题时，定义了可到达点集的到
山东大学博士学位论文达费用；
４．提出了无容量限制的带固定费用和可变费用的最小费用流问题固定费用的二物资最小费用流问题构造了费用图Ｗ（Ｇ）＝（ＵＥ７）；
５．提出了带容量限制的带固定费用和可变费用的最小费用流问题为带证明
了最优解的两个性质定理：
定理６．２．１最优解Ｘ一定是在所经过的边集Ｆ构成的子网络Ｇ’＝Ｇ（ＫＥ‘）上关于可变费用Ｃ０的最小费用流．
定理６．２．２图Ｇ”＝（ＵＥ”）中关于可变费用的最小费用流是带固定费用的最小费用流问题的最优解ｘ．
关键词：组合优化；最短路；最小费用流；紧急运输；随机网络；固定费用
ＳＴＵＤＹｏＮＳＯＭＥＣＯＭＢＩＮＡＴＯＲＩＡＬｏＰＴＩＭＩＺＡＴＩＯＮＰＲｏＢＬＥＭＳ
Ｄｏｎｇ（ＳｃｈｏｏｌｏｌＭａｔｈ．８Ｓｙｓ．Ｓｃｉ．，Ｚｈｅｎｎｉｎｇ
ＳｈａｎｄｏｕｇＵｎｉｖ．，Ｊｉｎａｎ２５０１００）
Ａｂｓｔｒａｃｔ
ＣｏｍｂｉｎａｔｏｒｉａｌＯｐｔｉｍｉｚａｔｉｏｎｉｓｏｎｅｉｍｐｏｒｔａｎｔｂｒａｎｃｈｏｆＯｐｅｒａｔｉｏｎＲｅｓｅａｒｃｈＷｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｐｒａｃｔｉｃｅ，ｔｈｅｒｅａｒｅｍｏｒｅａｎｄｍｏｒｅｎｅｗｐｒｏｂｌｅｍｓｔｈａｔｃａｎｎｏｔｂｅｓｏｌｖｅｄｂｙｔｈｅｉｒｔｒａｄｉｔｉｏｎａｌｍｏｄｅｌｓ，ｓｕｃｈａｓＳｈｏｒｔｅｓｔＰａｔｈ，ＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗａｎｄＴｒａｎｓｐｏｒｔａｔｉｏｎＰｒｏｂｌｅｍ，Ｓｏｖｒｅｔｒｙｔｏｃｏｎｓｔｒｕｃｔｓｏｍｅｎｅｎ＋ｃｏｍｂｉ－ｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｍｏｄｅｌｓ，ａｎｄｄｅｓｉｇｎａｌｇｏｒｉｔｈｍｓｆｏｒｔｈｅｍ．ＴｈｉｓｄｉｓｓｅｒｔａｔｉｏｎｓｔｕｄｉｅｓｓｏｍｅＳｈｏｒｔｅｓｔＰａｔｈ，ＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗａｎｄＴｒａｎｓｐｏｒｔａｔｉｏｎＰｒｏｂｌｅｍｗｉｔｈｓｐｅｃｉａｌｃｏｎｓｔｒａｉｎｔｓ．
Ｃｈａｐｔｅｒｌｉｓｉｎｔｒｏｄｕｃｔｉｏｎ．Ｆｉｒｓｔｌｙｗｅｉｎｔｒｏｄｕｃｅｄｔｈｅｕｎｉｆｏｒ，ｎｍｏｄｅｌｏｆＣｏｒｎ—ｈｉｎａｔｏｒｉａｌＯｐｔｉｍｉｚａｔｉｏｎ．ＢｅｃａｕｓｅｍａｎｙＣｏｍｂｉｎａｔｏｒｉａｌＯｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓａｒｅⅣ尸一ｈａｒｄ．ｗｅｉｎｔｒｏｄｕｃｅｄｓｏｍｅｆａｍｉｌｉａｒｍｅｔｈｏｄｓｔｏｄｅｎｌｗｉｔｈⅣ尸一ｈａｒｄ．Ｆｉｎａｌｌｙ，ｗｅｉｎｔｒｏｄｕｃｅｄｍｏｄｅｌｓａｎｄａｌｇｏｒｉｔｈｍｓｏｆｔｈｒｅｅｃｌａｓｓｉｃａｌＣｏｍｂｉｎａｔｏｒｉａｌＯｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓｔｏｂｅｓｔｕｄｉｅｄｉｎｔｈｉｓｄｉｓｓｅｒｔａｔｉｏｎ．
ＬｅｔＦｂｅａｌｉｍｉｔｅｄｓｅｔ，ａｎｄＣｉｓａｍａｐｐｉｎｇｆｒｏｍＦｔｏＲ，ｔｈａｔｉｓｔＯｓａｙ．ＣｉｓａｆｕｎｃｔｉｏｎｏｎＦ．Ｔｏｆｉｎｄｓｕｃｈａｎ，∈Ｆｔｈａｔｃ（ｆ）≤ｃ（ｇ）ｆｏｒａｎｙｇ∈ＦｉｓｃａｌｌｅｄｃｏｍｂｉｎａｔｏｒｉａｌＯｐｔｉｍｉｚａｔｉｏｎ，ａｎｄｉｔｉｓａｂｂｒｅｖｉａｔｅｄｔｏ卿。（，）
Ｅａｒｌｙｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓｕｓｕａｌｌｙｈａｖｅｓｏｍｅｒａｐｉｄａｎｄｅａｓｙａｌｇｏｒｉｔｈｍｓｔｏｇｅｔｔｈｅｉｒｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｓ．Ｗｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆ。ｐｒａｃｔｉｃｅ．ｐｅｏｐｌｅｍｅｅｔｗｉｔｈｍａｎｙｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓｔｈａｔｄｏｎｏｔｈａｖｅｐｏｌｙｎｏｍｉａｌａｌｇｏｒｉｔｈｍ．ａｎｄｔｈｅｙａｒｅｃａｌｌｅｄＮＰｐｒｏｂｌｅｍｓ，ＡｆｔｅｒｗａｒｄｐｅｏｐｌｅｓｏｒｔｅｄｏｕｔｓｏｍｅＮＰ—ｈａｒｄｐｒｏｂｌｅｍｓ．ａｎｄｔｈｅｙａｒｅｈａｒｄｌｙｔｏｈａｖｅｐｏｌｙｎｏｍｉａｌｔｉｍｅａｌｇｏｒｉｔｈｍ．ＩｆａｎａｌｇｏｒｉｔｈｍＣ址＇ｒｌｆｉｎｄｔｈｅｉｒｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｓ．ｔｈｅｎｉｔｓｒｕｎｎｉｎｇｔｉｍｅｍｕｓｔｂｅｔｏｏｌｏｎｇｔｏｂｅｕｎｂｅａｒａｂｌｅ．
ＢｅｃａｕｓｅｗｅｈａｖｅｎｏｔｆｏｕｎｄａｎｙＰｏｌｙｎｏｍｉａｌＴｉｍｅＡｌｇｏｒｉｔｈｍｆｏｒｔｈｅｓｅｐｒｏｂ—
ＩＸ
山东大学博士学位论文
ｖａｒｉａｂｌｅｃｏｓｔ
ｃ，ｊｏｎＧ’＝Ｇ（ＫＥ’）．
Ｔｈｅｏｒｅｍ６．２．２ＴｈｅｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗｃｏｒｒｅｓｐｏｎｄｉｎｇｔｏｖａｒｉａｂｌｅＣｏｓｔｉｎＧ”＝（ＶＥ”）ｉｓｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎＸｏｆｔｈｅｏｒｉｇｉｎａｌｐｒｏｂｌｅｍ．
Ｋｅｙｗｏｒｄｓ：Ｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎ；Ｓｈｏｒｔｅｓｔｐａｔｈ；Ｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗ；Ｅｍｅｒｇｅｎｃｙｔｒａｎｓｐｏｒｔａｔｉｏｎ；Ｓｔｏｃｈａｓｔｉｃｎｅｔｗｏｒｋ；Ｆｉｘｅｄｃｏｓｔ
山东足学博士学位论艾
１（、ｉｌｌｓ，ａｌｌｄｔｈｅｙａｒｅⅥ，ｒ、‘ｕｓｅｆｕｌｔｏ¨ｌｓｉｎａｇｒｅａｔｖｔｎ’ｉｅｔｙｏｆｃｏｎｔｅｘｔｓ．ｐｅｏｐｌｅｈａｖｅｔ¨ｔｌＶ￥ＯｌｌｌｅＡｐｐｒｏｘｉｍａｔｅＡｌｇｏｒｉｔｈｍ．ＨｅｕｌｉｓｔｉｔＡｌｇｏｒｉｔｔｕｎａｎｄＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｎｌｅｔｃ．ＡｐｐｒｏｘｉｍａｔｅＡｌ９０１：’ｉｔｈｎｌＣａｌｌｇｅｔａｓｏｌｕｔｉｏｎｔｈａｔＩｌ￡ｂｔｉｌｅｄｉｆｆｅｒｅｎｃｅⅥ７ｉｔｈｔｉｔ｛１ｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｎｏｌｎｏｌ。Ｐｔｈａｎ（、ａｎｄ甜ｉｓｕｓｕａｉｌ，ｖｖｅｒｙｓｍａｌｌ．Ｂｕｔｔｈｅａｌｇｏｒｉｔｈｎｌｉｓｕｓｕａｌｌｙｖｅｒｙｃｏｍｐｌｉｃａｔｅｄ，ａＭｉｓｄｉｆｆｉｃｕｌｔｔｏｐｒｏｇｒａｍ：ＨｅｕｒｉｓｔｉｃＡｌｇｏｒｉｔｈｍｉｓｕｓｕａｌｌｙｖｅｒｙｓｉｍｐｌｅ，ａｎｄｉｓｅａｓｙｔＯｐｒｏｇｒａｍ．ａｎｄｎｏｒｍａｌｌｙｉｔｃａｎｇｕａｒａｎｔｅｅｔｈａｔｔｈｅｓｏｌｕｔｉｏｎｈａｓｄｅｆｅｒｅｎｃｅｗｉｔｈｔｌｉｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｎｏｍｏｒｅｔｈａｎＱ．ｂｕｔｔｈｅｏｉｓｕｓｕａｌｌｙｍｏｒｅｔｈａｎｔｈａｔｏｆＡｐｐｒｏｘｉｍａｔｅＡｌｇｏｒｉｔｈｍ．ＴｈｅｒｅａｒｅｓｏｍｅＨｅｕｒｉｓｔｋＡｌｇｏｒｉｔｈｍｓｎｏｔａｂｌｅｔｏｇｕａｒａｎｔｅｅｔｈｅａｐｐｒｏｘｉｍａｔｉｏｎｄｅｇｒｅｅＯＬ．ｂｕｔｔｈｅｉｒｓｏｌｕｔｉｏｎｓａｒｅｕｓｕａｌｌｙｖｅｒｙｇｏｏｄ．Ｉｎｔｈｉｓｄｉｓｓｅｒｔａｔｉｏｎ．ｔｈｅＡｌｇｏｒｉｔｈｍＥＳＰａｎｄＫＥＳＰｆｏｒｔｈｅｓｈｏｒｔｅｓｔｐａｔｈｐｒｏｂｌｅｍｓｉｎｓｔｏｃｈａｓｔｉｃａｎｄｔｉｍｅ—ｄｅｐｅｎｄｅｎｔｎｅｔｗｏｒｋ，ａｎｄｔｈｅＡｕｇｍｅｎｔＰａｔｈＡｌｇｏｒｉｔｈｍｆｏｒｔｈｔ、ｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗｐｒｏｂｌｅｍｏｎｃｏｎｔｉｎｕｏｕｓｎｅｔ—ｗｏｒｋａｒｅａｌｌＨｅｕｒｉｓｔｉｃＡｌｇｏｒｉｔｈｍｓ．ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ（ａｂｂｒｅｖｉａｔｅｄｔｏＣＡ）ｉｓａｓｔｏｃｈａｓｔｉｃｐａｒａｌｌｅｌｓｅｌｌ－ａｄａｐｔｉｖｅｓｅａｒｃｈｉｎｇｍｅｔｈｏｄｔｈａｔｌｅａｒｎｓｆｒｏｍｂｉｏｌｏｇｉｃａｌｎａｔ?ｕｒａｌｓｅｌｅｃｔｉｏｎａｎｄｇｅｎｅｔｉｃｓ．ＢｅｃａｕｓｅＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ’Ｓｓｅａｒｃｈｉｎｇｂｅａｎｓｆｒｏｍａｇｒｅａｔｐｏｐｕｌａｔｉｏｎ，ｒｕｎｓｐａｒａｌｌｅｌｌｙ．ａｎｄｇｅｔｓｉｔｓｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｓｔｅｐｂｙｓｔｅｐ，ｉｔｃａｌｌａｖｏｉｄｔｈｅｌｏｃａｌｌｙｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ．ＡｎｄＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｄｏｎｏｔｒｅｑｕｉｒｅｔｈａｔｔｈｅｏｂｊｅｃｔｆｌｍｃｔｉｏｎｓｈｏｕｌｄｂｅｄｉｆｆｅｒｅｎｔｉａｌ、ＳＯＧｅｎｅｔｉｃ、Ａｌｇｏｒｉｔｈｍａｒｅｕｓｅｄｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｔｈａｔｃａｎｎｏｔ．ｏｒａｒｅｄｉｆｆｉｃｕｌｔｔｏｂｅｓｏｌｖｅｄｂｙｏｔｈｅｒｍｅｔｈｏｄｓ．ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ’Ｓｓｏｌｕｔｉｏｎｉｓｕｓｕａｌｌｙｎｅａｒｔｏｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ，ｂｕｔｉｔｕｓｕａｌｌｙｒｕｎｓｉｎｍｕｃｈｍｏｒｅｔｉｍｅ，ａｎｄｉｔｃａｎｎｏｔｇｕａｒａｎｔｅｅａｇｏｏｄｓｏｌｕｔｉｏｎｔｈｅｏｒｅｔｉｃａｌｌｙ．Ｔｈｉｓｄｉｓｓｅｒｔａｔｉｏｎｇｉｖｅｓ８ｎｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｔｏｔｈｅ，ｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗｗｉｔｈｆｉｘｅｄＣＯＳｔ．
Ｃｈａｐｔｅｒ２ｓｔｕｄｉｅｄｔｈｅＳｈｏｒｔｅｓｔＰａｔｈＰｒｏｂｌｅｍｏｎＳｔｏｃｈａｓｔｉｃＴｉｍｅ－ｄｅｐｅｎｄｅｎｔＮｅｗｏｒｋ．Ｉｎｔｈｅｄｅｔｅｒｍｉｎｉｓｔｉｃｎｅｔｗｏｒｋ，ｔｈｅｓｈｏｒｔｅｓｔｐａｔｈｐｒｏｂｌｅｍｈａｓｂｅｅｎｓｔｕｄｉｅｄｅｘｔｅｎｓｉｖｅｌｙａｎｄｆｏｕｎｄｔｏｂｅａｖｅｒｙｕｓｅｆｕｌｔｏｏｌｉｎａｇｒｅａｔｖａｒｉｅｔｙｏｆｃｏｎｔｅｘｔｓ．Ｉｎｔｈｅｓｅｐｒｏｂｌｅｍｓ，ｔｈｅａｒｃＣＯＳＴＳａｒｅｃｏｎｓｔａｎｔｓ．Ｔｈｅｇｏａｌｉｓｔｏｍｉｎｉｍｉｚｅｔｈｅｓｕｍｏｆｔｈｅｃｏｓｔｓｏｆｔｈｅｔｒａｖｅｒｓｅｄａｒｅｓ．ＴｈｅｐｒｏｂｌｅｍｈａｓｂｅｅｎｓｏｌｖｅｄｂｙＤｉｊｋｓｔｒａｉｎ１９５９１２５］．
Ｗｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｐｒａｃｔｉｃｅ，ｔｈｅｒｅａｒｅｍｏｒｅａｎｄｍｏｒｅａｐｐｌｉｃａｔｉｏｎｆｉｅｌｄｓｉｎｗｈｉｃｈｉｔｉｓｎａｔｕｒａｌｔＯｔａｋｅａｒｃ（ｏＳｔＳａｓｒａｎｄｏｍｖａｒｉａｂｌｅｓ．ｓｕｃｈ８ｓｖｅｈｉｃｌｅ－ｒｏｕｔｉｎｇｉｎｔｈｅｐｒｅｓｅｎｃｅｏｆｎｎｃｅｌｒａｉｎｗｅｎｔｈ（－ｌｃｏｎｄｉｔｉｏｎｓ，ＷｅＣａｎｌｌＯｔｋｎｏｗａｒｃｌｅｕｇｔｌｌｉｎ
山东大学博士学位论文
ａｄｖａｎｃｅ，ｂｕｔｗｅｋｕｏｗｉｔｓｐＬｏｂａｂｉｌｉｓｔｉｅｄｉｓｔｒｉｂｕｔｉｏｎｂｙ０１．１ｒｅｘＩ）ｅｒｉｅｕｃｅｏｒｈｉｓｔｏｒ５‘ｄａｔａ．ＳｕｃｈａｐｒｏｂｌｅｍｉｓｃａｌｌｅｄｔＩｍ．ＳｈｏｒｔｅｓｔＰａｔｈＰｒｏｂｌｅｍＯｉｌＳｔｏｃｈａｓｔｋＮｅｔｗｏｒｋＴｈｅｒｅａｒｅａｂｏｕｔｔｈｒｅｅｆｏｒｍｕｌａｔｉｏｕｓｄｅｐｅｎｄｉｎｇｏｎｔｈｅｔｉｍｅｗｈｅｎｔｈｅｒｅａｌｉｚｅｄｖａｌｕｅｓｏｆｔｈｅａｒｃＣＯＳＴＳａｒｅｌｅａｒｎｅｄ．Ｉｌｌ１９８７．Ｇ．Ａｎｄｒｅａｔｔａｄｉｓｃｕｓｓｅｄｔｈｅｄｉｆｉｅ【－ｅｎｃｅｂｅｔｗｅｅｎｔｈｅｓｅｔｈｒｅｅｃａｓｅｓｉｎｄｅｔａｉｌ［２６２７］．
Ｉｎ１９９６，ＲａｎｄｏｌｐｈＷ．Ｈａｌｌｆ３６】ｓｔｕｄｉｅｄｔｈｅｓｔｏｃｈａｓｔｉｃａｎｄｔｉｍｅ－ｄｅｐｅｎｄｅｎｔｎｅｔｗｏｒｋ，ｂｕｔｈｅｄｉｄｎｏｔｇｉｖｅａｌｌａｌｇｏｒｉｔｈｍ．Ｉｎ１９９８．ＥｌｉｓｅＤＭｉｌｌｅｒ－ＨｏｏｋｓａｎｄＨａｎｉＳ．Ｍａｈｍａｓｓａｎｉ【３７］ｓｔｕｄｉｅｄｔｈｅｎｅｔｗｏｒｋｗｈｉｃｈａｒｃｃｏｓｔｓａｒｅｔｉｍｅ－ｄｅｐｅｕｄｅｎｔｄｉｓｃｒｅｔｅｒａｎｄｏｍｖａｒｉａｂｌｅｓ．Ｔｈｅ＞‘ｇａｖｅａｎａｌｇｏｒｉｔｈｍｔｏｆｉｎｄｔｈｅｓｈｏｒｔｅｓｔｐａｔｈｕｎｄｅＩａｎｙｐｏｓｓｉｂｉｌｉｔｙ，ａｎｄｈｅｇａｖｅａｌｏｗｅｒｂｏｕｎｄｏｆｔｈｅｒｅｌｅｖａｎｔｐｒｏｂａｂｉｌｉｔｙ．Ｂｅｃａｕｓｅｔｈｅｐｒｏｂａｂｉｌｉｔｙｏｆｔｈｅｓｈｏｒｔｅｓｔｐａｔｈｉｓｓｍａｌｌｅｒｔｈａｎ１０～ｉｎｇｅｎｅｒａｌ，ＳＯｉｔｉｓｈａｒｄｌ）’ｒｅａｌｉｚａｂｌｅ．ＧｕｏｚｈｅｎＴａｎａｎｄＷｅｎＧａｏｆ３８１ｓｔｕｄｉｅｅｌｈｏｗｔｏｄｅｔｅｒｍｉｎｅｔｈａｔｏｒｅｐａｔｈｗｈｉｃｈｉｓｓｈｏｒｔｅｒｉｎｅｘｐｅｃｔａｔｉｏｎｔｈａｎａｎｏｔｈｅｒ．ａｎｄｔｈｅｙｇｉｖｅａｎａｌｇｏｒｉｔｈｍｔｈａｔｉｓｃｏｒｒｅｃｔｔｈｅｏｒｅｔｉｃａｌｌｙｂｕｔｉｔｉｓｎｏｔｅａｓｙｔｏｂｅａｐｐｌｉｅｄ．
Ｉｎｔｈｉｓｄｉｓｓｅｒｔａｔｉｏｎ，ｗｅｓｔｕｄｉｅｄｔｈｅｓｔｏｃｈａｓｔｉｃａｎｄｔｉｍｅ－ｄｅｐｅｎｄｅｎｔｎｅｔｗｏｒｋＡｎｄｗｅｇａｖｅｔｈｅＥｘｐｅｃｔｅｄＳｈｏｒｔｅｓｔＰａｔｈＰｒｏｂｌｅｍａｎｄｔｈｅＫ—ＥｘｐｅｃｔｅｄＳｈｏｒｔｅｓｔＰａｔｈｐｒｏｂｌｅｍｏｎｔｈｅＮｅｔｗｏｒｋ．ＷｅｐｕｔｆｏｒｗａｒｄＥＳＰａｎｄＫＥＳＰａｌｇｏｒｉｔｈｍｓｆｏｒｔｈｅｍ，ＥＳＰａｌｇｏｒｉｔｈｍＳｍａｉｎｉｄｅａｉｓａｓｆｏｌｌｏｗｓ：Ｆｒｏｍｎｏｄｅ１，ｌｅｔｅｄｇｅｌｅｎｇｔｈｂｅＥ（ｃｌ，（Ｏ））；ｔｈｅｎｌｅｔｔｉｍｅ（ｉ）＝Ｅ（ｃｎ（０））、ａｎｄｌｅｔｌｅｎｇｔｈｏｆｅｄｇｅ（ｉ．Ｊ）ｂｅＥ（ｅｑ（ｔｉｍｅ（ｉ））），ｃａｌｃｕｌａｔｅｅａｃｈｅｄｇｅ’Ｓｌｅｎｇｔｈｏｌｌｅｂｙｏｎｅ．ａｎｄｂｙＤｉｊｋｓｔｒａａｌｇｏｒｉｔｈｍｆｉｎｄｔｈｅｅｘｐｅｃｔｅｄｓｈｏｒｔｅｓｔｐａｔｈ．
Ｔｈｅｔｗｏａｌｇｏｒｉｔｈｍｓａｒｅａｌｌｈｅｕｒｉｓｔｉｃ，ａｎｄｔｈｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙｏｆＥＳＰｉｓｏ（ｎ２），ａｎｄｔｈａｔｏｆＫＥＳＰｉｓｋＯ（ｎｋ＋１）．Ｗｈｅｎｋｉｓｆｉｘｅｄ，ｔｈｅｙａｒｅａｌｌｐｏｌｙｎｏｍｉａｌｔｉｍｅａｌｇｏｒｉｔｈｍｓ．Ｔｈｅｙｃａｔ］ｓｏｌｖｅｎｏｔｏｎｌｙｔｈｅｐｒｏｂｌｅｍｗｈｉｃｈａｒｃｃｏｓｔｓａｒｅｄｉｓｃｒｅｔｅｒａｎｄｏｍｖａｒｉａｂｌｅｓｂｕｔａｌｓｏｔｈｅｐｒｏｂｌｅｍｗｈｉｃｈａｒｃｃｏｓｔｓａｒｅｃｏｎｔｉｎｕｏｕｓｒａｎｄｏｍｖａｒｉａｂｌｅｓ．Ｔｈｏｕｇｈｉｔｃａｎｎｏｔｆｉｎｄｔｈｅｅｘｐｅｃｔｅｄｓｈｏｒｔｅｓｔｐａｔｈｎｅｃｅｓｓａｒｉｌｙ，ｉｔｉｓｕｓｅｆｕｌｎｅｓｓｇｒｅａｔｌｙ．
Ｃｈａｐｔｅｒ３ｓｔｕｄｉｅｄａｋｉｎｄｏｆＥｍｅｒｇｅｎｃｙＴｒａｎｓｐｏｒｔａｔｉｏｎＰｒｏｂｌｅｍｗｉｔｈＣｏｓｔＣｏｎｓｔｒａｉｎｔ．Ｓｅｃｔｉｏｎｌｆｉｒｓｔｌ｝’ｉｎｔｒｏｄｕｃｅｄｔｈｅｈｉｓｔｏｒｙｏｆｅｍｅｒｇｅｎｃｙｔｒａｎｓｐｏｒｔａｔｉｏｎｐｒｏｂｌｅｍ，Ｉｎｌ９４１．Ｈｉｔｃｈｅｏｃｋ［１０】ｇａｖｅｂａｓｉｃｔｒａｎｓｐｏｒｔａｔｉｏｎｐｒｏｂｌｅｍｉｎｔｈｅｆｉｒｓｔｔｉｍｅ．
山东大学博士学位论文
Ｉｎ１９９８Ｇｅ（）ｒｇｅＦＬｉｓｔｐｌｏｐｏｓｅｄＥｍｅｒｇｅｎｃｙＰｒｏｂｌｅｍｉｎＩ，ｍ】《）｝Ｉ‘ｔｉｖ（１ｈａ／‘ａｒｄｏｕｓｍａｔｅｒｉａｌｔｒａｎｓｐｏｒｔａｔｉｏｎｐｒｏｂｌｅｍ．ｂｕｔｈｉｓｍｏｄｅｌｉｍｐｌｉｅｄｒｈａ）ｗｈ（１Ｉｌｔｈｅｌ￡、ｉｓａｎａｃｃｉｄｅｎｔ．ｔｈｅｎｅａｒｅｓｔｅｌｎｅｒｇｅｎｃｙｓｅｒｖｉｃｅｓｐｏｔａｌｗａｙｓｄｅａｌｓｗｉｔｈｉｔ．ｎＩｌ（１ｈｅｄｉｄｎｏｔｃｏｎｓｉｄｅｒｓｕｃｈｐｒｏｂｌｅｍｔｈａｔｔｈｅｕｅａｒｅｓｔｅｍｅｒｇｅｎｃｙｓｅｒｖｉｃｅｓｐｏｔｈａｄＩＩＯｅｎｏｕｇｈｃａｐａｂｉｌｉｔｙｔｏｄｅａｌｗｉｔｈｉｔａｌｏｎｅ．ＬｉｕＣｈｕｎｌｉｎｓｔｕｄｉｅｄｔｈｅｐｒｏｂｌｅｍｔｈａｔｏｎｅｅｍｅｒｇｅｎｃｙｓｅｒｖｉｃｅｓｐｏｔｈａｄｎｏｅｎｏｕｇｈｃａｐａｂｉｌｉｔｙ，ａｎｄｍｏｒｅｅｌｎｅｔ’ｇｅｎｃｙｓｅｔ’’ｖｉｃｅｓｐｏｔｉｓｎｅｅｄｅｄｔｏｄｅａｌｗｉｔｈｔｈｅａｃｃｉｄｅｎｔｃｏｏｐｅｒａｔｉｖｅｌｙ［１２，１３］．Ｔｈｅｙｓｔｕｄｉｅｄｓｈｏｒｔｅｓｔｐａｔｈｐｒｏｂｌｅｍｗｉｔｈｆｕｚｚｙｅｄｇｅｌｅｎｇｔｈ［１４，１５］，ｍｉｄｈ州ｔｏｏｈ（１０ｓｅｅｍｅｔ＿
ｌｅａｓｔ．ｇｅｎｃｙｓｅｒｖｉｃｅｓｐｏｔｓｔｏｄｅａｌｗｉｔｈｔｈｅａｃｃｉｄｅｎｔｃｏｏｐｅｒａｔｉｖｅｌｙｉｎｏｒｄｅｒｔＯｃｏｓｔ
ＢｕｔｔｈｅｙｄｉｄｎｏｔｃｏｎｓｉｄｅｒｔｈｅｃａｓｅｔｈａｔｔｈｅｒｅｗｅｒｅｍａｎｙａｃｃｉｄｅｎｔｓｉｎｔｈｅＳａｌｌｌｅｔｉｍｅ
Ｉｎ２００１，ＬｉＺｈｅｎｐｉｎｇ［１７】ｓｔｕｄｉｅｄｔｈｅＭｉｎｉｍｕｍＴｉｍｅ－ＳｐａｎＴｒａｎｓｐｏｒｔａｔｉｏｎＰｒｏｂｌｅｍ．Ｓｈｅｐｒｏｐｏｓｅｄｍｕｌｔｉ—ｓｕｐｐｌｙｍｕｌｔｉ—ｄｅｍａｎｄｅｍｅｒｇｅｎｃｙｔｒａｎｓｐｏｒｔａｔｉｏｌ：ｐｒｏｂｌｅｍ，ａｎｄｇａｖｅａｐｏｌｙｎｏｍｉａｌｔｉｍｅａｌｇｏｒｉｔｈｍ．ＢｕｔｓｈｅｄｉｄｎｏｔｃｏｎｓｉｄｅｒｔｈｅＣＯＳｔｗｈｉｌｅｔｒｙｉｎｇｔｏｔｒａｎｓｐｏｒｔｔｈｅｍａｔｅｒｉａｌｒａｐｉｄｌｙ．ＢｕｔｉｎｔｈｅＣａｓＰｏｆｃａｐｉｔａｌｓｈｏｒｔａｇｅ，ｗｅｃａｎｎｏｔｓｐｅｎｄｔｏｏｍｕｃｈｗｈｅｎｔｈｅｒｅｉｓａｎａｃｃｉｄｅｎｔ．Ｓｏ‘｝，ｆ。ｐｒｏｐｏｓｅｄｔｈｅＭｉｎｉｍｕｍＴｉｍｅ—ＳｐａｎＴｒａｎｓｐｏｒｔａｔｉｏｎＰｒｏｂｌｅｍｗｉｔｈＣｏｓｔＣｏｎｓｔｒａｉｎｔＳｅｃｔｉｏｎ２ｇａｖｅｔｈｅＭｉｎｉｍｕｍＴｉｍｅ－ＳｐａｎＴｒａｎｓｐｏｒｔａｔｉｏｎＰｒｏｂｌｅｍｗｉｔｈＣｏｓｔＣｏｎｓｔｒａｉｎｔ（ａｂｂｒｅｖｉａｔｅｄｔｏｐｒｏｂｌｅｍＩ１：Ｉｎａｂｉｐａｒｔｉｔｅｎｅｔｗｏｒｋ．Ｏｌｌｅｓｉ（ｈ、（）ｆｎｏｄｅｓｄｅｎｏｔｅｓｕｐｐｌｙｓｐｏｔｓＳ．ａｎｄｔｈｅｏｔｈｅｒｓｉｄｅｄｅｎｏｔｅｓｄｅｍａｎｄｓｐｏｔｓ丁ｅａｃｈａｒｃ（ｉ，Ｊ）ｈａｓｔｒａｎｓｐｏｒｔａｔｉｏｎｃｏｓｔ甜１』ａｎｄｔｒａｎｓｐｏｒｔａｔｉｏｎｔｉｍｅｔｏＷｈｅｎｔｈｅｒｅｉｓｇｌｌａｃｃｉｄｅｎｔ，ｈｏｗｔｏｔｒａｎｓｐｏｒｔｔｈｅｍａｔｅｒｉａｌｓｆｒｏｍＳｔｏＴＳＯｔｈａｔｔｏｔａｌｔｒａｎｓｐｏｒｔａｔｉｏｎ
Ｗａｎｄｌｏｎｇｅｓｔｔｒａｎｓｐｏｒｔａｔｉｏｎｔｉｍｅｉｓｍｉｎｉｍｉｚｅｄ’
ＣＯＳｔｉｓｎｏｍｏｒｅｔｈａｎ
Ｓｅｃｔｉｏｎ３ｔｒａｎｓｆｏｒｍｅｄｐｒｏｂｌｅｍＩｔｏｔｒａｄｉｔｉｏｎａｌｔｒａｎｓｐｏｒｔａｔｉｏｎｌｉｔｌｌｂｌｅｍ（ａｂ－
ｂｒｅｖｉａｔｅｄｔｏｐｒｏｂｌｅｍＩＩ），ａｎｄｄｉｓｃｕｓｓｅｄｔｈｅｒｅｌａｔｉｏｎｂｅｔｗｅｅｎｔｈｅｓ（）ＩｎｔｉｏｎｓｏｆｐｒｏｂｌｅｍＩａｎｄｐｒｏｂｌｅｍⅡ．Ｔｈｅｍａｉｎｒｅｓｕｌｔｉｓ：
Ｔｈｅｏｒｅｍ３．３．２ＴｈｅｒｅｍｕｓｔｂｅａｔｌｅａｓｔｏｎｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｐｒｏｂｌｅｍＩｉｎｉｔｓｂａｓｉｃｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎｓｅｔ．ａｎｄｔｈｅｒｅｍｕｓｔｂｅｏｎｅａｎｄａｔｌｅａｓｔ（）ｌｉｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｐｒｏｂｌｅｍＩｉｎｔｈｅｂａｓｉｃｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎｓｅｔｏｆｐｒｏｂｌｅｍⅡＰｒｏｂｌｅｍＩ’ＳｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｃａｎｂｅｆｏｕｎｄｉｎｔｈｅｂａｓｉｃｆｅａｓｉｂｈｌｓｏｌｕｔｉｏｎｓｅｔｏｆｐｒｏｂｌｅｍＩＩ，ＳＯｗｅｃａｌｌｎｓｅｔｈｅｔａｂｌｅｍｅｔｈｏｄｏｆｔｒａｄｉｔｉｏｎａｌｔｔ＇ｉ－１１ｌｑｍｒｔａｔｉｏｎｐｒｏｂｌｅｍｆｏｒｒｅｆｅｒｅ：ｉｃｅ．ａｉｄｌｏｏｋｆｏｒｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｐｒｏｂｌｅｍＩｊ；ｊｔｈｅｂａｓｉｃ
山∞：大学博ｊ二学懂论文
ｆｌ，ａｓｉｂｌｅｓｏｌｕｔｉｏｎｓ【１ｔｏｆｐｌｏｂｌｅｍⅡ．ＢｔｔｔｆｈＰｂａｓｉ（ｉ㈨ｓｉｂＬｅｓｏｈｔｔｉＯＬｌ０ｆｐｒｏｂｔｔ’ｔｉｔＩＩｉｓ１１０１，＂ａｌｗａ３。ｓａｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎｏｔＩｍ，ｂｈ、ｌＩｌＩ，ｎ¨ｗｗｅｔｔａｌｉ：ｑ％ｒ１１］ｐｒｏｂｌｅｍＩＩｔｏａｓｐｅｃｉａｌｔｒａｎｓｐｏｒｔａｔｉｏｎ１）ｒｏｂｌｅｎｌｕｈｏｓｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｎＲｔｓｔｂｅａｂａｓｉｃ：ｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎｏｆｐｒｏｂｌｅｍＩ．
Ｌｅｔｘ１ｉｓａｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎｏｆｐｒｏｂｈⅢ１Ⅱ，ｆｏｒｐⅥｒｖｅｄｇｅｔｈａｔｔｉＪ２ｔ（Ｘ１）．ｔｈｅｎｍｏｄｉ５．ｉｔｓｃｏｓｔ咄Ｔ＝Ｍ．ｈｅｒｅＭｉｓｒ１ｅｎｏｕｇｈｌａｒｇｅｐｏｓｉｔｉｖｅｎｎｎｌｂｅｒ．Ｔｈｅｎｗｅｇｅｔａｕｅｗｔｒａｎｓｐｏｒｔａｔｉｏｎｐｒｏｂｌｅｍ［ＩＩ【ａｂｂｒｅｖｉａｔｅｄｔｏｐｒｏｂｌｅｍＩｎ）．ＢｅｃａｕｓｅｐｒｏｂｌｅｍＩａｎｄｐｒｏｂｌｅｍＩｌｌｈａｖｅｔｈｅＳａｌｔＬｔ、（＇ｔｒｅｓｔｒａｉｎｔｃｏｎｄｉｔｉｏｎｓ．ｔｈｅｙｈａｖｅｓａ．１ｎｅｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎｓｅｔ．Ａｎｄｗｅｈａｖｅ：
Ｔｈｅｏｒｅｍ３．３．３ＩｆＸｉｓｔｈｅｏｐｔｉｍａｌｓ（）ｈｔｔｉｏｎｏｆｐｒｏｂｌｅｍＩ．ｔｈｅｏｐｔｉｍａｌｓｏｌｎ—ｔｉｏｎｏｆｐｒｏｂｌｅｍＩｌｌｃｏｎｓｔｒｕｅｃｅｄｆｒｏＩｎｘ。ｉｓｘ２．ａｌｌｄ钍｝’（ｘ２）＝∑∑拼；ｚ；＜Ｉ∥．
１＝１Ｊ＝１
ｔｈｅｎｔ（ｘ１）＞ｔ（ｘ）．
Ｓｅｃｔｉｏｎ４ｇａｖｅＭｏｄｉｆｉｅｄＴａｂｌｅＡｌｇｏｒｉｔｈｍｂｙｔｈｅｏｒｅｍ３．３．３：ＷｉｔｈＴａｂｌｅＡｌｇｏ—ｒｉｔｈｍｏｆＴｒａｎｓｐｏｒｔａｔｉｏｎＰｒｏｂｌｅｍ．ｖｃｅｌｏｏｋｆｏｒｔｈｅｎｆｉｎｉｍｍｎＣＯＳｔｔｒａｎｓｐｏｒｔａｔｉｏｎｓｃｈｅｍｅＸ．ａｎｄｉｔｓｔｒａｎｓｐｏｒｔａｔｉｏｎｔｉｍｅｉｓｄｘ），Ｆｏｒｅａｃｈｅｄｇｅｗｈｏｓｅｔｒａｎｓｐｏｒｔａ－ｔｉｏｎｔｉｍｅｉｓｎｏｌｅａｓｅｔｉｔａｎｔ（Ｘ），ｗｅｍｏｄｉｂ。ｉｔｓｔｒａｎｓｐｏｒｔａｔｉｏｎｃｏｓｔｔｏ。。．ＷｉｔｈＴａｂｌｅＡｌｇｏｒｉｔｈｍ．ｗｅｌｏｏｋｆｏｒｔｈｅｍｉｎｉｎｌｕｌｌ｜ＣＯＳｔｔｒａｎｓｐｏｒｔａｔｉｏｎｓｃｈｅｍｅＸ’ａｇａｉｎ．ｉｆｔｒａｎｓｐｏｒｔａｔｉｏｎｃｏｓｔｏｆＸ’ｉｓｍｏｒｅｔｈａｎｌＩ‘．ｔｈｅｎＸｉｓｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ．Ｓｅｃｔｉｏｎ５ｇａｖｅａｎｅｘａｍｐｌｅ．ｔｈｅｎｗｅｆｏｕｎｄｉｔｓｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｂｙＭｏｄｉｆｉｅｄＴｈｂｌｅＡｌｇｏｒｉｔｈｍ．Ｉｔｓｈｏｗｅｄｔｈａｔｔｈｅａｌｇｏｔｉｔｈｍｆｌｉｒｔｓｅａｓｉｌｙａｎｄｒａｐｉｄｌｙ．Ｃｈａｐｔｅｒ４ｓｔｕｄｉｅｄｔｈｅＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍｏｎＣｏｎｔｉｎｕｏｕｓＮｅｔｗｏｒｋ．Ａｔｆｉｒｓｔ，ｓｅｃｔｉｏｎｌｉｎｔｒｏｄｕｃｅｄｔｈｅｈｉｓｔｏｒ３’ｏｆＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍＯＵＣｏｎｔｉｎｕｏｕｓＮｅｔｗｏｒｋ．Ｉｎ１９５７。ＦｏｒｄａｎｄＦｔｔｌｋｅｒｓｏｎｆｉｒｓｔｌｙｐｒｏｐｏｓｅｄｔｈｅＭａｘ－ＦｌｏｗＰｒｏｂｌｅｍ［１８，１９１．Ｉｎ１９６１，ＦｕｌｋｅｒｓｏｎｓｔｕｄｉｅｄｔｈｅＭｉｎ－ｃｏｓｔＦｌｏｗＰｒｏｂｌｅｍａｌｏｎｅＦｒｏｍｔｈｅｎｏｎ．ＮｅｔｗｏｒｋＦｌｏｗＰｒｏｂｌｅｍｌｔａｓｔｗｏｂｒａｎｃｈｅｓ：ｔｈｅＭａｘ－ＦｌｏｗａｌｌｄＭｉｎ—ＣｏｓｔＰｒｏｂｌｅｎｌ．
ＩｎＦｏｒｄａｎｄＦｕｌｋｅｒｓｏｎ’Ｓｎｅｔｗｏｒｋｆｌｏｗｍｏｄｅｌ，ｅｄｇｅ’Ｓｃａｐａｃｉｔｙｉｓｃｏｎｓｔａｎｔ，ｆｉｏｗｃａｂｎｏｔｓｔａｙｉｎｍｅｄｉａｔｅｎｏｄｅｓ．ａｎｄｆｌｏｗｇｕｔｔｈｒｏｕｇｈａｌｌｅｄｇｅｉｎｓｔａｎｔａｎｅｏｕｓｌＫｗｅｃａｌｌｔｈｉｓｐｒｏｂｌｅｍｔｈｅｓｔａｔｉｃｎｅｔｗｏｒｋａｏｕｌｐｒｏｂｌｅｍ．Ｉｎ１９５８．ＦｏｒｄａｎｄＦｎｌｋｅｒ—ｓｏｎｆｉｒｓｔｌｙｐｒｏｐｏｓｅｄｄｙｎａｍｉｃｎｅｔｗｏｒｋ８ｔ｝、、ｐｒｏｂｌｅｍＩｎｔｈｉｓｍｏｄｅｌ．ｆｌｏｗｎｅｅｄｓｓｏｍｅｔｉｍｅｔｏｇｅｔｔｈｒｏｕｇｈｏｎｅｅｄＫｅ．Ｉｎ１１）７９．ＨａｌｐｅｎｓｔｕｄｉｅｄｔｂｅｆｌｏｗｐＪｏｂ—
山东大学博士学位论文
Ｉｅｍｉｎｗｈｉｃｈｅｄｇｅｓ’ｃａｐａｃｉｔｙｗａｓｖａｒｉａｂｌｅａｎｄｆｌｏｗｎｅｅｄｅｄｔｉｍｅｔｏ
ｇｅｔｔｈｒｏｕｇｈｅｄｇｅｓ［２２］．Ｉｎ１９８１，Ａｎｄｅｒｓｏｎ．Ｅ．Ｊｅｔｃ．ｐｒｏｐｏｓｅｄｍａｘ－ｆｌｏｗｐｒｏｂｌｅｍｏｎｃｏｎｔｉｎｕｏｕｓｔｉｍｅｎｅｔｗｏｒｋ［２３］．Ｉｎｔｈａｔｐｒｏｂｌｅｍ，ｅｄｇｅｓ’ｃａｐａｃｉｔｙｉｓｆｕｎｃｔｉｏｎｏｆｔｉｍｅ，ａｎｄｆｌｏｗｃａｎｓｔａｙｉｎｍｅｄｉａｔｅｎｏｄｅｓｓｏｍｅｔｉｍｅｓ，ａｎｄｔｈｅｍｅｄｉａｔｅｎｏｄｅｓ’ｓｔｏｒａｇｅｉｓｆｕｎｃｔｉｏｎｏｆｔｉｍｅ，ｗｅｃａｌｌｔｈｉｓｐｒｏｂｌｅｍＣｏｎｔｉｎｕｏｕｓＮｅｔｗｏｒｋＦｌｏｗＰｒｏｂｌｅｍ，Ａｎｄｔｈｅｙａｌｌｓｔｕｄｉｅｄｍａｘ－ｆｌｏｗｉｎａｌｌｋｉｎｄｓｏｆｎｅｔｗｏｒｋ．Ｃｈａｐｔｅｒ４ｉｎｔｈｉｓｄｉｓｓｅｒｔａｔｉｏｎｗｉｌｌｓｔｕｄｙｔｈｅＭｉｎ—ＣｏｓｔｆｌｏｗＰｒｏｂｌｅｍｏｎＣｏｎｔｉｎｕｏｕｓＮｅｔｗｏｒｋｗｈｏｓｅｅｄｇｅｓ’ｃａｐａｃｉｔｉｅｓａｒｅｖａｒｉａｂｌｅｓ，ａｎｄｆｌｏｗｃａｎｓｔａｙｉｎｍｅｄｉａｔｅｎｏｄｅｓ，ａｎｄｔｈｅｉｒｓｔｏｒａｇｅｓａｒｅｖａｒｉａｂｌｅｓ．Ｓｅｃｔｉｏｎ２ｇａｖｅｔｈｅｍｏｄｅｌｏｆｔｈｅＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍｏｎＣｏｎｔｉｎｕｏｕｓＮｅｔｗｏｒｋ：ＧｉｖｅｎｎｅｔｗｏｒｋＮ（ｔ）＝（ＫＡ，ｏ（ｔ），６（≠），叫（ｔ））．Ａｔａｎｙｔｉｍｅｔ∈［０，Ｔｌ，ａｎｄｔｈｅｕｎｉｔｃｏｓｔｏｆｅｄｇｅ（ｉ，Ｊ）ｉｓ＂玎（￡），ａｎｄｔｈｅｃａｐａｃｉｔｙｏｆｅｄｇｅ（ｉ，Ｊ）ｉｓ％（｛）．ＴｈｅｓｔｏｒａｇｅｏｆｎｏｄｅＪｉｓ片∑‰（ｔ）一ｆＪｋ（ｔ）］ｄｔｓａ／ｔ）．Ｈｏｗｔｏａｒｒａｎｇｅｆｌｏｗ向（ｔ）ＳＯｔｈａｔｉｎｆｏ，ＴＪｔｈｅｆｌｏｗｖａｌｕｅｆｒｏｍｓｔｏｔ譬∑疗。（ｔ）ｄｔ＝ＶＯ，ａｎｄｆｌｏｗ
（Ｊ．ｎ）ＥＡ
ｃｏｓｔＷ＝口∑Ａ３（ｔ）ｗ玎（ｔ）ｄｔｉｓｍｉｎｉｍｉｚｅｄ？
（ｉｄ）ｅＡ
Ｓｅｃｔｉｏｎ３ｄｅｆｉｎｅｄＲｅａｃｈａｂｌｅＮｏｄｅＳｅｔａｎｄｉｔｓＲｅａｃｈｉｎｇＣｏｓｔ（ｓｅｅｐａｇｅ２４）ｗｉｔｈａｇｒｏｕｐｏｆｒｅｃｕｒｓｉｏｎｒｕｌｅｓ．Ｓｅｃｔｉｏｎ４ｐｒｏｖｅｄｔｈｅＥｘｉｓｔｅｎｃｅＴｈｅｏｒｅｍａｎｄＯｐｔｉｍｉｚａｔｉｏｎＴｈｅｏｒｅｍｏｆＡｕｇｍｅｎｔＦｌｏｗ．
Ｔｈｅｏｒｅｍ４．４．１（ＥｘｉｓｔｅｎｃｅＴｈｅｏｒｅｍｏｆＡｕｇｍｅｎｔＦｌｏｗ）ＩｎｎｅｔｗｏｒｋⅣ（ｔ），ｆｏｒｆｌｏｗ，（￡），ｉｆｎｏｄｅｎｉｓａｌｗａｙｓｒｅａｃｈａｂｌｅｉｎｆｔ’，以ｔｈｅｎｗｅｃａｎｇｅｔａｎｅｗｆｅａｓｉｂｌｅｆｌｏｗ，≮）ｗｈｉｃｈｓａｔｉｓｆｉｅｓｔｈａｔｖ（／７（ｔ））＞口（，（｝））．
Ｔｈｅｏｒｅｍ４．４．３（ＯｐｔｉｍｉｚａｔｉｏｎＴｈｅｏｒｅｍｏｆＡｕｇｍｅｎｔＦｌｏｗ）Ｉｆｆｌｏｗｆ（ｔ）ｉｓａｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗ，ａｎｄｗｅａｕｇｍｅｎｔｔｈｅｆｌｏｗｆ（ｔ）ａｌｏｎｇｔｈｅｃｈａｉｎＲｃｏｎｓｔｒｕｃｔｅｄｂｙｔｈｅｍｅｔｈｏｄｉｎｔｈｅｏｒｅｍ４．４．１，ｔｈｅｎｗｅｇｅｔａｎｅｗｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗ，沁）．Ｉｎｓｅｃｔｉｏｎ５，ｂｙｔｈｅＯｐｔｉｍｉｚａｔｉｏｎＴｈｅｏｒｅｍｏｆＡｕｇｍｅｎｔＦｌｏｗｗｅｇａｖｅｔｈｅＡｕｇｍｅｎｔＦｌｏｗＡｌｇｏｒｉｔｈｍＯｎｃｏｎｔｉｎｕｏｕｓｎｅｔｗｏｒｋＮ（ｔ）＝（ＵＡ，ｏ（￡），６（ｔ），枷（ｔ））ｔｏｏｂｒａｉｎｔｈｅｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗｗｉｔｈｆｌｏｗｖａｌｕｅ口。地：Ｆｉｒｓｔ，ｌｏｏｋｆｏｒｒｅａｃｈａｂｌｅｎｏｄｅｓｅｔｏｆａｚｅｒｏｆｌｏｗ；ｔｈｅｎｓｅａｒｃｈｆｏｒｔｈｅｍｉｎｉｍｕｍｃｏｓｔａｕｇｅｍｎｔｃｈａｉｎＲｂｙｔｈｅｃｏｎｓｔｒｕｃｔｉｏｎｏｆｒｅａｃｈａｂｌｅｎｏｄｅｓｅｔ；ａｕｇｍｅｎｔｆｌｏｗａｌｏｎｇｃｈａｉｎＲ：ｔｈｅｎｒｅｐｅａｔｔｈｅａｂｏｖｅｐｒｏｃｅｄｕｒｅｔｉｌｌｆｌｏｗｖａｌｕｅ口＝咖．
Ｃｈａｐｔｅｒ５ｓｔｕｄｉｅｄｔｈｅＵｎｃａｐａｃｔａｔｅｄＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍ．Ｓｅｃｔｉｏｎｌ
山东大学博士学位论文
ｉｎｔｒｏｄｕｃｅｄｔｈｅｈｉｓｔｏｒｙｏｆｔｈｅＵｎｃａｐａｃｔａｔｅｄＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍｗｉｔｈＦｉｘｅｄＣｏｓｔ．ＦｕｌｋｅｒｓｏｎｐｒｏｐｏｓｅｄｔｈｅＭｉｎ—ＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍ，ｂｕｔｈｅｃｏｎｓｉｄｅｒｅｄｏｎｌｙｖａｒｉａｂｌｅｃｏｓｔ，ｄｉｄｎｏｔｃｏｎｓｉｄｅｒｆｉｘｅｄＣＯＳｔ．Ｉｎ１９９７，ＴｒｉｌｏｃｈａｎＳａｓｔｒｙｓｔｕｄｉｅｄｆｉｘｅｄｃｏｓｔｔｗｏ—ｃｏｍｍｏｄｉｔｙｍｉｎ—ｃｏｓｔｆｌｏｗｐｒｏｂｌｅｍ．Ｉｎｈｉｓｍｏｄｅｌ，ｔｈｅｒｅｗａｓｎｏｅｄｇｅｃａｐａｃｉｔｙｃｏｎｓｔｒａｉｎｔａｎｄｖａｒｉａｂｌｅｃｏｓｔ．Ｉｎｍａｎｙｃａｓｅｓ，ｗｅｎｅｅｄｐａｙｎｏｔｏｎｌｙｆｉｘｅｄｃｏｓｔ，ｂｕｔａｌｓｏｖａｒｉａｂｌｅｃｏｓｔ．Ｂｕｔｗｈｉｌｅｔｒａｎｓｐｏｒｔａｔｉｏｎｑｕａｎｔｉｔｙｉｓｆａｒｓｍａｌｌｅｒｔｈａｎａｌｌｅｄｇｅｓ’ｃａｐａｃｉｔｙ，ｗｅｃａｎｔｈｉｎｋｔｈａｔｔｈｅｒｅｉｓｎｏｅｄｇｅｃａｐａｃｉｔｙｃｏｎｓｔｒａｉｎｔ．ＳｏｗｅｓｔｕｄｉｅｄＵｎｃａｐａｃｉｔａｔｅｄＯｎｅ－ＣｏｍｍｏｄｉｔｙａｎｄＴｗｏ—ＣｏｍｍｏｄｉｔｙＭｉｎｉｍｕｍＣｏｓｔ．ＦｌｏｗＰｒｏｂｌｅｍｓｗｉｔｈＦｉｘｅｄａｎｄＶａｒｉａｂｌｅＣｏｓｔ．
Ｓｅｃｔｉｏｎ２ｓｔｕｄｉｅｄＵｎｃａｐａｃｉｔａｔｅｄＯｎｅ—ＣｏｍｍｏｄｉｔｙＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂ－ｌｅｍ．ＧｉｖｅｎａｎｕｎｄｉｒｅｃｔｅｄｇｒａｐｈＧ＝（ＫＥ），ｗｈｅｒｅ１７ｄｅｎｏｔｅｓｖｅｒｔｅｘｓｅｔ，ａｎｄＥｉｓｅｄｇｅｓｅｔ．Ｎｏｄｅ８ａｎｄｎｏｄｅｔａｒｅｓｏｕｒｃｅｎｏｄｅａｎｄｓｉｎｋｎｏｄｅｒｅｓｐｅｃｔｉｘ’ｅｌｙＦ０ｒ
ｅｖｅｒｙｅｄｇｅ（／，Ｊ），ｔｈｅｒｅａｒｅａｆｉｘｅｄｃｏｓｔＷｉｊａｎｄａｖａｒｉａｂｌｅｃｏｓｔｃｏ．Ｗｈｅｎｍｕｎｉｔｍａｔｅｒｉａｌｆｌｏｗｔｈｒｏｕｇｈｅｄｇｅ（ｉ，Ｊ）∈Ｅ，ｗｅｎｅｅｄｐａｙ叫｛ｊ＋ｍｃｉｊ．ＯｕｒｏｂｊｅｃｔｉｓｔｏｌｏｏｋｆｏｒａｆｅａｓｉｂｌｅｆｌｏｗｆｒｏｍｓｔｏｔｗｈｏｓｅｖａｌｕｅｉｓＶａｎｄｃｏｓｔｉｓｍｉｎｉｍｕｍ？ＳｕｃｈａｐｒｏｂｌｅｍｉｓｃａｌｌｅｄＵｎｃａｐａｃｉｔａｔｅｄＯｎｅ—ＣｏｍｍｏｄｉｔｙＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍ．ＴｈｅｎｗｅｄｅｆｉｎｅｄＦｌｏｗＧｒａｐｈ，ＦｌｏｗＰａｔｈａｎｄＦｌｏｗＰａｔｈ’Ｓ＼，ａｌｕｅ，ａｎｄｗｅｈａｄｔｈｅｆｏｌｌｏｗｉｎｇｔｈｅｏｒｅｍ：
Ｔｈｅｏｒｅｍ５．２．４Ｕｎｃａｐａｃｉｔａｔｅｄｏｌｌｅ—ｃｏｍｍｏｄｉｔｙｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗｐｒｏｂｌｅｍ
ｈａｓａｎｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｔｈａｔｈａｓｏｎｌｙｏｎｅｆｌｏｗｐａｔｈ．
Ｂｙｔｈｅｏｒｅｍ５．２．４，ｗｅｏｂｔａｉｎｅｄａｌｇｏｒｉｔｈｍ５．１：Ｌｅｔｅｄｇｅｌｅｎｇｔｈｂｅ”；＝ｗｕ＋ｃｉｊｙ，ｗｉｔｈＤｉｊｋｓｔｒａａｌｇｏｒｉｔｈｍｗｅｌｏｏｋｆｏｒｓｈｏｒｔｅｓｔｐａｔｈＰｆｒｏｍ８ｔｏｔ，ｔｈｅｎｔｈｅｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗａｌｏｎｇｔｈｅｐａｔｈ．Ｆｉｎａｌｌｙｗｅｐｒｏｖｅｄｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍ’ＳｃｏｍｐｌｅｘｉＤ７ｉｓ０协２）．
Ｓｅｃｔｉｏｎ３ｓｔｕｄｉｅｄＵｎｃａｐａｃｉｔａｔｅｄＴｗｏ—ＣｏｍｍｏｄｉｔｙＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂ—ｌｅｍ．ＩｎｕｎｄｉｒｅｃｔｅｄｇｒａｐｈＧ＝（ＫＥ），ｎｏｄｅ８１ａｎｄｎｏｄｅｔｌａｒｅｓｏｕｒｃｅｎｏｄｅａｎｄｓｉｎｋｎｏｄｅｏｆｃｏｍｍｏｄｉｔｙＩｒｅｓｐｅｃｔｉｖｅｌｙ，ａｎｄｎｏｄｅ８２ａｎｄｎｏｄｅｔ２ａｒｅｓｏｕｒｃｅｎｏｄｅａｎｄｓｉｎｋｎｏｄｅｏｆｃｏｍｍｏｄｉｔｙⅡｒｅｓｐｅｃｔｉｖｅｌｙ．Ｆｏｒｅａｃｈｅｄｇｅ（ｉ，Ｊ）∈Ｅ，ｔｈｅｒｅｉｓｆｉｘｅｄｃｏｓｔｗｏ，ａｎｄｔｈｅｒｅａｒｅｔｗｏｖａｒｉａｂｌｅｃｏｓｔｃｉｂａｎｄ弓ｆｏｒｃｏｍｍｏｄｉｔｙＩｏｎｅ
ａｎｄｃｏｍｍｏｄｉｔｙＩＩｒｅｓｐｅｃｔｉｖｅｌｙ．Ｉｆｔｈｅｒｅｉｓｆｌｏｗｏｎｅｄｇｅ（ｉ，Ｊ）∈Ｅ，ｗｅｎｅｅｄｐａｙｆｉｘｅｄｃｏｓｔ叫廿ｉｎｓｐｉｔｅｏｆｃｏｍｍｏｄｉｔｙＩｏｒⅡ．ＡｎｄＯｕｒｇｏａｌｉｓｔｏｌｏｏｋｆｏｒａｆｌｏｗｚ＝｛ｚｂ，ｚ０）ｗｈｏｓｅｔｏｔａｌｃｏｓｔｉｓｍｉｎｉｍｕｍ，ａｎｄｔｈｅｆｌｏｗｖａｌｕｅｆｒｏｍ８１ｔｏｔ】ｉｓｕ，
山东大学博士学位论文
ａｎｄｔｈｅｆｌＯＷｖａｌｕｅｆｒｏｍ
ｔｏｔ２ｉｓＫ．ＳｕｃｈａｐｒｏｂｌｅｍｉｓｃａｌｌｅｄＵｎｃａｐａｃｉｔａｔｅｄ
Ｓ２
Ｔｗｏ—ＣｏｍｍｏｄｉｔｙＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍ．ＴｈｅｎｗｅｄｅｆｉｎｅｄＳｈａｒｅｄＰａｔｈ．ＦｏｒｗａｒｄＳｈａｒｅｄＰａｔｈａｎｄＢａｃｋｗａｒｄＳｈａｒｅｄＰａｔｈ．Ａｎｄｗｅｐｒｏｖｅｄ：Ｔｈｅｏｒｅｍ５．３．２ＩｎＷｅｉｇｈｔＧｒａｐｈＷ（Ｇ）＝（ＶＥ’），ｔｈｅｒｅｍｕｓｔｅｘｉｓｔｏｎｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｗｉｔｈｏｎｌｙｏｎｅｓｈａｒｅｄｐａｔｈｏｎｕｎｃａｐａｃｉｔａｔｅｄｔｗｏ—ｃｏｍｍｏｄｉｔｙｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗｐｒｏｂｌｅｍ．
Ｆｉｎａｌｌｙｗｅｃｏｎｓｔｒｕｃｔｅｄａｌｇｏｒｉｔｈｍ５．２ｂｙｔｈｅｏｒｅｍ５．３．２（ｓｅｅｐａｇｅ３６），ａｎｄｗｅｐｒｏｖｅｄｔｈａｔｉｔｓｃｏｍｐｌｅｘｉｔｙｉｓＯ（ｎ３）．Ｉｎｓｅｃｔｉｏｎ４ｗｅｄｅｍｏｓｔｒａｔｅｄｔｈｅａｌｇｏｒｉｔｈｍ’Ｓｂａｓｉｃｉｄｅａｗｉｔｈａｎｅｘａｍｐｌｅ．
Ｃｈａｐｔｅｒ６ｓｔｕｄｉｅｄＣａｐａｃｉｔａｔｅｄＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍ．Ａｆｔｅｒｗｅｃｏｎ—ｓｉｄｅｒｅｄＵｎｃａｐａｃｉｔａｔｅｄＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍｉｎｃｈａｐｔｅｒ５．ｗｅｆｏｕｎｄｔｈａｔｔｒａｎｓｐｏｒｔａｔｉｏｎｌｏａｄｗａｓｌａｒｇｅｒｔｈａｎｓｏｍｅｅｄｇｅｃａｐａｃｉｔｙｉｎｍａｎｙｃ＆ｓｅｓ．ＳｏｗｅｓｔｕｄｉｅｄＣａｐａｃｉｔａｔｅｄＭｉｎｉｍｕｍＣｏｓｔＦｌｍｖＰｒｏｂｌｅｍｗｉｔｈＦｉｘｅｄａｎｄＶａｒｉａｂｌｅＣｏｓｔ．Ｓｅｃｔｉｏｎ２ｆｉｒｓｔｌｙｇａｖｅｔｈｅｍｏｄｅｌｏｆＣａｐａｃｉｔａｔｅｄＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂ－ｌｅｍｗｉｔｈＦｉｘｅｄＣｏｓｔ．Ｔｈｅｄｉｆｆｅｒｅｎｃｅｂｅｔｗｅｅｎｔｈｉｓｐｒｏｂｌｅｍａｎｄｔｈｅｐｒｏｂｌｅｍｉｎｃｈａｐｔｅｒ５ｉｓｔｈａｔｅｄｇｅ（ｉ，Ｊ）ｈａｓｕｐｐｅｒｃａｐａｃｉｔｙ，ｂｏｕｎｄｂｏ．
ＳｕｐｐｏｓｅｔｈａｔＸｉｓｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ（ｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗ）ｏｆｍｉｎｉｍｕｍＣＯＳｔｆｌｍｖｐｒｏｂｌｅｍｗｉｔｈｆｉｘｅｄｃｏｓｔ，Ｅ’ｉｓｔｈｅｅｄｇｅｓｅｔｔｈｒｏｕｇｈｗｈｉｃｈＸｆｌｏｗｓ．ＴｈｅｆｏｌｌｏｗｉｎｇｔｈｅｏｒｅｍｇｉｖｅｓａｐｒｏｐｅｒｔｙｏｆｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎＸ：
Ｔｈｅｏｒｅｍ６．２．１ＩｆＧ’＝Ｇ（ＫＥ’）ｉｓｏｎｅｓｕｂ?ｎｅｔｗｏｒｋｏｆＧｃｏｎｓｔｒｕｃｔｅｄｂｙＥ７．ｔｈｅｎｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎＸｍｕｓｔｂｅａｍｉｎｉｍｕｍＣＯＳｔｆｌｏｗｃｏｒｒｅｓｐｏｎｄｉｎｇｔｏｖａｒｉａｂｌｅｃｏｓｔｑｏｎＧ’＝Ｇ（ＫＥ’）．
Ｓｏｒｔａｌｌｐａｔｈｓｆｒｏｍ８ｔｏｔｉｎＧ＝（ＫＥ’）ｂｙ＇ｔｈｅｉｒｖａｒｉａｂｌｅｃｏｓｔａｓＰｌ，Ｐ２，…，ｍ１ＳｕｐｐｏｓｅｔｈａｔａｌｌｐａｔｈｓｗｈｏｓｅｖａｒｉａｂｌｅｃｏｓｔｉｓｌｅａｓｅｔｈａｎＰｋｌｉｎＧ＝（ＦＥ）ｆｒｏｍ８ｔｏｔ＆ｒｅ“，以，…，矾２．ＳｕｐｐｏｓｅｔｈａｔｉｆｅｄｇｅｓｉｎＣ＝｛ｅｌ，ｅ２，…，ｅｋ３）ａｒｅａｌｌｄｅｌｅｔｅｄ，ｔｈｅｎｐｌ，区，…，ｐ：２ａｌｌｂｒｅａｋｄｏｗｎ，ａｎｄＣｎＥ’＝≯，ａｎｄｎｏｏｔｈｅｒｅｄｇｅｓｅｔＣ’≥Ｃｓａｔｉｓｆｉｅｓａｌｌｔｈｅａｂｏｖｅ．ＴｈｅｎＥ’ｃＥ＼Ｃ，ａｎｄｗｅｄｅｎｏｔｅＥ”＝Ｅ＼ｅ．Ｔｈｅｎｗｅｈａｖｅ：
Ｔｈｅｏｒｅｍ６．２．２ＴｈｅｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗｃｏｒｒｅｓｐｏｎｄｉｎｇｔｏｖａｒｉａｂｌｅｃｏｓｔｉｎＧ”＝（ＫＥ”）ｉｓｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎＸｏｆｔｈｅｏｒｉｇｉｎａｌｐｒｏｂｌｅｍ．
Ｂｙｔｈｅｏｒｅｍ６，２．２，ｔｈｅｏｒｉｇｉｎａｌｐｒｏｂｌｅｍｉｓｔｒａｎｓｆｏｒｍｅｄｉｎｔｏｌｏｏｋｉｎｇｆｏｒＥ’’ｏｒ
山东大学博士学位论文
Ｃ．Ｔｈｉｓｉｓａｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ，ａｎｄｗｅｃａｎｈａｖｅｒｅｃｏｕｒｓｅｔｏｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ．
Ｓｅｃｔｉｏｎ３ｉｎｔｒｏｄｕｃｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｌＳｏｕｔｌｉｎｅ，ｔｈｅｎｄｅｐｅｎｄｉｎｇｏｎｔｈｅｐｒｏｐ—ｅｒｔｙｏｆｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ，ｗｅｄｅｓｉｇｎｅｄａｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ．Ｓｅｃｔｉｏｎ４ｄｅｓｉｇｎｅｄｔｈｒｅｅｅｘｐｅｒｉｍｅｎｔｓｐｒｏｄｕｃｅｄｂｙｃｏｍｐｕｔｅｒｒａｎｄｏｍｌｙ．Ｔｈｅｓｅｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｅｄｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍ’Ｓｗｅｉｇｈｔｅｄｍｅａｎａｐｐｒｏｘｉｍａｔｉｏｎｒａｔｉｏｉｓｎｏｍｏｒｅｔｈａｎ１．２３，ａｎｄｒｕｎｎｉｎｇｔｉｍｅｉｓａｂｏｕｔ９０ｓｅｃｏｎｄｓｉｎｎｅｔｗｏｒｋｗｉｔｈ１００ｎｏｄｅｓ，ａｎｄｒｕｎｎｉｎｇｔｉｍｅｉｎｃｒｅａｓｅｓｌｉｎｅａｒｌｙｗｉｔｈｎｏｄｅｎｕｍｂｅｒ．
ＴｈｅｉｎｎｏｖａｔｉｖｅｖｉｅｗｐｏｉｎｔｓｏｆｔｈｉｓｄｉｓｓｅｒｔａｔｉｏｎａｒｅａＳｆｏＩｌｏｗｓ：
１｜ＷｈｉｌｅｓｔｕｄｙｉｎｇｔｈｅＳｈｏｒｔｅｓｔＰａｔｈＰｒｏｂｌｅｍｏｎＳｔｏｃｈａｓｔｉｃＴｉｍｅ，ＤｅｐｅｎｄｅｎｔＮｅｔｗｏｒｋ，ｗｅｔｏｏｋｅｘｐｅｃｔｅｄｔｉｍｅｔｏａｒｒｉｖｅａｔａｎｏｄｅａｓｔｈｅｔｉｍｅｔｏａｒｒｉｖｅａｔｔｈｅｎｏｄｅ，ｔｈｅｎｔｏｏｋｒｅｌｅｖａｎｔｅｄｇｅ’Ｓｅｘｐｅｃｔｅｄｌｅｎｇｔｈａｓｌｅｎｇｔｈ，ａｎｄｄｅｓｉｇｎｅｄａＥＳＰａｌｇｏｒｉｔｈｍ；
２．ＷｅｐｕｔｆｏｒｗａｒｄｔｈｅＥｍｅｒｇｅｎｃｙＴｒａｎｓｐｏｒｔａｔｉｏｎＰｒｏｂｌｅｍｗｉｔｈＣｏｓｔＣｏｎ—ｓｔｒａＩｎｔ，ａｎｄｓｔｕｄｉｅｄｔｈｅｒｅｌａｔｉｏｎｂｅｔｗｅｅｎｔｈｅｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎａｎｄｂａｓｉｃｆｅ！ａｓｉｂｌｅｓｏｌｕｔｉｏｎｏｆｔｈｉｓｐｒｏｂｌｅｍａｎｄｔｈｅｔｒａｄｉｔｉｏｎａｌｔｒａｎｓｐｏｒｔａｔｉｏｎｐｒｏｂｌｅｍ．Ｔｈｅｎｗｅｈａｄ：
Ｔｈｅｏｒｅｍ３．３．２ＴｈｅｒｅｍｕｓｔｂｅａｔｌｅａｓｔｏｎｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｐｒｏｂｌｅｍＩｉｎｉｔｓｂａｓｉｃｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎｓｅｔ，ａｎｄｔｈｅｒｅｉｓｍｕｓｔｂｅｏｎｅａｎｄａｔｌｅａｓｔＯｉｌｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｐｒｏｂｌｅｍＩｉｎｔｈｅｂａｓｉｃｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎｓｅｔｏｆｐｒｏｂｌｅｍⅡ．Ｔｈｅｏｒｅｍ３．３．３ＩｆＸｉｓｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｐｒｏｂｌｅｍＩ，ｔｈｅｏｐｔｉｍａｌｓｏｌｕ?ｔｉｏｎｏｆｐｒｏｂｌｅｍⅢｃｏｎｓｔｒｕｃｔｅｄｆｒｏｍＸ１ｉｓＸ２，ａｎｄ∥（Ｆ）＝∑∑叫。ｊ％２＜Ⅳ．
Ｉ＿ｌＪ２ｌ
ｔｈｅｎｔ（ｘ１）＞ｔ∽）．
３．ＷｈｉｌｅｓｔｕｄｙｉｎｇｔｈｅＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍｏｎＣｏｎｔｉｎｕｏｕｓＮｅｔｗｏｒｋ，ｗｅｄｅｆｉｎｅｄｔｈｅＲｅａｃｈｉｎｇＣｏｓｔｏｆＲｅａｃｈａｂｌｅｎｏｄｅＳｅｔ；
４．ＷｈｉｌｅｓｔｕｄｙｉｎｇｔｈｅＵｎｃａｐａｃｉｔａｔｅｄＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍｗｉｔｈＦｉｘｅｄａｎｄＶａｒｉａｂｌｅＣｏｓｔ，ｗｅｃｏｎｓｔｒｕｃｔＷｅｉｇｈｔＧｒａｐｈｗ（ａ）＝（ＫＦ）；
５．ＷｅｇａｖｅｔｈｅＣａｐａｃｉｔａｔｅｄＭｉｎｉｍｕｍＣｏｓｔＦｌｏｗＰｒｏｂｌｅｍｗｉｔｈＦｉｘｅｄａｎｄＶａｒｉａｂｌｅＣｏｓｔ，ａｎｄｐｒｏｖｅｄｔｗｏｔｈｅｏｒｅｍｓａｂｏｕｔｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ’Ｓｐｒｏｐｅｒｔｙ：Ｔｈｅｏｒｅｍ６．２．１ＩｆＧ７＝Ｇ（ＵＥ’）ｉｓａｓｕｂ－ｎｅｔｗｏｒｋｏｆＧｃｏｎｓｔｒｕｃｔｅｄｆｒｏｍＦ，ｔｈｅｎｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎＸｍｕｓｔｈｅａｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗｃｏｒｒｅｓｐｏｎｄｉｎｇｔｏ
原创性声明
本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。
期：二２妇血７论文作者签名：壹舀毛专二一日
关于学位论文使用授权的声明
本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。
（保密论文在解密后应遵守此规定）
论文作者签名：ｊ避导师签名：啦日期：坠仝。５．ｆ］
遗传算法与组合优化.
第四章 遗传算法与组合优化 4.1 背包问题（knapsack problem ） 4.1.1 问题描述 0/1背包问题：给出几个尺寸为S 1，S 2，…，S n 的物体和容量为C 的背包，此处S 1，S 2，…，S n 和C 都是正整数；要求找出n 个物件的一个子集使其尽可能多地填满容量为C 的背包。 数学形式： 最大化 ∑=n i i i X S 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 广义背包问题：输入由C 和两个向量C ＝(S 1，S 2，…，S n )和P ＝(P 1，P 2，…，P n )组成。设X 为一整数集合，即X ＝1，2，3，…，n ，T 为X 的子集，则问题就是找出满足约束条件∑∈≤T i i C X ，而使∑∈T i i P 获得最大的子集T ，即求S i 和P i 的下标子集。 在应用问题中，设S 的元素是n 项经营活动各自所需的资源消耗，C 是所能提供的资源总量，P 的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。 广义背包问题可以数学形式更精确地描述如下： 最大化 ∑=n i i i X P 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 背包问题在计算理论中属于NP —完全问题，其计算复杂度为O (2n )，若允许物件可以部分地装入背包，即允许X ，可取从0.00到1.00闭区间上的实数，则背包问题就简化为极简单的P 类问题，此时计算复杂度为O (n )。
4.1.2 遗传编码 采用下标子集T 的二进制编码方案是常用的遗传编码方法。串T 的长度等于n(问题规模)，T i (1≤i ≤n )＝1表示该物件装入背包，T i ＝0表示不装入背包。基于背包问题有近似求解知识，以及考虑到遗传算法的特点（适合短定义距的、低阶的、高适应度的模式构成的积木块结构类问题），通常将P i ，S i 按P i /S i 值的大小依次排列，即P 1/S 1≥P 2/S 2≥…≥P n /S n 。 4.1.3 适应度函数 在上述编码情况下，背包问题的目标函数和约束条件可表示如下。 目标函数：∑==n i i i P T T J 1 )( 约束条件：C S T n i i i ≤∑=1 按照利用惩罚函数处理约束条件的方法，我们可构造背包问题的适应度函数f (T )如下式： f (T ) = J (T ) + g (T ) 式中g (T )为对T 超越约束条件的惩罚函数，惩罚函数可构造如下: 式中E m 为P i /S (1≤i ≤n )i 的最大值，β为合适的惩罚系数。 4.2 货郎担问题（Traveling Salesman Problem ——TSP ） 在遗传其法研究中，TSP 问题已被广泛地用于评价不同的遗传操作及选择机制的性能。之所以如此，主要有以下几个方面的原因： (1) TSP 问题是一个典型的、易于描述却难以处理的NP 完全（NP-complete ）问题。有效地 解决TSP 问题在可计算理论上有着重要的理论价值。 (2) TSP 问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此，快速、有效 地解决TSP 问题有着极高的实际应用价值。 (3) TSP 问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准，而遗传算法 就其本质来说，主要是处理复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在TSP 问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP 问题等有着多方面的重要意义。
基于遗传算法的多式联运组合优化
第四章基于遗传算法的集装箱多式联运运输组合优化模型 的求解 4.1 遗传算法简介 4.1.1 遗传算法 遗传算法(Genetic Algorithm,GA)是在20世纪六七十年代由美国密歇根大学的Holland J.H.教授及其学生和同事在研究人工自适应系统中发展起来的一种随机搜索方法,通过进一步的研究逐渐形成了一个完整的理论和方法体系取名为基本遗传算法(Simple Genetic Algorithm)。在接下来几年的研究过程中Holland在研究自然和人工系统的自适应行为的过程中采用了这个算法，并在他的著作《自然系统和人工系统的适配》中对基本遗传算法的理论和方法进行了系统的阐述与描写，同时提出了在遗传算法的理论研究和发展中具有极为重要的作用的模式理论，它的编码技术和遗传操作成为了遗传算法被广泛并成功的应用的基础，经过许多学者多年来的研究，遗传算法逐渐成熟起来，到现在已经成为了一个非常大的体系，广泛的应用于组合优化、系统优化、过程控制、经济预测、模式识别以及智能控制等多个领域。De Jong于1975年在他的博士论文中设计了一系列针对于各种函数优化问题的遗传算法的执行策略，详细分析了各项性能的评价指标。在此基础上，美国伊利诺大学的Goldberg于1989年系统全面的阐述了遗传算法理论，并通过例证对遗传算法的多领域应用进行了分析，为现代遗传算法的研究和发展奠定了基础。 遗传算法是一种模仿基于自然选择的生物进化过程的随机方法，它以类似于基因的编码作为种群的个体，首先，随机的产生初始种群的个体，从这个群体开始进行搜索，根据类似于生物适应能力的适应度函数值的大小，按照不同问题各自的特点，在当前的种群中运用适当的选择策略选择适应能力大的个体，其中所选择出来的个体经过遗传操作、交叉操作以及变异操作产生下一代种群个体。如此反复，像生物的进化过程一样逐代进化，直到满足期望的终止条件为止。
基于多目标粒子群算法的多约束组合优化问题研究
基于多目标粒子群算法的多约束组合优化问题研究组合优化问题在金融投资、资源分配等领域有着重要的应用,其求解方法一直是人们研究的重点。实际工程应用中的组合优化问题往往具有多个约束条件且在很多情况下问题规模较大,传统的优化算法由于需要遍历整个解空间,因此无法在多项式时间内完成求解。 元启发式算法将随机搜索算法与局部搜索算法相结合,同时从目标空间中的多个位置开始搜索,且目标是尽可能获得更好的解,被认为更适合用来求解具有多个约束的组合优化问题。遗传算法、粒子群算法、蚁群算法等都是常见的元启发式算法。 其中粒子群优化算法通过种群中个体之间的相互协作使得整个种群逐渐向问题的最优解靠近并最终收敛,其由分散到集中的寻优方式以及参数设置少、收敛快等特点使得该算法在解决多约束组合优化问题方面得到了广泛的应用。在解决多约束组合优化问题的过程中,如何妥善处理约束条件也是一个需要我们重点关注的问题。 根据对已有约束处理方法优缺点的分析,本文采用约束转目标的方法将多约束优化问题转化为具有三个以上目标的多目标优化问题,并结合粒子群算法对其进行求解。为了搜索到质量更高的最优解,本文提出一种改进的多目标粒子群优化算法IMaOPSO,以违反约束度来维护外部档案,以拥挤度和种群中个体与理想点的距离作为两个指标寻找种群的全局最优。 并且加入扰动变异算子来扩大粒子的搜索区域,使参与变异的粒子个数随算法迭代次数的增加而减少,在保证算法开发能力的同时避免其陷入局部最优。此外,针对多约束组合优化问题目标空间复杂、问题规模大的情况,在IMaOPSO算法
的基础上提出了一种基于多种群协同进化的多目标粒子群算法,使用多个种群分别搜索不同的区域,并且改进了算法的速度更新机制以及在算法中设计了一个替换算子,以提高算法的收敛性。 最后,以不同规模的多背包问题为算例验证了所提算法的有效性。
宝洁公司的产品组合策略和品牌策略分析分析报告.doc
宝洁公司的产品组合策略和品牌策略分析报告.doc
————————————————————————————————作者：————————————————————————————————日期：
宝洁公司产品组合策略和品牌策略分析报告 大部分企业都不只是一种产品，而是拥有多种产品，如何将这些产品统筹安排好，就是产品组合所要解决的事情。 一、宝洁公司简介 宝洁公司（Procter & Gamble），简称P&G，是一家美国消费日用品生产商，也是目前全球最大的日用品公司之一。宝洁在日用化学品市场上知名度相当高，其产品包括洗发、护发、护肤用品、化妆品、婴儿护理产品、妇女卫生用品、医药、食品、饮料、织物、家居护理、个人清洁用品及电池等。公司口号：“宝洁公司，优质出品。”旗下主要洗发护发用品：飘柔、伊卡璐、潘婷、海飞丝、沙宣等洗发护发系列。 二、宝洁公司的产品组合 在中国的洗发水领域中，宝洁公司推行多品牌的差异化市场细分策略，旗下拥有飘柔、海飞丝、潘婷、沙宣等多个强势的品牌，建立了相当高的品牌忠诚度，在洗发水行业占据了绝对的优势地位，下面是宝洁公司的产品组合示意图
产品线长度产品组合的宽度 洗涤剂牙膏香皂方便尿片 象牙雪 1930 格里 1952 象牙 1879 帮宝适 1961 洁佛 1923 佳洁士 1955 柯柯 1885 露肤 1976 汰渍 1946 登鞋 1980 拉瓦 1893 快乐 1923 佳美 1926 奥克多 1952 爵士 1952 达士 1954 舒肤佳 1963 大胆 1956 海岸 1974 吉思 1966 黎明 1942 独立 1979 表中表明宝洁公司产品组合的宽度是四条，产品项目的总数是22个，由于宝洁公司都是通过相同的分销渠道出售。因此，我们可以说该公司产品具有较强的关联性。就以上的产品对消费者的用途不同而言，该公司的产品线缺乏关联性。 三、宝洁洗发水的产品组合策略 1、扩展策略 宝洁洗发水有多种产品系列，如沙宣系列、潘婷系列、海飞丝系列等。对于宝洁洗发水系列来说，其适应市场需求，生产不同规格的产品。中等规格一般在200ml—400ml，大瓶一般在750ml。并且其生产有洗发水息息相关的一系列产品，如精华素、发膜等。而且宝洁的洗发水都有自己独特的功效，其中飘柔以使头发光滑柔顺著称，有去头屑、营养护发、洗护合一等几种产品。潘婷以头发修复及深层护养著称，有丝质顺滑、弹性丰盈、特效修复、清爽洁净去屑四大系列护
约束优化问题的极值条件
等式约束优化问题的极值条件 求解等式约束优化问题 )(m i n x f ..t s ()0=x h k ()m k ,,2,1???= 需要导出极值存在的条件，对这一问题有两种处理方法：消元法和拉格朗日乘子法（升维法） 一、消元法（降维法） 1.对于二元函数 ),(min 21x x f ..t s ()0,21=x x h ， 根据等式约束条件，将一个变量1x 表示成另一个变量2x 的函数关系()21x x ?=，然后将这一函数关系代入到目标函数()21,x x f 中消去1x 变成一元函数()2x F 2.对于n 维情况 ()n x x x f ,,,min 21???..t s ()0,,,21=???n k x x x h ),,2,1(l k ???= 由l 个约束方程将n 个变量中的前l 个变量用其余的l n -个变量表示： ()n l l x x x x ,,,2111???=++? ()n l l x x x x ,,,2122???=++? ... ()n l l l l x x x x ,,,21???=++? 将这些函数关系代入到目标函数中，得到()n l l x x x F ,,,21???++ 二、拉格朗日乘子法（升维法） 设T n x x x x ),,,(21???=，目标函数是()x f ，约束条件()0=x h k ),,2,1(l k ???=的l 个等式约束方程。为了求出()x f 的可能极值点T n x x x x ),,,(**2*1*???=，引入拉格朗日乘子k λ),,2,1(l k ???=，并构成一个新的目标函数 ()()x h x f x F l k k k ∑=+=1),(λλ 把()λ,x F 作为新的无约束条件的目标函数来求解它的极值点，满足约束条件 ()0=x h k ),,2,1(l k ???=的原目标函数()x f 的极值点。 ()λ,x F 具有极值的必要条件 ),,2,1(0n i x F i ???==?? ，),,2,1(0l k F k ???==??λ可得n l +
产品组合与产品策略分析
产品组合 现代企业出于扩大销售，分散风险，增加利润等原因，往往需要给目标市场提供系列产品组合而不是单一的产品或服务，这就涉及到产品组合决策问题。不论企业处于何种生命周期阶段，产品组合决策都是组织的核心决策之一。所谓最佳产品组合决策，是解决在一定约束条件下，通过选择企业产品系列种类的深化程度方案或产品线宽度的扩展程度方案的过程，寻求能使企业处于更有利的盈利和竞争状态的最佳产品组合。即如何安排产品组合，才能实现利润最大化的问题。为解决这个问题，人们开发出了各具适用性的产品组合决策模型，包括广为使用的矩阵分析模型系列和定量决策模型。它们对产品组合决策有其不同的功能价值和适用范围。对其适用性进行研究评价以及改进模型以增强其适用性无疑是非常有价值的课题。 一、矩阵类模型的适用性比较分析 常见的产品组合决策的矩阵类模型包括波士顿矩阵模型（BCG Matrix）及其改进优化的衍生模型如通用电器矩阵（GE Matrix）、C·霍福尔矩阵(C·Hofer Matrix)和三维分析图法等，统称为公司业务组合分析法（portfolio analysis）。这些产品组合决策模型分别有其适用性的优点和局限性，同时也有其适用共同性。 1、波士顿矩阵模型适用性比较分析 波士顿矩阵模型的基本思路是根据产品在市场上的销售增长率和市场占有率两个指标组合的状况对产品的市场地位做出评价，并针对组织现有业务组合和资源状况对每类产品选择合适的经营策略，决策出企业产品组合战略图谱。其优点是简便易行，但突出的局限性有两个，一是市场上的销售增长率和市场占有率两个指标代表力薄弱，存在较为明显的失真现象，使得模型对现实的解释和预判效力十分有限。与其关联的第二方面局限性是对瘦狗产品给出的实施战略过于机械和单一，事实上瘦狗产品的战略也是可以有多项选择的可行性。 2、通用电器矩阵模型适用性比较分析 鉴于波士顿矩阵模型的缺陷，美国通用电器公司对其进行了优化改进，用竞争地位和产业吸引力这两个更综合的指标置换了原有的单薄指标，并将指标值的二分法改良为更加精确的三分法，形成了九象限的新模型——行业引力／企业实力模型，即通用电器矩阵模型（GE Matrix）,也称作战略经营计划方格(Strategic Business Planning)，为管理者制定产品组合战略提供了更加细致合理的分析决策工具，并强调引入时间变量做出时间序列图谱用以比对，增强战略选择的可行性，由此大大增强了模型的适用范围。但其局限性正是由指标综合化优势衍生出的计算烦琐这个负效应所致，使得它的两个指标值的确定会带有强烈的主观判断性成分，因而在评价分析中存在着较大的模糊性，降低了模型的科学效力。与此对比，波士顿矩阵模型的两个指标评价却有较明晰的确定性。因此比较稳妥的做法是扬长避短，把波士顿矩阵模型用于竞争分析，而把通用电器矩阵模型用于本企业资源配置分析。 3、霍福尔矩阵模型适用性比较分析 为了增强矩阵的适用性，人们不断对上述模型进行改良优化，其中比较有代表性的模型是C·霍福尔矩阵（C·Hofer Matrix）和三维分析图法。C·霍福尔的产品／市场发展矩阵（Product/market Evolution Matrix）扩展了上述两种产品战略的选择方法，用产品／市场发展五阶段指标替换了业务增长率和产业吸引力两个指标因子作为新的纵坐标，与原有的横坐标——竞争地位三个指标值形成了多达十五象限的新矩阵，并为每一象限的产品配置了不同的战略处方，从而构建出了大多数企业的矩阵必居其一的三种典型的产品组合矩阵：成长型、
产品组合策略
产品组合策略 产品好比人一样，都有其由成长到衰退的过程。因此，企业不能仅仅经营单一的产品，世界上很多企业经营的产品往往种类繁多，如美国光学公司生产的产品超过3万种，美国通用电气公司经营的产品多达25万种。当然，并不是经营的产品越多越好，二个企业应该生产和经营哪些产品才是有利的?这些产品之间应该有些什么配合关系?--这就是产品组合问题。 一、产品组合 所谓产品组合是指一个企业生产或经营的全部产品线、产品项目的组合方式，它包括四个变数：宽度、长度、深度和一致性。例如美国宝洁公司的众多产品线中，有一条牙膏产品线，生产格利、克雷丝、登奎尔三种品牌的牙膏，所以该产品线有三个产品项目。其中克雷丝牙膏有三种规格和两种配方，则克雷丝牙膏的深度就是6。如果我们能计算每一产品项目的品种数目，就可以计算出该产品组合的平均深度。 企业在进行产品组合时，涉及到三个层次的问题需要做出抉择，即： ①是否增加、修改或剔除产品项目； ②是否扩展、填充和删除产品线； ③哪些产品线需要增设、加强、简化或淘汰--以此来确定最佳的产品组合。 三个层次问题的抉择应该遵循既有利于促进销售、又有利于增加企业的总利润这个基本原则。 产品组合的四个因素和促进销售、增加利润都有密切的关系。一般来说，拓宽、增加产品线有利于发挥企业的潜力、开拓新的市场；延长或加深产品线可以适合更多的特殊需要；加强产品线之间的一致性，可以增强企业的市场地位，发挥和提高企业在有关专业上的能力。 二、产品组合的评价方法
一种分析产品组合是否健全、平衡的方法称为三维分析图。在三维空间坐标上，以x、y＼x三个坐标轴分别表示市场占有率、销售成长率以及利润率，每一个坐标轴又为高、低两段，这样就能得到八种可能的位置。如三维分析图所示： 如果企业的大多数产品项目或产品线处于1、2、3、4号位置上，就可以认为产品组合已达到最佳状态。因为任何一个产品项目或产品线的利润率、成长率和占有率都有一个由低到高又转为低的变化过程，不能要求所有的产品项目同时达到最好的状态，即使同时达到也是不能持久的。因此企业所能要求的最佳产品组合，必然包括：目前虽不能获利但有良好发展前途、预期成为未来主要产品的新产品；目前已达到高利润率、高成长率和高占有率的主要产品；目前虽仍有较高利润率而销售成长率已趋降低的维持性产品；以及已决定淘汰、逐步收缩其投资以减少企业损失的衰退产品。 根据以上产品线分析，针对市场的变化，调整现有产品结构，从而寻求和保持产品结构最优化，这就是产品组合策略，其中包括如下策略： ①产品线扩散策略：包括向下策略、向上策略、双向策略和产品线填补策略； ②产品线削减策略；
数学建模：投资问题
投资的收益与风险问题 摘要 对市场上的多种风险资产和一种无风险资产（存银行）进行组合投资策略的设计需要考虑两个目标：总体收益尽可能大和总体风险尽可能小，而这两个目标在一定意义上是对立的。 本文我们建立了投资收益与风险的双目标优化模型，并通过“最大化策略”，即控制风险使收益最大，将原模型简化为单目标的线性规划模型一；在保证一定收益水平下，以风险最小为目标，将原模型简化为了极小极大规划模型二；以及引入收益——风险偏好系数，将两目标加权，化原模型为单目标非线性模型模型三。然后分别使用Matlab的内部函数linprog，fminmax，fmincon对不同的风险水平，收益水平，以及偏好系数求解三个模型。 关键词：组合投资，两目标优化模型，风险偏好
2.问题重述与分析 3.市场上有种资产（如股票、债券、…）()供投资者选择，某公司有数额为的 一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这种资产进行了评估，估算出在这一时期内购买的平均收益率为，并预测出购买的风险损失率为。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的中最大的一个风险来度量。 购买要付交易费，费率为，并且当购买额不超过给定值时，交易费按购买计算（不买当然无须付费）。另外，假定同期银行存款利率是, 且既无交易费又无风险。（） 1、已知时的相关数据如下： 试给该公司设计一种投资组合方案，即用给定的资金，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。 2、试就一般情况对以上问题进行讨论，并利用以下数据进行计算。 本题需要我们设计一种投资组合方案，使收益尽可能大，而风险尽可能小。并给出对应的盈亏数据，以及一般情况的讨论。 这是一个优化问题，要决策的是每种资产的投资额，要达到目标包括两方面的要求:净收益最大和总风险最低，即本题是一个双优化的问题，一般情况下，这两个目标是矛盾的，因为净收益越大则风险也会随着增加，反之也是一样的，所以，我们很难或者不可能提出同时满足这两个目标的决策方案，我们只能做到的是：在收益一定的情况下，使得风险最小的决策，或者在风险一定的情况下，使得净收益最大，或者在收益和风险按确定好的偏好比例的情况下设计出最好的决策方案，这
数学建模中的优化问题与规划模型
与最大、最小、最长、最短等等有关的问题都是优化问题。 解决优化问题形成管理科学的数学方法：运筹学。运筹学主要分支：（非）线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。 6.1 线性规划 1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论. 1. 问题 例1 作物种植安排 一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力1/2 1/3 1/4, 预计每亩产值分别为110元, 75元, 60元. 如何规划经营使经济效益最大. 分析：以取得最高的产值的方式达到收益最大的目标. 1. 求什么？分别安排多少亩地种蔬菜、棉花、水稻？ x 1亩、 x 2 亩、 x 3 亩 2. 优化什么？产值最大 max f=10x 1+75x 2 +60x 3 3. 限制条件？田地总量 x 1+x 2 +x 3 ≤ 50 劳力总数 1/2x 1 +1/3x 2 +1/4x 3 ≤ 20 模型I : 设决策变量：种植蔬菜x1亩, 棉花x2亩, 水稻x3亩， 求目标函数f=110x1+75x2+60x3 在约束条件x1+x2+x3≤ 50 1/2x1+1/3x2+1/4x3 ≤20 下的最大值 规划问题：求目标函数在约束条件下的最值, 规划问题包含3个组成要素: 决策变量、目标函数、约束条件。 当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题, 否则称为非线性规划问题。 2. 线性规划问题求解方法 称满足约束条件的向量为可行解,称可行解的集合为可行域, 称使目标函数达最值的可行解为最优解. 命题 1 线性规划问题的可行解集是凸集. 因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。 命题2 线性规划问题的最优解一定在可行解集的某个极点上达到. 图解法：解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的值，经比较后，取最值点为最优解。 命题 3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一族平行直线,目标值的大小描述了直线离原点的远近。 于是穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点即为取的极值的极点—最优解。 单纯形法: 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解. 正则模型: 决策变量: x 1,x 2 ,…,x n . 目标函数: Z=c 1 x 1 +c 2 x 2 +…+c n x n . 约束条件: a 11 x1+…+a1n x n≤b1, ……a m1x1+…+a mn x n≤b m, 模型的标准化 10. 引入松弛变量将不等式约束变为等式约束. 若有 a i1x 1 +…+a in x n ≤b i , 则引入 x n+i ≥ 0, 使得 a i1 x 1 +…+a in x n + x n+i =b i 若有 a j1x 1 +…+a jn x n ≥b j , 则引入 x n+j ≥ 0, 使得 a j1 x 1 +…+a jn x n - x n+j =b j .
粒子群算法和蚁群算法的结合及其在组合优化中的应用e
2007年第2期空间电子技术收稿日期：2006-04-03；收修改稿日期：2006-04-30 粒子群算法和蚁群算法的结合及其在 组合优化中的应用 张长春苏昕易克初 （西安电子科技大学综合业务网国家重点实验室，西安710071） 摘要文章首次提出了一种用于求解组合优化问题的PAAA 算法。该算法有效地 结合了粒子群算法和蚁群算法的优点，先利用粒子群算法的随机性、快速性、全局性得到 初始信息素分布（即粗搜索），再利用蚁群算法的并行性、正反馈性、求解精度高等优点求 精确解（即细搜索）。将文中提出的算法用于经典TSP 问题的求解，仿真结果表明PAAA 算 法兼有两种算法的优点，同时抛弃了各自的缺点。该算法在时间效率上优于蚁群算法，在 求精效率上优于粒子群算法，是综合了两种算法长处的一种新的启发式算法，达到时间性 能和优化性能上的双赢，获得了非常好的效果。 主题词蚁群算法粒子群算法旅行商问题PAAA 0引言 近年来对生物启发式计算（Bio-inspired Computing ）的研究，越来越引起众多学者的关注和兴趣，产生了神经网络、遗传算法、模拟退火、粒子群算法、蚁群算法等许多用于解决复杂优化问题的新方法。然而，面对各种问题的特殊性和复杂性，每种算法都表现出了自身的优势和缺陷，都存在时间性能和优化性能不能兼得的矛盾。 粒子群优化（Particie Swarm Optimization ，PSO ）算法[1， 2]是由Eberhart 和Kennedy 于1995年提出的一种全局优化算法，该算法源于对鸟群觅食行为的模拟。它的优势在于：（1） 算法简洁，可调参数少，易于实现；（2） 随机初始化种群，具有较强的全局搜索能力，类似于遗传算法；（3）利用评价函数衡量个体的优劣程度，搜索速度快；（4）具有较强的可扩展性。其缺点是：不能充分利用系统中的反馈信息，求解组合优化问题的能力不强。 蚁群算法[3，4]（Ant Coiony Optimization ，ACO ） 是由意大利学者M.Dorigo ，V.Maniezzo 和A.Coiorni 于20世纪90年代初提出的一种新型的智能优化算法，已经被应用到TSP 问题[5，6]、二次分配问题、工 件调度问题、图着色问题等许多经典组合优化问题中，取得了很好的效果。它的优点是：（1）采用一种正反馈机制，通过信息素的不断更新，达到最终收敛于最优路径上的目的；（2）是一种分布式的优化方法，易于并行实现；（3）是一种全局优化的方法，不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；（4）适合于求解离散优化问题；（5）鲁棒性强。但由于在算法的初始阶段信息素匮乏，所以求解速度较慢。 文章将粒子群算法和蚁群算法有机地结合，提出了PAAA 算法。它利用粒子群算法的较强的全局搜索能力生成信息素分布，再利用蚁群算法的正反馈机制求问题的精确解，汲取各自的优势，以达空间电子技术 SPACE ELECTRONIC TECHNOLOGY !"
遗传算法及其在TSP问题中的应用
遗传算法及其在TSP问题中的应用 摘要：本文首先介绍了遗传算法的基本理论与方法，从应用的角度对遗传算法做了认真的分析和研究，总结了用遗传算法提出求解组合优化问题中的典型问题——TSP问题的最优近似解的算法。其次，本文在深入分析和研究了遗传算法基本理论与方法的基础上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用Matlab语言编程实现其算法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改进，或者将遗传算法与其他方法相结合，以及在编程过程中对算法流程的改进。本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解TSP问题为例，深入讨论了各个遗传算子的程序实现，并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作用，最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在，以及运用Matlab编写遗传算法程序的一些注意事项。最后，本文提出将遗传算法与其它算法相结合来求解一般问题的想法；并将遗传算法的应用范围扩展，提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题，如求解配送/收集旅行商问题的遗传算法（TSPD）、遗传算法在货物配送问题中的应用（ST－TSP）、多旅行商问题（MTSP）等。 引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一个函数；而在组合优化问题中，一般是从一个无限集或有限的几个无限集中寻找一个对象——它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优化，它描述的是旅行商经N个城市的最短路径问题，因而对TSP问题的求解是数学上，同时也是优化问题中普遍关注的。旅行商问题（Traveling Salesman Problem，简称TSP）也称为货担郎问题，是一个较古的问题，最早可以追溯到1759年Euler提出的骑士旅行问题[9]。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（和旅行距离最短）的路径。 TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难精确地求出其最优解，因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题，经过简化处理后，都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的发展也具有重要意义。在过去的20年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机
九阳公司产品组合策略研究
九阳公司产品组合策略研究 1.绪论 1.1小家电市场环境分析 一直以来，小家电产业都是在沉默中低调潜行。然而随着大家电市场连年烽火硝烟，价格战互殴、原材料涨价、流通领域成本居高不下等等因素导致的大家电市场空间日益紧缩，利润空间逐渐薄弱，如今但凡涉及到家电行业的企业都把目光聚焦到了小家电这块“沃土”之上，相对的高额利润回报、快速的资金周转率、低应收账款回收风险是各路资本争宠小家电的最大理由。中国小家电市场正步入快速成长期，每年以超过20%的增长速度发展，潜力巨大。欧美国家市场上小家电品种约为200种，中国仅有不到100种；中国家庭平均拥有小家电数量不到10件，拥有量远低于欧美国家每户20-30件的水平；小家电的生命周期一般只有3年至6年，产品更新换代速度较传统家电快，消费者对小家电有持续的换购需求。于是乎众多洋品牌挥马杀到，大家电巨头纷纷树起大旗，小家电企业反戈迎战，“螺丝刀”工厂浑水摸鱼，此四股力量扎堆混战，一时难见高下，促使整个小家电产业波澜兴起。 1.1.1公司简介 九阳公司是国家大豆行动计划领导小组认定的示范企业、国家级星火计划重点扶持企业和中国专利山东省明星企业。作为一个专业化、追求卓越的小家电企业，九阳选择了自己擅长的领域切入，其总体发展的策略目标是树立在豆浆机制造领域的权威地位，通过不断推
陈出新产品来延长该产业的生命期。同时，在以豆浆机为核心的专业化利润模式的主线下，多年来的市场打拼使其在与厨房相关的各类小家电产品的市场消费心理、产品设计理念和大众需求趋势等方面积累了丰富经验，这为其拓宽相关产品线打下了良好而专业的基础。围绕己之所长的主动出击成为九阳可持续发展的另一张王牌，公司正积极延长产业链，多数产品正处于市场成长期，发展潜力巨大。九阳主要产品覆盖豆浆机、电磁灶、料理机、榨汁机、开水煲、紫砂煲、电压力煲等七大系列，作为豆浆机市场的开创者，公司豆浆机目前市场占有率87%，占据绝对优势的地位。公司在其他厨卫家电产品表现同样出众。料理机市场占有率排名第一，电磁炉、榨汁机、紫砂煲和开水煲排名第二。目前，公司拥有450名一级经销商，营销网络覆盖全国270多个地级城市、2000个县级城市，拥有8000多个零售终端。营销网络覆盖电器专营店、大卖场、百货商场等多种形式，自建的专卖店数量占比稳步增长，具有较强的议价能力，从而取得较高的毛利率。公司在行业内有着优异的业绩，2007年销售收入达到19.43亿元，净利润达到3.63亿元，在同行业企业中均居领先地位。 1.1.2市场分析 （1）小家电市场竞争格局分析 通常来说：小家电（small domestic appliance）包括个人护理系列、厨房小电器系列、家居电器系列、健康护理系列产品。这些系列又被称为“家庭小电器“和“个人护理产品”。在目前小家电市场，根据行业的品牌背景和营销特点可分为以下几类：1）国际小家电品牌
组合最优化问题及其求解优化算法
组合最优化问题最基本的特点就是变量是离散的, 由此导致其数学模型中的目标函数和约束函数在其可行域内是也是离散的。在现实世界中，许多的实际问题本质上是离散事件的而不是连续事件，都可归结为组合最优化问题。这类问题在理论上多数都属于NP难问题，NP类问题仍属于可计算问题，即存在算法来求解。求解这类组合最优化问题方法分为精确算法和近似算法两类。 常用的精确算法有动态规划、分支定界和枚举等。精确算法只能解决一些小规模问题，当求解小规模组合优化问题时可以用这类精确算法在较短的时间内得到最优解。当求解大规模组合优化问题时，理论上可以得到问题的最优解，但由于计算量太大，所以使用精确算法并不可行。利用精确算法求解NP-hard组合优化问题时，即使能得到最优解，但所需要的计算时间过长，在实际问题中难以直接应用。 近似算法是指在合理的计算时间内找到一个近似的最优解。近似算法虽然求解速度较快，但并不能保证得到问题的全局最优解。近似算法分为基于数学规划（最优化）的近似算法、启发式算法和基于智能优化的近似算法。 1) 基于数学规划（最优化）的近似算法是根据对问题建立的数学规划模型，运用如拉格朗日松弛、列生成等算法以获得问题的近似解，是以数学模型为基础，采用列生成、拉格朗日松弛和状态空间松弛等求解问题。 拉格朗日松弛（LR）算法求解问题的主要思想是分解和协调。首先对于NP难的优化问题，其数学模型须具有可分离性。通过使用拉格朗日乘子向量将模型中复杂的耦合约束引入目标函数，使耦合约束解除，形成松弛问题，从而分解为一些相互独立的易于求解的子问题，设计有效的算法求得所有子问题的最优解。利用乘子的迭代更新来实现子问题解的协调。列生成(Column generation, CG)算法是一种已经被认可的成功用于求解大规模线性规划、整数规划及混合整数规划问题的算法。 与智能优化算法相比，基于数学规划的近似算法的优点是通过建立问题的数学模型，松弛模型中难解的耦合约束或整数约束，得到的松弛问题的最优解可以为原问题提供一个下界。同时基于数学规划的近似算法还具有很好的自我评价功能，通过算法运行给出的问题的近优解(或最优解)为原问题提供一个上界，上界与下界进行比较，可以衡量算法的性能。 2) 启发式算法根据求解问题的特点，按照人们经验或某种规则设计的。这是一种构造式算法，比较直观、快速，利用问题的知识设计求解的方法步骤，相对比较简单，这种方法的求解速度较快，但所得解的质量不一定好。 3) 基于智能优化的近似算法是基于一定的优化搜索机制，并具有全局优化性能的一类算法。这类智能优化算法常见的有：模拟退火(SA)、遗传算法(GA)、蚁群算法(ACO)、路径重连算法(PR)、迭代局部搜索算法(ILS)、禁忌搜索算法(TS)、分散搜索算法(SS)、粒子群算法(PSO)等，这些算法也称超启发式算法(Meta-heuristic)。 智能优化算法是一种通用的算法框架，只要根据具体问题特点对这种算法框架结构进行局部修改，就可以直接应用它去解决不同的问题。这类算法本身不局限于某个框架，具有实践的通用性，适应于求解工业实际问题，能较快地处理大规模数据的同时得到令人满意的解。基于智能优化的近似算法，采用不同的搜索策略和优化搜索机制，寻找问题的近似最优解，具有很好的求解优势。虽然基于智能优化的近似算法不能保证求得全局最优解，但因其高效的优化性能、无需问题特殊信息、易于实现且速度较快等优点, 受到诸多领域广泛的关注和应用。基于智能优化的近似算法(超启发式算法)成为求解复杂组合最优化问题主要的有效方法。
产品组合策略
产品组合策略 Ting Bao was revised on January 6, 20021
产品组合策略 产品好比人一样，都有其由成长到衰退的过程。因此，企业不能仅仅经营单一的产品，世界上很多企业经营的产品往往种类繁多，如美国光学公司生产的产品超过3万种，美国通用电气公司经营的产品多达25万种。当然，并不是经营的产品越多越好，二个企业应该生产和经营哪些产品才是有利的这些产品之间应该有些什么配合关系--这就是产品组合问题。一、产品组合所谓产品组合是指一个企业生产或经营的全部产品线、产品项目的组合方式，它包括四个变数：宽度、长度、深度和一致性。例如美国宝洁公司的众多产品线中，有一条牙膏产品线，生产格利、克雷丝、登奎尔三种品牌的牙膏，所以该产品线有三个产品项目。其中克雷丝牙膏有三种规格和两种配方，则克雷丝牙膏的深度就是6。如果我们能计算每一产品项目的品种数目，就可以计算出该产品组合的平均深度。企业在进行产品组合时，涉及到三个层次的问题需要做出抉择，即：①是否增加、修改或剔除产品项目；②是否扩展、填充和删除产品线；③哪些产品线需要增设、加强、简化或淘汰--以此来确定最佳的产品组合。三个层次问题的抉择应该遵循既有利于促进销售、又有利于增加企业的总利润这个基本原则。产品组合的四个因素和促进销售、增加利润都有密切的关系。一般来说，拓宽、增加产品线有利于发挥企业的潜力、开拓新的市场；延长或加深产品线可以适合更多的特殊需要；加强产品线之间的一致性，可以增强企业的市场地位，发挥和提高企业在有关专业上的能力。二、产品组合的评价方法一种分析产品组合是否健全、平衡的方法称为三维分析图。在三维空间坐标上，以x、y＼x三个坐标轴分别表示市场占有率、销售成长率以及利润率，每一个坐标轴又为高、低两段，这样就能得到八种可能的位置。如三维分析图所示： 如果企业的大多数产品项目或产品线处于1、2、3、4号位置上，就可以认为产品组合已达到最佳状态。因为任何一个产品项目或产品线的利润率、成长率和占有率都有一个由低到高又转为低的变化过程，不能要求所有的产品项目同时达到最好
2011-组合优化问题简约与算法推演
软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.wendangku.net/doc/fa998066.html, Journal of Software,2011,22(9):1985?1993 [doi: 10.3724/SP.J.1001.2011.03948] https://www.wendangku.net/doc/fa998066.html, +86-10-62562563 ?中国科学院软件研究所版权所有. Tel/Fax: ? 组合优化问题简约与算法推演 郑宇军1,2+, 薛锦云1,2, 凌海风3 1(中国科学院软件研究所计算机科学国家重点实验室,北京 100190) 2(江西师范大学江西省高性能计算重点实验室,江西南昌 330027) 3(南京大学管理工程学院,江苏南京 210093) Combinatorial Optimization Problem Reduction and Algorithm Derivation ZHENG Yu-Jun1,2+, XUE Jin-Yun1,2, LING Hai-Feng3 1(The State Key Laboratory of Computer Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China) 2(Provincial Key Laboratory of High Performance Computing, Jiangxi Normal University, Nanchang 330027, China) 3(School of Management and Engineering, Nanjing University, Nanjing 210093, China) + Corresponding author: E-mail: yujun.zheng@https://www.wendangku.net/doc/fa998066.html, Zheng YJ, Xue JY, Ling HF. Combinatorial optimization problem reduction and algorithm derivation. Journal of Software, 2011,22(9):1985?1993. https://www.wendangku.net/doc/fa998066.html,/1000-9825/3948.htm Abstract: A unified algebraic model is used to represent optimization problems, which uses a transformational approach that starts from an initial problem specification and reduces it into sub-problems with less complexity. The model then constructs the problem reduction graph (PRG) describing the recurrence relations between the problem, and derives an algorithm with its correctness proof hand-in-hand. A prototype system that implements the formal algorithm development process mechanically is also designed. This approach significantly improves the automation of algorithmic program design and helps to understand inherent characteristics of the algorithms. Key words: combinatorial optimization problem; problem reduction; algorithm derivation; PAR (partition-and- recur); correctness proof 摘要: 针对组合优化类问题定义了代数结构模型,从问题的形式规约出发,通过一阶谓词和量词演算将问题逐 步简约为搜索空间更小、复杂度更低的子问题,根据问题的简约关系推导出求解算法,并在构造算法的同时也证明 了算法的正确性.开发了原型系统以支持上述形式化的开发过程.这种算法推演技术能够显著提高算法程序设计的 自动化水平,而问题简约的思想也更有利于对算法本质特征的理解. 关键词: 组合优化问题;问题简约;算法推演;PAR(partition-and-recur);正确性证明 中图法分类号: TP301文献标识码: A 组合优化问题是指在离散有限的数学结构中和给定的约束条件下寻找目标函数最优值的问题,它是组合 数学、运筹学和理论计算机科学中长期研究的重要问题之一.传统的组合优化算法设计策略(如动态规划、贪 心、回溯等)有着各自不同的适用范围,而且缺乏策略选择的有效标准[1],因而极大地限制了算法开发的形式化 ?基金项目: 国家自然科学基金(61105073, 60773054); 科技部国际科学技术合作项目(2008DFA11940) 收稿时间: 2009-09-25; 定稿时间: 2010-09-06