跳至内容

GLPK/可缩放矢量图形

Add links
来自维基教科书，开放世界中的开放书籍

可缩放矢量图形 (SVG) 是一种 XML 文件格式，用于描述二维图形。 SVG 1.1 是规范的最新版本。

只需一点努力，MathProgprintf语句可用于生成 SVG 代码。

示例

[编辑 | 编辑源代码]

旅行商问题

[编辑 | 编辑源代码]
使用 GLPK 生成的 SVG 输出

在 旅行商问题 中的任务是找到通过给定城市集的最短循环路径，每个城市只访问一次，然后返回起点。

以下模型展示了如何将解决方案输出为可缩放矢量图形。

###################################################################
# This file demonstrates output to a scalable vector graphic (SVG).
#
# Solve with option --nomip to see the difference
#
# Traveling salesman problem
#
###################################################################

# output file
param filename, symbolic := "out.svg";
# number of cities
param n := 35;

# set of cities
set N := {1..n};
# set of bidirectional arcs
set E := setof{(i,j) in N cross N : i > j} (i,j);
# set of unidirectional arcs
set F := setof{(i,j) in N cross N : i != j} (i,j);

# random locations for the cities
param cx{i in N} := Uniform01();
param cy{i in N} := Uniform01();
#sum of x- and y- distance
#param d{(i,j) in E} := abs(cx[i]-cx[j])+abs(cy[i]-cy[j]);
#maximum of x- and y- distance
#param d{(i,j) in E} := max(abs(cx[i]-cx[j]),abs(cy[i]-cy[j]));
#euclidean distance
param d{(i,j) in E} := sqrt((cx[i]-cx[j])^2+(cy[i]-cy[j])^2);

# connection
var x{(i,j) in E}, >=0, <= 1, binary;
# flow
var f{(i,j) in F}, >= 0;

# Objective
minimize dist :
  sum{(i,j) in E} x[i,j] * d[i,j];

# Every city must have two connections for a round trip
s.t. two{ i in N } :
  sum{j in N : i > j} x[i,j] + sum{j in N : i < j} x[j,i] = 2;

# The following constraints force the graph to be connected
# Flow is controlled by binaries
s.t. flow1 {(i,j) in F} :
  f[i,j] <= (if (i==1) then n else n-1) 
          * (if (i < j) then x[j,i] else x[i,j]);

# One unit is consumed in each node
s.t. flow2 {i in N} :
  sum{(i,j) in F} (f[i,j]-f[j,i]) <= if (i==1) then n-1 else -1;

# There must be flow into every node
s.t. flow3 { i in N } :
  sum{(i,j) in F} f[j,i] >= 1;

solve;

# Output the solution as scalable vector graphic
# write header
printf "<?xml version=""1.0"" standalone=""no""?>\n" > filename;
printf "<!DOCTYPE svg PUBLIC ""-//W3C//DTD SVG 1.1//EN"" \n" >> filename;
printf """http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"">\n" >> filename;
printf "<svg width=""100\%"" height=""100\%"" version=""1.0"" \n" >> filename;
printf "xmlns=""http://www.w3.org/2000/svg"">\n" >> filename;
# draw circles for cities
for {i in N}
  printf "<circle cx=""%f"" cy=""%f"" r=""5"" stroke=""black"" stroke-width=" &
         """2"" fill=""red""/>\n", cx[i] * 500, cy[i] * 500 >> filename;
# draw solid black lines for integer connections
for {(i,j) in E : x[i,j] == 1}
  printf "<line x1=""%f"" y1=""%f"" x2=""%f"" y2=""%f""" &
         " style=""stroke:black;stroke-width:2""/>\n", 
         cx[i] * 500, cy[i] * 500, cx[j] * 500, cy[j] * 500 >> filename;
# draw dashed red lines for fractional connections
for {(i,j) in E : x[i,j] > 0 && x[i,j] < 1}
  {
  printf "<line x1=""%f"" y1=""%f"" x2=""%f"" y2=""%f""",
         cx[i] * 500, cy[i] * 500, cx[j] * 500, cy[j] * 500 >> filename;
  printf " style=""stroke:red;stroke-dasharray: 3 3;stroke-width:2""/>\n"
         >> filename;
  }
printf "</svg>\n" >> filename;
end;

运行模型（在 Intel Core i5 处理器上运行 40 秒）

$ glpsol --math traveling.mod

这就是创建的输出文件out.svg看起来像（删除了一些行）

<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" 
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="100%" height="100%" version="1.0" 
xmlns="http://www.w3.org/2000/svg">
<circle cx="14.843435" cy="64.155902" r="5" stroke="black" stroke-width="2" fill="red"/>
<circle cx="276.895963" cy="4.798338" r="5" stroke="black" stroke-width="2" fill="red"/>
...
<line x1="103.248022" y1="381.131207" x2="127.779724" y2="409.131953" style="stroke:black;stroke-width:2"/>
<line x1="103.248022" y1="381.131207" x2="96.365578" y2="282.627837" style="stroke:black;stroke-width:2"/>
</svg>

生成的可以在最新的网络浏览器中查看（例如 Firefox 3.6 或 Internet Explorer 9）或使用（跨平台）SVG 编辑器（例如 Inkscape）进行查看和修改。

聚类

[编辑 | 编辑源代码]
使用 GLPK 创建的聚类问题解决方案

下面的示例涉及一个聚类问题。从 500 个城镇中选出 20 个作为聚类中心，并将其他城镇分配到聚类中，以使城镇与中心之间的总人口加权欧几里德距离最小化。

# Output file
param f, symbolic := "ct.svg";

# Centers
param nc := 20;
set C := {1 .. nc};

# Towns
param nt := 500;
set T := {1 .. nt};
param xt{T} := Uniform01();
param yt{T} := Uniform01();
param pt{T} := ceil(1000 * Uniform01());

# Image size
param scale := 1000;

# Colors
# saturation [0, 255]
param sat := 192;
param hue{c in C} := 6 * (c - 1) / nc;
param red{c in C} :=
  if hue[c] <= 1 or hue[c] >= 5 then 255
  else (if hue[c] >=2 and hue[c] <= 4 then 255 - sat
  else (if hue[c] <=2 then 255 - sat + sat * (2-hue[c])
  else 255 - sat + sat * (hue[c]-4) ));
param green{c in C} :=
  if hue[c] >= 1 and hue[c] <= 3 then 255
  else (if hue[c] >= 4 then 255 - sat
  else (if hue[c] <=1 then 255 - sat + sat * hue[c]
  else 255 - sat + sat * (4-hue[c]) ));
param blue{c in C} :=
  if hue[c] >= 3 and hue[c] <= 5 then 255
  else (if hue[c] <=2 then 255 - sat
  else (if hue[c] <=3 then 255 - sat + sat * (hue[c]-2)
  else 255 - sat + sat * (6-hue[c]) ));

var x{T,T}, binary;

minimize obj : sum{c in T, t in T : c != t} x[c,t] * pt[t]
               * sqrt((xt[c] - xt[t])^2 + (yt[c] - yt[t])^2);

s.t. cc : sum{c in T} x[c,c] = nc;
s.t. ct{c in T, t in T : c != t} : x[c,t] <= x[c,c];
s.t. tc{t in T} : sum{c in T} x[c,t] = 1;

solve;

for {c in T : x[c,c] > .5} {
  printf "Center %5.4f %5.4f\n", xt[c], yt[c];
  for {t in T : x[c,t] > .5} {
    printf "  Town %5.4f %5.4f (%5.0f)\n", xt[t], yt[t], pt[t];
  }
}

# Output the solution as scalable vector graphic

# header
printf "<?xml version=""1.0"" standalone=""no""?>\n" > f;
printf "<!DOCTYPE svg PUBLIC ""-//W3C//DTD SVG 1.1//EN"" \n" >> f;
printf """http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"">\n" >> f;
printf "<svg width=""%d"" height=""%d"" version=""1.0"" \n",
  1.2 * scale, 1.2 * scale >> f;
printf "xmlns=""http://www.w3.org/2000/svg"">\n" >> f;

# background
printf "<rect x=""0"" y=""0"" width=""%d"" height=""%d""" &
       " stroke=""none"" fill=""white""/>\n",
       1.2 * scale, 1.2 * scale>> f;

# border
printf "<rect x=""%d"" y=""%d"" width=""%d"" height=""%d""" &
       " stroke=""black"" stroke-width="".5"" fill=""white""/>\n",
       .1 * scale, .1 * scale, scale, scale >> f;

# circles for towns
for {t in T}
  printf {s in T, c in C : x[s,t] > .5
         && c = floor( .5 + sum{u in T : u <= s} x[u,u])}
         "<circle cx=""%f"" cy=""%f"" r=""%f"" stroke=""black"" " &
         "stroke-width=""1"" fill=""rgb(%d,%d,%d)""/>\n",
         (.1 + xt[t]) * scale, (.1 + yt[t]) * scale, .007 * sqrt(pt[t]/nt) *
	 scale, red[c], green[c] , blue[c] >> f;

# lines from towns to assigned centers
for {t in T, c in T : x[c,t] > .5}
  printf "<line x1=""%f"" y1=""%f"" x2=""%f"" y2=""%f""" &
         " style=""stroke:black;stroke-width:.5""/>\n",
         (.1 + xt[c]) * scale, (.1 + yt[c]) * scale,
         (.1 + xt[t]) * scale, (.1 + yt[t]) * scale >> f;

printf "</svg>\n" >> f;

end;
检索自 "https://wikibooks.cn/w/index.php?title=GLPK/Scalable_Vector_Graphics&oldid=3575895"
华夏公益教科书