Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

2.8.6. Метод штучного базису

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

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

(2.60)

(2.61)

(2.62)

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

(2.63)

У результаті додавання змінних у рівняння системи (2.61) область допустимих розв’язків задачі розширилась. Задачу з системою обмежень (2.63) називають розширеною, або М-задачею. Розв’язок розширеної задачі збігатиметься з розв’язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві. Тоді система обмежень (2.63) набуде вигляду (2.61) (не міститиме штучних змінних), а розв’язок розширеної задачі буде розв’язком і задачі (2.60)—(2.62).

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

(У разі розв’язання задачі на відшукання мінімального значення цільової функції вводять коефіцієнти, які є досить великими числами. Цільова функція тоді має вигляд: ).

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

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

Для розв’язання розширеної задачі за допомогою симплексних таблиць зручно використовувати таблиці, оцінкові рядки яких поділені на дві частини-рядки. Тоді в (m+2)-му рядку записують коефіцієнти з М, а в (m+1)-му — ті, які не містять М. Вектор, який підлягає включенню до базису, визначають за (m+2)-м рядком. Ітераційний процес по (m+2)-му рядку проводять до повного виключення всіх штучних змінних з базису, потім процес визначення оптимального плану продовжують за (m+1)-им рядком.

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

Теорема 2.8. Якщо в оптимальному плані розширеної задачі штучні змінні , то план є оптимальним планом початкової задачі.

Доведення. Зазначимо, що коли план є оптимальним планом розширеної задачі, то план — план початкової задачі. При цьому

.

Доведемо, що план — оптимальний план початкової задачі. Допустимо, що не є оптимальним планом. Тоді існує такий оптимальний план , для якого . Звідси для вектора , що є планом розширеної задачі, маємо:

,

тобто

.

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

Отже, загалом алгоритм розв’язування задачі лінійного програмування симплекс-методом складається з п’яти етапів:

1. Визначення початкового опорного плану задачі лінійного програмування.
2. Побудова симплексної таблиці.
3. Перевірка опорного плану на оптимальність за допомогою оцінок . Якщо всі оцінки задовольняють умову оптимальності, то визначений опорний план є оптимальним планом задачі. Якщо хоча б одна з оцінок не задовольняє умову оптимальності, то переходять до нового опорного плану або встановлюють, що оптимального плану задачі не існує.
4. Перехід до нового опорного плану задачі здійснюється визначенням розв’язувального елемента та розрахунками елементів нової симплексної таблиці.
5. Повторення дій, починаючи з п. 3.

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

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

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

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

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

Розв’язати задачу з прикладу 2.10 із додатковою умовою: продукція С має виготовлятися обсягом не менш як 9 одиниць.

Розв’язання. Математичну модель сформульованої задачі запишемо так:

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

Зауважимо, що нерівність типу «≥» перетворюємо у рівняння введенням у ліву частину обмеження додаткової змінної зі знаком «–».

Система містить лише два одиничні вектори — та , а базис у тривимірному просторі має складатися з трьох одиничних векторів. Ще один одиничний вектор можна дістати, увівши в третє обмеження з коефіцієнтом + 1 штучну змінну х8, якій відповідатиме одиничний вектор .

Тепер можемо розглянути розширену задачу лінійного програмування:

за умов:

На відміну від додаткових змінних штучна змінна х8 має в цільовій функції Z коефіцієнт +М (для задачі на min) або –М (для задачі на max), де М — досить велике додатне число.

У розширеній задачі базисними змінними є х5, х6, х8, а решта змінних вільні. Початковий опорний план задачі такий:

Складемо першу симплексну таблицю цієї задачі:

Розраховуючи оцінки першого опорного плану, дістаємо: Z0 = –9M; Z1 – с1 = –8; Z2 – с2 = –10, Z3 – с3 = –М і т. д. Отже, ми отримуємо оцінки двох видів: одні з них містять М, а інші є звичайними числами. Тому для зручності розділимо оцінковий рядок на два. У перший оцінковий рядок будемо записувати звичайні числа, а в другий — числа з коефіцієнтом М.

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

Наступні кроки розв’язування задачі наведені у загальній таблиці:

Оптимальним планом задачі є вектор:

Х* = (57; 100; 9; 0; 0; 0; 0),

Отже, оптимальним є виробництво 57 одиниць продукції А, 100 одиниць продукції В і 9 одиниць продукції С. Тоді прибуток буде найбільшим і становитиме 1456 грн.

Фінансові ресурси фірми можуть використовуватися для вкладення у два проекти. За інвестування в проект А гарантується отримання через рік прибутку в розмірі 60 коп. на кожну вкладену гривню, а вкладення в проект В дає змогу отримати дохід у розмірі 2 грн на кожну інвестовану гривню, але через два роки. За фінансування проекту В період інвестування має бути кратним двом. Визначити, як потрібно розпорядитися капіталом у сумі 100 000 грн, щоб максимізувати загальний грошовий дохід, який можна отримати через три роки після початку інвестування.

Розв’язання. Нехай xij — розмір вкладених коштів у і-му році в проект j (i = ; j = 1, 2). Побудуємо умовну схему розподілу грошових коштів протягом трьох років.

Згідно з наведеною схемою можна записати математичну модель задачі.

Цільова функція: грошовий дохід фірми після трьох років інвестицій

.

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

для 1-го року ;

для 2-го року ;

для 3-го року .

Виконавши елементарні перетворення, дістанемо систему обмежень:

Отже, економіко-математична модель сформульованої задачі має такий вигляд:

за умов:

Очевидно, що ця задача є задачею лінійного програмування і її можна розв’язати симплекс-методом. Згідно з алгоритмом необхідно звести систему обмежень задачі до канонічної форми. Це виконується за допомогою додаткових змінних х1, х2, та х3, які введемо зі знаком «+» до лівої частини всіх відповідних обмежень. У цільовій функції задачі ці змінні мають коефіцієнт, що дорівнює нулю.

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

Оптимальним є такий план:

За такого плану інвестувань

Але задача має ще один оптимальний план, який можна дістати, вибравши розв’язувальний елемент у стовпчику «х12» останньої симплексної таблиці. Це може бути або число 1, або 1,6. Візьмемо як розв’язувальний елемент 1. Виконавши один крок перетворень симплекс-методом, дістанемо таку другу кінцеву симплексну таблицю:

Звідси:

Зобразимо використання грошових коштів фірми за першим оптимальним планом задачі у вигляді схеми:

Згідно з розглянутою схемою перший оптимальний план інвестування передбачає на перший рік усі кошти обсягом 100 000 грн вкласти в проект А, що дасть змогу одержати прибуток обсягом 60 000 грн, а загальна сума в кінці року становитиме 160 000 грн. На другий рік усі кошти в розмірі 160 000 грн передбачається витратити на фінансування проекту В. Наприкінці другого року фірма прибутку не отримає. На третій рік фінансування проектів не передбачається, але в кінці року прибуток фірми від минулорічних інвестицій проекту В становитиме 320 000 грн, а загальний грошовий дохід — 480 000 грн.

Такий же максимальний дохід можна мати, провівши інвестиції за схемою:

Згідно з другим оптимальним планом у першому році фірма спрямовує весь капітал у розмірі 100 000 грн на фінансування проекту В. Це уможливить одержання грошового доходу лише наприкінці другого року обсягом 300 000 грн, які на третій рік повністю інвестуються в проект А. Загальний грошовий дохід фірми за три роки діяльності за цим варіантом також становитиме 480 000 грн.

Якщо як розв’язувальний елемент в останній симплексній таблиці взяти число 1,6, то матимемо третій оптимальний план:

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

Типові замовлення на рулони нестандартних розмірів наведено в табл. 2.9.

Таблиця 2.9

ЗАМОВЛЕННЯ НА РУЛОНИ ПАПЕРУ

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

Розв’язання. Аби виконати спеціальні замовлення, які надійшли, розглянемо п’ять можливих варіантів розрізування стандартних рулонів, що можуть використовуватися в різних комбінаціях. Варіанти розкрою наведено в табл. 2.10.

Таблиця 2.10

МОЖЛИВІ ВАРІАНТИ РОЗРІЗУВАННЯ СТАНДАРТНИХ РУЛОНІВ ПАПЕРУ

Нехай xj — кількість стандартних рулонів паперу, які буде розрізано j-способом, .

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

1. Щодо кількості рулонів шириною 0,8 м:

2х1 + х2 + х3 = 150.

2. Щодо кількості рулонів шириною 1 м:

х3 + 2х4 = 200.

3. Стосовно кількості рулонів шириною 1,2 м:

х2 + х5 = 300.

Цільова функція задачі — це мінімальні загальні втрати паперу під час розрізування стандартних рулонів на рулони нестандартної ширини. Математично вона має такий вигляд:

.

Математична модель задачі загалом записується так:

за умов:

Для розв’язування цієї задачі застосуємо алгоритм симплекс-методу. Оскільки задачу сформульовано в канонічній формі, запишемо її відразу у векторній формі:

де

У системі векторів маємо лише один одиничний вектор . Тому в перше та друге обмеження введемо штучні змінні х6 та х7. Розширена задача матиме вигляд:

за умов:

Процес розв’язання задачі симплекс-методом подано у вигляді таблиці:

Згідно з останньою симплексною таблицею запишемо оптимальний план задачі:

Х* = (0; 150; 0; 100; 150), min Z = 120.

Визначений оптимальний план передбачає: щоб у повному обсязі виконати спеціальні замовлення, які надходять на паперову фабрику, необхідно розрізати 150 стандартних рулонів другим способом, 100 рулонів — четвертим і 150 — п’ятим. За такого оптимального варіанта розкрою обсяг відходів паперу буде найменшим і становитиме 120 м.