犀角(Diceros Horn)

輸送問題

輸送問題をステップ実行するプログラム(Java Web Start)

m個のの供給地からn個の需要地へ物資を輸送する場合、 各供給地から需要地への輸送費と各供給地の供給量、 各需要地の需要量が与えられているとき、 どの供給地から需要地にどれだけ物資を輸送するのがコストが最も少なくなるか。 この問題を考えるのが輸送問題である。

このプログラムではそれを飛び石法を用いて解くことにする。 まず供給地の個数と需要地の個数を入力する。 するとコスト表と輸送量の表が現れる。 その表に必要な係数を入力して、「次のステップ」ボタンを押すと、 標準的な手順にしたがって、飛び石法で解を求めていく。

飛び石法で基底変数を変換する場合、そのループの場所の色を変えています。 輸送量の表の右下のセルに全輸送コストを表示しています。

解が退化する場合はメッセージを出して終了します。 その場合は供給量、需要量を摂動させて もう一度始めから解いて下さい。

posted at 15:31 | category: /Program/OR | 固定リンク(輸送問題 )

PERT

PERT Simulator(Java Web Start)

いくつかの作業をまとまりとして見るときそれをプロジェクトと言い、 作業リストからプロジェクトの日程計画をたてることを考える。 作業リストにはその作業を始めるのに既に終了しておかなくてはならない 作業(先行作業)と、所要時間から構成される。このときそれぞれの作業が いつから始めることが可能か、余裕があるかどうかを調べる。

ここでは作業リストを与えて、次のものを求める。

• 最早開始時刻(ES)
• 最早終了時刻(EF)
• 最遅開始時刻(LS)
• 最遅終了時刻(LF)
• 全余裕(TF)
• 自由余裕(FF)

まず最初の画面では作業の個数を選択する。次に作業リストを与える表が現れるので、 所要時間を記入し、先行作業のところにチェックをいれる。その後、『PERT実行』 と言うボタンを押せば上の値を求めて表として表示する。

まだ日程計画としてつじつまがあっていないとき (先行作業をたどって行くとループになるときなど) の例外処理はしていない。最悪無限ループに陥る可能性がある。 また、ダミー作業を挿入する方法が一意でないときの処理も いい加減である。その辺は注意して利用してほしい。

ひょっとしたらバグが残っているかもしれない。 見つけた人は教えてほしい。

posted at 15:20 | category: /Program/OR | 固定リンク(PERT )

シンプレックス法

シンプレックス法をステップ実行するプログラム(Java Web Start)

初めの画面では変数の個数と条件式の個数を入力する。 変数はスラック変数も含める。条件式は目的関数は含めない。 [ENTER] ボタンを押すと、シンプレックス表の画面に切り替わる。 ここで、シンプレックス表を入力する。左端の行は目的関数 (z) の係数、右端は定数を入力する。[STEP] を押すと1段階ごとに シンプレックス法を実行する。[RESET] を押すと、はじめの画面に戻る。

実行するときに実行可能基底解を表す表からはじめなければ、正しい答えは保証 されません。2段階シンプレックス法や罰金法などを用いて調整して下さい。

一般的な流儀では定数項を一番左に書いたり、目的関数を一番上に書いたりする かも知れませんが、その場合は適宜読みかえて下さい。

posted at 15:15 | category: /Program/OR | 固定リンク(シンプレックス法 )