ΠΠ΅ΡΠΎΠ΄ ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ² Π΄Π»Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ
ΠΠΎΡΠΊΠΎΠ»ΡΠΊΡ Π² Π½ΠΎΠ²ΠΎΠΉ ΡΠ°Π±Π»ΠΈΡΠ΅ ΡΠΈΡΠ»ΠΎ Π·Π°ΠΏΠΎΠ»Π½ΡΠ΅ΠΌΡΡ ΠΊΠ»Π΅ΡΠΎΠΊ Π±ΠΎΠ»ΡΡΠ΅, ΡΠ΅ΠΌ ΡΠΈΡΠ»ΠΎ ΡΡΠΎΠ»Π±ΡΠΎΠ², ΡΠΎ ΠΏΡΠΈ Π·Π°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠΈ ΠΊΠ»Π΅ΡΠΎΠΊ ΡΠ»Π΅Π΄ΡΠ΅Ρ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ ΡΠΏΠ΅ΡΠΈΠ°Π»ΡΠ½ΡΠΌ ΠΏΡΠ°Π²ΠΈΠ»ΠΎΠΌ, ΠΊΠΎΡΠΎΡΠΎΠ΅ ΡΠΎΡΡΠΎΠΈΡ Π² ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ. ΠΡΠ±ΠΈΡΠ°ΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ ΡΡΠΎΠ»Π±Π΅Ρ (ΡΡΡΠΎΠΊΡ), Π² ΠΊΠΎΡΠΎΡΠΎΠΌ ΠΈΠΌΠ΅Π΅ΡΡΡ ΠΎΠ΄Π½Π° ΠΊΠ»Π΅ΡΠΊΠ° Ρ ΠΏΠΎΠΌΠ΅ΡΠ΅Π½Π½ΡΠΌ Π² Π½Π΅ΠΉ ΠΊΡΡΠΆΠΊΠΎΠΌ. ΠΡΡ ΠΊΠ»Π΅ΡΠΊΡ Π·Π°ΠΏΠΎΠ»Π½ΡΡΡ ΠΈ ΠΈΡΠΊΠ»ΡΡΠ°ΡΡ ΠΈΠ· ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π½ΠΈΡ Π΄Π°Π½Π½ΡΠΉ ΡΡΠΎΠ»Π±Π΅Ρ (ΡΡΡΠΎΠΊΡ). ΠΠΎΡΠ»Π΅ ΡΡΠΎΠ³ΠΎ Π±Π΅ΡΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΡΡΡΠΎΠΊΡ (ΡΡΠΎΠ»Π±Π΅Ρ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠ΅ΡΠΎΠ΄ ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ² Π΄Π»Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
Π ΠΠ€ΠΠ ΠΠ’ ΠΏΠΎ Π΄ΠΈΡΡΠΈΠΏΠ»ΠΈΠ½Π΅ ΠΠΠ’ΠΠΠΠ’ΠΠ§ΠΠ‘ΠΠΠ ΠΠ‘ΠΠΠΠ« ΠΠ ΠΠΠ ΠΠΠΠΠ ΠΠΠΠΠΠ― Π½Π° ΡΠ΅ΠΌΡ: «ΠΠ΅ΡΠΎΠ΄ ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ² Π΄Π»Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ»
ΠΠΎΡΠΊΠ²Π°, 2010
1. Π Π΅ΡΠ΅Π½ΠΈΠ΅ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ Π’Π°ΠΊ ΠΊΠ°ΠΊ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½Π°Ρ Π·Π°Π΄Π°ΡΠ° ΡΠ²Π»ΡΠ΅ΡΡΡ Π·Π°Π΄Π°ΡΠ΅ΠΉ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ, ΡΠΎ ΠΎΡΠ½ΠΎΠ²Π½ΡΠ΅ ΡΡΠ°ΠΏΡ Π΅Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π±ΡΠ΄ΡΡ ΡΠ°ΠΊΠΈΠΌΠΈ:
IΡΡΠ°ΠΏ. ΠΠ°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΠ΅ Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π΄ΠΎΠΏΡΡΡΠΈΠΌΠΎΠ³ΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ.
IIΡΡΠ°ΠΏ. ΠΡΠ΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΈΠ· Π½Π΅Π±Π°Π·ΠΈΡΠ½ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ Π²Π²ΠΎΠ΄ΠΈΠΌΠΎΠΉ Π² Π±Π°Π·ΠΈΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ (ΠΌΠ΅ΡΠΎΠ΄ ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ²). ΠΡΠ»ΠΈ Π²ΡΠ΅ Π½Π΅Π±Π°Π·ΠΈΡΠ½ΡΠ΅ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΠ΅ ΡΠ΄ΠΎΠ²Π»Π΅ΡΠ²ΠΎΡΡΡΡ ΡΡΠ»ΠΎΠ²ΠΈΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΡΡΠΈ, ΡΠΎ ΡΠ»Π΅Π΄ΡΠ΅Ρ Π·Π°ΠΊΠΎΠ½ΡΠΈΡΡ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΡ; Π² ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ — ΠΏΠ΅ΡΠ΅ΠΉΡΠΈ ΠΊ III ΡΡΠ°ΠΏΡ.
IIIΡΡΠ°ΠΏ. ΠΡΠ±ΠΎΡ Π²ΡΠ²ΠΎΠ΄ΠΈΠΌΠΎΠΉ ΠΈΠ· Π±Π°Π·ΠΈΡΠ° ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ (ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡ ΡΡΠ»ΠΎΠ²ΠΈΡ Π΄ΠΎΠΏΡΡΡΠΈΠΌΠΎΡΡΠΈ) ΠΈΠ· ΡΠΈΡΠ»Π° ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ Π±Π°Π·ΠΈΡΠ°; Π·Π°ΡΠ΅ΠΌ Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΠ΅ Π½ΠΎΠ²ΠΎΠ³ΠΎ Π±Π°Π·ΠΈΡΠ½ΠΎΠ³ΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΈ Π²ΠΎΠ·Π²ΡΠ°ΡΠ΅Π½ΠΈΠ΅ ΠΊΠΎ II ΡΡΠ°ΠΏΡ.
ΠΠ»Ρ Π»ΡΡΡΠ΅Π³ΠΎ ΠΏΠΎΠ½ΠΈΠΌΠ°Π½ΠΈΡ ΠΌΠ΅ΡΠΎΠ΄Π° ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ², ΡΠ°ΡΡΠΌΠΎΡΡΠΈΠΌ ΠΏΠΎΠ΄ΡΠΎΠ±Π½Π΅Π΅ Π²ΡΠ΅ ΡΡΠ°ΠΏΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ, ΡΡΠΈΡΡΠ²Π°Ρ Π΅Π΅ ΡΠΏΠ΅ΡΠΈΡΠΈΠΊΡ.
I ΡΡΠ°ΠΏ. ΠΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π΄ΠΎΠΏΡΡΡΠΈΠΌΠΎΠ³ΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΠ»Ρ ΡΠ±Π°Π»Π°Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΉ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΡΠΎΠ»ΡΠΊΠΎ m + n — 1 Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΡΡ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠ΅ Π±Π°Π·ΠΈΡΠ½ΠΎΠ΅ Π΄ΠΎΠΏΡΡΡΠΈΠΌΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ ΠΈΠΌΠ΅ΡΡ m+n-1 Π±Π°Π·ΠΈΡΠ½ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ .
ΠΠ°ΡΠ°Π»ΡΠ½ΠΎΠ΅ Π±Π°Π·ΠΈΡΠ½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΏΠΎΠ»ΡΡΠ°ΡΡ Π½Π΅ΠΏΠΎΡΡΠ΅Π΄ΡΡΠ²Π΅Π½Π½ΠΎ ΠΈΠ· ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ ΡΠ°Π±Π»ΠΈΡΡ. ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΡΠΈ ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ.
1. ΠΡΠ°Π²ΠΈΠ»ΠΎ «ΡΠ΅Π²Π΅ΡΠΎ-Π·Π°ΠΏΠ°Π΄Π½ΠΎΠ³ΠΎ ΡΠ³Π»Π°»
ΠΡΠΈ Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΠΈ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π° ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ «ΡΠ΅Π²Π΅ΡΠΎ-Π·Π°ΠΏΠ°Π΄Π½ΠΎΠ³ΠΎ ΡΠ³Π»Π°» Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡ ΠΏΠ΅ΡΠ²ΡΠΉ ΠΈΠ· ΠΎΡΡΠ°Π²ΡΠΈΡ ΡΡ ΠΏΡΠ½ΠΊΡΠΎΠ² ΠΎΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ ΠΈ ΠΏΠ΅ΡΠ²ΡΠΉ ΠΈΠ· ΠΎΡΡΠ°Π²ΡΠΈΡ ΡΡ ΠΏΡΠ½ΠΊΡΠΎΠ² Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ. ΠΠ°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ ΡΠ°Π±Π»ΠΈΡΡ Π½Π°ΡΠΈΠ½Π°Π΅ΡΡΡ Ρ Π»Π΅Π²ΠΎΠ³ΠΎ Π²Π΅ΡΡ Π½Π΅Π³ΠΎ ΡΠ³Π»Π° (ΡΠ΅Π²Π΅ΡΠΎ-Π·Π°ΠΏΠ°Π΄Π½ΠΎΠ³ΠΎ), Π΄Π²ΠΈΠ³Π°ΡΡΡ Π΄Π°Π»Π΅Π΅ ΠΏΠΎ ΡΡΡΠΎΠΊΠ΅ Π²ΠΏΡΠ°Π²ΠΎ ΠΈΠ»ΠΈ ΠΏΠΎ ΡΡΠΎΠ»Π±ΡΡ Π²Π½ΠΈΠ· (ΡΠ²Π΅Π»ΠΈΡΠ΅Π½ΠΈΠ΅ i, ΡΠ²Π΅Π»ΠΈΡΠ΅Π½ΠΈΠ΅ j). ΠΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π₯11 ΠΏΡΠΈΠΏΠΈΡΡΠ²Π°ΡΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅, Π΄ΠΎΠΏΡΡΠΊΠ°Π΅ΠΌΠΎΠ΅ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΡΠΌΠΈ Π½Π° ΡΠΏΡΠΎΡ ΠΈ Π·Π°ΠΏΠ°ΡΡ.
ΠΠΎΡΠ»Π΅ ΡΡΠΎΠ³ΠΎ Π²ΡΡΠ΅ΡΠΊΠΈΠ²Π°ΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΉ ΡΡΠΎΠ»Π±Π΅Ρ ΠΈΠ»ΠΈ ΡΡΡΠΎΠΊΡ, ΡΠΈΠΊΡΠΈΡΡΡ ΡΡΠΈΠΌ, ΡΡΠΎ ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΠ΅ Π²ΡΡΠ΅ΡΠΊΠ½ΡΡΠΎΠ³ΠΎ ΡΡΠΎΠ»Π±ΡΠ° (ΡΡΡΠΎΠΊΠΈ) ΠΏΠΎΠ»Π°Π³Π°ΡΡΡΡ ΡΠ°Π²Π½ΡΠΌΠΈ Π½ΡΠ»Ρ. ΠΡΠ»ΠΈ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΡ Π²ΡΠΏΠΎΠ»Π½ΡΡΡΡΡ ΠΎΠ΄Π½ΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎ, ΡΠΎ ΠΌΠΎΠΆΠ½ΠΎ Π²ΡΡΠ΅ΡΠΊΠ½ΡΡΡ Π»ΠΈΠ±ΠΎ ΡΡΡΠΎΠΊΡ, Π»ΠΈΠ±ΠΎ ΡΡΠΎΠ»Π±Π΅Ρ. ΠΡΠΎΡΠ΅ΡΡ Π·Π°Π²Π΅ΡΡΠ°Π΅ΡΡΡ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° Π±ΡΠ΄Π΅Ρ ΠΏΡΠΈΡΠ²ΠΎΠ΅Π½ΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ Ρ min.
ΠΡΡ ΠΎΠ΄Π½ΡΠΉ ΠΎΠΏΠΎΡΠ½ΡΠΉ ΠΏΠ»Π°Π½, ΠΏΠΎΡΡΡΠΎΠ΅Π½Π½ΡΠΉ ΠΏΠΎ ΠΏΡΠ°Π²ΠΈΠ»Ρ «ΡΠ΅Π²Π΅ΡΠΎ-Π·Π°ΠΏΠ°Π΄Π½ΠΎΠ³ΠΎ ΡΠ³Π»Π°», ΠΎΠ±ΡΡΠ½ΠΎ ΠΎΠΊΠ°Π·ΡΠ²Π°Π΅ΡΡΡ Π²Π΅ΡΡΠΌΠ° Π΄Π°Π»Π΅ΠΊΠΈΠΌ ΠΎΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ, ΡΠ°ΠΊ ΠΊΠ°ΠΊ ΠΏΡΠΈ Π΅Π³ΠΎ ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ Π½Π΅ ΡΡΠΈΡΡΠ²Π°Π΅ΡΡΡ ΡΡΠΎΠΈΠΌΠΎΡΡΡ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ (Π²Π΅Π»ΠΈΡΠΈΠ½Π° Ρij). ΠΠΎΠ»Π΅Π΅ ΡΠΎΠ²Π΅ΡΡΠ΅Π½Π½ΡΠΌ ΠΏΡΠ°Π²ΠΈΠ»ΠΎΠΌ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΡΠ°Π²ΠΈΠ»ΠΎ «ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°» .
2.ΠΡΠ°Π²ΠΈΠ»ΠΎ «ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°»
Π ΠΌΠ΅ΡΠΎΠ΄Π΅ «ΡΠ΅Π²Π΅ΡΠΎ-Π·Π°ΠΏΠ°Π΄Π½ΠΎΠ³ΠΎ ΡΠ³Π»Π°» Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ ΠΏΠΎΡΡΠ΅Π±Π½ΠΎΡΡΡ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ ΠΈΠ· ΠΎΡΡΠ°Π²ΡΠΈΡ ΡΡ ΠΏΡΠ½ΠΊΡΠΎΠ² Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΡΠ΄ΠΎΠ²Π»Π΅ΡΠ²ΠΎΡΡΠ΅ΡΡΡ Π·Π° ΡΡΠ΅Ρ Π·Π°ΠΏΠ°ΡΠΎΠ² ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ ΠΈΠ· ΠΎΡΡΠ°Π²ΡΠΈΡ ΡΡ ΠΏΡΠ½ΠΊΡΠΎΠ² ΠΎΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ. ΠΡΠ΅Π²ΠΈΠ΄Π½ΠΎ, ΡΡΠΎ Π²ΡΠ±ΠΎΡ ΠΏΡΠ½ΠΊΡΠΎΠ² Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΈ ΠΎΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ ΡΠ΅Π»Π΅ΡΠΎΠΎΠ±ΡΠ°Π·Π½ΠΎ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΡ, ΠΎΡΠΈΠ΅Π½ΡΠΈΡΡΡΡΡ Π½Π° ΡΡΠΎΠΈΠΌΠΎΡΡΡ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ, Π° ΠΈΠΌΠ΅Π½Π½ΠΎ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ ΡΠ»Π΅Π΄ΡΠ΅Ρ Π²ΡΠ±ΠΈΡΠ°ΡΡ ΠΊΠ°ΠΊΡΡ-Π»ΠΈΠ±ΠΎ ΠΊΠ»Π΅ΡΠΊΡ, ΠΎΡΠ²Π΅ΡΠ°ΡΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌΡ ΡΠ°ΡΠΈΡΡ (Π΅ΡΠ»ΠΈ ΡΠ°ΠΊΠΈΡ ΠΊΠ»Π΅ΡΠΎΠΊ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ, ΡΠΎ ΡΠ»Π΅Π΄ΡΠ΅Ρ Π²ΡΠ±ΠΈΡΠ°ΡΡ Π»ΡΠ±ΡΡ ΠΈΠ· Π½ΠΈΡ ), ΠΈ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡ ΠΏΡΠ½ΠΊΡΡ Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΈ ΠΎΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠ΅ Π²ΡΠ±ΡΠ°Π½Π½ΠΎΠΉ ΠΊΠ»Π΅ΡΠΊΠ΅.
ΠΡΠ°Π²ΠΈΠ»ΠΎ «ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°» Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎΠ±Ρ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΈΡΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΠ΅ ΠΎΠ±ΡΠ΅ΠΌΡ ΠΈΠ· ΠΏΡΠ½ΠΊΡΠΎΠ² ΠΎΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ ΠΌΠ°ΡΡΡΡΡΠ°ΠΌΠΈ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ. ΠΠ°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΡΠ°Π±Π»ΠΈΡΡ Π½Π°ΡΠΈΠ½Π°Π΅ΠΌ Ρ ΠΊΠ»Π΅ΡΠΊΠΈ, ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ°Ρ ΡΡΠΎΠΈΠΌΠΎΡΡΡ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΠΈ (ΡΠ»Π΅ΠΌΠ΅Π½Ρ cij) ΠΈΠ· Π²ΡΠ΅ΠΉ ΡΠ°Π±Π»ΠΈΡΡ. ΠΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΡΠΎΠΉ ΠΊΠ»Π΅ΡΠΊΠΈ Ρ ij ΠΏΡΠΈΡΠ²Π°ΠΈΠ²Π°Π΅ΡΡΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Ρ ΡΡΠ΅ΡΠΎΠΌ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΠΉ. ΠΠ°ΡΠ΅ΠΌ ΠΎΡΡΠ°ΡΠΎΠΊ ΠΏΠΎ ΡΡΠΎΠ»Π±ΡΡ ΠΈΠ»ΠΈ ΡΡΡΠΎΠΊΠ΅ ΠΏΠΎΠΌΠ΅ΡΠ°Π΅ΡΡΡ Π² ΠΊΠ»Π΅ΡΠΊΡ ΡΠΎΠ³ΠΎ ΠΆΠ΅ ΡΡΠΎΠ»Π±ΡΠ° ΠΈΠ»ΠΈ ΡΡΡΠΎΠΊΠΈ, ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ ΡΠ»Π΅Π΄ΡΡΡΠ΅Π΅ ΠΏΠΎ Π²Π΅Π»ΠΈΡΠΈΠ½Π΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Ρij ΠΈ Ρ. Π΄. ΠΠ½ΡΠΌΠΈ ΡΠ»ΠΎΠ²Π°ΠΌΠΈ, ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ Π·Π°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΠΊΠ»Π΅ΡΠΎΠΊ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ ΠΏΠΎ Π²Π΅Π»ΠΈΡΠΈΠ½Π΅ Ρij, Π° ΠΏΠΎΠΌΠ΅ΡΠ°Π΅ΠΌΠ°Ρ Π² ΡΡΠΈΡ ΠΊΠ»Π΅ΡΠΊΠ°Ρ Π²Π΅Π»ΠΈΡΠΈΠ½Π° Ρ ij ΡΠ°ΠΊΠ°Ρ ΠΆΠ΅, ΠΊΠ°ΠΊ ΠΈ Π² ΠΏΡΠ°Π²ΠΈΠ»Π΅ «ΡΠ΅Π²Π΅ΡΠΎ-Π·Π°ΠΏΠ°Π΄Π½ΠΎΠ³ΠΎ ΡΠ³Π»Π°» .
3.ΠΠ΅ΡΠΎΠ΄ Π°ΠΏΠΏΡΠΎΠΊΡΠΈΠΌΠ°ΡΠΈΠΈ Π€ΠΎΠ³Π΅Π»Ρ.
ΠΡΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠΈ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π° ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π°ΠΏΠΏΡΠΎΠΊΡΠΈΠΌΠ°ΡΠΈΠΈ Π€ΠΎΠ³Π΅Π»Ρ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ ΠΏΠΎ Π²ΡΠ΅ΠΌ ΡΡΠΎΠ»Π±ΡΠ°ΠΌ ΠΈ ΠΏΠΎ Π²ΡΠ΅ΠΌ ΡΡΡΠΎΠΊΠ°ΠΌ Π½Π°Ρ ΠΎΠ΄ΡΡ ΡΠ°Π·Π½ΠΎΡΡΡ ΠΌΠ΅ΠΆΠ΄Ρ Π΄Π²ΡΠΌΡ Π·Π°ΠΏΠΈΡΠ°Π½Π½ΡΠΌΠΈ Π² Π½ΠΈΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌΠΈ ΡΠ°ΡΠΈΡΠ°ΠΌΠΈ. ΠΡΠΈ ΡΠ°Π·Π½ΠΎΡΡΠΈ Π·Π°ΠΏΠΈΡΡΠ²Π°ΡΡ Π² ΡΠΏΠ΅ΡΠΈΠ°Π»ΡΠ½ΠΎ ΠΎΡΠ²Π΅Π΄Π΅Π½Π½ΡΡ Π΄Π»Ρ ΡΡΠΎΠ³ΠΎ ΡΡΡΠΎΠΊΠ΅ ΠΈ ΡΡΠΎΠ»Π±ΡΠ΅ ΡΡΠ»ΠΎΠ²ΠΈΠΉ Π·Π°Π΄Π°ΡΠΈ. Π‘ΡΠ΅Π΄ΠΈ ΡΠΊΠ°Π·Π°Π½Π½ΡΡ ΡΠ°Π·Π½ΠΎΡΡΠ΅ΠΉ Π²ΡΠ±ΠΈΡΠ°ΡΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΡ. Π ΡΡΡΠΎΠΊΠ΅ (ΠΈΠ»ΠΈ ΡΡΠΎΠ»Π±ΡΠ΅), ΠΊΠΎΡΠΎΡΠΎΠΉ Π΄Π°Π½Π½Π°Ρ ΡΠ°Π·Π½ΠΎΡΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ, ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΡΠ°ΡΠΈΡ. ΠΠ»Π΅ΡΠΊΡ, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ ΠΎΠ½ Π·Π°ΠΏΠΈΡΠ°Π½, Π·Π°ΠΏΠΎΠ»Π½ΡΡΡ Π½Π° Π΄Π°Π½Π½ΠΎΠΉ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ.
ΠΡΠΎΡ ΠΌΠ΅ΡΠΎΠ΄ Π΄Π°Π΅Ρ Π½Π°ΠΈΠ»ΡΡΡΠ΅Π΅ Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠ΅ ΠΏΡΠΈΠ±Π»ΠΈΠΆΠ΅Π½ΠΈΠ΅, ΡΠ°ΡΡΠΎ ΠΎΠΊΠ°Π·ΡΠ²Π°ΡΡΠ΅Π΅ΡΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ ΠΏΠ»Π°Π½ΠΎΠΌ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π°ΠΏΠΏΡΠΎΠΊΡΠΈΠΌΠ°ΡΠΈΠΈ Π€ΠΎΠ³Π΅Π»Ρ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΉ:
I ΡΡΠ°ΠΏ. ΠΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π΄ΠΎΠΏΡΡΡΠΈΠΌΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π°.
ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΡΡΡΠΎΠΊΠΈ ΡΠ°Π±Π»ΠΈΡΡ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠΈΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ cij ΠΏΠΎ Π²ΠΎΠ·ΡΠ°ΡΡΠ°Π½ΠΈΡ. ΠΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ Π²Π΅Π»ΠΈΡΠΈΠ½Ρ «ΡΡΡΠ°ΡΠ°» ΡΡΡΠΎΠΊΠΈ ΠΊΠ°ΠΊ ΡΠ°Π·Π½ΠΎΡΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ Π²ΡΠΎΡΠΎΠ³ΠΎ ΠΈ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Π² ΡΠ°Π½ΠΆΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΌ ΡΡΠ΄Ρ.
ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΡΠΎΠ»Π±ΡΠ° ΡΠ°Π±Π»ΠΈΡΡ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠΈΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ cij ΠΏΠΎ Π²ΠΎΠ·ΡΠ°ΡΡΠ°Π½ΠΈΡ. ΠΠ°Π»Π΅Π΅ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ Π²Π΅Π»ΠΈΡΠΈΠ½Ρ ΡΡΡΠ°ΡΠ° ΡΡΠΎΠ»Π±ΡΠ°.
ΠΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ ΡΡΡΠΎΠΊΡ (ΠΈΠ»ΠΈ ΡΡΠΎΠ»Π±Π΅Ρ), ΠΈΠΌΠ΅ΡΡΡΡ (ΠΈΠΌΠ΅ΡΡΠΈΠΉ) Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΠΉ ΡΡΡΠ°Ρ ΠΏΠΎ Π²ΡΠ΅ΠΌ ΡΡΡΠ°ΡΠ°ΠΌ ΡΡΡΠΎΠΊ ΠΈ ΡΡΠΎΠ»Π±ΡΠΎΠ², Π° Π² Π½Π΅ΠΉ (Π² Π½Π΅ΠΌ) — ΡΠ»Π΅ΠΌΠ΅Π½Ρ Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ Π²Π΅Π»ΠΈΡΠΈΠ½ΠΎΠΉ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ Ρij. ΠΠ°ΡΠΈΠΊΡΠΈΡΠΎΠ²Π°ΡΡ ΠΈΠ½Π΄Π΅ΠΊΡΡ (i, j) ΡΡΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°.
ΠΡΠΈΡΠ²ΠΎΠΈΡΡ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠ΅Π΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΈΠ· Π΄ΠΎΠΏΡΡΡΠΈΠΌΡΡ (Ρ ΡΡΠ΅ΡΠΎΠΌ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΠΉ) ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ Ρ ij, ΠΈΠ½Π΄Π΅ΠΊΡΡ ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡ ΡΠ°Π³Ρ 3.
Π‘ΠΊΠΎΡΡΠ΅ΠΊΡΠΈΡΠΎΠ²Π°ΡΡ Π²Π΅Π»ΠΈΡΠΈΠ½Ρ Π°i ΠΈ bj ΠΈ Π²ΡΡΠ΅ΡΠΊΠ½ΡΡΡ ΡΡΡΠΎΠΊΡ i, Π΅ΡΠ»ΠΈ Π°i = 0, ΠΈΠ»ΠΈ ΡΡΠΎΠ»Π±Π΅Ρ j, Π΅ΡΠ»ΠΈ bj = 0.
ΠΡΠΎΠ²Π΅ΡΠΈΡΡ, Π²ΡΠ΅ Π»ΠΈ Π²Π΅Π»ΠΈΡΠΈΠ½Ρ Π°i ΠΈ bj. ΡΠ°Π²Π½Ρ Π½ΡΠ»Ρ, Π΅ΡΠ»ΠΈ Π΄Π°, ΡΠΎ ΠΎΠΊΠΎΠ½ΡΠΈΡΡ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΡ; Π² ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ Π²Π·ΡΡΡ Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΉ ΠΎΡΡΠ°Π²ΡΡΡΡΡ ΡΠ°ΡΡΡ ΡΠ°Π±Π»ΠΈΡΡ ΠΈ ΠΏΠ΅ΡΠ΅ΠΉΡΠΈ ΠΊ ΡΠ°Π³Ρ 3.
ΠΠ°ΠΊ ΠΏΡΠ°Π²ΠΈΠ»ΠΎ, ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΠΌΠ΅ΡΠΎΠ΄Π° Π°ΠΏΠΏΡΠΎΠΊΡΠΈΠΌΠ°ΡΠΈΠΈ Π€ΠΎΠ³Π΅Π»Ρ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΠΏΠΎΠ»ΡΡΠΈΡΡ Π»ΠΈΠ±ΠΎ ΠΎΠΏΠΎΡΠ½ΡΠΉ ΠΏΠ»Π°Π½, Π±Π»ΠΈΠ·ΠΊΠΈΠΉ ΠΊ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌΡ, Π»ΠΈΠ±ΠΎ ΡΠ°ΠΌ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΏΠ»Π°Π½.
II ΡΡΠ°ΠΏ. ΠΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Π²Π²ΠΎΠ΄ΠΈΠΌΠΎΠΉ Π² Π±Π°Π·ΠΈΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ («ΠΌΠ΅ΡΠΎΠ΄ ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ²»).
ΠΡΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ «ΠΌΠ΅ΡΠΎΠ΄ ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ²» ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½ΡΠ΅Π½ ΠΏΡΠΈΠ½ΡΠΈΠΏΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°ΡΠΈ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ ΡΡΠ»ΠΎΠ²ΠΈΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΡΡΠΈ Π² ΡΠΈΠΌΠΏΠ»Π΅ΠΊΡ-ΠΌΠ΅ΡΠΎΠ΄Π΅. Π‘Π½Π°ΡΠ°Π»Π° Π½Π°Ρ ΠΎΠ΄ΡΡ ΠΎΠΏΠΎΡΠ½ΡΠΉ ΠΏΠ»Π°Π½ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ, Π° Π·Π°ΡΠ΅ΠΌ Π΅Π³ΠΎ ΡΠ»ΡΡΡΠ°ΡΡ Π΄ΠΎ ΠΏΠΎΠ»ΡΡΠ΅Π½ΠΈΡ «ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π°». Π‘ΠΎΠ΄Π΅ΡΠΆΠ°Π½ΠΈΠ΅ «ΠΌΠ΅ΡΠΎΠ΄Π° ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ²» Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ:
1. ΠΠ°ΠΆΠ΄ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅ i ΠΈ ΡΡΠΎΠ»Π±ΡΡ j ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ ΡΠ°Π±Π»ΠΈΡΡ ΡΡΠ°Π²ΠΈΡΡΡ Π² ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠ΅ ΡΠΈΡΠ»Π° ui ΠΈ vj, Π½Π°Π·ΡΠ²Π°Π΅ΠΌΡΠ΅ ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»Π°ΠΌΠΈ. ΠΠ½ΠΈ Π΄ΠΎΠ»ΠΆΠ½Ρ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π±Π°Π·ΠΈΡΠ½ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ Ρ ij ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΠ΄ΠΎΠ²Π»Π΅ΡΠ²ΠΎΡΡΡΡ ΡΡΠ»ΠΎΠ²ΠΈΡ ui + vj = Ρij. ΠΡΠΈ ΡΡΠ»ΠΎΠ²ΠΈΡ ΠΏΡΠΈΠ²ΠΎΠ΄ΡΡ ΠΊ ΡΠΈΡΡΠ΅ΠΌΠ΅, ΡΠΎΡΡΠΎΡΡΠ΅ΠΉ ΠΈΠ· m + n — 1 ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ (ΡΠ°ΠΊ ΠΊΠ°ΠΊ ΠΈΠΌΠ΅Π΅ΡΡΡ Π²ΡΠ΅Π³ΠΎ m + n — 1 Π±Π°Π·ΠΈΡ-ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ), Π² ΠΊΠΎΡΠΎΡΡΡ ΡΠΈΠ³ΡΡΠΈΡΡΡΡ m + n Π½Π΅ΠΈΠ·Π²Π΅ΡΡΠ½ΡΡ . ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ² ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡ ΠΈΠ· ΡΡΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ, ΠΏΡΠΈΠ΄Π°Π²Π°Ρ ΠΎΠ΄Π½ΠΎΠΌΡ ΠΈΠ· Π½ΠΈΡ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ»ΡΠ½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ui = 0).
2. ΠΠΏΡΠ΅Π΄Π΅Π»ΡΡΡΡΡ ΠΎΡΠ΅Π½ΠΊΠΈ cij Π΄Π»Ρ Π½Π΅Π±Π°Π·ΠΈΡΠ½ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ Π² ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠΈ Ρ ΡΠΎΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠ΅ΠΌ:
Ρij = ui + vj — Ρij
3. ΠΡΠ»ΠΈ Π²ΡΠ΅ ΠΎΡΠ΅Π½ΠΊΠΈ Ρij ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½Ρ, ΡΠΎ Π½Π°ΠΉΠ΄Π΅Π½Π½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎ, Π² ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ Π½ΠΎΠ²ΡΡ Π²Π²ΠΎΠ΄ΠΈΠΌΡΡ Π² Π±Π°Π·ΠΈΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ.
4. ΠΠ²ΠΎΠ΄ΠΈΠΌΠΎΠΉ Π² Π±Π°Π·ΠΈΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠ²Π»ΡΠ΅ΡΡΡ Π½Π΅Π±Π°Π·ΠΈΡΠ½Π°Ρ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ, ΠΈΠΌΠ΅ΡΡΠ°Ρ ΡΠ°ΠΌΡΡ Π±ΠΎΠ»ΡΡΡΡ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΡΡ ΠΎΡΠ΅Π½ΠΊΡ Ρij.
ΠΠ°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΡΠΌ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ Π²Π²ΠΎΠ΄ΠΈΠΌΠΎΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΌΠ΅ΡΠΎΠ΄ Π΄ΠΈΡΡΠ΅ΡΠ΅Π½ΡΠΈΠ°Π»ΡΠ½ΡΡ ΡΠ΅Π½Ρ. ΠΡΠ»ΠΈ ΠΏΡΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠΈ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π° ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ² ΡΠ½Π°ΡΠ°Π»Π° Π½Π°Ρ ΠΎΠ΄ΠΈΠ»ΡΡ ΠΊΠ°ΠΊΠΎΠΉ-Π½ΠΈΠ±ΡΠ΄Ρ Π΅Π΅ ΠΎΠΏΠΎΡΠ½ΡΠΉ ΠΏΠ»Π°Π½, Π° Π·Π°ΡΠ΅ΠΌ ΠΎΠ½ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ ΡΠ»ΡΡΡΠ°Π»ΡΡ, ΡΠΎ ΠΏΡΠΈ Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π΄ΠΈΡΡΠ΅ΡΠ΅Π½ΡΠΈΠ°Π»ΡΠ½ΡΡ ΡΠ΅Π½Ρ ΡΠ½Π°ΡΠ°Π»Π° Π½Π°ΠΈΠ»ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»ΡΡΡ ΠΌΠ΅ΠΆΠ΄Ρ ΠΏΡΠ½ΠΊΡΠ°ΠΌΠΈ Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΡΠ°ΡΡΡ Π³ΡΡΠ·Π° (ΡΠ°ΠΊ Π½Π°Π·ΡΠ²Π°Π΅ΠΌΠΎΠ΅ ΡΡΠ»ΠΎΠ²Π½ΠΎ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅) ΠΈ Π½Π° ΠΏΠΎΡΠ»Π΅Π΄ΡΡΡΠΈΡ ΠΈΡΠ΅ΡΠ°ΡΠΈΡΡ ΠΏΠΎΡΡΠ΅ΠΏΠ΅Π½Π½ΠΎ ΡΠΌΠ΅Π½ΡΡΠ°ΡΡ ΠΎΠ±ΡΡΡ Π²Π΅Π»ΠΈΡΠΈΠ½Ρ Π½Π΅ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΡ ΠΏΠΎΡΡΠ°Π²ΠΎΠΊ.
ΠΠ΅ΡΠ²ΠΎΠ½Π°ΡΠ°Π»ΡΠ½ΡΠΉ Π²Π°ΡΠΈΠ°Π½Ρ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ Π³ΡΡΠ·Π° ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ. Π ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΠΈΠ· ΡΡΠΎΠ»Π±ΡΠΎΠ² ΡΠ°Π±Π»ΠΈΡΡ Π΄Π°Π½Π½ΡΡ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ Π½Π°Ρ ΠΎΠ΄ΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΡΠ°ΡΠΈΡ. ΠΠ°ΠΉΠ΄Π΅Π½Π½ΡΠ΅ ΡΠΈΡΠ»Π° Π·Π°ΠΊΠ»ΡΡΠ°ΡΡ Π² ΠΊΡΡΠΆΠΊΠΈ, Π° ΠΊΠ»Π΅ΡΠΊΠΈ, Π² ΠΊΠΎΡΠΎΡΡΡ ΡΡΠΎΡΡ ΡΠΊΠ°Π·Π°Π½Π½ΡΠ΅ ΡΠΈΡΠ»Π°, Π·Π°ΠΏΠΎΠ»Π½ΡΡΡ. Π Π½ΠΈΡ Π·Π°ΠΏΠΈΡΡΠ²Π°ΡΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΠ΅ ΡΠΈΡΠ»Π°. Π ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ΅ ΠΏΠΎΠ»ΡΡΠ°ΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ΅ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΏΠΎΡΡΠ°Π²ΠΎΠΊ Π³ΡΡΠ·Π° Π² ΠΏΡΠ½ΠΊΡΡ Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ. ΠΡΠΎ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Π² ΠΎΠ±ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ Π½Π΅ ΡΠ΄ΠΎΠ²Π»Π΅ΡΠ²ΠΎΡΡΠ΅Ρ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΡΠΌ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΉ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ. ΠΠΎΡΡΠΎΠΌΡ Π² ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΡΡΡΠΈΡ ΡΠ°Π³ΠΎΠ² ΡΠ»Π΅Π΄ΡΠ΅Ρ ΠΏΠΎΡΡΠ΅ΠΏΠ΅Π½Π½ΠΎ ΡΠΎΠΊΡΠ°ΡΠ°ΡΡ Π½Π΅ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠ΅ ΠΏΠΎΡΡΠ°Π²ΠΊΠΈ Π³ΡΡΠ·Π° ΡΠ°ΠΊ, ΡΡΠΎΠ±Ρ ΠΏΡΠΈ ΡΡΠΎΠΌ ΠΎΠ±ΡΠ°Ρ ΡΡΠΎΠΈΠΌΠΎΡΡΡ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ ΠΎΡΡΠ°Π²Π°Π»Π°ΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ. ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ ΡΠ½Π°ΡΠ°Π»Π° ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡ ΠΈΠ·Π±ΡΡΠΎΡΠ½ΡΠ΅ ΠΈ Π½Π΅Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΡΠ΅ ΡΡΡΠΎΠΊΠΈ.
Π‘ΡΡΠΎΠΊΠΈ, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠ΅ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠ°ΠΌ, Π·Π°ΠΏΠ°ΡΡ ΠΊΠΎΡΠΎΡΡΡ ΠΏΠΎΠ»Π½ΠΎΡΡΡΡ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Ρ, Π° ΠΏΠΎΡΡΠ΅Π±Π½ΠΎΡΡΠΈ ΠΏΡΠ½ΠΊΡΠΎΠ² Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ, ΡΠ²ΡΠ·Π°Π½Π½ΡΡ Ρ Π΄Π°Π½Π½ΡΠΌΠΈ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»ΡΠΌΠΈ Π·Π°ΠΏΠ»Π°Π½ΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌΠΈ ΠΏΠΎΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ, Π½Π΅ ΡΠ΄ΠΎΠ²Π»Π΅ΡΠ²ΠΎΡΠ΅Π½Ρ, ΡΡΠΈΡΠ°ΡΡΡΡ Π½Π΅Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΡΠΌΠΈ. ΠΡΠΈ ΡΡΡΠΎΠΊΠΈ ΠΈΠ½ΠΎΠ³Π΄Π° Π½Π°Π·ΡΠ²Π°ΡΡ ΡΠ°ΠΊΠΆΠ΅ ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΠΌΠΈ. Π‘ΡΡΠΎΠΊΠΈ, Π·Π°ΠΏΠ°ΡΡ ΠΊΠΎΡΠΎΡΡΡ ΠΈΡΡΠ΅ΡΠΏΠ°Π½Ρ Π½Π΅ ΠΏΠΎΠ»Π½ΠΎΡΡΡΡ, ΡΡΠΈΡΠ°ΡΡΡΡ ΠΈΠ·Π±ΡΡΠΎΡΠ½ΡΠΌΠΈ. ΠΠ½ΠΎΠ³Π΄Π° ΠΈΡ Π½Π°Π·ΡΠ²Π°ΡΡ ΡΠ°ΠΊΠΆΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΡΠΌΠΈ.
ΠΠΎΡΠ»Π΅ ΡΠΎΠ³ΠΎ ΠΊΠ°ΠΊ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Ρ ΠΈΠ·Π±ΡΡΠΎΡΠ½ΡΠ΅ ΠΈ Π½Π΅Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΡΠ΅ ΡΡΡΠΎΠΊΠΈ, Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΈΠ· ΡΡΠΎΠ»Π±ΡΠΎΠ² Π½Π°Ρ ΠΎΠ΄ΡΡ ΡΠ°Π·Π½ΠΎΡΡΠΈ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠΈΡΠ»ΠΎΠΌ Π² ΠΊΡΡΠΆΠΊΠ΅ ΠΈ Π±Π»ΠΈΠΆΠ°ΠΉΡΠΈΠΌ ΠΊ Π½Π΅ΠΌΡ ΡΠ°ΡΠΈΡΠΎΠΌ, Π·Π°ΠΏΠΈΡΠ°Π½Π½ΡΠΌ Π² ΠΈΠ·Π±ΡΡΠΎΡΠ½ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅. ΠΡΠ»ΠΈ ΡΠΈΡΠ»ΠΎ Π² ΠΊΡΡΠΆΠΊΠ΅ Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ Π² ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅, ΡΠΎ ΡΠ°Π·Π½ΠΎΡΡΡ Π½Π΅ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡ. Π‘ΡΠ΅Π΄ΠΈ ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΡ ΡΠΈΡΠ΅Π» Π½Π°Ρ ΠΎΠ΄ΡΡ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅Π΅. ΠΡΠΎ ΡΠΈΡΠ»ΠΎ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΠΎΠΉ ΡΠ΅Π½ΡΠΎΠΉ. ΠΠΎΡΠ»Π΅ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΠΎΠΉ ΡΠ΅Π½ΡΡ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄ΡΡ ΠΊ Π½ΠΎΠ²ΠΎΠΉ ΡΠ°Π±Π»ΠΈΡΠ΅. ΠΡΠ° ΡΠ°Π±Π»ΠΈΡΠ° ΠΏΠΎΠ»ΡΡΠ°Π΅ΡΡΡ ΠΈΠ· ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅ΠΉ ΡΠ°Π±Π»ΠΈΡΡ ΠΏΡΠΈΠ±Π°Π²Π»Π΅Π½ΠΈΠ΅ΠΌ ΠΊ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΌ ΡΠ°ΡΠΈΡΠ°ΠΌ, ΡΡΠΎΡΡΠΈΠΌ Π² ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΡ ΡΡΡΠΎΠΊΠ°Ρ , ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΠΎΠΉ ΡΠ΅Π½ΡΡ. ΠΡΡΠ°Π»ΡΠ½ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΎΡΡΠ°ΡΡΡΡ ΠΏΡΠ΅ΠΆΠ½ΠΈΠΌΠΈ. ΠΡΠΈ ΡΡΠΎΠΌ Π²ΡΠ΅ ΠΊΠ»Π΅ΡΠΊΠΈ Π½ΠΎΠ²ΠΎΠΉ ΡΠ°Π±Π»ΠΈΡΡ ΡΡΠΈΡΠ°ΡΡ ΡΠ²ΠΎΠ±ΠΎΠ΄Π½ΡΠΌΠΈ. ΠΠΎΡΠ»Π΅ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ Π½ΠΎΠ²ΠΎΠΉ ΡΠ°Π±Π»ΠΈΡΡ Π½Π°ΡΠΈΠ½Π°ΡΡ j Π·Π°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Π΅Π΅ ΠΊΠ»Π΅ΡΠΎΠΊ. Π’Π΅ΠΏΠ΅ΡΡ ΡΠΆΠ΅ ΡΠΈΡΠ»ΠΎ Π·Π°ΠΏΠΎΠ»Π½ΡΠ΅ΠΌΡΡ ΠΊΠ»Π΅ΡΠΎΠΊ Π½Π° ΠΎΠ΄Π½Ρ Π±ΠΎΠ»ΡΡΠ΅, ΡΠ΅ΠΌ Π½Π° ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅ΠΌ ΡΡΠ°ΠΏΠ΅. ΠΡΠ° Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½Π°Ρ ΠΊΠ»Π΅ΡΠΊΠ° Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ Π² ΡΡΠΎΠ»Π±ΡΠ΅, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ Π±ΡΠ»Π° Π·Π°ΠΏΠΈΡΠ°Π½Π° ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½Π°Ρ ΡΠ΅Π½ΡΠ°. ΠΡΠ΅ ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ ΠΊΠ»Π΅ΡΠΊΠΈ Π½Π°Ρ ΠΎΠ΄ΡΡΡΡ ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΉ Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΠΈΠ· ΡΡΠΎΠ»Π±ΡΠΎΠ² ΠΈ Π² Π½ΠΈΡ Π·Π°ΠΏΠΈΡΠ°Π½Ρ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΠ΅ Π΄Π»Ρ Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΡΡΠΎΠ»Π±ΡΠ° ΡΠΈΡΠ»Π°, Π·Π°ΠΊΠ»ΡΡΠ΅Π½Π½ΡΠ΅ Π² ΠΊΡΡΠΆΠΊΠΈ. ΠΠ°ΠΊΠ»ΡΡΠ΅Π½Ρ Π² ΠΊΡΡΠΆΠΊΠΈ ΠΈ Π΄Π²Π° ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΡΡ ΡΠΈΡΠ»Π°, ΡΡΠΎΡΡΠΈΡ Π² ΡΡΠΎΠ»Π±ΡΠ΅, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ Π² ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅ΠΉ ΡΠ°Π±Π»ΠΈΡΠ΅, Π±ΡΠ»Π° Π·Π°ΠΏΠΈΡΠ°Π½Π° ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½Π°Ρ ΡΠ΅Π½ΡΠ°.
ΠΠΎΡΠΊΠΎΠ»ΡΠΊΡ Π² Π½ΠΎΠ²ΠΎΠΉ ΡΠ°Π±Π»ΠΈΡΠ΅ ΡΠΈΡΠ»ΠΎ Π·Π°ΠΏΠΎΠ»Π½ΡΠ΅ΠΌΡΡ ΠΊΠ»Π΅ΡΠΎΠΊ Π±ΠΎΠ»ΡΡΠ΅, ΡΠ΅ΠΌ ΡΠΈΡΠ»ΠΎ ΡΡΠΎΠ»Π±ΡΠΎΠ², ΡΠΎ ΠΏΡΠΈ Π·Π°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠΈ ΠΊΠ»Π΅ΡΠΎΠΊ ΡΠ»Π΅Π΄ΡΠ΅Ρ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ ΡΠΏΠ΅ΡΠΈΠ°Π»ΡΠ½ΡΠΌ ΠΏΡΠ°Π²ΠΈΠ»ΠΎΠΌ, ΠΊΠΎΡΠΎΡΠΎΠ΅ ΡΠΎΡΡΠΎΠΈΡ Π² ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ. ΠΡΠ±ΠΈΡΠ°ΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ ΡΡΠΎΠ»Π±Π΅Ρ (ΡΡΡΠΎΠΊΡ), Π² ΠΊΠΎΡΠΎΡΠΎΠΌ ΠΈΠΌΠ΅Π΅ΡΡΡ ΠΎΠ΄Π½Π° ΠΊΠ»Π΅ΡΠΊΠ° Ρ ΠΏΠΎΠΌΠ΅ΡΠ΅Π½Π½ΡΠΌ Π² Π½Π΅ΠΉ ΠΊΡΡΠΆΠΊΠΎΠΌ. ΠΡΡ ΠΊΠ»Π΅ΡΠΊΡ Π·Π°ΠΏΠΎΠ»Π½ΡΡΡ ΠΈ ΠΈΡΠΊΠ»ΡΡΠ°ΡΡ ΠΈΠ· ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π½ΠΈΡ Π΄Π°Π½Π½ΡΠΉ ΡΡΠΎΠ»Π±Π΅Ρ (ΡΡΡΠΎΠΊΡ). ΠΠΎΡΠ»Π΅ ΡΡΠΎΠ³ΠΎ Π±Π΅ΡΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΡΡΡΠΎΠΊΡ (ΡΡΠΎΠ»Π±Π΅Ρ), Π² ΠΊΠΎΡΠΎΡΠΎΠΉ ΠΈΠΌΠ΅Π΅ΡΡΡ ΠΎΠ΄Π½Π° ΠΊΠ»Π΅ΡΠΊΠ° Ρ ΠΏΠΎΠΌΠ΅ΡΠ΅Π½Π½ΡΠΌ Π² Π½Π΅ΠΉ ΠΊΡΡΠΆΠΊΠΎΠΌ. ΠΡΡ ΠΊΠ»Π΅ΡΠΊΡ Π·Π°ΠΏΠΎΠ»Π½ΡΡΡ ΠΈ ΠΈΡΠΊΠ»ΡΡΠ°ΡΡ ΠΈΠ· ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π½ΠΈΡ Π΄Π°Π½Π½ΡΡ ΡΡΡΠΎΠΊΡ (ΡΡΠΎΠ»Π±Π΅Ρ). ΠΡΠΎΠ΄ΠΎΠ»ΠΆΠ°Ρ ΡΠ°ΠΊ, ΠΏΠΎΡΠ»Π΅ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ³ΠΎ ΡΠΈΡΠ»Π° ΡΠ°Π³ΠΎΠ² Π·Π°ΠΏΠΎΠ»Π½ΡΡΡ Π²ΡΠ΅ ΠΊΠ»Π΅ΡΠΊΠΈ, Π² ΠΊΠΎΡΠΎΡΡΡ ΠΏΠΎΠΌΠ΅ΡΠ΅Π½Ρ ΠΊΡΡΠΆΠΊΠΈ Ρ Π·Π°ΠΊΠ»ΡΡΠ΅Π½Π½ΡΠΌΠΈ Π² Π½ΠΈΡ ΡΠΈΡΠ»Π°ΠΌΠΈ. ΠΡΠ»ΠΈ ΠΊ ΡΠΎΠΌΡ ΠΆΠ΅ ΡΠ΄Π°Π΅ΡΡΡ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ Π²Π΅ΡΡ Π³ΡΡΠ·, ΠΈΠΌΠ΅ΡΡΠΈΠΉΡΡ Π² ΠΏΡΠ½ΠΊΡΠ°Ρ ΠΎΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ, ΠΌΠ΅ΠΆΠ΄Ρ ΠΏΡΠ½ΠΊΡΠ°ΠΌΠΈ Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ, ΡΠΎ ΠΏΠΎΠ»ΡΡΠ°ΡΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΏΠ»Π°Π½ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ. ΠΡΠ»ΠΈ ΠΆΠ΅ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΏΠ»Π°Π½ Π½Π΅ ΠΏΠΎΠ»ΡΡΠ΅Π½, ΡΠΎ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄ΡΡ ΠΊ Π½ΠΎΠ²ΠΎΠΉ ΡΠ°Π±Π»ΠΈΡΠ΅. ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ Π½Π°Ρ ΠΎΠ΄ΡΡ ΠΈΠ·Π±ΡΡΠΎΡΠ½ΡΠ΅ ΠΈ Π½Π΅Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΡΠ΅ ΡΡΡΠΎΠΊΠΈ, ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΡΡ ΡΠ΅Π½ΡΡ ΠΈ Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ ΡΡΠΎΠ³ΠΎ ΡΡΡΠΎΡΡ Π½ΠΎΠ²ΡΡ ΡΠ°Π±Π»ΠΈΡΡ. ΠΡΠΈ ΡΡΠΎΠΌ ΠΌΠΎΠ³ΡΡ Π²ΠΎΠ·Π½ΠΈΠΊΠ½ΡΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΠ΅ Π·Π°ΡΡΡΠ΄Π½Π΅Π½ΠΈΡ ΠΏΡΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠΈ Π·Π½Π°ΠΊΠ° ΡΡΡΠΎΠΊΠΈ, ΠΊΠΎΠ³Π΄Π° Π΅Π΅ Π½Π΅ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠΉ ΠΎΡΡΠ°ΡΠΎΠΊ ΡΠ°Π²Π΅Π½ Π½ΡΠ»Ρ. Π ΡΡΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΡΡΡΠΎΠΊΡ ΡΡΠΈΡΠ°ΡΡ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΠΏΡΠΈ ΡΡΠ»ΠΎΠ²ΠΈΠΈ, ΡΡΠΎ Π²ΡΠΎΡΠ°Ρ Π·Π°ΠΏΠΎΠ»Π½Π΅Π½Π½Π°Ρ ΠΊΠ»Π΅ΡΠΊΠ°, ΡΡΠΎΡΡΠ°Ρ Π² ΡΡΠΎΠ»Π±ΡΠ΅, ΡΠ²ΡΠ·Π°Π½Π½ΠΎΠΌ Ρ Π΄Π°Π½Π½ΠΎΠΉ ΡΡΡΠΎΠΊΠΎΠΉ Π΅ΡΠ΅ ΠΎΠ΄Π½ΠΎΠΉ Π·Π°ΠΏΠΎΠ»Π½Π΅Π½Π½ΠΎΠΉ ΠΊΠ»Π΅ΡΠΊΠΎΠΉ, ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Π° Π² ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅.
ΠΠΎΡΠ»Π΅ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ³ΠΎ ΡΠΈΡΠ»Π° ΠΎΠΏΠΈΡΠ°Π½Π½ΡΡ Π²ΡΡΠ΅ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΉ Π½Π΅ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠΉ ΠΎΡΡΠ°ΡΠΎΠΊ ΡΡΠ°Π½ΠΎΠ²ΠΈΡΡΡ ΡΠ°Π²Π½ΡΠΌ Π½ΡΠ»Ρ. Π ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ΅ ΠΏΠΎΠ»ΡΡΠ°ΡΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΏΠ»Π°Π½ Π΄Π°Π½Π½ΠΎΠΉ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ.
III ΡΡΠ°ΠΏ. ΠΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ, Π²ΡΠ²ΠΎΠ΄ΠΈΠΌΠΎΠΉ ΠΈΠ· Π±Π°Π·ΠΈΡΠ° (ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΡΠΈΠΊΠ»Π°).
ΠΡΠΎΡΠ΅Π΄ΡΡΠ° ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΡΠΈΠΊΠ»Π° ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½ΡΠ½Π° ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ ΡΡΠ»ΠΎΠ²ΠΈΡ Π΄ΠΎΠΏΡΡΡΠΈΠΌΠΎΡΡΠΈ Π² ΡΠΈΠΌΠΏΠ»Π΅ΠΊΡ-ΠΌΠ΅ΡΠΎΠ΄Π΅.
1. Π‘ΡΡΠΎΠΈΡΡΡ Π·Π°ΠΌΠΊΠ½ΡΡΡΠΉ ΡΠΈΠΊΠ», ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΉ Π²Π²ΠΎΠ΄ΠΈΠΌΠΎΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ. ΠΠ½ ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ Π³ΠΎΡΠΈΠ·ΠΎΠ½ΡΠ°Π»ΡΠ½ΡΡ ΠΈ Π²Π΅ΡΡΠΈΠΊΠ°Π»ΡΠ½ΡΡ ΡΠ²ΡΠ·Π°Π½Π½ΡΡ ΠΎΡΡΠ΅Π·ΠΊΠΎΠ², ΠΊΠΎΠ½ΡΠ°ΠΌΠΈ ΠΊΠΎΡΠΎΡΡΡ Π΄ΠΎΠ»ΠΆΠ½Ρ Π±ΡΡΡ Π±Π°Π·ΠΈΡΠ½ΡΠ΅ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΠ΅ (Π·Π° ΠΈΡΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅ΠΌ ΡΠ΅Ρ ΠΊΠΎΠ½ΡΠΎΠ², ΠΊΠΎΡΠΎΡΡΠ΅ ΠΎΡΠ½ΠΎΡΡΡΡΡ ΠΊ Π²Π²ΠΎΠ΄ΠΈΠΌΠΎΠΉ Π² Π±Π°Π·ΠΈΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ). ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π±Π°Π·ΠΈΡΠ½ΠΎΠ³ΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΈ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ΅ΠΉ Π½Π΅Π±Π°Π·ΠΈΡΠ½ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΡΡΠΎΠΈΡΡ Π»ΠΈΡΡ ΠΎΠ΄ΠΈΠ½ ΡΠΈΠΊΠ».
2. ΠΠ΅ΡΠ΅ΡΠ½ΡΠΌ Π²Π΅ΡΡΠΈΠ½Π°ΠΌ ΡΠΈΠΊΠ»Π° (Π½Π°ΡΠΈΠ½Π°Ρ Ρ Π²Π²ΠΎΠ΄ΠΈΠΌΠΎΠΉ Π² Π±Π°Π·ΠΈΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ) ΠΏΡΠΈΡΠ²Π°ΠΈΠ²Π°Π΅ΡΡΡ Π·Π½Π°ΠΊ «+», ΡΠ΅ΡΠ½ΡΠΌ — «-» (Π±ΡΠ΄Π΅ΠΌ Π½Π°Π·ΡΠ²Π°ΡΡ ΡΡΠΈ ΠΊΠ»Π΅ΡΠΊΠΈ ΠΏΠ»ΡΡΠΎΠ²ΡΠΌΠΈ ΠΈ ΠΌΠΈΠ½ΡΡΠΎΠ²ΡΠΌΠΈ).
3. ΠΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ Π²ΡΠ²ΠΎΠ΄ΠΈΠΌΠ°Ρ ΠΈΠ· Π±Π°Π·ΠΈΡΠ° ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ, ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΎΠ΄Π½Π° ΠΈΠ· Π±Π°Π·ΠΈΡΠ½ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ , ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Π½ΡΡ Π² Π²Π΅ΡΡΠΈΠ½Π°Ρ ΡΠΈΠΊΠ»Π°, ΠΎΡΠΌΠ΅ΡΠ΅Π½Π½ΡΡ Π·Π½Π°ΠΊΠΎΠΌ «-» ΠΈ ΠΈΠΌΠ΅ΡΡΠΈΡ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅Π΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅.
4. Π€ΠΎΡΠΌΠΈΡΡΠ΅ΡΡΡ Π½ΠΎΠ²ΠΎΠ΅ Π΄ΠΎΠΏΡΡΡΠΈΠΌΠΎΠ΅ Π±Π°Π·ΠΈΡΠ½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅. ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΠ΅, Π½Π°Ρ ΠΎΠ΄ΡΡΠΈΠ΅ΡΡ Π² Π²Π΅ΡΡΠΈΠ½Π°Ρ ΡΠΈΠΊΠ»Π°, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ ΠΊΠΎΡΡΠ΅ΠΊΡΠΈΡΡΡΡΡΡ, Π° ΠΈΠΌΠ΅Π½Π½ΠΎ ΡΠΌΠ΅Π½ΡΡΠ°ΡΡΡΡ ΠΈΠ»ΠΈ ΡΠ²Π΅Π»ΠΈΡΠΈΠ²Π°ΡΡΡΡ Π½Π° Π²Π΅Π»ΠΈΡΠΈΠ½Ρ Π²Π²ΠΎΠ΄ΠΈΠΌΠΎΠΉ Π² Π±Π°Π·ΠΈΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π² Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΠΈ ΠΎΡ Π·Π½Π°ΠΊΠ° Π²Π΅ΡΡΠΈΠ½Ρ ΡΠΈΠΊΠ»Π°.
ΠΠΏΠΈΡΠ°Π½Π½ΡΠΉ Π²ΡΡΠ΅ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄ ΠΎΡ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π° ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΊ Π΄ΡΡΠ³ΠΎΠΌΡ Π΅Π΅ ΠΎΠΏΠΎΡΠ½ΠΎΠΌΡ ΠΏΠ»Π°Π½Ρ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠ΄Π²ΠΈΠ³ΠΎΠΌ ΠΏΠΎ ΡΠΈΠΊΠ»Ρ ΠΏΠ΅ΡΠ΅ΡΡΠ΅ΡΠ°. Π‘Π»Π΅Π΄ΡΠ΅Ρ ΠΎΡΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ ΠΏΡΠΈ ΡΠ΄Π²ΠΈΠ³Π΅ ΠΏΠΎ ΡΠΈΠΊΠ»Ρ ΠΏΠ΅ΡΠ΅ΡΡΠ΅ΡΠ° ΡΠΈΡΠ»ΠΎ Π·Π°Π½ΡΡΡΡ ΠΊΠ»Π΅ΡΠΎΠΊ ΠΎΡΡΠ°Π΅ΡΡΡ Π½Π΅ΠΈΠ·ΠΌΠ΅Π½Π½ΡΠΌ ΠΈ ΡΠ°Π²Π½ΡΠΌ (n + m — 1).
ΠΠ΄Π½Π°ΠΊΠΎ ΠΏΡΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠΈ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π° ΠΈΠ»ΠΈ Π² ΠΏΡΠΎΡΠ΅ΡΡΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°ΡΠΈ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΏΠΎΠ»ΡΡΠ΅Π½ Π²ΡΡΠΎΠΆΠ΄Π΅Π½Π½ΡΠΉ ΠΎΠΏΠΎΡΠ½ΡΠΉ ΠΏΠ»Π°Π½. Π§ΡΠΎΠ±Ρ ΠΈΠ·Π±Π΅ΠΆΠ°ΡΡ Π·Π°ΡΠΈΠΊΠ»ΠΈΠ²Π°Π½ΠΈΡ, ΡΠ»Π΅Π΄ΡΠ΅Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠ΅ Π½ΡΠ»Π΅Π²ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π° Π·Π°ΠΌΠ΅Π½ΠΈΡΡ ΡΠΊΠΎΠ»Ρ ΡΠ³ΠΎΠ΄Π½ΠΎ ΠΌΠ°Π»ΡΠΌ ΡΠΈΡΠ»ΠΎΠΌ Π΅ ΠΈ ΡΠ΅ΡΠ°ΡΡ Π·Π°Π΄Π°ΡΡ ΠΊΠ°ΠΊ Π½Π΅Π²ΡΡΠΎΠΆΠ΄Π΅Π½Π½ΡΡ. Π ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌ ΠΏΠ»Π°Π½Π΅ ΡΠ°ΠΊΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΡΡΠΈΡΠ°ΡΡ Π΅ = 0.
ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΡΠΉ Π·Π°Π΄Π°ΡΠ° Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΠ³Π΅Π»Ρ ΡΠΈΠΊΠ»
2. ΠΡΠΈΠΌΠ΅Ρ ΠΏΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°ΡΠΈ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΠΈ ΡΠΎΠ²Π°ΡΠΎΠ² ΡΠ°Π·Π»ΠΈΡΠ½ΡΠΌΠΈ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΡΠΌΠΈ ΡΡΠ΅Π΄ΡΡΠ²Π°ΠΌΠΈ Π² ΡΡΠ΄Π΅ ΡΠ»ΡΡΠ°Π΅Π² ΠΏΡΠΈΠ²ΠΎΠ΄ΡΡ ΠΊ ΡΠ°ΠΊΠΈΠΌ Π½Π΅ΠΆΠ΅Π»Π°ΡΠ΅Π»ΡΠ½ΡΠΌ ΡΠ²Π»Π΅Π½ΠΈΡΠΌ, ΠΊΠ°ΠΊ ΠΏΠΎΡΠΎΠΆΠ½ΠΈΠ΅ ΠΏΡΠΎΠ±Π΅Π³ΠΈ, ΠΏΡΠΎΡΡΠΎΠΈ, Π²ΡΡΡΠ΅ΡΠ½ΡΠ΅ ΠΈ Π½Π΅ΡΠ°ΡΠΈΠΎΠ½Π°Π»ΡΠ½ΡΠ΅ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΠΈ. ΠΠ»Ρ ΠΈΡ ΠΈΡΠΊΠ»ΡΡΠ΅Π½ΠΈΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΡΡ ΠΌΠ΅ΡΠΎΠ΄Ρ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ, Π² ΡΠ°ΡΡΠ½ΠΎΡΡΠΈ ΡΠ°ΠΊΠ°Ρ ΡΠΊΠΎΠ½ΠΎΠΌΠΈΠΊΠΎ-ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠ°Ρ ΠΌΠΎΠ΄Π΅Π»Ρ, ΠΊΠ°ΠΊ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½Π°Ρ Π·Π°Π΄Π°ΡΠ°.
ΠΡΠΎΡΡΠ΅ΠΉΡΠΈΠΌ ΠΏΡΠΈΠΌΠ΅ΡΠΎΠΌ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΡΠ²Π»ΡΠ΅ΡΡΡ Π·Π°Π΄Π°ΡΠ° ΠΎ ΠΏΠ»Π°Π½ΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΏΡΠΎΠ΄ΡΠΊΡΠ° ΠΈΠ· ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ³ΠΎ ΡΠΈΡΠ»Π° ΠΏΡΠ½ΠΊΡΠΎΠ² ΠΎΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ Π² ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ ΠΏΡΠ½ΠΊΡΠΎΠ² Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΏΡΠΈ ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠ΅Π½ΠΈΠΈ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΡ Π·Π°ΡΡΠ°Ρ Π½Π° Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Π΄Π°Π½Π½ΠΎΠΉ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ.
ΠΡΠΈΠΌΠ΅Ρ: Π’ΡΠΈ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠ° Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΡΠΎΠ²Π°ΡΠ° ΡΠ°ΡΠΏΠΎΠ»Π°Π³Π°ΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌΠΈ Π·Π°ΠΏΠ°ΡΠ°ΠΌΠΈ: ΠΏΠ΅ΡΠ²ΡΠΉ — 120 Π΅Π΄ΠΈΠ½ΠΈΡ, Π²ΡΠΎΡΠΎΠΉ — 100 Π΅Π΄ΠΈΠ½ΠΈΡ, ΡΡΠ΅ΡΠΈΠΉ — 80 Π΅Π΄ΠΈΠ½ΠΈΡ. Π’ΠΎΠ²Π°Ρ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±ΡΡΡ ΠΏΠ΅ΡΠ΅Π²Π΅Π·Π΅Π½ ΡΡΠ΅ΠΌ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»ΡΠΌ: ΡΠΏΡΠΎΡ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ — 90 Π΅Π΄ΠΈΠ½ΠΈΡ; ΡΠΏΡΠΎΡ Π²ΡΠΎΡΠΎΠ³ΠΎ — 90 Π΅Π΄ΠΈΠ½ΠΈΡ; ΡΠΏΡΠΎΡ ΡΡΠ΅ΡΡΠ΅Π³ΠΎ — 120 Π΅Π΄ΠΈΠ½ΠΈΡ. ΠΠ·Π²Π΅ΡΡΠ½Ρ ΡΠ°ΠΊΠΆΠ΅ ΠΏΠΎΠΊΠ°Π·Π°ΡΠ΅Π»ΠΈ Π·Π°ΡΡΠ°Ρ (cij) Π½Π° ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΡ Π΅Π΄ΠΈΠ½ΠΈΡΡ ΡΠΎΠ²Π°ΡΠ° ΠΎΡ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠ° ΠΊ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ.
Π’ΡΠ΅Π±ΡΠ΅ΡΡΡ ΡΠΎΡΡΠ°Π²ΠΈΡΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΏΠ»Π°Π½ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ, ΠΏΡΠΈΠ²ΠΎΠ΄ΡΡΠΈΠΉ ΠΊ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΠΌ Π·Π°ΡΡΠ°ΡΠ°ΠΌ Π½Π° Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Π΄Π°Π½Π½ΠΎΠΉ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ.
ΠΠΎΠ΄ ΠΏΠ»Π°Π½ΠΎΠΌ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ ΠΏΠΎΠ½ΠΈΠΌΠ°Π΅ΡΡΡ ΠΌΠ°ΡΡΠΈΡΠ°
X11 | X12 | X13 | |
X21 | X22 | X23 | |
X31 | X32 | X33 | |
Π² ΠΊΠΎΡΠΎΡΠΎΠΉ Ρ ij ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π΅Π΄ΠΈΠ½ΠΈΡ ΡΠΎΠ²Π°ΡΠ°, ΠΏΠ»Π°Π½ΠΈΡΡΠ΅ΠΌΠΎΠ³ΠΎ ΠΊ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΠ΅ ΠΎΡ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠ° Ρ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ i ΠΊ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ Ρ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ j.
ΠΠ»Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°ΡΠΈ ΠΈΡΡ ΠΎΠ΄Π½ΡΠ΅ Π΄Π°Π½Π½ΡΠ΅ ΡΠ΄ΠΎΠ±Π½ΠΎ ΡΠ²Π΅ΡΡΠΈ Π² ΡΠ°Π±Π»ΠΈΡΡ:
ΠΠΎΡΡΠ°Π²ΡΠΈΠΊΠΈ | ΠΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠΎΠ² | ΠΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»ΠΈ ΠΈ ΠΈΡ ΡΠΏΡΠΎΡ | |||
ΠΠ°ΠΆΠ΄ΡΡ ΠΊΠ»Π΅ΡΠΊΡ ΡΠ°Π±Π»ΠΈΡΡ ΠΏΠΎΠΌΠ΅ΡΠΈΠΌ Π΄Π²ΠΎΠΉΠ½ΡΠΌ ΠΈΠ½Π΄Π΅ΠΊΡΠΎΠΌ (i, j). ΠΠ΅ΡΠ²ΡΠΉ (i) — Π½ΠΎΠΌΠ΅Ρ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠ°, Π²ΡΠΎΡΠΎΠΉ (j) — Π½ΠΎΠΌΠ΅Ρ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ.
Π§ΠΈΡΠ»Π° Π½Π° ΠΏΠ΅ΡΠ΅ΡΠΈΡΠ΅Π½ΠΈΠΈ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ ΠΈ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ°ΡΡΡΡ Ρij.
ΠΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠ°Ρ ΠΏΠΎΡΡΠ°Π½ΠΎΠ²ΠΊΠ° Π΄Π°Π½Π½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΈΠΌΠ΅Π΅Ρ Π²ΠΈΠ΄: Π½Π°ΠΉΡΠΈ ΠΌΠΈΠ½ΠΈΠΌΡΠΌ ΡΠ΅Π»Π΅Π²ΠΎΠΉ ΡΡΠ½ΠΊΡΠΈΠΈ (ΠΏΠΎΠΊΠ°Π·Π°ΡΠ΅Π»Ρ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎΡΡΠΈ)
Z= 7Ρ 11 + 6Ρ 12 + 4Ρ 13 + ΠΡ 21 + 8Ρ 22 + 5Ρ 23 + +2Ρ 31 +3Ρ 32 + 7Ρ 33 ΠΏΡΠΈ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΡΡ :
n n n
Π£x1j =120; Π£x2j =100; Π£x3j =80;
j=i j=i j=i
m m m
Π£xi1 =90; Π£xi1 =90; Π£xi1 =120; Ρ ij>0
i=l i=l i=l
Π’ΡΠ°Π½ΡΠΏΠΎΡΡΠ½Π°Ρ Π·Π°Π΄Π°ΡΠ° ΠΎΡΠ½ΠΎΡΠΈΡΡΡ ΠΊ ΠΊΠ»Π°ΡΡΡ Π·Π°Π΄Π°Ρ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ. Π Π΅ΡΠ΅Π½ΠΈΠ΅ ΡΠ°ΠΊΠΈΡ Π·Π°Π΄Π°Ρ ΠΎΠ±ΡΡΠ½ΠΎ ΡΠ²ΡΠ·Π°Π½ΠΎ Ρ ΠΏΠΎΠ»ΡΡΠ΅Π½ΠΈΠ΅ΠΌ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ (Π΄ΠΎΠΏΡΡΡΠΈΠΌΠΎΠ³ΠΎ) ΠΏΠ»Π°Π½Π° ΠΈ ΠΏΠΎΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ Π΅Π³ΠΎ ΡΠ»ΡΡΡΠ΅Π½ΠΈΠ΅ΠΌ.
ΠΠΏΠΎΡΠ½ΡΠΉ ΠΏΠ»Π°Π½ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΏΠΎΠ»ΡΡΠ΅Π½ ΡΠ°Π·Π»ΠΈΡΠ½ΡΠΌΠΈ ΠΌΠ΅ΡΠΎΠ΄Π°ΠΌΠΈ. Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΠΌΠ΅ΡΠΎΠ΄ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°, ΠΈΠ»ΠΈ ΠΌΠ΅ΡΠΎΠ΄ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΡ .
Π ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠΈ Ρ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΡ Π·Π°ΡΡΠ°Ρ Π²ΡΠ±Π΅ΡΠ΅ΠΌ Π² ΡΠ°Π±Π»ΠΈΡΠ΅ ΠΊΠ»Π΅ΡΠΊΡ, ΠΈΠΌΠ΅ΡΡΡΡ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΠΉ ΠΏΠΎΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π·Π°ΡΡΠ°Ρ, Ρ. Π΅. ΠΊΠ»Π΅ΡΠΊΡ (3,1). ΠΡΠΎΠΈΠ·Π²Π΅Π΄Π΅ΠΌ ΠΏΠΎΡΡΠ°Π²ΠΊΡ Π² ΡΡΡ ΠΊΠ»Π΅ΡΠΊΡ, ΡΠ°Π²Π½ΡΡ 80 Π΅Π΄ΠΈΠ½ΠΈΡΠ°ΠΌ, ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΠΏΠ΅ΡΠ²ΠΎΠΌΡ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ ΡΡΠ΅Π±ΡΠ΅ΡΡΡ .90 Π΅Π΄ΠΈΠ½ΠΈΡ, Π° Ρ ΡΡΠ΅ΡΡΠ΅Π³ΠΎ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠ° Π² Π½Π°Π»ΠΈΡΠΈΠΈ Π»ΠΈΡΡ 80 Π΅Π΄ΠΈΠ½ΠΈΡ. ΠΠ΅ΡΠ²ΠΎΠΌΡ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π΅ΡΠ΅ 10 Π΅Π΄ΠΈΠ½ΠΈΡ ΡΠΎΠ²Π°ΡΠ°. ΠΠ½ ΠΌΠΎΠΆΠ΅Ρ ΠΏΠΎΠ»ΡΡΠΈΡΡ ΠΈΡ ΠΈΠ»ΠΈ ΠΎΡ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ, ΠΈΠ»ΠΈ ΠΎΡ Π²ΡΠΎΡΠΎΠ³ΠΎ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠ°. Π’Π°ΠΊ ΠΊΠ°ΠΊ ΠΏΠΎΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π·Π°ΡΡΠ°Ρ Π² ΠΊΠ»Π΅ΡΠΊΠ΅ (2,1) ΠΌΠ΅Π½ΡΡΠ΅, ΡΠ΅ΠΌ Π² ΠΊΠ»Π΅ΡΠΊΠ΅ (1,1), ΡΠΎ Π·Π°ΠΏΠΈΡΡΠ²Π°Π΅ΠΌ 10 Π΅Π΄ΠΈΠ½ΠΈΡ Π² ΠΊΠ»Π΅ΡΠΊΡ (2,1).
ΠΡΠΎΡΠΎΠΉ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊ, ΠΎΡΠ΄Π°Π² 10 Π΅Π΄ΠΈΠ½ΠΈΡ, Π±ΡΠ΄Π΅Ρ ΡΠ°ΡΠΏΠΎΠ»Π°Π³Π°ΡΡ 90 Π΅Π΄ΠΈΠ½ΠΈΡΠ°ΠΌΠΈ. ΠΡ ΠΌΠΎΠΆΠ½ΠΎ Π½Π°ΠΏΡΠ°Π²ΠΈΡΡ Π²ΡΠΎΡΠΎΠΌΡ ΠΈΠ»ΠΈ ΡΡΠ΅ΡΡΠ΅ΠΌΡ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ. Π ΡΠ²ΡΠ·ΠΈ Ρ ΡΠ΅ΠΌ, ΡΡΠΎ ΠΏΠΎΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π·Π°ΡΡΠ°Ρ Π² ΠΊΠ»Π΅ΡΠΊΠ΅ (2, 3) ΠΌΠ΅Π½ΡΡΠ΅, ΡΠ΅ΠΌ Π² ΠΊΠ»Π΅ΡΠΊΠ΅ (2, 2), Π½Π°ΠΏΡΠ°Π²ΠΈΠΌ ΠΈΡ ΡΡΠ΅ΡΡΠ΅ΠΌΡ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ. ΠΠ΅Π΄ΠΎΡΡΠ°ΡΡΠΈΠ΅ 30 Π΅Π΄ΠΈΠ½ΠΈΡ ΡΡΠ΅ΡΠΈΠΉ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ ΠΏΠΎΠ»ΡΡΠΈΡ ΠΎΡ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠ°.
ΠΡΡΠ°Π²ΡΠΈΠ΅ΡΡ Ρ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠ° 90 Π΅Π΄ΠΈΠ½ΠΈΡ Π·Π°ΠΏΠΈΡΠ΅ΠΌ Π² ΠΊΠ»Π΅ΡΠΊΡ (1, 2) ΠΈ, ΡΠ΅ΠΌ ΡΠ°ΠΌΡΠΌ, ΡΠ΄ΠΎΠ²Π»Π΅ΡΠ²ΠΎΡΠΈΠΌ ΡΠΏΡΠΎΡ Π²ΡΠΎΡΠΎΠ³ΠΎ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ.
ΠΠ° ΡΡΠΎΠΌ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΡΡΠΈΡΠ°ΡΡ Π·Π°ΠΊΠΎΠ½ΡΠ΅Π½Π½ΡΠΌ.
ΠΠΎΡΡΠ°Π²ΡΠΈΠΊΠΈ | ΠΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠΎΠ² | ΠΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»ΠΈ ΠΈ ΠΈΡ ΡΠΏΡΠΎΡ | |||
ΠΠΎΠ»ΡΡΠΈΠ² ΠΎΠΏΠΎΡΠ½ΡΠΉ ΠΏΠ»Π°Π½, Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΡΠ΅Π½ΠΈΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΡΡ Π΅ΠΌΡ ΡΡΠΎΠΈΠΌΠΎΡΡΡ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ (ΠΏΠΎΠΊΠ°Π·Π°ΡΠ΅Π»Ρ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎΡΡΠΈ ΠΈΠ»ΠΈ ΡΠ΅Π»Π΅Π²ΡΡ ΡΡΠ½ΠΊΡΠΈΡ). ΠΠ»Ρ ΠΏΠ»Π°Π½Π°, ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΠΎΠ³ΠΎ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΡ Π·Π°ΡΡΠ°Ρ, Z = 1300 Π΅Π΄.
Π‘Π»Π΅Π΄ΡΡΡΠΈΠΌ ΡΡΠ°ΠΏΠΎΠΌ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°ΡΠΈ, Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎ ΠΎΡ ΡΠΎΠ³ΠΎ, ΠΊΠ°ΠΊΠΈΠΌ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π±ΡΠ» Π½Π°ΠΉΠ΄Π΅Π½ ΠΎΠΏΠΎΡΠ½ΡΠΉ ΠΏΠ»Π°Π½, ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΠ΅ Π΅Π³ΠΎ ΡΠ»ΡΡΡΠ΅Π½ΠΈΠ΅ Π΄ΠΎ ΠΏΠΎΠ»ΡΡΠ΅Π½ΠΈΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ. Π‘ ΡΡΠΎΠΉ ΡΠ΅Π»ΡΡ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΡ ΡΠΎΠ²Π°ΡΠΎΠ² ΠΏΠΎΡΡΠ°Π²ΠΈΠΌ Π² ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠ΅ ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»Ρ Π1, Π2, Π3 ΠΈ Π·Π°ΠΏΠΈΡΠ΅ΠΌ ΠΈΡ Π² Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΌ ΡΡΠΎΠ»Π±ΡΠ΅, Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ — ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»Ρ B1, Π2, Π3, ΠΊΠΎΡΠΎΡΡΠ΅ Π·Π°ΠΏΠΈΡΠ΅ΠΌ Π² Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅. ΠΠ΄ΠΈΠ½ ΠΈΠ· ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ², Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ A1 ΠΏΡΠΈΡΠ°Π²Π½ΡΠ΅ΠΌ ΠΊ Π½ΡΠ»Ρ, Π° ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ Π½Π°ΠΉΠ΄Π΅ΠΌ Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ:
Πij = Πi + Πj
ΠΠ°ΠΏΠΈΡΠ΅ΠΌ Π΄Π°Π½Π½ΠΎΠ΅ ΡΠΎΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠ΅ Π΄Π»Ρ Π²ΡΠ΅Ρ Π·Π°ΠΏΠΎΠ»Π½Π΅Π½Π½ΡΡ ΠΊΠ»Π΅ΡΠΎΠΊ (Π₯ij > 0) ΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΠΌ Π2, Π3, Π1, Π2, Π3. ΠΠ»Ρ Π½Π΅Π·Π°ΠΏΠΎΠ»Π½Π΅Π½Π½ΡΡ ΠΊΠ»Π΅ΡΠΎΠΊ (Π₯ij = 0) Π·Π°ΠΏΠΈΡΠ΅ΠΌ Π°Π½Π°Π»ΠΎΠ³ΠΈΡΠ½ΡΡ Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΡ, Π»Π΅Π²ΡΡ ΡΠ°ΡΡΡ ΠΊΠΎΡΠΎΡΠΎΠΉ ΠΏΡΠΈΠ½ΡΡΠΎ Π½Π°Π·ΡΠ²Π°ΡΡ ΠΏΡΠ΅Π²Π΄ΠΎΡΡΠΎΠΈΠΌΠΎΡΡΡΡ.
Cij = Ai+Bj
Π£ΡΠ»ΠΎΠ²ΠΈΠ΅ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΡΡΠΈ ΠΏΠ»Π°Π½Π° Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΡΠ²ΠΎΠ±ΠΎΠ΄Π½ΠΎΠΉ ΠΊΠ»Π΅ΡΠΊΠΈ (Xij = 0)
Π‘ij<οΏ½Π‘ij.
ΠΠ°ΠΉΠ΄Π΅ΠΌ Π΄Π»Ρ ΡΠ²ΠΎΠ±ΠΎΠ΄Π½ΡΡ ΠΊΠ»Π΅ΡΠΎΠΊ ΡΠ°Π·Π½ΠΎΡΡΠΈ Πij = Π‘ij — Cij ΠΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΠΎΠ΄Π½Π° ΠΈΠ· ΡΠ°Π·Π½ΠΎΡΡΠ΅ΠΉ, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ°Ρ ΠΊΠ»Π΅ΡΠΊΠ΅ (3,2), ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½Π°, ΡΠΎ ΡΠ»ΡΡΡΠ΅Π½ΠΈΠ΅ ΠΏΠ»Π°Π½Π° Π½Π°ΡΠΈΠ½Π°Π΅ΠΌ ΠΈΠΌΠ΅Π½Π½ΠΎ Ρ Π½Π΅Π΅.
ΠΠΎΡΡΠ°Π²ΡΠΈΠΊΠΈ | ΠΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠΎΠ² | ΠΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»ΠΈ ΠΈ ΠΈΡ ΡΠΏΡΠΎΡ | Ai | |||
Bj | ||||||
ΠΠ°ΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ Π΅ΡΠ»ΠΈ ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΡ ΡΠ°Π·Π½ΠΎΡΡΠ΅ΠΉ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ, ΡΠΎ ΠΏΠ΅ΡΠ²ΠΎΠΉ Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ ΠΊΠ»Π΅ΡΠΊΠ°, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΠ°Π·Π½ΠΎΡΡΡ ΠΏΠΎ Π°Π±ΡΠΎΠ»ΡΡΠ½ΠΎΠΉ Π²Π΅Π»ΠΈΡΠΈΠ½Π΅ Π±ΠΎΠ»ΡΡΠ΅.
ΠΠΎΠ³ΡΡΠ·ΠΈΠΌ ΠΊΠ»Π΅ΡΠΊΡ (3, 2), ΠΏΠΎΡΡΠ°Π²ΠΈΠ² Π² Π½Π΅Π΅ Π·Π½Π°ΠΊ ΠΏΠ»ΡΡ (+), ΠΈ ΡΠΎΡΡΠ°Π²ΠΈΠΌ ΡΠ΅ΠΏΡ ΠΏΠ΅ΡΠ΅ΡΡΠ΅ΡΠ° ΠΏΠΎ ΠΏΡΠ°Π²ΠΈΠ»Ρ: ΡΠ΅ΠΏΡ ΠΏΠ΅ΡΠ΅ΡΡΠ΅ΡΠ° ΡΡΡΠΎΠΈΡΡΡ Π² Π²ΠΈΠ΄Π΅ ΠΏΡΡΠΌΠΎΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠ°, ΠΎΠ΄Π½Π° ΠΈΠ· Π²Π΅ΡΡΠΈΠ½ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ Π² ΡΠ²ΠΎΠ±ΠΎΠ΄Π½ΠΎΠΉ ΠΊΠ»Π΅ΡΠΊΠ΅ (3, 2), Π° ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ — Π² Π·Π°Π½ΡΡΡΡ ; Π²ΡΠ΅ ΡΠ³Π»Ρ Π΄ΠΎΠ»ΠΆΠ½Ρ Π±ΡΡΡ ΠΏΡΡΠΌΡΠΌΠΈ; Π² ΠΎΠ΄Π½ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅ ΠΈ Π² ΠΎΠ΄Π½ΠΎΠΌ ΡΡΠΎΠ»Π±ΡΠ΅ Π½Π΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±ΡΡΡ Π±ΠΎΠ»Π΅Π΅ Π΄Π²ΡΡ Π²Π΅ΡΡΠΈΠ½; Π²ΡΠ΅ΠΌ Π²Π΅ΡΡΠΈΠ½Π°ΠΌ ΠΏΡΠΈΠΏΠΈΡΡΠ²Π°ΡΡΡΡ ΡΠ΅ΡΠ΅Π΄ΡΡΡΠΈΠ΅ΡΡ Π·Π½Π°ΠΊΠΈ (ΠΏΠ»ΡΡ — Π΄ΠΎΠ³ΡΡΠ·ΠΈΡΡ, ΠΌΠΈΠ½ΡΡ — ΡΠ°Π·Π³ΡΡΠ·ΠΈΡΡ).
ΠΠΎΡΡΠ°Π²ΡΠΈΠΊΠΈ | ΠΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠΎΠ² | ΠΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»ΠΈ ΠΈ ΠΈΡ ΡΠΏΡΠΎΡ | Ai | |||
6; | 4+ | |||||
3+ | 5; | |||||
2; | 3+6 | |||||
Bj | ||||||
ΠΠ· ΠΊΠ»Π΅ΡΠΎΠΊ ΡΠΎ Π·Π½Π°ΠΊΠΎΠΌ ΠΌΠΈΠ½ΡΡ (-) Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ°Ρ Π²Π΅Π»ΠΈΡΠΈΠ½Π° Π³ΡΡΠ·Π° min (80, 90, 90) = 80 ΠΈ ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ°Π΅ΡΡΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ ΠΏΠΎ ΠΊΠ»Π΅ΡΠΊΠ°ΠΌ ΠΏΠΎΡΡΡΠΎΠ΅Π½Π½ΠΎΠΉ ΡΠ΅ΠΏΠΈ: 80 Π΅Π΄ΠΈΠ½ΠΈΡ Π΄ΠΎΠ±Π°Π²Π»ΡΡΡΡΡ Π² ΠΊΠ»Π΅ΡΠΊΠΈ ΡΠΎ Π·Π½Π°ΠΊΠΎΠΌ ΠΏΠ»ΡΡ ΠΈ ΠΈΠ·ΡΠΌΠ°ΡΡΡΡ ΠΈΠ· ΠΊΠ»Π΅ΡΠΎΠΊ ΡΠΎ Π·Π½Π°ΠΊΠΎΠΌ ΠΌΠΈΠ½ΡΡ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΏΠΎΠ»ΡΡΠ°Π΅ΠΌ Π½ΠΎΠ²ΡΠΉ ΠΏΠ»Π°Π½ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ. ΠΡΠΈΠΌΠ΅Π½ΠΈΠ² ΠΊ Π½Π΅ΠΌΡ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π½Π½ΡΡ Π²ΡΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄ΠΈΠΊΡ, ΠΌΠΎΠΆΠ½ΠΎ ΡΠ±Π΅Π΄ΠΈΡΡΡΡ, ΡΡΠΎ ΡΡΠΎΡ ΠΏΠ»Π°Π½ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ.
ΠΠΎΡΡΠ°Π²ΡΠΈΠΊΠΈ | ΠΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠΎΠ² | ΠΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»ΠΈ ΠΈ ΠΈΡ ΡΠΏΡΠΎΡ | |||
Π ΠΎΠ±ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠ°Ρ ΠΏΠΎΡΡΠ°Π½ΠΎΠ²ΠΊΠ° ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΈΠΌΠ΅Π΅Ρ Π²ΠΈΠ΄:
ΠΏΡΠΈ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΡΡ
Π ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π½Π½ΠΎΠΌ ΠΏΡΠΈΠΌΠ΅ΡΠ΅ Ρ. Π΅. Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠΎΠ² ΡΠ°Π²Π½Ρ ΡΡΠΌΠΌΠ°ΡΠ½ΠΎΠΌΡ ΡΠΏΡΠΎΡΡ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Π΅ΠΉ. Π’ΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΡΠ΅ Π·Π°Π΄Π°ΡΠΈ ΠΏΠΎΠ΄ΠΎΠ±Π½ΠΎΠ³ΠΎ Π²ΠΈΠ΄Π° Π½Π°Π·ΡΠ²Π°ΡΡ Π·Π°ΠΊΡΡΡΡΠΌΠΈ. ΠΠ°Π΄Π°ΡΠΈ, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΡΡ ΡΡΠΎ ΡΡΠ»ΠΎΠ²ΠΈΠ΅ Π½Π΅ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΡΡ ΡΠΎΠ±ΠΎΠΉ ΠΎΡΠΊΡΡΡΡΠ΅ Π·Π°Π΄Π°ΡΠΈ. ΠΠ»Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΎΡΠΊΡΡΡΡΡ Π·Π°Π΄Π°Ρ ΠΈΡ ΠΏΡΠΈΠ²ΠΎΠ΄ΡΡ ΠΊ Π·Π°ΠΊΡΡΡΠΎΠΌΡ Π²ΠΈΠ΄Ρ ΠΏΡΡΠ΅ΠΌ Π²Π²Π΅Π΄Π΅Π½ΠΈΡ ΡΠΈΠΊΡΠΈΠ²Π½ΠΎΠ³ΠΎ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠ° ΠΈΠ»ΠΈ ΡΠΈΠΊΡΠΈΠ²Π½ΠΎΠΉ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ Ρ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΡΠΌΠΈ ΠΏΠΎ ΠΏΠΎΡΡΠ°Π²ΠΊΠ΅ ΠΈΠ»ΠΈ ΡΠΏΡΠΎΡΠΎΠΌ, ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΠΌΡΠΌΠΈ ΠΏΠΎ ΡΠΎΡΠΌΡΠ»Π΅ Π ΠΎΡΡΠ°Π»ΡΠ½ΠΎΠΌ ΠΌΠ΅ΡΠΎΠ΄ΠΈΠΊΠ° ΡΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°ΡΠΈ ΠΎΡΡΠ°Π΅ΡΡΡ Π½Π΅ΠΈΠ·ΠΌΠ΅Π½Π½ΠΎΠΉ.
1. ΠΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅. Π£ΡΠ΅Π±Π½ΠΎΠ΅ ΠΈΠ·Π΄Π°Π½ΠΈΠ΅. ΠΠΎΠ΄ ΠΎΠ±ΡΠ΅ΠΉ ΡΠ΅Π΄Π°ΠΊΡΠΈΠ΅ΠΉ Π. Π. ΠΠ°Π»Π΄ΠΈΠ½Π°, Π°Π²ΡΠΎΡΡ Π. Π. ΠΠ°Π»Π΄ΠΈΠ½, Π. Π. ΠΡΡΠ·Π³Π°Π»ΠΎΠ², Π. Π. Π ΡΠΊΠΎΡΡΠ΅Π². ΠΠΎΡΠΊΠ²Π°: «ΠΠ·Π΄Π°ΡΠ΅Π»ΡΡΠΊΠΎ-ΡΠΎΡΠ³ΠΎΠ²Π°Ρ ΠΊΠΎΡΠΏΠΎΡΠ°ΡΠΈΡ «ΠΠ°ΡΠΊΠΎΠ² ΠΈ Π», 2010.