Задачі лінійного цілочислового програмування

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

Класичним прикладом управлінської задачі, яка описується цілочисловою моделлю, є задача про «товарний портфель».

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

Побудову економіко-математичної моделі такого виду задач розглянемо на прикладі задачі оптимізації маршруту (задача «комівояжера»).

Задача «комівояжера». Існує n міст, що пов'язані між собою транспортною мережею. До задачі «комівояжера» зводиться також багато інших практично важливих задач: перевезення пошти або певних товарів у місті; перевірка або інспекція підприємств та установ; з'єднання пунктів лініями газопостачання або зв'язку тощо.

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

Методи розв'язання задач цілочислового програмування можна поділити на три групи.

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

— Комбінаторні методи. Ці методи базуються на ідеї цілеспрямованого перебирання всіх допустимих цілочислових розв'язків з відсіюванням множин неперспективних допустимих розв'язків.

— Наближені методи. Вони, як правило, дозволяють знайти наближений розв'язок задачі за меншого обсягу обчислень та спрощення відповідних алгоритмів.

Висновки

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

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

3. До основних ознак, за якими можна класифікувати економіко- математичні моделі, належать: цільове призначення (теоретичні, прикладні); ступінь агрегування (макроекономічні, мікроекономічні); спрямування (балансові, трендові, оптимізаційні, імітаційні); підхід до вивчення системи (дескриптивні, нормативні); фактор часу (статичні, динамічні); характер інформації (детерміновані, стохастичні); характеристика математичного апарату, який застосовується в моделях (математичного програмування, кореляційно-регресійні, теорії масового обслуговування, сіткового планування й управління тощо).

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

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

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

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

Дата добавления: 2015-12-07