На галоўную старонку
цэлалікавых праграмаванне
У канец старонкі
13. цэлалікавых ПРАГРАМАВАННЕ
Цэлалікавых праграмаванне - адзін з найбольш маладых, перспектыўных і хутка развіваюцца раздзелаў матэматычнага праграмавання. Можна пералічыць вялікая колькасць разнастайных задач планавання эканомікі, арганізацыі вытворчасці, даследаванні канфліктных сітуацый, сінтэзу схем аўтаматычнага рэгулявання, якія фармальна зводзяцца да выбару лепшых, у пэўным сэнсе, значэнняў параметраў з пэўнай дыскрэтнай сукупнасці зададзеных велічынь. Да іх можна аднесці і экстрэмальныя камбінаторныя задачы, якія ўзнікаюць у розных раздзелах дыскрэтнай матэматыкі.
Задачы і метады, якія адносяцца да пералічанага коле пытанняў, у літаратуры называюцца па-рознаму. Найбольшае распаўсюджванне атрымаў тэрмін «цэлалікавых праграмаванне», аднак сустракаюцца і такія як «дыскрэтнае праграмаванне», радзей «камбінаторныя (або диофантово) праграмаванне».
Найбольш вывучанымі задачамі гэтага класа з'яўляюцца цэлалікавых задачы лінейнага праграмавання, у якіх на ўсе зменныя (ці на іх частка) накладзена дадатковае патрабаванне цэлалікавых. Ад іх прынята адрозніваць так званыя дыскрэтныя задачы лінейнага праграмавання, у якіх вобласць дапушчальнага змены кожнай зменнай - ня мноства цэлых неадмо ¢ ных лікаў, а некаторы зададзены канчатковае мноства.
Цэлалікавых задачы матэматычнага праграмавання могуць узнікаць рознымі шляхамі.
1. Існуюць задачы лінейнага праграмавання, якія фармальна да цэлалікавых не адносяцца, але пры адпаведных зыходных дадзеных заўсёды валодаюць цэлалікавых планам. Прыклады такіх задач - транспартная задача і яе мадыфікацыі (задачы аб прызначэннях, аб патоках ў сетках).
2. Штуршком да вывучэння цэлалікавых задач ва ўласным сэнсе слова з'явілася разгляд задач лінейнага праграмавання, у якіх пераменныя прадстаўлялі фізічна непадзельныя велічыні. Яны былі названыя задачамі з непадзельнас. Такія, напрыклад, задачы аб аптымізацыі комплексу сродкаў дастаўкі грузаў, пра знаходжанне мінімальнага парожняга прабегу аўтамабіляў пры выкананні зададзенага плана перавозак, аб вызначэнні аптымальнага машыннага парку і яго аптымальнага размеркавання па ўказаных работ пры ўмове мінімізацыі сумарнай кошту (машыннага парку і вырабляюцца работ), аб знаходжанні мінімальнага колькасці судоў для ажыццяўлення гэтага графіка перавозак і т. п.
3. Іншым важным штуршком да пабудовы тэорыі цэлалікавага праграмавання стаў новы падыход да некаторых экстрэмальных камбінаторныя задачам. У іх патрабуецца знайсці экстрэмуму цэлалікавай лінейнай функцыі, зададзенай на канчатковым мностве элементаў. Такія задачы прынята называць задачамі з альтэрнатыўнымі зменнымі. У якасці прыкладаў можна назваць задачы коміваяжора (вандроўнага гандляра), пра аптымальны прызначэнні, тэорыі раскладу, або каляндарнага планавання, і задачы з дадатковымі лагічнымі ўмовамі (напрыклад, тыпу «або - або», «калі - то" і т. П.) .
Гістарычна першай задачай цэлалікавага тыпу з'яўляецца апублікаваная ў 1932 г. венгерскім матэматыкам Е. Эгервари задача аб прызначэнні персаналу. У 1955 г. на Другім сімпозіуме па лінейным праграмаванні была разгледжана задача аб бамбавіку, вядомая як задача аб ранцы.
Прывядзём прыклады цэлалікавых задач лінейнага праграмавання.
Прыклад. Задача аб ранцы. Маецца m -вектор абмежаваных рэсурсаў 
, Якія можна выкарыстоўваць для перавозкі розных па сваіх характарыстыках грузаў. Кожны j -й груз 
валодае наступнымі ўласцівасцямі: 1) непадзельнас; 2) карыснасцю 
; 3) расходам i -га рэсурсу для перавозкі адзінкі j -га грузу 
. Выбраць такі нумар грузу для перавозкі, пры якім максімізуецца агульная карыснасць рэйса (сумарная кошт перавезеных за рэйс грузаў).
Складзем матэматычную мадэль задачы. абазначым праз 
колькасць выбраных для траспортировки прадметаў. Патрабаванню непадзельнасці адпавядае ўмова
цэлыя, 
(13.1)
Супастаўленне выдаткаў рэсурсаў кожнага тыпу для транспарціроўкі адзінкі грузу і іх наяўнасці прыводзіць да абмежавання
(13.2)
Агульная карыснасць рэйса вызначаецца значэннем функцыі
. (13.3)
Прыватным выпадкам задачы (13.1) - (13.2) з'яўляецца задача аб ранцы, у якой любы з зададзенага набору прадметаў 
можа быць абраны ці не. Тады матэматычная мадэль прыме наступны выгляд:
максымізаваць
пры ўмовах
Прыклад. У вобласці
знайсці максімум функцыі 
.
Вырашым задачу геаметрычна (мал. 13.1). Вобласць пошуку экстрэмуму - шматкутнік OABCD. Бо лінія ўзроўню мэтавай функцыі раўналежная баку BC шматкутніка, экстрэмуму дасягаецца ў вяршынях 
і 
, А таксама ў любым пункце адрэзка BC і роўны 7. Нас цікавяць толькі кропкі з цэлалікавымі каардынатамі, таму ні B, ні C не зьяўляюцца дапушчальным рашэннем задачы. Акругліўшы значэнне каардынатаў кропак B і C, атрымаем кропку (4; 3), не належыла вобласці пошуку. Лёгка паказаць, што цэлалікавых оптымум дасягаецца ў кропках M (2; 3) і N (3, 2) і роўны 5. Абедзве пункту знаходзяцца ўнутры вобласці пошуку.
малюнак 13.1
Безгрунтоўнасць акруглення падкрэсліваецца таксама наступнымі меркаваннямі. Нягледзячы на тое, што цэлалікавых зменныя звычайна выказваюць колькасць непадзельных прадметаў, магчымыя і іншыя тыпы спецыфікацыі гэтых зменных. Так у задачы аб ранцы рашэнне ўяўляецца булевай зменнай 
(X = 0 або x = 1). У гэтым выпадку бессэнсоўна апераваць дробавымі значэннямі велічыні x і працэдура акруглення з'яўляецца лагічна непрымальнай.
З прыведзенага прыкладу відаць, што для вырашэння задач цэлалікавага праграмавання неабходна разгледзець асаблівыя метады аптымізацыі. Акрамя таго, аптымальнае рашэнне задач цэлалікавага праграмавання не абавязкова належыць мяжы мнагагранніка (шматкутніка) умоў, што характэрна для задач лінейнага праграмавання.
назад Да пачатку старонкі наперад
