NetworkX⑤（最小カット問題）

NetworkXを、使って 最小カット問題 を解いてみます。

最小カット問題

グラフに対してｓからｔへのパスが存在しなくなるために除去しなければいけない辺の 容量の和の最小値 を求める問題を 最小カット問題 といいます。

前回記事で使ったグラフをもう一度作成します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import networkx as nx

G = nx.DiGraph()

#(始点，終点，重み)でエッジを設定
G.add_edges_from([('s', '1', dict(capacity=10)),
                  ('s', '2', dict(capacity=2)),
                  ('1', '2', dict(capacity=6)),
                  ('1', '3', dict(capacity=6)),
                  ('3', '2', dict(capacity=3)),
                  ('2', 't', dict(capacity=5)),
                  ('3', 't', dict(capacity=8)),
])

#エッジラベルの描画時に'capacity'の表示を無くすための工夫
edge_labels = {(i, j): w['capacity'] for i, j, w in G.edges(data=True)}
pos = nx.spring_layout(G, k=10)
nx.draw_networkx_edge_labels(G,pos, edge_labels=edge_labels)

# グラフの描画
nx.draw_networkx(G, pos)

[実行結果]

解法

最小カット問題 を解くためには、minimum_cut関数 を使います。

引数には、グラフオブジェクト、始点ノード、終了ノード を設定します。

[Google Colaboratory]

1
2
3
4
5
cut_value, partition = nx.minimum_cut(G, 's', 't')
print(f'cut value: {cut_value}')

S, T = partition
print(f'  (S, T): ({S}, {T})')

[実行結果]

cut value: 11

  (S, T): ({'1', '2', 's'}, {'3', 't'})

始点側のノードの集合は {‘1’, ‘2’, ‘s’} で、終点側の集合は {‘3’, ‘t’} となりました。

この集合２つをつなぐエッジ（辺）の容量の和は 11 であり、これが最小となります。

最小カット問題 の解は 最大流問題 と解は同じとなり、最大流最小カット定理 と呼ばれます。

NetworkX④（最大流問題）

NetworkXを、使って 最大流問題 を解いてみます。

最大流問題

グラフ間に流れる数値を最大化させる問題を 最大流問題 といいます。

[最大流問題の例]

ネットワーク上の２台のコンピュータｓ、ｔがありｓからｔにデータを送ります。

このネットワークには全部でＮ台のコンピュータがあり、いくつかのコンピュータ間は一方向性の

通信ケーブルで接続されていて、それぞれ１秒間に通信できる最大のデータ量が決まってきます。

ｓからｔへ１秒間で最大どれだけのデータを送信することができるでしょうか。

まず、ネットワーク上のコンピュータとデータ量をグラフに表示してみます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import networkx as nx

G = nx.DiGraph()

#(始点，終点，重み)でエッジを設定
G.add_edges_from([('s', '1', dict(capacity=10)),
                  ('s', '2', dict(capacity=2)),
                  ('1', '2', dict(capacity=6)),
                  ('1', '3', dict(capacity=6)),
                  ('3', '2', dict(capacity=3)),
                  ('2', 't', dict(capacity=5)),
                  ('3', 't', dict(capacity=8)),
])

#エッジラベルの描画時に'capacity'の表示を無くすための工夫
edge_labels = {(i, j): w['capacity'] for i, j, w in G.edges(data=True)}
pos = nx.spring_layout(G, k=10)
nx.draw_networkx_edge_labels(G,pos, edge_labels=edge_labels)

# グラフの描画
nx.draw_networkx(G, pos)

[実行結果]

解法

最大流問題 を解くためには、maximum_flow関数 を使います。

引数には、グラフオブジェクト、始点ノード、終了ノードを設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
flow_value, flows = nx.maximum_flow(G, 's', 't')
print(f'maximum flow: {flow_value}')

caps = nx.get_edge_attributes(G, 'capacity')
for u in nx.topological_sort(G):
    for v, flow in sorted(flows[u].items()):
        print(f'  ({u}, {v}): {flow}/{caps[(u, v)]}')

[実行結果]

maximum flow: 11

  (s, 1): 9/10

  (s, 2): 2/2

  (1, 2): 3/6

  (1, 3): 6/6

  (3, 2): 0/3

  (3, t): 6/8

  (2, t): 5/5

ｓからｔへの最大流は 11 と導き出すことができました。

また、最大流が流れる際に各ノード間に流すデータ通信も表示しています。

NetworkX③（パス／閉路／放射状の描画）

NetworkX を使っていろいろなタイプの描画を行ってみます。

パス

まずは パス を描画します。

add_path関数 に複数のノード番号を設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 指定したパス上の頂点と辺を追加
nx.add_path(G, [1, 2, 3, 4, 5])  # 1 → 2 → 3 → 4 → 5

nx.draw_networkx(G)

[実行結果]

順番に ノードを辿ったグラフ が描画されました。

閉路

次に 閉路 を描画します。

add_cycle関数 に複数のノード番号を設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 指定した閉路上の頂点と辺を追加
nx.add_cycle(G, [1, 2, 3, 4, 5])  # 1 → 2 → 3 → 4 → 5 → 1

nx.draw_networkx(G)

[実行結果]

順番にノード番号を辿り、最後のノードから最初の番号に戻る 閉路グラフ を描画することができました。

放射状

最後に 放射線状 のグラフを描画します。

add_star関数 に複数のノード番号を設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 放射状に頂点と辺を追加
nx.add_star(G, [1, 2, 3, 4, 5])  # 1 → 2, 1 → 3, 1 → 4, 1 → 5

nx.draw_networkx(G)

[実行結果]

最初のノードから、２番目以降のノード全てにエッジのある 放射上のグラフ を描画することができました。

NetworkX②（ノード削除、エッジ削除）

ノード削除

今回はグラフからノードを削除してみます。

まずは、前回記事と同様のグラフを描画します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)                
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)     
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

[実行結果]

上記のグラフから、ノード（頂点）を削除してみます。

[Google Colaboratory]

1
2
3
# 頂点の削除 (削除された頂点に接続されている辺も削除されます)
G.remove_node(5)            # 頂点を１つ削除
G.remove_nodes_from([3, 4]) # 頂点を複数削除

[実行結果]

ノードが削除されました。

また削除されたモードに合わせてエッジも削除されていることが確認できます。

エッジ削除

今度はグラフからエッジを削除してみます。

まずグラフ図を描画します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)                
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)     
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

上記のグラフから、エッジ（辺）を削除してみます。

[実行結果]

[Google Colaboratory]

1
2
3
# # 辺の削除
G.remove_edge(3, 4)                   # 辺を１つ削除
G.remove_edges_from([(1, 3), (2, 5)]) # 辺を複数削除

[実行結果]

エッジ（辺）が削除されました。

NetworkX ①（グラフ描画）

NetworkX

NetworkX は、グラフ理論 や ネットワーク理論系の計算 を行うためのPythonパッケージです。

簡単にグラフが定義できたり，図を作ったりできます。

グラフは 頂点（ノード） と 辺（エッジ） で成り立っています。。

無向グラフ

辺に向きがないグラフを 無向グラフ といいます。

NetworkX を使って 無向グラフ を描いてみます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
import networkx as nx

G = nx.Graph()    # 無向グラフ

# 頂点の追加
G.add_node(1)
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

[実行結果]

有向グラフ

辺に向きがあるグラフを 有効グラフ といいます。

NetworkX を使って 有効グラフ を描いてみます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

[実行結果]

Union Find木を使って問題を解く②

Union Find木を使って問題を解く②

前前回記事で実装した Union Find木 を使って、下記の問題を解いてみます。

[問題]

Ｎ匹の動物がいて、１，２、・・・・Ｎと番号がつけられています。

動物はすべて３つの種類Ａ，Ｂ，Ｃのいずれかです。

ＡはＢと食べ、ＢはＣを食べ、ＣはＡを食べます。

そして次の２種類の情報が順番に与えられます。

　・タイプ１：ｘとｙは同じ種類です。

　・タイプ２：ｘはｙを食べます。

これらの情報はすべて 正しいとは限りません。

以前に与えられた情報と 矛盾する情報 や、ｘ、ｙが正しい番号でない ような間違った情報が与えられる可能性があります。

与えられた情報のうち、間違った情報の個数 を出力してください。

また間違った情報は捨てると考えます。

[条件]

・動物数Ｎは、1以上 50000以下

・与えられる情報の数は、0以上 100000以下

[解き方]
Union Find木 は、同じグループを管理するデータ構造ですが、この問題では同じ情報だけではなく 食べる という関係があります。

各動物ｉについて３つの要素 i-A、i-B、i-C をつくり、３×Ｎこの要素で Union Find木 を作成し、次のように考えます。

  • i-x は ｉが種類ｘである場合 を表す。
  • 各グループは、それらがすべて同時に起こることが分かっている。

例えば、i-A と j-B が同じグループである場合、ｉが種類Ａならばｊは必ず種類Ｂであり、ｊが種類Ｂならばｉはかならず種類Ａであることを表します。

そうするとそれぞれの情報について、以下を行えばよいことになります。

  • タイプ１：ｘとｙが同じ種類の場合
    x-Aとy-A、x-Bとy-B、x-Cとy-Cの３つのペアをグループ化する。
  • タイプ２：ｘがｙを食べる場合
    x-Aとy-B、x-Bとy-C、x-Cとy-Aの３つのペアをグループ化する。

また、それぞれグループ化する前に矛盾がおきているかどうかのチェックを行います。

[Google Colaboratory]

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
#-------------入力---------------
n = 100     # 動物の数
# ２種類のタイプ情報、動物１、動物２
info_lst = [{'type':1, 'x':101, 'y':1},
            {'type':2, 'x':1, 'y':2},
            {'type':2, 'x':2, 'y':3},
            {'type':2, 'x':3, 'y':3},
            {'type':1, 'x':1, 'y':3},
            {'type':2, 'x':3, 'y':1},
            {'type':1, 'x':5, 'y':5}]
#--------------------------------
uf = UnionFind(n * 3)
ans = 0

for info in info_lst:
    tp = info['type']
    x, y = info['x'] - 1, info['y'] - 1   # [1 ～ n ]の範囲を、[0 ～ n - 1 ]の範囲にする 

    # 動物の番号の範囲をチェック
    if x < 0 or x >= n or y < 0 or y >= n:
        print('動物番号の範囲チェックエラー', info)
        ans += 1
    else:
      if tp == 1:   # 同じ種類の場合
          if uf.same(x, y + n) or uf.same(x, y + n * 2):
              print('矛盾', info)
              ans += 1
          else:
              print('同じ種類としてグループ化', info)
              uf.union(x, y)
              uf.union(x + n, y + n)
              uf.union(x + n * 2, y + n * 2)
      else:         # xはyを食べる場合
          if uf.same(x, y) or uf.same(x, y + n * 2):
              print('矛盾', info)
              ans += 1
          else:
              print('食べられる種類としてグループ化', info)
              uf.union(x, y + n)
              uf.union(x + n, y + n * 2)
              uf.union(x + n * 2, y)

# print(uf.all_group_members())
# for group in uf.all_group_members():
#     members = uf.members(group)
#     if len(members) > 1:
#         print(members)
print()
print('答え', ans)

[実行結果]

動物番号の範囲チェックエラー {'type': 1, 'x': 101, 'y': 1}
食べられる種類としてグループ化 {'type': 2, 'x': 1, 'y': 2}
食べられる種類としてグループ化 {'type': 2, 'x': 2, 'y': 3}
矛盾 {'type': 2, 'x': 3, 'y': 3}
矛盾 {'type': 1, 'x': 1, 'y': 3}
食べられる種類としてグループ化 {'type': 2, 'x': 3, 'y': 1}
同じ種類としてグループ化 {'type': 1, 'x': 5, 'y': 5}

答え 3

１つめの情報は番号として間違っていて、４つめと５つめの情報は矛盾しているので、正解は３ということになります。

Union Find木を使って問題を解く

Union Find木を使って問題を解く

前回記事で実装した Union Find木 を使って、下記の問題を解いてみます。

[問題]

人 1 から 人 N までのN 人の人がいます。

「人Ai と人 Bi は友達である」という情報が M 個与えられます。

同じ情報が複数回与えられることもあります。

X と Y が友達、かつ、Y と Z が友達ならば、X と Z も友達です。

また、M 個の情報から導くことができない友達関係は存在しません。

いじわるな高橋君は、このN人をいくつかのグループに分け、全ての人について「同じグループの中に友達がいない」という状況を作ろうとしています。

最小でいくつのグループに分ければ良いでしょうか？

[条件]

・人数Nは、2以上 200000以下です。

・友達関係の数Mは、0以上 200000以下です。

・AiとBiは、1以上 N以下です。

・AiとBiは、異なる数字です。

[解き方]
Union Find木 を使って友達同士のグループを作ります。

同じグループの中に友達がいない 状況を作るためには、友達の数が一番多いグループの人数分グループ数に分ければよいことになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n = 5
lst = [(1, 2), (3, 4), (5, 1)]
#-----------入力２---------------
# n = 4
# lst = [(1, 2), (2, 1), (1, 2), (2, 1), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
#-----------入力３---------------
#n = 10
#lst = [(3, 1), (4, 1), (5, 9), (2, 6)]
#--------------------------------
uf = UnionFind(n)   # 前回記事で実装した「Union Find木」を使う

for l in lst:       # 友達関係から友達グループを作成する
    uf.union(l[0]-1, l[1]-1)

ans = 0             # 友達がいない状況をつくるためのグループ数
for g in uf.all_group_members().values():   # 友達グループごとにループ
    print(f'友達グループ', g)               # 友達グループのメンバー
    g_size = len(g)         # 友達の数
    # 友達の数が「友達がいない状況をつくるためのグループ数」より大きかったら
    if g_size > ans:
        ans = g_size        # グループ数に友達数を設定

print('答え =>', ans)

[実行結果（入力１の場合）]

友達グループ [0, 1, 4]
友達グループ [2, 3]
答え => 3

１つ目の友達グループが３人ともっとも人数が多いので、３グループに分ければよいことになります。

例えば｛0, 2｝｛1, 3｝｛4｝と分ければ、だれも友達がいないグループとなります。

[実行結果（入力２の場合）]

友達グループ [0, 1, 2, 3]
答え => 4

４人全員が友達なので、４グループに分けて全員をばらばらにする必要があります。

[実行結果（入力３の場合）]

友達グループ [0, 2, 3]
友達グループ [1, 5]
友達グループ [4, 8]
友達グループ [6]
友達グループ [7]
友達グループ [9]
答え 3

１つめの友達グループが３人ともっとも人数が多いので、３グループに分けます。

友達が２人の場合は、３グループのうちいずれかの２グループに振り分ければよいですし、友達がいない人は、３グループのどこに分けても友達関係はできません。

Union Find木

Union Find木

Union Find木 は、グループ分けを管理することができるデータ構造です。

次のようなことを効率的に行うことができます。

  • 要素aと要素bが同じグループに属しているかどうかをチェックする。
  • 要素aと要素bのグループを一つにまとめる。

グループ同士をまとめることはできますが、要素をグループから除いたり、グループを分けたりすることはできません。

Union Find木 を実現するためのクラスは以下のようになります。

[Google Colaboratory]

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
from collections import defaultdict

# n個の要素を0 ～ n - 1のインデックスで管理する
class UnionFind():
    def __init__(self, n):
        self.n = n                # 要素の数
        self.parents = [-1] * n   # 各要素の親要素の番号を格納するリスト

    def find(self, x):            # 要素[x]が属するグループの親を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):        # 要素[x]が属するグループと要素yが属するグループとを併合
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):            # 要素[x]が属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):         # 要素[x],要素[y]が同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):         # 要素[x]が属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):              # すべての親の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):        # グループの数を返す
        return len(self.roots())

    def all_group_members(self):  # 全グループの全要素を返す
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):  # printでの表示用。ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

動作確認

実装した Union Find木 の動作を確認してみます。

要素数5個（0,1,2,3,4）のUnion Find木を定義し、[0,1]のグループと[2,3,4]のグループに分けます。

[Google Colaboratory]

1
2
3
4
5
6
uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(3, 4)

print(uf)

[実行結果]

0: [0, 1]

2: [2, 3, 4]

２つのグループに分けることができました。

親の要素(一番もとになる要素)がグループのキーとなっていることが確認できます。

次に、要素1と要素3が所属するグループを調べてみます。

[Google Colaboratory]

1
2
print(uf.find(1))
print(uf.find(3))

[実行結果]

0

2

要素1がグループ0に所属し、要素3がグループ2に所属していることが分かりました。

今度は、要素0,要素2が同じグループに属するかどうかと、要素3,要素4が同じグループに属するかどうかを調べます。

[Google Colaboratory]

1
2
print(uf.same(0, 2))
print(uf.same(3, 4))

[実行結果]

False

True

要素0,要素2は違うグループであり、要素3,要素4は同じグループに属することを確認できました。

最後に、要素3が所属するグループの全要素を表示します。

[Google Colaboratory]

1
print(uf.members(3))

[実行結果]

[2, 3, 4]

要素3が所属するグループの全要素は、2,3,4であることが分かりました。

次回は、Union Find木 を使って問題を解いてみます。

線形計画問題（PuLP）

線形計画問題

線形計画問題 は、ある条件下での 領域の最大・最小 を求める問題です。

数理最適化ライブラリのPuLP を使うと、線形計画問題 を解くことができます。

[問題]

ある工場では製品 p と製品 q を製造しています。

製品 p と製品 q を製造するには原料 m と原料 n が必要で、次のような条件となっています。

・製品 p を１ｋｇ製造するには原料 m が１ｋｇ、原料 n が２ｋｇ必要。

・製品 q を１ｋｇ製造するには原料 m が３ｋｇ、原料 n が１ｋｇ必要。

・原料 m の在庫は３０ｋｇ、原料 n の在庫は４０ｋｇあります。

・単位量当たりの利益は、製品 p が１万円、製品 q が２万円です。

この条件で利益を最大にするためには、製品 p と製品 q をそれぞれ何ｋｇ製造すればよいでしょうか。

製品 p の製造量を x ｋｇ、と製品 q の製造量を y ｋｇとすると以下のように不等号をつかった式にまとめることができます。


x + 3y ≦ 30
2x + y ≦ 40
x ≧ 0、y ≧ 0


連立方程式との違いは、等号（==） が 不等号（≧、≦） になっている点です。



 ソースコード


上記の条件式をもとにソースコードを作成すると下記のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import pulp

# 第１引数は任意の名前、第２引数は最大化問題を解く指定
problem = pulp.LpProblem('Test', pulp.LpMaximize)

x = pulp.LpVariable('x')    # 製品pを製造する量。変数xをpulp.LpVariable関数を定義。
y = pulp.LpVariable('y')    # 製品qを製造する量。変数yをpulp.LpVariable関数を定義。

# 線形計画問題の条件式
problem += 1 * x + 3 * y <= 30
problem += 2 * x + 1 * y <= 40
problem += x >= 0
problem += y >= 0

problem += x + 2 * y        # 目的関数。最大化する式。

status = problem.solve()    # 数理モデルを解く

print('Status:', pulp.LpStatus[status])   # 結果
print('x =', x.value(), 'y =', y.value(), 'obj =', problem.objective.value()) # xとyの解と利益の関数値


[実行結果]

Status: Optimal

x = 18.0 y = 4.0 obj = 26.0




製品 p の製造量を １８ｋｇ、と製品 q の製造量を ４ｋｇとしたときに利益を最大にできることが導きだされました。


obj = 26.0 は最大化しようとした利益の関数値です。（15行目）


x + 2 * y = 26 となることが確認できます。

数理最適化ライブラリ（PuLP）

数理最適化

数理最適化ライブラリ PuLP を使って、連立一次方程式を解いてみます。

本来の数理最適化ライブラリの使い方とは少々異なりますが、数理モデルを初めて実装するにはとてもよい題材です。

[問題]

１個１２０円のリンゴと１個１５０円のミカンを合わせて１０個買ったら代金の合計が１４４０円でした。

リンゴとミカンをそれぞれ何個買ったでしょうか。

この問題は、リンゴの個数を x、ミカンの個数を y として連立一次方程式を立てることができます。

120x + 150y = 1440
x + y = 10



 ソースコード


まずは 数理最適化ライブラリ PuLP をインストールできます。

[Google Colaboratory]

1
!pip install pulp


連立一次方程式をソースコードにすると下記のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import pulp

# 第１引数は任意の名前、第２引数は最大化問題を解く指定（今回は連立一次方程式を解くのでとくに意味はない）
problem = pulp.LpProblem('Test', pulp.LpMaximize)

x = pulp.LpVariable('x')    # 変数xをpulp.LpVariable関数を定義
y = pulp.LpVariable('y')    # 変数yをpulp.LpVariable関数を定義

problem += 120 * x + 150 * y == 1440    # 連立一次方程式を定義
problem += x + y == 10                  # 連立一次方程式を定義

status = problem.solve()    # 数理モデルを解く

print('Status:', pulp.LpStatus[status])   # 結果
print('x =', x.value(), 'y =', y.value()) # xとyの解


[実行結果]

Status: Optimal
x = 2.0 y = 8.0




Optimal は、最適化計算をした結果最適解が得られたという意味です。


リンゴの個数は2、ミカンの個数は8となり、合わせて１０個 であり、代金の合計も １４４０円 で、連立一次方程式の解として正しいことが確認できます。
© 2026 Playing with Python All Rights Reserved.
Theme by hipaper