ΠŸΠΎΠΌΠΎΡ‰ΡŒ Π² написании студСнчСских Ρ€Π°Π±ΠΎΡ‚
АнтистрСссовый сСрвис

ΠœΠ΅Ρ‚ΠΎΠ΄Ρ‹ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ основных Π²ΠΈΠ΄ΠΎΠ² Π·Π°Π΄Π°Ρ‡ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ программирования

Π Π΅Ρ„Π΅Ρ€Π°Ρ‚ΠŸΠΎΠΌΠΎΡ‰ΡŒ Π² Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΠΈΠ£Π·Π½Π°Ρ‚ΡŒ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒΠΌΠΎΠ΅ΠΉ Ρ€Π°Π±ΠΎΡ‚Ρ‹

Рассмотрим постановку Π·Π°Π΄Π°Ρ‡ΠΈ ΠΎ Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠ΅ΠΌ использовании рСсурсов. ΠŸΡƒΡΡ‚ΡŒ нСкоторая производствСнная Π΅Π΄ΠΈΠ½ΠΈΡ†Π° (Ρ†Π΅Ρ…, Π·Π°Π²ΠΎΠ΄, объСдинСниС ΠΈ Ρ‚. Π΄.), исходя ΠΈΠ· ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΡƒΡ€Ρ‹ Ρ€Ρ‹Π½ΠΊΠ°, тСхничСских ΠΈΠ»ΠΈ тСхнологичСских возмоТностСй ΠΈ ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΡ…ся рСсурсов, ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ‹ΠΏΡƒΡΠΊΠ°Ρ‚ΡŒ n Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… Π²ΠΈΠ΄ΠΎΠ² ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ†ΠΈΠΈ (Ρ‚ΠΎΠ²Π°Ρ€ΠΎΠ²), извСстных ΠΏΠΎΠ΄ Π½ΠΎΠΌΠ΅Ρ€Π°ΠΌΠΈ, ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°Π΅ΠΌΡ‹ΠΌΠΈ индСксом j. Π’ΠΎΠ²Π°Ρ€Ρ‹ Π±ΡƒΠ΄Π΅ΠΌ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°Ρ‚ΡŒ. ΠŸΡ€Π΅Π΄ΠΏΡ€ΠΈΡΡ‚ΠΈΠ΅ ΠΏΡ€ΠΈ производствС… Π§ΠΈΡ‚Π°Ρ‚ΡŒ Π΅Ρ‰Ρ‘ >

ΠœΠ΅Ρ‚ΠΎΠ΄Ρ‹ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ основных Π²ΠΈΠ΄ΠΎΠ² Π·Π°Π΄Π°Ρ‡ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ программирования (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚, курсовая, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ)

ОсобСнно ΡˆΠΈΡ€ΠΎΠΊΠΎΠ΅ ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ ΠΈ ΠΌΠΎΠ΄Π΅Π»ΠΈ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ программирования ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠ»ΠΈ ΠΏΡ€ΠΈ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΈ Π·Π°Π΄Π°Ρ‡ экономии рСсурсов (Π²Ρ‹Π±ΠΎΡ€ Ρ€Π΅ΡΡƒΡ€ΡΠΎΡΠ±Π΅Ρ€Π΅Π³Π°ΡŽΡ‰ΠΈΡ… Ρ‚Π΅Ρ…Π½ΠΎΠ»ΠΎΠ³ΠΈΠΉ, составлСниС смСсСй, раскрой ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»ΠΎΠ², производствСнно-транспортных ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΡ… Π·Π°Π΄Π°Ρ‡). [8, c.92].

Рассмотрим постановку Π·Π°Π΄Π°Ρ‡ΠΈ ΠΎ Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠ΅ΠΌ использовании рСсурсов. ΠŸΡƒΡΡ‚ΡŒ нСкоторая производствСнная Π΅Π΄ΠΈΠ½ΠΈΡ†Π° (Ρ†Π΅Ρ…, Π·Π°Π²ΠΎΠ΄, объСдинСниС ΠΈ Ρ‚. Π΄.), исходя ΠΈΠ· ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΡƒΡ€Ρ‹ Ρ€Ρ‹Π½ΠΊΠ°, тСхничСских ΠΈΠ»ΠΈ тСхнологичСских возмоТностСй ΠΈ ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΡ…ся рСсурсов, ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ‹ΠΏΡƒΡΠΊΠ°Ρ‚ΡŒ n Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… Π²ΠΈΠ΄ΠΎΠ² ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ†ΠΈΠΈ (Ρ‚ΠΎΠ²Π°Ρ€ΠΎΠ²), извСстных ΠΏΠΎΠ΄ Π½ΠΎΠΌΠ΅Ρ€Π°ΠΌΠΈ, ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°Π΅ΠΌΡ‹ΠΌΠΈ индСксом j. Π’ΠΎΠ²Π°Ρ€Ρ‹ Π±ΡƒΠ΄Π΅ΠΌ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°Ρ‚ΡŒ . ΠŸΡ€Π΅Π΄ΠΏΡ€ΠΈΡΡ‚ΠΈΠ΅ ΠΏΡ€ΠΈ производствС этих Π²ΠΈΠ΄ΠΎΠ² ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ†ΠΈΠΈ Π΄ΠΎΠ»ΠΆΠ½ΠΎ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡ΠΈΠ²Π°Ρ‚ΡŒΡΡ ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΠΌΠΈΡΡ Π²ΠΈΠ΄Π°ΠΌΠΈ рСсурсов, Ρ‚Π΅Ρ…Π½ΠΎΠ»ΠΎΠ³ΠΈΠΉ, Π΄Ρ€ΡƒΠ³ΠΈΡ… производствСнных Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΎΠ² (ΡΡ‹Ρ€ΡŒΡ, ΠΏΠΎΠ»ΡƒΡ„Π°Π±Ρ€ΠΈΠΊΠ°Ρ‚ΠΎΠ², Ρ€Π°Π±ΠΎΡ‡Π΅ΠΉ силы, оборудования, элСктроэнСргии ΠΈ Ρ‚. Π΄.). ВсС эти Π²ΠΈΠ΄Ρ‹ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡ΠΈΠ²Π°ΡŽΡ‰ΠΈΡ… Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΎΠ² Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ ΠΈΠ½Π³Ρ€Π΅Π΄ΠΈΠ΅Π½Ρ‚Π°ΠΌΠΈ. ΠŸΡƒΡΡ‚ΡŒ ΠΈΡ… Ρ‡ΠΈΡΠ»ΠΎ Ρ€Π°Π²Π½ΠΎ m; ΠΏΡ€ΠΈΠΏΠΈΡˆΠ΅ΠΌ ΠΈΠΌ ΠΈΠ½Π΄Π΅ΠΊΡ i. Они ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½Ρ‹, ΠΈ ΠΈΡ… ΠΊΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²Π° Ρ€Π°Π²Π½Ρ‹ соотвСтствСнно условных Π΅Π΄ΠΈΠ½ΠΈΡ†. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, — Π²Π΅ΠΊΡ‚ΠΎΡ€ рСсурсов. Π˜Π·Π²Π΅ΡΡ‚Π½Π° экономичСская Π²Ρ‹Π³ΠΎΠ΄Π° (ΠΌΠ΅Ρ€Π° полСзности) производства ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ†ΠΈΠΈ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π²ΠΈΠ΄Π°, исчисляСмая, скаТСм, ΠΏΠΎ ΠΎΡ‚пускной Ρ†Π΅Π½Π΅ Ρ‚ΠΎΠ²Π°Ρ€Π°, Π΅Π³ΠΎ ΠΏΡ€ΠΈΠ±Ρ‹Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ, ΠΈΠ·Π΄Π΅Ρ€ΠΆΠΊΠ°ΠΌ производства, стСпСни удовлСтворСния потрСбностСй ΠΈ Ρ‚. Π΄. ΠŸΡ€ΠΈΠΌΠ΅ΠΌ Π² ΠΊΠ°Ρ‡Π΅ΡΡ‚Π²Π΅ Ρ‚Π°ΠΊΠΎΠΉ ΠΌΠ΅Ρ€Ρ‹, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, Ρ†Π΅Π½Ρƒ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ, Ρ‚. Π΅. — Π²Π΅ΠΊΡ‚ΠΎΡ€ Ρ†Π΅Π½. Π˜Π·Π²Π΅ΡΡ‚Π½Ρ‹ Ρ‚Π°ΠΊΠΆΠ΅ тСхнологичСскиС коэффициСнты, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΡƒΠΊΠ°Π·Ρ‹Π²Π°ΡŽΡ‚, сколько Π΅Π΄ΠΈΠ½ΠΈΡ† i-Π³ΠΎ рСсурса трСбуСтся для производства Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹ ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ†ΠΈΠΈ j-Π³ΠΎ Π²ΠΈΠ΄Π°. ΠœΠ°Ρ‚Ρ€ΠΈΡ†Ρƒ коэффициСнтов Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ тСхнологичСской ΠΈ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ Π±ΡƒΠΊΠ²ΠΎΠΉ А. ИмССм. ΠžΠ±ΠΎΠ·Π½Π°Ρ‡ΠΈΠΌ Ρ‡Π΅Ρ€Π΅Π· ΠΏΠ»Π°Π½ производства, ΠΏΠΎΠΊΠ°Π·Ρ‹Π²Π°ΡŽΡ‰ΠΈΠΉ, ΠΊΠ°ΠΊΠΈΠ΅ Π²ΠΈΠ΄Ρ‹ Ρ‚ΠΎΠ²Π°Ρ€ΠΎΠ² Π½ΡƒΠΆΠ½ΠΎ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚ΡŒ ΠΈ Π² ΠΊΠ°ΠΊΠΈΡ… количСствах, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΎΠ±Π΅ΡΠΏΠ΅Ρ‡ΠΈΡ‚ΡŒ ΠΏΡ€Π΅Π΄ΠΏΡ€ΠΈΡΡ‚ΠΈΡŽ максимум объСма Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ ΠΏΡ€ΠΈ ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΡ…ΡΡ рСсурсах. Π’Π°ΠΊ ΠΊΠ°ΠΊ — Ρ†Π΅Π½Π° Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹ j-ΠΉ ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ†ΠΈΠΈ, Ρ†Π΅Π½Π° Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½Π½Ρ‹Ρ… Π΅Π΄ΠΈΠ½ΠΈΡ† Π±ΡƒΠ΄Π΅Ρ‚ Ρ€Π°Π²Π½Π°, Π° ΠΎΠ±Ρ‰ΠΈΠΉ объСм Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ ΠΏΡ€ΠΈΠΌΠ΅Ρ‚ Π²ΠΈΠ΄ (Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° 2.1). Π­Ρ‚ΠΎ — цСлСвая функция, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ Π½ΡƒΠΆΠ½ΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ.

(1.11).

Π’Π°ΠΊ ΠΊΠ°ΠΊ — расход i-Π³ΠΎ рСсурса Π½Π° ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡ‚Π²ΠΎ Π΅Π΄ΠΈΠ½ΠΈΡ† j-ΠΉ ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ†ΠΈΠΈ, Ρ‚ΠΎ, просуммировав расход i-Π³ΠΎ рСсурса Π½Π° Π²Ρ‹ΠΏΡƒΡΠΊ всСх n Π²ΠΈΠ΄ΠΎΠ² ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ†ΠΈΠΈ, ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ ΠΎΠ±Ρ‰ΠΈΠΉ расход этого рСсурса, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π½Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΏΡ€Π΅Π²ΠΎΡΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ Π΅Π΄ΠΈΠ½ΠΈΡ† (Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° 1.12).

(1.12).

Π§Ρ‚ΠΎΠ±Ρ‹ искомый ΠΏΠ»Π°Π½ Π±Ρ‹Π» Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½, наряду с ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ΠΈΡΠΌΠΈ Π½Π° Ρ€Π΅ΡΡƒΡ€ΡΡ‹ Π½ΡƒΠΆΠ½ΠΎ Π½Π°Π»ΠΎΠΆΠΈΡ‚ΡŒ условиС Π½Π΅ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π½Π° ΠΎΠ±ΡŠΡ‘ΠΌΡ‹ выпуска ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ†ΠΈΠΈ .

Π’ ΠΌΠΎΠ΄Π΅Π»ΡŒ Π·Π°Π΄Π°Ρ‡ΠΈ ΠΎ Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠ΅ΠΌ использовании рСсурсов входят: цСлСвая функция (Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° 1.13), систСма ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ΠΈΠΉ (Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° 1.14) ΠΈ ΡƒΡΠ»ΠΎΠ²ΠΈΡ Π½Π΅ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ (Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° 1.15).

(1.13).

(1.13).

(1.14).

(1.14).

(1.15).

Π’Π°ΠΊ ΠΊΠ°ΠΊ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ входят Π² Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ ΠΈ ΡΠΈΡΡ‚Π΅ΠΌΡƒ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ΠΈΠΉ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² ΠΏΠ΅Ρ€Π²ΠΎΠΉ стСпСни, Π° ΠΏΠΎΠΊΠ°Π·Π°Ρ‚Π΅Π»ΠΈ ΡΠ²Π»ΡΡŽΡ‚ΡΡ постоянными Π² ΠΏΠ»Π°Π½ΠΈΡ€ΡƒΠ΅ΠΌΡ‹ΠΉ ΠΏΠ΅Ρ€ΠΈΠΎΠ΄, Ρ‚ΠΎ ΡΡ‚ΠΎ — Π·Π°Π΄Π°Ρ‡Π° Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ программирования.

Π’ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… отраслях Π½Π°Ρ€ΠΎΠ΄Π½ΠΎΠ³ΠΎ хозяйства Π²ΠΎΠ·Π½ΠΈΠΊΠ°Π΅Ρ‚ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ° составлСния Ρ‚Π°ΠΊΠΈΡ… Ρ€Π°Π±ΠΎΡ‡ΠΈΡ… смСсСй Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ исходных ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»ΠΎΠ², ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ обСспСчивали Π±Ρ‹ ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½ΠΈΠ΅ ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ³ΠΎ ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ‚Π°, ΠΎΠ±Π»Π°Π΄Π°ΡŽΡ‰Π΅Π³ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½Ρ‹ΠΌΠΈ свойствами. К ΡΡ‚ΠΎΠΉ Π³Ρ€ΡƒΠΏΠΏΠ΅ Π·Π°Π΄Π°Ρ‡ относятся Π·Π°Π΄Π°Ρ‡ΠΈ ΠΎ Π²Ρ‹Π±ΠΎΡ€Π΅ Π΄ΠΈΠ΅Ρ‚Ρ‹, составлСнии ΠΊΠΎΡ€ΠΌΠΎΠ²ΠΎΠ³ΠΎ Ρ€Π°Ρ†ΠΈΠΎΠ½Π° Π² ΠΆΠΈΠ²ΠΎΡ‚новодствС, ΡˆΠΈΡ…Ρ‚ Π² ΠΌΠ΅Ρ‚Π°Π»Π»ΡƒΡ€Π³ΠΈΠΈ, Π³ΠΎΡ€ΡŽΡ‡ΠΈΡ… ΠΈ ΡΠΌΠ°Π·ΠΎΡ‡Π½Ρ‹Ρ… смСсСй Π² Π½Π΅Ρ„Ρ‚Π΅ΠΏΠ΅Ρ€Π΅Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°ΡŽΡ‰Π΅ΠΉ ΠΏΡ€ΠΎΠΌΡ‹ΡˆΠ»Π΅Π½Π½ΠΎΡΡ‚ΠΈ, смСсСй для получСния Π±Π΅Ρ‚ΠΎΠ½Π° Π² ΡΡ‚Ρ€ΠΎΠΈΡ‚Π΅Π»ΡŒΡΡ‚Π²Π΅ ΠΈ Ρ‚. Π΄. Высокий ΡƒΡ€ΠΎΠ²Π΅Π½ΡŒ Π·Π°Ρ‚Ρ€Π°Ρ‚ Π½Π° ΠΈΡΡ…ΠΎΠ΄Π½Ρ‹Π΅ ΡΡ‹Ρ€ΡŒΠ΅Π²Ρ‹Π΅ ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Ρ‹ ΠΈ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΡΡ‚ΡŒ ΠΏΠΎΠ²Ρ‹ΡˆΠ΅Π½ΠΈΡ эффСктивности производства Π²Ρ‹Π΄Π²ΠΈΠ³Π°Π΅Ρ‚ Π½Π° ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ ΠΏΠ»Π°Π½ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ: ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ†ΠΈΡŽ с Π·Π°Π΄Π°Π½Π½Ρ‹ΠΌΠΈ свойствами ΠΏΡ€ΠΈ Π½Π°ΠΈΠΌΠ΅Π½ΡŒΡˆΠΈΡ… Π·Π°Ρ‚Ρ€Π°Ρ‚Π°Ρ… Π½Π° ΠΈΡΡ…ΠΎΠ΄Π½Ρ‹Π΅ ΡΡ‹Ρ€ΡŒΠ΅Π²Ρ‹Π΅ ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Ρ‹.

Π‘ΡƒΡ‰Π½ΠΎΡΡ‚ΡŒ Π·Π°Π΄Π°Ρ‡ΠΈ ΠΎΠ± ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠΌ раскроС состоит Π² Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅ Ρ‚Π°ΠΊΠΈΡ… тСхнологичСски допустимых ΠΏΠ»Π°Π½ΠΎΠ² раскроя, ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… получаСтся Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΡ‹ΠΉ ΠΊΠΎΠΌΠΏΠ»Π΅ΠΊΡ‚ Π·Π°Π³ΠΎΡ‚ΠΎΠ²ΠΎΠΊ, Π° ΠΎΡ‚Ρ…ΠΎΠ΄Ρ‹ (ΠΏΠΎ Π΄Π»ΠΈΠ½Π΅, ΠΏΠ»ΠΎΡ‰Π°Π΄ΠΈ, ΠΎΠ±ΡŠΠ΅ΠΌΡƒ, массС ΠΈΠ»ΠΈ стоимости) сводятся ΠΊ ΠΌΠΈΠ½ΠΈΠΌΡƒΠΌΡƒ. Π‘ΠΎΠ»Π΅Π΅ слоТныС постановки Π²Π΅Π΄ΡƒΡ‚ ΠΊ Π·Π°Π΄Π°Ρ‡Π°ΠΌ цСлочислСнного программирования.

ΠžΠ±Ρ‰Π°Ρ постановка транспортной Π·Π°Π΄Π°Ρ‡ΠΈ состоит Π² ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠΈ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π° ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ·ΠΎΠΊ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ ΠΎΠ΄Π½ΠΎΡ€ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π³Ρ€ΡƒΠ·Π° ΠΈΠ· m ΠΏΡƒΠ½ΠΊΡ‚ΠΎΠ² отправлСния Π² n ΠΏΡƒΠ½ΠΊΡ‚ΠΎΠ² назначСния. ΠŸΡ€ΠΈ этом Π² ΠΊΠ°Ρ‡Π΅ΡΡ‚Π²Π΅ критСрия ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ бСрСтся Π»ΠΈΠ±ΠΎ минимальная ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ·ΠΎΠΊ всСго Π³Ρ€ΡƒΠ·Π°, Π»ΠΈΠ±ΠΎ минимальноС врСмя Π΅Π³ΠΎ доставки. Рассмотрим Ρ‚Ρ€Π°Π½ΡΠΏΠΎΡ€Ρ‚Π½ΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ, Π² ΠΊΠ°Ρ‡Π΅ΡΡ‚Π²Π΅ критСрия ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ взята минимальная ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ·ΠΎΠΊ всСго Π³Ρ€ΡƒΠ·Π°. ΠžΠ±ΠΎΠ·Π½Π°Ρ‡ΠΈΠΌ Ρ‡Π΅Ρ€Π΅Π· Ρ‚Π°Ρ€ΠΈΡ„Ρ‹ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ·ΠΊΠΈ Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹ Π³Ρ€ΡƒΠ·Π° ΠΈΠ· i-Π³ΠΎ ΠΏΡƒΠ½ΠΊΡ‚Π° отправлСния Π² j-ΠΉ ΠΏΡƒΠ½ΠΊΡ‚ назначСния, Ρ‡Π΅Ρ€Π΅Π· — запасы Π³Ρ€ΡƒΠ·Π° Π² i-ΠΌ ΠΏΡƒΠ½ΠΊΡ‚Π΅ отправлСния, Ρ‡Π΅Ρ€Π΅Π· — потрСбности Π² Π³Ρ€ΡƒΠ·Π΅ Π² j-ΠΌ ΠΏΡƒΠ½ΠΊΡ‚Π΅ назначСния, Π° Ρ‡Π΅Ρ€Π΅Π· — количСство Π΅Π΄ΠΈΠ½ΠΈΡ† Π³Ρ€ΡƒΠ·Π°, ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ·ΠΈΠΌΠΎΠ³ΠΎ ΠΈΠ· i-Π³ΠΎ ΠΏΡƒΠ½ΠΊΡ‚Π° отправлСния Π² j-ΠΉ ΠΏΡƒΠ½ΠΊΡ‚ назначСния. Π’ΠΎΠ³Π΄Π° матСматичСская постановка Π·Π°Π΄Π°Ρ‡ΠΈ состоит Π² ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠΈ минимального значСния Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ (Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° 1.16) ΠΏΡ€ΠΈ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½Ρ‹Ρ… ограничСниях (Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° 1.17) ΠΈ ΡƒΡΠ»ΠΎΠ²ΠΈΡΡ… Π½Π΅ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ (Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° 1.18).

(1.16).

(1.16).

(1.17).

(1.17).

(1.18).

(1.18).

ΠžΠ±Ρ‹Ρ‡Π½ΠΎ исходныС Π΄Π°Π½Π½Ρ‹Π΅ транспортной Π·Π°Π΄Π°Ρ‡ΠΈ Π·Π°ΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ Π² Π²ΠΈΠ΄Π΅ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π΅ΠΉ планирования. (Ρ‚Π°Π±Π». 1.2).

Если общая ΠΏΠΎΡ‚Ρ€Π΅Π±Π½ΠΎΡΡ‚ΡŒ Π² Π³Ρ€ΡƒΠ·Π΅ Π² ΠΏΡƒΠ½ΠΊΡ‚Π°Ρ… назначСния Ρ€Π°Π²Π½Π° запасу Π³Ρ€ΡƒΠ·Π° Π² ΠΏΡƒΠ½ΠΊΡ‚Π°Ρ… отправлСния, Ρ‚ΠΎ ΠΌΠΎΠ΄Π΅Π»ΡŒ Ρ‚Π°ΠΊΠΎΠΉ транспортной Π·Π°Π΄Π°Ρ‡ΠΈ называСтся Π·Π°ΠΊΡ€Ρ‹Ρ‚ΠΎΠΉ. Если ΠΆΠ΅ ΡƒΠΊΠ°Π·Π°Π½Π½ΠΎΠ΅ условиС Π½Π΅ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΠ΅Ρ‚ся, Ρ‚ΠΎ ΠΌΠΎΠ΄Π΅Π»ΡŒ транспортной Π·Π°Π΄Π°Ρ‡ΠΈ называСтся ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΎΠΉ.

Π’ ΡΠ»ΡƒΡ‡Π°Π΅ ΠΏΡ€Π΅Π²Ρ‹ΡˆΠ΅Π½ΠΈΡ запаса Π½Π°Π΄ ΠΏΠΎΡ‚Ρ€Π΅Π±Π½ΠΎΡΡ‚ΡŒΡŽ, вводится Ρ„ΠΈΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ (n+1)-ΠΉ ΠΏΡƒΠ½ΠΊΡ‚ назначСния с ΠΏΠΎΡ‚Ρ€Π΅Π±Π½ΠΎΡΡ‚ΡŒΡŽ (Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° 1.19) ΠΈ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ Ρ‚Π°Ρ€ΠΈΡ„Ρ‹ ΡΡ‡ΠΈΡ‚Π°ΡŽΡ‚ΡΡ Ρ€Π°Π²Π½Ρ‹ΠΌΠΈ Π½ΡƒΠ»ΡŽ. Аналогично, Π² ΡΠ»ΡƒΡ‡Π°Π΅, Ссли потрСбности ΠΏΡ€Π΅Π²Ρ‹ΡˆΠ°ΡŽΡ‚ количСство запасов, Ρ‚Π°ΠΊΠΆΠ΅ вводится Ρ„ΠΈΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ (m+1)-ΠΉ ΠΏΡƒΠ½ΠΊΡ‚ отправлСния с Π·Π°ΠΏΠ°ΡΠΎΠΌ Π³Ρ€ΡƒΠ·Π° ΠΈ Ρ‚Π°Ρ€ΠΈΡ„Ρ‹ ΠΏΠΎΠ»Π°Π³Π°ΡŽΡ‚ΡΡ Ρ€Π°Π²Π½Ρ‹ΠΌΠΈ Π½ΡƒΠ»ΡŽ (Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° 1.20). Π­Ρ‚ΠΈΠΌ Π·Π°Π΄Π°Ρ‡Π° сводится ΠΊ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎΠΉ транспортной Π·Π°Π΄Π°Ρ‡Π΅, ΠΈΠ· ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ получаСтся ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ ΠΏΠ»Π°Π½ исходной Π·Π°Π΄Π°Ρ‡ΠΈ.

(1.19).

(1.19).

(1.20).

(1.20).

Как ΠΈ Π΄Π»Ρ всякой Π·Π°Π΄Π°Ρ‡ΠΈ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ программирования, ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ ΠΏΠ»Π°Π½ транспортной Π·Π°Π΄Π°Ρ‡ΠΈ являСтся ΠΈ ΠΎΠΏΠΎΡ€Π½Ρ‹ΠΌ ΠΏΠ»Π°Π½ΠΎΠΌ. ΠžΠΏΠΎΡ€Π½Ρ‹ΠΉ ΠΏΠ»Π°Π½ являСтся допустимым Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ΠΌ Π’Π— ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ся Π² ΠΊΠ°Ρ‡Π΅ΡΡ‚Π²Π΅ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ базисного Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ ΠΏΡ€ΠΈ Π½Π°Ρ…ΠΎΠΆΠ΄Π΅Π½ΠΈΠΈ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ ΠΏΠΎΡ‚Π΅Π½Ρ†ΠΈΠ°Π»ΠΎΠ². БущСствуСт Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° нахоТдСния ΠΎΠΏΠΎΡ€Π½Ρ‹Ρ… ΠΏΠ»Π°Π½ΠΎΠ²:

  • 1. ΠΌΠ΅Ρ‚ΠΎΠ΄ сСвСро-Π·Π°ΠΏΠ°Π΄Π½ΠΎΠ³ΠΎ ΡƒΠ³Π»Π°;
  • 2. ΠΌΠ΅Ρ‚ΠΎΠ΄ минимального элСмСнта;
  • 3. ΠΌΠ΅Ρ‚ΠΎΠ΄ Π΄Π²ΠΎΠΉΠ½ΠΎΠ³ΠΎ прСдпочтСния;
  • 4. ΠΌΠ΅Ρ‚ΠΎΠ΄ ΡˆΡ‚Ρ€Π°Ρ„ΠΎΠ² (ЀогСля).

" ΠšΠ°Ρ‡Π΅ΡΡ‚Π²ΠΎ" ΠΎΠΏΠΎΡ€Π½Ρ‹Ρ… ΠΏΠ»Π°Π½ΠΎΠ², ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Ρ… этими ΠΌΠ΅Ρ‚ΠΎΠ΄Π°ΠΌΠΈ, различаСтся: Π² ΠΎΠ±Ρ‰Π΅ΠΌ случаС ΠΌΠ΅Ρ‚ΠΎΠ΄ ЀогСля Π΄Π°Π΅Ρ‚ Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠ΅Π΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ (Π·Π°Ρ‡Π°ΡΡ‚ΡƒΡŽ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ΅), Π° ΠΌΠ΅Ρ‚ΠΎΠ΄ сСвСро-Π·Π°ΠΏΠ°Π΄Π½ΠΎΠ³ΠΎ ΡƒΠ³Π»Π°Π½Π°ΠΈΡ…ΡƒΠ΄ΡˆΠ΅Π΅.

ВсС ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ нахоТдСния ΠΎΠΏΠΎΡ€Π½Ρ‹Ρ… ΠΏΠ»Π°Π½ΠΎΠ² ΠΎΡ‚Π»ΠΈΡ‡Π°ΡŽΡ‚ΡΡ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ способом Π²Ρ‹Π±ΠΎΡ€Π° ΠΊΠ»Π΅Ρ‚ΠΊΠΈ для заполнСния. Π‘Π°ΠΌΠΎ Π·Π°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ происходит ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎ нСзависимо ΠΎΡ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠΎΠ³ΠΎ ΠΌΠ΅Ρ‚ΠΎΠ΄Π°. Π‘Π»Π΅Π΄ΡƒΠ΅Ρ‚ ΠΏΠΎΠΌΠ½ΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΏΠ΅Ρ€Π΅Π΄ Π½Π°Ρ…ΠΎΠΆΠ΄Π΅Π½ΠΈΠ΅ΠΌ ΠΎΠΏΠΎΡ€Π½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π° транспортная Π·Π°Π΄Π°Ρ‡Π° Π΄ΠΎΠ»ΠΆΠ½Π° Π±Ρ‹Ρ‚ΡŒ сбалансирована.

Π’ ΠΌΠ΅Ρ‚ΠΎΠ΄Π΅ сСвСро-Π·Π°ΠΏΠ°Π΄Π½ΠΎΠ³ΠΎ ΡƒΠ³Π»Π° ΠΈΠ· Π²ΡΠ΅Ρ… Π½Π΅ Π²Ρ‹Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹Ρ… ΠΊΠ»Π΅Ρ‚ΠΎΠΊ выбираСтся самая лСвая ΠΈ Π²Π΅Ρ€Ρ…няя (сСвСро-западная) ΠΊΠ»Π΅Ρ‚ΠΊΠ°. Π”Ρ€ΡƒΠ³ΠΈΠΌΠΈ словами, Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ шагС выбираСтся пСрвая ΠΈΠ· ΠΎΡΡ‚Π°Π²ΡˆΠΈΡ…ΡΡ Π½Π΅ Π²Ρ‹Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹Ρ… строк ΠΈ ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ ΠΈΠ· ΠΎΡΡ‚Π°Π²ΡˆΠΈΡ…ΡΡ Π½Π΅ Π²Ρ‹Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹Ρ… столбцов.

Для Ρ‚ΠΎΠ³ΠΎ Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π·Π°ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ ΠΊΠ»Π΅Ρ‚ΠΊΡƒ (i, j), Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΡΡ€Π°Π²Π½ΠΈΡ‚ΡŒ Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΉ запас Ρ‚ΠΎΠ²Π°Ρ€Π° Π² Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Π΅ΠΌΠΎΠΉ i-ΠΉ строкС с Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ ΠΏΠΎΡ‚Ρ€Π΅Π±Π½ΠΎΡΡ‚ΡŒΡŽ Π² Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Π΅ΠΌΠΎΠΌ j-ΠΌ столбцС. НахоТдСниС ΠΎΠΏΠΎΡ€Π½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π° продолТаСтся Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° Π½Π΅ Π±ΡƒΠ΄ΡƒΡ‚ Π²Ρ‹Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹ всС строки ΠΈ ΡΡ‚ΠΎΠ»Π±Ρ†Ρ‹. [9 c.137].

Π’ ΠΌΠ΅Ρ‚ΠΎΠ΄Π΅ минимального элСмСнта ΠΏΠ΅Ρ€Π²ΠΎΠΉ ΠΊΠ»Π΅Ρ‚ΠΊΠΎΠΉ Π²Ρ‹Π±ΠΈΡ€Π°ΡŽΡ‚ ΠΊΠ»Π΅Ρ‚ΠΊΡƒ с Π½Π°ΠΈΠΌΠ΅Π½ΡŒΡˆΠ΅ΠΉ суммой доставки ΠΈ Π·Π°ΠΏΠΎΠ»Π½ΡΡŽΡ‚ Π΅Π΅ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½ΠΎ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹ΠΌ Π³Ρ€ΡƒΠ·ΠΎΠΌ.

Если Ρ‚Π°Π±Π»ΠΈΡ†Π° стоимостСй Π²Π΅Π»ΠΈΠΊΠ°, Ρ‚ΠΎ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€ всСх элСмСнтов Π·Π°Ρ‚Ρ€ΡƒΠ΄Π½ΠΈΡ‚Π΅Π»Π΅Π½. Π’ ΡΡ‚ΠΎΠΌ случаС ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ ΠΌΠ΅Ρ‚ΠΎΠ΄ Π΄Π²ΠΎΠΉΠ½ΠΎΠ³ΠΎ прСдпочтСния, ΡΡƒΡ‚ΡŒ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ Π·Π°ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌ: Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ строкС ΠΈ ΠΊΠ°ΠΆΠ΄ΠΎΠΌ столбцС ΠΎΡ‚ΠΌΠ΅Ρ‡Π°ΡŽΡ‚ «V» Π½Π°ΠΈΠΌΠ΅Π½ΡŒΡˆΡƒΡŽ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ, Π° Π·Π°Ρ‚Π΅ΠΌ ΠΊΠ»Π΅Ρ‚ΠΊΠΈ с Π΄Π²ΠΎΠΉΠ½Ρ‹ΠΌ символом «VV» Π·Π°ΠΏΠΎΠ»Π½ΡΡŽΡ‚ с ΡƒΡ‡Π΅Ρ‚ΠΎΠΌ наимСньшСй стоимости. Π—Π°Ρ‚Π΅ΠΌ Ρ€Π°ΡΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‚ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ·ΠΊΠΈ ΠΏΠΎ ΠΊΠ»Π΅Ρ‚ΠΊΠ°ΠΌ, ΠΎΡ‚ΠΌΠ΅Ρ‡Π΅Π½Π½Ρ‹ΠΌ Π·Π½Π°ΠΊΠΎΠΌ «V». Π’ ΠΎΡΡ‚Π°Π²ΡˆΠ΅ΠΉΡΡ части Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ·ΠΊΠΈ Ρ€Π°ΡΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‚ ΠΏΠΎ Π½Π°ΠΈΠΌΠ΅Π½ΡŒΡˆΠ΅ΠΉ стоимости.

На ΠΊΠ°ΠΆΠ΄ΠΎΠΌ шагС ΠΌΠ΅Ρ‚ΠΎΠ΄Π° ЀогСля для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ i-ΠΉ строки Π²Ρ‹Ρ‡ΠΈΡΠ»ΡΡŽΡ‚ΡΡ ΡˆΡ‚Ρ€Π°Ρ„Ρ‹, ΠΊΠ°ΠΊ Ρ€Π°Π·Π½ΠΎΡΡ‚ΡŒ ΠΌΠ΅ΠΆΠ΄Ρƒ двумя наимСньшими Ρ‚Π°Ρ€ΠΈΡ„Π°ΠΌΠΈ строки. Π’Π°ΠΊΠΈΠΌ ΠΆΠ΅ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ Π²Ρ‹Ρ‡ΠΈΡΠ»ΡΡŽΡ‚ΡΡ ΡˆΡ‚Ρ€Π°Ρ„Ρ‹ для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ j-Π³ΠΎ столбца. ПослС Ρ‡Π΅Π³ΠΎ выбираСтся ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ ΡˆΡ‚Ρ€Π°Ρ„ ΠΈΠ· Π²ΡΠ΅Ρ… ΡˆΡ‚Ρ€Π°Ρ„ΠΎΠ² строк ΠΈ ΡΡ‚ΠΎΠ»Π±Ρ†ΠΎΠ². Π’ ΡΡ‚Ρ€ΠΎΠΊΠ΅ ΠΈΠ»ΠΈ столбцС, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΌ Π²Ρ‹Π±Ρ€Π°Π½Π½ΠΎΠΌΡƒ ΡˆΡ‚Ρ€Π°Ρ„Ρƒ, для заполнСния выбираСтся Π½Π΅ Π²Ρ‹Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚ая ΠΊΠ»Π΅Ρ‚ΠΊΠ° с ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ Ρ‚Π°Ρ€ΠΈΡ„ΠΎΠΌ. Если сущСствуСт нСсколько ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Ρ… ΠΏΠΎ Π²Π΅Π»ΠΈΡ‡ΠΈΠ½Π΅ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… ΡˆΡ‚Ρ€Π°Ρ„ΠΎΠ² Π² ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π΅, Ρ‚ΠΎ Π² ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… строках ΠΈΠ»ΠΈ столбцах выбираСтся ΠΎΠ΄Π½Π° Π½Π΅ Π²Ρ‹Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚ая ΠΊΠ»Π΅Ρ‚ΠΊΠ° с ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ Ρ‚Π°Ρ€ΠΈΡ„ΠΎΠΌ.

Если ΠΊΠ»Π΅Ρ‚ΠΎΠΊ с ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ Ρ‚Π°Ρ€ΠΈΡ„ΠΎΠΌ Ρ‚Π°ΠΊΠΆΠ΅ нСсколько, Ρ‚ΠΎ ΠΈΠ· Π½ΠΈΡ… выбираСтся ΠΊΠ»Π΅Ρ‚ΠΊΠ° (i, j) с ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ суммарным ΡˆΡ‚Ρ€Π°Ρ„ΠΎΠΌ, Ρ‚. Π΅. суммой ΡˆΡ‚Ρ€Π°Ρ„ΠΎΠ² ΠΏΠΎ i-ΠΉ строкС ΠΈ j-ΠΌΡƒ столбцу.

Если ΠΏΠ»Π°Π½ транспортной Π·Π°Π΄Π°Ρ‡ΠΈ являСтся ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ, Ρ‚ΠΎ Π΅ΠΌΡƒ соотвСтствуСт систСма ΠΈΠ· m+n чисСл Ui ΠΈ Vj, ΡƒΠ΄ΠΎΠ²Π»Π΅Ρ‚Π²ΠΎΡ€ΡΡŽΡ‰ΠΈΡ… условиям: Ui+Vj=Cij для занятых ΠΊΠ»Π΅Ρ‚ΠΎΠΊ ΠΈ Ui+Vj?Π‘ij Π² ΡΠ²ΠΎΠ±ΠΎΠ΄Π½Ρ‹Ρ… ΠΊΠ»Π΅Ρ‚ΠΊΠ°Ρ…. Числа Ui ΠΈ Vj Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ΡΡ ΠΏΠΎΡ‚Π΅Π½Ρ†ΠΈΠ°Π»Π°ΠΌΠΈ соотвСтствСнно поставщиков ΠΈ ΠΏΠΎΡ‚Ρ€Π΅Π±ΠΈΡ‚Π΅Π»Π΅ΠΉ. ΠŸΡ€ΠΈ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΈ ΠΎΠ΄Π½ΠΎΠΌΡƒ нСизвСстному ΠΏΠΎΡ‚Π΅Π½Ρ†ΠΈΠ°Π»Ρƒ придаСтся ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅. [9 c.141].

Π˜ΡΡ…ΠΎΠ΄Ρ ΠΈΠ· ΠΈΠ·Π»ΠΎΠΆΠ΅Π½Π½ΠΎΠ³ΠΎ ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Π° ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ Ρ‚Π°ΠΊΠΈΠ΅ Π²Ρ‹Π²ΠΎΠ΄Ρ‹: Π‘ΠΎΠ΄Π΅Ρ€ΠΆΠ°Π½ΠΈΠ΅ матСматичСского программирования ΡΠΎΡΡ‚Π°Π²Π»ΡΡŽΡ‚ тСория ΠΈ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ ΠΎ Π½Π°Ρ…ΠΎΠΆΠ΄Π΅Π½ΠΈΠΈ экстрСмумов Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ Π½Π° ΠΌΠ½ΠΎΠΆΠ΅ΡΡ‚Π²Π°Ρ…, опрСдСляСмых Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΌΠΈ ΠΈ Π½Π΅Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΌΠΈ ограничСниями (равСнствами ΠΈ Π½Π΅Ρ€Π°Π²Π΅Π½ΡΡ‚Π²Π°ΠΌΠΈ). ΠœΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΡ‡Π΅ΡΠΊΠΎΠ΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ являСтся ΠΎΠ΄Π½ΠΈΠΌ ΠΈΠ· Ρ€Π°Π·Π΄Π΅Π»ΠΎΠ² Π½Π°ΡƒΠΊΠΈ ΠΎΠ± ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΠΈ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ.

Π—Π°Π΄Π°Ρ‡ΠΈ матСматичСского программирования находят ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Π² Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… областях чСловСчСской Π΄Π΅ΡΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ, Π³Π΄Π΅ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌ Π²Ρ‹Π±ΠΎΡ€ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈΠ· Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… ΠΎΠ±Ρ€Π°Π·ΠΎΠ² дСйствий (ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ дСйствий), Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, ΠΏΡ€ΠΈ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΈ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌ управлСния ΠΈ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΡ производствСнных процСссов, Π² ΠΏΡ€ΠΎΠ΅ΠΊΡ‚ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠΈ ΠΈ ΠΏΠ΅Ρ€ΡΠΏΠ΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΌ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠΈ, Π² Π²ΠΎΠ΅Π½Π½ΠΎΠΌ Π΄Π΅Π»Π΅ ΠΈ Ρ‚. Π΄.

На Π΄ΠΎΠ»ΡŽ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ программирования приходится Π±ΠΎΠ»Π΅Π΅ 75% всСх Ρ€Π΅ΡˆΠ°Π΅ΠΌΡ‹Ρ… Π² ΠΌΠ°Ρ‚СматичСском ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠΈ Π·Π°Π΄Π°Ρ‡. БущСствуСт мноТСство Ρ‚ΠΈΠΏΠΎΠ²Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ программирования, для ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ достаточно Ρ…ΠΎΡ€ΠΎΡˆΠΎ извСстны:

  • — Π·Π°Π΄Π°Ρ‡Π° ΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠΌ ΠΏΠΎΡ‚ΠΎΠΊΠ΅
  • — Π·Π°Π΄Π°Ρ‡Π° ΠΎ ΠΏΠΎΡ‚ΠΎΠΊΠ΅ минимальной стоимости
  • — Π·Π°Π΄Π°Ρ‡Π° коммивояТСра
  • — Π·Π°Π΄Π°Ρ‡Π° ΠΎ ΠΏΠΎΠΊΡ€Ρ‹Ρ‚ΠΈΠΈ/раскроС
  • — Π·Π°Π΄Π°Ρ‡Π° ΠΎ Π²Ρ‹Π±ΠΎΡ€Π΅ Π΄ΠΈΠ΅Ρ‚Ρ‹ (ΠΎ ΡΠΎΡΡ‚Π°Π²Π»Π΅Π½ΠΈΠΈ сплава/раствора/смСси)
  • — Ρ‚ранспортная Π·Π°Π΄Π°Ρ‡Π°
  • — Π·Π°Π΄Π°Ρ‡Π° ΠΎ Π½Π°Π·Π½Π°Ρ‡Π΅Π½ΠΈΡΡ…
  • — Π·Π°Π΄Π°Ρ‡Π° ΠΎ Π²Ρ‹Π±ΠΎΡ€Π΅ ΠΏΡ€ΠΎΠ΅ΠΊΡ‚ΠΎΠ²
  • — Π΄Ρ€ΡƒΠ³ΠΈΠ΅ Ρ‚ΠΈΠΏΡ‹ Π·Π°Π΄Π°Ρ‡
ΠŸΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ вСсь тСкст
Π—Π°ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Ρ„ΠΎΡ€ΠΌΡƒ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ Ρ€Π°Π±ΠΎΡ‚ΠΎΠΉ