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

Низка економічних задач при їх розв’язуванні вимагає цілочислових значень змінних у кінцевому розв’язку. Зміст таких задач полягає у тому, що змінні відображують неподільні елементи, наприклад людські ресурси, машини, верстати та інше обладнання, транспорт, або неподільну продукцію (плавка металу, наряд-замовлення і т.п.). Причому цілочисловість змінних у задачах можлива як частковою, так і повною.

Вимоги дискретності змінних у розв’язку деяких задач оптимізації вимагає спеціальних методів розв’язування, тому такі задачі об’єднуються в окремий клас задач дискретного програмування (іноді його називають цілочисловим програмуванням).

Задачі дискретного програмування можна умовно розділити на три основні класи:

– цілочислові задачі лінійного типу;

– задачі з бульовими змінними;

– комбінаторні задачі.

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

У задачах з бульовими змінними накладаються додаткові умови:

та . Це задачі так званого двійкового вибору типу „так-ні”, "прийнято-відхилено" та ін. Типовою задачею цього класу є задача про призначення, за допомогою якої знаходяться парні зв’язки між двома множинами точок. Такі задачі розв’язуються за угорським методом, методом розгалужень і меж та ін.

Типовими комбінаторними задачами є задачі складання розпису, що зв’язані з розподілом ресурсів за часом. Ці задачі використовують метод випадкового пошуку, евристичні методи, а також метод послідовного аналізу варіантів, алгоритм Джонсона та інші, які будуються за принципом оптимальності задач динамічного програмування.

Комбінаторні задачі та задачі з бульовими змінними складають клас нелінійних цілочислових задач.

Класифікацію задач дискретного програмування можна зобразити схемою (рис.7.1).

Рис.7.1