PuLP で線形最適化問題を解く

2020/05/15

線形最適化問題とは?

1次式のみで定義できる式から、ある条件(制約)をもとに問題の最適解を見つけることです。
2次以上の式や、離散的な変数(連続でない)に関しての問題は対象外となります。

目的関数と制約

問題を解決するには、目的関数(求めたい解の定義式)と、問題の制約(条件)を定義します。
問題定義の関数は、 最小化最大化の2種類あります。

例えば、生産するための最大利益、乗り換え案内などの最短経路を求めたりする問題です。

上記は3つの制約で、ある目的関数から最適解を求めたグラフ化です。
制約は(不等式)の不等号の向きで範囲が異なります。

 

PuLP とは

PuLP は COIN-OR プロジェクトで開発された線形最適化問題を解くための Pythonライブラリです。

Jupyter Notebook インストール

視覚的に確認するために、Jupyter Notebook をインストールします。
個人的には、Anaconda は入れたくないので pip3 でインストールします。


$ pip3 install jupyter

Pulp インストール


$ pip3 install pulp

Pulp の基本

決定変数

変数作成変数は、 LpVariable() で定義します。

  • 連続変数(実数値)
  • 0 or 1変数
  • 整数値

第1引数

「インスタンス名」で必須です。

第2引数

  • lowBound:変数の下限値(デフォルト:None)
  • upBound:変数の上限値(デフォルト:None)
  • cat:変数の種類(デフォルト:連続変数 = pulp.LpContinuous)

変数の利用例


x1 = pulp.LpVariable('x1', 0)
x2 = pulp.LpVariable('x2', 0) 

問題定義のモデル作成

目的関数と制約

目的関数を LpProblem() でインスタンスを作成し、制約を追加してきます。

最大化モデル作成


LpProblem(sense= LpMaximize)

最小化モデル作成


LpProblem(sense=LpMinimize)

ラベル付きの例


problem = pulp.LpProblem('最大化問題', sense=pulp. LpMaximize)

作成したインスタンスに、目的関数、制約の式を追加します。


problem = pulp.LpProblem('生産計画問題', sense=pulp. LpMaximize)
problem+= x1 + 2*x2, '目的関数 利益見込み'
problem+= x1 + 3*x2 <= 24, '原料制約'
problem+= 4*x1 + 4*x2 <= 48, '労働時間制約'
problem+= 2*x1 + x2 <= 22, '機会稼働制約'
problem

最適解の計算

定義した問題定義を実際に解くには、 solve() を利用しますが、戻り値は実際の解ではなく、成功フラグになります。


result = problem.solve()

実行結果のステータス

実行結果のステータスを確認するのに、 LpStatus() を利用します。


print(pulp.LpStatus[result])

ステータスの種類


{
 -3: 'Undefined',
 -2: 'Unbounded',
 -1: 'Infeasible',
 0: 'Not Solved',
 1: 'Optimal'
}

目的関数の最適値(最大・最小値)

目的関数の最適解は、 value(モデル.objective) で取得します。


print(pulp.value(problem.objective))

最適解を求める

解の取得

最適解を求めたら、解を取得します。
定義した決定変数を variables() 、それぞれの解を value(オブジェクト) で取得します。


for v in problem.variables():
    print(f’{v} = {pulp.value(v)}’)

結果


$ python3 2-1.py 
x1 = 6.0
x2 = 6.0

Jupiter Notebook

AWS CLI と jq でインスタンス一覧を整形して表示
React と Laravel7 のプロジェクトを作成する
Homebrewインストール-2020年版
3直線で囲まれた範囲塗りつぶし
PuLP で線形最適化問題を解く
カスタムのペジネーションを作る
node-sass を使って sass をコンパイルする
Log ファサードでSQLログを分離して書き出す
いちから始める Docker - 複数のコンテナを使う - (2020年)
いちから始める Docker - docker-compose を使う - (2020年)
AWS ECR を使ってみる
Laravel7 でマルチ認証
Mac に AWS Client を設定する
Laravel 7 リリース
v-html でHTML表示する
Laravel で Vue コンポーネントを使う
Laravel で Nuxt.js を使ってみる(Docker環境)
いちから始める Docker -コンテナをビルド- (2020年)
いちから始める Docker -起動してみる- (2020年)
Mac で MySQL(8系)
composer で vendor がインストールできない
Eloquent の日付を Carbon で扱う
webpack 4 入門(npm編)
[Mac]容量を減らす
DIコンテナはじめ
freee SDKを Laravel で使ってみる
freee API を使ってみる
Segueを利用しない画面遷移
Xcode11.3 で XVim2 を利用する
Codable で JSONを読み込み
Webpack入門(yarn編)
MacからLaradock PostgreSQLで接続エラー
Dockerで不要なコンテナ・イメージを削除
Mac で Laradock の構築
yarn インストール&プロジェクト作成
Laravel 6.x 構築(Homestead編)
Composer インストール
nvm インストール
npm install が Mac でエラー
HTMLタグでカーソルが同時処理(ミラーリング)されてしまう
DI(依存性注入)
[Ubuntu]Let's Encryptで無料の証明書を利用する
[Apache]Apache2.4のアクセス制限が変更
[Ubuntu]rootのログインとsudo権限追加
タミヤ マイコンロボット工作セットをMacに接続してみた
pgAdimn4 でブラウザで開けなくなる
Java8 を HomebrewとjEnvで構築
Android Studio環境構築 2019
ロケールの再構築
vagrant グループに Apacheを追加