Share
Embed
メタヒューリスティクスに基づく汎用線形整数計画ソルバーの開発
2024/11/22 Optimization Night #9 講演資料
https://optimization.connpass.com/event/332590/
yk
November 23, 2024
Transcript
33 slides
-
࣍ ͡Ίʹ ιϧόʔ։ൃͷഎܠɾత ΞϧΰϦζϜ֓ཁ ઃܭɾ࣮ͷϙΠϯτ
։ൃϓϩηε ͓ΘΓʹ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." -
࣍ ͡Ίʹ ιϧόʔ։ൃͷഎܠɾత ΞϧΰϦζϜ֓ཁ ઃܭɾ࣮ͷϙΠϯτ
։ൃϓϩηε ͓ΘΓʹ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." -
͡Ίʹ ઢܗܭըʹର͢ΔϝλώϡʔϦεςΟΫειϧόʔl13*/5&.14˞z 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." n ࢬݶఆ๏ιϧόʔ͕ੑೳΛൃشͮ͠Β͍نɾߏͷઢܗܭըͷΠϯελϯε ʹରͯ͠ɼྑ࣭ͳ࣮ߦՄೳղΛ࣌ؒͰൃݟ͢Δ͜ͱΛతͱͨࣗ͠࡞ιϧόʔ n ࢬݶఆ๏ιϧόʔͷੑೳΛิ͠ɼ࣮༻తʹʮղ͚ΔʯΠϯελϯεΛ૿͢ͷ͕ͶΒ͍
n $ ϔομʔΦϯϦʔϥΠϒϥϦͱͯ͠ϞσϦϯάڥͱ͋Θ࣮ͤͯɾఏڙɽ .14ϑΝΠϧΛೖྗͱͯ͠ड͚͚ΔελϯυΞϩϯ൛༻ҙ n .*5-JDFOTFͷͱΦʔϓϯιʔειϑτΣΞͱͯ͠ެ։த ˞13*/5&.141P3UBCMF*/5&HFS.BUIFNBUJDBM1SPHSBNNJOH4PMWFSͷུʜͷͭΓɽൃԻʮϓϥϯλϯʯ -
͡Ίʹ ੑೳධՁʢ.*1-*##FODINBSL4FUʣ Ұ෦Πϯελϯεʹ͓͍ͯɼࢬݶఆ๏ιϧόʔΛิ͢ΔੑೳΛൃش 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ϕϯνϚʔΫηοτ .*1-*##FODINBSL4FU IUUQTNJQMJC[JCEF ७ܭըΠϯελϯεͷͷ͏ͪɼ࣮ߦෆՄೳΠϯελϯεͱFOMJHIU@IBSE˞Λআ͘
ܭࢉ࣌ؒ TFD ධՁର 13*/5&.14W ൺֱର $#$ 4$*1 )J()4ʢ͍ͣΕ044ࢬݶఆ๏ιϧόʔʣ $#$ 4$*1 )J()4ͷͲΕΑΓ ྑ͍ղΛٻΊΔ͜ͱͷͰ͖ͨΠϯελϯε ˞ɿ͍ΘΏΔʮϥΠπΞτʯɻదͳલॲཧʹΑΓ࠷దղ͕ٻ·ͬͯ͠·͏ͷͰɼώϡʔϦεςΟΫεͷੑೳධ Ձʹ͔ͳ͍ɽ -
͡Ίʹ ੑೳධՁʢ.*1-*# 0QFOΠϯελϯε˞ʣ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." /P Πϯελϯε λΠϓ ܾఆม
੍ Լք ʢ࿈ଓ؇ʣ ఆߋ৽ཤྺʢݱࡏ ੨ࣈ͕ຊιϧόͰߋ৽ͨ͠ఆʣ DED ू߹ύοΩϯά ˠˠʜˠ TDQKTDQL ू߹ඃ෴ ˠ TDQL ू߹ඃ෴ ˠˠʜˠ TDQM ू߹ඃ෴ ˠˠ TDQN ू߹ඃ෴ ˠˠʜˠ TDQO ू߹ඃ෴ ˠˠˠʜˠ ˞ɿ࠷దੑͷূ໌ͷ͋Δղ͕ະൃݟ࣮͘͠ߦෆՄೳੑ͕ະূ໌Ͱ͋ΔΠϯελϯε IUUQTNJQMJC[JCEFJOTUBO DF@EFUBJMT@TDQKTDJQIUNM ΑΓʢʣɻ -
0QUJNJ[BUJPO/JHIUr:VKJ,0(6." minimize ! 𝑥" + 10 𝑥# subject
to 66 𝑥" + 14 𝑥# ≥ 1430, −82 𝑥" + 28 𝑥# ≥ 1306, 𝑥", 𝑥# ∈ ℤ. n ࣜϕʔεͷίʔυͰ࠷దԽΛهड़Մೳ n มɾ੍ͷଟ࣍ݩఴࣈʹରԠ n ੵʢ𝒄!𝒙 ʣɼ૯ʢ∑! 𝑥! ʣͳͲɼසग़͢Δهड़ʹର͢Δҥߏจඋ ྫ ͡Ίʹ ϞσϦϯάڥ -
0QUJNJ[BUJPO/JHIUr:VKJ,0(6." <>:,PHVNB 5BCV4FBSDI#BTFE)FVSJTUJD4PMWFSGPS(FOFSBM*OUFHFS-JOFBS1SPHSBNNJOH1SPCMFNT *&&& "DDFTT WPM QQ
l ΞϧΰϦζϜৄࡉ l Φʔϓϯιʔεࢬݶఆ๏ ιϧόʔͱͷੑೳൺֱ l ιϧόʔʹΈೖΕͨ ओཁͳʹؔ͢Δ "CMBUJPO4UVEZ ͓ͳ༰ ͡Ίʹ ؔ࿈จ -
࣍ ͡Ίʹ ιϧόʔ։ൃͷഎܠɾత ΞϧΰϦζϜ֓ཁ ઃܭɾ࣮ͷϙΠϯτ
։ൃϓϩηε ͓ΘΓʹ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." -
ιϧόʔ։ൃͷഎܠɾత ࣮ʹର͢Δཧ࠷దԽͷద༻ϓϩηε n ܾఆมɾ੍݅ɾత͕ؔ࠷ॳ͔Β֬ఆ͍ͯ͠Δέʔε·ͣͳ͍ n ʮղ͘Ձͷ͋ΔʯΛ࡞ΓࠐΉʮϞσϦϯάʯ͕࠷େͷؔ n ϞσϦϯάஈ֊Ͱ։ൃ͢ΔϓϩτλΠϓΞϧΰϦζϜʹ࣌ؒΛ͔͚ͨ͘ͳ͍ n ݕ౼ͷ݁Ռʮ࠷దԽ͠ͳ͍ʯͱ͍͏݁ʹͳΔ͜ͱेʹ͋Γ͑Δ
n ͍͔ʹͯ͠खؒΛ͔͚ͣʹղΛٻΊΔ͔ʁ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ϞσϦϯά ΞϧΰϦζϜ ઃܭɾ࣮ γεςϜԽ ɾӡ༻ ղܾ ɾ࠷దԽ Ϣʔβ ΠϯλϏϡʔ ՝ઃఆ˞ ఆࣜԽ ϓϩτλΠϓ ΞϧΰϦζϜ ࣮ ࣮ ղͷධՁ ˞ɿ࠷దԽͷϢʔβɼఆܭࢉڐ༰࣌ؒɼ࣮ߦ͢ΔλΠϛϯάɾසɼར༻Մೳσʔλͱͦͷෆ࣮֬ੑɼඅ༻ରޮՌɼར ӹ૬ͳͲͷ؍͔Βɼ࠷దԽͷཁ൱࠷దԽείʔϓΛܾఆ͢Δ͜ͱ͕ΰʔϧ -
ιϧόʔ։ൃͷഎܠɾత खؒΛ͔͚ͣʹ࠷దԽ͍ͨ͠ͱ͖ʹΔ͜ͱ n ࠷ॳʹࢼ͢͜ͱ n ʢࠞ߹ʣܭըͱͯ͠ఆࣜԽͯ͠.*1ιϧόʔ˞Λద༻͢Δ n యܕͱͯۙ͠ࣅ͠ɼཱ֬͞ΕͨΞϧΰϦζϜΛద༻͢Δ n ൺֱతγϯϓϧͳώϡʔϦεςΟΫεΛ࣮ͯ͠ద༻͢Δ
n ʢࠞ߹ʣܭը͕ղ͚ͳ͍ͱ͖ͷॲํᝦ n ˓ͷنΛॖখ͋Δׂ͍ͯ͠ղ͘ n ˓.*1ιϧόʔΛ͍ͭͭɼదͳܭࢉ࣌ؒͰଧͪͬͯఘΊΔ n ˚.*1ιϧόʔΛ͍ͭͭɼߏΛ׆͔ͨ͠ಛघղ๏Λߏங͢Δ n º ಛԽͷߴੑೳώϡʔϦεςΟΫεΛ͍͖ͳΓઃܭɾ࣮͢Δ n ࠷దԽ͢ΔͷΛΊ·͢ɼͱͳͬͨͱ͖ͷϦεΫ͕େ͖͍ n ˓.*1ιϧόʔͷ͔ΘΓʹ൚༻ώϡʔϦεςΟΫειϧόʔΛద༻͢Δ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ˞ɿຊࢿྉͰʮ.*1ιϧόʔʯͱʮࢬݶఆ๏ιϧόʔʯΛ΄΅ಉ͡ҙຯͰ͍·͢ ͜ΕΛ࣮༻తͳબࢶͱͯ͠Ճ͍͑ͨʂ -
ιϧόʔ։ൃͷഎܠɾత ઢܗܭըʢ*-1ʣ n ࿈ଓมѻ͑ͳ͍ͷͷɼ͞·͟·ͳ߹ͤ࠷దԽΛఆࣜԽՄೳ n ΠϯελϯεσʔλͰදݱ͞Εɼ-1ܗࣜ.14ܗࣜͳͲͷඪ४తͳ ϑΝΠϧϑΥʔϚοτ͕ଘࡏ n ҰϞσϧԽ͕ྃ͢ΕɼෳͷιϧόΛࢼ͢͜ͱ͕Ͱ͖Δ
0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ILP : minimize 𝒍 % 𝒙 % 𝒖 𝒂( )𝒙 = 𝑏( , 𝑖 ∈ 𝐼* , 𝒂( )𝒙 ≤ 𝑏( , 𝑖 ∈ 𝐼% , 𝑥+ ∈ ℤ, 𝑗 ∈ 𝐽 𝒄)𝒙 subject to 𝐼! :੍ࣜ݅ͷఴࣈू߹ɼ 𝐼" ɿෆ੍ࣜ݅ͷఴࣈू߹ɼ 𝐽ɿܾఆมͷఴࣈू߹ -
n -PDBM*-1<><> n ࣮ߦՄೳੑͷ୳ࡧʢ4FBSDIʣɼతؔͷվળʢ*NQSPWFʣɾղͷम ਖ਼ʢ3FTUPSFʣͷͭͷϞʔυΛભҠ͢Δɼہॴ୳ࡧ๏ʹجͮ͘ιϧόʔ n .*1-*#ͷ0QFOΠϯελϯεͷఆղΛۙଟߋ৽ n .*1 ରԠ൛ͷ-PDBM.*1ଘࡏ
n (1--JDFOTF n #BSZPOZY<><> n (FOFSBMJ[FE %BH8FEFMJO)FVSJTUJDʹجͮ͘ιϧόʔ n .*5-JDFOTF 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ιϧόʔ։ൃͷഎܠɾత *-1͚044ώϡʔϦεςΟοΫιϧόʔ <>IUUQTHJUIVCDPNTIBPXFJDBJHSPVQ-PDBM*-1 <>1-JOFUBM /FX$IBSBDUFSJ[BUJPOTBOE&GGJDJFOU-PDBM4FBSDIGPS(FOFSBM*OUFHFS-JOFBS1SPHSBNNJOH BS9JW QSFQSJOUBS9JW <>IUUQTHJUIVCDPNRVFTOFMCBSZPOZY <>4.BRSPUFUBM -FBSOJOH1BSBNFUFSTPGUIF8FEFMJO)FVSJTUJDXJUI"QQMJDBUJPOUP$SFXBOE#VT%SJWFS 4DIFEVMJOH IBM ༻ͰHVSPCJ /P3FM)FVSJTUJDʣ/VPSJVN0QUJNJ[FSʢXDTQ XMTʣ ͳͲ͕͋Δ͕ɼ044ͷώϡʔϦεςΟοΫιϧόʔগͳ͍ͷ͕ݱঢ় -
࣍ ͡Ίʹ ιϧόʔ։ൃͷഎܠɾత ΞϧΰϦζϜ֓ཁ ઃܭɾ࣮ͷϙΠϯτ
։ൃϓϩηε ͓ΘΓʹ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." -
ᶃ Πϯελϯεʹରͯ͠ݸผʹௐ͖͢ύϥϝʔλ͕ͳ͍͜ͱ n ௐ͖͢ύϥϝʔλ͕ͻͱͭͰ͋Δͱ൚༻ιϧόͱ͍ͯͮ͠Β͍ n ͱ͘ʹతؔͷϨϯδʹґଘ͢Δύϥϝʔλͷௐࠔ n ύϥϝʔλ͕͋Δ͜ͱࣗମ0,ɽͨͩ͠ɼଟ༷ͳΠϯελϯεʹରͯ͠ ྑͳੑೳΛ͕ࣔ͋͢Δ͜ͱɽ࣮͘͠ߦதʹࣗಈௐͰ͖Δ͜ͱ n
ྫ֎ɿ୳ࡧ࣌ؒɾ෮ճͷ্ݶʢϢʔβʹΑΔมߋɾௐΛఆʣ ᶄ ֤෮Ͱͷڍಈ͕ܭࢉ࣌ؒ෮ճͷ্ݶʹґଘ͠ͳ͍͜ͱ n ʮܭࢉ࣌ؒʢ͋Δ͍෮ճʣΛԆ৳ͯ͠࠶ܭࢉͨ͠Βղ͕ѱԽͨ͠ʯ ͱ͍͏͜ͱ͕ͳ͍͜ͱΛอূ͍ͨ͠ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ΞϧΰϦζϜ֓ཁ ΞϧΰϦζϜͷཁ݅ʢͱͯ͠উखʹఆΊͨͷʣ ᶃᶄΛຬͨ͢ΞϧΰϦζϜͱͯ͠8FJHIUFE 5BCV4FBSDI<>Λ࠾༻ <>,/POPCFBOE5*CBSBLJ "O*NQSPWFE5BCV4FBSDI.FUIPEGPSUIF8FJHIUFE$POTUSBJOU4BUJTGBDUJPO 1SPCMFN *OG4ZTU0QFS3FT 7PM QQ -
n 5BCV4FBSDI<> n ϝλώϡʔϦεςΟΫεͷҰछ n ࠷ྑҠಈઓུ˞ʹجͮ͘ہॴ୳ࡧ๏ͷ֦ுͱΈͳͤΔ n Ұมߋͨ͠ղͷଐੑΛ5BCV-JTUʹอ࣋͠ɼ5BCV5FOVSF͕ఆΊΔظؒத ͷ࠶ૢ࡞Λېࢭ͢Δ͜ͱͰɼہॴղ͔Βͷग़ͱ୳ࡧͷଟ༷ԽΛਤΔ n
ʹ͋Θͤͨ5BCV-JTUอ࣋ଐੑɾ୳ࡧۭؒɾۙɾධՁؔͷઃܭ͕ඞཁ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." 5BCV4FBSDIͷ୳ࡧ֓೦ਤ <>'(MPWFS 'VUVSF1BUITGPS*OUFHFS1SPHSBNNJOHBOE-JOLTUP"SUJGJDJBM*OUFMMJHFODF $PNQVUFST 0QFSBUJPOT3FTFBSDI 7PM /P QQ ˞ɿۙղͯ͢ΛධՁ͠ɼධՁ͕ؔ࠷ྑͷղʹભҠ͢Δઓུ l ܾఆมɿ𝑥 ∈ 0,1 ! l 5BCV5FOVSFɿ l ۙɿ୯ҰมͷϑϦοϓ l 5BCV-JTUอ࣋ଐੑɿܾఆมͷఴࣈ ੨ࣈɿૢ࡞ͨ͠ม ɿૢ࡞ېࢭม ෮ճ 解 (0, 0, 0, 0, 0) (0, 1, 0, 0, 0) (0, 1, 0, 1, 0) (0, 1, 0, 1, 1) (0, 0, 0, 1, 1) ΞϧΰϦζϜ֓ཁ 8FJHIUFE5BCV4FBSDIʢ̍ʣ -
n 5BCV4FBSDIͷಛ B ˓ύϥϝʔλௐ͕༰қ n ύϥϝʔλ5BCV5FOVSFͷΈͰ͋Γɼ͔ͭ*-1ͷ߹ 5BCV5FOVSFఔͱ͓͚ͯ͠ɼܦݧతʹൺֱతൣͳ Πϯελϯεʹରͯ͠ੑೳΛൃش C ˓ߴ͍ہॴ୳ࡧੑೳ
n ॳظղ͔ΒᩦཉతʹղΛߋ৽͢ΔͨΊɼॳظղͷपลʹ͋Δ վળղΛݟಀ͞ͳ͍ D ˓ղΛࢄΒ͔͞ͳ͍ n ଟ༷ԽΛతͱͨ֬͠తͳղഁյѱԽडཧΛ͓͜ͳΘͳ͍ ͨΊɼॳظղ͔Βͷมߋ༰ΛۛຯɾධՁ͍͢͠ E ˚ߴ͍ੑೳΛಘΑ͏ͱ͢Δͱ࣮ྔ͕ଟ͘ͳΔ n ʮͯ͢ͷۙղͷධՁ͢Δʯͱ͜Ζ͕ܭࢉͷϘτϧωοΫɽ େنΠϯελϯεΛఆ͢Δ߹ɼᶃධՁରۙղͷߜΓࠐΈɼ ᶄࠩධՁʹΑΔۙղධՁߴԽ͕ॏཁͱͳΔʢޙड़ʣ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ࣮ద༻ ʹ͓͍ͯ خ͍͠ੑ࣭ ΞϧΰϦζϜ֓ཁ 8FJHIUFE5BCV4FBSDIʢ̎ʣ -
ΞϧΰϦζϜ֓ཁ 8FJHIUFE5BCV4FBSDIʢ̏ʣ n 5BCV-JTUอ࣋ଐੑ n ܾఆมͷఴࣈΛ5BCV-JTUͰอ࣋͢Δ n ղΛ5BCV-JTUͰอ࣋͢Δ߹ͱൺֱͯ͠ېࢭ͞ΕΔૢ࡞͕૿͑ɼ ଟ༷Խ͕ظͰ͖Δɽ·ͨېࢭૢ࡞͔Ͳ͏͔ͷఆߴʹͰ͖Δ n
୳ࡧۭؒ n *-1ʹରͯ͠ɼ࣮ߦՄೳղͷΈ͔Β୳ࡧۭؒΛߏ͢Δ͜ͱࠔ n ࣮ߦෆՄೳղؚΉɼ֤มͷ্Լݶ੍Ͱنఆ͞ΕΔۭؒશମΛ୳ࡧ n ۙ n ҎԼͷछྨʹՃ͑ɼΠϯελϯεͷߏղੳʹجͮ͘ՃۙΛ࠾༻ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." /P ໊ۙ ର ૢ࡞ 'MJQ ม ͋ΔͻͱͭͷมͷΛ͔Βʹɼ͋Δ͍͔Βʹมߋ͢Δ 4IJGU Ұൠͷม ͋ΔͻͱͭͷมͷΛɼ্Լݶ੍ͷൣғͰ͢Δ +VNQ Ұൠͷม ͋ΔͻͱͭͷมͷΛɼݱࡏͱ্ݶʢԼݶʣͷதؒʹมߋ͢Δ -
ΞϧΰϦζϜ֓ཁ 8FJHIUFE5BCV4FBSDIʢ̐ʣ n ϖφϧςΟؔ๏Λ༻͍Δ͜ͱͰ࣮ߦՄೳղͱ࣮ߦෆՄೳղΛಉҰͷईͰධՁ n ୳ࡧதɼ੍ͷ९कɾҳঢ়گΛࢹͭͭ͠ɼϖφϧςΟΛಈతʹมߋ͠ ࣮ߦՄೳղͱ࣮ߦෆՄೳղͷڥք෦Λॏతʹ୳ࡧʢઓུతৼಈʣ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6."
ILP : minimize 𝒍 $ 𝒙 $ 𝒖 𝒂' (𝒙 = 𝑏' , 𝑖 ∈ 𝐼) , 𝒂' (𝒙 ≤ 𝑏' , 𝑖 ∈ 𝐼$ , 𝑥! ∈ ℤ, 𝑗 ∈ 𝐽 𝒄(𝒙 subject to ILP′ : minimize 𝒍 $ 𝒙 $ 𝒖 𝑥! ∈ ℤ, 𝑗 ∈ 𝐽 𝒄(𝒙 + J '∈+"∪+# 𝑤' - max(𝒂' (𝒙 − 𝑏' , 0) − J '∈+" 𝑤' . min(𝒂' (𝒙 − 𝑏' , 0) subject to ੍݅ͷҧྔΛϖφϧςΟͱͯ͠తؔʹՃࢉʢͦͷΘΓʹ੍Λ؇ʣ ϖφϧςΟʢඇෛʣ n ධՁؔʢۙղબͷͨΊͷධՁܭࢉʣ -
࣍ ͡Ίʹ ιϧόʔ։ൃͷഎܠɾత ΞϧΰϦζϜ֓ཁ ઃܭɾ࣮ͷϙΠϯτ
։ൃϓϩηε ͓ΘΓʹ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." -
ઃܭɾ࣮ͷϙΠϯτ ͍͔ʹͯ͠ࢬݶఆ๏͚ΠϯελϯεΛղ͖͘͢͢Δ͔ʁ n ࢬݶఆ๏ͱώϡʔϦεςΟΫεͰదͨ͠ఆࣜԽҟͳΔ n ࢬݶఆ๏ɿ࿈ଓ؇Λղ͍ͯಘΒΕΔԼք͕ڧ͍ఆࣜԽ͕Α͍ n ώϡʔϦεςΟΫεɿมɾ੍͕গͳ͍ఆࣜԽ͕Α͍ʢҰ෦ྫ֎͋Γʣ B ܭࢉલʹదͳલॲཧʹΑΓΠϯελϯεαΠζΛॖখ͢Δ
C Πϯελϯεͷߏʢ੍݅ͷछྨʣΛղੳ͠ɼͦ͜ͰಘΒΕͨใ Λ׆༻ͯ͠தؒมͷফڈ༗ޮͳۙͷநग़Λ͓͜ͳ͏ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." Πϯελϯεॖখ தؒมͷফڈ ༗ޮͳۙͷநग़ • ҧ͑͠ͳ੍͍Λআڈ • ΛݻఆͰ͖ΔมΛఆԽ ϞσϦϯάͷศٓͷͨΊಋೖ͞Εͯ ͍ΔதؒมΛೖɾফڈ ߏ͔Β༗ޮͳۙΛநग़ ʢྫɿ/ݸͷબࢶ͔ΒͻͱͭબͿʣ 𝑨 𝑨′ 𝑨𝒙 = 𝒃 𝑨′𝒙′ = 𝒃′ minimize !, &, ' 𝑧 subj. to 𝑧 = 𝑥 + 𝑦 minimize !,& 𝑥 + 𝑦 𝑥# + 𝑥$ + 𝑥% = 1 (𝑥# , 𝑥$ , 𝑥% ∈ 0,1 ) 𝑥 = (0, 1, 0) 𝑥 = (1, 0, 0) 𝑥 = (0, 0, 1) ։ൃํᶄɿࢬݶఆ๏ιϧόʔ͚ʹఆࣜԽ͞ΕͨΠϯελϯεΛͦͷ··ղ ͍ͯྑͳੑೳ͕ಘΒΕΔ͜ͱ -
n Πϯελϯεॖখॲཧͷ֓ཁ˞ B దͳ੍݅ʹண͠ɼ੍ؚ͕ࣜΉ֤มͷͱΓ͏Δ্ԼݶΛܭࢉͯ͠ɼ ܾ֘ఆมͷ্Լݶ੍ͷڧԽ͋Δ͍ͷݻఆΛ͓͜ͳ͏ C దͳ੍݅ʹண͠ɼ͍͔ͳΔมͷʢͷʣʹରͯ͠৵͠ಘͳ͍߹ɼ ੍֘݅Λআ͢Δ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6."
ઃܭɾ࣮ͷϙΠϯτ Πϯελϯεॖখ ˞͜ͷ΄͔ɼॏෳ͢Δ੍ͷআڈɼෆ߸ͷ͖͚͕ͩҟͳΔෆ੍ࣜͷ੍ࣜͷϚʔδɼಛఆʢू߹ׂ ɼू߹ඃ෴ɼϥΠπΞτʣઐ༻ͷख๏ͳͲΛซ༻ɽৄࡉʹ͍ͭͯҎԼهࣄʹهࡌ IUUQTTOPXCFSSZGJFMEIBUFOBEJBSZDPNFOUSZ .*1-*##FODINBSL4FU७ܭը Πϯελϯε Πϯελϯεॖখ݁Ռ -
ઃܭɾ࣮ͷϙΠϯτ Πϯελϯεͷߏղੳʢ̍ʣ n Πϯελϯεʹؚ·ΕΔ੍݅ΛɼͦͷߏΛͱʹҎԼͷλΠϓʹྨ˞ n ͍͔ͭ͘ͷ੍݅λΠϓʹରͯ͠ɼಛఆͷมͷফڈۙநग़Λ͓͜ͳ͏ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ˞.*1-*#*OTUBODF4UBUJTUJD(VJEF
IUUQTNJQMJC[JCEFTUBUJTUJDTIUNM ʹهࡌͷྨΛಠࣗʹमਖ਼ɾ֦ு ͨ͠ͷɽෳλΠϓʹ߹க͢Δ੍݅/Pͷए͍ͷʹྨ͢Δɽ ͱ͘ʹॏཁͳ੍݅λΠϓʢߏΛେ͖͘ม͑Δ͔ͨͪͰͷมফڈɾۙఆٛΛ࣮ࢪʣ -
n ΞϧΰϦζϜվળͷछྨ n ࠾༻͍ͯ͠Δߟ͔͑ͨ n ͓ʹܭࢉͷվળΛ௨ͯ͡ɼ൚༻ੑɾੑೳͷϕʔεΞοϓΛਤΔ n ୳ࡧڍಈͷվળޮՌཧ۶͚͕ͮΉ͔ͣ͘͠ɼධՁͨ͠ΠϯελϯεҎ֎Ͱ ͏·͘ػೳ͢Δ͔Ͳ͏͔Θ͔Βͳ͍͏͑ɼύϥϝʔλ૿͑Δ n
ܭࢉͷվળධՁͨ͠ΠϯελϯεҎ֎ʹରͯ͠ޮՌΛݟࠐΈ͍͢ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ։ൃํᶅɿ൚༻ੑͱੑೳΛཱ྆͢Δ͜ͱ /P վળछྨ આ໌ ۩ମྫ ୳ࡧڍಈͷվળ ಉ͡෮ճͰΑΓྑ͍ղʹ౸ୡͰ͖ ΔΑ͏ʹ͢ΔͨΊͷվળ ಛघۙͷఆٛɼղͷઁ ಈɼϦελʔτͳͲ ܭࢉͷվળ ֤෮ͰಘΒΕΔղม͑ͣɼΑΓ ͘෮Ͱ͖ΔΑ͏ʹ͢ΔͨΊͷվળ ۙղධՁͷߴԽͳͲ ઃܭɾ࣮ͷϙΠϯτ ൚༻ੑͱੑೳͷཱ྆ -
ᶃ ධՁରۙղͷݮ n ղΛվળ͠͏ΔۙղͷΈΛධՁରͱ͢Δ˞ ᶄ ղධՁͷޮԽ n ݱࡏղͷతؔɾ੍ؔΛอ࣋͠ɼۙղʹ͓͚Δ֤ؔͷΛࠩධՁ n ੍ؔʹ͍ͭͯɼۙૢ࡞ʹରͯ͠ײΛͭͷͷΈΛධՁ
ᶅ ฒྻԽ n ۙղධՁΛ0QFO.1ͰฒྻԽɽฒྻԽͷద൱࠷దεϨουΠϯελϯε ܭࢉػʹґଘ͢ΔͨΊɼόϯσΟοτΞϧΰϦζϜΛ༻͍ͯΦϯϥΠϯ࠷దԽ˞ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ઃܭɾ࣮ͷϙΠϯτ ߴԽͷجຊࢦ /P ঢ়گ આ໌ ݱࡏղ͕࣮ߦෆՄೳ ͍ͣΕ͔ͷ੍݅ҧΛվળ͢ΔۙղͷΈΛධՁରͱ͢Δ ݱࡏղ͕࣮ߦՄೳ తؔΛվળ͢ΔۙղͷΈΛධՁରͱ͢Δ ˞੍֤݅తؔʹ͓͚ΔมͷΛνΣοΫ͢Δ͜ͱͰߜΓࠐΈՄೳɻ ˞ੑೳʹվળ༨͕͋ΔͨΊվྑݕ౼தʢ࣌ͷ࠷৽όʔδϣϯʢWʣʣ ෮͋ͨΓͷղධՁ࣌ؒʹᶃධՁରۙղºᶄղධՁ࣌ؒ ºᶅฒྻԽޮՌ -
0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ઃܭɾ࣮ͷϙΠϯτ ߴԽͷޮՌ ฏۉղධՁ࣌ؒ ʢײͷͳ੍͍ؔ ͷͯ͢ධՁ ͨ͠߹ʹର͢Δܭ ࢉ࣌ؒͷൺʣ
ฏۉධՁରۙ ʢશۙʹର͢Δൺʣ ܾఆมͷ ੍݅ͷ ߦྻඇྵີ .*1-*##FODINBSL4FU७ܭըΠϯελϯεʹର͢Δ ධՁରۙղͷݮɺղධՁͷޮԽͷ"CMBUJPO4UVEZ݁Ռʢ࣮ߦෆՄೳΠϯελϯεɼFOMJHIU@IBSEΛআ͘ʣ n ධՁରۙղͷݮɼղධՁͷޮԽͱʹεύʔεɾେنͳΠϯε λϯεʹ͓͍ͯޮՌେ -
࣍ ͡Ίʹ ιϧόʔ։ൃͷഎܠɾత ΞϧΰϦζϜ֓ཁ ઃܭɾ࣮ͷϙΠϯτ
։ൃϓϩηε ͓ΘΓʹ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." -
ᶃ ։ൃͷࡉԽ n ։ൃεςοϓΛࡉׂ͔͘͠ɼҙਤ͠ͳ͍ੑೳมԽʹؾ͖ͮ͘͢͢Δ n ͱ͘ʹɼ୳ࡧڍಈͷมߋͱܭࢉͷվળݪଇͱͯ͠ಉ࣌ʹ࣮ࢪ͠ͳ͍ ᶄ ੑೳͷࢹ n ΞϧΰϦζϜվྑɾػೳՃͷλΠϛϯάͰϕϯνϚʔΫηοτΛ༻͍ͨ
ੑೳධՁΛ͓͜ͳ͍ɼͦͷ݁ՌΛσʔλϕʔεʹ֨ೲ͢Δ n ϕϯνϚʔΫηοτ͓ʹ.*1-*##FODINBSL4FUΛར༻ ᶅ ϑΝΠϯνϡʔχϯάېࢭ n ύϥϝʔλͷσϑΥϧτͷϑΝΠϯνϡʔχϯά͠ͳ͍ n ਐԽܭࢉͳͲΛ༻͍ͨύϥϝʔλ࠷దԽʹΑΓɼϕϯνϚʔΫηοτʹର ͢Δݟ্ֻ͚ͷੑೳΛߴΊͯɼະͷΠϯελϯεʹର͢Δੑೳ্ อূ͞Εͳ͍ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ։ൃϓϩηε جຊํ -
0QUJNJ[BUJPO/JHIUr:VKJ,0(6." ։ൃϓϩηε NMGMPXΛར༻ͨ͠ੑೳධՁ݁Ռͷཧ n NMGMPXʢIUUQTNMGMPXPSHʣΛར༻͠ɼੑೳධՁɾ݁Ռͷཧ·ͰશࣗಈԽ n όʔδϣϯؒͰͷੑೳࠩΛ༰қʹՄࢹԽɾൺֱՄೳ l
ఆղతؔ l ఆղ੍ҧྔ l ࣮ߦՄೳղऔಘՄ൱ l ෮ճ l ۙղධՁճ ͳͲ NMGMPXͷϢʔβΠϯλʔϑΣʔε ͓ͳੑೳࢹ߲ -
࣍ ͡Ίʹ ιϧόʔ։ൃͷഎܠɾత ΞϧΰϦζϜ֓ཁ ઃܭɾ࣮ͷϙΠϯτ
։ൃϓϩηε ͓ΘΓʹ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6." -
͓ΘΓʹ n ·ͱΊ n ϝλώϡʔϦεςΟΫεʹجͮ͘൚༻ઢܗܭըιϧόʔΛ։ൃ n ࢬݶఆ๏ιϧόʔΛੑೳ໘Ͱิ͢Δ͜ͱ͕͓ͳૂ͍ n 8FJHIUFE5BCV4FBSDIΛϕʔεͱͯ͠ɼΠϯελϯεαΠζݮɼ ۙղͷߜΓࠐΈɼղධՁͷߴԽͳͲΛ࣮
n ௐ͖͢ύϥϝʔλ͕ͳ͘ɼ·ͨࢬݶఆ๏ιϧόʔ͚ʹఆࣜԽ͞ΕͨΠϯε λϯεΛͦͷ··ղ͍ͯྑͳੑೳ͕ظͰ͖Δ n Ռ n 13*/5&.14ʢ։ൃͨ͠ιϧόʔʣ n IUUQTTOPXCFSSZGJFMEHJUIVCJPQSJOUFNQT n 5BCV4FBSDI#BTFE)FVSJTUJD4PMWFSGPS(FOFSBM*OUFHFS-JOFBS 1SPHSBNNJOH1SPCMFNTʢؔ࿈จʣ n IUUQTJFFFYQMPSFJFFFPSHEPDVNFOU n ࠓޙͷ՝ʢݱࡏͷऔΓΈʣ n ػցֶशͱϝλώϡʔϦεςΟΫεʢຊιϧόʔʣΛ߹ͤͨղ୳ࡧख๏ͷࡧ ʢେྔͷ࣮ߦՄೳղΛͱʹղߏΛֶश͠ผͷ࣮ߦՄೳղΛੜ͢ΔɼͳͲʣ 0QUJNJ[BUJPO/JHIUr:VKJ,0(6."