优化问题的数学模型VIP免费

1/13一.管理科学的定义管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策制定的一门学科.(1)定量因素(2)科学的方法(3)辅助决策制定二.用管理科学的方法解决问题的基本步骤.（1）提出问题，并根据需要收录有关数据信息。管理科学工作者向管理者咨询、鉴别所要考虑的问题以确定合理的目标，然后根据要求收集一些关键数据，并对数据作相应的分析。（2）建立模型，引入决策变量，确定目标函数（约束条件）。建模过程是一项创造性的工作，在处理实际问题时，一般没有一个唯一正确的模型，而是有多种不同的方案。建模是一个演进过程，从一个初始模型往往需要不断的完善渐渐演化成一个完整的数学模型。（3）从模型中形成一个对问题求解的算法。要在计算机上运行数学程序对模型进行求解，一般情况下能找到对模型求解的标准软件。例如，对线性规划问题已有Excel、Cplex、Lingo等标准软件求解。有时要自己编写程序。（4）测试模型并在必要时修正。在模型求解后，需要对模型进行检验，以保证该模型能准确反映实际问题，需要检验模型提供的解是否合理，所有主要相关因素是否已考虑，当有些条件变化时，解如何变化等。（5）应用模型分析问题以及提出管理建议。对模型求解并分析后，将相应的最优方案提交给管理者，由管理者做出决策。管理科学工作者并不作管理决策，其研究只是对涉及的问题进行分析并向管理者提出建议。管理者还要考虑管理科学以外的众多因素才能做出决策。（6）帮助实施管理决策。建议被管理者采纳以后，一旦做出管理决策一般要求帮助监督决策方案的实施。新问题,新模型,新算法,新应用.三.优化问题的数学模型1212max(min)(,,,)(,,)0..1,2,njnZfxxxgxxxstjm由于,jfg是非线性函数时，此问题是非线性优化问题,求解较复杂。我们主要讨论线性优化问题，常见的形式：混合整数规划（1）max00ZCXhYAXGYbXY取整数其中111,,,,mnmpmnpAGbCh，不失一般性，我们假定,,,,ChAGb都是整数矩阵。当0p时，（1）为纯整数规划，当0n时，（1）为线性规划。2/13下图列出若干常见线性优化问题之间的关系，见Figure1.1Mixed-integerprogrammmingPure-integerprogrammingMixed0-1programminglinearprogrammmingIntegerknapsack0-1programmingUncapacitatedfacilitylocationFixed-changenetworkflow0-1knapsackSetcoveringSetpackingLinearnetworkflowTravelingsalesmanNodepackingMatchingTransportationShortestpathAssignmentFigure1.13.1．1Setpacking与Nodepacking（Setpacking）模型：max1{0,1}ZCXAXx其中A是元素为0或1的矩阵（Nodepacking）模型：max1{0,1}ZCXAXx其中A是元素为0或1的矩阵，且每行恰有两个1（没有重复行）显然，Nodepacking是Setpacking特例。对于Setpacking问题，事实上是一个独立集问题，例如1000110010100111A我们按下列方式构造网络：每列对应于一个顶点，jx对应于点j，所以有四3/13个点，按行检查，对任意i若1ilikaa，则在点l与点h之间有一条边相连。构成如图网络以后，可以看出约束1AX相当于确定顶点使得被确定的顶点之间没有边相连；而目标系数C相当于点的权重向量问题变为如何在网络确定若干个（独立的）顶点使得总权重最大的问题。而Nodepacking问题中，A是0－1矩阵（每行只有两个元素是1），事实上是一个网络的边点关联矩阵，最终也可以化为与上问题类似的问题。1234Figure1.23.2背包问题对于0-1背包问题（Knapsack）一般模式：max..{0,1}ZCXAXbstx事实上，它的求解很困难，我们不妨举个非常简单的例子。1231231max92860720..{0,1}iZxxxxxxbstx1x的系数比1：9，2x的系数比1：4，3x系数比为1：3，从资源分配问题角度应依次考虑123,,xxx，而事实上，最优解非常依赖于右端项1b。当17b时，最优解为（1，0，0）；当178b时，最优解为（0，1，0）；当1820b时，最优解为（1，1，0）；当12021b时，最优解为（0，0，1）；没有体现1x优先，不同于线性规划。3．3Matching（赋权图）匹配问题在网络中，一个匹配是指一些边集使得没有两边相关联。最大赋权匹配问题，寻找一个匹配使得总权最大。最大基数匹配问题，（假定每条边权为1），找出边数最多的匹配。指派问...