Python - 線形計画法（シンプレックス法）！
Updated:
今回は、線形計画法を「シンプレックス法」で解くアルゴリズムを Python3 で実装してみました。
0. 前提条件
- LMDE 2 (Linux Mint Debian Edition 2; 64bit) での作業を想定。
- Python 3.6.4 での作業を想定。
- 当方は他のバージョンとの共存環境であり、
python3.6,pip3.6で 3.6 系を使用するようにしている。（適宜、置き換えて考えること）
1. アルゴリズムについて
当ブログ過去記事を参照。
2. Python スクリプトの作成
- 敢えてオブジェクト指向で作成している。
- Shebang ストリング（1行目）では、フルパスでコマンド指定している。（当方の慣習）
- 数値計算ライブラリ NumPy は使用しない。（この程度の行列計算は List で充分）
- 必要であれば、スクリプト内の定数を変更する。（実装したい線形計画法に合わせて）
File: linear_programming_simplex.py
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#! /usr/local/bin/python3.6
"""
Linear programming with Simplex method
"""
import sys
import traceback
class LinearProgrammingSimplex:
N_ROW = 4 # Number of rows
N_COL = 6 # Number of columns
N_VAR = 2 # Number of variants
def __init__(self):
self.a = [
[ 1.0, 2.0, 1.0, 0.0, 0.0, 14.0],
[ 1.0, 1.0, 0.0, 1.0, 0.0, 8.0],
[ 3.0, 1.0, 0.0, 0.0, 1.0, 18.0],
[-2.0, -3.0, 0.0, 0.0, 0.0, 0.0]
]
def exec(self):
""" Execution """
try:
while True:
mn, y = self.__select_col(9999)
if mn >= 0:
break
mn, x = self.__select_row(9999, y)
self.__divide_pivot_var(x, y)
self.__sweep_out(x, y)
self.__display()
except Exception as e:
raise
def __select_col(self, mn):
""" Column selection
:param float mn
:return list: [float, int]
"""
y = 0
try:
for k in range(self.N_COL - 1):
if self.a[self.N_ROW - 1][k] >= mn:
continue
mn, y = self.a[self.N_ROW - 1][k], k
return [mn, y]
except Exception as e:
raise
def __select_row(self, mn, y):
""" Row selection
:param float mn
:param int y
:return list: [float, int]
"""
x = 0
try:
for k in range(self.N_ROW - 1):
p = self.a[k][self.N_COL - 1] / self.a[k][y]
if self.a[k][y] <= 0 or p >= mn:
continue
mn, x = p, k
return [mn, x]
except Exception as e:
raise
def __divide_pivot_var(self, x, y):
""" Pivot coefficient division by p
:param int x
:param int y
"""
try:
p = self.a[x][y]
for k in range(self.N_COL):
self.a[x][k] /= p
except Exception as e:
raise
def __sweep_out(self, x, y):
""" Pivot sweeping out
:param int x
:param int y
"""
try:
for k in range(self.N_ROW):
if k == x:
continue
d = self.a[k][y]
for j in range(self.N_COL):
self.a[k][j] -= d * self.a[x][j]
except Exception as e:
raise
def __display(self):
""" Display """
try:
for k in range(self.N_VAR):
flag = -1
for j in range(self.N_ROW):
if self.a[j][k] == 1:
flag = j
v = 0.0 if flag == -1 else self.a[flag][self.N_COL - 1]
print("x{:d} = {:8.4f}".format(k, v))
z = self.a[self.N_ROW - 1][self.N_COL - 1]
print("z = {:8.4f}".format(z))
except Exception as e:
raise
if __name__ == '__main__':
try:
obj = LinearProgrammingSimplex()
obj.exec()
except Exception as e:
traceback.print_exc()
sys.exit(1)
3. Python スクリプトの実行
まず、実行権限を付与。
$ chmod +x linear_programming_simplex.py
そして、実行。
$ ./linear_programming_simplex.py
x0 = 2.0000
x1 = 6.0000
z = 22.0000
解が正しいこと確認する。
以上
Comments