Π”ΠΈΠΏΠ»ΠΎΠΌΡ‹, курсовыС, Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚Ρ‹, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Ρ‹Π΅...
Брочная ΠΏΠΎΠΌΠΎΡ‰ΡŒ Π² ΡƒΡ‡Ρ‘Π±Π΅

ГрафичСский способ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ программирования

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

КаТдоС ΠΈΠ· Π½Π΅Ρ€Π°Π²Π΅Π½ΡΡ‚Π² систСмы ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ΠΈΠΉ (1.2) ΠΈ (1.3) опрСдСляСт Π½Π° ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Π½ΠΎΠΉ плоскости x1Оx2 Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΏΠΎΠ»ΡƒΠΏΠ»ΠΎΡΠΊΠΎΡΡ‚ΡŒ, Π° ΡΠΈΡΡ‚Π΅ΠΌΠ° нСравСнств Π² Ρ†Π΅Π»ΠΎΠΌ — пСрСсСчСниС ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… плоскостСй: Π›ΡŽΠ±Π°Ρ внутрСнняя ΠΈ Π³Ρ€Π°Π½ΠΈΡ‡Π½Π°Ρ Ρ‚ΠΎΡ‡ΠΊΠ° ΠžΠ”Π  являСтся Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ΠΌ Π·Π°Π΄Π°Ρ‡ΠΈ. ΠŸΡ€ΠΈΡ€Π°Π²Π½ΡΠ΅ΠΌ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ (1.1) ΠΊ Π½ΡƒΠ»ΡŽ, Ρ‚ΠΎΠ³Π΄Π° ΡƒΡ€Π°Π²Π½Π΅Π½ΠΈΠ΅. Ai1x1 + ai2x2 + … + ainxn + yi = bi, i = ΠΈ Ρ…j = 0, j =. Z = c1x1 + c2x2 +…+ cnxnmax… Π§ΠΈΡ‚Π°Ρ‚ΡŒ Π΅Ρ‰Ρ‘ >

ГрафичСский способ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ программирования (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚, курсовая, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ)

НаиболСС простым ΠΈ Π½Π°Π³Π»ΡΠ΄Π½Ρ‹ΠΌ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π—Π›ΠŸ являСтся графичСский ΠΌΠ΅Ρ‚ΠΎΠ΄. Он ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΠ΅Ρ‚ся для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π—Π›ΠŸ с Π΄Π²ΡƒΠΌΡ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌΠΈ, Π·Π°Π΄Π°Π½Π½Ρ‹ΠΌΠΈ Π² Π½Π΅ΠΊΠ°Π½ΠΎΠ½ΠΈΡ‡Π΅ΡΠΊΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅, ΠΈ ΠΌΠ½ΠΎΠ³ΠΈΠΌΠΈ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌΠΈ Π² ΠΊΠ°Π½ΠΎΠ½ΠΈΡ‡Π΅ΡΠΊΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅ ΠΏΡ€ΠΈ условии, Ρ‡Ρ‚ΠΎ ΠΎΠ½ΠΈ содСрТат Π½Π΅ Π±ΠΎΠ»Π΅Π΅ Π΄Π²ΡƒΡ… свободных ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

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

Z = c1x1 + c2x2 +…+ cnxnmax (min), (1.1).

a1x1 + a12x2 + … + a1nxn b1, (1.2).

am1x1 + am2x2 + … + amnxn bm ,

xi0, j =. (1.3).

КаТдоС ΠΈΠ· Π½Π΅Ρ€Π°Π²Π΅Π½ΡΡ‚Π² систСмы ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ΠΈΠΉ (1.2) ΠΈ (1.3) опрСдСляСт Π½Π° ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Π½ΠΎΠΉ плоскости x1Оx2 Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΏΠΎΠ»ΡƒΠΏΠ»ΠΎΡΠΊΠΎΡΡ‚ΡŒ, Π° ΡΠΈΡΡ‚Π΅ΠΌΠ° нСравСнств Π² Ρ†Π΅Π»ΠΎΠΌ — пСрСсСчСниС ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… плоскостСй:

ai1x1 + ai2x2 + … + ainxn + yi = bi, i = ΠΈ Ρ…j = 0, j = .

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

Π›ΡŽΠ±Π°Ρ внутрСнняя ΠΈ Π³Ρ€Π°Π½ΠΈΡ‡Π½Π°Ρ Ρ‚ΠΎΡ‡ΠΊΠ° ΠžΠ”Π  являСтся Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ΠΌ Π·Π°Π΄Π°Ρ‡ΠΈ. ΠŸΡ€ΠΈΡ€Π°Π²Π½ΡΠ΅ΠΌ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ (1.1) ΠΊ Π½ΡƒΠ»ΡŽ, Ρ‚ΠΎΠ³Π΄Π° ΡƒΡ€Π°Π²Π½Π΅Π½ΠΈΠ΅.

Z = c1x1 + c2x2 +…+ cnxn=0.

прСдставляСт собой ΠΏΠΎΠ»ΡƒΠΏΠ»ΠΎΡΠΊΠΎΡΡ‚ΡŒ, ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΡΡ‰ΡƒΡŽ Ρ‡Π΅Ρ€Π΅Π· Π½Π°Ρ‡Π°Π»ΠΎ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ ΠΈ ΠΏΠ΅Ρ€ΠΏΠ΅Π½Π΄ΠΈΠΊΡƒΠ»ΡΡ€Π½ΡƒΡŽ Π²Π΅ΠΊΡ‚ΠΎΡ€Ρƒ-Π³Ρ€Π°Π΄ΠΈΠ΅Π½Ρ‚Ρƒ (Π½Π°ΠΏΡ€Π°Π²Π»ΡΡŽΡ‰Π΅ΠΌΡƒ Π²Π΅ΠΊΡ‚ΠΎΡ€Ρƒ) =(с1, с2,…, сn). НаправлСниС Π²Π΅ΠΊΡ‚ΠΎΡ€Π°-Π³Ρ€Π°Π΄ΠΈΠ΅Π½Ρ‚Π° ΠΏΠΎΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚ Π½Π°ΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠ΅ возрастания Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π°ΠΉΡ‚ΠΈ максимум Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΠ΅Ρ€Π΅Π΄Π²ΠΈΠ³Π°Ρ‚ΡŒ Π³ΠΈΠΏΠ΅Ρ€ΠΏΠ»ΠΎΡΠΊΠΎΡΡ‚ΡŒ Π² Π½Π°ΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠΈ Π²Π΅ΠΊΡ‚ΠΎΡ€Π° ΠΊΠ°ΠΊ ΠΌΠΎΠΆΠ½ΠΎ дальшС ΠΎΡ‚ Π½Π°Ρ‡Π°Π»Π° ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚, Π½ΠΎ Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΎΠ½Π° ΠΈΠΌΠ΅Π»Π° с ΠžΠ”Π  хотя Π±Ρ‹ ΠΎΠ΄Π½Ρƒ ΠΎΠ±Ρ‰ΡƒΡŽ Ρ‚ΠΎΡ‡ΠΊΡƒ. Π§Ρ‚ΠΎΠ±Ρ‹ Π½Π°ΠΉΡ‚ΠΈ ΠΌΠΈΠ½ΠΈΠΌΡƒΠΌ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, Π½ΡƒΠΆΠ½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ Π±Π»ΠΈΠΆΠ°ΠΉΡˆΡƒΡŽ Ρ‚ΠΎΡ‡ΠΊΡƒ Π² ΠžΠ”Π  ΠΎΡ‚ Π½Π°Ρ‡Π°Π»Π° ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚.

ΠŸΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ вСсь тСкст
Π—Π°ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Ρ„ΠΎΡ€ΠΌΡƒ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ Ρ€Π°Π±ΠΎΡ‚ΠΎΠΉ