混合整数計画法（Mixed-Integer Programming, MIP)

混合整数計画法（Mixed-Integer Programming, MIP)

混合整数計画法（Mixed-Integer Programming, MIP）は、連続変数と整数変数の両方を含む最適化問題を解くための手法です。

以下に具体例を示し、それをPythonで解く方法を紹介します。

例題

ある工場では、2種類の製$品 (A) $と$ (B) $を生産しています。

工場の目標は、利益を最大化することです。以下の情報が与えられています。

  • 製品$ (A) $の単位当たりの利益は$ 40 $ドル。
  • 製品$ (B) $の単位当たりの利益は$ 30 $ドル。
  • 製品$ (A) $の製造には$ 2 $時間の機械時間と$ 1 $単位の材料が必要。
  • 製品$ (B) $の製造には$ 1 $時間の機械時間と$ 1 $単位の材料が必要。
  • 使用可能な機械時間は$ 8 $時間。
  • 使用可能な材料は$ 5 $単位。
  • 製品$ (A) $と$ (B) $の生産数は整数でなければならない。

この問題を解くために、次のように定式化します。

数学的定式化

【最大化する目的関数】
　$\text{Maximize } 40x_A + 30x_B$

【制約条件】
　$2x_A + x_B \leq 8$ (機械時間の制約)
　$x_A + x_B \leq 5$ (材料の制約)
　$x_A, x_B \geq 0$
　$x_A, x_B \in \mathbb{Z} (整数条件)$

Pythonによる解法

ここでは、Pythonのcvxpyライブラリを使ってこの問題を解きます。

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
import cvxpy as cp

# 変数の定義
x_A = cp.Variable(integer=True)
x_B = cp.Variable(integer=True)

# 目的関数の定義
objective = cp.Maximize(40 * x_A + 30 * x_B)

# 制約の定義
constraints = [
    2 * x_A + x_B <= 8,  # 機械時間の制約
    x_A + x_B <= 5,      # 材料の制約
    x_A >= 0,            # 非負の制約
    x_B >= 0             # 非負の制約
]

# 問題の定義
prob = cp.Problem(objective, constraints)

# 問題を解く
result = prob.solve()

# 結果の表示
print(f"Optimal value: {result}")
print(f"Optimal solution: x_A = {x_A.value}, x_B = {x_B.value}")

結果の解説

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

1
2
Optimal value: 180.0
Optimal solution: x_A = 3.0, x_B = 2.0

この結果は、製品$ (A) $を$ 3 $単位、製品$ (B) $を$ 2 $単位生産することが利益を最大化する最適な解であることを示しています。

このときの最大利益は$ 180 $ドルです。

解説

1. 変数の定義:

1
2
x_A = cp.Variable(integer=True)
x_B = cp.Variable(integer=True)

ここでは、製品$ (A) $と$ (B) $の生産数を整数変数として定義します。

2. 目的関数の定義:

1
objective = cp.Maximize(40 * x_A + 30 * x_B)

目的関数は、製品$ (A) $と$ (B) $の生産による利益を最大化するものです。

3. 制約の定義:

1
2
3
4
5
6
constraints = [
   2 * x_A + x_B <= 8,  # 機械時間の制約
   x_A + x_B <= 5,      # 材料の制約
   x_A >= 0,            # 非負の制約
   x_B >= 0             # 非負の制約
]

ここでは、機械時間と材料の使用量に関する制約を定義しています。

4. 問題の定義と解法:

1
2
prob = cp.Problem(objective, constraints)
result = prob.solve()

問題を定義し、solveメソッドで解きます。

5. 結果の表示:

1
2
print(f"Optimal value: {result}")
print(f"Optimal solution: x_A = {x_A.value}, x_B = {x_B.value}")

最適な値と解を表示します。

このようにして、混合整数計画法を用いて最適な生産計画を立てることができます。