ΠΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ°
Π Π΅ΡΠ΅Π½ΠΈΠ΅ Π±ΡΠ΄Π΅ΠΌ Π²Π΅ΡΡΠΈ Π² ΡΠΎΡΠΌΠ΅ ΡΠΈΠΌΠΏΠ»Π΅ΠΊΡ-ΡΠ°Π±Π»ΠΈΡ. ΠΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠ΅ Π·Π°ΡΡΠ°ΡΡ Π½Π° ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΡ ΡΠΎΡΡΠ°Π²ΡΡ: ΠΡΠ΅ΠΌΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΡΠΈΠΊΠ»Π°: 6+8+5+6+4=29 Π΅Π΄. Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ. ΠΠ΅ΡΠ΅ΠΉΠ΄Π΅ΠΌ ΠΎΡ Π½Π΅ΡΠ°Π²Π΅Π½ΡΡΠ² ΠΊ ΡΠ°Π²Π΅Π½ΡΡΠ²Π°ΠΌ: 1+210*5+180*2+140*7+10*4+110*8+90*0+270*2=4 060 Π΄Π΅Π½. Π΅Π΄. Π’ΠΎΠ³Π΄Π° ΡΡΠ½ΠΊΡΠΈΡ ΠΏΡΠΈΠ±ΡΠ»ΠΈ ΠΏΡΠΈΠΌΠ΅Ρ Π²ΠΈΠ΄: F (Ρ )=8Π₯1+6Π₯2+7Π₯3+9Π₯4>max. Π ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠΌ Π²ΠΈΠ΄Π΅: Π₯1+Ρ 2+2×3+3×4+Ρ 7=1500. Π Π°ΡΡ ΠΎΠ΄ ΡΡΡΡΡ. ΠΠ°ΠΏΠ°ΡΡ ΡΡΡΡΡ. Π₯1+Ρ 2+2×3+3×4?1500. ΠΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»ΠΈ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ° (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΠΠΠΠ§Π № 1
ΠΡΠ΅Π΄ΠΏΡΠΈΡΡΠΈΠ΅ Π²ΡΠΏΡΡΠΊΠ°Π΅Ρ ΡΠ΅ΡΡΡΠ΅ Π²ΠΈΠ΄Π° ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ Π1, Π2, Π3, Π4, ΠΏΡΠΈ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½Π½ΡΡ Π·Π°ΠΏΠ°ΡΠ°Ρ ΡΡΡΡΡ Π‘1, Π‘2, Π‘3, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΡΡ Π΄Π»Ρ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π° ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ. ΠΠ·Π²Π΅ΡΡΠ½Π° ΠΏΡΠΈΠ±ΡΠ»Ρ, ΠΏΠΎΠ»ΡΡΠ°Π΅ΠΌΠ°Ρ ΠΎΡ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π²ΠΈΠ΄Π° ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ. Π’ΡΠ΅Π±ΡΠ΅ΡΡΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ ΠΎΠ±ΡΠ΅ΠΌΡ Π²ΡΠΏΡΡΠΊΠ° ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π²ΠΈΠ΄Π° ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠ°Ρ ΠΏΡΠ΅Π΄ΠΏΡΠΈΡΡΠΈΡ ΠΏΠΎΠ»ΡΡΠ΅Π½ΠΈΠ΅ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠ΅ΠΉ ΠΏΡΠΈΠ±ΡΠ»ΠΈ ΠΏΡΠΈ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ.
Π Π°ΡΡ ΠΎΠ΄ ΡΡΡΡΡ Π½Π° ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²ΠΎ Π΅Π΄ΠΈΠ½ΠΈΡΡ ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ, Π·Π°ΠΏΠ°ΡΡ ΡΡΡΡΡ ΠΈ ΠΏΡΠΈΠ±ΡΠ»Ρ, ΠΏΠΎΠ»ΡΡΠ°Π΅ΠΌΠ°Ρ ΠΎΡ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ Π΅Π΄ΠΈΠ½ΠΈΡΡ ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ, ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½Ρ Π² ΡΠ°Π±Π»ΠΈΡΠ΅.
ΠΠΈΠ΄Ρ ΡΡΡΡΡ | Π Π°ΡΡ ΠΎΠ΄ ΡΡΡΡΡ | ΠΠ°ΠΏΠ°ΡΡ ΡΡΡΡΡ | ||||
Π1 | Π2 | Π3 | Π4 | |||
Π‘1 | ||||||
Π‘2 | ||||||
Π‘3 | ||||||
ΠΡΠΈΠ±ΡΠ»Ρ | —; | |||||
Π Π΅ΡΠ΅Π½ΠΈΠ΅ ΠΡΡΡΡ Π₯1, Π₯2, Π₯3, Π₯4 — ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π΅Π΄ΠΈΠ½ΠΈΡ Π²ΡΠΏΡΡΠΊΠ°Π΅ΠΌΠΎΠΉ ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ Π1, Π2, Π3, Π4 ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΠΎ.
Π’ΠΎΠ³Π΄Π° ΡΡΠ½ΠΊΡΠΈΡ ΠΏΡΠΈΠ±ΡΠ»ΠΈ ΠΏΡΠΈΠΌΠ΅Ρ Π²ΠΈΠ΄:
F (Ρ )=8Π₯1+6Π₯2+7Π₯3+9Π₯4>max
ΠΠ°ΠΏΠΈΡΠ΅ΠΌ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΡ ΠΏΠΎ ΡΠ°ΡΡ ΠΎΠ΄Ρ ΡΡΡΡΡ Π² Π²ΠΈΠ΄Π΅ ΡΠΈΡΡΠ΅ΠΌΡ Π½Π΅ΡΠ°Π²Π΅Π½ΡΡΠ²:
2Π₯1+Π₯3+2Π₯4?800
Π₯1+2Π₯2+3Π₯4?900
2Π₯1+Π₯2+2Π₯3+3Π₯4?1500
Π₯1,2,3?0
ΠΠ΅ΡΠ΅ΠΉΠ΄Π΅ΠΌ ΠΎΡ Π½Π΅ΡΠ°Π²Π΅Π½ΡΡΠ² ΠΊ ΡΠ°Π²Π΅Π½ΡΡΠ²Π°ΠΌ:
2Π₯1+Π₯3+2Π₯4+Π₯5=800
Π₯1+2Π₯2+3Π₯4+Π₯6=900
2Π₯1+Π₯2+2Π₯3+3Π₯4+Π₯7=1500
Π Π΅ΡΠ΅Π½ΠΈΠ΅ Π±ΡΠ΄Π΅ΠΌ Π²Π΅ΡΡΠΈ Π² ΡΠΎΡΠΌΠ΅ ΡΠΈΠΌΠΏΠ»Π΅ΠΊΡ-ΡΠ°Π±Π»ΠΈΡ.
β ΠΏ/ΠΏ | Π₯ Π±Π°Π· | Π₯1 | Π₯2 | Π₯3 | Π₯4 | Π₯5 | Π₯6 | Π₯7 | Πi | Πi/ Π°iΠΊ | |
Π₯5 | |||||||||||
Π₯6 | ; | ||||||||||
Π₯7 | |||||||||||
«0» | F (Ρ ) | — 8 | — 6 | -7 | — 9 | ||||||
Π₯5 | — 0,5 | 0,5 | — 0,5 | — 100 | |||||||
Π₯6 | |||||||||||
Π₯3 | 0,5 | 1,5 | 0,5 | ||||||||
«0» | F (Ρ ) | — 1 | -2,5 | 1,5 | 3,5 | ||||||
Π₯5 | 1,25 | 1,25 | 0,25 | — 0,5 | |||||||
Π₯2 | 0,5 | 1,5 | 0,5 | ||||||||
Π₯3 | 0,75 | 0,75 | — 0,25 | 0,5 | |||||||
«0» | F (Ρ ) | 0,25 | 5,25 | 1,25 | 3,5 | ||||||
ΠΠ°ΠΊ Π²ΠΈΠ΄ΠΈΠΌ, Π² ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅ΠΉ ΡΡΡΠΎΠΊΠ΅ Π²ΡΠ΅ ΡΠΈΡΠ»Π° ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½Ρ, ΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΠΉ ΠΏΠ»Π°Π½ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ.
ΠΠ»Ρ ΠΏΠΎΠ»ΡΡΠ΅Π½ΠΈΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ ΠΏΡΠΈΠ±ΡΠ»ΠΈ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π²ΡΠΏΡΡΠΊΠ°ΡΡ 450 Π΅Π΄. ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ Π2 ΠΈ 525 Π΅Π΄. ΠΏΡΠΎΠ΄ΡΠΊΡΠΈΠΈ Π3. ΠΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½Π°Ρ ΠΏΡΠΈΠ±ΡΠ»Ρ Π² ΡΡΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΡΠΎΡΡΠ°Π²ΠΈΡ 6375 Π΄Π΅Π½. Π΅Π΄.
ΠΠΠΠΠ§Π № 2
ΠΠΌΠ΅Π΅ΡΡΡ 4 ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠ° ΠΈ 4 ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ. ΠΠ·Π²Π΅ΡΡΠ½Ρ ΡΠ°ΡΠΈΡΡ Π½Π° ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΡ Π΅Π΄ΠΈΠ½ΠΈΡΡ Π³ΡΡΠ·Π° ΠΎΡ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠ° ΠΊ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ. ΠΠ°ΠΉΡΠΈ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΏΠ»Π°Π½ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΠΈ Π³ΡΡΠ·ΠΎΠ² ΠΎΡ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠΎΠ² ΠΊ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»ΡΠΌ, ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠΈΠ²Π°ΡΡΠΈΠΉ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠ΅ Π·Π°ΡΡΠ°ΡΡ.
ΠΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»ΠΈ | ||||||
ΠΠΎΡΡΠ°Π²ΡΠΈΠΊΠΈ | ||||||
Π’Π°ΠΊ ΠΊΠ°ΠΊ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π³ΡΡΠ·Π° Ρ ΠΏΠΎΡΡΠ°Π²ΡΠΈΠΊΠΎΠ² (1220) ΠΏΡΠ΅Π²ΡΡΠ°Π΅Ρ ΡΡΠ΅Π±ΡΠ΅ΠΌΠΎΠ΅ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»ΡΠΌΠΈ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π³ΡΡΠ·Π° (1130) Π½Π° 1220 — 1130=90 Π΅Π΄., ΡΠΎ Π²Π²Π΅Π΄Π΅ΠΌ ΡΠΈΠΊΡΠΈΠ²Π½ΠΎΠ³ΠΎ ΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»Ρ Ρ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎΠΌ Π³ΡΡΠ·Π° 90 Π΅Π΄. ΠΈ Π½ΡΠ»Π΅Π²ΡΠΌΠΈ ΡΠ°ΡΠΈΡΠ°ΠΌΠΈ Π½Π° ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΡ. ΠΠ΅ΡΠ²ΠΎΠ½Π°ΡΠ°Π»ΡΠ½ΡΠΉ ΠΎΠΏΠΎΡΠ½ΡΠΉ ΠΏΠ»Π°Π½ ΡΠΎΡΡΠ°Π²ΠΈΠΌ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π΄Π²ΠΎΠΉΠ½ΠΎΠ³ΠΎ ΠΏΡΠ΅Π΄ΠΏΠΎΡΡΠ΅Π½ΠΈΡ, Π΄Π°Π»Π΅Π΅ Π±ΡΠ΄Π΅ΠΌ Π΅Π³ΠΎ ΡΠ»ΡΡΡΠ°ΡΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ². Π ΠΏΡΠ°Π²ΠΎΠΌ Π²Π΅ΡΡ Π½Π΅ΠΌ ΡΠ³Π»Ρ ΡΠΊΠ°Π·Π°Π½Ρ ΡΠ°ΡΠΈΡΡ Π½Π° ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΡ, Π² Π»Π΅Π²ΠΎΠΌ Π²Π΅ΡΡ Π½Π΅ΠΌ ΡΠ³Π»Ρ — ΡΡΠΌΠΌΠ° ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ², Π²Π½ΠΈΠ·Ρ ΠΏΠΎ ΡΠ΅Π½ΡΡΡ — ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΈΠΌΠΎΠ³ΠΎ Π³ΡΡΠ·Π°.
Ui | |||||||
4 5 | 1 8 | 1 1 | 5 5 | — 3 0 | |||
2 2 | — 1 6 | — 1 5 | 3 7 | — 5 0 | — 2 | ||
7 7 | 4 4 | 4 9 | 8 8 | 0 0 | |||
5 6 | 2 2 | 2 7 | 6 9 | — 2 0 | |||
Vj | — 3 | ||||||
Π ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΠΎΠΌ ΠΏΠ»Π°Π½Π΅ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ Π΄Π»Ρ Π²ΡΠ΅Ρ ΡΡΠ΅Π΅ΠΊ ΡΡΠΌΠΌΠ° ΠΏΠΎΡΠ΅Π½ΡΠΈΠ°Π»ΠΎΠ² (Ui+ Vj) Π½Π΅ ΠΏΡΠ΅Π²ΡΡΠ°Π΅Ρ ΡΠ°ΡΠΈΡΡ. Π‘Π»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ ΡΡΠΎΡ ΠΏΠ»Π°Π½ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΎΠΊ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ ΠΈ Π΅Π³ΠΎ Π½Π΅Π»ΡΠ·Ρ ΡΠ»ΡΡΡΠΈΡΡ.
ΠΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠ΅ Π·Π°ΡΡΠ°ΡΡ Π½Π° ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΡ ΡΠΎΡΡΠ°Π²ΡΡ:
210*1+210*5+180*2+140*7+10*4+110*8+90*0+270*2=4 060 Π΄Π΅Π½. Π΅Π΄.
ΠΠΠΠΠ§Π № 3
Π’ΡΠ΅Π±ΡΠ΅ΡΡΡ ΡΠ°ΡΡΡΠ°Π²ΠΈΡΡ 5 ΡΠ°Π±ΠΎΡΠΈΡ ΠΏΠΎ ΡΠ΅Ρ Π½ΠΎΠ»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠ΅ΠΏΠΎΡΠΊΠ΅ ΡΠ°ΠΊ, ΡΡΠΎΠ±Ρ Π²ΡΠ΅ΠΌΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ Π²ΡΠ΅Π³ΠΎ ΡΠΈΠΊΠ»Π° ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ Π±ΡΠ»ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ. ΠΡΠ΅ΠΌΡ, Π·Π°ΡΡΠ°ΡΠΈΠ²Π°Π΅ΠΌΠΎΠ΅ ΠΊΠ°ΠΆΠ΄ΡΠΌ ΡΠ°Π±ΠΎΡΠΈΠΌ ΠΏΡΠΈ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠΈ Π»ΡΠ±ΠΎΠΉ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½ΠΎ Π² ΡΠ°Π±Π»ΠΈΡΠ΅.
1-Ρ | 2-Ρ | 3-Ρ | 4-Ρ | 5-Ρ | ||
1-ΠΉ | ||||||
2-ΠΉ | ||||||
3-ΠΉ | ||||||
4-ΠΉ | ||||||
5-ΠΉ | ||||||
Π Π΅ΡΠ΅Π½ΠΈΠ΅
1-Ρ | 2-Ρ | 3-Ρ | 4-Ρ | 5-Ρ | ||
1-ΠΉ | ||||||
2-ΠΉ | ||||||
3-ΠΉ | ||||||
4-ΠΉ | ||||||
5-ΠΉ | ||||||
qimin | ||||||
Zmin=4
1-Ρ | 2-Ρ | 3-Ρ | 4-Ρ | 5-Ρ | ||
1-ΠΉ | ||||||
2-ΠΉ | ||||||
3-ΠΉ | ||||||
4-ΠΉ | ||||||
5-ΠΉ | ||||||
qimin | ||||||
Zmin=1
1-Ρ | 2-Ρ | 3-Ρ | 4-Ρ | 5-Ρ | ||
1-ΠΉ | ||||||
2-ΠΉ | ||||||
3-ΠΉ | ||||||
4-ΠΉ | ||||||
5-ΠΉ | ||||||
qimin | ||||||
Zmin=1
1-Ρ | 2-Ρ | 3-Ρ | 4-Ρ | 5-Ρ | ||
1-ΠΉ | ||||||
2-ΠΉ | ||||||
3-ΠΉ | ||||||
4-ΠΉ | ||||||
5-ΠΉ | ||||||
qimin | ||||||
Π ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠΌ Π²ΠΈΠ΄Π΅:
ΠΈΠ»ΠΈ:
1-Ρ | 2-Ρ | 3-Ρ | 4-Ρ | 5-Ρ | ||
1-ΠΉ | ||||||
2-ΠΉ | ||||||
3-ΠΉ | ||||||
4-ΠΉ | ||||||
5-ΠΉ | ||||||
ΠΡΠ΅ΠΌΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΡΠΈΠΊΠ»Π°: 6+8+5+6+4=29 Π΅Π΄. Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ.