Pythonプログラミング（総合演習課題）

このページには、線形計画法を使って空間を「最大限に」埋める円を描くプログラムの開発を、演習課題としてまとめました。

準備

以下に取り組む前に、まず、以下のページの内容を確認しておくこと。

• 基本的な図形の描画
• 線形計画法による最適化（補足：双対問題）

課題１ 円の描画

亀で描く基本的な図形 多角形の描画関数を参考に、中心座標 x,y 半径 r の円を描く関数 circle(x,y,r) を定義し、 それを使って、図1に示すように、左端が互いに接し、半径の異なる10個の円を描画するプログラム: ten-circles.pyを作成せよ。

円を多角形で近似的に（「折れ線近似」で）描く際、小さな円では線分（多角形の辺）の長さをあまり短くしても、見栄えはほとんど違わない。 そこで、circle()関数では、半径に応じて辺の長さを適切に調整することで、小さな円ほど素早く描ける（亀場での描画時間が短くなる）ように工夫せよ。

課題では、最も大きな円の中心座標を(0.0, 0.0)、半径を200.0とし、円の半径が 200.0, 180.0, 160.0, ... 20.0 と規則的に変化するようプログラムすること。 その際、「規則的な変化」を反復処理（for文）によって実現すること。

スクリーンショットの画像ファイル名は ten-circles.pngとせよ。

課題２　円による「縄張り」の定式化

この課題に取り組む前に、線形計画法による最適化 の内容を把握し、例題プログラムを実行してみること。線形計画法については、参考書3.7節『焙煎コーヒー売ってます』が参考になる。

上記を踏まえ、平面上の異なる４点(点0, 1, 2, 3とする）を中心に、半径がそれぞれ $r_0, r_1, r_2, r_3$ の4つの円を描いた際、 円が互いに重なり合わず（円が別の円の中に含まれてもいけない）、かつ、半径の和($r_0+r_1+r_2+r_3$)を最大とするような半径の組み合わせを、線形計画問題として解きたい。

円iとjの中心間距離を$d_{ij}$のように表記する（例えば、1と2の距離は$d_{12}$）とき、この問題の制約条件と目的関数を表す表式を、 以下の例（これは3点の場合）にならってテキストファイルで文書化せよ。数式はPythonの書式に沿って記述すること。 ファイル名は opt-circle-4.txt とせよ。

課題2
氏名 東北太郎

点0, 1, 2の座標をそれぞれ (x[i], y[i]) (ここでi=0,1,2)とし、それらを中心とする円の半径を r0, r1, r2 とする。

目的関数:
1*r0 + 1*r1 + 1*r2

制約条件:
1*r0 + 1*r1 + 0*r2 <= d01
0*r0 + 1*r1 + 1*r2 <= d12
1*r0 + 0*r1 + 1*r2 <= d02
r0>=0
r1>=0
r2>=0

ここで、点間の距離はそれぞれ
d01 = sqrt((x[0]-x[1])*(x[0]-x[1]) + (y[0]-y[1])*(y[0]-y[1]))
d12 = sqrt((x[1]-x[2])*(x[1]-x[2]) + (y[1]-y[2])*(y[1]-y[2]))
d02 = sqrt((x[0]-x[2])*(x[0]-x[2]) + (y[0]-y[2])*(y[0]-y[2]))
で与えられる。

課題３　円による「縄張り」の描画

課題2を踏まえ、以下に示すの4つの円の配置について最適解を計算し、図4の例のように、亀場に最適な大きさの円を描くプログラムを作成せよ。

0, 0
100, 120
30, -70
-90, 10

最適解の計算とグラフィック表示は、ひとつのプログラム中で行なうようにすること（２本の別々のプログラムを作成するのではない）。 円の描画には、課題1で作成したcircle()関数を用いること。 また、グラフィック表示だけでなく、円の半径$r_i$と目的関数$z$の最大値を、printf()関数を使って、コンソール画面に出力するようにすること。

プログラムファイル名はopt-circle-4.py、スクリーン画像のファイル名はopt-circle-4.pngとせよ。

# 情報基礎 課題3 氏名：東北太郎 */

import math
from turtle3 import Turtle
from simplex import SimplexMethod

q = SimplexMethod(?, ?)

a = [ ??? ]
b = [ ??? ]
c = [ ??? ]

# 線形計画法を解く 
q.init_coef(alpha, b, c)
res = q.simplex()
if res>0:
    q.print_solution()

# 計算結果をグラフィック表示する
t = Turtle("localhost")
...

課題４ 線形計画法による計算の自動化

課題3で作成したプログラムをさらに発展させ、 キーボードから8つの点のx,y座標を入力すると、線形計画法の条件式（配列要素の値）を計算によって自動生成し、 円の配置をグラフィック表示するプログラムを作成せよ。 加えて、円の半径$r_i$と目的関数$z$の値を、コンソール画面に出力するようにすること。 プログラムファイル名は opt-circle-8.py とし、スクリーン画像はopt-circle-8.pngとせよ。

なお、スクリーン画像を提出する際には、以下の座標値について計算した結果を示すこと：

円の中心座標（x,y)
0, 0
-50,-180
-100,0
-100,120
70,180
90,10
180,50
-170,-60

描画の際、図3のように、円だけでなく中心点の座標も分かるよう表示すること。

【ヒント】$n$個の点が与えられたとき、互いの中心間の距離は、$ {n \choose 2}$　通りの組み合わせがある。 すなわち、２つの円の半径の関係についての制約条件の数は$\frac{n(n-1)}{2}$である。