Методи дослідження операцій

МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

«КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ»

Методи дослідження операцій

Затверджено Методичною радою НТУУ «КПІ»

як навчально-методичний посібник для студентів вищих навчальних закладів

Дзюбан І. Ю.

Жиров О. Л.

Охріменко М. Г.

Київ 2005

УДК 519.8(075.8)

ББК 65вбя73

Д43

Рецензент: Г. П. Донець, доктор фізико-математичних наук, професор, завідувач відділу економічної кібернетики Інституту кібернетики ім. В. М. Глушкова НАНУ

Рецензент: Ф. А. Шевченко, директор головного центру інформаційних систем КНЕУ, професор кафедри інформаційного менеджменту

Дзюбан І. Ю., Жиров О. Л., Охріменко М. Г.

Д43 Методи дослідження операцій: навч.-метод. посіб./ І. Ю. Дзюбан, О. Л. Жиров, М. Г. Охріменко — К.: ІВЦ «Видавництво «Політехніка ««, 2005. — 108 с.: іл. — Бібліограф.: с. 104

ISBN 966−622−186−1

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

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

Для студентів, аспірантів і викладачів вищих навчальних закладів.

УДК 519.8(075.8)

ББК 65вбя73

ISBN 966−622−186−1

Вступ

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

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

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

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

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

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

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

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

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

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

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

Для розуміння тексту студентові достатньо володіти основами математичного аналізу, лінійної алгебри та аналітичної геометрії

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

1. Основні визначення дослідження операцій

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

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

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

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

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

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

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

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

2. Математична модель операції

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

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

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

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

Математичні моделі, які використовують у задачах ДО, можна грубо розділити на два види: аналітичні та статистичні.

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

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

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

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

Видатний фахівець з ДО Т. Л. Сааті в книзі дав таке іронічне визначення: «дослідження операцій — мистецтво давати погані відповіді на ті практичні питання, на які даються ще гірші відповіді іншими методами».

Але в досить простих, за сучасних досягненнях людського розуму, ситуаціях, у практичній діяльності людини ДО може надати ОПР корисну допомогу.

Перейдемо до аналізу найпростіших аналітичних моделей економіки.

3. Модель «затрати-випуск» В. В. Леонтьєва

Розглянемо найпростішу модель «затрати-випуск» — замкнену і статичну. Будемо вважати, що об'єкт економічної діяльності випускає найменувань продукції, де значок «*» при векторі означає операцію транспонування. Крім того,

де Z — вектор внутрішнього споживання продукції об'єктом;

Y — вектор кінцевої продукції (продукції, яка йде на продаж, у запаси, тощо).

Будемо вважати, що

де — невід'ємна матриця своїх елементів, які є коефіцієнтами прямих затрат при виробництві продукції. Або

(3.1)

У деталізованому вигляді матричне рівняння (3.1) має вигляд:

(3.2)

де — кількість продукції і-го виду, потрібної для виробництва одиниці продукції j-го виду. — компоненти вектора кінцевого випуску. Зміст компонентів вектора — кількість валового продукту відповідної номенклатури.

Будемо вважати, що технологічні коефіцієнти задано наперед. Модель (3.2) дозволяє за умов, коли, задано вектор Y, визначити розміри відповідних значень вектора валового продукту, виробничу собівартість випуску кожного виду продукції, матрицю повних затрат і дослідити на продуктивність матрицю А.

Матриця, А називається продуктивною (інколи вживають термін цілком продуктивна), якщо матриця не має від'ємних елементів. Матриця Е — одинична матриця розмірності (nЧn).

Приклад. Нехай матриця, А має вигляд

вектор .

Знайти:

а) матрицю повних затрат ;

б) вектор валового випуску ;

в) виробничу собівартість S₁, S₂, S₃, S₄ кожного виду продукції.

Розв’язування. Шукаємо матрицю

де — детермінант (визначник) матриці

(det B =):

Шукаємо вектор валового випуску :

Шукаємо виробничу собівартість S₁, S₂, S₃, S₄ :

Часто виникає необхідність встановлення факту продуктивності матриці без знаходження елементів матриці. Справедливі наступні твердження:

Твердження 1. Для продуктивності матриці достатнє виконання умов:

або

Твердження 2. Згідно з для продуктивності матриці необхідне і достатнє виконання таких умов:

існує рядок і₀ у матриці для якого виконується умова:

існує перенумерація рядків і стовпців матриці, для якої виконуються умови

Припустімо, що, тоді

.

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

Завдання для самостійних і контрольних робіт

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

4. Модель розподілу ресурсів

Модель «затрати-випуск» В.В. Леонтьєва характеризує лише деякі особливості закритого виробництва. Насправді ситуація складніша, оскільки за умови закритого виробництва необхідні початкові ресурси для початку виробництва, які під час функціонування економічної системи можуть відтворюватися, але в стартовій ситуації мають бути в наявності як складова частина виробництва. Залежно від кількості цих ресурсів прибуток буде різним, а тому виникає задача раціонального (оптимального) їх розподілу.

Будемо вважати, що, крім балансових рівнянь В.В. Леонтьєва (3.1), (3.2) у нашій моделі є критерій оптимальності:

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

Крім того, задано вектор, що характеризує запаси ресурсів, які є на виробництві. Задано матрицю з невід'ємними елементами, тоді можна записати

або

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

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

при

(4.1)

Якщо матриця продуктивна, то з (3.1) можна знайти, а підставивши х⁰ у (4.1) одержимо задачу: знайти такі, щоб

(4.2)

(4.3)

До виробничих (технологічних) обмежень можуть бути долучені і обмеження екологічного, соціального характеру та ін. Тому серед обмежень (4.2), (4.3) можуть бути і такі, що потребують виконання їх або нерівностей оберненого знака до (4.2), (4.3). У загальному вигляді задача оптимального розподілу ресурсів зводиться до розв’язання задачі лінійного програмування (ЗЛП).

5. Загальний вигляд задачі лінійного програмування

Потрібно знайти вектор, який забезпечує найбільше (max) або найменше (min) значення функції:

(5.1)

за виконання умов:

(5.2)

Числа — довільні дійсні числа.

Будемо вважати, що завжди в (5.1) стоїть знак «mах». Це припущення не зменшує загальності міркувань, адже заміною змінних будь-яку ЗЛП можна завжди звести до процедури максимізації L, якщо для L у (5.1) стояла вимога її мінімізації. Так само в (5.2) множенням на «-» правої та лівої частини нерівності, у якій стоїть знак «?», можна досягнути стандарту (5.2). Якщо в нерівностях (5.2) є знак «=», наприклад, при і₀-ій нерівності, тоді замість однієї рівності можна записати дві еквівалентні нерівності:

Задачу (5.2),(5.3) можна розв’язати за допомогою симплекс-методу [1], а задачі малої розмірності (n=2,3) — графічно.

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

Приклад. Знайти найбільше та найменше значення функції

якщо х₁ та х₂ задовольняють нерівностям (лежать в області D₁):

(6.1)

Розв’язування: — нормалі до прямих, які утворені заміною знаків «?» та «?» на знак «=». — нормаль до прямої

Будуємо область D₁ (рис. 1).

Рис. 1

Алгоритм побудови області D₁, може бути таким:

Будуємо прямокутник Р: ().

У побудованому прямокутнику шукаємо точки, які задовольняють першу нерівність Для цього будуємо пряму за двома точками перетину з осями координат (0, 6) та (6, 0). Пряма ділить прямокутник Р на дві частини. Та частина прямокутника, яка лежить у напрямку від прямої, має значення лівої частини рівності більші за 6 (у напрямку нормалі лінійна функція зростає), але щоб задовольнити першу нерівність треба розглядати всі значення х₁ та х₂ для яких ліва частина нерівності менша за 6. Цю умову буде виконано якщо в прямокутнику Р узяти частину, яка лежить на самій прямій та в напрямку антинормалі. Тобто, щоб задовольнити першу нерівність, треба брати точки прямокутника Р, які лежать на прямій і нижче від неї.

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

В одержаному трикутнику слід вилучити точки, які не задовольняють умову (третій нерівності в (6.1)). Будуємо пряму і вибираємо точки на прямій та поза прямою в бік антинормалі. Одержимо знову чотирикутник (див. рис. 1).

Завершуємо побудову області D₁, вилученням з одержаного чотирикутника точок, що не задовольняють нерівності. Це точки, які лежать поза прямою в напрямку антинормалі. Одержуємо п’ятикутник АВСDE. Переходимо до виконання пункту 2.

Шукаємо оптимальні розв’язки.

знаходиться в крайній точці області D₁, в напрямку нормалі до L, .

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

знаходиться шляхом обчислення функції L у точці перетину прямих l₂ та l₃ (напрям). Точку перетину знаходять як результат розв’язку системи рівнянь — значення функції L у точці перетину осі х₂ з прямою l₁ (напрям). Точку перетину знаходять через розв’язання системи рівнянь

Відповідь: .

Завдання для самостійних і контрольних робіт

Розв’язати графічно ЗЛП.

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

Алгоритм симплекс-методу дозволяє повністю дослідити ЗЛП. Якщо розв’язок існує, то його буде знайдено симплекс-процедурою, якщо розв’язку немає то в процесі реалізації симплекс-процедури буде встановлено факт його відсутності. Схема розв’язання має такий вигляд.

І. Згідно [1], записуємо ЗЛП (5.1), (5.2) в нормальному стандартному вигляді.

(7.1)

ІІ. Будуємо симплекс-таблицю.

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

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

ІІІ. Шукаємо допустимий розв’язок. Для цього побудуємо нову симплекс-таблицю (7.3), згідно наступних правил:

Беремо будь-який від'ємний елемент у першому стовпчику таблиці (7.2) (за винятком першого). Якщо такого елемента немає, переходимо до виконання пункту ІV.

Нехай таким елементом є b_m < 0.

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

У базовому стовпчику перебираємо всі елементи (крім першого), які мають однакові знаки з відповідними елементами першого стовпчика. Для них обчислюємо відношення, j₀ — номер базового стовпчика. Нехай j₀ =2, тоді m рядок призначаємо базовим, а елемент a_m2, який стоїть у клітинці, де перетинаються базовий рядок і базовий стовпчик, — базовим елементом. Проводимо взаємозаміну вільної та базової змінних, які відповідають базовому стовпчику та базовому рядку.

У базовій клітинці таблиці (7.3) записуємо елемент обернений до відповідного елемента табл. (7.2).

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

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

Усі інші елементи табл. (7.3) утворюються як результат додавання відповідного елемента табл. (7.2) та добутку відповідного елемента базового стовпчика табл. (7.3) на чисельник відповідного елемента базового рядка тієї самої таблиці.

Після заповнення табл. (7.3), повторюємо процедуру починаючи з п. 1, використовуючи як вихідну табл. (7.3).

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

ІV. Будуємо оптимальний розв’язок ЗЛП Знаходимо серед елементів першого рядка (крім першого елемента) додатні числа. Якщо таких елементів немає, переходимо до виконання п. V.

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

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

Зауваження 1. Якщо в задачі (5.1), (5.2) тоді в (7.1) перша нерівність виглядатиме так:

а в першій симплекс-таблиці перший рядок матиме такий вигляд:

Кінцева таблиця симплекс-процедури І-V у першій клітинці міститиме число, яке дорівнює

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

Приклад. Розв’язати ЗЛП

за умов

Розв’язування: Запишемо задачу в нормальному вигляді (виконаємо п.І).

Складаємо симплекс-таблицю:

Визначаємо базовий стовпчик і базовий рядок, перетин яких дає базовий елемент. Базовий елемент «-1». Будуємо нову таблицю.

Повторюємо симплекс-процедуру.

Записуємо фінальну симплекс-таблицю:

Відповідь:

Завдання для самостійних і контрольних робіт Розв’язати за допомогою симплекс-методу:

8. Спряжені (двоїсті) задачі лінійного програмування. Основні властивості

Розглянемо основну ЗЛП, записану (без зменшення загальності міркувань) у вигляді:

(8.1)

при обмеженнях

(8.2)

Розглянемо, також, задачу:

(8.3)

(8.4)

Задачу (8.3), (8.4) одержана із задачі (8.1), (8.2) згідно з такими правилами:

вільні члени обмежень (8.2) є коефіцієнтами нового критерію, а коефіцієнти в критерії - вільними членами в обмеженнях (8.4);

матрицею коефіцієнтів нових обмежень є матриця, що одержана транспонуванням матриці ;

у нових обмеженнях (8.4) знаки нерівностей протилежні знакам нерівностей (8.2);

максимізація критерію змінюється на мінімізацію критерія

Задача (8.3), (8.4) називається спряженою (двоїстою) до задачі (8.1), (8.2).

Не важко помітити, що задачу (8.1), (8.2) можна розглядати як спряжену відносно своєї спряженої задачі (8.3), (8.4) або

Властивість 1. Якщо одна зі спряжених задач (8.1), (8.2) чи (8.3), (8.4) має розв’язок, то й інша має розв’язок, причому виконується рівність:

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

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

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

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

1)

2)

Приклад. Сформулювати ЗЛП, спряжену до заданої:

Розв’язування Запишемо нерівності у формі (8.2):

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

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

Завдання для самостійних і контрольних робіт Розв’язати ЗЛП, спряжену до заданої.

9. Економічна інтерпретація основної та спряженої задач лінійного програмування

Основну ЗЛП (8.1), (8.2) можна інтерпретувати так. Нехай є n різних технологій для виробництва одного продукту. При цьому використовується m інгредієнтів (різні види сировини й інші виробничі фактори). За j-ю технологією за одиницю часу використовується одиниць і-го інгредієнта, загальний запас якого дорівнює і виробляється одиниць продукту. Нехай — час, протягом якого виробництво здійснюється за j-ю технологією. Тоді при «завданні» буде вироблено одиниць продукції і використано одиниць і-го інгредієнта ().

Природно виникає задача: відшукати такий оптимальний план, при якому за наявних запасів інгредієнтів виготовлялася б максимальна кількість продукції. Математична модель цієї ситуації - основна ЗЛП: максимізувати лінійну форму за обмежень Для економічної інтерпретації спряженої ЗЛП зручно ціну одиниці продукції, що виготовляється, узяти за одиницю. Тоді за j-ю технологією за одиницю часу створюється продукт ціною в грошових одиниць. На це витрачається одиниць першого інгредієнта, — другого інгредієнта, … , — m-го інгредієнта. Позначивши відносні ціни одиниці кожного інгредієнта відповідно для оцінки використаних ресурсів (у прийнятому масштабі цін) одержимо суму і очевидно, вона не менша за ціну одержаного продукту:

(9.1)

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

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

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

Властивість 2 можна трактувати так: якщо в деякому оптимальному плані виробництва витрати і-го інгредієнта строго менші за його резерви :

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

Далі, якщо в деякому оптимальному плані відносних цін сумарна вартість інгредієнтів, що використовуються за j-ю технологією, строго більша за ціну виробленого за цією технологією кінцевого продукту:

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

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

10. Задачі транспортного типу

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

Класична ЗТТ формулюється таким чином. Нехай є m пунктів відправлення продукції:, у яких сконцентровано запаси певного однорідного товару (вантажу) в кількості відповідно одиниць. Крім того, є n пунктів призначення:, які подали замовлення відповідно на одиниць товару. Припустімо, що сума всіх замовлень дорівнює сумі запасів:

(10.1)

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

Треба скласти такий план перевезень, щоб забезпечити виконання всіх замовлень і щоб сумарна вартість перевезень при цьому була мінімальна (найменша):

(10.2)

де — кількість товару, що перевозиться з пункту в пункт .

Побудуємо математичну модель цієї задачі.

Невід'ємні змінні (кількість яких) повинні задовольняти такі умови:

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

(10.3)

Сумарна кількість вантажу, що перевозиться в кожний пункт призначення з усіх пунктів відправлення, має дорівнювати замовленню для даного пункту. Це дає нам n умов-рівностей:

(10.4)

Має виконуватись умова (10.2):

(10.5)

Функція — лінійна, обмеження рівності (10.3), (10.4) також лінійні. Перед нами типова ЗЛП з обмеженнями-рівностями.

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

Неважко переконатися, що не всі n+m рівнянь (10.3), (10.4) незалежні. Дійсно, підсумовуючи всі рівняння (10.3) та (10.4) одержимо одне й теж саме число згідно з умовою (10.1). Отже, умови (10.3), (10.4) зв’язані однією лінійною залежністю, і фактично з цих рівнянь лише n+m-1, не n+m, лінійно незалежні. Це означає, що ранг системи рівнянь (10.3), (10.4) однаковий:

r = n+m-1,

а отже, можна розв’язати ці рівняння відносно n+m-1 базових змінних, виразивши їх через інші, вільні.

Підрахуємо кількість вільних змінних:

k = mn-(m+n-1) = mn - m — (n-1) = (m-1)(n-1).

Із розгляду ЗЛП відомо, що оптимальний розв’язок досягається в одній з вершин області допустимих розв’язків (ОДР), де хоча б k змінних перетворюється на нуль. У нашому випадку для оптимального плану перевезень хоча б (m-1)(n-1) значень повинні бути рівні нулю. Значення кількості одиниць ватажу, який направляється з пункту в пункт будемо називати перевезеннями.

Будь-яку сукупність будемо називати планом перевезень, або просто планом.

План будемо називати допустимим, якщо він задовольняє умови (10.3), (10.4) («балансові умови» - всі замовлення виконані, всі запаси вичерпані).

Допустимий план будемо називати опорним, якщо в ньому відмінні від нуля не більше r = n+m-1 базових перевезень, а всі інші дорівнюють нулю.

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

Розв’язок ЗТТ можна звести до деякої маніпуляції із симплекс-таблицями, які для цієї задачі будемо називати транспортними таблицями,

де ПП — пункт призначення вантажу; ПВ — пункт відправлення вантажу; усі інші позначення відповідають попереднім. Клітинки таблиці, у яких будемо записувати відмінні від нуля перевезення, називатимемо базовими, а порожні - вільними.

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

сума перевезень у кожному рядку таблиці має дорівнювати запасу даного ПВ;

сума перевезень у кожному стовпчику таблиці має дорівнювати розміру замовлення певного ПП;

сумарна вартість перевезень — мінімальна.

Надалі всі дії щодо знаходженню розв’язків ЗТТ будуть пов’язані з перетвореннями транспортної табл. (10.6). Для опису цих перетворень скористаємося нумерацією клітинок таблиці, подібної до нумерації клітин шахової дошки. Клітинкою (), або, будемо називати клітинку, яка стоїть в i-му рядку і j-му стовпчику транспортної таблиці. Наприклад, верхня ліва клітинка позначатиметься як (1, 1), яка стоїть під нею — (1,2) і т.д.

11. Знаходження опорного плану задачі транспортного типу

Розв’язок ЗТТ, як і кожної ЗЛП починається із знаходження опорного (допустимого) розв’язку, або, як будемо говорити, опорного плану. На відміну від загального випадку ЗЛП розв’язок ЗТТ завжди існує, оскільки сумарна вартість перевезень — невід'ємна обмежена знизу функція.

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

Приклад. Розглянемо таблицю:

Треба знайти опорний (допустимий) план.

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

Міркуємо таким чином. Пункт В₁ подав замовлення на 18 одиниць вантажу. Задовольнимо це замовлення за рахунок запасу 48, який є в пункті А₁, і запишемо перевезення 18 в клітинці (1,1). Після цього замовлення з пункту В₁ виконане, а в пункті А₁ залишилося ще 48−18=30 одиниць продукції. Задовольняємо за їх рахунок замовлення з пункту В₂ (27 одиниць). Запишемо 27 в клітинку (1,2). Три одиниці продукції в пункті А₁ призначимо пункту В₃. У складі замовлення В₃ залишилися незабезпеченими 39 одиниць. З них 30 покриємо за рахунок пункту А₂, чим його запас буде вичерпано, а ще 9 візьмемо з пункту А₃. Із 18 одиниць пункту відправлення А₃ 12 виділимо на пункт В₄; 6 одиниць, що лишилися, призначимо пункту В₅ і разом з 20 одиницями пункту А₄ повністю покриємо його замовлення. Одержимо:

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

Таким чином, складено план перевезень, що задовольняє балансові рівняння вигляду (10.3), (10.4). Одержаний розв’язок не тільки допустимим, а й опорний розв’язок ЗТТ.

Клітинки таблиці (11.2), в яких стоять ненульові перевезення — базові, їх кількість задовольняє умову r= n+m-1=8. Інші клітинки — вільні (порожні), їх кількість (m-1)(n-1)=12. Отже, план опорний і поставлене завдання побудови опорного плану виконане. Виникає запитання: а чи оптимальний за сумарною вартістю перевезень план отримано? Звичайно, ні. Адже під час побудови опорного плану зовсім не враховувалась вартість локальних перевезень. Природно, що цей план не зобов’язаний бути оптимальним. Дійсно, сумарна вартість цього плану складає:

.

Не важко переконатися, що коли перенесемо 18 одиниць з клітини (1,1) в клітину (2,1), а потім 18 одиниць з клітини (2,3) в (1,3), одержимо сумарну вартість перевезень:

Балансові співвідношення при цьому не були порушені. Отже, попередній план перевезень не був оптимальним.

12. Поліпшення плану перевезень

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

Циклом у транспортній таблиці будемо називати декілька клітинок, з'єднаних замкнутою ламаною лінією, яка в кожній з цих клітинок здійснює поворот на 90⁰. Наприклад, у табл.(12.1) зображено два цикли: перший з чотирма вершинами (2,1), (2,3), (4,3), (4,1) і другий з вісьмома вершинами (1,4), (1,6), (4,6), (4,4), (3,4), (3,5), (5,5), (5,4). Стрілками вказано напрямок проходження циклу. Не важко переконатися, що кожен цикл має парну кількість вершин, а отже, і парну кількість стрілок.

Домовимося відмічати знаком «+» ті вершини циклу, перевезення в яких збільшуються, а знаком «-» — вершини, в яких вони зменшуються. Цикл з вершинами, відміченими знаками «+» або «-», будемо називати орієнтованим. Знаки «+» та «-» у циклі будемо розставляти почергово, це означає, що у вершини зі знаком «+» дві сусідні мають знаки «-» і навпаки.

Перенести якусь кількість одиниць вантажу орієнтованим циклом означає збільшити перевезення у вершинах зі знаком «+», і зменшити перевезення на ту саму кількість вантажу у вершинах зі знаком «-».

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

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

Наприклад, для циклів зображених в табл. (12.1), ціна циклів відповідно дорівнює:

с₂₁ — с_{2 3}+ с₄₃ — с₄₁ і с₁₄ — с₁₆ + с₄₆ — с₄₄ + с₃₄ — с₃₅ + с₅₅ — с₅₄.

Позначимо ціну циклу через r. Із переміщенням одиниці вантажу по циклу вартість перевезення збільшиться на величину r; із переміщенням по ньому k одиниць вантажу вартість перевезень збільшиться на kr. Звідси випливає: щоб поліпшити план перевезень, треба здійснювати перевезення тими циклами, ціна яких від'ємна. Якщо кожного разу вдасться здійснити таке переміщення, то вартість плану зменшиться на величину kr.

Оскільки перевезення не можуть бути від'ємними, будемо користуватися лише тими циклами, «від'ємні» вершини яких лежать у базових клітинках таблиці. Якщо циклів з від'ємними числом r у таблиці не залишилося, це означає, що подальше поліпшення плану не можливе, тобто задачі (10.3), (10.4), (10.5) розв’язані.

Відшукати цикли з від'ємними вартостями можна використовуючи метод потенціалів.

Будемо вважати, що кожен із пунктів відправлення А_і вносить на перевезення одиниці вантажу (все одно куди) якусь суму, у свою чергу кожен із пунктів призначення також вносить за перевезення одиниці вантажу суму. Ці суми передаються третій особі («перевізнику»). Позначимо