Pythonあれこれ（Vol.94掲載）
著者：飯尾 淳
本連載では「Pythonを昔から使っているものの、それほど使いこなしてはいない」という筆者が、いろいろな日常業務をPythonで処理することで、立派な「蛇使い」に育つことを目指します。その過程を温かく見守ってください。皆さんと共に勉強していきましょう。第24回では、高校で学ぶレベルの数学を用いて、問題を最適にする解は何かを探索します。題材は、線形計画法と組合せ最適問題の二つです。
シェルスクリプトマガジン Vol.94は以下のリンク先でご購入できます。
図3 図1の問題を解くPythonコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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コード
|
1 2 3 4 5 6 7 |
（略） # ソルバーの定義 solver = pywraplp.Solver.CreateSolver('CBC') # 変数の準備 x = solver.IntVar(0, solver.infinity(), 'x') y = solver.IntVar(0, solver.infinity(), 'y') （略） |
図6 データを準備するためのPythonコード
|
1 2 3 |
teachers = ['田中', '山本', '竹村', '飯島', '佐藤'] days = ['月', '火', '水', '木', '金'] periods = ['1限', '2限', '3限', '4限'] |
図7 lessons連想配列を作成するPythonコード
|
1 2 3 |
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 2 3 4 5 6 7 |
{('田中', '月', '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コード
|
1 2 3 |
for d in days: for p in periods: model.Add(sum(lessons[(t, d, p)] for t in teachers) == 1) |
図10 「先生は1日に1コマだけ授業を担当する」制約条件を与えるPythonコード
|
1 2 3 |
for t in teachers: for d in days: model.Add(sum(lessons[(t, d, p)] for p in periods) <= 1) |
図11 「担当時間数に偏りが出ないように配置する」制約条件を与えるPythonコード
|
1 2 3 |
for t in teachers: model.Add(sum(lessons[(t, d, p)] \ for d in days for p in periods) == 4) |
図12 requests連想配列を定義するコードの例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
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コード
|
1 2 3 |
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コード
|
1 2 3 4 5 6 7 8 |
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コード
|
1 2 3 |
for t in teachers: model.Add(sum(lessons[(t, d, p)]*requests[t][d][p] \ for d in days for p in periods) >= 3) |