Page 76 - 4719

ДИСКРЕТНЕ ПРОГРАМУВАННЯ

ПРАКТИЧНЕ ЗАНЯТТЯ 13

Тема: ФОРМАЛІЗАЦІЯ ЗАДАЧІ ДИСКРЕТНОГО
ПРОГРАМУВАННЯ З ЦІЛОЧИСЛОВИМИ ЗМІННИМИ

Мета заняття: Навчити студентів формалізувати задачі
дискретного програмування з цілочисловими змінними

1. Основні теоретичні положення

При розв’язку достатньо великої кількості оптимізаційних
завдань всі шукані змінні або їх частина повинні приймати
тільки значення цілих чисел. Математична модель таких
завдань аналогічна лінійним і нелінійним моделям і містить
цільову функцію, систему обмежень і граничні умови. Проте
система обмежень у завданнях з цілочисловими змінними
доповнюється обмеженнями типу
x = ціле , (13.1)
k
де k = 1, 2 ... l;
l - кількість цілочислових змінних.
Оптимізаційні задачі, в яких шукані змінні або їх частина
повинні бути цілими числами, вирішуються методами
цілочислового програмування.
Введення додаткових обмежень по цілочисельності
змінних істотно збільшує обсяг обчислень і ускладнює
обчислювальну процедуру при пошуку оптимального
розв’язку. Проте в заданому діапазоні цілочислова змінна має
меншу кількість значень, чим безперервна. Зокрема, в
діапазоні 0 < х < 3 цілочислова змінна х має чотири значення
(х = 0, 1, 2, 3), а безперервна змінна - нескінченну кількість
значень.
Спроба розв’язати цілочислову оптимізаційну задачу
методом повного перебору значень змінних приводить до дуже
великого об'єму обчислень. Так, наприклад, у задачі з трьома
цілочисловими змінними і діапазоном їх зміни 0 < x k < 10, k =
3
1, 2, 3 кількість цілочислових розв’язків складе 11 =1331.

75