産業プロセス最適化

産業プロセス最適化

産業プロセス最適化の例題として、混合飲料工場の原材料配合最適化問題を考えてみましょう。

この例では、原材料$A$、$B$、$C$を混ぜて飲料を作る際に、コストを最小化しつつ、必要な栄養成分を満たす配合を見つける問題を扱います。

問題設定

  1. 原材料の単価:

    • 原材料A: $3円/g$
    • 原材料B: $2円/g$
    • 原材料C: $1円/g$
  2. 栄養成分(各$100g$あたり):

    • 原材料A: タンパク質$10g$、脂質$5g$、炭水化物$15g$
    • 原材料B: タンパク質$5g$、脂質$10g$、炭水化物$5g$
    • 原材料C: タンパク質$2g$、脂質$4g$、炭水化物$20g$
  3. 必要な栄養成分量(最小限):

    • タンパク質: $30g$
    • 脂質: $20g$
    • 炭水化物: $50g$

目標

  • 総コストを最小化する原材料$A$、$B$、$C$の配合量を求める。

制約条件

  • 各原材料の配合量は非負($>= 0$)
  • 栄養成分量の制約を満たすこと

最適化モデル

この問題は線形計画法(Linear Programming, LP)を使って解くことができます。

Pythonでは scipy.optimize.linprog を用いることで簡単に解くことができます。

コード例

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
import numpy as np
from scipy.optimize import linprog

# 原材料の単価
cost = np.array([3, 2, 1])

# 栄養成分マトリックス (各行が原材料、各列が栄養成分: [タンパク質, 脂質, 炭水化物])
nutrition = np.array([
[10, 5, 15], # 原材料A
[5, 10, 5], # 原材料B
[2, 4, 20] # 原材料C
])

# 必要な栄養成分量
requirements = np.array([30, 20, 50])

# 線形計画法の実行
result = linprog(c=cost, A_ub=-nutrition.T, b_ub=-requirements, bounds=(0, None), method='highs')

# 結果の表示
if result.success:
print("最適な配合量:")
print(f"原材料A: {result.x[0]:.2f} g")
print(f"原材料B: {result.x[1]:.2f} g")
print(f"原材料C: {result.x[2]:.2f} g")
print(f"総コスト: {result.fun:.2f} 円")
else:
print("解が見つかりませんでした")

実行結果の解釈

このコードを実行すると、原材料$A$、$B$、$C$の最適な配合量とそのときの総コストが表示されます。

これにより、工場が最もコスト効率の良い方法で必要な栄養成分を満たすことができます。

最適化の結果は以下の通りです:

最適な配合量

  • 原材料A: $2.67 g$
  • 原材料B: $0.52 g$
  • 原材料C: $0.37 g$

総コスト

  • $9.41 円$

これにより、工場は総コストを$9.41$円に抑えつつ、必要な栄養成分(タンパク質$30g$、脂質$20g$、炭水化物$50g$)を満たすことができます。

この配合が最適な解となります。

Privacy Policy

Privacy Policy

This privacy policy applies to the Piano BGM app (hereby referred to as “Application”) for mobile devices that was created by (hereby referred to as “Service Provider”) as a Free service. This service is intended for use “AS IS”.

Information Collection and Use

The Application collects information when you download and use it. This information may include information such as

  • Your device’s Internet Protocol address (e.g. IP address)
  • The pages of the Application that you visit, the time and date of your visit, the time spent on those pages
  • The time spent on the Application
  • The operating system you use on your mobile device

The Application does not gather precise information about the location of your mobile device.

The Application collects your device’s location, which helps the Service Provider determine your approximate geographical location and make use of in below ways:

  • Geolocation Services: The Service Provider utilizes location data to provide features such as personalized content, relevant recommendations, and location-based services.
  • Analytics and Improvements: Aggregated and anonymized location data helps the Service Provider to analyze user behavior, identify trends, and improve the overall performance and functionality of the Application.
  • Third-Party Services: Periodically, the Service Provider may transmit anonymized location data to external services. These services assist them in enhancing the Application and optimizing their offerings.

The Service Provider may use the information you provided to contact you from time to time to provide you with important information, required notices and marketing promotions.

For a better experience, while using the Application, the Service Provider may require you to provide us with certain personally identifiable information. The information that the Service Provider request will be retained by them and used as described in this privacy policy.

Third Party Access

Only aggregated, anonymized data is periodically transmitted to external services to aid the Service Provider in improving the Application and their service. The Service Provider may share your information with third parties in the ways that are described in this privacy statement.

Please note that the Application utilizes third-party services that have their own Privacy Policy about handling data. Below are the links to the Privacy Policy of the third-party service providers used by the Application:

The Service Provider may disclose User Provided and Automatically Collected Information:

  • as required by law, such as to comply with a subpoena, or similar legal process;
  • when they believe in good faith that disclosure is necessary to protect their rights, protect your safety or the safety of others, investigate fraud, or respond to a government request;
  • with their trusted services providers who work on their behalf, do not have an independent use of the information we disclose to them, and have agreed to adhere to the rules set forth in this privacy statement.

Opt-Out Rights

You can stop all collection of information by the Application easily by uninstalling it. You may use the standard uninstall processes as may be available as part of your mobile device or via the mobile application marketplace or network.

Data Retention Policy

The Service Provider will retain User Provided data for as long as you use the Application and for a reasonable time thereafter. If you’d like them to delete User Provided Data that you have provided via the Application, please contact them at angularity@msn.com and they will respond in a reasonable time.

Children

The Service Provider does not use the Application to knowingly solicit data from or market to children under the age of 13.

The Application does not address anyone under the age of 13. The Service Provider does not knowingly collect personally identifiable information from children under 13 years of age. In the case the Service Provider discover that a child under 13 has provided personal information, the Service Provider will immediately delete this from their servers. If you are a parent or guardian and you are aware that your child has provided us with personal information, please contact the Service Provider (angularity@msn.com) so that they will be able to take the necessary actions.

Security

The Service Provider is concerned about safeguarding the confidentiality of your information. The Service Provider provides physical, electronic, and procedural safeguards to protect information the Service Provider processes and maintains.

Changes

This Privacy Policy may be updated from time to time for any reason. The Service Provider will notify you of any changes to the Privacy Policy by updating this page with the new Privacy Policy. You are advised to consult this Privacy Policy regularly for any changes, as continued use is deemed approval of all changes.

This privacy policy is effective as of 2024-06-18

Your Consent

By using the Application, you are consenting to the processing of your information as set forth in this Privacy Policy now and as amended by us.

Contact Us

If you have any questions regarding privacy while using the Application, or have questions about the practices, please contact the Service Provider via email at angularity@msn.com.


Rastrigin関数

Rastrigin関数

Rastrigin関数の最小化を考えます。

Rastrigin関数は、多次元の最適化問題でよく使われる非線形かつ非凸な関数で、複数の局所最小値を持つため、グローバル最適化の良い例題です。

Rastrigin関数の定義は以下の通りです:

$$
f(\mathbf{x}) = An + \sum_{i=1}^{n} \left[ x_i^2 - A \cos(2 \pi x_i) \right]
$$

ここで、通常$ ( A = 10 ) $で、$ ( n ) $は次元数です。

この関数のグローバル最小値は$ (\mathbf{x} = \mathbf{0}) $であり、そのときの関数値は$0$です。

プログラム例

以下は、PythonRastrigin関数を最適化するためのコードです。

scipy.optimizeモジュールのdual_annealing関数を使用してグローバル最適化を行います。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import numpy as np
from scipy.optimize import dual_annealing

# Rastrigin関数の定義
def rastrigin(x):
A = 10
return A * len(x) + sum([(xi**2 - A * np.cos(2 * np.pi * xi)) for xi in x])

# 最適化の設定
bounds = [(-5.12, 5.12) for _ in range(2)] # 2次元のRastrigin関数

# dual_annealingによる最適化
result = dual_annealing(rastrigin, bounds)

# 結果の表示
print("最適化結果:")
print("最小値:", result.fun)
print("最適解:", result.x)
print("反復回数:", result.nit)

ソースコード解説

  1. 関数の定義

    • Rastrigin関数を定義します。
      この関数は入力ベクトル x に対して評価されます。
  2. 最適化の設定

    • 最適化する範囲(ここでは、各次元が ([-5.12, 5.12]) の範囲にあります)を設定します。
  3. dual_annealingによる最適化

    • SciPyのdual_annealing関数を使用して、Rastrigin関数の最小値を求めます。
  4. 結果の表示

    • 最適化結果として、最小値最適解、および反復回数を表示します。

このコードを実行することで、Rastrigin関数のグローバル最小値を求めることができます。

Rastrigin関数の性質上、最適化アルゴリズムが局所最小値に陥らないようにするための良いテストケースとなります。

結果解説

[実行結果]

最適化結果:
最小値: 1.8474111129762605e-13
最適解: [-3.00458545e-08 -5.08182682e-09]
反復回数: 1000
  1. 最小値: 1.8474111129762605e-13

    • これはRastrigin関数の最小値で、最適化アルゴリズムが見つけた関数の評価値です。
      この値は非常に小さいことから、ほぼゼロに近いことを示しています。
      Rastrigin関数の理論的なグローバル最小値は$0$なので、この結果は非常に良い最適化が行われたことを示しています。
  2. 最適解: [-3.00458545e-08 -5.08182682e-09]

    • これは関数が最小値を取るときの入力ベクトル(解)です。
      ここで示されている値は、非常に小さい数値(ほぼゼロ)です。
      理論的な最適解はすべての変数がゼロのベクトル$ (\mathbf{0}) $なので、この結果は理論的な最適解に非常に近いことを示しています。
    • 具体的には、$ (-3.00458545 \times 10^{-8}) $と$ (-5.08182682 \times 10^{-9}) $はどちらもゼロに非常に近い値です。
  3. 反復回数: 1000

    • これは最適化アルゴリズムが終了するまでに行われた反復(イテレーション)の回数です。
      dual_annealingアルゴリズムが設定された最大の反復回数に達したことを示しています。
      最適化が成功し、非常に小さい最小値を見つけた一方で、アルゴリズムは最大反復回数まで探索を続けました。

最適化アルゴリズムと結果の評価

  • dual_annealing アルゴリズム:

    • これは焼きなまし法(Simulated Annealing)に基づくグローバル最適化アルゴリズムです。
      多くの局所最小値を持つ関数(非凸関数)の最適化に適しています。
    • このアルゴリズムは、温度を徐々に下げながら探索範囲を狭めていくことで、局所最小値に陥ることを防ぎつつ、グローバル最小値を探索します。
  • 結果の評価:

    • 最小値がほぼゼロであり、最適解が理論的な最適解(ゼロベクトル)に非常に近いことから、アルゴリズムは非常に効果的に動作したと評価できます。
    • 最大反復回数に達したものの、最適化の目的は十分に達成されたと考えられます。
      探索プロセスをさらに続ける必要はないでしょう。

まとめ

この結果は、Rastrigin関数の最小化においてdual_annealingアルゴリズムが有効に機能したことを示しています。

最適化アルゴリズムは、非常に小さな関数値と理論的な最適解に近い解を見つけることができました。

医療リソース最適化

医療リソース最適化

医療リソース最適化の問題を考え、Pythonで解いてみましょう。

ここでは、病院内のベッドの配分を最適化する問題を例にします。

具体的には、限られた数のベッドを複数の患者グループにどのように配分すれば、全体の患者満足度を最大化できるかを考えます。

問題設定

  • 病院には合計$ (N) $台のベッドがある。
  • 患者グループは$ (G) $グループあり、それぞれのグループには異なる数の患者がいる。
  • 各患者グループ$ (i) $の患者数は$ (P_i) $であり、満足度は$ (U_i) $で与えられる。
  • ベッドの割り当てを最適化して、患者満足度の総和を最大化する。

数理モデル

この問題は整数線形計画問題としてモデル化できます。

変数

  • $(x_i)$: 患者グループ$ (i) $に割り当てるベッドの数(整数)

目的関数

最大化する目的関数は全体の満足度の総和です。
$$
\text{maximize} \quad \sum_{i=1}^{G} U_i \cdot x_i
$$

制約条件

  • 各グループに割り当てるベッドの総数は病院のベッド数を超えてはいけません。
    $$
    \sum_{i=1}^{G} x_i \leq N
    $$
  • 各グループに割り当てるベッドの数は、そのグループの患者数を超えてはいけません。
    $$
    0 \leq x_i \leq P_i \quad \forall i
    $$

Python実装

Pythonでこの問題を解くために、数理最適化ライブラリである PuLP を使用します。

まず、必要なライブラリをインストールします。

1
pip install pulp

次に、以下のPythonコードを実行します。

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

# パラメータの設定
N = 50 # 病院のベッド数
P = [10, 20, 30, 40] # 各患者グループの患者数
U = [5, 4, 3, 2] # 各患者グループの満足度
G = len(P) # 患者グループの数

# 問題の定義
problem = pulp.LpProblem("Bed_Allocation_Optimization", pulp.LpMaximize)

# 変数の定義
x = [pulp.LpVariable(f"x{i}", lowBound=0, upBound=P[i], cat='Integer') for i in range(G)]

# 目的関数の設定
problem += pulp.lpSum([U[i] * x[i] for i in range(G)]), "Total_Satisfaction"

# 制約条件の設定
problem += pulp.lpSum(x) <= N, "Total_Beds_Constraint"
for i in range(G):
problem += x[i] <= P[i], f"Patient_Group_{i}_Constraint"

# 問題の解決
problem.solve()

# 結果の表示
print(f"Status: {pulp.LpStatus[problem.status]}")
for i in range(G):
print(f"Group {i + 1}: Allocate {x[i].varValue} beds")

print(f"Total Satisfaction: {pulp.value(problem.objective)}")

# 結果の可視化
import matplotlib.pyplot as plt

allocated_beds = [x[i].varValue for i in range(G)]
group_labels = [f"Group {i + 1}" for i in range(G)]

plt.bar(group_labels, allocated_beds)
plt.xlabel("Patient Groups")
plt.ylabel("Allocated Beds")
plt.title("Optimal Bed Allocation")
plt.show()

結果の説明

このコードは、病院のベッド配分問題を整数線形計画問題としてモデル化し、最適なベッド配分を求めます。

最後に、各患者グループに割り当てられたベッドの数と、合計の患者満足度を表示し、グラフで可視化します。

[実行結果]

ソースコード解説

1. 必要なライブラリのインポート

1
2
import pulp
import matplotlib.pyplot as plt
  • pulp は線形計画法(LP)を解くためのライブラリです。
  • matplotlib.pyplot はグラフの描画に使用されます。

2. パラメータの設定

1
2
3
4
N = 50  # 病院のベッド数
P = [10, 20, 30, 40] # 各患者グループの患者数
U = [5, 4, 3, 2] # 各患者グループの満足度
G = len(P) # 患者グループの数
  • N は病院の総ベッド数です。
  • P は各患者グループの患者数を表します。
  • U は各患者グループの満足度を表します。
  • G は患者グループの数です。

3. 問題の定義

1
problem = pulp.LpProblem("Bed_Allocation_Optimization", pulp.LpMaximize)
  • ここでは、問題を「Bed_Allocation_Optimization」という名前で定義し、目的が最大化(満足度の合計)であることを指定しています。

4. 変数の定義

1
x = [pulp.LpVariable(f"x{i}", lowBound=0, upBound=P[i], cat='Integer') for i in range(G)]
  • 各患者グループに割り当てるベッド数を表す変数 x[i] を定義します。
  • lowBound=0 は変数の下限を0に設定し、upBound=P[i] は各グループの患者数を上限とします。
  • cat='Integer' は変数が整数であることを指定しています。

5. 目的関数の設定

1
problem += pulp.lpSum([U[i] * x[i] for i in range(G)]), "Total_Satisfaction"
  • 各グループの満足度 U[i] に割り当てるベッド数 x[i] を掛け合わせた総和を目的関数として定義しています。
  • pulp.lpSum はリストの総和を計算します。

6. 制約条件の設定

1
2
3
problem += pulp.lpSum(x) <= N, "Total_Beds_Constraint"
for i in range(G):
problem += x[i] <= P[i], f"Patient_Group_{i}_Constraint"
  • pulp.lpSum(x) <= N は、全体のベッド数が N 以下であるという制約を設定します。
  • ループ内では、各グループのベッド割り当てがそのグループの患者数を超えないように制約を追加しています。

7. 問題の解決

1
problem.solve()
  • problem.solve() は定義された線形計画問題を解きます。

8. 結果の表示

1
2
3
4
print(f"Status: {pulp.LpStatus[problem.status]}")
for i in range(G):
print(f"Group {i + 1}: Allocate {x[i].varValue} beds")
print(f"Total Satisfaction: {pulp.value(problem.objective)}")
  • pulp.LpStatus[problem.status] は解のステータス(最適、不可解など)を表示します。
  • ループ内では各グループに割り当てられたベッド数を表示します。
  • pulp.value(problem.objective) は最適な満足度の合計を表示します。

9. 結果の可視化

1
2
3
4
5
6
7
8
allocated_beds = [x[i].varValue for i in range(G)]
group_labels = [f"Group {i + 1}" for i in range(G)]

plt.bar(group_labels, allocated_beds)
plt.xlabel("Patient Groups")
plt.ylabel("Allocated Beds")
plt.title("Optimal Bed Allocation")
plt.show()
  • allocated_beds は各グループに割り当てられたベッド数をリストにします。
  • group_labels は各グループのラベルを作成します。
  • plt.bar は棒グラフを作成します。
  • plt.xlabel, plt.ylabel, plt.title はグラフのラベルとタイトルを設定します。
  • plt.show() はグラフを表示します。

このスクリプトは、病院の限られたベッド数を最も効率的に配分することで患者満足度を最大化するための線形計画問題を解き、その結果を視覚化します。

結果解説

[実行結果]

最適なベッド配分

問題を解いた結果、以下のようなベッド配分が最適であることが示されました:

  • Group 1: $10$台のベッドを割り当てる
  • Group 2: $20$台のベッドを割り当てる
  • Group 3: $20$台のベッドを割り当てる
  • Group 4: ベッドを割り当てない

合計の満足度

各グループに割り当てたベッドの数に応じて、全体の満足度の合計は$190$となります。

詳細な解析

  • Group 1:
    このグループには$10$人の患者がいて、満足度は$5$です。
    ベッドを10台割り当てると、満足度は$ (10 \times 5 = 50) $になります。
  • Group 2:
    このグループには$20$人の患者がいて、満足度は$4$です。
    ベッドを$20$台割り当てると、満足度は$ (20 \times 4 = 80) $になります。
  • Group 3:
    このグループには$30$人の患者がいて、満足度は$3$です。
    ベッドを$20$台割り当てると、満足度は$ (20 \times 3 = 60) $になります。
  • Group 4:
    このグループには$40$人の患者がいて、満足度は$2$です。
    しかし、このグループにはベッドが割り当てられていないため、満足度は$0$です。

これらを合計すると、全体の満足度は$ (50 + 80 + 60 + 0 = 190) $になります。

Rosenbrock関数

Rosenbrock関数

Rosenbrock関数は、多変数関数の中でも特に最適化アルゴリズムの性能を評価するために広く使用されるベンチマーク関数の一つです。

この関数は、最小値を求めるための最適化問題において典型的な「谷」の形状を持つため、最適化アルゴリズムのテストに非常に適しています。

Rosenbrock関数の定義

Rosenbrock関数は次のように定義されます:

$$
f(x, y) = (a - x)^2 + b(y - x^2)^2
$$

ここで、$ ( a ) $と$ ( b ) $は定数です。
標準的には$ ( a = 1 ) $と$ ( b = 100 ) $がよく使われます。
この関数は2次元でもっともよく知られていますが、一般的には$ ( n ) $次元にも拡張できます。

主要な特徴

  1. 谷の形状

    • 関数の形状は、2次元平面上で見ると「谷」のような形をしています。
      これにより、関数の最小値を見つけるのが容易ではなく、アルゴリズムが谷の底に向かって進む必要があります。
  2. 非線形性

    • 関数は非線形であり、特に$ ( y ) $が$ ( x^2 ) $に依存しているため、複雑な形状を持ちます。
      これにより、局所最小値に陥る可能性が高くなります。
  3. グローバル最小値

    • 標準的な設定$(( a = 1 ), ( b = 100 ))$では、関数のグローバル最小値は$ ( (x, y) = (1, 1) )$ にあり、この点での関数値は$ ( f(1, 1) = 0 ) $です。

プログラム例

以下のコードは、この関数の3Dグラフを描画するPythonスクリプトです:

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
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

# Rosenbrock関数の定義
def rosenbrock(x, y, a=1, b=100):
return (a - x)**2 + b * (y - x**2)**2

# グリッドの作成
x = np.linspace(-2, 2, 400)
y = np.linspace(-1, 3, 400)
X, Y = np.meshgrid(x, y)
Z = rosenbrock(X, Y)

# プロットの設定
fig = plt.figure(figsize=(12, 8))
ax = fig.add_subplot(111, projection='3d')

# 3Dグラフの描画
ax.plot_surface(X, Y, Z, cmap='viridis', edgecolor='none')

# 軸ラベルの設定
ax.set_xlabel('X axis')
ax.set_ylabel('Y axis')
ax.set_zlabel('Z axis')
ax.set_title('3D Plot of the Rosenbrock Function')

# グラフの表示
plt.show()

このコードでは、次の手順を実行しています:

  1. Rosenbrock関数の定義

    • 関数 rosenbrock(x, y, a, b) を定義し、デフォルトの定数値$ (a=1) $と$ (b=100) $を使用します。
  2. グリッドの作成

    • $x$軸と$y$軸の範囲を設定し、それに基づいてメッシュグリッド XY を作成します。
  3. Rosenbrock関数の計算

    • メッシュグリッド XY に対して関数値 Z を計算します。
  4. プロットの設定

    • プロットの設定を行い、3Dグラフを描画します。
  5. 3Dグラフの描画

    • plot_surface を使って、3Dグラフを描画します。
    • カラーマップは viridis を使用し、エッジの色は表示しません。
  6. 軸ラベルとタイトルの設定

    • 軸ラベルとグラフのタイトルを設定します。
  7. グラフの表示

    • 最後に plt.show() を使ってグラフを表示します。

この3Dグラフは、Rosenbrock関数の形状を視覚的に示し、関数の複雑さを理解するのに役立ちます。

結果解説

[実行結果]

  • 形状

    • グラフの形状は、Rosenbrock関数の特性を反映しています。
      特に、グラフは「谷」を形成しており、最小値を中心に広がっています。
      この谷は最適化問題において重要で、最適化アルゴリズムがこの谷の最小値を見つけることを目指します。
  • 最小値

    • $( a = 1 ) $と$ ( b = 100 ) $の場合、Rosenbrock関数の最小値は$ ( (x, y) = (1, 1) ) $にあります。
      この点では関数値$ ( f(1, 1) = 0 ) $となります。
  • カラーマップ

    • viridis カラーマップは、関数値の違いを視覚的に強調します。
      高い値は黄色で、低い値は青で表示されます。
      これにより、関数の勾配極小値が視覚的に識別しやすくなります。

実行結果

このコードを実行すると、Rosenbrock関数の3Dプロットが表示され、関数の複雑な形状を視覚的に確認できます。

これにより、関数の特性と最適化の難しさを理解するのに役立ちます。

ビンパッキング問題 (Bin Packing Problem)

ビンパッキング問題 (Bin Packing Problem)

ビンパッキング問題 (Bin Packing Problem) は、異なるサイズのアイテムをできるだけ少ないビン(容器)に詰める問題です。

ここでは、具体的な例を示し、Pythonで解く方法を紹介します。

具体例

問題設定:

  • ビンの容量は$ 10 $とします。
  • 詰めるアイテムのサイズは$ [2, 5, 4, 7, 1, 3, 8] $です。

目的:

  • すべてのアイテムを収めるために必要なビンの数を最小化します。

Pythonでの解法

ビンパッキング問題を解くためのアルゴリズムの一つに、First-Fit Decreasing (FFD) 法があります。

この方法では、アイテムを大きい順に並べ替え、各アイテムを順番に最初に収まるビンに詰めていきます。

以下に、FFD法を用いてこの問題を解くPythonコードを示します。

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
def first_fit_decreasing(bin_capacity, items):
# アイテムを大きい順にソート
items = sorted(items, reverse=True)
# ビンのリスト(各ビンの残り容量を保持)
bins = []
# 各ビンに詰めたアイテムを記録するリスト
bin_contents = []

for item in items:
# アイテムを詰めるためのビンを見つけるフラグ
placed = False

# 既存のビンにアイテムを詰める
for i in range(len(bins)):
if bins[i] >= item:
bins[i] -= item
bin_contents[i].append(item)
placed = True
break

# 既存のビンにアイテムを詰められなかった場合、新しいビンを追加
if not placed:
bins.append(bin_capacity - item)
bin_contents.append([item])

return bins, bin_contents

# 問題の定義
bin_capacity = 10
items = [2, 5, 4, 7, 1, 3, 8]

# First-Fit Decreasing 法で問題を解く
bins, bin_contents = first_fit_decreasing(bin_capacity, items)

# 結果の表示
print(f"Total bins used: {len(bins)}")
print("Bin contents:", bin_contents)

解説

  1. アイテムのソート:

    • items = sorted(items, reverse=True) でアイテムを大きい順にソートします。
  2. ビンのリスト:

    • 空のビンのリスト bins を作成します。
  3. アイテムの配置:

    • 各アイテムについて、既存のビンに収められるかをチェックします。
    • 既存のビンに収められる場合、そのビンにアイテムを追加します。
    • 既存のビンに収められない場合、新しいビンを追加し、そのビンにアイテムを入れます。
  4. 結果の表示:

    • 最終的に使用されたビンの数と各ビンの内容を表示します。

Pythonでの解法

このコードを実行すると、以下のような結果が得られます。

1
2
Total bins used: 3
Bin contents: [[8, 2], [7, 3], [5, 4, 1]]

この結果は、3つのビンが使用され、それぞれのビンに収められたアイテムの合計サイズが表示されます。

具体的には、以下のようにアイテムが配置されています。

  • ビン1: 8 + 2 = 10
  • ビン2: 7 + 3 = 10
  • ビン3: 5 + 4 + 1 = 10

カタランの最小曲面(Catalan's minimal surface)

カタランの最小曲面(Catalan's minimal surface)

カタランの最小曲面(Catalan’s minimal surface)は、最小曲面の一例です。

最小曲面とは、与えられた境界条件の下で面積が極小になる曲面のことです。

最小曲面は、特定の物理的条件下で見られる曲面で、石鹸膜の形状などがその一例です。

特徴と方程式

カタランの最小曲面は、特定のパラメトリック方程式で表されます。

以下はその特徴と方程式です:

  • 特徴:

    • カタランの最小曲面は、最小曲面の中でも比較的シンプルな形状を持ち、解析的に記述できる例です。
    • この曲面は平面上の曲線に沿った振動を持つ形状をしており、見た目には波打つような形状をしています。
  • 方程式:

    • パラメトリック方程式で表されるカタランの最小曲面は次のようになります:
      $$
      x(u, v) = u - \sin(u)
      $$
      $$
      y(u, v) = v
      $$
      $$
      z(u, v) = 1 - \cos(u)
      $$
    • ここで、$(u)$と$(v)$はパラメータであり、$(x)$, $(y)$, $(z)$はそれぞれの座標を表します。

グラフの形状

カタランの最小曲面の形状は、波打つリボンのような形状をしており、以下のような特徴を持っています:

  • 曲面が周期的に振動する形状を持ちます。
  • 振動の周期は、パラメータ$ (u) $に依存します。
  • この曲面は、与えられた境界条件の下で、エネルギーが最小となる形状をしています。

カタランの最小曲面は、数学的にも美しく、また物理的な応用(例えば、材料科学構造力学など)にも関連する興味深い対象です。

プログラム例

カタランの最小曲面を描くためのPythonコードを示します。

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 numpy as np
import plotly.graph_objs as go

# x, yの範囲
u = np.linspace(-2 * np.pi, 2 * np.pi, 100)
v = np.linspace(-2, 2, 100)
u, v = np.meshgrid(u, v)

# カタランの最小曲面の方程式
x = u - np.sin(u)
y = v
z = 1 - np.cos(u)

# 3Dプロットの作成
surface = go.Surface(x=x, y=y, z=z, colorscale='Viridis')

layout = go.Layout(
title='Catalan\'s Minimal Surface',
scene=dict(
xaxis=dict(title='X'),
yaxis=dict(title='Y'),
zaxis=dict(title='Z')
)
)

fig = go.Figure(data=[surface], layout=layout)
fig.show()

コードの説明

  1. パラメータの設定:

    • uvはパラメトリック方程式のパラメータで、それぞれ$x$と$y$の範囲を設定します。
  2. カタランの最小曲面の方程式:

    • x, y, zはカタランの最小曲面の座標です。
    • 方程式 x = u - np.sin(u), y = v, z = 1 - np.cos(u) を使用します。
  3. 3Dプロットの作成:

    • go.Surfaceを使って3Dプロットを作成します。
    • layoutでグラフのレイアウトを設定します。
    • fig.show()でグラフを表示します。

このコードを実行すると、カタランの最小曲面の美しい3Dプロットが表示されます。

[実行結果]

制約充足問題

制約充足問題

$Python$の制約充足問題を解くためにpython-constraintライブラリを使用したサンプルコードを示します。

この例では、$3$つの変数$(x、y、z)$に対する制約条件を設定し、制約条件を満たす解を見つけます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from constraint import Problem

# 問題を作成
problem = Problem()

# 変数の定義
problem.addVariable('x', [1, 2, 3])
problem.addVariable('y', [4, 5, 6])
problem.addVariable('z', [7, 8, 9])

# 制約条件の定義
def custom_constraint(x, y, z):
if x + y > z:
return True

problem.addConstraint(custom_constraint, ['x', 'y', 'z'])

# 問題を解く
solutions = problem.getSolutions()

# 解の表示
for solution in solutions:
print(solution)

このコードでは、Problemオブジェクトを作成し、addVariableメソッドを使用して変数を定義します。

次に、addConstraintメソッドを使用して制約条件を定義します。

最後に、getSolutionsメソッドを使用して制約条件を満たす解を見つけます。

制約条件は、$3$つの変数$(x、y、z)$の値が与えられ、それらの値が特定の条件を満たすかどうかを評価します。

この例では、$x$と$y$の合計が$z$より大きい場合に制約条件を満たします。

[実行結果]

{'x': 3, 'y': 6, 'z': 8}
{'x': 3, 'y': 6, 'z': 7}
{'x': 3, 'y': 5, 'z': 7}
{'x': 2, 'y': 6, 'z': 7}

最小全域木(Minimum Spanning Tree, MST)問題

最小全域木(Minimum Spanning Tree, MST)問題

最小全域木(Minimum Spanning Tree, MST)問題は、グラフ理論における基本的な最適化問題の一つです。

与えられた重み付きの無向グラフにおいて、すべてのノードをつなぐために必要なエッジの集合であって、その総重みが最小となるような部分グラフを見つける問題です。

具体的には、無向グラフ $ ( G = (V, E) ) $が与えられたとき、その部分グラフ$ ( T ) $で以下の条件を満たすものを最小全域木と呼びます:

  1. $( T ) $は$ ( G ) $の全域木である(すべてのノードが連結されている)。
  2. $( T ) $のエッジ数は$ ( V - 1 ) $である。
  3. $( T ) $のエッジの重みの合計が最小である。

最小全域木問題は、通信ネットワーク電気回路道路ネットワークなどの多くの応用分野で重要な役割を果たしています。

具体的な例としては、都市間の最短経路を確立する通信ネットワークや、最小コストですべての地域を結ぶ電力網などがあります。

最小全域木問題は、PrimのアルゴリズムKruskalのアルゴリズムなどのアルゴリズムを用いて解くことができます。
これらのアルゴリズムは、グラフのエッジの重みを考慮して、最小の重みを持つエッジを選択しながら部分グラフを構築していきます。

要するに、最小全域木問題は与えられたグラフ内のすべてのノードを最小のコストでつなぐ木を見つける問題であり、多くの応用分野で効果的に利用されています。

プログラム例

NetworkXを使用して最小全域木問題を解決し、その結果をグラフ化する方法を以下に示します。

まず、グラフを作成し、最小全域木を計算し、その結果を描画します。

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

# グラフの作成
G = nx.Graph()
G.add_weighted_edges_from([
(0, 1, 1),
(0, 2, 3),
(1, 2, 1),
(1, 3, 4),
(2, 3, 2),
(3, 4, 5),
(4, 5, 1),
(5, 0, 2)
])

# 最小全域木の取得
mst = nx.minimum_spanning_tree(G)

# グラフの描画
pos = nx.spring_layout(G) # ノードの配置を計算
plt.figure(figsize=(12, 8))

# 元のグラフを描画(灰色のエッジ)
nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray', node_size=500, font_size=15)

# 最小全域木を描画(赤色のエッジ)
nx.draw_networkx_edges(mst, pos, edge_color='red', width=2)

# エッジの重みを表示
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

plt.title("Minimum Spanning Tree in the Graph")
plt.show()

【コードの説明】

  1. networkxmatplotlib.pyplotをインポートします。
  2. グラフ G を作成し、ノード間の重み付きエッジを追加します。
  3. nx.minimum_spanning_tree関数を使用して最小全域木 mst を取得します。
  4. ノードの配置を計算するために nx.spring_layout を使用します。
  5. plt.figure を使用して描画領域のサイズを設定します。
  6. 元のグラフ G を灰色のエッジで描画します。
  7. 最小全域木 mst を赤色のエッジで描画します。
  8. エッジの重みを表示します。
  9. グラフにタイトルを設定し、表示します。

このコードを実行すると、与えられたグラフの最小全域木赤色のエッジで強調表示されたグラフが表示されます。

最小全域木は、グラフ内のすべてのノードを最小コストで連結する部分グラフです。

[実行結果]

ソースコード解説

このソースコードは、NetworkXを使用してグラフを作成し、最小全域木を計算し、結果を可視化するためのものです。

以下では、コードの各部分を詳しく説明します。

1. ライブラリのインポート

1
2
import networkx as nx
import matplotlib.pyplot as plt
  • networkxはグラフ理論やネットワーク解析のためのPythonライブラリです。
  • matplotlib.pyplotはグラフを描画するためのPythonライブラリです。

2. グラフの作成

1
2
3
4
5
6
7
8
9
10
11
G = nx.Graph()
G.add_weighted_edges_from([
(0, 1, 1),
(0, 2, 3),
(1, 2, 1),
(1, 3, 4),
(2, 3, 2),
(3, 4, 5),
(4, 5, 1),
(5, 0, 2)
])
  • 無向グラフ G を作成します。
  • add_weighted_edges_fromメソッドを使用して、重み付きのエッジを追加します。
    エッジはタプルの形で指定され、最初の2つの要素はノードのペアで、3番目の要素はエッジの重みです。

3. 最小全域木の取得

1
mst = nx.minimum_spanning_tree(G)
  • nx.minimum_spanning_tree関数を使用して、与えられたグラフの最小全域木を計算します。

4. グラフの描画

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pos = nx.spring_layout(G)  # ノードの配置を計算
plt.figure(figsize=(12, 8))

# 元のグラフを描画(灰色のエッジ)
nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray', node_size=500, font_size=15)

# 最小全域木を描画(赤色のエッジ)
nx.draw_networkx_edges(mst, pos, edge_color='red', width=2)

# エッジの重みを表示
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

plt.title("Minimum Spanning Tree in the Graph")
plt.show()
  • nx.spring_layout関数を使用して、グラフ内のノードの配置を計算します。
  • plt.figure(figsize=(12, 8))で描画領域のサイズを設定します。
  • 元のグラフ G を灰色のエッジで描画します。
  • 最小全域木 mst を赤色のエッジで描画します。
  • nx.get_edge_attributes関数を使用して、グラフのエッジの属性(ここでは重み )を取得します。
  • nx.draw_networkx_edge_labels関数を使用して、エッジの重みを表示します。
  • plt.title関数を使用して、グラフにタイトルを設定します。

以上が、与えられたソースコードの詳細な説明です。

これにより、グラフがどのように構成され、最小全域木がどのように計算されて可視化されるかが理解できるでしょう。

グラフ解説

[実行結果]

グラフに表示される内容を詳しく説明します。

  1. ノード(頂点):

    • グラフ内の各ノードは、円で表現されています。
      円の中には、ノードの名前が表示されています。
      この例では、ノードは$0$から$5$までの整数で表されています。
  2. エッジ(辺):

    • グラフ内の各エッジは、ノード間の接続関係を表しています。
      エッジは、ノード間の線で表現されます。
    • エッジの上に表示される数字は、エッジの重み(コスト距離など)を示しています。
      この例では、エッジの重みは整数です。
  3. 最小全域木:

    • 最小全域木は、グラフ内のすべてのノードを含み、かつ全てのノードが直接または間接的に接続されている部分グラフです。
    • 最小全域木は赤色のエッジで強調表示されています。
    • 最小全域木は、元のグラフ内のすべてのノードを最小コストで連結するように構築されます。
  4. エッジの重み:

    • エッジの上に表示される数字は、エッジの重みを示しています。
      最小全域木のエッジには重みが表示されますが、元のグラフのすべてのエッジには表示されません。
  5. グラフのタイトル:

    • グラフのタイトルは、「Minimum Spanning Tree in the Graph」です。
      これは、描画されているグラフが元のグラフ内の最小全域木を示していることを示しています。

これらの要素が組み合わさって、グラフ全体が構成されています。

これにより、最小全域木がどのように元のグラフから選ばれるかや、各エッジの重み最小全域木の構築にどのように影響するかがわかります。

Helicoid(ヘリコイド)

Helicoid(ヘリコイド)

Helicoid(ヘリコイド)を描画してみましょう。

Helicoidは、微分幾何学応用数学でよく知られている曲面の一つで、螺旋状の形状を持っています。

Helicoidは次のようなパラメトリック方程式で表されます。

$$
x(u, v) = u \cos(v)
$$
$$
y(u, v) = u \sin(v)
$$
$$
z(u, v) = c v
$$

ここで、$( c ) $は螺旋の巻きの間隔を調整する定数です。

プログラム例

以下に、PythonコードでHelicoidを描画する方法を示します。

必要なライブラリのインストール

1
pip install matplotlib numpy

PythonコードでHelicoidを描画

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
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

# パラメトリック方程式のパラメータ範囲を設定
u = np.linspace(-10, 10, 100)
v = np.linspace(0, 4 * np.pi, 100)
u, v = np.meshgrid(u, v)

# Helicoidの定数
c = 1

# Helicoidの方程式
x = u * np.cos(v)
y = u * np.sin(v)
z = c * v

# 3Dプロットを作成
fig = plt.figure(figsize=(10, 7))
ax = fig.add_subplot(111, projection='3d')

# サーフェスプロット
surf = ax.plot_surface(x, y, z, cmap='viridis')

# カラーバー
fig.colorbar(surf, ax=ax, shrink=0.5, aspect=5)

# タイトルと軸のラベルを設定
ax.set_title('Helicoid')
ax.set_xlabel('X-axis')
ax.set_ylabel('Y-axis')
ax.set_zlabel('Z-axis')

# プロットを表示
plt.show()

説明

  1. numpyを使って$u$と$v$の範囲を設定し、グリッドを作成します。
  2. Helicoidのパラメトリック方程式を使用して$x$, $y$, $z$の値を計算します。
  3. matplotlibmpl_toolkits.mplot3dを使って3Dグラフを描画します。
  4. グラフには軸ラベル、タイトル、カラーバーが含まれています。

このコードを実行すると、螺旋状の形状を持つHelicoidを描画した3Dグラフが表示されます。

[実行結果]

ソースコード解説

ソースコードを詳しく説明します。

1. 必要なライブラリのインポート

1
2
3
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

説明

  • numpy: 数値計算ライブラリであり、配列操作や数学関数の計算に使用します。
  • matplotlib.pyplot: グラフ描画ライブラリであり、データの可視化に使用します。
  • mpl_toolkits.mplot3d.Axes3D: matplotlibの3Dプロット機能を使用するためのモジュールです。

2. パラメトリック方程式のパラメータ範囲を設定

1
2
3
u = np.linspace(-10, 10, 100)
v = np.linspace(0, 4 * np.pi, 100)
u, v = np.meshgrid(u, v)

説明

  • uvは、Helicoidをパラメトリックに表現するためのパラメータです。
  • np.linspace(start, stop, num)は、startからstopまでの範囲をnum個の等間隔で分割した値を生成します。
    • uは$-10$から$10$までの範囲で$100$個の値を持ちます。
    • vは$0$から$4π$までの範囲で$100$個の値を持ちます。
  • np.meshgrid(u, v)は、uvのグリッドを作成し、各組み合わせに対して対応するx, y, z座標を計算できるようにします。

3. Helicoidの定数

1
c = 1

説明

  • cはHelicoidの螺旋の巻きの間隔を調整する定数です。
    この例では、cは$1$に設定されています。

4. Helicoidの方程式

1
2
3
x = u * np.cos(v)
y = u * np.sin(v)
z = c * v

説明

  • Helicoidのパラメトリック方程式を用いて、各パラメータに対するx, y, zの値を計算します。
    • x = u * np.cos(v):
      uvの値を使ってx座標を計算します。
    • y = u * np.sin(v):
      uvの値を使ってy座標を計算します。
    • z = c * v:
      vの値に定数cを掛けてz座標を計算します。

5. 3Dプロットを作成

1
2
fig = plt.figure(figsize=(10, 7))
ax = fig.add_subplot(111, projection='3d')

説明

  • fig = plt.figure(figsize=(10, 7)):
    図のサイズを指定して新しい図を作成します。
    figsizeは幅と高さをインチ単位で指定します。
  • ax = fig.add_subplot(111, projection='3d'):
    3Dプロット用のサブプロットを追加します。
    • 111は$1$行$1$列のサブプロットグリッドを作成し、その$1$番目のサブプロットを指します。
    • projection='3d'は3Dプロットを作成することを指定します。

6. サーフェスプロット

1
surf = ax.plot_surface(x, y, z, cmap='viridis')

説明

  • ax.plot_surface(x, y, z, cmap='viridis'):
    x, y, zのデータを使って3Dサーフェスプロットを作成します。
    • cmap='viridis'はカラーマップを指定し、サーフェスの色をz軸の値に応じて変化させます。

7. カラーバー

1
fig.colorbar(surf, ax=ax, shrink=0.5, aspect=5)

説明

  • fig.colorbar(surf, ax=ax, shrink=0.5, aspect=5):
    サーフェスプロットのカラーバーを追加します。
    • shrink=0.5はカラーバーの高さを縮小して、全体の高さの$50%$にします。
    • aspect=5はカラーバーのアスペクト比を設定します。

8. タイトルと軸のラベルを設定

1
2
3
4
ax.set_title('Helicoid')
ax.set_xlabel('X-axis')
ax.set_ylabel('Y-axis')
ax.set_zlabel('Z-axis')

説明

  • ax.set_title('Helicoid'): プロットにタイトル「Helicoid」を設定します。
  • ax.set_xlabel('X-axis'): X軸にラベル「X-axis」を設定します。
  • ax.set_ylabel('Y-axis'): Y軸にラベル「Y-axis」を設定します。
  • ax.set_zlabel('Z-axis'): Z軸にラベル「Z-axis」を設定します。

9. プロットを表示

1
plt.show()

説明

  • plt.show(): 作成した図を表示します。
    このコマンドが実行されると、Helicoidの3Dサーフェスプロットがウィンドウに表示されます。

以上が、コードの各部分の詳しい説明です。

このコードは、Helicoidという螺旋状の形状を持つ曲面を3Dで描画するためのものです。

グラフ解説

[実行結果]

グラフに表示される内容は以下の通りです:

1. グラフの形状

  • Helicoid(ヘリコイド)の形状が描画されます。
    これは螺旋状の形状を持つ曲面であり、中心から外側に向かって広がる形をしています。

2. カラーマップ

  • グラフはカラーマップ(viridis)を使用して色付けされています。
    このカラーマップは高さ($z$軸の値)に応じて色が変わります。
    これにより、$z$軸方向の変化を視覚的に容易に捉えることができます。

3. カラーバー

  • カラーバーがグラフの右側に表示され、色と高さの対応を示します。
    カラーバーは、サーフェスの高さがどの色に対応するかを示し、$z$軸の値の範囲を視覚化します。

4. タイトルと軸ラベル

  • タイトル: グラフの上部に「Helicoid」というタイトルが表示されます。
    これにより、描画されている曲面がHelicoidであることがわかります。
  • 軸ラベル: 各軸にラベルが付けられています。
    • X軸には「X-axis」
    • Y軸には「Y-axis」
    • Z軸には「Z-axis」

これにより、各軸が何を表しているかが明示されます。

グラフの表示

  • 3Dサーフェスプロットとして、$x$, $y$, $z$の値から計算されたHelicoidの曲面が表示されます。
    曲面は、$u$と$v$という2つのパラメータに基づいて生成される点の集合から形成されています。

これらの要素が組み合わさって、Helicoidの3D曲面が視覚的にわかりやすく表示されています。