Прийняття управлінських рішень - Петруня Ю.Є. - 4.4. Задачі лінійного цілочислового програмування

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

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

п

2 аух7 < Ьі , і = 1 т1:

7=1

п -

2 ауху > Ьі, і = т1 +1,т2 :

7=1

п -

ауху = Ьі , і = т2 +1, т:

7=1 _

ху > 0, у = 1, п:

ху - цілі числа, у = 1, п1: п1 < п,

де с7, а7, Ьі - задані дійсні числа.

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

Задача про "товарний портфель"

Припустімо, що треба перевезти предмети різних найменувань, причому кількість предметів одного найменування може повторюватися. Задано обмеження щодо кожної характеристики предметів (вага, об'єм тощо) вектором В = (Ьі)т та

елементи матриці А = (ау)тхп, де означають /-ту характеристику

предмета у-го найменування. Задані також елементи вектора С = (су) п,

де Cj - корисність від перевезення предмета j-ro найменування. Треба так організувати перевезення товару, щоб максимізувати загальну корисність рейсу. Нехай Xj - кількість предметів j-ro найменування,

j = 1, n . Тоді математична модель задачі має такий вигляд:

n

z =2CjXj -" max; j=1

2 ajXj < bi, i = 1, m;

j=i _

< Xj > 0, j = 1, n ; Xj - цілі числа, j = 1, n.

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

Окремий вид прикладних цілочислових задач - це так звані задачі про прийняття або відхилення рішень, в яких змінні набувають значень тільки 0 або 1. Побудову економіко-математичної моделі такого виду задач розглянемо на прикладі задачі оптимізапії маршруту (задача "комівояжера").

Задача "комівояжера"

Існує n міст, що пов'язані між собою транспортною мережею. Відомі елементи матриці C = (Cj)nyn, де Cj

- відстані від z'-ro до j-ro міста. Виїхавши з одного міста, "комівояжер" повинен побувати в кожному місті тільки один раз і повернутися в те місто, з якого почав рухатися. Потрібно відшукати такий замкнений маршрут, що проходить через кожне місто лише один раз і довжина якого мінімальна.

Вводяться змінні Xj = {0;1}, де Xj набувають значення 1, якщо

комівояжер переїжджає від 7-го до j-ro міста, і 0 - у протилежному випадку.

Потрібно мінімізувати загальну відстань

n n

z = 2 2CjXj, за умов одноразового виїзду та в'їзду для всіх міст 2 Xij =1 (j =1 ^ i * j);

2 Xij =1 (i =1 ^ i * j).

j=1

Зазначені обмеження не повністю описують допустимі маршрути і не виключають можливості розриву маршруту. Щоб запобігти цьому, вводиться додаткова умова

Ui - Uj + nXj < n -1 (i = 1, n, j = 1, n, І Ф j),

де ui, Uj - невід'ємні цілочислові змінні, які в процесі розв'язання

задачі набуватимуть значень порядкових номерів міст за оптимальним маршрутом прямування комівояжера.

У результаті математична модель має такий вигляд

n n

z = Т.Т.СуХу -> min, i ф j;

Z xij =1 (j =1, n, i * j);

i=1

£ Xj = 1 (i = 1, n, i Ф j);

Xj = {0; 1} (i = 1, n, j = 1, n);

Ui - Uj + nXjj < n -1 (i = 1, n, j = 1, n, i Ф j).

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

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

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

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

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

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

Висновки

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

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

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

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

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

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

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