- ベストアンサー
輸送問題についての最適解アルゴリズムと取入れ変数の決定方法
- 輸送問題に関する最適解を求めるアルゴリズムと、取入れ変数の決定方法についてまとめました。
- 輸送問題には、初期実行可能基底解の構築から、被約費用の計算や最適化判定、追出し変数と取入れ変数の決定、実行可能基底解の更新までの手順が存在します。
- 具体的な例を通して、取入れ変数の決定方法を説明しました。また、四角の形が成立しない場合にはどのように対処するかについても考察しました。
- winwinroom
- お礼率100% (2/2)
- 数学・算数
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
m供給地の数 n需要地の数 a(i)供給地iの供給量 b(i)需要地jの需要量 c(i,j)供給地iから需要地jに1個輸送する費用 x(i,j)供給地iから需要地jに輸送する量 とする 需要1 需要2 ＋－－－－＋－－－－＋ 供給1 ｜ 50 ｜ 30 ｜ ＋－－－－＋－－－－＋ 供給2 ｜ 0 ｜ 10 ｜ ＋－－－－＋－－－－＋ の場合 m=2 n=2 a(1)=80 a(2)=10 b(1)=50 b(2)=40 で初期可能解は x(1,1)=50 x(1,2)=30 x(2,1)=0 x(2,2)=10 で c(1,2)+c(2,1)<c(1,1)+c(2,2) の時 x(2,2)=10=min(x(1,1),x(2,2)) で x(1,1)←x(1,1)-10 x(2,2)←x(2,2)-10 x(1,2)←x(1,2)+10 x(2,1)←x(2,1)+10 需要1 需要2 ＋－－－－＋－－－－＋ 供給1 ｜ 40 ｜ 40 ｜ ＋－－－－＋－－－－＋ 供給2 ｜ 10 ｜ 0 ｜ ＋－－－－＋－－－－＋ と実行可能解を更新する c(1,1)+c(2,2)<c(1,2)+c(2,1) の時は x(2,1)=0=min(x(1,2),x(2,1)) だから更新しない 需要1 需要2 ＋－－－－＋－－－－＋ 供給1 ｜ 50 ｜ 0 ｜ ＋－－－－＋－－－－＋ 供給2 ｜ 0 ｜ 40 ｜ ＋－－－－＋－－－－＋ の場合 m=2 n=2 a(1)=50 a(2)=40 b(1)=50 b(2)=40 で初期可能解は x(1,1)=50 x(1,2)=0 x(2,1)=0 x(2,2)=40 で c(1,2)+c(2,1)<c(1,1)+c(2,2) の時 x(2,2)=40=min(x(1,1),x(2,2)) で x(1,1)←x(1,1)-40 x(2,2)←x(2,2)-40 x(1,2)←x(1,2)+40 x(2,1)←x(2,1)+40 需要1 需要2 ＋－－－－＋－－－－＋ 供給1 ｜ 10 ｜ 40 ｜ ＋－－－－＋－－－－＋ 供給2 ｜ 40 ｜ 0 ｜ ＋－－－－＋－－－－＋ と実行可能解を更新する c(1,1)+c(2,2)<c(1,2)+c(2,1) の時は x(2,1)=0=min(x(1,2),x(2,1)) だから更新しない
お礼
ありがとうございます。 参考にしてロジックを考えてみます。 またわからなかったらご質問させてください。m(^^)m