輸送問題についての最適解アルゴリズムと取入れ変数の決定方法
- 輸送問題に関する最適解を求めるアルゴリズムと、取入れ変数の決定方法についてまとめました。
- 輸送問題には、初期実行可能基底解の構築から、被約費用の計算や最適化判定、追出し変数と取入れ変数の決定、実行可能基底解の更新までの手順が存在します。
- 具体的な例を通して、取入れ変数の決定方法を説明しました。また、四角の形が成立しない場合にはどのように対処するかについても考察しました。
- ベストアンサー
輸送問題について
輸送問題に関する最適解を求めるアルゴリズムを探しています。 (1)初期実行可能基底解 (2)シンプレックス乗数、被約費用の計算 (3)被約費用の最適化判定 (4)追出し変数と取入れ変数の決定 (5)実行可能基底解の更新 という順番で解こうとしています。 なぜこの方法で解けるか？という理論に関しては、私の頭脳では理解不能な状態でフローを考えています。m(==)m 問題は、(3)で最適化と判断できない場合、(4)で取入れ変数を決めて、移動量の±する場所を決定し、実行可能基底解を更新する場面なのですが、 多くの参考となるサイトや情報では、例えば↓のような感じです。 需要１ 需要２ 需要３ ＋－－－－＋－－－－＋－－－－＋－－－ 供給１ ｜ ５０ ｜ ３０ ｜ ＊＊ ｜ ＋－－－－＋－－－－＋－－－－＋－－－ 供給２ ｜ ０ ｜ １０ ｜ ＊＊ ｜ ＋－－－－＋－－－－＋－－－－＋－－－－ ｜ ＊＊ ｜ ＊＊ ｜ ＊＊ ｜ 被約費用が０未満で絶対位置の大きい個所が 供給２→需要１であった場合、 ここを取入れ変数とし、この上下の実行可能解を検索すると、供給１→需要２ 横方向に検索して、供給１→需要２ 縦方向に検索して、供給２→需要２ となり、この四角のなかで、数値の一番小さい個所（供給→需要２）の１０で±して実行可能解を更新するとあります。 需要１ 需要２ 需要３ ＋－－－－＋－－－－＋－－－－＋－－－ 供給１ ｜ ４０ ｜ ４０ ｜ ＊＊ ｜ ＋－－－－＋－－－－＋－－－－＋－－－ 供給２ ｜ １０ ｜ ０ ｜ ＊＊ ｜ ＋－－－－＋－－－－＋－－－－＋－－－－ ｜ ＊＊ ｜ ＊＊ ｜ ＊＊ ｜ 例題等では、この状態で解けていくのですが・・ たとえば、実行可能解が 需要１ 需要２ 需要３ ＋－－－－＋－－－－＋－－－－＋－－－ 供給１ ｜ ５０ ｜ ０ ｜ ＊＊ ｜ ＋－－－－＋－－－－＋－－－－＋－－－ 供給２ ｜ ０ ｜ ４０ ｜ ＊＊ ｜ ＋－－－－＋－－－－＋－－－－＋－－－－ ｜ ＊＊ ｜ ＊＊ ｜ ＊＊ ｜ で、取入れ変数が供給２→需要１であった場合、この処理がなりたちません。 このような場合は、どうしたらよいでしょうか？ 現在、想定している需要・供給地は、５００か所以上あり、こんな場面は多々出てくると思うのですが。 EXCELで少し作ってみたのですが、添付画像のような場合、取入れ変数は、工場１３→倉庫６ となると思うのですが、この状況だと、±する四角ができあがりません。 理論を理解できていないので、説明がおぼつかないのですが、ご指導よろしくお願いいたします。 この輸送問題に関する他のアルゴリズムも探しているのですが、なにか参考になるサイト等ございましたら、教えてください。
- 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)) だから更新しない
関連するQ&A
- 複数の輸送手段がある資材所要量計画
こんにちは。 資材所要量計画において、製品をオーダーしてから、届くまでのリードタイムは１つに決定されている。ということは輸送手段がトラックにせよ、飛行機にせよなんらかの１つの輸送手段に決定されているということですよね。 それをサプライチェインマネジメントの観点で全体的コストの削減を考えたのですが、輸送手段が複数考えられる場合、例えば船と飛行機で、全部船、全部飛行機とすると輸送コストは明らかに違ってきますよね。 具体例を出すと、 飛行機容量１０ 船容量２０ 注文１ ２ ３ ４ ５ ６ ７ ８ 量 ４ ３ ４ ６ ５ ３ ５ ４ とすると、例えば、解表現；飛行機０船１ 注文１ ２ ３ ４ ５ ６ ７ ８ 量 ４ ３ ４ ６ ５ ３ ５ ４ 手段０ ０ １ １ １ １ ０ ０ （注文１、２と注文７，８はまとめて飛行機、注文３，４，５，６はまとめて船） とできますよね。 輸送手段の組合せは２^８ありそうですが、実際は２＊８で考えられるので、全列挙で問題ないのですが、 注文の組みあわせが、近似解を用いらなければ不可能です。（注文数８は余裕ですが） ここで問題なのが組合せの解表現です。 さっきの例ですと 注文 １ ２ ３ ４ ５ ６ ７ ８ 量 ４ ３ ４ ６ ５ ３ ５ ４ 組合せ１ １ ２ ２ ２ ２ ３ ３ のようにして、同じ数字は同じ発送日かつ同じ輸送手段で、遺伝的アルゴリズムで攻めるというのは、適しているのでしょうか？ やはり、GAは０と１のみの遺伝子表現で解が表現できないと有効ではないのでしょうか？ うまい解表現はないでしょうか？
- ベストアンサー
- 数学・算数
- 大学の問題なのですが、解けなくて困ってます…
大学の問題なのですが、解けなくて困ってます… 線形計画問題 (1) Z=2X1-X2+X3-X4:最小化 X1+X2+2X3+X4=2 -X1+2X2-3X3+X4=1 X1,X2,X3,X4>0 1)実行可能基底解をすべて求めよ 2)X1,X2を基底変数とするシンプレックス表から出発して単体法で最適解を求めよ 3)この問題の双対問題を書け (2)線形計画問題に変形し単体法を用いて解け | X1-X2 |:最小化 2X1-X2+X3<2 3X2-X3<5 X1+X2+2X3>6 X1,X2,X3>0 (<，>は＿がついてますが表記が？になるのであえてこれにしました) (２の方は目的関数の絶対値をとって単に計算したやつでも構いません) よろしくお願いします。
- ベストアンサー
- 数学・算数
- 商品輸送中の破損と修理費負担について
以下のような場合、修理費用はこちらの負担になってしまうのでしょうか。 Ｓ社製品を修理のため、Ｓ社指定のＮ輸送業者を利用してＳ社に送る手配をしました。 しかし、Ｎ輸送業者の対応が不適切であり、Ｓ社との連携が確実ではなかったことが判明しました。 Ｎ輸送業者が不手際に対して謝罪したため、今回の輸送については、予定通りにＮ輸送業者を利用することとなりました。 その後、Ｓ社から製品の故障箇所確認の連絡があり、Ａという部分にのみ故障が認められたとのことで、その修理を承諾しました。 その折、返送に関しては他の輸送業者を利用したいとお願いしましたが、Ｓ社ではＮ輸送業者しか扱わないという理由で却下されました。 そして、返ってきた製品は、送る前とは明らかに異なり、故障と思われる部分Ｂがありました。 Ｂの故障について、Ｓ社に問い合わせしたところ、「使用のための故障である可能性がある」との返答でした。 修理後、使用していないのに「使用の為の故障」という理屈に納得できず、１．輸送中の故障 ２．故障箇所確認の不十分 の2点を指摘しました。 １については、輸送中と受け取り後のどちらの故障か確定ができない可能性が高いとの返答でした。 ２については、故障箇所は1度の預かりで製品全体を確認しているので、故障箇所確認時点で指摘していない部分は故障していなかった とのことでした。 さらに、これに関する修理費用について聞いたところ、メーカー保障とは言い難いとの返答でした。 Ｓ社の言い分を通すと、輸送中の破損・故障については、こちらが負担するということになるかと思います。 輸送業者の変更を要求し、却下され、さらに製品が故障した場合にはこちらが修理費を負担するということになるようです。 納得し難いのですが、法律ではどのような判断になるのでしょうか。
- 締切済み
- その他（法律）
- 独占企業の利潤最大化問題
下記の問題が解けません。 どなたかご教授頂けないでしょうか？ ------------------------------------------------------------------------- 完全競争市場において、X財の需要関数と供給関数がそれぞれ、 以下のように表されているとする。 D＝－２P＋２３０（D：X財の需要量、P：価格） S＝２P－２０（S：X財の供給量） このとき、生産者理論に関する以下の各問に答えよ。 設問１（※設問２は分かるので、設問１だけ書きます） この市場におけるX財の供給が1社の企業に独占された場合の価格と生産量を答えよ。 ------------------------------------------------------------------------- MC＝MRを使って解くことは分かるのですが、MCを求めることができません。 初心者なので、途中の解説も入れて頂けると助かります。 よろしくお願いいたします。
- ベストアンサー
- 経済
- 外国為替の均衡点は？
外国為替の均衡点は？ 需要と供給で価格は決まると仮定します。 この場合、貨幣の需要と供給は何なのでしょうか？ これにより、為替の傾向が決まると理論上は考えられます。 購買力平価説だけではないと思ったからです。 キャリートレードの様に各国の金利によって需要がきまる事を 前の事件でしったからです。 貨幣の需要は、購買力と各国の銀行の金利、これ意外に何があるのでしょうか。 また、それぞれどのくらいの影響力があるのでしょうか。
- ベストアンサー
- FX・外国為替取引
- 行列を用いて連立一次方程式を作る問題について
解ベクトル（x e）を用いてこの国の為替市場が均衡する。この国の通貨に対する需要量（供給量）と為替レートを求めるための連立一次方程式を表記せよという問題があるのですが、この場合の係数行列は２×２ですか？ 需要関数x=100-e 供給関数x=-300+5e という条件が与えられていて、 （１）でその連立一次方程式を表記する問題 （２）ではその求めた連立一次方程式とクラメールの公式を用いて均衡為替レートを求めよ、という問いになっています。 隠れた均衡式xd=xsを含めて考えて３×３の係数行列として計算するとちょうど綺麗な数字（100）が出てくるのですが、解ベクトル（ｘ e）は2つしかありません。しかしそのまま二つの式だけで求めようとすると割り切れない値（-400÷-６）が出てきてしまいます。 これはきちんと係数行列をまとめる方法があるのでしょうか？それとも単純に自分のミスでしょうか・・？
- 締切済み
- 数学・算数
- 需要曲線と供給曲線がわかりません。
需要曲線と供給曲線がわかりません。 経済学の入門用の本を見ると、最初のほうに需要曲線と供給曲線のことが描いてあることが多いです。どの本をみても、なぜああいう形をしているのかイマイチわかりません。 部分均衡理論では、他の市場からの影響を排除するために一つの市場だけを考えます。また、対象となる財の市場を扱うのに、財の量と価格のみを変数としてその他の変数の存在を無視します。 わからないのは以下の二つの主張です。 主張1． 独立変数を財の量、従属変数を財の価格としたとき、需要曲線は微分可能でその微分係数は常に負。 主張2． 主張1と同じ仮定で、供給曲線は微分可能でその微分係数は常に正。 これが私には理解できずに、ここから先に進んでいくことができません。 （例A） ある財Aを固定して、Aの需要について考えます。 部分均衡理論の前提により、消費者の懐具合は変数となりません。 言い換えると、定数になりますから、例えばどの人も一人当たり10万円持っているとしましょう。 Aの価格が10万円より高く設定されているとき、たとえば11万円とすると、借金することを考えなければ誰もAを購入できません。つまり、需要は0になります。 では、Aの価格が10万円以下に設定されているとき、たとえば9万円とすると、誰でも購入できます。どんな人が購入するか考えたとき、部分均衡理論では他の財のことを考えないので、世界には財と呼べるものはAしかない。価格が変わらなければ、ある人は永久に買い物をしないか、一度だけAを買うかの2つに1つしかありません。 買う人と買わない人の差は何か？とにかくAの価格と量以外に変数は無いので、差は無いはずと考えるか、または、買う人の発生する確率を固定するかのどちらかと考えます。前者を後者の特別な場合と考えれば、ある人がAを購入する確率pが与えられているとしてよいでしょう。 そうすると、ある価格における需要の量は、その財が例えば音楽CDのように2枚あっても仕方ないものであれば、「人口×p」となるはずです。 財の価格と量以外に変数は無いことが前提なので、pは変化しないことになります。 すると、Aの価格を少し下げても、逆に、Aの価格を少し上げても、pは変化しませんから、価格が10万円以下である限り、需要の量は一定になるはずです。 つまり、Aの需要の価格を量で微分すると0になります。 （例B） 財Bはダイヤモンドで、純度や大きさが同じ一定のもの、100万円くらいで売られているようなものとします。 価格がたとえば千円とすると需要がものすごく多くなるでしょうか？ ニセモノだと思って買わないと判断する人が結構いると思います。 そうすると、Bの需要の価格を量で微分できたとしてもそれが正になることがあると考えられます。 （例C） 財Cは誰も知らないようなもので、知名度がほとんどないとします。誰も知らないので価値があるとは誰も思いません。それで少量生産して1つ千円で売っていたとします。ところがある程度商売が進んでいくうちに、その価値を見出した人がいて、そんな価格では安すぎるからもっと高くしたほうがいいと言い出したとします。それで価格を1万円にしてその人のやり方にしたがっていたら売れまくってしまった、というような場合、需要量が増えて価格も高くなったことになります。 （例D） 供給曲線について。ものすごく量が多いときは大量生産することが多いと思います。 その場合、ロットで千個単位とか10万個単位といったひと塊で供給量の増減をするのが普通と思います。半端な数だと、半端な数だけ作るようにシステムができていないから困ってしまうわけです。つまり、供給曲線は連続ではなく、とびとびの値でしか定義できません。もちろん微分できないどころか定義すらできません。このような場合、均衡点が存在しないのが普通です。 「主張1」や「主張2」によって、その下に上げた例A～Dが間違っているはずなのですが、どこが間違っているのかが私にはわかりません。ご教示ください。
- ベストアンサー
- 経済学・経営学
- アルゴリズム論の参考書
アルゴリズム論のよい文献をさがしています。データベース論ではなくてNP困難や貪欲アルゴリズム、最適化論、ヒューリスティック、離散数学に焦点を当てた実用的かつ理論的な参考書を探しています。プログラマをやっているので、コードを書く前に（同じことを実行するが異なったコードスタイルの関数等への）スピードを論理的に比較したり、輸送問題やスケジューリング論が理解できるようになるのが主な目的です。初心者向けと上級者向け、分けて紹介していただければ幸いです。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 不完全競争に関する問題
ある財の市場において、需要関数はｘ＝１００－ｐによって与えられ、ｘの生産のための費用関数はＣ（ｘ）＝２０ｘによって与えられているとする。 (１)この財が独占企業によって供給される場合の独占価格および生産量を求めなさい。 (２)この財が同質的な２つの企業によって競争的に供給されている場合のクールノー均衡(数量競争が行われる場合の均衡)およびベルトラン均衡(価格競争が行われる場合の均衡)を求めなさい。 (１)は何とか、ｐ＝４０、ｘ＝６０と答えがでたのですが、(２)の方が分かりません。 どなたか分かる方がいれば、教えていただけると助かります。 また可能であれば(１)の答えがこれで正解かも教えていただけると助かります。 よろしくおねがいいたします。
- ベストアンサー
- 経済学・経営学
- 需要関数/供給関数における価格弾性値について
数学や計量経済学の基礎が十分にない中での質問にて失礼いたします。 学術論文や研究レポートで、需要関数/供給関数を推定したものを見かけるのですが、需要/供給の価格弾性値は、示された需要/供給関数の中にある、変数「自己価格」にかかる係数の値と考えればよいのでしょうか。 また、ラグ付き関数の場合、変数「自己価格」にかかる係数の値が当期1期における弾性値であって、長期の弾性値については、関数形に依存するが、「自己価格」の係数と極限(lim)の概念を使って求める、という理解で合っているでしょうか。
- 締切済み
- 経済学・経営学
お礼
ありがとうございます。 参考にしてロジックを考えてみます。 またわからなかったらご質問させてください。m(^^)m