2026年数学应用数学优化试题及答案

2026年数学应用数学优化试题及答案一、选择题（30分）1.下列哪个不是线性规划的标准形式？A.目标函数为最大化B.所有约束条件为等式C.所有变量非负D.目标函数为线性函数2.在单纯形法中，基变量的个数等于：A.变量的总数B.约束条件的个数C.决策变量的个数D.松弛变量的个数3.对于凸规划问题，下列说法正确的是：A.局部最优解一定是全局最优解B.可行域一定是凸集C.目标函数一定是凸函数D.以上都正确4.动态规划解决多阶段决策问题的核心思想是：A.贪心算法B.分治策略C.最优性原理D.回溯法5.下列哪种方法不适合求解非线性规划问题？A.梯度法B.内点法C.单纯形法D.拟牛顿法6.在整数规划中，下列哪种情况会导致"割平面法"失效？A.问题无可行解B.问题有无界解C.问题有多重最优解D.问题为纯整数规划7.下列哪种算法属于启发式算法？A.单纯形法B.梯度下降法C.遗传算法D.内点法8.在图论中，求解最短路径问题的常用算法是：A.Prim算法B.Dijkstra算法C.Kruskal算法D.Ford-Fulkerson算法9.对于多目标优化问题，下列说法正确的是：A.一定存在唯一的最优解B.Pareto最优解集一定是唯一的C.Pareto最优解之间没有优劣之分D.所有目标函数可以线性组合成一个单目标函数10.下列哪种优化方法不需要计算目标函数的梯度？A.梯度下降法B.牛顿法C.遗传算法D.共轭梯度法11.在非线性规划中，KKT条件是：A.凸规划的必要条件B.凸规划的充分条件C.一般非线性规划的必要条件D.一般非线性规划的充分条件12.下列哪种方法不适合求解大规模线性规划问题？A.单纯形法B.内点法C.列生成法D.分支定界法13.在随机优化中，下列哪种方法用于处理期望值模型？A.蒙特卡洛模拟B.机会约束规划C.两阶段随机规划D.样本平均近似14.对于0-1整数规划问题，下列哪种方法最有效？A.图论方法B.动态规划C.分支定界法D.割平面法15.在优化算法中，收敛速度最快的通常是：A.梯度下降法B.牛顿法C.共轭梯度法D.遗传算法二、填空题（20分）1.线性规划问题的一般形式包括目标函数和约束条件，其中目标函数是______函数，约束条件是______函数。2.在单纯形法中，检验数表示的是______的变化率。3.对偶线性规划中，原问题的______对应对偶问题的______。4.动态规划的基本方程通常表示为______。5.凸函数的定义是：对于任意x1,x2∈D和λ∈[0,1]，有f(λx1+(1-λ)x2)______λf(x1)+(1-λ)f(x2)。6.在非线性规划中，无约束优化问题的最优解满足的一阶必要条件是______。7.图论中的最小生成树问题可以使用______算法或______算法求解。8.在整数规划中，Gomory割平面法通过添加______来切割非整数解。9.遗传算法是一种基于______原理的优化算法。10.在多目标优化中，Pareto最优解是指______。三、判断题（20分）1.线性规划问题的可行域一定是凸集。（）2.单纯形法在求解线性规划问题时一定能在有限步内找到最优解。（）3.对于凸规划问题，任何局部最优解都是全局最优解。（）4.动态规划可以解决所有类型的优化问题。（）5.非线性规划问题的最优解一定满足KKT条件。（）6.整数规划问题可以通过将整数约束去掉后求解线性规划问题得到原问题的最优解。（）7.在图论中，最小生成树问题中的边权值可以为负数。（）8.遗传算法保证能找到全局最优解。（）9.多目标优化问题中，所有Pareto最优解的目标函数值都相同。（）10.在优化算法中，收敛速度与问题的规模无关。（）四、计算题（30分）1.求解以下线性规划问题：maxz=3x1+2x2s.t.2x1+x2≤182x1+3x2≤423x1+x2≤24x1,x2≥02.使用动态规划方法求解以下背包问题：背包容量为10，有3个物品，重量分别为5、4、6，价值分别为10、40、30，求最大价值。3.使用梯度下降法求解以下无约束优化问题：minf(x)=x1^2+2x2^2+2x1x2+4x1-6x2初始点取x0=(0,0)，迭代两次，学习率取0.1。五、证明题（20分）1.证明：对于凸规划问题，任何局部最优解都是全局最优解。2.证明：在对偶线性规划中，若原问题和对偶问题都有可行解，则它们都有最优解，且最优值相等。六、应用题（40分）1.某工厂生产两种产品A和B，每单位产品A的利润为3元，每单位产品B的利润为2元。生产每单位产品A需要2小时劳动力和1单位原材料，生产每单位产品B需要1小时劳动力和3单位原材料。工厂每天有18小时劳动力和24单位原材料可供使用。此外，由于市场需求，每天至少生产2单位产品A和3单位产品B。请建立数学模型，并用线性规划方法确定最优生产计划，使工厂利润最大化。2.某物流公司需要在5个城市之间建立配送网络，已知任意两个城市之间的距离如下表所示（单位：公里）：||城市1|城市2|城市3|城市4|城市5||---|-------|-------|-------|-------|-------||城市1|0|120|200|150|180||城市2|120|0|160|100|140||城市3|200|160|0|220|170||城市4|150|100|220|0|190||城市5|180|140|170|190|0|请建立数学模型，用图论方法求解旅行商问题，找出从城市1出发，访问所有城市各一次后返回城市1的最短路径。参考答案：一、选择题1.B。线性规划的标准形式要求约束条件为等式，而非所有约束条件都必须是等式。标准形式通常包括等式约束和变量非负约束，而原始问题可能包含不等式约束。2.B。在单纯形法中，基变量的个数等于约束条件的个数（不包括非负约束），因为每个基变量对应一个约束方程。3.D。对于凸规划问题，局部最优解一定是全局最优解，可行域一定是凸集，目标函数一定是凸函数（对于最小化问题）或凹函数（对于最大化问题）。4.C。动态规划解决多阶段决策问题的核心思想是最优性原理，即一个最优策略具有这样的性质：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的决策必须构成最优策略。5.C。单纯形法是专门用于求解线性规划问题的方法，不适合求解非线性规划问题。梯度法、内点法和拟牛顿法都是求解非线性规划的常用方法。6.B。当问题有无界解时，割平面法会失效，因为无法找到一个有限的最优解来切割。7.C。遗传算法是一种启发式算法，而单纯形法、梯度下降法和内点法都是精确算法。8.B。Dijkstra算法是求解最短路径问题的常用算法，它能够找到从源点到所有其他顶点的最短路径。Prim算法用于求解最小生成树，Kruskal算法也用于求解最小生成树，Ford-Fulkerson算法用于求解最大流问题。9.C。在多目标优化中，Pareto最优解是指在某个目标得到改善时，至少会损害其他一个目标，因此Pareto最优解之间没有绝对的优劣之分。多目标优化问题通常不存在唯一的最优解，而是存在一个Pareto最优解集。所有目标函数不能简单地线性组合成一个单目标函数，因为不同目标可能具有不同的量纲和重要性。10.C。遗传算法是一种进化算法，不需要计算目标函数的梯度，它基于生物进化原理，通过选择、交叉和变异等操作来搜索最优解。梯度下降法、牛顿法和共轭梯度法都需要计算目标函数的梯度。11.C。KKT条件是一般非线性规划问题的必要条件，对于凸规划问题，KKT条件也是充分条件。12.A。单纯形法在求解大规模线性规划问题时效率较低，因为它在每次迭代中需要处理整个基矩阵。内点法、列生成法和分支定界法更适合求解大规模问题。13.A。蒙特卡洛模拟是一种通过随机抽样来估计期望值的方法。机会约束规划用于处理概率约束，两阶段随机规划用于处理多阶段随机决策问题，样本平均近似是一种将随机问题转化为确定性问题的方法。14.C。分支定界法是求解0-1整数规划问题的最有效方法之一，它通过系统地搜索解空间并剪枝来高效地找到最优解。图论方法适用于特定类型的组合优化问题，动态规划适用于具有最优子结构的问题，割平面法通常与分支定界法结合使用。15.B。在优化算法中，牛顿法通常具有最快的收敛速度，它利用目标函数的二阶信息（Hessian矩阵）来指导搜索方向，从而实现二次收敛。梯度下降法的收敛速度较慢，共轭梯度法介于两者之间，遗传算法作为一种启发式算法，收敛速度通常较慢。二、填空题1.线性，线性。线性规划问题的一般形式包括目标函数和约束条件，其中目标函数是线性函数，约束条件也是线性函数。2.目标函数。在单纯形法中，检验数表示的是当非基变量增加一个单位时，目标函数的变化率。3.变量，约束。在对偶线性规划中，原问题的变量对应对偶问题的约束条件，原问题的约束条件对应对偶问题的变量。4.f_k(s_k)=opt{f_{k+1}(s_{k+1})+d_k(s_k,u_k)}。动态规划的基本方程通常表示为当前阶段的最优收益等于从下一阶段开始的收益加上当前阶段的代价，然后对所有可能的状态转移求最优值。5.≤。凸函数的定义是：对于任意x1,x2∈D和λ∈[0,1]，有f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2)。如果严格不等号成立，则函数称为严格凸函数。6.梯度等于零。在非线性规划中，无约束优化问题的最优解满足的一阶必要条件是目标函数的梯度等于零向量，即∇f(x)=0。7.Prim，Kruskal。图论中的最小生成树问题可以使用Prim算法或Kruskal算法求解。Prim算法从一个顶点开始，逐步添加与当前树连接的最小权边；Kruskal算法按边的权值从小到大排序，依次选择不形成环的边。8.线性不等式约束。在整数规划中，Gomory割平面法通过添加线性不等式约束（割平面）来切割非整数解，从而缩小可行域，逐步逼近整数最优解。9.生物进化。遗传算法是一种基于生物进化原理的优化算法，它通过模拟自然选择、交叉和变异等过程来搜索最优解。10.不存在其他解能在不损害至少一个目标的情况下改进所有目标。在多目标优化中，Pareto最优解是指不存在其他解能在不损害至少一个目标的情况下改进所有目标。Pareto最优解集构成了所谓的Pareto前沿。三、判断题1.√。线性规划问题的可行域是由线性不等式或等式约束定义的凸集，因此一定是凸集。2.√。单纯形法在求解线性规划问题时，如果问题有最优解，则一定能在有限步内找到最优解。3.√。对于凸规划问题，任何局部最优解都是全局最优解，这是凸规划的重要性质。4.×。动态规划可以解决具有最优子结构和无后效性特点的优化问题，但不能解决所有类型的优化问题。5.×。对于一般非线性规划问题，KKT条件是最优解的必要条件，但不是充分条件。对于凸规划问题，KKT条件才是充分必要条件。6.×。整数规划问题不能简单地通过将整数约束去掉后求解线性规划问题得到原问题的最优解，因为线性规划的最优解通常不满足整数约束。7.×。在图论中，最小生成树问题中的边权值通常为非负数。如果存在负权边，最小生成树算法仍然可以工作，但通常假设边权值为非负。8.×。遗传算法是一种启发式算法，不能保证找到全局最优解，特别是在复杂和非凸的问题中。9.×。在多目标优化中，Pareto最优解的目标函数值通常不同，每个Pareto最优解代表一种不同的权衡。10.×。在优化算法中，收敛速度通常与问题的规模有关，大规模问题的收敛速度通常较慢。四、计算题1.求解以下线性规划问题：maxz=3x1+2x2s.t.2x1+x2≤182x1+3x2≤423x1+x2≤24x1,x2≥0解：首先将问题转化为标准形式，引入松弛变量x3,x4,x5：maxz=3x1+2x2+0x3+0x4+0x5s.t.2x1+x2+x3=182x1+3x2+x4=423x1+x2+x5=24x1,x2,x3,x4,x5≥0初始基变量为x3,x4,x5，非基变量为x1,x2，初始基可行解为(0,0,18,42,24)，目标函数值为0。构建初始单纯形表：|基变量|x1|x2|x3|x4|x5|解||--------|----|----|----|----|----|-----||x3|2|1|1|0|0|18||x4|2|3|0|1|0|42||x5|3|1|0|0|1|24||z|-3|-2|0|0|0|0|选择x1作为入基变量（因为其系数-3是最小的），计算比值：x3行：18/2=9x4行：42/2=21x5行：24/3=8最小比值出现在x5行，因此x5出基。进行行变换，使x1列在x5行变为1，其他行变为0：x5行除以3：(1,1/3,0,0,1/3,8)x3行减去2倍x5行：(0,1/3,1,0,-2/3,2)x4行减去2倍x5行：(0,7/3,0,1,-2/3,26)z行加上3倍x5行：(0,-1,0,0,1,24)更新后的单纯形表：|基变量|x1|x2|x3|x4|x5|解||--------|----|-----|----|----|-----|-----||x3|0|1/3|1|0|-2/3|2||x4|0|7/3|0|1|-2/3|26||x1|1|1/3|0|0|1/3|8||z|0|-1|0|0|1|24|选择x2作为入基变量（因为其系数-1是最小的），计算比值：x3行：2/(1/3)=6x4行：26/(7/3)≈11.14x1行：8/(1/3)=24最小比值出现在x3行，因此x3出基。进行行变换，使x2列在x3行变为1，其他行变为0：x3行乘以3：(0,1,3,0,-2,6)x4行减去7/3倍x3行：(0,0,-7,1,4,12)x1行减去1/3倍x3行：(1,0,-1,0,1,6)z行加上x3行：(0,0,3,0,-1,30)更新后的单纯形表：|基变量|x1|x2|x3|x4|x5|解||--------|----|----|----|----|----|-----||x2|0|1|3|0|-2|6||x4|0|0|-7|1|4|12||x1|1|0|-1|0|1|6||z|0|0|3|0|-1|30|此时，检验数中x5的系数为-1，为负数，但x5的系数在约束中为正，因此可以继续迭代。选择x5作为入基变量，计算比值：x2行：6/(-2)=-3（不考虑负比值）x4行：12/4=3x1行：6/1=6最小正比值出现在x4行，因此x4出基。进行行变换，使x5列在x4行变为1，其他行变为0：x4行除以4：(0,0,-7/4,1/4,1,3)x2行加上2倍x4行：(0,1,1/2,1/2,0,12)x1行减去x4行：(1,0,3/4,-1/4,0,3)z行加上x4行：(0,0,5/4,1/4,0,33)更新后的单纯形表：|基变量|x1|x2|x3|x4|x5|解||--------|----|----|------|------|----|-----||x2|0|1|1/2|1/2|0|12||x5|0|0|-7/4|1/4|1|3||x1|1|0|3/4|-1/4|0|3||z|0|0|5/4|1/4|0|33|此时，所有检验数都非负，因此得到最优解：x1=3，x2=12，x3=0，x4=0，x5=3，目标函数值为33。2.使用动态规划方法求解以下背包问题：背包容量为10，有3个物品，重量分别为5、4、6，价值分别为10、40、30，求最大价值。解：将问题按物品数量划分为3个阶段，每个阶段决定是否放入当前物品。定义状态s为当前背包剩余容量，决策为是否放入当前物品。逆序求解，从最后一个物品开始。第3阶段（物品3，重量6，价值30）：当s<6时，不能放入物品3，最大价值为0。当s≥6时，可以选择放入或不放入物品3：-放入：价值为30-不放入：价值为0因此，f3(s)=max{30,0}=30（当s≥6时），f3(s)=0（当s<6时）第2阶段（物品2，重量4，价值40）：当s<4时，不能放入物品2，最大价值为f3(s)。当s≥4时，可以选择放入或不放入物品2：-放入：价值为40+f3(s-4)-不放入：价值为f3(s)因此，f2(s)=max{40+f3(s-4),f3(s)}计算各s值：s=0:f2(0)=f3(0)=0s=1:f2(1)=f3(1)=0s=2:f2(2)=f3(2)=0s=3:f2(3)=f3(3)=0s=4:f2(4)=max{40+f3(0),f3(4)}=max{40+0,0}=40s=5:f2(5)=max{40+f3(1),f3(5)}=max{40+0,0}=40s=6:f2(6)=max{40+f3(2),f3(6)}=max{40+0,30}=40s=7:f2(7)=max{40+f3(3),f3(7)}=max{40+0,30}=40s=8:f2(8)=max{40+f3(4),f3(8)}=max{40+0,30}=40s=9:f2(9)=max{40+f3(5),f3(9)}=max{40+0,30}=40s=10:f2(10)=max{40+f3(6),f3(10)}=max{40+30,30}=70第1阶段（物品1，重量5，价值10）：当s<5时，不能放入物品1，最大价值为f2(s)。当s≥5时，可以选择放入或不放入物品1：-放入：价值为10+f2(s-5)-不放入：价值为f2(s)因此，f1(s)=max{10+f2(s-5),f2(s)}计算s=10时的值：f1(10)=max{10+f2(5),f2(10)}=max{10+40,70}=max{50,70}=70回溯寻找最优解：在第1阶段，s=10时选择不放入物品1，因为f1(10)=f2(10)=70。在第2阶段，s=10时选择放入物品2，因为f2(10)=40+f3(6)=70。在第3阶段，s=6时选择放入物品3，因为f3(6)=30。因此，最优解为放入物品2和物品3，总重量为4+6=10，总价值为40+30=70。3.使用梯度下降法求解以下无约束优化问题：minf(x)=x1^2+2x2^2+2x1x2+4x1-6x2初始点取x0=(0,0)，迭代两次，学习率取0.1。解：首先计算函数的梯度：∇f(x)=(∂f/∂x1,∂f/∂x2)=(2x1+2x2+4,4x2+2x1-6)初始点x0=(0,0)：∇f(x0)=(20+20+4,40+20-6)=(4,-6)x1=x0-α∇f(x0)=(0,0)-0.1(4,-6)=(-0.4,0.6)第1次迭代后点x1=(-0.4,0.6)：∇f(x1)=(2(-0.4)+20.6+4,40.6+2(-0.4)-6)=(-0.8+1.2+4,2.4-0.8-6)=(4.4,-4.4)x2=x1-α∇f(x1)=(-0.4,0.6)-0.1(4.4,-4.4)=(-0.4-0.44,0.6+0.44)=(-0.84,1.04)因此，经过两次迭代后，得到的解为x2=(-0.84,1.04)，对应的函数值为：f(x2)=(-0.84)^2+2(1.04)^2+2(-0.84)1.04+4(-0.84)-61.04=0.7056+21.0816+2(-0.8736)-3.36-6.24=0.7056+2.1632-1.7472-3.36-6.24=-8.4784五、证明题1.证明：对于凸规划问题，任何局部最优解都是全局最优解。证明：考虑凸规划问题：minf(x)s.t.g_i(x)≤0,i=1,2,...,mh_j(x)=0,j=1,2,...,p其中f(x)是凸函数，g_i(x)是凸函数，h_j(x)是仿射函数。设x是一个局部最优解，即存在一个邻域N(x)，使得对于所有x∈N(x)∩S（S为可行域），有f(x)≥f(x)。假设x不是全局最优解，则存在一个可行点x̄∈S，使得f(x̄)<f(x)。由于f(x)是凸函数，对于任意λ∈(0,1)，有：f(λx̄+(1-λ)x)≤λf(x̄)+(1-λ)f(x)由于f(x̄)<f(x)，所以：f(λx̄+(1-λ)x)<λf(x)+(1-λ)f(x)=f(x)即f(λx̄+(1-λ)x)<f(x)。另外，由于g_i(x)是凸函数，对于任意λ∈(0,1)，有：g_i(λx̄+(1-λ)x)≤λg_i(x̄)+(1-λ)g_i(x)≤λ0+(1-λ)0=0即λx̄+(1-λ)x满足不等式约束。由于h_j(x)是仿射函数，对于任意λ∈(0,1)，有：h_j(λx̄+(1-λ)x)=λh_j(x̄)+(1-λ)h_j(x)=λ0+(1-λ)0=0即λx̄+(1-λ)x满足等式约束。因此，对于任意λ∈(0,1)，点λx̄+(1-λ)x都是可行点，且f(λx̄+(1-λ)x)<f(x)。当λ足够小时，λx̄+(1-λ)x∈N(x)，这与x是局部最优解矛盾。因此，假设不成立，x必须是全局最优解。2.证明：在对偶线性规划中，若原问题和对偶问题都有可行解，则它们都有最优解，且最优值相等。证明：考虑原线性规划问题（P）和对偶线性规划问题（D）：(P)maxc^Txs.t.Ax≤bx≥0(D)minb^Tys.t.A^Ty≥cy≥0设x̄是(P)的可行解，ȳ是(D)的可行解。由可行性条件，有Ax̄≤b和A^Tȳ≥c。由于x̄≥0和ȳ≥0，可以得到：ȳ^TAx̄≤ȳ^Tbc^Tx̄≤(A^Tȳ)^Tx̄=ȳ^TAx̄因此，c^Tx̄≤ȳ^Tb。这表明对于(P)的任意可行解x̄和(D)的任意可行解ȳ，有c^Tx̄≤ȳ^Tb。即(P)的目标函数值不超过(D)的目标函数值。由线性规划的基本定理，如果(P)和(D)都有可行解，则它们都有最优解，且最优值相等。具体来说，考虑(P)的目标函数值集合{c^Tx|Ax≤b,x≥0}和(D)的目标函数值集合{b^Ty|A^Ty≥c,y≥0}。由前面的不等式，(P)的目标函数值有上界（例如ȳ^Tb），因此(P)有最优解。同样，(D)的目标函数值有下界（例如c^Tx̄），因此(D)有最优解。设x是(P)的最优解，y是(D)的最优解。由最优性条件，c^Tx≥c^Tx̄≤b^Ty≥b^Ty。但由之前的结论，c^Tx̄≤b^Tȳ对于所有可行解x̄和ȳ都成立，因此特别地，c^Tx≤b^Ty。另一方面，由强对偶定理，如果(P)和(D)都有可行解，则它们的最优值相等，即c^Tx=b^Ty。因此，(P)和(D)都有最优解，且最优值相等。六、应用题1.某工厂生产两种产品A和B，每单位产品A的利润为3元，每单位产品B的利润为2元。生产每单位产品A需要2小时劳动力和1单位原材料，生产每单位产品B需要1小时劳动力和3单位原材料。工厂每天有18小时劳动力和24单位原材料可供使用。此外，由于市场需求，每天至少生产2单位产品A和3单位产品B。请建立数学模型，并用线性规划方法确定最优生产计划，使工厂利润最大化。解：首先建立数学模型。设x1为每天生产产品A的数量，x2为每天生产产品B的数量。目标函数是最大化利润：maxz=3x1+2x2约束条件包括：1.劳力约束：2x1+x2≤182.原材料约束：x1+3x2≤243.产品A的最低产量：x1≥24.产品B的最低产量：x2≥35.非负约束：x1,x2≥0（实际上已经被最低产量约束涵盖）因此，完整的线性规划模型为：maxz=3x1+2x2s.t.2x1+x2≤18x1+3x2≤24x1≥2x2≥3下面用图解法求解这个线性规划问题。首先，绘制约束条件对应的直线：1.2x1+x2=18：当x1=0时，x2=18；当x2=0时，x1=92.x1+3x2=24：当x1=0时，x2=8；当x2=0时，x1=243.x1=2：垂直于x1轴的直线4.x2=3：垂直于x2轴的直线确定可行域的顶点：1.x1=2和x2=3的交点：(2,3)2.x1=2和2x1+x2=18的交点：22+x2=18，x2=14，点(2,14)3.x1=2和x1+3x2=24的交点：2+3x2=24，3x2=22，x2=22/3≈7.33，点(2,22/3)4.x2=3和2x1+x2=18的交点：2x1+3=18，2x1=15，x1=7.5，点(7.5,3)5.x2=3和x1+3x2=24的交点：x1+9=24，x1=15，点(15,3)检查这些点是否满足所有约束：-点(2,3)：满足所有约束-点(2,14)：检查x1+3x2=2+314=44>24，不满足原材料约束-点(2,22/3)：检查2x1+x2=4+22/3≈11.33<18，满足劳力约束-点(7.5,3)：检查x1+3x2=7.5+9=16.5<24，满足原材料约束-点(15,3)：检查2x1+x2=30+3=33>18，不满足劳力约束因此，可行域的顶点为：(2,3)、(2,22/3)和(7.5,3)。计算这些顶点的目标函数值：-点(2,3)：z=32+23=6+6=12-点(2,22/3)：z=32+2(22/3)=6+44/3≈6+14.67=20.67-点(7.5,3)：z=37.5+23=22.5+6=28.5因此，最优解为(7.5,3)，最大利润为28.5元。但是，由于产品数量通常应为整数，我们需要考虑整数解。在点(7.5,3)附近，检查整数点：-(7,3)：z=37+23=21+6=27，检查约束：27+3=17≤18，7+33=16≤24，满足-(8,3)：z=38+23=24+6=30，检查约束：28+3=19>18，不满足劳力约束-(7,4)：z=37+24=21+8=29，检查约束：27+4=18≤18，7+34=19≤24，满足-(6,4)：z=36+24=18+8=26，检查约束：26+4=16≤18，6+34=18≤24，满足因此，最优整数解为(7,4)，最大利润为29元。2.某物流公司需要在5个城市之间建立配送网络，已知任意两个城市之间的距离如下表所示（单位：公里）：||城市1|城市2|城市3|城市4|城市5||---|-------|-------|-------|-------|-------||城市1|0|120|200|150|180||城市2|120|0|160|100|140||城市3|200|160|0|220|170||城市4|150|100|220|0|190||城市5|180|140|170|190|0|请建立数学模型，用图论方法求解旅行商问题，找出从城市1出发，访问所有城市各一次后返回城市1的最短路径。解：旅行商问题是一个经典的组合优化问题，目标是找到一条访问每个城市恰好一次并返回起点的最短路径。我们可以将这个问题建模为一个完全图，其中顶点代表城市，边权代表城市之间的距离。我们需要找到一个哈密尔顿回路，即访问每个顶点恰好一次的回路，使总距离最小。由于问题规模较小（5个城市），可以使用穷举法求解所有可能的哈密尔顿回路，然后选择总距离最小的一个。从城市1出发，访问其他4个城市的排列共有4!=24种可能。计算每种排列对应的总距离：1.1→2→3→4→5→1：距离=120(1-2)+160(2-3)+220(3-4)+190(4-5)+180(5-1)=8702.1→2→3→5→4→1：距离=120(1-2)+160(2-3)+170(3-5)+190(5-4)+150(4-1)=7903.1→2→4→3→5→1：距离=120(1-2)+100(2-4)+220(4-3)+170(3-5)+180(5-1)=7904.1→2→4→5→3→1：距离=120(1-2)+100(2-4)+190(4-5)+170(5-3)+200(3-1)=7805.1→2→5→3→4→1：距离=120(1-2)+140(2-5)+170(5-3)+220(3-4)+150(4-1)=8006.1→2→5→4→3→1：距离=120(1-2)+140(2-5)+190(5-4)+220(4-3)+200(3-1)=8707.1→3→2→4→5→1：距离=200(1-3)+160(3-2)+100(2-4)+190(4-5)+180(5-1)=8308.1→3→2→5→4→1：距离=200(1-3)+160(3-2)+140(2-5)+190(5-4)+150(4-1)=8409.1→3→4→2→5→1：距离=200(1-3)+220(3-4)+100(4-2)+140(2-5)+180(5-1)=840