Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
線形計画法とカーマーカー法 〜プログラマのための数学勉強会#3〜
Search
Shintaro Kaneko
May 22, 2015
Programming
3
74k
線形計画法とカーマーカー法 〜プログラマのための数学勉強会#3〜
カーマーカー法はやめて「線形計画法と整数計画法」です。
Shintaro Kaneko
May 22, 2015
Tweet
Share
More Decks by Shintaro Kaneko
See All by Shintaro Kaneko
How to keep growing SRE team at Eureka
kaneshin
3
8.9k
Go - CLI Tools Design
kaneshin
0
6.7k
Summer Internship 2018 - The principle of the eureka summer internship 2018
kaneshin
2
89
Summer Internship 2018 - The eureka summer internship 2018
kaneshin
0
85
Summer Internship 2018 - How to develop a product
kaneshin
0
67
How to write Go code
kaneshin
8
8k
Go Package Guidelines
kaneshin
1
1.1k
net/http package ~GoConference 2017 Spring~
kaneshin
1
2.7k
Essentials of Golang
kaneshin
5
13k
Other Decks in Programming
See All in Programming
現場で役立つモデリング 超入門
masuda220
PRO
13
3k
Amazon Neptuneで始めてみるグラフDB-OpenSearchによるグラフの全文検索-
satoshi256kbyte
4
340
What’s New in Compose Multiplatform - A Live Tour (droidcon London 2024)
zsmb
1
350
Piniaの現状と今後
waka292
5
1.5k
詳細解説! ArrayListの仕組みと実装
yujisoftware
0
490
のびしろを広げる巻き込まれ力:偶然を活かすキャリアの作り方/oso2024
takahashiikki
1
410
生成 AI を活用した toitta 切片分類機能の裏側 / Inside toitta's AI-Based Factoid Clustering
pokutuna
0
620
僕がつくった48個のWebサービス達
yusukebe
18
17k
アジャイルを支えるテストアーキテクチャ設計/Test Architecting for Agile
goyoki
7
2.8k
開発効率向上のためのリファクタリングの一歩目の選択肢 ~コード分割~ / JJUG CCC 2024 Fall
ryounasso
0
370
ピラミッド、アイスクリームコーン、SMURF: 自動テストの最適バランスを求めて / Pyramid Ice-Cream-Cone and SMURF
twada
PRO
9
1k
Go言語でターミナルフレンドリーなAIコマンド、afaを作った/fukuokago20_afa
monochromegane
2
140
Featured
See All Featured
Build The Right Thing And Hit Your Dates
maggiecrowley
32
2.4k
Unsuck your backbone
ammeep
668
57k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
14
1.9k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
27
4.2k
Designing for Performance
lara
604
68k
Building Applications with DynamoDB
mza
90
6.1k
Scaling GitHub
holman
458
140k
Designing for humans not robots
tammielis
249
25k
Optimizing for Happiness
mojombo
376
69k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
126
18k
What's in a price? How to price your products and services
michaelherold
243
12k
GraphQLの誤解/rethinking-graphql
sonatard
66
10k
Transcript
ઢܗܭը๏ͱΧʔϚʔΧʔ๏ ϓϩάϥϚͷͨΊͷֶษڧձ
ઢܗܭը๏ͱΧʔϚʔΧʔ๏
ΧʔϚʔΧʔͷ୭ಘ
ΧʔϚʔΧʔͷ୭ಘ ͑ͬʂʁ
ઢܗܭը๏ͱΧʔϚʔΧʔ๏
ઢܗܭը๏ͱܭը๏
ࣗݾհ Shintaro Kaneko ‣ גࣜձࣾΤϨΧ ‣ pairsͷ։ൃશൠ୲ ‣ ࠷ۙGoݴޠͰ։ൃ͍ͯ͠·͢ ‣
େֶ࣌ ‣ ࠷దԽͷඇઢܗܭը๏Λઐ߈ ‣ github.com/kaneshin/lbfgs ʢݹʣ ‣ ඍํఔ͕͖ࣜͩͬͨ kaneshin kaneshinth shintaro.kaneko
ࣗݾհ Shintaro Kaneko ‣ גࣜձࣾΤϨΧ ‣ pairsͷ։ൃશൠ୲ ‣ ࠷ۙGoݴޠͰ։ൃ͍ͯ͠·͢ ‣
େֶ࣌ ‣ ࠷దԽͷඇઢܗܭը๏Λઐ߈ ‣ github.com/kaneshin/lbfgs ʢݹʣ ‣ ඍํఔ͕͖ࣜͩͬͨ kaneshin kaneshinth shintaro.kaneko ٱ͠ৼΓͷֶʂ
Copyright © 2009-2015 eureka, Inc. All rights reserved.
Copyright © 2009-2015 eureka, Inc. All rights reserved.
Copyright © 2009-2015 eureka, Inc. All rights reserved. ‣ pairsϚονϯάΞϧΰϦζϜ͕ඇৗʹॏཁ
‣ ๛ͳϢʔβʔͷσʔλͷ׆༻ ‣ ΤϯδχΞ͕Ϗδωε໘͔ΒΞϧΰϦζϜΛߟ͑Δ ‣ ࣾษڧձͰRษڧʴ౷ܭֶͷษڧձ։࠵ ‣ ϏοάσʔλΛਖ਼͍ࣝ͠Ͱ༻͢Δ ‣ ౷ܭΛؒҧͬͨೝࣝͰ༻͠ͳ͍ʢภͬͨσʔλΛΘͳ͍
ຊ౷ܭͷͰ ͋Γ·ͤΜʂ
ຊͷΰʔϧ
ຊͷΰʔϧ ࠷దԽʢཧܭըʣΛ ͪΐͬͱͰͬͯΒ͏
ຊ͢͜ͱ
ຊ͢͜ͱ ΦϖϨʔγϣϯζɾϦαʔν ࠷దԽʢཧܭըʣ ઢܗܭըͱܭը
ຊΒͳ͍͜ͱ Βͳ͍͜ͱ ϓϩάϥϜͰγϛϡϨʔγϣϯ Γ͔ͨͬͨΜͰ͕͢ ͕࣌ؒݫ͍͠ͷͰׂѪ
ຊ͢͜ͱ ΦϖϨʔγϣϯζɾϦαʔν ࠷దԽʢཧܭըʣ ઢܗܭըͱܭը
ΦϖϨʔγϣϯζɾϦαʔν
ΦϖϨʔγϣϯζɾϦαʔνʢORʣ ‣ OR૬͍Λࢦ͢ ‣ ༷ʑͳܭըʹରͯ͠࠷ޮతʹͳΔΑ͏ҙࢥܾఆ͢Δ ‣ ֶɾ౷ܭతϞσϧɺΞϧΰϦζϜͷར༻ ‣ ʮγϛϡϨʔγϣϯʯͷཱ֬ORཱ͕ऀ ‣
ORͰݱ࣮ͷΛཧϞσϧʹஔ͖͑Δ ‣ ࠷దԽɼͪߦྻɼ֬ͳͲ ‣ ܉ࣄతؔ৺ͱܦࡁతؔ৺͕ڧ͍
ͭ·Γʁ
ྫ͑ɼேͷ௨ۈిं
ேͷ௨ۈిं ‣ ܦ࿏ݕࡧʹʮYahoo!࿏ઢʯ͍ͬͯΔͱࢥ͍·͢ ‣ ཪଆͰʮܦ࿏ޮʯʮίετޮʯͷߟྀ ‣ Ո͔ΒӺ·Ͱʹཁ͢Δ࣌ؒΛܭࢉ ‣ ెาӺͰిंΛͨͳ͍Α͏ʹग़ൃ͢Δܭը ‣
ࢁखઢͷَͷΑ͏ͳμΠϠ ‣ γϛϡϨʔγϣϯ͕Կສճ͞Εͨ݁Ռ
ேͷ௨ۈిं ‣ ܦ࿏ݕࡧʹʮYahoo!࿏ઢʯ͍ͬͯΔͱࢥ͍·͢ ‣ ཪଆͰʮܦ࿏ޮʯʮίετޮʯͷߟྀ ‣ Ո͔ΒӺ·Ͱʹཁ͢Δ࣌ؒΛܭࢉ ‣ ెาӺͰిंΛͨͳ͍Α͏ʹग़ൃ͢Δܭը ‣
ࢁखઢͷَͷΑ͏ͳμΠϠ ‣ γϛϡϨʔγϣϯ͕Կສճ͞Εͨ݁Ռ ͜ΕΒORͷҰछ
ׂͱۙʹOR
ຊ͢͜ͱ ΦϖϨʔγϣϯζɾϦαʔν ࠷దԽʢཧܭըʣ ઢܗܭըͱܭը
࠷దԽ
࠷దԽORͷҰཁૉ
ઢܗܭը ඇઢܗܭը ܭը ήʔϜཧ OR σʔλ ϚΠχϯά : : :
: ۚ༥ֶ ࠷దԽ
࠷దԽͱ ʢoptimization problemʣ ཧܭըͱΑΕΔ ʢMathematical Programming Problemʣ
࠷దԽͱ ༩͑ΒΕͨ݅ͷͱͰ ԿΒ͔ͷؔΛ࠷খԽɾ࠷େԽ͢Δ
࠷దԽͱ ༩͑ΒΕͨ݅ͷͱͰ ԿΒ͔ͷؔΛ࠷খԽɾ࠷େԽ͢Δ
࠷దԽͱ
࠷దԽͱ ੍݅ͷͱͰ
࠷దԽͱ ੍݅ͷͱͰɼతؔͷ
࠷దԽͱ ੍݅ͷͱͰɼతؔͷ ࠷దͱͳΔ
࠷దԽͱ ੍݅ͷͱͰɼతؔͷ ࠷దͱͳΔ࠷దղΛ
࠷దԽͱ ੍݅ͷͱͰɼతؔͷ ࠷దͱͳΔ࠷దղΛ࣮ߦՄೳྖҬ͔Β୳͢
࠷దԽͱ ੍݅ͷͱͰɼతؔͷ ࠷దͱͳΔ࠷దղΛ࣮ߦՄೳྖҬ͔Β୳͢
తؔɾ੍݅ʹΑͬͯ ࠷దԽྨ͞ΕΔ
࠷దԽͷྨʢ෦తʣ ‣ ઢܗܭը ‣ తؔɾ੍݅ͷू߹͕̍࣍ࣜͷΈ ‣ ඇઢܗܭը ‣ తؔɾ੍݅ʹඇઢܗ͕ࣜଘࡏ͢Δ ‣
ܭըʢࠞ߹ɾ७ʣ ‣ ੍݅ͷҰ෦·ͨશͯͷมͷͱΔ͕ ‣ ̎࣍ܭը ‣ త͕ؔ̎࣍ࣜɼ੍݅ͷू߹͕̍࣍ࣜ etc…
ઢܗܭը ඇઢܗܭը ܭը ήʔϜཧ OR ࠷దԽ σʔλ ϚΠχϯά : :
: : ۚ༥ֶ
ઢܗܭը ඇઢܗܭը ܭը ήʔϜཧ OR ࠷దԽ σʔλ ϚΠχϯά : :
: : ۚ༥ֶ
ຊ͢͜ͱ ΦϖϨʔγϣϯζɾϦαʔν ࠷దԽʢཧܭըʣ ઢܗܭըͱܭը
ઢܗܭը
ઢܗܭը తؔɾ੍݅ͷू߹͕̍࣍ࣜͷΈ
ྫɿੜ࢈ܭը
̎มͷੜ࢈ܭը ‣ M1, M2, M3ͷݪྉΛ༻͍ͯɼP1, P2Λੜ࢈͍ͯ͠Δ
̎มͷੜ࢈ܭը ‣ M1, M2, M3ͷݪྉΛ༻͍ͯɼP1, P2Λੜ࢈͍ͯ͠Δ ‣ ར༻ՄೳྔɿM1 ≦ 27t,
M2 ≦ 45t, M3 ≦15t
̎มͷੜ࢈ܭը ‣ M1, M2, M3ͷݪྉΛ༻͍ͯɼP1, P2Λੜ࢈͍ͯ͠Δ ‣ ར༻ՄೳྔɿM1 ≦ 27t,
M2 ≦ 45t, M3 ≦15t ‣ P1ͷੜ࢈ ‣ M1Λ2t, M2Λ8t, M3Λ3t ‣ ར५2ສʂ
̎มͷੜ࢈ܭը ‣ 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ສʂ
̎มͷੜ࢈ܭը ‣ 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ສʂ ར५Λ࠷େԽ͍ͨ͠
̎มͷੜ࢈ܭը ݪྉʘ P1 P2 ར༻Մೳྔ M1 2 6 27 M2
8 6 45 M3 3 1 15 ར५ 2 5
̎มͷੜ࢈ܭը ݪྉʘ P1 P2 ར༻Մೳྔ M1 2 6 27 M2
8 6 45 M3 3 1 15 ར५ 2 5
̎มͷੜ࢈ܭը P1, P2ͷੜ࢈ྔΛมྔ (x1, x2) ͱ͢Δͱ Λ࠷େԽͤ͞Δ࠷దԽͱͳΔ
̎มͷੜ࢈ܭը ݪྉʘ P1 P2 ར༻Մೳྔ M1 2 6 27 M2
8 6 45 M3 3 1 15 ར५ 2 5
̎มͷੜ࢈ܭը ੍݅ར༻Մೳͳݪྉͷྔͱඇෛ
̎มͷੜ࢈ܭը ੍݅ར༻Մೳͳݪྉͷྔͱඇෛ
̎มͷੜ࢈ܭը ઢܗܭըͱͯ͠ఆࣜԽ
̎มͷੜ࢈ܭը ઢܗܭըͱͯ͠ఆࣜԽ ͜ͷͷ࠷దղΛٻΊ͍ͨ
ͱ͜ΖͰ
࿈ଓ͔ʁ
ܭը
ܭը ੍݅ͷҰ෦·ͨશͯͷมͷͱΔ͕
ྫɿੜ࢈ܭըʢʣ
̎มͷੜ࢈ܭըʢʣ ‣ 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ສʂ ར५Λ࠷େԽ͍ͨ͠
̎มͷੜ࢈ܭըʢʣ ‣ 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ສʂ ར५Λ࠷େԽ͍ͨ͠
̎มͷੜ࢈ܭըʢʣ ‣ 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ສʂ ར५Λ࠷େԽ͍ͨ͠
̎มͷੜ࢈ܭըʢʣ ઢܗܭըͱͯ͠ఆࣜԽ
̎มͷੜ࢈ܭըʢʣ ઢܗܭըͱͯ͠ఆࣜԽ ͰΫϨ ͰΫϨ
̎มͷੜ࢈ܭըʢʣ ܭըͱͯ͠ఆࣜԽ
̎มͷੜ࢈ܭըʢʣ ܭըͱͯ͠ఆࣜԽ ͜ͷͷ࠷దղΛٻΊ͍ͨ
άϥϑͰΈΔղ๏ ԼهΛάϥϑͰදݱ͢Δ
None
None
ઢܗܭըͷ߹
ઢܗܭըͷ߹
ઢܗܭըͷ߹
ઢܗܭըͷ߹ ࠷దղ
ܭըͷ߹
ܭըͷ߹ ࠷దղ?
ܭըͷ߹ ࠷దղ!
ઢܗܭըͱܭըͷҧ͍ ‣ ઢܗܭըͷ࠷దղ ‣ ୯ମ๏ͱ͍͏ɺลΛḷ͍ͬͯ͘ํ๏͕࣮༻త ‣ ଟ߲ࣜ࣌ؒͰղ͚ͳ͍ͱ͖͕͋Δ ‣ ๏ͱ͍͏ղ๏ଘࡏ͢Δ ‣
࣮ߦྖҬͷ෦͔ΒղΛ୳ࡧ͢Δ ‣ ܭըͷ࠷దղ ‣ ઢܗܭըͰಘΒΕͨ࠷దղʹ͍ۙͷ͕࠷దղʹͳΒͳ͍ ߹͕͋Δ ๏ ϫγ͕ҭͯͨ
·ͱΊ
·ͱΊ ࠷దԽ ͳΜͱͳ͘ཧղͯ͠Β͑ͨͰ͠ΐ͏͔ʁ
·ͱΊ - ࠷ޙʹ ‣ ͜ͷ·ͩ·ͩϓϩάϥϜͷࢿ࢈͕গͳ͍ ‣ ཧϞσϧʹམͱͨ͢Ίʹֶͷ͕ࣝͳ͍ͱ͍͠ ‣ ઐతͳاۀ͕ಠ͍ͯ͠Δײ͕͋Δ ‣
ͦΕͧΕͷܭըߟ͑Δ͜ͱ͕ҧ͏ ‣ ݚڀ͍ͨ͠߹ΛߜΔ͖
·ͱΊ ͜ΕҎ্ͷ࠷దԽͷ γϛϡϨʔγϣϯͳͲ ୭͔͕ͬͯ͘ΕΔͱ৴͍ͯ͡·͢ʂ
Thank you :)
͓·͚ - ๏ʢΧʔϚʔΧʔ๏ʣ