探すのはソルバーに任せる
家具職人は机と椅子を作れますが、木材も時間も限りがあります。どの組み合わせがいちばん儲かるでしょうか。午後いっぱいかけて計画を試すこともできます。それとも、制限を書き出して、ソルバーに最善の計画を見つけさせる、あるいは計画がないことを証明させることもできます。
このレッスンが終わると
メモ
最適化モデルを動かして、そのステータス、計画、影の価格を読めます。
キーワード
- モデル：目的と制限を書き出したもの。
- ソルバー：モデルの最善の答えを見つけるプログラム。
- 余裕：制限の残り。
- 影の価格：制限があと 1 単位増えたときの価値。
- 整数：小数のない数。
ウォームアップ：すでに知っていること
メモ
頭の中で答えてください。1. 変数とは何ですか。2. 何かを最大にするとはどういう意味ですか。3. 椅子を 2.5 脚作れますか。3 つ目の答えは、すぐあとで使います。
始める前に
メモ
このレッスンの上のバーでラボを起動を押します。このラボは自分専用のUbuntu マシンまるごと 1 台なので、コンテナーより起動に少し時間がかかり、初回はソルバーも入れます。各実行ボタンは、コマンドをマシンのターミナルに順番に、同じセッションの中で入力します。マシンがまだ起動中と出たら、数秒待ってからもう一度押してください。動きを見たり、自分で入力したりしたいときは、バーのターミナルを開くを押します。
モデルは目的と制限である
ファイルはフォルダー optimisation にあります。最初のコマンドでそこに移ります。lp.py は PuLP で書いたモデルで、机と椅子、最大にしたい利益、木材と時間と保管場所の制限があります。opt は、ソルバーが使える状態で Python のファイルを動かします。最初の行にOptimalと出ます。ソルバーが最後まで終わり、答えが信頼できるという意味です。計画は机 20 台と椅子 60 脚で、利益は 2800 です。
cd optimisationここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
opt lp.pyここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
チェック
ヒント
余裕がある制限はどれで、その影の価格はいくつですか。答え：保管場所は 60 余っているので、あと 1 単位増えても価値はありません。木材と時間は使い切られていて、影の価格は 20 と 10 です。木材があと 1 単位あれば、利益が 20 増えます。
よくある間違い
注意
使い切った制限が、利益が低い原因だといつでも思い込む人が多くいます。そうとは限りません。影の価格を読んでください。使い切っていて価格が 20 の制限は増やす価値があり、余裕のある制限は、大きくてもそれ以上の価値はありません。
整数には別のソルバーがいる
integer.py はプロジェクトを選びます。プロジェクトは丸ごとやるか、やらないかです。モデルを 2 回解きます。小数を許すと値は 45.17 で、計画はプロジェクトを 0.67 だけやります。この計画を丸ごとのプロジェクトに丸めると、予算 19 に対して費用が 22 になり、計画になりません。丸ごとのプロジェクトだけを求めると、値は 42 で、プロジェクトは bridge、garden、theatre の 3 つです。
opt integer.pyここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
チェック
ヒント
小数を許した答えのほうが、整数の答えより価値が大きいのはなぜですか。答え：規則が少ないからです。プロジェクトの一部を許すことは助けにしかならないので、整数の答えの上限になります。
制約ソルバーがシフト表を作る
shifts.py は OR-Tools CP-SAT を使います。看護師 3 人が 1 日 3 つの勤務を 4 日間分け合い、それぞれに入りたくない勤務の希望があります。夜勤の次の日の朝勤には誰も入りません。ソルバーはOPTIMALと答え、希望を 1 つ破る必要があると伝えます。初日に、2 人が同じ勤務を避けることはできないからです。各日のシフト表が表示されます。
opt shifts.pyここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
最後のチェック
ヒント
見返さずに答えてください。1. ソルバーは何をしますか。2. ステータスが Optimal だと何が分かりますか。3. 影の価格とは何ですか。4. 小数を含む計画を丸められないのはなぜですか。答え：モデルの最善の答えを見つける、ソルバーが終わり答えが最善だと分かる、制限があと 1 単位増えたときの価値、丸めた計画が制限を破ることがあるから。では、ホームフォルダーのREADME.mdを cat ~/README.md で開いてください。2 つのモデルを書きます。
先生へ
ヒント
手順と実行ボタンがレッスンで、ラボは生徒一人ひとりの専用コピーです。これは VM ラボで行います。生徒はそれぞれ、PuLP、CBC、OR-Tools が入った自分専用の Ubuntu マシンを持ち、実行ボタンはそのターミナルに入力して、表示された内容を見せます。要点：1. モデルは目的と制限で、ソルバーが最善の答えを見つける。2. 数字より先にステータスを読む。3. 余裕と影の価格が、どの制限が大事かを教える。4. 整数には整数用のソルバーが必要で、丸めると制限を破ることがある。よくある間違い：価格を読まずに、使い切った制限のせいにすること。準備：ラボとブラウザー。ヒント：2 つ目の実行の前に、プロジェクトの 0.67 を自分で丸めてみるようクラスに言ってください。ラボ自体には、見えないインスタンスで 2 つのモデルを採点するチェックがあります。オペレーションズ・リサーチのモジュールは SciPy で問題を解きますが、このラボは、クラスが PuLP と OR-Tools に出会う場所です。自分のモジュールにコピーして変更するか、レッスンビルダーのラボメニューから一から作ってください。