Upgrade to Pro — share decks privately, control downloads, hide ads and more …

線形計画法とカーマーカー法 〜プログラマのための数学勉強会#3〜

線形計画法とカーマーカー法 〜プログラマのための数学勉強会#3〜

カーマーカー法はやめて「線形計画法と整数計画法」です。

Shintaro Kaneko

May 22, 2015
Tweet

More Decks by Shintaro Kaneko

Other Decks in Programming

Transcript

  1. ࣗݾ঺հ Shintaro Kaneko ‣ גࣜձࣾΤ΢ϨΧ ‣ pairsͷ։ൃશൠ୲౰ ‣ ࠷ۙ͸GoݴޠͰ։ൃ͍ͯ͠·͢ ‣

    େֶ࣌୅ ‣ ࠷దԽ໰୊ͷඇઢܗܭը๏Λઐ߈ ‣ github.com/kaneshin/lbfgs ʢݹʣ ‣ ඍ෼ํఔ͕ࣜ޷͖ͩͬͨ kaneshin kaneshinth shintaro.kaneko
  2. ࣗݾ঺հ Shintaro Kaneko ‣ גࣜձࣾΤ΢ϨΧ ‣ pairsͷ։ൃશൠ୲౰ ‣ ࠷ۙ͸GoݴޠͰ։ൃ͍ͯ͠·͢ ‣

    େֶ࣌୅ ‣ ࠷దԽ໰୊ͷඇઢܗܭը๏Λઐ߈ ‣ github.com/kaneshin/lbfgs ʢݹʣ ‣ ඍ෼ํఔ͕ࣜ޷͖ͩͬͨ kaneshin kaneshinth shintaro.kaneko ٱ͠ৼΓͷ਺ֶʂ
  3. Copyright © 2009-2015 eureka, Inc. All rights reserved. ‣ pairs͸ϚονϯάΞϧΰϦζϜ͕ඇৗʹॏཁ

    ‣ ๛෋ͳϢʔβʔͷσʔλͷ׆༻ ‣ ΤϯδχΞ͕Ϗδωε໘͔ΒΞϧΰϦζϜΛߟ͑Δ ‣ ࣾ಺ษڧձͰRษڧʴ౷ܭֶͷษڧձ΋։࠵ ‣ ϏοάσʔλΛਖ਼͍͠஌ࣝͰ࢖༻͢Δ ‣ ౷ܭΛؒҧͬͨೝࣝͰ࢖༻͠ͳ͍ʢภͬͨσʔλΛ࢖Θͳ͍
  4. ࠷దԽ໰୊ͷ෼ྨʢ෦෼తʣ ‣ ઢܗܭը໰୊ ‣ ໨తؔ਺ɾ੍໿৚݅ͷू߹͕̍࣍ࣜͷΈ ‣ ඇઢܗܭը໰୊ ‣ ໨తؔ਺ɾ੍໿৚݅ʹඇઢܗ͕ࣜଘࡏ͢Δ ‣

    ੔਺ܭը໰୊ʢࠞ߹੔਺ɾ७੔਺ʣ ‣ ੍໿৚݅ͷҰ෦·ͨ͸શͯͷม਺ͷͱΔ஋͕੔਺ ‣ ̎࣍ܭը໰୊ ‣ ໨తؔ਺͕̎࣍ࣜɼ੍໿৚݅ͷू߹͕̍࣍ࣜ etc…
  5. ̎ม਺ͷੜ࢈ܭը໰୊ ‣ M1, M2, M3ͷݪྉΛ༻͍ͯɼP1, P2Λੜ࢈͍ͯ͠Δ ‣ ར༻ՄೳྔɿM1 ≦ 27t,

    M2 ≦ 45t, M3 ≦15t ‣ P1ͷੜ࢈ ‣ M1Λ2t, M2Λ8t, M3Λ3t ‣ ར५͸2ສʂ
  6. ̎ม਺ͷੜ࢈ܭը໰୊ ‣ M1, M2, M3ͷݪྉΛ༻͍ͯɼP1, P2Λੜ࢈͍ͯ͠Δ ‣ ར༻ՄೳྔɿM1 ≦ 27t,

    M2 ≦ 45t, M3 ≦15t ‣ P1ͷੜ࢈ ‣ M1Λ2t, M2Λ8t, M3Λ3t ‣ ར५͸2ສʂ ‣ P2ͷੜ࢈ ‣ M1Λ6t, M2Λ6t, M3Λ1t ‣ ར५͸5ສʂ
  7. ̎ม਺ͷੜ࢈ܭը໰୊ ‣ M1, M2, M3ͷݪྉΛ༻͍ͯɼP1, P2Λੜ࢈͍ͯ͠Δ ‣ ར༻ՄೳྔɿM1 ≦ 27t,

    M2 ≦ 45t, M3 ≦15t ‣ P1ͷੜ࢈ ‣ M1Λ2t, M2Λ8t, M3Λ3t ‣ ར५͸2ສʂ ‣ P2ͷੜ࢈ ‣ M1Λ6t, M2Λ6t, M3Λ1t ‣ ར५͸5ສʂ ར५Λ࠷େԽ͍ͨ͠
  8. ̎ม਺ͷੜ࢈ܭը໰୊ʢ੔਺ʣ ‣ M1, M2, M3ͷݪྉΛ༻͍ͯɼP1, P2Λੜ࢈͍ͯ͠Δ ‣ ར༻ՄೳྔɿM1 ≦ 27t,

    M2 ≦ 45t, M3 ≦15t ‣ P1ͷੜ࢈ ‣ M1Λ2t, M2Λ8t, M3Λ3t ‣ ར५͸2ສʂ ‣ P2ͷੜ࢈ ‣ M1Λ6t, M2Λ6t, M3Λ1t ‣ ར५͸5ສʂ ར५Λ࠷େԽ͍ͨ͠
  9. ̎ม਺ͷੜ࢈ܭը໰୊ʢ੔਺ʣ ‣ M1, M2, M3ͷݪྉΛ༻͍ͯɼP1, P2Λੜ࢈͍ͯ͠Δ ‣ ར༻ՄೳྔɿM1 ≦ 27t,

    M2 ≦ 45t, M3 ≦15t ‣ P1ͷੜ࢈ɹݸ਺ͰΫϨ ‣ M1Λ2t, M2Λ8t, M3Λ3t ‣ ར५͸2ສʂ ‣ P2ͷੜ࢈ɹݸ਺ͰΫϨ ‣ M1Λ6t, M2Λ6t, M3Λ1t ‣ ར५͸5ສʂ ར५Λ࠷େԽ͍ͨ͠
  10. ̎ม਺ͷੜ࢈ܭը໰୊ʢ੔਺ʣ ‣ M1, M2, M3ͷݪྉΛ༻͍ͯɼP1, P2Λੜ࢈͍ͯ͠Δ ‣ ར༻ՄೳྔɿM1 ≦ 27t,

    M2 ≦ 45t, M3 ≦15t ‣ P1ͷੜ࢈ɹݸ਺ͰΫϨ ‣ M1Λ2t, M2Λ8t, M3Λ3t ‣ ར५͸2ສʂ ‣ P2ͷੜ࢈ɹݸ਺ͰΫϨ ‣ M1Λ6t, M2Λ6t, M3Λ1t ‣ ར५͸5ສʂ ར५Λ࠷େԽ͍ͨ͠ ੔਺ ੔਺
  11. ઢܗܭըͱ੔਺ܭըͷҧ͍ ‣ ઢܗܭը໰୊ͷ࠷దղ ‣ ୯ମ๏ͱ͍͏ɺลΛḷ͍ͬͯ͘ํ๏͕࣮༻త ‣ ଟ߲ࣜ࣌ؒͰղ͚ͳ͍ͱ͖͕͋Δ ‣ ಺఺๏ͱ͍͏ղ๏΋ଘࡏ͢Δ ‣

    ࣮ߦྖҬͷ಺෦͔ΒղΛ୳ࡧ͢Δ ‣ ੔਺ܭըͷ࠷దղ ‣ ઢܗܭըͰಘΒΕͨ࠷దղʹ͍ۙ੔਺ͷ఺͕࠷దղʹͳΒͳ͍ ৔߹͕͋Δ ಺఺๏͸ ϫγ͕ҭͯͨ