Метад гаморам. Рашэнне задач цэлалікавага праграмавання

Маса задач эканамічнага характару, праблем планавання і нават рашэнне пытанняў з іншых сфер чалавечай жыццядзейнасці звязана з зменнымі, якія адносяцца да цэлых лікаў. У выніку іх аналізу і пошуку аптымальных спосабаў вырашэння з'явілася паняцце экстрэмальнай задачы. Яе асаблівасцямі з'яўляецца вышэйназваная асаблівасць прымаць цэлае значэння, а сама задача разглядаецца ў матэматыцы, як цэлалікавых праграмаванне.

У якасці асноўнага напрамкі выкарыстання задач з зменнымі, якія прымаюць цэлыя значэння, з'яўляецца аптымізацыя. А метад, які выкарыстоўвае цэлалікавых лінейнае праграмаванне, яшчэ называюць метадам адсячэння.

Метад гаморам атрымаў сваю назву па імі матэматыка, першым распрацавалі ў 1957-1958 гадах алгарытм, да гэтага часу шырока выкарыстоўваецца для вырашэння цэлалікавых задач лінейнага праграмавання. Кананічная форма задачы цэлалікавага праграмавання дазваляе даступна і ў поўным аб'ёме раскрыць перавагі гэтага метаду.

Метад гаморам дачыненні да лінейнага праграмаванні істотна ўскладняе задачу знаходжання аптымальных значэнняў. Бо цэлалікавых з'яўляецца асноўнай умовай, дадаткова да ўсіх параметрах задачы. Нярэдкія выпадкі, калі задача, маючы дапушчальныя (цэлалікавых) планы, пры наяўнасці ў мэтавай функцый абмежаванняў на дапушчальным мностве, у рашэнні не прыходзіць да дасягнення максімуму. Гэта адбываецца па прычыне адсутнасці менавіта цэлалікавых рашэнняў. Без гэтага ж умовы, як правіла, у выглядзе рашэння знаходзіцца прыдатны вектар.

Для абгрунтавання лікавых алгарытмаў пры вырашэнні задач ўзнікае неабходнасць ажыццяўляць накладыванія розных дадатковых умоў.

Выкарыстоўваючы метад гаморам, звычайна лічаць мноства планаў задачы абмежаваным так званым Мнагаграннікі рашэнняў. Зыходзячы з гэтага вынікае, што мноства ўсіх цэлалікавых планаў для пастаўленай задачы мае канчатковае значэнне.

Таксама для гарантаванасці цэлалікавых функцыі мяркуюць, што каэфіцыенты значэнняў таксама з'яўляюцца цэлымі лікамі. Нягледзячы на строгасць такіх умоў, послабее іх атрымоўваецца на няшмат.

Метад гаморам, па сутнасці, прадугледжвае пабудову абмежаванняў, якія адсякаюць рашэння, якія не з'яўляюцца нецелочисленными. Пры гэтым не адбываецца адсячэння ні аднаго рашэння цэлалікавага плана.

Алгарытм рашэння задачы ўключае ў сябе знаходжанне падыходных варыянтаў сімплексным метадам, не прымаючы да ўвагі умоў цэлалікавых. Калі ва ўсіх кампанентах аптымальнага плана прысутнічаюць рашэнні, якія адносяцца да цэлых лікаў, то можна лічыць, што мэта цэлалікавага праграмавання дасягнутая. Магчыма, што выявіцца невырашальнасць задачы, так мы атрымліваем доказ таго, што задача цэлалікавага праграмавання не мае рашэння.

Магчымы варыянт, калі ў кампанентах аптымальнага рашэння прысутнічаюць колькасці нецелых. У такім выпадку да ўсіх абмежаванням задачы дадаецца новае абмежаванне. Для новага абмежаванні характэрна наяўнасць шэрагу уласцівасцяў. Перш за ўсё, яно павінна быць лінейным, павінна адсякаць з знойдзенага аптымальнага мноства нецелочисленный план. Ні адно цэлалікавых рашэнне не павінна быць страчана, адцята.

Пры пабудове абмежаванні варта выбіраць кампаненту аптымальнага плана з найбольшай дробавай часткай. Менавіта гэта абмежаванне будзе дададзена да ўжо наяўнай сімплексным табліцы.

Знаходзім рашэнне атрыманай задачы, выкарыстоўваючы звычайныя сімплексным пераўтварэнні. Правяраем рашэнне задачы на наяўнасць цэлалікавага аптымальнага плана, калі ўмова выконваецца, то задача вырашана. Калі ізноў быў атрыманы вынік з наяўнасцю нецелочисленных рашэнняў, то ўводзім дадатковае абмежаванне, і паўтараем працэс вылічэнняў.

Ажыццявіўшы канчатковае лік ітэрацый, дамагаемся атрымання аптымальнага плана задачы, пастаўленай перад цэлалікавых праграмаваннем, альбо даказваем невырашальнасць задачы.