著者:飯尾 淳
本連載では「Pythonを昔から使っているものの、それほど使いこなしてはいない」という筆者が、いろいろな日常業務をPythonで処理することで、立派な「蛇使い」に育つことを目指します。その過程を温かく見守ってください。皆さんと共に勉強していきましょう。第24回では、高校で学ぶレベルの数学を用いて、問題を最適にする解は何かを探索します。題材は、線形計画法と組合せ最適問題の二つです。
シェルスクリプトマガジン Vol.94は以下のリンク先でご購入できます。


図3 図1の問題を解くPythonコード
from ortools.linear_solver import pywraplp
# ソルバーの定義
solver = pywraplp.Solver.CreateSolver('GLOP')
# 変数の準備
x = solver.NumVar(0, solver.infinity(), 'x')
y = solver.NumVar(0, solver.infinity(), 'y')
# 目的関数と制約条件の定義
solver.Maximize(400 * x + 300 * y)
solver.Add(60 * x + 40 * y <= 3200)
solver.Add(20 * x + 30 * y <= 2000)
solver.Add(20 * x + 10 * y <= 1000)
# 問題を解く
status = solver.Solve()
# 結果を出力
if status == pywraplp.Solver.OPTIMAL:
print(f'解:')
print(f'x = {x.solution_value()}')
print(f'y = {y.solution_value()}')
else:
print('最適解は存在しません')
図4 CBCソルバーを使うように書き換えた図3のPythonコード
(略)
# ソルバーの定義
solver = pywraplp.Solver.CreateSolver('CBC')
# 変数の準備
x = solver.IntVar(0, solver.infinity(), 'x')
y = solver.IntVar(0, solver.infinity(), 'y')
(略)
図6 データを準備するためのPythonコード
teachers = ['田中', '山本', '竹村', '飯島', '佐藤']
days = ['月', '火', '水', '木', '金']
periods = ['1限', '2限', '3限', '4限']
図7 lessons連想配列を作成するPythonコード
lessons = { (t, d, p): \
model.NewBoolVar('lesson_%s_%s_%s' % (t, d, p)) \
for t in teachers for d in days for p in periods }
図8 lessons連想配列の内容
{('田中', '月', '1限'): lesson_田中_月_1限(0..1),
('田中', '月', '2限'): lesson_田中_月_2限(0..1),
('田中', '月', '3限'): lesson_田中_月_3限(0..1),
('田中', '月', '4限'): lesson_田中_月_4限(0..1),
('田中', '火', '1限'): lesson_田中_火_1限(0..1),
('田中', '火', '2限'): lesson_田中_火_2限(0..1),
(略)
図9 「同時に2人以上の先生が授業することはない」制約条件を与えるPythonコード
for d in days:
for p in periods:
model.Add(sum(lessons[(t, d, p)] for t in teachers) == 1)
図10 「先生は1日に1コマだけ授業を担当する」制約条件を与えるPythonコード
for t in teachers:
for d in days:
model.Add(sum(lessons[(t, d, p)] for p in periods) <= 1)
図11 「担当時間数に偏りが出ないように配置する」制約条件を与えるPythonコード
for t in teachers:
model.Add(sum(lessons[(t, d, p)] \
for d in days for p in periods) == 4)
図12 requests連想配列を定義するコードの例
requests = {
'田中': {
'月': {'1限': 0, '2限': 0, '3限': 1, '4限': 0},
'火': {'1限': 0, '2限': 0, '3限': 0, '4限': 0},
'水': {'1限': 0, '2限': 1, '3限': 0, '4限': 0},
'木': {'1限': 0, '2限': 0, '3限': 0, '4限': 1},
'金': {'1限': 0, '2限': 1, '3限': 0, '4限': 0} },
'山本': {
'月': {'1限': 1, '2限': 0, '3限': 0, '4限': 0},
'火': {'1限': 0, '2限': 1, '3限': 0, '4限': 0},
'水': {'1限': 0, '2限': 0, '3限': 1, '4限': 0},
'木': {'1限': 1, '2限': 0, '3限': 0, '4限': 0},
'金': {'1限': 0, '2限': 0, '3限': 0, '4限': 0} },
'竹村': {
'月': {'1限': 0, '2限': 1, '3限': 0, '4限': 0},
'火': {'1限': 0, '2限': 1, '3限': 0, '4限': 0},
'水': {'1限': 1, '2限': 0, '3限': 0, '4限': 0},
'木': {'1限': 1, '2限': 0, '3限': 0, '4限': 0},
'金': {'1限': 0, '2限': 0, '3限': 0, '4限': 0} },
'飯島': {
'月': {'1限': 0, '2限': 0, '3限': 0, '4限': 1},
'火': {'1限': 0, '2限': 0, '3限': 0, '4限': 0},
'水': {'1限': 0, '2限': 1, '3限': 0, '4限': 0},
'木': {'1限': 0, '2限': 1, '3限': 0, '4限': 0},
'金': {'1限': 1, '2限': 0, '3限': 0, '4限': 0} },
'佐藤': {
'月': {'1限': 0, '2限': 0, '3限': 0, '4限': 0},
'火': {'1限': 0, '2限': 0, '3限': 1, '4限': 0},
'水': {'1限': 0, '2限': 0, '3限': 1, '4限': 0},
'木': {'1限': 0, '2限': 1, '3限': 0, '4限': 0},
'金': {'1限': 0, '2限': 0, '3限': 0, '4限': 1} }
}
図13 目的関数を定義するPythonコード
model.Maximize( \
sum(requests[t][d][p] * lessons[(t, d, p)] \
for t in teachers for d in days for p in periods))
図14 結果を表示するPythonコード
for d in days:
print(d + "曜日:")
for p in periods:
for t in teachers:
if solver.Value(lessons[(t, d, p)]) == 1:
print(t+'先生が'+p+'の授業を担当する。', end="")
print() if requests[t][d][p] == 1 else print('※')
print()
図16 「先生の希望は少なくとも3コマはかなえる」制約条件を与えるPythonコード
for t in teachers:
model.Add(sum(lessons[(t, d, p)]*requests[t][d][p] \
for d in days for p in periods) >= 3)