線形計画問題（Linear Programming Problem）

線形計画問題（Linear Programming Problem）

目的最適化の一つの例として、線形計画問題（Linear Programming Problem）を挙げることができます。

以下に、シンプルな線形計画問題をPythonで解く方法を示します。

ここではscipy.optimize.linprogを使います。

例題

問題の目的は、以下の制約条件を満たしつつ、次の目的関数を最小化することです。

目的関数:

$
f(x, y) = 3x + 4y
$

制約条件:

  1. $( x + 2y \geqq 4 )$
  2. $( 3x + y \geqq 3 )$
  3. $( x \geqq 0 )$
  4. $( y \geqq 0 )$

この問題をPythonで解く方法を以下に示します。

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

# 目的関数の係数
c = np.array([3, 4])

# 制約条件の係数行列
A = np.array([[-1, -2], [-3, -1]])

# 制約条件の右辺ベクトル
b = np.array([-4, -3])

# 変数の下限定義 (x ≥ 0, y ≥ 0)
x_bounds = (0, None)
y_bounds = (0, None)

# linprog関数を使って問題を解く
result = linprog(c, A_ub=A, b_ub=b, bounds=[x_bounds, y_bounds], method='highs')

# 結果を表示
if result.success:
    print("最適解:", result.x)
    print("目的関数値:", result.fun)
else:
    print("最適化は成功しませんでした。")

[実行結果]

解説

  1. 目的関数の係数: c = [3, 4]

    • 目的関数 $ ( f(x, y) = 3x + 4y ) $の係数です。

  2. 制約条件の係数行列: A = [[-1, -2], [-3, -1]]

    • 制約条件を標準形$（ (Ax \leqq b) ）$にするために、不等式の符号を反転させています。

  3. 制約条件の右辺ベクトル: b = [-4, -3]

    • 同様に符号を反転させた右辺ベクトルです。

  4. 変数の下限定義: x_bounds = (0, None), y_bounds = (0, None)

    • 変数$ (x, y) $が非負であることを示しています。

  5. linprog関数の実行:

    • 目的関数、制約条件、変数の範囲を指定して、線形計画問題を解きます。
    • method='highs' は最先端のアルゴリズムを使って最適化を行うオプションです。

  6. 結果の表示:

    • result.success が True の場合、最適解と目的関数値を表示します。

このようにして、この線形計画問題の最適化をPythonコードで解くことができます。