【精品】优化问题的数学模型

《【精品】优化问题的数学模型》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一.管理科学的定义管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策制定的一门学科.（1）定量因素（2）科学的方法（3）辅助决策制定二•用管理科学的方法解决问题的基本步骤.（1）提出问题，并根据需要收录有关数据信息。管理科学工作者向管理者咨询、鉴别所要考虑的问题以确定合理的目标，然后根据要求收集一些关键数据，并对数据作相应的分析。（2）建立模型，引入决策变量，确定目标函数（约朿条件）。建模过程是一项创造性的工作，在处理实际问题时，一般没有一个唯一正确的模型，而是有多种不同的方案。建模是一个演进过程，从一个初始模型往往需要不断的完善渐渐演化成一个完整的数学模型

2、。（3）从模型中形成一个对问题求解的算法。要在计算机上运行数学程序对模型进行求解，一般情况下能找到刈•模型求解的标准软件。例如，对线性规划问题已有Excel>Cplex、Lingo等标准软件求解。有时要自己编写程序。（4）测试模型并在必要时修止。在模型求解后，需要对模型进行检验，以保证该模型能准确反映实际问题，需要检验模型提供的解是否合理，所有主要相关因素是否已考虑，当有些条件变化吋，解如何变化等。（5）应用模型分析问题以及提出管理建议。对模型求解并分析后，将相应的最优方案提交给管理者，由管理者做出决策。管理科学工作者并不作管理决策，其研究只是对涉及的问题进行分析并向管理者提出

3、建议。管理者还要考虑管理科学以外的众多因素才能做出决策。（6）帮助实施管理决策。建议被管理者采纳以后，一旦做出管理决策一般要求帮助监督决策方案的实施。新问题，新模型，新算法，新应用.三•优化问题的数学模型max(min)Z=,花，…，兀)gj（兀1，兀2，・・・£）5。丿=1,2,・・・加由于是非线性函数时，此问题是非线性优化问题，求解较复杂。我们主要讨论线性优化问题，常见的形式：混合整数规划maxZ=CX+hYAX+GY0取整数y>o其中AwGn“也如Cghg，不失一般性，我们假定C,h,A,G,b都是整数矩阵。当p=0时，（1）为纯整数规划，当〃=0时，（1）

4、为线性规划。下图列出若干常见线性优化问题之间的关系，见FigureL1Plgurw1.13.1.1Setpacking与Nodepacking(Setpacking)模型:maxZ=CXMX<1其中A是元素为o或1的矩阵「{0,1}(Nodepacking)模型：maxZ=CXJAX<1其中A是元素为()或1的矩阵，且每行恰有两个1(没有遼复行)

5、xe{0,l}显然,Nodepacking是Setpacking特例。对于Setpacking问题，事实上是一个独立集问题，例如ri00011100我们按下列方式构造网络：每列对应于一个顶点，◎对应于点丿，所以有四101070111个

6、点，按行检查，对任意，若au=aik=,则在点/与点力之间有一条边相连。构成如图网络以后，可以看出约束AX51相当于确定顶点使得被确定的顶点之间没有边相连；而冃标系数C相当于点的权重向量问题变为如何在网络确定若干个（独立的）顶点使得总权重最大的问题。而Nodepacking问题中，A是0—1矩阵（每行只有两个元素是1）,事实上是一个网络的边点关联矩阵，最终也可以化为与上问题类似的问题。Figure1.23.2背包问题对于0・1背包问题（Knapsack）—般模式:maxZ=CXAX

7、+6OX3x,+7x2+20x3

8、二部图的匹配问题。（注:二部图是指可以把图中顶点分为两个部分,每一部分之I'可没有连接）-般模型maxZ=^CcX。eeE工Xe