シェルスクリプトマガジン

Pythonあれこれ（Vol.94掲載）

著者：飯尾 淳

本連載では「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)