クラウドコンピューティング最適化問題 PuLP

クラウドコンピューティング最適化問題

クラウドコンピューティングにおけるサーバー配置問題を例にして、PuLPを用いて解いていきます。

サーバー配置問題とは、複数のクラウドサービスを提供するために必要なサーバーを、最小限のコストで配置する問題です。

ここでは、各サーバーのスペックと利用料金が既知であると仮定します。

[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
from pulp import *

# 問題設定
servers = ["Server1", "Server2", "Server3"]
spec = {"Server1": {"CPU": 4, "Memory": 16, "Storage": 500},
"Server2": {"CPU": 2, "Memory": 8, "Storage": 250},
"Server3": {"CPU": 8, "Memory": 32, "Storage": 1000}}
costs = {"Server1": 100, "Server2": 50, "Server3": 200}
demands = {"CPU": 10, "Memory": 32, "Storage": 800}

# モデル定義
prob = LpProblem("Server Allocation Problem", LpMinimize)

# 変数定義
servers_vars = LpVariable.dicts("Server", servers, lowBound=0, upBound=None, cat="Integer")

# 目的関数
prob += lpSum([costs[s] * servers_vars[s] for s in servers])

# 制約条件
for r in spec["Server1"].keys():
prob += lpSum([spec[s][r] * servers_vars[s] for s in servers]) >= demands[r]

# 解法
prob.solve()

# 結果出力
print("Total cost: {}".format(value(prob.objective)))
for s in servers:
print("{}: {}".format(s, value(servers_vars[s])))

このコードでは、各サーバーのスペックをspec、利用料金をcosts、要求スペックをdemandsとして定義し、PuLPを用いてモデルを定義しています。

変数として各サーバーの割り当てをservers_varsと定義し、目的関数と制約条件を設定した後にprob.solve()を実行することで最適解を求め、結果を出力しています。

[実行結果]

Total cost: 250.0

Server1: 0.0

Server2: 1.0

Server3: 1.0

この結果から、サーバー2サーバー3それぞれ1台使用することで、最小のコストで要求スペックを満たすことができることがわかります。

また、この最適解においてかかるコストは250となります。

医療最適化問題 PuLP

医療最適化問題

ある病院における輸血の最適化問題を考えてみましょう。

具患者に輸血を行う場合、その輸血に使用する血液の種類によって、患者に不適切な血液を投与してしまうリスクがあります。

このため、輸血に使用する血液の種類を適切に選択することが重要です。

この問題をPuLPを使って解くためには、以下のような手順を踏みます。

  1. 必要なパッケージをインポートします。

    1
    from pulp import *
  2. 問題を定義します。

    1
    2
    # 問題を定義
    prob = LpProblem('Blood_Transfusion', LpMinimize)
  3. 変数を定義します。

    1
    2
    3
    4
    # 変数を定義
    blood_type_A = LpVariable('Blood_Type_A', lowBound=0, cat='Integer')
    blood_type_B = LpVariable('Blood_Type_B', lowBound=0, cat='Integer')
    blood_type_O = LpVariable('Blood_Type_O', lowBound=0, cat='Integer')
  4. 目的関数を定義します。

    1
    2
    # 目的関数を定義
    prob += 10 * blood_type_A + 20 * blood_type_B + 30 * blood_type_O

各血液の種類について、そのコストを10, 20, 30としました。

血液の種類がAの場合には10のコスト、Bの場合には20のコスト、Oの場合には30のコストがかかるということになります。

  1. 制約条件を定義します。
    1
    2
    3
    4
    5
    # 制約条件を定義
    prob += blood_type_A + blood_type_B + blood_type_O >= 100
    prob += blood_type_A >= 20
    prob += blood_type_B >= 30
    prob += blood_type_O >= 40

病院で必要な総血液量が100であること、血液の種類Aが20以上必要であること、血液の種類Bが30以上必要であること、血液の種類Oが40以上必要であることを制約条件として定義しています。

  1. 最適化を実行します。

    1
    2
    # 最適化を実行
    prob.solve()
  2. 結果を表示します。

    1
    2
    3
    4
    5
    # 結果を表示
    print('Blood Type A: ', blood_type_A.value())
    print('Blood Type B: ', blood_type_B.value())
    print('Blood Type O: ', blood_type_O.value())
    print('Total Cost: ', value(prob.objective))

完全なソースコード

以上の手順をすべて組み合わせた完全なコードは次のようになります。

[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
from pulp import *

# 問題を定義
prob = LpProblem('Blood_Transfusion', LpMinimize)

# 変数を定義
blood_type_A = LpVariable('Blood_Type_A', lowBound=0, cat='Integer')
blood_type_B = LpVariable('Blood_Type_B', lowBound=0, cat='Integer')
blood_type_O = LpVariable('Blood_Type_O', lowBound=0, cat='Integer')

# 目的関数を定義
prob += 10 * blood_type_A + 20 * blood_type_B + 30 * blood_type_O

# 制約条件を定義
prob += blood_type_A + blood_type_B + blood_type_O >= 100
prob += blood_type_A >= 20
prob += blood_type_B >= 30
prob += blood_type_O >= 40

# 最適化を実行
prob.solve()

# 結果を表示
print('Blood Type A: ', blood_type_A.value())
print('Blood Type B: ', blood_type_B.value())
print('Blood Type O: ', blood_type_O.value())
print('Total Cost: ', value(prob.objective))

[実行結果]

Blood Type A:  30.0
Blood Type B:  30.0
Blood Type O:  40.0
Total Cost:  2100.0

この結果から、血液の種類Aが30、種類Bが30、種類Oが40必要であり、総コストが2100であることが確認できました。

音楽推薦最適化問題 PuLP

音楽推薦最適化問題

音楽推薦の最適化問題PuLPを用いて解く例題を以下に示します。

この問題では、複数の楽曲を聴取したユーザーが、各楽曲に対して評価を付けたデータを利用して、ユーザーに最適な楽曲の推薦リストを作成します。

推薦リストは、ユーザーが楽曲を聴取するためにかかる時間の合計を最小限に抑えるように決定します。

[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
# PuLPをインポートする
from pulp import *

# データを定義する
users = ['User 1', 'User 2', 'User 3', 'User 4']
songs = ['Song 1', 'Song 2', 'Song 3', 'Song 4']
ratings = {
('User 1', 'Song 1'): 3,
('User 1', 'Song 2'): 4,
('User 1', 'Song 3'): 5,
('User 1', 'Song 4'): 2,
('User 2', 'Song 1'): 5,
('User 2', 'Song 2'): 4,
('User 2', 'Song 3'): 2,
('User 2', 'Song 4'): 3,
('User 3', 'Song 1'): 4,
('User 3', 'Song 2'): 5,
('User 3', 'Song 3'): 3,
('User 3', 'Song 4'): 4,
('User 4', 'Song 1'): 2,
('User 4', 'Song 2'): 3,
('User 4', 'Song 3'): 4,
('User 4', 'Song 4'): 5
}
time_limits = {
'User 1': 60,
'User 2': 90,
'User 3': 120,
'User 4': 60
}

# 問題を定義する
prob = LpProblem("Music Recommendation", LpMinimize)

# 変数を定義する
x = LpVariable.dicts('x', [(u, s) for u in users for s in songs], cat='Binary')

# 目的関数を定義する
prob += lpSum([x[(u, s)] * ratings[(u, s)] for u in users for s in songs])

# 制約条件を追加する
for u in users:
prob += lpSum([x[(u, s)] for s in songs]) <= len(songs) // 2, f"User {u} - Song count"
prob += lpSum([x[(u, s)] * ratings[(u, s)] for s in songs]) >= 3, f"User {u} - Minimum rating"
prob += lpSum([x[(u, s)] * ratings[(u, s)] for s in songs]) <= 5, f"User {u} - Maximum rating"
prob += lpSum([x[(u, s)] * ratings[(u, s)] for s in songs]) * 5 <= time_limits[u], f"User

[実行結果]

Status: Optimal

Total rating: 12.0

User 1 recommendations: ['Song 1']

User 2 recommendations: ['Song 4']

User 3 recommendations: ['Song 3']

User 4 recommendations: ['Song 2']

この結果から、各ユーザーにおすすめする曲を決定することができます。

たとえば、User 1 には ‘Song 1’ をおすすめすることができます。

また、最適化問題の総合評価が 12 であることから、ユーザーが評価する曲の総合的な評価を最大化しつつ、制約条件を満たす最適な曲の選択を行っていることがわかります。

グラフ理論の例題 NetworkX

NetworkX

PythonのライブラリであるNetworkXは、グラフ理論を扱う際に便利なツールです。

このライブラリを使うことで、グラフ理論の様々な問題を解決することができます。

例えば、グラフの可視化グラフの検索グラフの解析などが挙げられます。

1. 最短経路を求める

以下のようなグラフがあるとします。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_edge('A', 'B', weight=4)
G.add_edge('A', 'C', weight=2)
G.add_edge('B', 'D', weight=5)
G.add_edge('C', 'D', weight=1)

nx.draw(G, with_labels=True)
plt.show()

[実行結果]

このグラフでは、ノード同士を結ぶエッジには重みが設定されています。

このグラフで、ノードAからノードDへの最短経路を求めるには、以下のコードを実行します。

[Google Colaboratory]

1
2
shortest_path = nx.shortest_path(G, source='A', target='D', weight='weight')
print("最短経路は", shortest_path, "です。")

このコードでは、nx.shortest_path()を用いて最短経路を求めています。

weight=’weight’を指定することで、エッジの重みを考慮した最短経路が求められます。

[実行結果]

最短経路は ['A', 'C', 'D'] です。

2. 最小全域木を求める

以下のようなグラフがあるとします。

[Google Colaboratory]

1
2
3
4
5
6
7
8
import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
G.add_weighted_edges_from([('A', 'B', 4), ('A', 'H', 8), ('B', 'C', 8), ('B', 'H', 11), ('C', 'D', 7), ('C', 'F', 4), ('C', 'I', 2), ('D', 'E', 9), ('D', 'F', 14), ('E', 'F', 10), ('F', 'G', 2), ('G', 'H', 1), ('G', 'I', 6), ('H', 'I', 7)])

nx.draw(G, with_labels=True)
plt.show()

[実行結果]

このグラフは、9つの頂点と14本の辺を持つ重み付きグラフです。

このグラフの最小全域木を求めるには、以下のコードを実行します。

[Google Colaboratory]

1
2
T = nx.minimum_spanning_tree(G)
print("最小全域木の辺は", T.edges(data=True), "です。")

このコードでは、nx.minimum_spanning_tree()を用いて最小全域木を求めています。

求められた最小全域木の辺は、辞書形式で返されます。

[実行結果]

最小全域木の辺は [('A', 'B', {'weight': 4}), ('A', 'H', {'weight': 8}), ('H', 'G', {'weight': 1}), ('C', 'I', {'weight': 2}), ('C', 'F', {'weight': 4}), ('C', 'D', {'weight': 7}), ('D', 'E', {'weight': 9}), ('F', 'G', {'weight': 2})] です。

まとめ

今回は、NetworkXを用いてグラフ理論の問題を解決する例題を2つ挙げてみました。

NetworkXは非常に豊富な機能を持っているため、様々な問題に対して適用することができます。

グラフ理論 NetworkX

NetworkX

NetworkXは、グラフ理論を用いた問題を解決するためのPythonライブラリです。

以下に、NetworkXで解決できる問題の例です。

🔹グラフの構築や可視化
🔹グラフの特徴量の計算(次数中心性、媒介中心性、近接中心性など)
🔹グラフの操作(ノードやエッジの追加・削除、グラフのサブグラフの抽出など)
🔹最短経路や最短距離の計算
🔹ネットワーク分析や社会ネットワーク分析の実行
🔹グラフの可視化やレイアウトの設定

これらの機能を使って、例えば以下のような問題を解決することができます。

🔹ソーシャルメディアのネットワーク分析による、情報拡散や影響力の分析
🔹輸送網や交通網の最適ルートの検索や交通量の分析
🔹電力網や水道網の効率的な運営のためのネットワーク解析
🔹化学反応のシミュレーションや、生物学的ネットワークの解析
🔹ウェブページのリンク構造の解析や、検索エンジンのランキングアルゴリズムの開発

なお、これらはあくまでも一例であり、グラフ理論が応用される領域は多岐に渡ります。

最短経路問題

最短経路問題とは、あるグラフ上で2つの頂点間の最短経路を求める問題です。

NetworkXライブラリには、最短経路を求めるための関数が用意されています。

以下は、最短経路を求める例として、グラフ上の2つの頂点の最短経路を求めるコードです。

[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
import networkx as nx
import matplotlib.pyplot as plt

# グラフの定義
G = nx.Graph()
G.add_edge(0, 1, weight=4)
G.add_edge(0, 2, weight=3)
G.add_edge(1, 3, weight=2)
G.add_edge(2, 3, weight=5)
G.add_edge(2, 4, weight=6)
G.add_edge(3, 4, weight=1)

# 最短経路の計算
shortest_path = nx.shortest_path(G, source=0, target=4, weight='weight')

# 結果の表示
print(f"The shortest path from node 0 to node 4 is: {shortest_path}")

# グラフの可視化
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, node_color='lightblue')
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_labels(G, pos)
edge_labels = {(u, v): d['weight'] for u, v, d in G.edges(data=True)}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.axis('off')
plt.show()

この例では、グラフGを定義して、nx.shortest_path()関数を使って、頂点0から頂点4までの最短経路を計算しています。

nx.shortest_path()関数は、グラフと、最短経路の始点と終点を指定する引数を取り、最短経路を表す頂点のリストを返します。


次に、計算結果を表示し、最後にグラフを可視化しています。

グラフの可視化には、matplotlibライブラリを使用しています。


nx.spring_layout()関数は、グラフのレイアウトを計算する関数であり、nx.draw_networkx_nodes()nx.draw_networkx_edges()nx.draw_networkx_labels()nx.draw_networkx_edge_labels()関数は、それぞれ、ノード、エッジ、ラベル、エッジラベルを描画するための関数です。

[実行結果]

エネルギー最適化問題 PuLP

問題

エネルギー最適化問題の例題として、以下のような問題を考えてみましょう。

🔹2つの発電所があり、それぞれ最大で100MW50MWの電力を供給できる。
🔹需要は150MWである。
🔹各発電所の発電コストは、1MWあたりそれぞれ10ドル20ドルである。
🔹目的は、発電コストを最小化することである。

解き方・ソースコード

PythonのPuLPライブラリを使用してこの問題を解いてみます。

[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
import pulp

# 問題を定義
problem = pulp.LpProblem('Optimization Problem', pulp.LpMinimize)

# 変数を定義
p1 = pulp.LpVariable('p1', lowBound=0, upBound=100, cat='Continuous')
p2 = pulp.LpVariable('p2', lowBound=0, upBound=50, cat='Continuous')

# 目的関数を定義
problem += 10*p1 + 20*p2, 'Total Cost'

# 制約条件を定義
problem += p1 + p2 >= 150, 'Demand'
problem += p1 <= 100, 'Capacity of Plant 1'
problem += p2 <= 50, 'Capacity of Plant 2'

# 問題を解く
problem.solve()

# 結果を出力
print(f'Optimal solution found with total cost of {problem.objective.value():.2f}')
print(f'Plant 1 generates {p1.value()} MW')
print(f'Plant 2 generates {p2.value()} MW')

まずpulpで問題を定義します。

その後、発電所1と発電所2の発電量を表す変数p1p2を定義します。


次に、目的関数を定義します。

この問題では、発電コストを最小化する必要があるため、変数p1とp2に対して、それぞれの発電コストを乗じて、総和をとります。


次に、制約条件を定義します。

この問題では、需要を満たす必要があるため、発電所1と発電所2の発電量の合計が150MW以上でなければなりません。

また、各発電所の発電量は、それぞれ最大で100MWと50MWでなければなりません。


最後に、problem.solve関数を使って最適解を出力します。

解には、発電所1と発電所2の発電量が含まれます。

[実行結果]

Optimal solution found with total cost of 2000.00

Plant 1 generates 100.0 MW

Plant 2 generates 50.0 MW

最適な発電コストは2000.00であり、その時の発電量は発電所1が100.0 MWであり、発電所2が50.0 MWであることが確認できました。

ポートフォリオ最適化 PuLP

問題

2つの投資先があり、投資先1の期待リターンは10%、リスクが5%、投資先2の期待リターンは15%、リスクが8%とします。

また、ポートフォリオの全体的なリスクは6%未満にしたいと考えています。


この2つの投資先に関して、最適なポートフォリオを計算してください。

解き方・ソースコード

PythonのPuLPライブラリを使用してこの問題を解いてみます。

[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
# 必要なライブラリをインポートする
import pulp

# 投資先とそれぞれの期待リターンとリスクを定義する
assets = ['Asset 1', 'Asset 2']
returns = {'Asset 1': 0.1, 'Asset 2': 0.15}
risks = {'Asset 1': 0.05, 'Asset 2': 0.08}

# 最適化問題を定義する
prob = pulp.LpProblem('Portfolio Optimization', pulp.LpMaximize)

# 投資先の割合を決定する変数を作成する
weights = pulp.LpVariable.dicts('Weight', assets, lowBound=0, upBound=1)

# 目的関数を設定する
prob += pulp.lpSum([weights[a] * returns[a] for a in assets])

# 制約条件を設定する
prob += pulp.lpSum([weights[a] for a in assets]) == 1
prob += pulp.lpSum([weights[a] * risks[a] for a in assets]) <= 0.06

# 最適化問題を解く
prob.solve()

# 結果を表示する
print('Optimal Portfolio:')
for a in assets:
print('{}: {:.2%}'.format(a, weights[a].value()))

print('Expected Return: {:.2%}'.format(pulp.value(prob.objective)))
print('Risk: {:.2%}'.format(pulp.lpSum([weights[a] * risks[a] for a in assets]).value()))

このソースコードでは、投資先の割合を決定する変数を作成し、目的関数を最大化するように設定し、制約条件を設定しています。

最後に、prob.solve()を呼び出して問題を解決し、結果を表示しています。

[実行結果]

Optimal Portfolio:

Asset 1: 66.67%

Asset 2: 33.33%

Expected Return: 11.67%

Risk: 6.00%

投資先1に66.67%、投資先2に33.33%を割り当てると最適なポートフォリオとなり、期待リターンは11.67%、リスクは6.00%であることが確認できました。

ボードゲーム

問題

$1$ から $N$ までの整数が一個ずつ書かれた $ N \times N $ のマス目 $P$ が与えられます。

次の2種類の操作を繰り返すことで、すべての $k$ に対して「整数 $k$ が上から $k$ 行目・左から $k$ 列目のマスに存在する」ようにするためには、最小何回の操作が必要ですか。

🔹隣接する2つの行を交換する。
🔹隣接する2つの列を交換する。

[制約]
🔹$ 2 \leqq N \leqq 100 $

解き方・ソースコード

まず行の操作と列の操作を分解できないかどうかを考えます。

$i$ 行目に書かれた唯一の整数を $X_i$、$j$ 列目に書かれた唯一の整数を $Y_j$ とすると、以下の2点が成り立ちます。

🔹$i$行目と $i+1$ 行目を交換した場合: $X_i$ と $X_{i+1}$ のみが入れ替わり、$Y$ は不変
🔹$j$列目と $j+1$ 列目目を交換した場合: $Y_j$ と $Y_{j+1}$ のみが入れ替わり、$X$ は不変

このことは「行に対する操作」と「列に対する操作」を分けてよいことを意味しています。


また、目的通りの盤面になっていることと、$X=[1,2,3,4]$ かつ $Y=[1,2,3,4]$ になっていることはまったく同じです。

したがって、入力例1の最小操作回数は

🔹値1:最小何回の「隣接要素の交換」で、配列 $X$ を $[1,2,3,4]$ にできるか。
🔹値2:最小何回の「隣接要素の交換」で、配列 $Y$ を $[1,2,3,4]$ にできるか。

総和となります。

[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
#-------- 入力例1 ---------
N = 4 # 整数の数
P = [
[0, 0, 2, 0],
[3, 0, 0, 0],
[0, 0, 0, 4],
[0, 1, 0, 0],
]
#---------------------------
# 「交換数を求める問題」2 つに分解する
X = [ None ] * N
Y = [ None ] * N
for i in range(N):
for j in range(N):
if P[i][j] != 0:
X[i] = P[i][j]
Y[j] = P[i][j]

# 交換数を求める関数
def inversion(A):
answer = 0
for i in range(len(A)):
for j in range(i + 1, len(A)):
if A[i] > A[j]:
answer += 1
return answer

# 答えを出力
print('解:', inversion(X) + inversion(Y))

[実行結果]

解: 5

最小操作回数が5回であることが確認できました。

数理解析モデル PuLP

PuLPとは

PuLPはPythonで書かれたオープンソースの線形および整数計画問題を解くためのモデリングライブラリです。

PuLPは、Pythonで線形最適化問題を解決するための高水準のインターフェースを提供し、制約条件、目的関数、変数を自然な形式で定義できます。

PuLPは、商用および非商用のプロジェクトで使用できます。

PuLPを使用することで、複雑な最適化問題を簡単に定式化および解決できるようになります。

これにより、様々な業界や分野で問題解決の効率が向上し、効果的な意思決定が可能になります。

問題

以下は、、PuLPを使用して解くことができる簡単な整数計画問題のサンプルです。

この問題では、変数 $x$ と $y$ を定義し、以下の制約条件を満たしながら目的関数を最大化することが目的です。

【目的関数】
🔹$ 3x + 4y $

【制約条件】
🔹$ 2x + y \leqq 20 $
🔹$ 4x - 5y \geqq -10 $
🔹$ x + 2y \leqq 14 $
🔹$x, y$は非負の整数である

ソースコード

[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
import pulp

# 問題の定義
problem = pulp.LpProblem('Simple Integer Programming Problem', pulp.LpMaximize)

# 変数の定義
x = pulp.LpVariable('x', lowBound=0, cat='Integer')
y = pulp.LpVariable('y', lowBound=0, cat='Integer')

# 目的関数の定義
problem += 3*x + 4*y, 'Objective Function'

# 制約条件の定義
problem += 2*x + y <= 20, 'Constraint 1'
problem += 4*x - 5*y >= -10, 'Constraint 2'
problem += x + 2*y <= 14, 'Constraint 3'

# 最適化の実行
problem.solve()

# 結果の出力
print(f'Status: {pulp.LpStatus[problem.status]}')
print(f'Optimal Solution: {pulp.value(problem.objective)}')
print(f'x: {pulp.value(x)}')
print(f'y: {pulp.value(y)}')

まず、problemオブジェクトを作成します。

このオブジェクトは、数理最適化問題のモデルを表します。

ここでは、問題名と最大化を指定しています。


次に、変数$x$変数$y$を定義します。

ここでは、下限が0の整数変数であることを指定しています。

目的関数は、$ problem += 3 * x + 4 * y $ と定義されています。

この問題では、この目的関数を最大化することが目的です。


制約条件は、それぞれ以下のように定義されています。

🔹制約1: $ 2 * x + y <= 20 $
🔹制約2: $ 4 * x - 5 * y >= -10 $
🔹制約3: $ x + 2 * y <= 14 $


最後に、problem.solve()を呼び出すことで、問題を解きます。

pulp.LpStatus[problem.status]を使用すると、解の状態を表示することができます。

また、pulp.value()を使用することで、最適解の目的関数の値変数$x$と$y$の値を表示することができます。

[実行結果]

Status: Optimal
Optimal Solution: 36.0
x: 8.0
y: 3.0

最適解は、x=8, y=3であり、目的関数の値は36となっています。

制約条件を満たしながら、目的関数の最大値を得ることができました。

圧縮

問題

配列 $A=[A_1, A_2, … , A_N]$ が与えられます。

大小関係を崩さないように、配列をできるだけ圧縮してください。

ここでの圧縮とは、以下の条件を全て満たす配列 $B=[B_1, B_2, … , B_N]$ を求める操作です。

なお、このような配列 $B$ は1通りに決まります。

🔹条件1 $B_1,B_2, … , B_N$ は1以上の整数である。
🔹条件2 $A_i < A_j$ であるような組 $(i,j)$ については、$B_i<B_j$ である。
🔹条件3 $A_i = A_j$ であるような組 $(i,j)$ については、$B_i=B_j$ である。
🔹条件4 $A_i > A_j$ であるような組 $(i,j)$ については、$B_i>B_j$ である。
🔹条件5 条件1~条件4を満たす中で、配列 $B$ の最大値をできるだけ小さくする。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq A_i \leqq 10^9 $

解き方

この問題はソートして重複を消す方法で解くことができます。


手順は以下の通りです。

1.配列 $A$ を昇順にソートします。
2.ソート後の配列 $A$ について、重複を除いた配列 $C$ を作成します。
3.配列 $C$ の要素に対して、$C_i$ が元の配列 $A$ の何番目の要素であったかを示す配列 $P$ を作成します。
  つまり、$A_{P_i} = C_i$ となるような配列 $P$ を作成します。
4.配列 $B$ を用意し、$B_i$ を $P_i$ 番目の要素とすることで、配列 $B$ を求めます。

この方法で求められる配列 $B$ も、与えられた条件を満たす圧縮された配列となります。

ソースコード

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#-------- 入力例1 ---------
N = 5 # 整数の数
A = [46, 80, 11, 36, 46] # 配列A
#---------------------------
import bisect

# 配列 T の作成(重複も消す)
T = list(set(A))
T.sort()

# 答えを求める
B = [None] * N
for i in range(N):
B[i] = bisect.bisect_left(T, A[i])
B[i] += 1

# 答え
print("解:", [str(i) for i in B])

このコードは、配列 $A$ をできるだけ圧縮するために、配列 $T$ を作成し、各要素に対応する圧縮された値を求めるものです。


まず、配列 $T$ を作成するために、set()関数を使い、重複を消した後、list()関数でリスト化しています。

その後、sort()メソッドを使い、要素を昇順に並べ替えています。

この $T$ 配列は、$A$ 配列を圧縮するための目印となるもので、条件2と3において、大小関係を崩さずに圧縮することができます。


次に、None で初期化した $B$ 配列を作成します。その後、for ループを用いて、配列 $A$ の各要素に対応する圧縮された値を求めます。

この圧縮された値は、配列 $T$ の中で、$A_i$ が何番目に小さいかを示しています。

bisect_left() 関数を使うことで、$A_i$ が $T$ 配列の中でどの位置にあるかを求めています。

bisect_left() 関数は、二分探索を行い、挿入するべきインデックスを返す関数です。

ここで、返される値は、$0$ から始まるため、$+1$ する必要があります。


最後に、$B$ 配列を表示して終了となります。


このコードは、時間計算量 $O(N \log N)$ で、与えられた条件を満たす圧縮された配列 $B$ を求めています。

[実行結果(入力例1)]

解: ['3', '4', '1', '2', '3']