ТЕМА 7. ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА МЕТОДИ ЇХ РОЗВ’ЯЗАННЯ. ТЕОРІЯ ДВОЇСТОСТІ ТА АНАЛІЗ ЛІНІЙНИХ МОДЕЛЕЙ ОПТИМІЗАЦІЙНИХ ЗАДАЧ.

1. Поняття про задачу лінійного програмування. Розгорнутий і стислий вигляд задачі лінійного програмування.

2. Канонічна задача лінійного програмування. Перехід до канонічної форми.

3. Графічний метод розв’язання задачі лінійного програмування.

4. Симплексний метод розв’язання задач лінійного програмування.

5. Двоїстість в лінійному програмуванні. Пряма та двоїста задачі лінійного програмування. Зв’язок між розв’язками прямої та двоїстої задач.

1. Поняття про задачу лінійного програмування. Розгорнутий і стислий вигляд задачі лінійного програмування.

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

У розгорнутому вигляді задача лінійного програмування формулюється так: знайти максимальне (мінімальне) значення цільової функції:

(7.1)

при заданих обмеженнях у вигляді рівностей і нерівностей:

………………………………

, (7.2)

………………………………

та умові невід’ємності:

. (7.3)

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

;

; (7.4)

де – загальна кількість змінних (невідомих) величин;

– порядковий номер змінної;

– загальна кількість обмежень;

– порядковий номер обмеження;

– змінна з порядковим номером ;

– оцінка цільової функції на одиницю -го виду діяльності;

– норма витрат -го виду ресурсу на одиницю -го виду діяльності;

– обсяг наявного ресурсу -го виду.

Завжди можна вважати, що в системі (7.2) перші обмежень – нерівності, а останні обмежень – рівності. Це можна отримати звичайним перевпорядкуванням обмежень.

Відносно знака нерівності, можна вважати, що ліва частина менша правої або дорівнює їй. Це також легко зробити, помноживши на (-1) обидві частини тих нерівностей, які мають протилежний знак.

Зауважимо, що вибір типу шуканого екстремуму (максимуму чи мінімуму) відносний. Так, задача пошуку максимум функції

(7.5)

рівнозначна задачі пошуку мінімуму функції

. (7.6)

2. Канонічна задача лінійного програмування. Перехід до канонічної форми.

Задачу лінійного програмування, записану у вищенаведеній формі (розгорнутій чи стислій), називають загальною задачею лінійного програмування.

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

Враховуючи це, запишемо загальний вигляд канонічної задачі лінійного програмування в скороченому вигляді:

;

; (7.7)

Більшість відомих методів розв’язання задач лінійного програмування призначені для канонічних задач, тому початковий етап розв’язання будь-якої задачі лінійного програмування звичайно пов’язаний із зведенням її до деякої еквівалентної канонічної задачі.

Для цього достатньо зробити два кроки:

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

· змінні, на які не накладена умова невід’ємності, представляють у вигляді різниці двох нових невід’ємних змінних:

. (7.8)

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

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

3. Графічний метод розв’язання задачі лінійного програмування.

Розглянемо конкретний приклад розв’язання задачі оптимізації виробничої програми підприємства графоаналітичним методом.

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

Таблиця 7.1

Вихідні дані задачі оптимізації плану виробництва

Елемент моделі	Вид продукції		Наявність ресурсу
Елемент моделі	А	Б	Наявність ресурсу
Ресурси:
- сировина	4	5	200
- трудові	450	350	15750
- капіталовкладення	7	3	210
Прибуток від реалізації одиниці виробу, грош. од.	55	32,5	-
План, од.			-

Потрібно знайти оптимальний план виробництва за критерієм максимуму прибутку.

Позначимо шукані величини, тобто кількість одиниць продукції А і Б відповідно х₁ і х₂. Сформулюємо математичну модель задачі: визначити оптимальний план , який забезпечить максимальне значення цільової функції при заданих обмеженнях ресурсів.

Модель задачі при цих даних має вигляд:

(1)

(2)

(3)

(4)

(5)

(6)

Графічний розв’язок задачі оптимізації плану випуску продукції подано на рис. 7.1.

Умови невід’ємності (5) і (6) визначають першу координатну чверть.

Рис. 7.1. Графічний розв’язок задачі оптимізації плану випуску продукції

Кожна із нерівностей (2)-(4) визначає певну півплощину, обмежену прямою. На рис. 7.1 ці прямі названо (по першому ресурсу), (по другому ресурсу), (по третьому ресурсу).

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

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

Якщо точка лежить нижче прямої, ресурс використовується неповністю, тобто є залишки ресурсу.

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

Перетин (спільна частина) цих півплощин визначає область допустимих планів задачі. На рис. 71 це заштрихований п’ятикутник ОА₂КLС₁.

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

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

Задачу вибору оптимального плану найзручніше розв’язувати графоаналітичним способом. Для цього будують одну з ізоквант цільової функції, тобто лінію на площині Х₁ОХ₂, яка з’єднує точки планів з однаковими значеннями цільової функції.

Рівняння ізокванти має вигляд = const або в нашому випадку:

= D.

Всі ізокванти паралельні між собою.

Тому слід побудувати одну з ізоквант D₁D₂ і переміщувати її паралельно самій себе, поки вона не дотикнеться до області допустимих планів. Координати точки (точок) дотику і визначають оптимальні плани.

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

На рис. 7.1 оптимальний план знаходиться в точці L (), яка утворена перетином прямих, що відповідають обмеженням (3) і (4) відповідно на другий і третій ресурси.

Для знаходження оптимального плану (координат точки L) слід розв’язати систему з двох лінійних рівнянь:

Її розв’язок = 24, = 14.

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

грош. од.

При цьому другий і третій ресурси (трудові та капіталовкладення) використовуються в оптимальному плані повністю (оскільки точка лежить на перетині обмежень саме на ці ресурси), а рівень використання першого ресурсу (сировини) визначимо:

Якби було прийнято „очевидне”, на перший погляд, рішення – виробляти тільки більш дорогу продукцію (в нашому випадку це продукція А за ціною 55 грош. од.), то, як видно з рис. 7.1, підприємство могло б випустити такої продукції в кількості 30 одиниць (точка С₁). Для цієї продукції найбільш дефіцитний ресурс – третій (капіталовкладення) і він вичерпується при x₁= 30.

Цільова функція досягла б для такого плану значення:

55×30+32,5×0=1650 грош. од.

Це становить 93% від максимального рівня.

Розрахуємо рівень використання 1-ого і 2-ого ресурсів:

;

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

Графічним методом можна розв’язувати також задачі, системи обмежень яких містять лінійно незалежних рівнянь і змінних, причому і задовольняють умову:

. (7.9)

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

Однак є більш універсальний метод розв’язання задач лінійного програмування – симплексний метод або метод послідовного покращення плану.

4. Симплексний метод розв’язання задач лінійного програмування.

Симплекс-метод був розроблений у 1947 році американським математиком Джорджем Данцигом.

Алгоритм розв’язання задачі лінійного програмування (ЗЛП) на максимум симплексним методом подано на рис. 7.2.

Рис. 7.2. Алгоритм розв’язання задачі лінійного програмування на максимум симплексним методом

Розглянемо більш детально кожен крок зазначеного алгоритму.

1. Побудова математичної моделі задачі лінійного програмування, тобто формування цільової функції і системи обмежень.

2. Зведення задачі лінійного програмування до канонічного вигляду (система рівностей, умова невід’ємності).

3. Побудова початкової симплекс-таблиці (таблиця 7.2).

Таблиця 7.2

Початкова симплексна таблиця

№

С рядок

C₁

C₂

…

C_l

…

C_n

…

стов-пчик

Базис

х₀

х₁

х₂

…

X_l

…

х_n

х_n+1

х_n+2

…

х_n+m

х_n+1

b₁

a₁₁

a₁₂

…

a_1l

…

a_1n

…

х_n+2

b₂

a₂₁

a₂₂

…

a_2l

…

a_2n

…

х_n+k

b_k

a_k1

a_k2

…

a_kl

…

a_kn

…

х_n+m

b_m

a_m1

a_m2

…

a_ml

…

a_mn

…

m+1

m+2

S -C

-C₁

-C₂

…

-C_l

…

-C_n

…

Рядок і стовпчик „С” є значеннями коефіцієнтів цільової функції при відповідних змінних.

Стовпчик „Базис” – вироби, які включені в план.

Стовпчик „х₀” – вільні члени рівнянь.

В стовпчик “Базис” ввійдуть невідомі, які утворюють одиничну матрицю.

В стовпчик „С” заносять значення коефіцієнтів цільової функції, які відповідають невідомим базису. Тоді заповнюють всі стовпчики , записуючи в них коефіцієнти при із системи рівнянь (7.7).

В таблиці перші m рядків визначаються даними задачі, а показники m+1 і m+2 рядків розраховуються.

Елементи рядка „S” визначаємо за формулою (7.10):

. (7.10)

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

Останній рядок – результат віднімання від даних рядка „S” даних рядка „С”. Його також називають оцінкою плану.

4. Перевіряємо, чи всі С_j £ 0 (j=1,…,n+m). Якщо є С_j > 0, то переходимо до наступного кроку. Інакше допустимий базисний розв’язок є оптимальним.

5. Вибір головного стовпчика здійснюємо за правилом:

- C_l = min{- C_j} або C_l = max{C_j} , j=1,…,n+m. (3.11)

6. Перевіряємо, чи всі a_il £ 0 (i=1,…,m). Якщо ця умова виконується, то функція необмежена і розв’язок знайти не можна. Інакше переходимо до наступного кроку.

7. Вибір головного рядка і головного елемента здійснюємо за правилом:

a_k = min { ,де a_il > 0}, l = 1…m. (7.12)

Тоді k-тий рядок головний, a_kl – головний елемент.

8. При побудові другої симплексної таблиці розрахунок елементів здійснюємо за правилами:

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

; (7.13)

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

. (7.14)

в) елементи головного рядка, крім головного елемента, отримують шляхом ділення на головний елемент:

(7.15)

Аналогічно розраховують елементи стовпчика :

(7.16)

(7.17)

9. Переходимо до кроку 4.

10. Економічний аналіз результатів. Значення невідомих змінних знаходять в останній симплекс-таблиці в стовпчику , оптимальне значення функції – в комірці F. Після цього роблять висновки.

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

Згідно з теорією лінійного програмування кожній задачі лінійного програмування відповідає двоїста їй задача лінійного програмування.

В загальному вигляді вихідна задача лінійного програмування (7.18) і двоїста до неї задача (7.19) записуються в такому вигляді:

;

(7.18)

;

(7.19)

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

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

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

Змінні двоїстої задачі називають об’єктивно обумовленими оцінками або двоїстими оцінками.

Двоїста задача у відношенні до вихідної складається за такими правилами:

Вихідна функція вихідної задачі (7.18) формулюється на максимум, а цільова функція двоїстої задачі (7.19) – на мінімум. При цьому в задачі на максимум знак всіх нерівності у функціональних обмеженнях (менше або дорівнює), а в задачі на мінімум – навпаки (більше або дорівнює).

Матриця із коефіцієнтів при невідомих в системі обмежень (7.18) вихідної задачі, і аналогічна матриця в двоїстій задачі є транспонованими.

Кількість змінних двоїстої задачі дорівнює кількості функціональних обмежень вихідної задачі, а кількість обмежень в системі двоїстої задачі – відповідно кількості змінних вихідної задачі.

Коефіцієнтами при невідомих у цільовій функції двоїстої задачі (7.19) є вільні члени обмежень в системі (7.18) обмежень вихідної задачі, а правими частинами в обмеженнях двоїстої задачі – коефіцієнти при невідомих у цільовій функції вихідної задачі.

Кожному обмеженню однієї задачі відповідає змінна іншої задачі: номер змінної співпадає з номером обмеження; при цьому обмеженню, записаному у вигляді нерівності зі знаком , відповідає змінна, пов’язана умовою невід’ємності. Якщо ж функціональне обмеження записане у вигляді рівності, то відповідна змінна двоїстої задачі може набувати як додатних, так і від’ємних значень.

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

Тобто, мова йдеться про пару взаємно двоїстих задач лінійного програмування.

Розглянемо побудову двоїстої задачі на конкретному прикладі.

Нехай задана загальна задача лінійного програмування:

цільова функція:

;