Задачі цілочисельного ЛП. Геометрична інтерпретація системи обмежень задач цілочислового програмування - Економіко-математичне моделювання

Умова цілочисловості є по суті нелінійною і може зустрічатися в задачах, що містять як лінійні, так і нелінійні функції. Задачі математичного програмування, в яких крім умови цілочисловості всі обмеження та цільова функція є лінійними, що мають назву цілочислових задач лінійного програмування.

Загальна цілочислова задача лінійного програмування записується так: за умов: ; ;-- цілі числа.

Скажімо, множина допустимих розв'язків деякої нецілочислової задачі лінійного програмування має вигляд, зображений на рис. 13.1

Геометрично множина допустимих планів будь-якої лінійної цілочислової задачі являє собою систему точок з цілочисловими координатами, що знаходяться всередині опуклого багатокутника допустимих розв'язків відповідної нецілочислової задачі. Отже, для розглянутого на рис. 13.1 випадку множина допустимих планів складається з дев'яти точок (рис. 13.2), які утворені перетинами сім'ї прямих, що паралельні осям Ох1 та Oх2 і проходять через точки з цілими координатами 0, 1, 2. Для знаходження цілочислового оптимального розв'язку пряму, що відповідає цільовій функції, пересуваємо у напрямку вектора нормалі до перетину з кутовою точкою утвореної цілочислової сітки. Координати цієї точки і є оптимальним цілочисловим розв'язком задачі. У нашому прикладі оптимальний цілочисловий розв'язок відповідає точці М ().

Очевидно, особливість геометричної інтерпретації цілочислової задачі у зіставленні зі звичайною задачею лінійного програмування полягає лише у визначенні множини допустимих розв'язків. Областю допустимих розв'язків загальної задачі лінійного програмування є опуклий багатогранник, а вимога цілочисловості розв'язку приводить до такої множини допустимих розв'язків, яка є дискретною і утворюється тільки з окремих точок.

рис 13.2

Рис 13.1 Рис 13.2

Похожие статьи




Задачі цілочисельного ЛП. Геометрична інтерпретація системи обмежень задач цілочислового програмування - Економіко-математичне моделювання

Предыдущая | Следующая