公园内道路设计问题

公园内道路设计问题·

摘要

公园内道路设计问题本质上是最短路径问题，该问题是现实生活中常见的的研究课题，在商业利润估算、生产生活、运输路线选择等方面都有重要意义。本文对公园内道路设计问题进行建模、求解及相关分析。

对于问题一，根据题目中两个原则：边界道路不计入修建道路总长及最短道路长不大于两点连线1.4倍，首先考虑将仅从边界走且满足小于1.4倍的点找出，只考虑余下不能利用边界的入口点与题设中所给四个交叉点之间的最短路径。针对简化后的问题，图论模型可知，利用Kruskal算法求得公园路径的最小生成树，再利用Floyd算法求出无法利用边界的点两两之间的最短路径，最后对仍不满足小于1.4倍要求的点进行局部优化，得出最短道路总长为395。

对于问题二，在问题一所求的最短设计方案基础上，排除考虑可在边界上经过的点及路径确定的P1→P8，对余下的点P2、P3、P4、P5、P6进行讨论，简化问题，得到不确定交叉点情况下的最短路径。对简化后的点间连线图引入费马点确定两个交叉点坐标，分别为M'(59.06，77.59)、N(173.10，43.64)。循环问题一求解方法，得出利用费马点优化后最短总路程为353.58，与问题一结果比较，395-353.58=41.42米，道路修建优化效果良好。

对于问题三，公园增加矩形湖，修建的道路不能通过或者只能沿着湖边修建，可以看成是对问题二方案增加约束条件。考虑到湖的影响，公园左边交叉点M的路径不改变，对右边路径进行讨论，分成两种方案设计，方案一路径不经过湖边，方案二路径沿着湖边经过，有三个交点。通过非线性规划对目标函数最短路径进行约束，求得最优值。通过比较得出方案一的交叉点坐标为N'（187.2841，53.14394）,设计道路总路程最短，为364.05。

本文主要用最短路径讨论公园内部道路建设问题，此类方法亦可推广到网线的布局、城市道路的修建、公共场所的修建等现实问题中。

关键词： Kruskal算法 Floyd算法 费马点 非线性规划

一、 问题重述

最短路径问题在现实生活中应用较多，现在要修建一个有8个入口的公园，即确定公园入口与园内交叉点的适当连线，使得公园的任意两个入口相连，但需满足道路总长度和最小，而且任意的两个入口之间的最短道路长不大于两点连线的1.4倍。同时公园四周的边上存在已经建好的道路，且不计入道路总长。我们将主要设计对象假设为一个长200米，宽100米的矩形公园。

根据题目所给数据，本文需解决的问题有：

1、假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。

2、现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。 3、若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，以此为前提，重复完成上一问题中的任务。

二、 问题分析

2.1问题一的分析

问题一是求解在公园内确定4个道路交叉点时，如何修建道路达到公园内道路总路程最短。由于题目中规定在边界点不算入道路总路程，首先可以将满足条件的点选出不加考虑。对不可在边界计算的点进行分析，先画出最小生成树，再根据Floyd算法求得两两点之间最短路径，最后进行优化使这些点满足任意的两个入口之间的最短道路长不大于两点连线的1.4倍，进而算出最短道路总路程，并画出道路设计图。 2.2问题二的分析

问题二是求解不确定交叉点，可在公园内任意修建道路的最小总路程。根据问题一方法分析，求解修建道路最短总路程必须先确定交叉点位置。由于边界路程不计入总路程，首先把可在边界上经过的点排除考虑，得到简化后的入口点间路线图。在此基础上引入费马点，通过求解费马点坐标来确定要增设的交叉点位置，再根据优化后的交叉点循环问题一方法，求出最短总路程。

2.3问题三的分析

问题三是在问题二基础上添加了个矩形湖，因此，问题三可以看成是带约束条件的问题二。由于新修的道路不能通过矩形湖，所以用非线性规划对路径进行约束规划，分两种方案进行设计，一种路径不经过湖边，另一种是路径沿着湖边经过，通过计算比较出最优设计方案，满足道路总路程最短，并画出道路设计方案图。

Pi D' W D R Lij Lmin M N

Mc

xi yi Z

三、 符号说明 公园边界的入口点(i=1,2,3,4,5,6,7,8) 道路入口点两两之间距离的1.4倍的矩阵 由最小生成树得出的邻接矩阵 道路入口点两两之间的距离矩阵 路径矩阵 i点到j点的距离 最短总路程

∆P2P5P6中的费马点

∆P3P4P5中的费马点

优化改进后的∆P2P5P6的费马点 费马点横坐标 费马点纵坐标

各点到费马点的最短路径

四、 模型假设

1、每个入口都是一个质点，不占空间位置； 2、忽略道路拐弯处引起的路径增长； 3、假设所有道路都是直线；

4、假设公园中湖的四周没有修成的路。

五、 模型建立与求解 5.1 问题一模型建立与求解

由题目已知，通过边界不修新路的点不计算路程，则可以先把满足两点间的路径不大于两点直线距离1.4倍的点剔除，只需考虑不能利用边界的点与四个交叉点之间的关系。首先算出道路入口点两两之间的距离（附录一数据），再计算出入口点两两之间距离1.4倍的距离矩阵R8⨯8，用于下面问题比较分析：

⎡[***********]45⎤

⎢⎥[**************]78⎢⎥⎢[**************]⎥⎢⎥

[1**********]82⎥ =⎢

⎢0119154198⎥⎢⎥

035116⎢⎥

⎢0106⎥⎢⎥

0⎥⎢⎣⎦

R8⨯8

若仅通过边界不修新路，计算出各点之间的路径距离如下表1： 表1-通过边界各点之间路径距离

通过比较分析，可知除一些可从边界上经过且不用修新路的入口外，其余不可利

用边界的入口点路径有PPPP2→P5、P2→P6、P2→P7、 1→P5、1→P6、1→P8、

P3→P4、P3→P5、P3→P6、P3→P7，对这些入口进行最短路径分析求解。

5.1.1 Kruskal法求最小生成树

针对P8 及公园4个固定道路交叉点A、B、C、D ，求出这12个1、P2...P点两两之间的直线距离，见附录二数据。根据数据写出公园道路设计联通图的邻接矩阵，通过Kruskal算法，解得如下表2结果： 表2-Kruskal算法程序运行结果

经分析：

根据表2画出最小生成树如下图5.1：

图5.1最小生成树示意图

5.1.2 Floyd法求最短路径

（1）写出最小生成树的邻接对角矩阵如下：

⎡030∞∞∞∞∞32∞∞∞∞⎤⎢⎥0110∞∞∞∞∞∞41∞∞⎢⎥⎢064∞∞∞∞∞∞57∞⎥⎢⎥

0∞∞∞∞∞∞∞∞⎢⎥

⎢085∞∞∞∞∞31⎥⎢⎥

0∞∞29∞∞∞⎥

W=⎢ ⎢0∞∞∞∞∞⎥

⎢⎥

0∞∞∞∞⎥⎢

⎢037∞65⎥⎢⎥⎢0∞∞⎥⎢⎥

031⎢⎥

⎢0⎥⎣⎦

（2）求路径矩阵R=(rij)v⨯v，其中：

(k-1)(k-1)(k-1)

⎧k，若d>d+dijikkj(k)⎪ r-1ij=⎨(k-1)⎪⎩rij,否则

R12⨯12

⎡1222⎢1233⎢

⎢2234⎢

⎢3334⎢12121212⎢

9999=⎢⎢6666⎢

⎢1111⎢10101212⎢

⎢2222⎢

⎢3333⎢⎣991111

22282

[***********][***********][***********][***********][***********][**************]

2⎤10⎥⎥11⎥⎥3⎥12⎥⎥9⎥6⎥⎥1⎥12⎥⎥9⎥⎥12⎥12⎥⎦

根据上述最短路径矩阵，针对需要考虑的入口P1→P5、P1→P6、P1→P8、 、

P2→P5、P2→P6、P2→P7、P3→P4、P3→P5、P3→P6、P3→P7求出这些入口之间的距离矩阵。

（2）求距离矩阵

(0)

① 把带权邻接矩阵W作为距离矩阵的初值，即D(0)=(dij)v⨯v=W

② D（0）= dij中dij

（v）

（v）

v×v

其中dij

（v）

=min dij

（v−1）

+div

（v−1）

+dvj

（v−1）

,其

是从vi到vj的只允许以v1，v2…vv作为中间点的路径中最短路的长度，即

使从vi到vj中间可插入任何顶点的路径中最短路的长度，因此Dv即使距离矩阵。

D12⨯12

⎡[***********]32108⎢[***********]78⎢⎢[***********]⎢

[**************]6⎢

⎢[1**********]⎢

02516929⎢=⎢

019454

⎢

0140⎢

⎢0⎢⎢⎢⎢⎢⎣

71

[***********]360

[***********]0229961320

173⎤143⎥⎥87⎥⎥151⎥30⎥⎥94⎥

119⎥

⎥205⎥65⎥⎥102⎥

⎥30⎥0⎥⎦

由距离矩阵中对需要考虑的入口与表1中两直线距离的1.4倍进行比较，得出

P1→P5及 P2→P5 两条路径仍不满足两点间的路径不大于两点直线距离1.4倍的条件，故逐步分析比较，进行局部优化，经分析发现，因为P1→P2是可以沿边界走的，所以只需优化P2→P5 路径：

P2→P5具体路径是P2→B→A→D→P5 ，可以考虑去掉A→D边

① 若改变路径为 P2→B→A→P5 满足小于1.4倍条件，且在道路图 中可连接。

② 若改变路径为P2→B→P8→P5 满足小于1.4倍条件，但是在道路 图中不可连接。

所以我们选取第一条路径方案优化，且优化后最小路程为：

Lmin=L18+L2B+LBA+L67+LA5+LA6+L5D+LDC+LC3+L34=395 调整后最终的道路设计方案如图5.1.2所示：

图5.1.2道路设计方案

由上图数据计算检验得，任意两点间的路径不大于两点直线距离1.4倍，道路总长为 395米。

5.2 问题二模型建立与求解

在本问题中，要求在公园内任意修路，交叉点不确定。首先考虑可以利用边界经过的入口，在问题一中分析得出P6→P7可经过边界，可以排除考1→P2及P虑，其次P也可以排除考虑。所以在交叉点不确定情况下，1→P8也是最短路径，只需要考虑点P2、P3、P4、P5、P6间的最短路径。将上述点连接起来（满足两点之间最短距离），得到无交叉点的优化道路图5.2-1：

图5.2-1无交叉点的优化道路图

在图5.2-1的基础上，再进一步针对已有的线路优化，设计出最短的道路，由此我们引入费马点的定义进行优化建模。

5.2.1费马点优化模型

定义：在一个三角形中，到三个顶点距离之和最小的点叫做这个三角形的费马点。 性质：

（1） 若三角形的三个角都小于1200，那么三条距离连线正好三等分费马点所在

的周角。

（2） 若三角形的三个角有一个大于1200，那么该钝角的顶点就是费马点。 步骤：

（1）平面内一点

P到△ABC三顶点的之和为PA+PB+PC，当点P为费马点时，

距离之和最小。

(2).三内角皆小于120°的三角形，分别以 AB,BC,CA，为边，向三角形外侧做正三角形ABC1,ACB1,BCA1,然后连接AA1,BB1,CC1,则三线交于一点P,则点P就是所求的费马点。

(3).若三角形有一内角大于或等于120度,则此钝角的顶点就是所求的费马点. (4)当△ABC为等边三角形时,此时内心与费马点重合。

据此，在改进后的图中，寻找费马点：在∆P2P5P6和∆P3P4P5中寻找费马点，如下图5.2-2：

图5.2.2寻找费马点

设M(x1,y1)，N(x2,y2)，由费马点的定义，我们得到求解费马点的目标函数分别为：

ZM=

x1-352+y1-1002+x1-502+y12+x1-1202+y1-1002

20x1+3y1-1000≥0约束条件为： 10x1-7y1-500≤0

y1≤100

ZN=

x2-1202+y2-1002+x2-1602+y22+x2-2002+y2-502

5x2-

4y2-800≤05x2+8y2-1400≤0

约束条件为: 5x2+2y2-800≥0

运用lingo解得 M(62.33，77.86) N(173.10，43.64)

确定交叉点位置，循环问题一解法，通过Kruskal算法找出最小生成树，再用Floyd算法计算最短路径，经分析，费马点优化后的两两最短路径中，只有P1→P6 不满足两点间的路径不大于两点直线距离1.4倍这个条件，需要进行改进。

5.2.2 费马点改进模型

在原目标函数基础上，再次利用费马点进行改进，目标函数不变，

ZM=

x1-352+y1-1002+x1-502+y12+x1-1202+y1-1002

约束条件改为

，77.

59) 解得 Mc(59.06

循环问题一方法，所有路径均满足条件，求得改进优化后的道路设计图5.2-3：

在不确定交叉点情况下任意修路，既要满足两点间的路径不大于两点直线距离1.4倍，又使修路总路程最短，应取两个交叉点坐标位置

Mc(59.06，77.59)

修路总路程最小为353.58米，与问题一结果比较，有很大改进。 N(173.10，43.64)，

5.3 问题三模型建立与求解

本问题中，在第二问的基础上，考虑到了公园内部有一个人工湖，原设计的道路方案有些道路不能通过，只能到达湖的周边。因此，要对第二问得到的路线设计进行局部优化，使其符合题设要求。增加一个矩形后的公园道路图5.3-1如下

：

图5.3-1

如图所示，第二问的设计路线中因为有了人工湖的存在导致P2→N路线不能通过，而在人工湖左边的交叉点

Mc路线没有什么阻碍，还是第二问中得出的

最优的，因此，本问题只考虑改变N这个交叉点就行，对其进行局部优化，以达到实际情况和满足内部总路程最小的要求。下面用非线性规划设计两种方案进行优化：

（1）改变交叉点N位置，优化为N'，连接P5N'、P3N'、P4

N'，使三条路

径不经过湖且满足题目条件。

（2）改变交叉点N位置，在矩形湖边上分别找三个点a、b、c，连接P5a、

P5b、P5c，沿着湖边经过且满足题目条件。

方案（1）中的目标函数为：

ZN'=

x-120+y-100

22

+

x-160+y+

2

2x-200+y-50

2

2

100-y100-y2

≤-2.75或≥-120-x120-x3y

-2.25≤≤9

x-1604y-501

≤约束条件为 -≤

7x-2007120≤x≤2000≤y≤100

xxxx

-160+y+

2

2xx

2

-200+y-50

2

2

2

2

-160+y+

2

2

2

-200+y-50

x-160+y+

2

2-200+y-50+85

2

2

x-200+y-50+110

2

2

解得minZN'=156.1069 交叉点N'（187.2841，53.14394）所以修路总路程为L总=364.05，具体方案设计图5.3-2如下：

图5.3-2 方案二的目标函数：

Zabc=100-70+120-a+

2

2

222

b-502+（200-165）+c-160+（45）+(165-a)+(165-c)+25

约束条件为

140≤a≤16545≤b≤70140≤c≤165

解得

a=165b=50

c=160

所以经过分析发现，点a与点R4重合，点c与点R3重合，即方案二道路设计如图5.3-3，

min Z=184.2616,修路总路程为L总=392.20424。

图5.3-3

通过以上分析，通过总路程比较可知方案一比方案二更优，因为它设计的公园内部道路路线更短，所以最终选用方案一用作公园道路设计，道路总路程为364.05。

六、 模型的评价与推广

6.1模型优点

（1）在问题一求解中，充分利用了边界条件和1.4倍的约束条件将不满足的点找出来分析讨论，将复杂的问题进行了简化，减小了求解工作量； （2）在问题二中，模型引入了费马点的定义，通过寻找费马点的方法来找道路交叉点，多次优化费马点坐标优化得到满足条件的道路设计图。这种方法简单实用，易于理解。

（3）利用规划模型，以总路程最小为目标去解决实际的道路设计问题，操作简便。结合了问题二所得的结果，很好的利用了现有的数据。考虑较为全面，分析比较了两种情况道路的总长。使得问题更加优化。 6.2模型缺点

问题二结合问题一的结果，简化问题引用费马点的定义，便于解决问题，但在考虑交叉点时，没有去仔细考虑交叉点为3、4的情况。 6.3模型推广

本文主要讨论的是公园内部道路建设问题，我们所使用的方法适用于大部分最短路径问题，包括网线的布局、城市道路的修建、公共场所的修建等问题。该模型对节约社会资源，方便人们活动等各方面问题有重大意义。

七、参考文献

[1] 赵静，但琦等.数学建模与数学实验[M]. 高等教育出版社，施普林格出版社 [2] 王海英，黄强，李传涛，褚宝增.图论算法及其MATLAB实现[M].北京航空大学出版社

[3]朱斌，林博，付思伟.公园内道路的优化设计模型[A].高等数学研究，2013(5)第16卷第3期

八、 附录

附录一：

最小生成树邻接矩阵

附录二：

12个点两两之间距离

P1 P2 P3 P4 P5 P6 P7 P8 A B C D

P1 P2 P3 P4 P5 P6 P7 P8 A B C D

0.00 30.00 140.00 186.82 141.42 136.78 161.78 32.02 107.63 71.23 196.57 172.82 30.00 0.00 110.00 174.03 173.23 106.78 131.78 62.02 77.63 41.23 166.57 142.82 140.00 110.00 0.00 64.03 117.39 181.32 206.32 172.02 152.17 151.23 56.57 86.98 204.03 174.03 64.03 0.00 181.42 245.35 270.35 236.05 216.20 215.26 120.60 151.01 203.23 173.23 117.39 181.42 0.00 85.00 110.00 235.25 95.60 132.00 60.82 30.41 136.78 106.78 181.32 245.35 85.00 0.00 25.00 168.80 29.15 65.55 124.75 94.34 161.78 131.78 206.32 270.35 110.00 25.00 0.00 193.80 54.15 90.55 149.75 119.34 32.02 62.02 172.02 236.05 235.25 168.80 193.80 0.00 139.65 103.25 228.59 204.84 107.63 77.63 152.17 216.20 95.60 29.15 54.15 139.65 0.00 36.40 95.60 65.19 71.23 41.23 151.23 215.26 132.00 65.55 90.55 103.25 36.40 0.00 132.00 101.59 196.57 166.57 56.57 120.60 60.82 124.75 149.75 228.59 95.60 132.00 0.00 30.41 172.82 142.82 86.98 151.01 30.41 94.34 119.34 204.84 65.19 101.59 30.41 0.00

附录三：

计算各点两两之间的距离程序 function d=juli(x,y);

%向量x为各点的横坐标，向量y为各点的纵坐标 n=length(x);m=length(y); for i=1:n for j=1:m

d(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2); end end d

d1=d*1.4 %d1为各点两两之间距离的1.4倍距离的矩阵

边界各点两两之间的最短路径距离程序 %边界各点两两之间的最短路径距离 m=zeros(8,8);

m(1,2)=30;m(2,3)=110;m(3,4)=90;m(4,5)=130;m(5,6)=85;m(6,7)=25; m(7,8)=85;m(1,8)=45; for i=1:8 for j=1:8

if(m(i,j)~=0)

m(j,i)=m(i,j); end end end

for i=1:8 for j=1:8

if(m(i,j)==0) m(i,j)=inf; if(i==j)

m(i,j)=0; end end end end

[t,c]=floyd(ll);

%调用floyd函数，t为边界各点两两之间的最短路径的距离矩阵，c为路由矩阵。

Kruskal算法

function [T c]=Krusf(d,flag) % function [T c]=Krusf(d,flag)

% 求最小生成树的Kruskal算法 % 边权矩阵的产生方法：

% 1)一般的边权矩阵，为nxn维。调用方式[T c]=Krusf(d)

% 2）边权矩阵的前两行分别记录图上所有边的起始顶点和终止顶点，

% 无向边不重复记录。第三行记录对应边的权值。调用方式为[T c]=Krusf(d,1) % c:生成树的费用; % T:生成树的边集合; if nargin==1 n=size(d,2);

m=sum(sum(d~=0))/2; b=zeros(3,m); k=1;

for i=1:n

for j=(i+1):n if d(i,j)~=0

b(1,k)=i;b(2,k)=j; b(3,k)=d(i,j);k=k+1; end end end else b=d; end

n=max(max(b(1:2,:))); m=size(b,2);

[B,i]=sortrows(b',3); B=B';

c=0;T=[]; k=1;t=1:n; for i=1:m

if t(B(1,i))~=t(B(2,i)) T(1:2,k)=B(1:2,i); c=c+B(3,i); k=k+1;

tmin=min(t(B(1,i)),t(B(2,i))); tmax=max(t(B(1,i)),t(B(2,i))); for j=1:n

if t(j)==tmax t(j)=tmin; end end end

if k==n

break;

end

end

T;

c;

生成最小生成树的邻接矩阵

d=[0.0000 30.0000 140.0000 186.8154 141.4214 101.1187 100.4988 32.0156 80.7775 44.7214 107.7033 118.0042

30.0000 0.0000 110.0000 158.1139 122.0656 101.1187 107.7033 55.9017 75.0000 41.2311 80.6226 95.5249

140.0000 110.0000 0.0000 64.0312 107.7033 160.0781 180.2776 161.9413 133.1353 126.4911 56.5685 83.2166

186.8154 158.1139 64.0312 0.0000 94.3398 172.4094 196.4688 201.5564 152.0691 160.3122 80.6226 87.3212

141.4214 122.0656 107.7033 94.3398 0.0000 85.0000 110.0000 141.5097 74.3303 100.0000 60.0000 30.4138 101.1187 101.1187 160.0781 172.4094 85.0000 0.0000 25.0000 82.7647 29.1548 60.2080 104.0433 85.4400

100.4988 107.7033 180.2776 196.4688 110.0000 25.0000 0.0000 75.6637 47.1699 67.0820 125.2996 109.2016

32.0156 55.9017 161.9413 201.5564 141.5097 82.7647 75.6637 0.0000 70.7107 42.7200 120.9339 123.4909

80.7775 75.0000 133.1353 152.0691 74.3303 29.1548 47.1699 70.7107 0.0000 36.4005 78.2624 65.1920

44.7214 41.2311 126.4911 160.3122 100.0000 60.2080 67.0820 42.7200 36.4005 0.0000 80.0000 80.7775

107.7033 80.6226 56.5685 80.6226 60.0000 104.0433 125.2996 120.9339 78.2624 80.0000 0.0000 30.4138

118.0042 95.5249 83.2166 87.3212 30.4138 85.4400 109.2016 123.4909 65.1920 80.7775 30.4138 0.0000 ]; D=zeros(12,12);

D(5,6)=1;D(2,3)=1;D(6,7)=1;D(6,9)=1;D(1,2)=1;D(5,12)=1;D(11,12)=1;D(1,8)=1;D(9,10)=1;D(2,10)=1;D(3,11)=1;D(3,4)=1;D(9,12)=1;

for i=1:12

for j=1:12

if(D(i,j)==1)

D(j,i)=1;

end

end

end

D

for i=1:12

for j=1:12

if(i==j)

ll(i,j)=0;

else

if(D(i,j)==1)

ll(i,j)=d(i,j);

ll(j,i)=d(i,j);

else

ll(i,j)=inf;

ll(j,i)=inf;

end

end

end

end

ll %ll为最小生成树的邻接矩阵

Floyd算法

function[D,R]=floyd(a)

n=size(a,1);

D=a

for i=1:n

for j=1:n

R(i,j)=j;

end

end

R

for k=1:n

for i=1:n

for j=1:n

if D(i,k)+D(k,j)

D(i,j)=D(i,k)+D(k,j);

R(i,j)=R(i,k);

end

end

end

k

D

R

end

第二问：

右点 费马点

model:

min=@sqrt((x2-120)^2+(y2-100)^2)+@sqrt((x2-200)^2+(y2-50)^2)+@sqrt((x2-160)^2+y2^2);

5*x2-4*y2-800

5*x2+8*y2-1400

5*x2+2*y2-800>=0;

end

左点 费马点

model:

min=@sqrt((x1-35)^2+(y1-100)^2)+@sqrt((x1-50)^2+y1^2)+@sqrt((x1-1

20)^2+(y1-100)^2);

20*x1+3*y1-1000>=0;

10*x1-7*y1-500

y1

end

优化后的左点

model:

min=@sqrt((x1-35)^2+(y1-100)^2)+@sqrt((x1-50)^2+y1^2)+@sqrt((x1-1

20)^2+(y1-100)^2);

20*x1+3*y1-1000>=0;

10*x1-7*y1-500

y1

@sqrt((x1-35)^2+(y1-100)^2)+@sqrt((x1-50)^2+y1^2)

end

第三问：

model:

min=@sqrt((x-160)^2+y^2)+@sqrt((x-200)^2+(y-50)^2)+@sqrt((x-120)^2+(y-100)^2);

(100-y)/(120-x)>=-2/3;

y/(x-160)>=-2.25;

y/(x-160)

(y-50)/(x-200)>=-4/7;

(y-50)/(x-200)

x

120

0

y

@sqrt((x-200)^2+(y-50)^2)+@sqrt((x-160)^2+y^2)

@sqrt((x-160)^2+y^2)+@sqrt((x-120)^2+(y-100)^2)

@sqrt((x-200)^2+(y-50)^2)+@sqrt((x-160)^2+y^2)+85

model:

min=@sqrt((100-70)^2+(120-a)^2)+@sqrt((b-50)^2+35^2)+@sqrt((c-160)^2+70^2)+(165-a)+(165-c)+25;

140

a

45

b

140

c

end