ΠΠ±ΡΠΈΠΉ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ ΠΊ ΠΏΡΠΈΠ½ΡΡΠΈΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π² ΡΡΠ»ΠΎΠ²ΠΈΡΡ ΠΏΠΎΠ»Π½ΠΎΠΉ Π½Π΅ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΠΎΡΡΠΈ
ΠΡΠΈ ΠΏΡΠΈΠ½ΡΡΠΈΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠΉ Π² ΡΡΠ»ΠΎΠ²ΠΈΡΡ ΠΏΠΎΠ»Π½ΠΎΠΉ Π½Π΅ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΠΎΡΡΠΈ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΌΠΈ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠ°ΠΌΠΈ ΠΌΠΎΠ³ΡΡ ΡΠ»ΡΠΆΠΈΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΠΏΡΠ°Π²ΠΈΠ»Π°-ΡΠ΅ΠΊΠΎΠΌΠ΅Π½Π΄Π°ΡΠΈΠΈ. ΠΡΠ°Π²ΠΈΠ»ΠΎ ΠΠ°Π»ΡΠ΄Π° (ΠΏΡΠ°Π²ΠΈΠ»ΠΎ ΠΊΡΠ°ΠΉΠ½Π΅Π³ΠΎ ΠΏΠ΅ΡΡΠΈΠΌΠΈΠ·ΠΌΠ°). Π Π°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Ρ i-Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅, Π±ΡΠ΄Π΅ΠΌ ΠΏΠΎΠ»Π°Π³Π°ΡΡ, ΡΡΠΎ Π½Π° ΡΠ°ΠΌΠΎΠΌ Π΄Π΅Π»Π΅ ΡΠΈΡΡΠ°ΡΠΈΡ ΡΠΊΠ»Π°Π΄ΡΠ²Π°Π΅ΡΡΡ ΡΠ°ΠΌΠ°Ρ ΠΏΠ»ΠΎΡ Π°Ρ, Ρ. Π΅. ΠΏΡΠΈΠ½ΠΎΡΡΡΠ°Ρ ΡΠ°ΠΌΡΠΉ ΠΌΠ°Π»ΡΠΉ Π΄ΠΎΡ ΠΎΠ΄ ai = min qij. ΠΠΎ ΡΠ΅ΠΏΠ΅ΡΡ ΡΠΆΠ΅ Π²ΡΠ±Π΅ΡΠ΅ΠΌ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Ρ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΠΌ ai0. ΠΡΠ°ΠΊ, ΠΏΡΠ°Π²ΠΈΠ»ΠΎ ΠΠ°Π»ΡΠ΄Π° ΡΠ΅ΠΊΠΎΠΌΠ΅Π½Π΄ΡΠ΅Ρ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠ±ΡΠΈΠΉ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ ΠΊ ΠΏΡΠΈΠ½ΡΡΠΈΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π² ΡΡΠ»ΠΎΠ²ΠΈΡΡ ΠΏΠΎΠ»Π½ΠΎΠΉ Π½Π΅ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΠΎΡΡΠΈ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΡΠΈ ΠΏΡΠΈΠ½ΡΡΠΈΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠΉ Π² ΡΡΠ»ΠΎΠ²ΠΈΡΡ ΠΏΠΎΠ»Π½ΠΎΠΉ Π½Π΅ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΠΎΡΡΠΈ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΌΠΈ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠ°ΠΌΠΈ ΠΌΠΎΠ³ΡΡ ΡΠ»ΡΠΆΠΈΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΠΏΡΠ°Π²ΠΈΠ»Π°-ΡΠ΅ΠΊΠΎΠΌΠ΅Π½Π΄Π°ΡΠΈΠΈ. ΠΡΠ°Π²ΠΈΠ»ΠΎ ΠΠ°Π»ΡΠ΄Π° (ΠΏΡΠ°Π²ΠΈΠ»ΠΎ ΠΊΡΠ°ΠΉΠ½Π΅Π³ΠΎ ΠΏΠ΅ΡΡΠΈΠΌΠΈΠ·ΠΌΠ°). Π Π°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Ρ i-Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅, Π±ΡΠ΄Π΅ΠΌ ΠΏΠΎΠ»Π°Π³Π°ΡΡ, ΡΡΠΎ Π½Π° ΡΠ°ΠΌΠΎΠΌ Π΄Π΅Π»Π΅ ΡΠΈΡΡΠ°ΡΠΈΡ ΡΠΊΠ»Π°Π΄ΡΠ²Π°Π΅ΡΡΡ ΡΠ°ΠΌΠ°Ρ ΠΏΠ»ΠΎΡ Π°Ρ, Ρ. Π΅. ΠΏΡΠΈΠ½ΠΎΡΡΡΠ°Ρ ΡΠ°ΠΌΡΠΉ ΠΌΠ°Π»ΡΠΉ Π΄ΠΎΡ ΠΎΠ΄ ai = min qij. ΠΠΎ ΡΠ΅ΠΏΠ΅ΡΡ ΡΠΆΠ΅ Π²ΡΠ±Π΅ΡΠ΅ΠΌ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Ρ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΠΌ ai0. ΠΡΠ°ΠΊ, ΠΏΡΠ°Π²ΠΈΠ»ΠΎ ΠΠ°Π»ΡΠ΄Π° ΡΠ΅ΠΊΠΎΠΌΠ΅Π½Π΄ΡΠ΅Ρ ΠΏΡΠΈΠ½ΡΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ i0 ΡΠ°ΠΊΠΎΠ΅, ΡΡΠΎ ai0 = max = max (min qij). Π’Π°ΠΊ, Π² Π²ΡΡΠ΅ΡΠΊΠ°Π·Π°Π½Π½ΠΎΠΌ ΠΏΡΠΈΠΌΠ΅ΡΠ΅ ΠΈΠΌΠ΅Π΅ΠΌ a1 = 0, a2 =2, a3 = 3, a4 = -12. Π’Π΅ΠΏΠ΅ΡΡ ΠΈΠ· ΡΠΈΡΠ΅Π» 0, 2, 3, -12 Π½Π°Ρ ΠΎΠ΄ΠΈΠΌ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅. ΠΡΠΎ — 3. ΠΠ½Π°ΡΠΈΡ, ΠΏΡΠ°Π²ΠΈΠ»Π° ΠΠ°Π»ΡΠ΄Π° ΡΠ΅ΠΊΠΎΠΌΠ΅Π½Π΄ΡΠ΅Ρ ΠΏΡΠΈΠ½ΡΡΡ 3-Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅. ΠΠ°Π½Π½ΠΎΠΌΡ ΠΏΡΠ°Π²ΠΈΠ»Ρ ΡΠ»Π΅Π΄ΡΠ΅Ρ ΡΠ΅Π»ΠΎΠ²Π΅ΠΊ, Π±ΠΎΡΡΠΈΠΉΡΡ ΡΠΈΡΠΊΠ°. ΠΡΠ°Π²ΠΈΠ»ΠΎ Π‘ΡΠ²ΠΈΠ΄ΠΆΠ° (ΠΏΡΠ°Π²ΠΈΠ»ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΡΠΈΡΠΊΠ°). ΠΠ°Π½Π½ΠΎΠΌΡ ΠΏΡΠ°Π²ΠΈΠ»Ρ ΡΠ»Π΅Π΄ΡΠ΅Ρ ΡΠ΅Π»ΠΎΠ²Π΅ΠΊ, Π±ΠΎΡΡΠΈΠΉΡΡ ΡΠΈΡΠΊΠ°. ΠΡΠΈ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠΈ ΡΡΠΎΠ³ΠΎ ΠΏΡΠ°Π²ΠΈΠ»Π° Π°Π½Π°Π»ΠΈΠ·ΠΈΡΡΠ΅ΡΡΡ ΠΌΠ°ΡΡΠΈΡΠ° ΡΠΈΡΠΊΠΎΠ² R = (rij). Π Π°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Ρ i-Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅, Π±ΡΠ΄Π΅ΠΌ ΠΏΠΎΠ»Π°Π³Π°ΡΡ, ΡΡΠΎ Π½Π° ΡΠ°ΠΌΠΎΠΌ Π΄Π΅Π»Π΅ ΡΠΊΠ»Π°Π΄ΡΠ²Π°Π΅ΡΡΡ ΡΠΈΡΡΠ°ΡΠΈΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΡΠΈΡΠΊΠ° bi = max rij. ΠΠΎ ΡΠ΅ΠΏΠ΅ΡΡ ΡΠΆΠ΅ Π²ΡΠ±Π΅ΡΠ΅ΠΌ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ i0 Ρ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΠΌ bi0. ΠΡΠ°ΠΊ, ΠΏΡΠ°Π²ΠΈΠ»ΠΎ Π‘ΡΠ²ΠΈΠ΄ΠΆΠ° ΡΠ΅ΠΊΠΎΠΌΠ΅Π½Π΄ΡΠ΅Ρ ΠΏΡΠΈΠ½ΡΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ i0 ΡΠ°ΠΊΠΎΠ΅, ΡΡΠΎ bi0 = min bi = min (max rij). Π’Π°ΠΊ, Π² Π²ΡΡΠ΅ΡΠΊΠ°Π·Π°Π½Π½ΠΎΠΌ ΠΏΡΠΈΠΌΠ΅ΡΠ΅ ΠΈΠΌΠ΅Π΅ΠΌ b1 = 30, b2 =10, b3 = 5, b4 = 22. Π’Π΅ΠΏΠ΅ΡΡ ΠΈΠ· ΡΠΈΡΠ΅Π» 30, 10, 5, 22 Π½Π°Ρ ΠΎΠ΄ΠΈΠΌ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅. ΠΡΠΎ — 5. ΠΠ½Π°ΡΠΈΡ, ΠΏΡΠ°Π²ΠΈΠ»ΠΎ Π‘ΡΠ²ΠΈΠ΄ΠΆΠ° ΡΠ΅ΠΊΠΎΠΌΠ΅Π½Π΄ΡΠ΅Ρ ΠΏΡΠΈΠ½ΡΡΡ 3-Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅. ΠΡΠ°Π²ΠΈΠ»ΠΎ «ΡΠΎΠ·ΠΎΠ²ΠΎΠ³ΠΎ ΠΎΠΏΡΠΈΠΌΠΈΠ·ΠΌΠ°». ΠΠΠ ΡΡΠΈΡΠ°Π΅Ρ, ΡΡΠΎ Π΄Π»Ρ Π½Π΅Π³ΠΎ ΡΠ»ΠΎΠΆΠΈΡΡΡ ΡΠ°ΠΌΠ°Ρ Π±Π»Π°Π³ΠΎΠΏΡΠΈΡΡΠ½Π°Ρ ΡΠΈΡΡΠ°ΡΠΈΡ, Ρ. Π΅. ΠΎΠ½ ΠΏΠΎΠ»ΡΡΠΈΡ ΡΠ°ΠΌΡΠΉ Π±ΠΎΠ»ΡΡΠΎΠΉ Π΄ΠΎΡ ΠΎΠ΄ Π² ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ΅ ΡΠ²ΠΎΠ΅ΠΉ Π΄Π΅ΡΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ ci = max qij. Π’Π΅ΠΏΠ΅ΡΡ Π²ΡΠ±Π΅ΡΠ΅ΠΌ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ i0 Ρ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΠΌ ci0. ΠΡΠ°ΠΊ, ΠΏΡΠ°Π²ΠΈΠ»ΠΎ «ΡΠΎΠ·ΠΎΠ²ΠΎΠ³ΠΎ ΠΎΠΏΡΠΈΠΌΠΈΠ·ΠΌΠ° ΡΠ΅ΠΊΠΎΠΌΠ΅Π½Π΄ΡΠ΅Ρ ΠΏΡΠΈΠ½ΡΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ i0 ΡΠ°ΠΊΠΎΠ΅, ΡΡΠΎ ci0 = max (max qij). Π’Π°ΠΊ, Π² Π²ΡΡΠ΅ΡΠΊΠ°Π·Π°Π½Π½ΠΎΠΌ ΠΏΡΠΈΠΌΠ΅ΡΠ΅ ΠΈΠΌΠ΅Π΅ΠΌ Ρ1 = 6, Ρ2 = 22, Ρ3 = 32, Ρ4 = 10. Π’Π΅ΠΏΠ΅ΡΡ ΠΈΠ· ΡΠΈΡΠ΅Π» 6, 22, 32, 10 Π±Π΅ΡΠ΅ΠΌ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅. ΠΡΠΎ — 32. ΠΠ½Π°ΡΠΈΡ, ΠΏΡΠ°Π²ΠΈΠ»ΠΎ «ΡΠΎΠ·ΠΎΠ²ΠΎΠ³ΠΎ ΠΎΠΏΡΠΈΠΌΠΈΠ·ΠΌΠ°» ΡΠ΅ΠΊΠΎΠΌΠ΅Π½Π΄ΡΠ΅Ρ 3-Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅. ΠΡΠ°Π²ΠΈΠ»ΠΎ ΠΡΡΠ²ΠΈΡΠ° (Π²Π·Π²Π΅ΡΠΈΠ²Π°ΡΡΠ΅Π΅ ΠΏΠ΅ΡΡΠΈΠΌΠΈΡΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΈ ΠΎΠΏΡΠΈΠΌΠΈΡΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΏΠΎΠ΄Ρ ΠΎΠ΄Ρ ΠΊ ΡΠΈΡΡΠ°ΡΠΈΠΈ). ΠΡΠΈΠ½ΠΈΠΌΠ°Π΅ΡΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ i, Π½Π° ΠΊΠΎΡΠΎΡΠΎΠΌ min qΠ΄ΠΎΡΡΠΈΠ³Π°Π΅ΡΡΡ ΠΌΠ°ΠΊΡΠΈΠΌΡΠΌ ij max q+ (1 — ijΠ³Π΄Π΅ Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ ΠΈΠ· ΡΡΠ±ΡΠ΅ΠΊΡΠΈΠ²Π½ΡΡ ΡΠΎΠΎΠ±ΡΠ°ΠΆΠ΅Π½ΠΈΠΉ. ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅ 0 ΠΏΡΠΈΠ±Π»ΠΈΠΆΠ°Π΅ΡΡΡ ΠΊ Π΅Π΄ΠΈΠ½ΠΈΡΠ΅, ΡΠΎ ΠΏΡΠ°Π²ΠΈΠ»ΠΎ ΠΡΡΠ²ΠΈΡΠ° ΠΏΡΠΈΠ±Π»ΠΈΠΆΠ°Π΅ΡΡΡ ΠΊ ΠΏΡΠ°Π²ΠΈΠ»ΡΠΡΠ»ΠΈ ΠΊ Π½ΡΠ»Ρ ΠΏΡΠ°Π²ΠΈΠ»ΠΎ ΠΡΡΠ²ΠΈΡΠ° ΠΏΡΠΈΠ±Π»ΠΈΠΆΠ°Π΅ΡΡΡ ΠΊ ΠΏΡΠ°Π²ΠΈΠ»ΡΠΠ°Π»ΡΠ΄Π°, ΠΏΡΠΈ ΠΏΡΠΈΠ±Π»ΠΈΠΆΠ΅Π½ΠΈΠΈ «ΡΠΎΠ·ΠΎΠ²ΠΎΠ³ΠΎ ΠΎΠΏΡΠΈΠΌΠΈΠ·ΠΌΠ°». = ½.ΠΠΎΠ·ΡΠΌΠ΅ΠΌ i1 = Π * 6 + (1- Π ) * 0 = 3 i2 = Π * 22 + (1 — Π ) * 2 = 12 i3 = Π * 32 + (1 — Π ) * 3 = 17.5 i4 = Π * 10 + (1 — Π ) * (-12) = -1 ΠΡΠ°ΠΊ, ΠΌΡ ΠΈΠΌΠ΅Π΅ΠΌ i1 = 3, i2 = 12, i3 = 17.5, i4 = -1. Π’Π΅ΠΏΠ΅ΡΡ ΠΈΠ· ΡΠΈΡΠ΅Π» 3, 12, 17.5, -1 Π±Π΅ΡΠ΅ΠΌ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅. ΠΡΠΎ — 17.5. ΠΠ½Π°ΡΠΈΡ, ΠΏΡΠ°Π²ΠΈΠ»ΠΎ ΠΡΡΠ²ΠΈΡΠ° ΡΠ΅ΠΊΠΎΠΌΠ΅Π½Π΄ΡΠ΅Ρ 3-Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅.