下载文档原格式
数学建模第二讲简单的优化模型数学建模是利用数学方法对实际问题进行建模、分析和求解的过程。
在实际问题中，常常需要针对一些指标进行优化，以达到最优的效果。
本讲将介绍一些简单的优化模型。
一、线性规划模型线性规划是一种重要的数学优化方法，广泛应用于工程、经济、管理等领域。
其数学模型可以表示为：\begin{aligned}&\text{max} \quad c^Tx \\&\text{s.t.} \quad Ax \leq b, \quad x \geq 0\end{aligned}\]其中，$x$为决策变量，$c$为目标函数系数，$A$为约束条件系数矩阵，$b$为约束条件右端向量。
线性规划模型指的是目标函数和约束条件都是线性的情况。
通过线性规划模型，可以求解出使得目标函数取得最大（或最小）值时的决策变量取值。
二、非线性规划模型非线性规划模型指的是目标函数或约束条件中存在非线性部分的情况。
非线性规划模型相对于线性规划模型更为复杂，但在实际问题中更为常见。
对于非线性规划问题，通常采用数值优化方法进行求解，如梯度下降法、牛顿法等。
这些方法通过迭代的方式逐步靠近最优解。
三、整数规划模型整数规划模型是指决策变量必须为整数的规划模型。
整数规划在实际问题中应用广泛，如物流配送问题、工程调度问题等。
整数规划模型通常难以求解，因为整数规划问题是一个NP难问题。
针对整数规划问题，常用的求解方法有枚举法、分支定界法、遗传算法等。
四、动态规划模型动态规划模型是指将问题划分为子问题，并通过求解子问题最优解来求解原问题最优解的方法。
动态规划通常用于求解具有重叠子问题和最优子结构性质的问题。
动态规划模型具有递推性质，通过递归或迭代的方式求解子问题的最优解，并保存中间结果，以提高求解效率。
五、模拟退火模型模拟退火是一种用来求解组合优化问题的随机优化算法。
模拟退火算法基于固体退火过程的模拟，通过温度的控制和随机跳出来避免陷入局部最优解。
最优化问题的建模与解法最优化问题（optimization problem）是指在一组可能的解中寻找最优解的问题。
最优化问题在实际生活中有广泛的应用，例如在工程、经济学、物流等领域中，我们经常需要通过数学模型来描述问题，并利用优化算法来求解最优解。
本文将介绍最优化问题的建模和解法，并通过几个实例来说明具体的应用。
一、最优化问题的数学建模最优化问题的数学建模包括目标函数的定义、约束条件的确定以及变量范围的设定。
1. 目标函数的定义目标函数是一个表达式，用来衡量问题的解的优劣。
例如，对于一个最大化问题，我们可以定义目标函数为：max f(x)其中，f(x)是一个关于变量x的函数，表示问题的解与x的关系。
类似地，对于最小化问题，我们可以定义目标函数为：min f(x)2. 约束条件的确定约束条件是对变量x的一组限制条件，用来定义问题的可行解集合。
约束条件可以是等式或不等式，通常表示为：g(x) ≤ 0h(x) = 0其中，g(x)和h(x)分别表示不等式约束和等式约束。
最优化问题的解必须满足所有的约束条件，即：g(x) ≤ 0, h(x) = 03. 变量范围的设定对于某些变量，可能需要限定其取值的范围。
例如，对于一个实数变量x，可能需要设定其上下界限。
变量范围的设定可以通过添加额外的不等式约束来实现。
二、最优化问题的解法最优化问题的解法包括数学方法和计算方法两种，常见的数学方法有最优性条件、拉格朗日乘子法等，而计算方法主要是通过计算机来求解。
1. 数学方法数学方法是通过数学分析来求解最优化问题。
其中，常见的数学方法包括：（1）最优性条件：例如，对于一些特殊的最优化问题，可以通过最优性条件来判断最优解的存在性和性质。
最优性条件包括可导条件、凸性条件等。
（2）拉格朗日乘子法：对于带有约束条件的最优化问题，可以通过拉格朗日乘子法将原问题转化为无约束最优化问题，从而求解最优解。
2. 计算方法计算方法是通过计算机来求解最优化问题。
数学建模优化问题的求解方法
数学建模优化问题的求解方法有很多。
下面列举几种常见的方法：
1. 数学规划方法：包括线性规划、整数规划、非线性规划、动态规划等。
这些方法通过数学模型和约束条件来描述问题，并通过寻找最优解来优化问题。
2. 图论方法：将问题抽象成图或网络，并利用图论算法来求解最优解。
常见的算法有最短路径算法、最小生成树算法、最大流算法等。
3. 近似算法：对于复杂的优化问题，往往很难找到精确的最优解。
近似算法通过寻找接近最优解的解来近似优化问题。
常见的近似算法有贪心算法、近邻算法、模拟退火算法等。
4. 遗传算法：模拟生物进化的过程，通过选择、交叉和变异等操作来搜索问题的解空间，并逐步优化解。
遗传算法适用于复杂问题和无法直接求解的问题。
5. 物理方法：将优化问题转化为物理模型，利用物理规律求解。
比如蚁群算法模拟蚂蚁找食物的行为，粒子群算法模拟鸟群觅食的行为等。
以上只是数学建模优化问题求解方法的几种常见方法，实际问题求解时要根据问题的特点选择适合的方法，并结合领域知识和实际情况进行调整和优化。
多目标优化数学模型是指在优化问题中存在多个目标函数的情况下，通过数学建模来求解最优解。
多目标优化问题可以形式化为如下形式：
$$
\begin{align*}
\text{minimize} \quad f_1(x) \\
\text{subject to} \quad f_2(x) \leq 0 \\
\quad f_3(x) \leq 0 \\
\quad \vdots \\
\quad f_m(x) \leq 0 \\
\end{align*}
$$
其中，$x$是决策变量，$f_1(x), f_2(x), \ldots, f_m(x)$是目标函数，$m$是目标函数的个数。
在多目标优化中，通常存在多个不同的最优解，这些最优解构成了一个被称为Pareto前沿（Pareto front）的集合。
Pareto前沿是指在所有满足约束条件的解中，无法通过改变一个目标函数的值而使其他目标函数的值变得更好的解。
求解多目标优化问题的常用方法包括遗传算法、粒子群算法、模拟退
火算法等。
这些算法通过在解空间中搜索，逐步逼近Pareto前沿，从而得到一组近似最优解。
多目标优化数学模型的应用非常广泛，例如在工程设计中，可以通过多目标优化来平衡不同的设计目标，如成本、性能、可靠性等；在金融投资中，可以通过多目标优化来平衡风险和收益等。
数学建模中的多目标优化问题在数学建模中，多目标优化问题是一个重要且具有挑战性的问题。
在实际应用中，我们常常面临的是多个目标之间的矛盾与权衡，因此需要找到一个平衡点来满足各个目标的需求。
本文将介绍多目标优化问题的定义、解决方法以及应用案例。
第一部分：多目标优化问题的定义多目标优化问题是指在给定的约束条件下，寻找多个目标函数的最优解的问题。
常见的形式可以表示为：最小化/最大化 f1(x), f2(x), ..., fn(x)其中，fi(x)表示第i个目标函数，x表示决策变量。
多目标优化问题与单目标优化问题的不同之处在于，单目标问题只需考虑一个目标函数，而多目标问题需要同时考虑多个目标函数。
第二部分：多目标优化问题的解决方法在解决多目标优化问题时，常用的方法有以下几种：1. 加权求和法（Weighted Sum Method）：将多个目标函数加权求和，转化为单目标函数进行求解。
具体地，可以通过设置不同的权重系数，使得不同目标函数在求解中的重要性得到体现。
2. Pareto优化法（Pareto Optimization）：Pareto优化法基于Pareto最优解的概念，即同时满足所有约束条件下，无法改善任何一个目标函数而不损害其他目标函数的解集。
通过构建Pareto最优解集，可以帮助决策者在多个解中进行选择。
3. 遗传算法（Genetic Algorithm）：遗传算法是一种基于生物进化原理的优化算法，通过模拟自然选择、交叉和变异等过程来搜索最优解。
在多目标优化问题中，遗传算法通过维护一个种群中的多个个体，以逐步进化出Pareto最优解集。
4. 粒子群优化算法（Particle Swarm Optimization）：粒子群优化算法是一种模拟鸟群觅食的行为进行优化的算法。
在多目标优化问题中，粒子群优化算法通过在解空间中搜索多个粒子，通过粒子之间的合作与竞争，逐步逼近Pareto最优解。
第三部分：多目标优化问题的应用案例多目标优化问题在各个领域都有广泛的应用。
数学建模经典问题
数学建模是一种将实际问题转化为数学问题，并运用数学工具解决实际问题的方法。
在数学建模的过程中，我们需要面对各种各样的问题，其中一些问题已经被广泛研究并被视为经典问题。
本文将介绍几个数学建模中的经典问题。
1.旅行商问题
旅行商问题是一个经典的路线优化问题。
假设有一个旅行商要拜访n个城市，每个城市之间的距离是已知的。
旅行商需要找到一条回路，使得他可以在每个城市停留一次，并返回起点城市，同时旅行路程最短。
这个问题是一个NP难问题，可以用动态规划、分支限界等方法求解。
2.背包问题
背包问题是一个经典的优化问题。
假设有一个背包，它的容量为C，有n个物品，每个物品有一个重量和一个价值。
旅行商需要在这些物品中选择一些放入背包，使得背包的重量不超过C，同时所选物品的总价值最大。
这个问题也是一个NP难问题，可以用动态规划、贪心算法等方法求解。
3.热传导方程
热传导方程是一个经典的偏微分方程，描述了物体内部温度的变化。
它可以用来模拟热传导过程，例如烤面包、冷却热水等。
热传导方程可以用有限元方法、有限差分方法等数值方法求解。
4.计算几何
计算几何是一个经典的数学分支，研究几何问题的计算方法。
例如，给定n个点，如何寻找一个最小的圆，使得这n个点都在圆内或圆上。
这个问题可以用Welzl算法等方法求解。
这些经典问题在数学建模中经常出现，它们不仅有理论研究的价值，而且对于实际应用也有着很大的意义。
在数学建模的过程中，我们应该灵活运用各种数学工具，以便更好地解决实际问题。
数学建模中的优化算法应用实例数学建模是一种有效的解决实际问题的方法，而优化算法则是数学建模中不可或缺的工具之一。
优化算法能够寻找最优解，最大化或最小化某个目标函数，有着广泛的应用领域。
本文将介绍数学建模中的几个优化算法应用实例，以展示其在实际问题中的作用和价值。
一、车辆路径规划优化在实际的物流配送领域中，如何合理地规划车辆路径，使得总运输成本最小、配送效率最高，是一个关键问题。
优化算法在车辆路径规划中起到了至关重要的作用。
通过建立数学模型，基于某个目标函数（如最小化总运输成本），可以采用遗传算法、模拟退火算法等优化算法，快速找到最优解，从而提高物流配送的效率和效益。
二、资源分配优化在资源分配问题中，常常需要考虑到各种限制条件，如最大化利润、最小化生产成本等。
优化算法能够帮助决策者在有限的资源下做出最优的分配决策。
例如，对于生产调度问题，可以利用线性规划等优化算法，将生产计划与订单需求进行匹配，使得生产成本最小化、交货期最短化。
三、供应链优化供应链管理中的优化问题也是实际应用中的重点关注点之一。
通过数学建模和优化算法，可以实现供应链中物流、库存、订单等多个环节的优化。
例如，在供应链网络设计中，可以使用整数规划算法来寻找最优仓储和配送中心的位置，从而降低总运输成本；在需求预测和库存管理中，可以利用模拟退火算法等优化算法，提高供应链的响应速度和利润率。
四、机器学习模型参数优化在机器学习领域，模型参数的选择对模型的性能和准确性有着重要的影响。
通过建立数学模型，可以将模型参数优化问题转化为参数寻优问题，进而采用优化算法求得最优参数。
例如，在神经网络的训练过程中，可以利用遗传算法、粒子群优化算法等进行参数调整，提高模型的预测准确性和泛化能力。
五、能源系统优化能源系统的优化是实现可持续发展的重要方向之一。
通过优化算法，可以针对能源系统进行容量规划、发电机组简化和能源分配等问题的优化。
例如，在微电网系统优化中，可以利用整数规划等算法，实现可再生能源与传统能源的协同供电，最大化清洁能源的利用率。
1、高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳万元，可使用的金属板有500t，劳动力有300人/月，机器有100台/月，此外，不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号为100万元，中号为150万元，大号为200万元，现在要制定一个生产计划，使获得的利润为最大，max=4*x1+5*x2+6*x3-100*y1-150*y2-200*y3;2*x1+4*x2+8*x3<=500;2*x1+3*x2+4*x3<=300;1*x1+2*x2+3*x3<=100;@bin(y1);@bin(y2);@bin(y3);y1+y2+y3>=1;Global optimal solution found.Objective value: 300.0000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced CostX1 100.0000 0.000000X2 0.000000 3.000000X3 0.000000 6.000000Y1 1.000000 100.0000Y2 0.000000 150.0000Y3 0.000000 200.0000Row Slack or Surplus Dual Price1 300.0000 1.0000002 300.0000 0.0000003 100.0000 0.0000004 0.000000 4.0000005 0.000000 0.0000002、安排4个人去做4项不同的工作,每个工人完成各项工作所消耗的时间（单位：（2）如果在（1）中在增加一项工作E，甲、乙、丙、丁四人完成工作E的时间分别为17,20,15,16分钟，那么应指派这四人干哪四项工作，使得这四人总的消耗时间为最少？min=20*x11+19*x12+20*x13+28*x14+18*x21+24*x22+27*x23+20*x24+26*x31+16 *x32+15*x33+18*x34+17*x41+20*x42+24*x43+19*x44;x11+x12+x13+x14=1;x21+x22+x23+x24=1;x31+x32+x33+x34=1;x41+x42+x43+x44=1;x11+x21+x31+x41=1;x12+x22+x32+x42=1;x13+x23+x33+x43=1;x14+x24+x34+x44=1;@bin(x11);@bin(x12);@bin(x13);@bin(x14);@bin(x21);@bin(x22);@bin(x23);@bin(x24);@bin(x31);@bin(x32);@bin(x33);@bin(x34);@bin(x41);@bin(x42);@bin(x43);@bin(x44);Global optimal solution found.Objective value: 71.00000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced CostX11 0.000000 20.00000X12 1.000000 19.00000X13 0.000000 20.00000X14 0.000000 28.00000X21 0.000000 18.00000X22 0.000000 24.00000X23 0.000000 27.00000X24 1.000000 20.00000X31 0.000000 26.00000X32 0.000000 16.00000X33 1.000000 15.00000X34 0.000000 18.00000X41 1.000000 17.00000X42 0.000000 20.00000X43 0.000000 24.00000X44 0.000000 19.00000Row Slack or Surplus Dual Price1 71.00000 -1.0000002 0.000000 0.0000003 0.000000 0.0000004 0.000000 0.0000005 0.000000 0.0000006 0.000000 0.0000007 0.000000 0.0000008 0.000000 0.0000009 0.000000 0.000000min=20*x11+19*x12+20*x13+28*x14+17*x15+18*x21+24*x22+27*x23+20*x24+20 *x25+26*x31+16*x32+15*x33+18*x34+15*x35+17*x41+20*x42+24*x43+19*x44+1 6*x45;x11+x12+x13+x14+x15=1;x21+x22+x23+x24+x25=1;x31+x32+x33+x34+x35=1;x41+x42+x43+x44+x45=1;x11+x21+x31+x41<=1;x12+x22+x32+x42<=1;x13+x23+x33+x43<=1;x14+x24+x34+x44<=1;x15+x25+x35+x45<=1;@bin(x11);@bin(x12);@bin(x13);@bin(x14);@bin(x15);@bin(x21);@bin(x22);@bin(x23);@bin(x24);@bin(x25);@bin(x31);@bin(x32);@bin(x33);@bin(x34);@bin(x35);@bin(x41);@bin(x42);@bin(x43);@bin(x44);@bin(x45);Objective value: 68.00000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced Cost X11 0.000000 20.00000 X12 1.000000 19.00000 X13 0.000000 20.00000 X14 0.000000 28.00000 X15 0.000000 17.00000 X21 1.000000 18.00000 X22 0.000000 24.00000 X23 0.000000 27.00000 X24 0.000000 20.00000 X25 0.000000 20.00000X31 0.000000 26.00000X32 0.000000 16.00000X33 1.000000 15.00000X34 0.000000 18.00000X35 0.000000 15.00000X41 0.000000 17.00000X42 0.000000 20.00000X43 0.000000 24.00000X44 0.000000 19.00000X45 1.000000 16.00000Row Slack or Surplus Dual Price1 68.00000 -1.0000002 0.000000 0.0000003 0.000000 0.0000004 0.000000 0.0000005 0.000000 0.0000006 0.000000 0.0000007 0.000000 0.0000008 0.000000 0.0000009 1.000000 0.00000010 0.000000 0.0000003、一个公司考虑到北京、上海、广州和武汉四个城市设立库房，这些库房负责向华北、华中、华南三个地区供货，每个库房每月可处理货物1000件。
几个优化问题的数学建模一、一个开放式基金投资问题6、模型的评价模型的主要优点是采用较为成熟的数学理论建立模型，利用数学软件计算，可信度比较高，便于推广。
主要缺点是建立的模型是确定的而不是更符合实际情况的随机型模型。
二、结合人员分配的生产规划问题1、问题某公司要对四种产品（P1，P2，P3，P4）在五条生产线（L1到L5）上的生产进行规划。
产品P1和P4的单位纯利润为7元，产品P2的单位纯利润为8元，产品P3的单位纯利润为9元。
在规划期内这五条生产线各自可以进行生产的时间长度各不相同。
L1到L5的最大可用生产时间分别为4500小时，5000小时，4500小时，1500小时和2500小时。
表1列出了在每条生产线上生产每种产品一个单位所需要的时间。
（1）、假设生产是流水线作业，产品P1到P4各应生产多少才能使总利润最大？（2）、如果在生产过程中允许在生产线之间进行人员转移（从而使工时也相应转移），如表2所示，则最大利润是多少？应转移多少个工时，如何转移？（3）、如果生产不是流水线作业，模型应如何修改？表1 单位生产时间表2 可以进行的人员转移2、假设（1）每条生产线可生产各种产品；（2）每个生产人员的工作效率相同，且熟练各条生产线的操作，可在各条生产线之间转移。
3、建模3.1、问题(1) 设每种产品必须经过5条生产线才能生产出来，产品P i 的产量为x i ,单位纯利润为r i ,在生产线L j 上的单位生产时间为d ij 。
生产线L j 的可用总工时数为c j ,则可得模型1：max 41i =∑r i x is.t.41i =∑d ij x i ≤c j ，j=1，2，3，4，5x i ≥0，i=1，2，3，43.2、问题(2) 设y jk 为从生产线L j 转移到生产线L k 的工时数，生产线L j 的最大可转移总工时数为b j ,j,k=1,2,3,4,5,j ≠k ，则可得模型2：max 41i =∑r i x is.t.3.3、问题(3) 设每种产品只需在任意一条生产线上即可生产出来，产品P i在生产线L j 上的产量为x ij , i=1，2，3，4；j=1，2，3，4，5，则只需在上述两个模型中，将目标函数修改为max 41i =∑51j =∑r i x ij ,将41i =∑d ij x i 修改为41i =∑d ij x ij ,其余不变。
4、求解利用Lindo 软件包，根据题目所给数据编程求解线性规划模型1，2，得如下结果。
4.1、模型1的结果 最大利润为18882.97元，产品P 1，P 2的产量分别为1542.55，1010.64，其他两种产品不生产，只有生产线L 3和L 5用尽了所有可用工时。
这表明可通过转移工时来增加利润。
4.2、模型2的结果 最大利润为23431.10元，产品P 1，P 2，P 3，P 4 的产量分别为 702.35,942.82,554.83,854.84.L 1上总计用了4100个工时，有400个工时转移到L 4上；L 2上用了3840个工时，有800个工时转移到L 5上；L 3上用了4300个工时，有200个工时转移到L 4上；L 4上用完了原有工时，还用了转移来的600个工时；L 5上用完了原有工时，还用了转移来的800个工时。
5、进一步讨论 若假设x i ∈N ，i=1,2,3,4，则模型为整数线性规划，可类似求解。
41i =∑d ij x i ≤c j +51k =∑y kj -51k =∑y jk ,j=1，2，3，4，551k =∑y jk ≤b j ，j=1，2，3，4,5y 15，y 21,y 24,y 35,y 41,y 42,y 43,y 54=0y jj =0,j=1,2,3,4,5x i ≥0，i=1，2，3，4y jk ≥0,j,k=1,2,3,4,5三、网络最大流问题1、问题 在单源单汇具有容量上限的网络),,(C E V N =中求从源到汇的流量最大的可行流。
2、模型max )(v f∑∑≠=j t s i k ki ij v v v f f ,,∑∑==j kkt sj f v f f )( E ∈≤≤j i ij ij v v c f ,03、算法（1）Ford-Fulkerson 算法，计算复杂性与容量有关，而与点数和边数无关； （2）Edmonds-Karp 算法，计算复杂性为),(2n m O 其中V =n ，E m =； （3）单纯形法，非多项式算法，可利用Lindo 、Lingo 或Matlab 软件编程计算。
4、应用 （1）最小割集； （2）最小流； （3）多端最大流； （4）增益流；（5）点具有容量的最小流；（6）最小费用流，其模型只要在最大流模型中将目标改为∑∈Ev v ij ijj i f bmin即可得。
5、进一步讨论 约束条件 E ∈≤≤j i ij ij v v c f ,0中的容量值若为整数，求解上述线性规划，必得整数最大流，即各条边上的流量为整数。
四、图的独立集、覆盖集与支配集问题1、匹配（边独立集）（1）问题 求图中边数最多的不相邻边之集，即最大匹配。
（2）算法1）求非偶图最大匹配的“开花”算法，计算复杂性为)(3n O 。
或引入0-1变量ij x ，当iv 与j v 配对时，1;ij x =否则，0,ij x =建立如下模型，利用软件编程计算。
max ij ijx ∑∑()1,1,2,,..01,1,2,,,j i ij v N v ij x i n s t x i j n i j∈⎧≤=⎪⎨⎪==≠⎩∑或，2）求偶图),,(E Y X G =最大匹配的匈牙利算法，计算复杂性为)(mn O 。
或引入0-1变量ij x ，当X x i ∈与Y y j ∈配对时，1=ij x ；否则，0=ij x ，建立如下模型，利用软件编程计算。
∑∑jijixmax∑∈≤j i ij X x x ,1 ∑∈≤ii ij Y y x ,1 10或=ij x（3）应用1）问题 求加权偶图中权和最大或最小的最大匹配，即最优匹配。
2）模型 若求权和最大的最优匹配，则其模型只要在上述模型中将目标改为∑∑jijij ixw max 即可得，其中，当E ∈j i y x 时，)(y x w w i ij =,否则，0w =ij ；若求权和最小的最优匹配，则其模型只要在上述模型中将目标改为∑∑'jijij ixw max即可得，其中当E ∈j i y x 时，ij ijw w w -='，否则，0=ij w ，{}ij w w max =。
3）算法 a)kuhn-Munkras 算法，计算复杂性为)(4n O ；b ）利用软件编程计算。
（4）推广 一人承担多项工作或一项工作由多人承担的，指派问题，只要将上述模型中的约束条件适当修改即可。
2、边覆盖集（1）问题 求图中边数最少的覆盖所有点的边之集，即最小边覆盖集。
（2）算法 通过最大匹配求得。
或引入0-1变量ij x ，当i j v v 属于边覆盖集时，1;ij x =否则，0,ij x =建立如下模型，利用软件编程计算。
1.min ij ijx ∑∑1,1,2,,..01,1,2,,,ij j ij x i n s t x i j n i j⎧≥=⎪⎨⎪==≠⎩∑或，3、点覆盖集（1）问题 求图中点数最少的覆盖所有边的点之集，即最小点覆盖集。
（2）算法 求所有极小点覆盖集的逻辑算法：∏∏=∈+ni v N v ij v v i j 1)((）。
或引入0-1变量ix ，当iv 属于（点）覆盖集时，1;i x =否则0i x =，建立如下模型，利用软件编程计算。
min i ix ∑1,,1..011,2,,,i j i j i x x v v E i j n s t x i n +≥∈≤<≤⎧⎪⎨==⎪⎩或，4、点独立集（1）问题 求图中点数最多的不相邻点之集，即最大点独之集。
（2）算法 求出最小点覆盖集，其补集即为最大点独立集。
或引入0-1变量i x ，当i v 属于（点）独立集时，1i x =；否则；0i x =，建立如下模型，利用软件编程计算。
max i ix ∑()1,1,2,,..011,2,,j i i j v N v i x x i ns t x i n∈⎧+≤=⎪⎨⎪==⎩∑或，5、支配集（1）问题 求点数最少的点之集，使图中每个点或属于该点集，或与该点集中至少一点相邻，即最小支配集。
（2）算法 求所有极小支配集的逻辑算法：∏=∑∈+ni iiv N j v j v v 1)((）。
或引入0-1变量i x ，当i v 属于支配集时，1i x =；否则；0i x =，建立如下模型，利用软件编程计算。
min i ix ∑()1,1,2,,..011,2,,,j i i j v N v i x x i ns t x i n ∈⎧+≥=⎪⎨⎪==⎩∑或，五、中国邮路问题（CPP ）1、问题 求Euler 图中的Euler 回路。
2、算法 Fleury 算法，计算复杂性为)(m O 。
3、应用（1）问题 在加权连通图中求经过每条边至少一次的权和最小的回路，即中国邮路。
（2）模型 设ij x 为经过边j i v v 的次数，则得如下模型。
∑E∈j i v v ijijxw max∑∑E ∈E ∈∈=j i ik v v i v v ki ij V v x x ,E ∈∈≤j i ij v v N x ,1(3)算法 1）奇偶点图上作业法；2）最小权匹配算法，计算复杂性为)(3n O 4、推广 多邮递员中国邮路问题（CPP k -）六、旅行推销商问题（TSP ）1、问题 求Hamilton 图中的Hamilton 回路。
2、算法 DFS 法，计算复杂性为)!(n O3、应用（1）问题 在加权连通图中求经过每个点至少一次的权和最小的回路，即推销商回路。
（2）模型 先将一般加权连通图转化成一个等价的加权完全图，设当从i v 到j v 时，1=ij x ，否则，0=ij x ，则得如下模型。
∑∑==n i nj ijij xw 11min∑===njijnix1,,1,1∑===niijnjx1,,1,1 1,,2-=nkniikxxxki ii ii i k1,,,1113221=-≤+++=ijx或1，jinji≠=,,,1,（3）算法1）分枝定界法，非多项式算法；2）最小生成树法；3）代换法；4）插入法；5）最近邻法；6）神经网络法；7）模拟退火法；8）蚂蚁算法，2）—8）均为近似算法。
4、推广多旅行推销商问题)(TSPk-七、图的着色问题1、点着色（1）问题求给图的点着色，且使邻点异色的最少颜色数。
