ΠΡΡΠ³ΠΈΠ΅ Π²ΠΈΠ΄Ρ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π΅Π½Π½ΡΡ ΡΡΠ½ΠΊΡΠΈΠΉ
ΠΠΎΡΡΡΠΈΡΠΈΠ΅Π½ΡΡ a ΠΈ b ΡΡΠ½ΠΊΡΠΈΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ Π½Π°Ρ ΠΎΠ΄ΡΡΡΡ ΠΏΡΠΈ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ L ΠΈ KΠΏΠΎΠΊΠ°Π·ΡΠ²Π°ΡΡ ΠΏΡΠΎΠΏΠΎΡΡΠΈΠΈ, Π² ΠΊΠΎΡΠΎΡΡΡ ΠΎΠ΄ΠΈΠ½ ΡΠ°ΠΊΡΠΎΡ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π·Π°ΠΌΠ΅ΡΡΠ½ Π΄ΡΡΠ³ΠΈΠΌ. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Π΅ΡΠ»ΠΈ a=b=1, ΡΠΎ ΡΡΠΎ Π·Π½Π°ΡΠΈΡ, ΡΡΠΎ 1 ΡΠ°Ρ ΡΡΡΠ΄Π° ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π·Π°ΠΌΠ΅Π½Π΅Π½ 1 ΡΠ°ΡΠΎΠΌ ΠΌΠ°ΡΠΈΠ½Π½ΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ Π΄Π»Ρ ΡΠΎΠ³ΠΎ, ΡΡΠΎΠ±Ρ ΠΏΡΠΎΠΈΠ·Π²Π΅ΡΡΠΈ ΡΠ°ΠΊΠΎΠΉ ΠΆΠ΅ ΠΎΠ±ΡΡΠΌ ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ. ΠΠ°Π½Π½Π°Ρ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π΅Π½Π½Π°Ρ ΡΡΠ½ΠΊΡΠΈΡ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΎΠ΄Π½ΠΎΡΠΎΠ΄Π½ΠΎΠΉ ΠΏΠ΅ΡΠ²ΠΎΠΉ ΡΡΠ΅ΠΏΠ΅Π½ΠΈ, ΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, ΠΎΠ½Π° ΠΈΠΌΠ΅Π΅Ρ ΠΏΠΎΡΡΠΎΡΠ½Π½ΡΡ ΠΎΡΠ΄Π°ΡΡ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΡΡΠ³ΠΈΠ΅ Π²ΠΈΠ΄Ρ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π΅Π½Π½ΡΡ ΡΡΠ½ΠΊΡΠΈΠΉ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΡΡΠ³ΠΈΠΌ Π²ΠΈΠ΄ΠΎΠΌ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π΅Π½Π½ΠΎΠΉ ΡΡΠ½ΠΊΡΠΈΠΈ ΡΠ²Π»ΡΠ΅ΡΡΡ Π»ΠΈΠ½Π΅ΠΉΠ½Π°Ρ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π΅Π½Π½Π°Ρ ΡΡΠ½ΠΊΡΠΈΡ, ΠΊΠΎΡΠΎΡΠ°Ρ ΠΈΠΌΠ΅Π΅Ρ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΉ Π²ΠΈΠ΄:
Q (L, K) = aL + bK.
ΠΠ°Π½Π½Π°Ρ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π΅Π½Π½Π°Ρ ΡΡΠ½ΠΊΡΠΈΡ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΎΠ΄Π½ΠΎΡΠΎΠ΄Π½ΠΎΠΉ ΠΏΠ΅ΡΠ²ΠΎΠΉ ΡΡΠ΅ΠΏΠ΅Π½ΠΈ, ΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, ΠΎΠ½Π° ΠΈΠΌΠ΅Π΅Ρ ΠΏΠΎΡΡΠΎΡΠ½Π½ΡΡ ΠΎΡΠ΄Π°ΡΡ ΠΎΡ ΠΌΠ°ΡΡΡΠ°Π±ΠΎΠ² ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π°. ΠΡΠ°ΡΠΈΡΠ΅ΡΠΊΠΈ Π΄Π°Π½Π½Π°Ρ ΡΡΠ½ΠΊΡΠΈΡ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½Π° Π½Π° ΡΠΈΡΡΠ½ΠΊΠ΅ 1.2, Π°.
ΠΠΊΠΎΠ½ΠΎΠΌΠΈΡΠ΅ΡΠΊΠΈΠΉ ΡΠΌΡΡΠ» Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠΉ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π΅Π½Π½ΠΎΠΉ ΡΡΠ½ΠΊΡΠΈΠΈ ΡΠΎΡΡΠΎΠΈΡ Π² ΡΠΎΠΌ, ΡΡΠΎ ΠΎΠ½Π° ΠΎΠΏΠΈΡΡΠ²Π°Π΅Ρ ΡΠ°ΠΊΠΎΠ΅ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²ΠΎ, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ ΡΠ°ΠΊΡΠΎΡΡ ΡΠ²Π»ΡΡΡΡΡ Π²Π·Π°ΠΈΠΌΠΎΠ·Π°ΠΌΠ΅Π½ΡΠ΅ΠΌΡΠΌΠΈ, ΡΠΎ Π΅ΡΡΡ, Π½Π΅ ΠΈΠΌΠ΅Π΅Ρ Π·Π½Π°ΡΠ΅Π½ΠΈΡ — ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΡΡΡΠ΄ ΠΈΠ»ΠΈ ΡΠΎΠ»ΡΠΊΠΎ ΠΊΠ°ΠΏΠΈΡΠ°Π». ΠΠΎ Π² ΡΠ΅Π°Π»ΡΠ½ΠΎΠΉ ΠΆΠΈΠ·Π½ΠΈ ΡΠ°ΠΊΠ°Ρ ΡΠΈΡΡΠ°ΡΠΈΡ ΠΏΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΈ Π½Π΅ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Π°, ΡΠ°ΠΊ ΠΊΠ°ΠΊ Π»ΡΠ±Π°Ρ ΠΌΠ°ΡΠΈΠ½Π° Π²ΡΠ΅ ΡΠ°Π²Π½ΠΎ ΠΎΠ±ΡΠ»ΡΠΆΠΈΠ²Π°Π΅ΡΡΡ ΡΠ΅Π»ΠΎΠ²Π΅ΠΊΠΎΠΌ.
ΠΠΎΡΡΡΠΈΡΠΈΠ΅Π½ΡΡ a ΠΈ b ΡΡΠ½ΠΊΡΠΈΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ Π½Π°Ρ ΠΎΠ΄ΡΡΡΡ ΠΏΡΠΈ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ L ΠΈ KΠΏΠΎΠΊΠ°Π·ΡΠ²Π°ΡΡ ΠΏΡΠΎΠΏΠΎΡΡΠΈΠΈ, Π² ΠΊΠΎΡΠΎΡΡΡ ΠΎΠ΄ΠΈΠ½ ΡΠ°ΠΊΡΠΎΡ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π·Π°ΠΌΠ΅ΡΡΠ½ Π΄ΡΡΠ³ΠΈΠΌ. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Π΅ΡΠ»ΠΈ a=b=1, ΡΠΎ ΡΡΠΎ Π·Π½Π°ΡΠΈΡ, ΡΡΠΎ 1 ΡΠ°Ρ ΡΡΡΠ΄Π° ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π·Π°ΠΌΠ΅Π½Π΅Π½ 1 ΡΠ°ΡΠΎΠΌ ΠΌΠ°ΡΠΈΠ½Π½ΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ Π΄Π»Ρ ΡΠΎΠ³ΠΎ, ΡΡΠΎΠ±Ρ ΠΏΡΠΎΠΈΠ·Π²Π΅ΡΡΠΈ ΡΠ°ΠΊΠΎΠΉ ΠΆΠ΅ ΠΎΠ±ΡΡΠΌ ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ.
ΠΠ΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΡΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ Π² Π½Π΅ΠΊΠΎΡΠΎΡΡΡ Π²ΠΈΠ΄Π°Ρ Ρ ΠΎΠ·ΡΠΉΡΡΠ²Π΅Π½Π½ΠΎΠΉ Π΄Π΅ΡΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ ΡΡΡΠ΄ ΠΈ ΠΊΠ°ΠΏΠΈΡΠ°Π» Π²ΠΎΠΎΠ±ΡΠ΅ Π½Π΅ ΠΌΠΎΠ³ΡΡ Π·Π°ΠΌΠ΅Π½ΠΈΡΡ Π΄ΡΡΠ³ Π΄ΡΡΠ³Π° ΠΈ Π΄ΠΎΠ»ΠΆΠ½Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ Π² ΡΠΈΠΊΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΉ ΠΏΡΠΎΠΏΠΎΡΡΠΈΠΈ: 1 ΡΠ°Π±ΠΎΡΠΈΠΉ — 2 ΡΡΠ°Π½ΠΊΠ°, 1 Π°Π²ΡΠΎΠ±ΡΡ — 1 Π²ΠΎΠ΄ΠΈΡΠ΅Π»Ρ. Π ΡΡΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΡΠ»Π°ΡΡΠΈΡΠ½ΠΎΡΡΡ Π·Π°ΠΌΠ΅ΡΠ΅Π½ΠΈΡ ΡΠ°ΠΊΡΠΎΡΠΎΠ² ΡΠ°Π²Π½Π° Π½ΡΠ»Ρ, Π° ΡΠ΅Ρ Π½ΠΎΠ»ΠΎΠ³ΠΈΡ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π° ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ°Π΅ΡΡΡ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π΅Π½Π½ΠΎΠΉ ΡΡΠ½ΠΊΡΠΈΠ΅ΠΉ ΠΠ΅ΠΎΠ½ΡΡΠ΅Π²Π°:
Q (L, K) = min{; },.
ΠΠ΅Π»ΠΈΡΠΈΠ½Π°. | ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅. |
Q. | ΠΠ±ΡΡΠΌ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π° ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ. |
a, b. | Π’Π΅Ρ Π½ΠΎΠ»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΈ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΡΠΉ ΡΠ°ΡΡ ΠΎΠ΄ ΡΠ°ΠΊΡΠΎΡΠΎΠ² ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π° Π½Π° Π΅Π΄ΠΈΠ½ΠΈΡΡ ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ. |
min{x; y}. | ΠΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΠΌΠΈ x ΠΈ y |
ΠΡΠ»ΠΈ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ Π°Π²ΡΠΎΠ±ΡΡΠ΅ Π΄Π°Π»ΡΠ½Π΅Π³ΠΎ ΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΡ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±ΡΡΡ Π΄Π²Π° Π²ΠΎΠ΄ΠΈΡΠ΅Π»Ρ, ΡΠΎ ΠΏΡΠΈ Π½Π°Π»ΠΈΡΠΈΠΈ Π² Π°Π²ΡΠΎΠ±ΡΡΠ½ΠΎΠΌ ΠΏΠ°ΡΠΊΠ΅ 50 Π°Π²ΡΠΎΠ±ΡΡΠΎΠ² ΠΈ 90 Π²ΠΎΠ΄ΠΈΡΠ΅Π»Π΅ΠΉ ΠΎΠ΄Π½ΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎ ΠΌΠΎΠ³ΡΡ ΠΎΠ±ΡΠ»ΡΠΆΠΈΠ²Π°ΡΡΡΡ ΡΠΎΠ»ΡΠΊΠΎ 45 ΠΌΠ°ΡΡΡΡΡΠΎΠ²:
min{90/2; 50/1} = 45.