11761

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

Книга

Математика и математический анализ

ВСТУП Дослідження операцій – це розділ прикладної математики що займається побудовою математичних моделей реальних задач і процесів економічних соціальних технічних військових і таких інших їх аналізом і застосуваннями. Більшість цих моделей пов’язані з отри...

Украинкский

2013-04-11

2.36 MB

79 чел.

ВСТУП

Дослідження операцій – це розділ прикладної математики, що займається побудовою математичних моделей реальних задач і процесів (економічних, соціальних, технічних, військових і таких інших), їх аналізом і застосуваннями. Більшість цих моделей пов’язані з отриманням рекомендацій для прийняття «оптимальних» рішень.

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

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

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

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

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

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

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

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

  1.  складання математичних моделей задач прийняття рішення;
  2.  питання  існування "оптимальних" рішень у різних класах задач;
  3.  розробка необхідних і достатніх ознак оптимальності;
  4.  розробка методів чисельного обчислення "оптимальних" рішень.

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


РОЗДІЛ 1.

МЕТОДОЛОГІЧНІ ОСНОВИ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ

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

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

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

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

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

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

- доматематичний (змістовний) аналіз проблеми;

- математичний аналіз проблеми;

- застосування результатів дослідження на практиці.

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

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

1. Визначення мети дослідження.

2. Складання плану розробки проекту.

3. Формулювання проблеми.

4. Збір даних (статистичних, експертних і інших).

5. Побудова математичної моделі.

6. Розробка обчислювального методу.

7. Розробка технічного завдання на програмування.

8. Перевірка математичної моделі та оцінку рішення.

9. Реалізація результатів на практиці.

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

Етапи 5-8 відносяться до математичної частини досліджень. Це  найскладніші і ключові етапи дослідження операцій. Етап 9 - заключна частина досліджень здійснюється спільними зусиллями замовників і математиків-розробників моделі.

1.2 Математичне моделювання. Загальна структура

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

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

- Хто приймає рішення ?

- Які цілі прийняття рішення для кожного ОПР ?

- У чому складається прийняття рішення ?

- Які можливості ОПР (з погляду прийняття рішень)?

- За яких умов відбувається прийняття рішення?

Формалізуючи (описуючи математично) відповіді на ці питання ми отримаємо необхідну модель задачі.

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

Потрібно скласти для фірми план добового випуску виробів таким чином, щоб дохід від їх продажу був максимальним.

Під час аналізу згаданих найважливіших факторів будемо виходити тільки з умови задачі. Тут:

- ОПР - орган планування (фірма);

- мета - максимізація прибутку від продажу випущених за добу виробів двох видів;

- прийняття рішення для ОПР полягає у визначенні добових обсягів випуску кожного з двох видів виробів;

- можливості ОПР обмежені часовими ресурсами експлуатації верстатів трьох видів;

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

Після виявлення найважливіших факторів слід аналізувати всі параметри задачі: значення яких параметрів відомо (задано); які параметри є невідомими (шуканими) величинами; якими з параметрів ми можемо керувати (керовані змінні), а якими немає (некеровані параметри).

У наведеному прикладі відомими є такі параметри:

  1.  добова норма b1 експлуатації верстата 1;
  2.  добова норма b2 експлуатації верстата 2;
  3.  добова норма b3 експлуатації верстата 3;
  4.  час aij обробки одиниці виробу виду i на верстаті типу j;
  5.  вартість с1  (продажу) одиниці виробу виду 1;
  6.  вартість c2 (продажу) одиниці виробу виду 2;

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

- обсяг добового випуску виробу виду 1;

- обсяг добового випуски виробу виду 2.

Ці два параметри можна вважати керованими, оскільки фірма сама визначає їх величину (виходячи з реальних умов).

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

x1 - обсяг добового випуску одиниць виробу виду 1;

x2 - обсяг добового випуску одиниць виробу виду 2.

Тоді прибуток від продажу x1 і x2 буде визначатися як c1 x1 + c2 x2,

а час, необхідний для обробки x1, x2 одиниць виробів на верстаті j - як

aij x1 + a2j x1 , (j = l,2,3).

Тепер поставлену задачу можна сформулювати математично:

c1 x1 + c2 x2  max,

a11 x1 + a21 x2  b1,

a12 x1 + a22 x2  b1,

a13 x1 + a23 x2  b1,

x1 0, x2  0.

Умови невід’ємності змінних випливає із сенсу величин x1 і x2 - це доповнення моделі відсутньою інформацією.

Наведений запис і є задачею математичного програмування з цільовою функцією c1 x1 + c2 x2 і множиною допустимих рішень X, що описується п'ятьма нерівностями (на площині це багатокутник, утворений перетинанням п'яти півплощин).

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

Позначимо через  N = {1,2,...,n} множину сторін, що приймають участь у даній конкретній задачі, де кожен елемент i множина N називаються особами, що приймають рішення (ОПР), наприклад, окрема особистість, фірма, плановий орган великого концерну, уряду та інші. Кожен елемент iN характеризується своїми можливостями. Позначимо через Хi множину усіх його допустимих рішень (стратегій, альтернатив). Припустимо, що такі множини математично описані: X1, X2,..., Xn.

Після цього процес прийняття рішення всіма ОПР зводиться до такого формальному акту: кожна з ОПР вибирає конкретний елемент x1X1, x2X2,…,xnXn  зі своєї припустимої множини рішень. У результаті отримується набір х = (x1,...,xn) обраних рішень, що називається ситуацією.

Формалізація цілей прийняття рішення здійснюється за такою схемою. Тим або іншим способом будуються аналітичні закони (функції) f1,....,fn, що ставлять у відповідність кожної ситуації x набір з n чисел f1(x), f2(x),...,fn(x).

Функція fi(x) = fi(x1,...,xn)  називається критерієм якості i-ої ОПР. Число fi(x) є кількісною оцінкою ситуації x для i-oї ОПР з погляду переслідуваної нею мети. Тому в моделі мета i-oї особи формалізується таким чином: вибрати таке рішення xiXi, щоб досягти найбільшого значення функції fi. Однак досягнення цієї мети цілком від нього не залежить з огляду наявності інших сторін, що впливають на загальну ситуацію x з метою досягнення своїх власних цілей. Цей факт перетинання інтересів (конфліктність) пояснюється тим, що функція fi крім xi  залежить і від інших змінних xj (i  j). Тому в моделях прийняття рішення з багатьма учасниками застосовуються складніші принципи оптимального поводження, ніж пряма максимізація або мінімізація  критерію якості.

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

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

<N; X1....,Xn; f1....fn; Σ >                                      (1.1)

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

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

1. Множина ОПР (N).

2. Критерії якості (f1,...,fn).

3. Множина допустимих рішень (X1,...,Xn).

4. Обмеження на параметри задачі, передумови, рівняння зв'язку (Σ).

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

<Х, f>                                                      (1.2)

У схемі (1.2) ОПР може розглядатися як орган планування, множина допустимих рішенні Х задається за допомогою обмежень на можливості ОПР, а критерій якості f називається цільовою функцією. При цьому задача оптимізації ставиться таким чином:

      max f(x)    (f(x)→max)                       (1.3)

                                             xX    xX

     min f(x)                        (f(x)→min)    (1.4)

                                            xX    xX

Це різна форма запису однієї і тієї ж задачі. Їх оптимальними розв’язками називаються пари x*, f(x*).

1.3 Етапи математичного моделювання. Приклади

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

1. Вивчення умови задачі (предметної області).

2. Визначення найважливіших факторів (див. підрозділ 1.2).

3. Виділення відомих і невідомих параметрів.

4. Виявлення керованих і некерованих параметрів.

5. Доповнення умови задачі відсутніми відомостями.

6. Введення системи позначень.

7. Побудова математичної моделі задачі (математичний опис найважливіших факторів, співвідношень і зв'язків між параметрами).

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

Приклад 1.2. (Розміщення замовлень). Фірма отримала замовлення на кілька тисяч нових виробів, що збираються з окремих блоків. Керівництво фірми прийняло рішення розмістити замовлення на виготовлення n блоків і вибрало n фірм-постачальників. Кожне замовлення настільки велике, що фірма-постачальник не може виконати більш одного замовлення. Кожному постачальнику запропоновано визначити вартість виконання замовлення, тобто ціну, по якій він готовий поставити фірмі різні блоки. Фірма повинна укласти n контрактів на постачання їй n видів блоків, мінімізувавши при цьому свої загальні витрати на придбання комплектуючих вузлів з боку.

Позначимо: i – номер (назва) блоку, i = 1,....n;  j – номер (назва) фірми-постачальника, j= 1,...,n; сij - вартість виконання i-ro блоку j-ої фірми (задане число). Крім того, введемо для кожного i і j число.

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

.

Обмеження задачі (на змінні хij) мають такий зміст:

1) кожен i-й блок повинен бути виконаний;

2) кожен постачальник j повинен виконати один (який-небудь) блок .

Математично ці умови запишуться відповідно як:

xi1+xi2 +…+xin =1,

xij+x2j+…+xnj =1...

Таким чином, приходимо до такого задачі оптимізації (моделі):

xij = 0 або 1 для всіх i,j.

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

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

ij = М (аi, - i) (аj - j)

прибутку для цінних паперів виду i і виду j.

Математична модель запишеться як

за обмежень:

;

;

xj  0, j = 1,…,n

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

Приклад 1.4 (Задача про рекламу). Фірма планує проведення радіо-рекламної кампанії по збуті автомобілів в одному з регіонів, де розташовано s радіостанцій, протягом двох тижнів. Фірма оцінила попередньо, що якщо радіостанції j виділити уj доларів, то чистий прибуток від збільшення збуту дорівнює Rj(yj) (Rj - функція реалізації прибутку від обсягу фінансування реклами). На рекламу виділена загальна сума, що дорівнює N доларам. Число рекламних оголошень на день не повинно перевищувати M. Якщо фірма виділила j-ій радіостанції уj доларів, то число рекламних оголошень буде Kj(yj)  (Kj - функція, що кожній виділеній сумі ставить у відповідність кількість рекламних оголошень на день, і вважається відомою). Як потрібно фінансувати s радіостанцій, щоб отримати сумарний максимальний прибуток від реакції збуту на рекламу ?

Очевидно, що математична модель має вид:

за обмежень:

   yj  0, j = 1,…,s.

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

Позначимо:

xt – випуск продукції протягом деякого відрізка t;

yt – рівень запасів на кінець відрізка t;

Dt – попит на продукцію для відрізка t;

Витрати на відрізку t (позначимо їх через Сt) залежать від випуску xt і рівня запасів yt, тобто є функцією від цих невідомих величин: ct = ct (xt, yt).

Вимога задоволення попиту в межах кожного часового відрізка означає, що рівень запасів на кінець відрізка t (тобто yt) повинен дорівнювати сумі – рівня запасів на початок відрізка t (тобто yt-1) і випуску продукції на відрізку t (тобто xt) мінус попит на відрізку t (тобто Dt).

Звідси отримуємо таку модель

за обмежень:

уt-1 + xt - yt = Dt,   t =1,2,…T;

yТ = 0,  xt, yt  0 для всіх t.

Тут y0 – заданий рівень запасів на початок планового періоду, а yТ  –рівень запасу на кінець періоду.                                        

Приклад 1.6. (Оптимізація схеми обслуговування). Система обслуговування складається з n типів різних приладів (наприклад каси в магазинах, телефонні лінії, автозаправні стовпчики та інші.). Кожен прилад у будь-який момент часу обслуговує не більш однієї заявки (наприклад покупця, телефонної розмови, автомобіля та інші.). Відома кількість приладів j-го типу і число заявок i-го типу, що прибули в систему на момент часу t. Відома також ефективність j-го приладу під час обслуговування заявки i-го виду. Потрібно розподілити вільні прилади за заявками таким чином, щоб сумарна ефективність була найбільшою.

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

Nj - кількість приладів j-го типу;

dit - число заявок i-го типу на момент часу t;

μij - ефективність j-го приладу під час обслуговуванні заявки i-го виду. Позначимо шукану величину через xij - число приладів j-го виду, відведених для обслуговування заявок i-го типу.

Цих даних досить для складання математичної моделі вигляду

за обмежень:

 

xij - цілі невід’ємні числа для всіх i, j, тут m і n задані числа кількості видів заявок і приладів.

Приклад 1.7. (Вибір оптимального виду посівної культури). Фермер може посіяти одну з трьох культур: A1, А2 або А3. Врожаї цих культур багато в чому залежать від погоди. Потрібно визначити, яку з цих культур сіяти, щоб забезпечити найбільший прибуток, якщо відома ціна аi одного центнера культури Ai, i = 1, 2, 3, і середня врожайність кожної культури в залежності від погоди (літо буде посушливим, нормальним або дощової). Достовірний прогноз погоди відсутній.

Позначимо через hij - врожайність i-ої культури за погодних умов j (тут j =1 –літа посушливе, j =2 – нормальне літо, j =3 – дощове літо). Числа hij, як і числа ai задані (відомі). Реально може мати місце тільки одна із ситуацій (i, j), i = l, 2, 3; j = l, 2, 3. Причому (i, j) означає, що посіяно культуру Aj, а погода знаходиться у стані j. Усього таких ситуацій дев'ять. Очевидно, що ОПР (фермер) може вибрати тільки вид культури, стан погоди від нього не залежить. Якщо фермер засіяв культуру A1, то він може отримати (залежно від стану погоди) один з таких прибутоків: a1h11, a1h12, a1h13, щодо культури A2: a2h21, a2h22, a2h23, і для культури А3: a3h31, a3h32, a3h3 . Запишемо всі ці результати в одну таблицю (матрицю):

.

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

Приклад 1.8. (Вибір асортименту товарів). На базі торгової організації є n типів одного з товарів асортиментного мінімуму. У магазин повинен бути завезений тільки один з типів даного товару. Потрібно вибрати той тип товару, що доцільно завезти в магазин. Якщо товар типу j буде користатися попитом, то магазин від його реалізації дістане прибуток pj, якщо ж він не буде користатися попитом – то збиток qj. Скласти математичну модель цієї задачі в умовах невизначеного попиту. Керуючись формалізацією задачі приклада 1.7, обґрунтуйте, що шукана модель має вид:

.

Поясніть задачу магазина на цій моделі.

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

Під час побудови математичної моделі припустимо, що проект складається з п'яти операція А, В, С, Д, Е. За умовою відома послідовність операцій і їх тривалість. Нехай ці дані будуть такими:

Операції

Безпосередньо попередні операції

Тривалість операцій

А

-

t

В

-

t

С

А

t

D

А

t

Е

B,D

tE

F

С,Е

-

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

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

yCD - момент початку операцій С і D;

yЕ - момент початку операції Е;

yF - момент початку операції F.

Тут, yF – момент завершення всього комплексу. Моменти yА і yВ – мо моменти 0 початку операцій, оскільки операції А і В не мають попередніх. При цьому математична модель має вигляд:

min yF

за обмежень:

yCDtA;   yEtB;   yEtD + yCD;   yFtC + yCD;   yFtE + yE .

1.4 Розділи і класи задач дослідження операцій

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

Якщо елементи математичної моделі (1.1) не залежать від часу, тобто процес прийняття рішення зводиться до миттєвого акту вибору точки із заданої множини, то задача ДО називається статичною. Інакше, тобто коли прийняття рішення є багатоетапним (дискретним) або неперервним (у часі) процесом, то задача ДО називається динамічною. Приклади 1.1-1.4, 1.7 і 1.8 відносяться до статичних, а приклади 1.5-1.6 і 1.9 – до динамічних задач. Задачі ДО, що не містять випадкових величин і ймовірносних явищ називаються детермінованими (приклади 1.1, 1.2, 1.4, 1.5, 1.9), задачі, що характеризуються випадковими величинами з імовірнісними оцінками –стохастичними (приклади 1.3, 1.4, 1.6), а задачі прийняття рішення в умовах невизначеності - конфліктними (приклади 1.7, 1.8).

Залежно від кількості ОПР в (1.1) розрізняють задачі оптимізації (1.2) і ігрові задачі (n ≥ 2, де n - число елементів на множині N).

Ігрова задача (або гра) – це математична модель задачі прийняття рішення в умовах конфлікту, тобто в тих ситуаціях, коли має місце протистояння інтересів двох або більш сторін. Залежно від характеру конфлікту розрізняють, антагоністичні (приклади 1.7, 1.8), неантагоністичні (безкоаліційні) і кооперативні ігри.

Якщо в задачі оптимізації всі елементи лінійні (цільова функція та обмеження), то отримуємо задачі лінійного програмування (приклади 1.1, 1.2), інакше – задачі нелінійного програмування (приклад 1.З і 1.4, якщо функції Rj, і Kj нелінійні). Якщо в задачі оптимізації присутній фактор часу, то вона називається задачею оптимального керування (приклад 1.5). Іноді такі задачі називають задачами динамічного програмування. Однак ця неточна назва, оскільки динамічне програмування – це назва методу розв’язання задач оптимального керування.

Часто в ОПР є не одна, а кілька цілей. Математична модель

<X; f1,…,fn; Σ >                                                (1.5)

такої задачі називається задачею багатокритеріальною (векторною) оптимізації. У моделі (1.5) ОПР вибирає рішення х  Х таким чином, щоб отримати як можна більші значення f1(x),...,fn(x) критеріїв.

Є такі класи задач ДО, що отримали свою назву, виходячи з їх призначення: системи масового обслуговування (приклад 1.6), задачі керування запасами (приклад 1.3), задачі мережного і календарного планування (приклад 1.9).

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

Задача оптимального розкрою матеріалу. Фірма виготовляє виріб, що складається з р деталей (наприклад комплект постільної білизни). Причому в один виріб ці деталі входять у кількостях k1,…,kr...З цією метою визначається розкрій m партій матеріалу. У i-ій партії є bi одиниць матеріалу. Кожну одиницю матеріалу можна розкроїти на деталі n способами. Під час розкрою одиниці i-ої партії j-им способом виходить аijr деталей r-го виду. Потрібно скласти такий план розкрою матеріалів, щоб з них отримати максимальне число виробів.

Транспортна задача. Є n постачальників і m споживачів деякого однорідного продукту. Відомі випуск продукції в кожного постачальника і потреби в ній кожного споживача, а також витрати на перевезення продукції від постачальників до споживачів.        

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

Задача про призначення на роботу. Є n робіт і n виконавців. Вартість виконання роботи i виконавцем j дорівнює cij. Потрібно розподілити виконавців на роботи так, щоб мінімізувати витрати.

Задача про суміші (про раціон). З m видів вихідних матеріалів, кожний з який складається з n компонент, скласти суміш, у якій зміст компонентів повинен бути не менше b1,...,bn. Відомі ціни одиниці матеріалів: c1...cm і питома вага j-гo компонента в одиниці i-гo матеріалу. Треба скласти суміш, у якій витрати були б мінімальними.

Задача про рюкзак. Є n предметів. Вага предмета i дорівнює p1, а його цінність – cі (i = l,…,n). Потрібно для заданої цінності вантажу вибрати сукупність предметів мінімальної ваги.

Задача про комівояжера. Є n міст і задана відстань cij між ними (i, j = = l....,n). Виїжджаючи з одного (вихідного) міста, комівояжер повинен побувати  в усіх інших містах по одному разові і повернутися у вихідне місто. Треба визначити, у якому порядку слід об'їжджати міста, щоб сумарна пройдена відстань була найменшою.

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

Задача про розподіл капіталовкладень. Є n проектів, причому для кожного проекту i відомий очікуваний ефект γj від його реалізації і необхідна величина капіталовкладень gj. Загальний обсяг капіталовкладень не може перевищувати заданої величини b. Потрібно визначити, які проекти необхідно реалізувати, щоб сумарний ефект був найбільшим.

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

1.5 Основні вимоги до математичних моделей і їх властивості

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

- адекватність (відповідність моделі своєму оригіналу);

- простота (відсутність другорядних факторів);

- об'єктивність (відповідність наукових висновків реальним умовам);

- чутливість (здатність моделі реагувати  на зміну параметрів);

- стійкість (малому збурюванню вихідних параметрів повинно відповідати мала зміна рішення задачі (моделі));

- універсальність (широта області застосування).

У теорії оптимізації на даний час розроблено велике число моделей і методів розв’язання різних класів задач (див. підрозділ 1.4). Тому під час побудови математичної моделі будь-якої задачі виникають проблеми ідентифікації: - чи можна використовувати відому модель для формалізації даної задачі?, а якщо ні, то у якій мірі потрібна переробка (пристосування) відповідної моделі ?

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

Ідентифікація моделі

Чи можливе пристосування?

Побудова нової 

модели

Чи підходить  задача до відомих моделей?

ні

ні

таккк

Вибір моделі

так

Ідентифікація методу розв’язання

Розробка нового методу

Чи можлива модифікація? 

Чи можливе розв’язання задачі відомими

методами

ні

ні

Вибір методу

так

такк

Розв’язання задачі

Приклад 1.10 (Задача розміщення підприємств). З метою розширення сфери діяльності фірма планує відкрити кілька нових філій. Пункт i є однією з можливих точок розміщення нової філії потужністю Si, а постійні витрати пов’язані з його експлуатацією, дорівнюють Fi ≥ 0 незалежно від фактичного обсягу випуску. Існує усього m можливих пунктів (i =1,2,…,m) розміщення, але відкривати філії у всіх цих пунктах нераціонально. Для кожного пункту i виготовлення і пункту j збуту відомі: cij ≥ 0 – сукупні виробничі і транспортні витрати; Fij ≥ 0 – деякі постійні витрати (Fij не залежить від обсягу перевезень xij > 0, однак для xij = 0 Fij = 0). Потрібно вибрати такі пункти розміщення нових підприємств, щоб сумарні витрати були мінімальні.

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

(сумарні транспортні витрати) (1.5)

за обмежень:

 (пропозиція);   (1.6)

 (попит);    (1.7)

xij ≥ 0 (обсяг перевезень)                       (1.8)

Для нашого прикладі введемо позначення:

Uij = min (аi,bj).

Тоді замість функції (1.5) отримаємо сумарні витрати у вигляді:

.    (1.9)

Замість обмеження (1.6) на потужності постачальників вводимо обмеження на пропускні здатності маршрутів

,    (1.10)

при цьому обмеження (1.7) по попиту споживачів залишається без змін:

   (1.11)

Побудову моделі ще не закінчено. Слід забезпечити щоб умова  xij > 0 виконувалося тільки у випадку, коли zij = 1. Це досягається за допомогою лінійних обмежень:

xijUij zij  для будь-яких i, j = 1,...,m   (1.12)

Крім того,

хij  ≥ 0,  i, j = 1,...,m     (1.13)

Тепер можна сказати, що математична модель (1.9)-(1.13) задачі прикладу 1.10 отримана у результаті модифікації моделі (1.5) - (1.8) класичної транспортної задачі.

1.6 Формалізація принципів оптимального поводження в моделях 

     прийняття рішення.

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

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

Принцип максимізації (мінімізації). Такий принцип застосовується, в основному, у задачах математичного програмування (див. підрозділи (1.2) - (1.4)).

Принцип згортки критеріїв. Застосовується при "оптимізації багатьох критеріїв одним координуючим центром (задача багатокритеріальної оптимізації (1.5)). Для кожного з критеріїв (цільових функцій) f1(u),...,fn(u) експертним шляхом призначаються "ваги" (числа) ,  причому αi показує "важливість або значимість" критерію f. Далі розв’язок x* з множини допустимих рішень Х вибирається такий, щоб максимізувати (чи мінімізувати) згортку критеріїв

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

f1(x), f2(x),...,fn(x).

Розв’язок х*Х  буде "краще" розв’язку хХ у сенсі лексикографічної переваги, якщо виконується одна з n+1 умов:

  1.  f1(x*) > f1(x);
  2.   f1(x*) = f1(x), f2(x*) > f2(x);
  3.  f1(x*) = f1(x), f2(x*) = f2(x), f3(x*) > f3(x);

……………….................................................

  1.  fi(x*) = fi(x) для i = 1,…, n-1,  fn(x*) > fn(x);

             n+1) fi(x*) = fi(x) для i = 1,…,n...

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

Принцип рівноваги. Це узагальнення принципу мінімаксу, коли у взаємодії беруть участь багато сторін, кожна з яких переслідує свою мету (прямого протистояння немає). Нехай число ОПР (учасників неантагоністичного конфлікту) є n. Набір обраних стратегій (ситуація) x1*, x2*,…,xn* називається рівноважним, якщо однобічне відхилення будь-якої ОПР від цієї ситуації може призвести хіба лише до зменшення його ж "виграшу". У ситуації рівноваги учасники не отримують “максимального” виграшу, але вони змушені дотримуватись її.

Принцип оптимальності по Парето. Даний принцип припускає в якості оптимальних ті ситуації (набори стратегій х1,…,xn), у який поліпшення “виграшу” окремого учасника неможливе без погіршення “виграшів” інших учасників. Цей принцип висуває слабкіші вимоги до поняття оптимальності, ніж принцип рівноваги. Тому Парето-оптимальні ситуації існують майже завжди.

Принцип не домінуючих результатів. Цей принцип є представником багатьох принципів оптимальності в кооперативних іграх (колективне прийняття рішень) і приводить до поняття "ядра" рішень. Всі учасники поєднуються і спільними погодженими діями максимізують “загальний виграш”. Принцип не домінуючих результатів – один із принципів “справедливого” розподілу між учасниками. Це та ситуація, коли жоден з учасників не може аргументовано заперечити проти запропонованого розподілу (елемента "ядра"). Існують й інші принципи оптимального розподілу загального сумарного виграшу.

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

Арбітражні схеми. Економічні конфлікти наводять на думку про арбітраж. Небажано щоб зіткнення інтересів переходили, наприклад, у відкриті погрози і контрпогрози. Повинні існувати соціальні механізми, що дозволяли б враховувати переваги і стратегічні можливості кожного учасника і забезпечили б “справедливе” розв’язання конфлікту. Такий механізм, будь то окрема особа або система голосування, називається арбітром.

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

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

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

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

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

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


РОЗДІЛ 2. ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

2.1 Попередні відомості теорії лінійного програмування.

Задача математичного програмування (1.3) або (1.4) називається задачею лінійного програмування (ЛП), якщо цільова функція f є лінійною функцією, а множина допустимих рішень Х задається лінійними нерівностями або рівняннями

min(max) f(x)=c1x1+c2x2+…+cnxn    (2.1)

                                   a11x1+a12x2+…+a1nxn b1;

a21x1+a22x2+…+a2nxnb2;     (2.2)

         …………………………

         ak1x1+ak2x2+…+aknxnbk;

  x1 ≥ 0,…, xn ≥ 0 ,                (2.3)

або у векторному вигляді

                                      (2.4)

де  

А = {,...,}; ,…, ; ; .

Наведена модель є стандартною постановкою задачі ЛП, у якій в системі обмежень (2.2) можуть бути різні відношення типу “ > ”, “ > ”, “ = ”. Тут c1,…,cn – коефіцієнти при цільовій функції, a11,...,ann – коефіцієнти при змінних в системі обмежень, b1,…,bk – вільні члени системи обмежень. Усі ці компоненти задачі ЛП є відомими (заданими) числами. Невідомими (шуканими) змінними будуть елементи вектора  {x1,…,xn}T.  При цьому задача ЛП полягає у тому щоб знайти такі значення змінних x1*,...,xn* (точку мінімуму (максимуму)), щоб вони, по-перше задовольняли обмеження (2.2) і (2.3) (умова допустимості), а, по-друге, щоб у точці х* = (х1*,...,xn*) цільова функція  f приймала мінімальне (максимальне) значення f(x*) (умова оптимальності). Аналогічно ставиться задача на мінімум. 

Крім стандартної форми запису задачі ЛП  є також загальна і канонічна форми запису. Загальна форма запису аналогічна стандартній за винятком того, що на значення вектору шуканих змінних {x1,…,xn}T не накладено ніяких обмежень за знаком.

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

  ;

;

 .

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

Приклад 2.1. Звести до канонічної таку загальну задачу ЛП:

    

Введемо додаткові змінні  x5 0 та x6 0 в друге і третє обмеження-нерівності. Крім того, замінимо x'2= - x2 0, а змінні x3 та x4, що не обмежені за знаком, запишемо у вигляді x3= x'3- x''3,  де x'3, x''3 0; x4= x'4- x''4, де   x'4, x''4 0. Таким чином, зводимо задачу до вигляду:

Приклад 2.2. Перехід від канонічної форми запису задачі ЛП до стандартної. Структура задачі ЛП залежить від рангу r системи обмежень. Якщо r < n, то n-r змінним, які називають небазисними, можна надавати будь-які значення, при цьому r змінні, що називаються базисними, можна визначити через небазисні. Розглянемо канонічну задачу ЛП:

Ранг системи обмежень дорівнює двом. Тому за небазисні змінні виберемо, наприклад, х1 та х4. Визначимо через них базисні змінні x2 та x3:

.

Оскільки х1 та х4 невід’ємні, то: 8+3/2x2 - x3  0; 2+5/2x2 0. При цьому цільова функція від небазисних змінних набуде такого вигляду:

10 +5x2 3x3  max.

Запишемо тепер задачу у стандартній формі:

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

,  ,  ,

де . Якщо ж обмеження задані у формі , то

,  ,  .

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

.

Введемо такі позначення:

, ,…,,,…,,...

Тоді канонічну задачу ЛП можна записати у вигляді:

,

.

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

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

Означення 2.2. Розв’язком задачі лінійного програмування називається її план, що мінімізує (або максимізує) лінійну форму.

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

.                               (2.5)

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

Помножимо зліва обидві частини виразу (2.5) на матрицю , що є матрицею, оберненою щодо матриці В , і як результат отримаємо

,                               (2.6)

звідки знайдемо вектор розв’язку  :

.                                       (2.7)

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

  .                                                  (2.8)

Розв’язок (2.8) називають базисним розв’язком системи з рівнянь з невідомими.

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

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

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

Означення 2.3. План задачі лінійного програмування будемо називати опорним, якщо вектори умов з додатними коефіцієнтами лінійно незалежні.

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

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

Невироджений опорний план утворюється перетинанням гіперплощин з n+m гіперплощин, що утворюють допустиму область розв’язків. У випадку виродженості в кутовій точці багатокутника розв’язків перетинається більше гіперплощин.

Теорема 2.1. (Основна теорема лінійного програмування):

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

Доведення. Доведення теореми засновано на такій лемі.

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

1) Нехай - деяка внутрішня точка (див. на рисунку зліва). Багатокутник обмежений, замкнений і має скінчене число кутових точок. – допустима множина.

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

Оскільки функція лінійна, то

.                                              (*)

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

.

Підставимо це значення в лінійну форму (*) замість і отримаємо

.

Оскільки, за припущенням, – оптимальна точка, то ми отримали протиріччя: . Отже, , - кутова точка.

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

,    і   ,

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

Теорема 2.2. Якщо відомо, що система векторів умов , лінійно незалежна, причому така, що

,

де всі , то точка є кутовою точкою багатокутника розв’язків.

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

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

1. Допустима множина розв’язків ЛП або порожня, або є опуклим багатокутником у Rn, що є перетинанням півпросторів, які описуються нерівностями (2.2)-(2.3)). Вона може бути обмеженою, так і необмеженою; у будь-якому випадку це замкнений багатокутник.

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

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

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

Методами розв’язання задач ЛП є графічний метод (у випадку двох змінних), або його різновиди (у загальному випадку).

2.2 Графічна інтерпретація розв’язання задач ЛП 

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

Знайти екстремум лінійної форми (2.1) за умови обмежень (2.2)-(2.3), при цьому, у цих виразах покладемо, що n=2. Кожна із нерівностей системи обмежень визначає півплощину, що обмежується прямою ai1x1+ai2x2=bi, (). Умови невід’ємності шуканих змінних визначають півплощини відповідно з граничними прямими x1=0, x2=0.

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

Якщо f = 0, пряма проходить через початок координат. Інші значення цільової функції є відстанню даної прямої від початку координат, помноженою на довжину вектора С=(с1, с2), координатами якого є коефіцієнтами при змінних лінійної форми. Нас цікавлять лише ті прямі, що відповідають лінійній формі, що мають спільні точки із сторонами багатокутника розв’язків. Задача ЛП, при цьому, полягає у тому, щоб, зміщуючи пряму лінійної форми, знайти спільну з нею таку точку багатокутника розв’язків, в якій лінійна форма приймає екстремальне значення.

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

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

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

2. Багатокутник планів задачі ЛП є необмеженим. Тоді лінійна форма може бути необмеженою на множині планів лише знизу або лише зверху, або і знизу і зверху.

3. Множина планів задачі ЛП порожня, тобто не існує багатокутника існування планів, які б не суперечили системі обмежень.

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

Алгоритм геометричної інтерпретації задач ЛП з двома основними змінними містить такі етапи.

  1.  У кожному обмеженні, що задане нерівністю, замінити знаки нерівностей на знаки рівнянь і провести на площині  відповідні їм прямі.
  2.  Знайти півпростір, заданий відповідним обмеженням-нерівністю.
  3.  Виявити багатокутник планів задачі.
  4.  Провести гіперплощину-пряму рівня цільової функції, що має спільні точки з багатокутником планів.
  5.  Визначити напрям зміщення прямої рівня цільової функції для досягнення екстремуму.
  6.  Знайти точку (або точки) багатокутника, де пряма рівня досягає екстремуму , або встановити її необмеженість на множині планів задачі.
  7.  Знайти координати точки розв’язання задачі ЛП, що і буде оптимальним планом задачі.

Приклад 2.3. (Випадок єдиного оптимального розв’язку). Використовуючи графічний метод, знайти розв’язок такої задачі ЛП:

max f(x) = x1- x2;

1+2х2 ≤ 14;

x1 – 4x2 ≤ 0;

3x1 – x2 ≥ 0;

–x1 + x2 ≤ 2;

x1 ≥ 0, x2 ≥ 0.

Розв’язок. На площині R2 будуємо припустиму множину, що описується шістьма нерівностями. Це буде перетинання шести півплощин, кожна з яких задається обмеженням-нерівністю на R2. Наприклад, першу з них 3x1+2х2 14 будуємо таким чином. Проводимо пряму 3x1+2х2 =14, що є границею цієї півплощини. Щоб визначити, яку з півплощин, що лежать з обох сторін від цієї прямої, описує нерівність 3x1+2х214, досить поставити в ній координати початку координат, тобто (0,0). Якщо нерівність виконується, то беремо ту півплощину, що містить початок координат, якщо не виконується, те беремо півплощину, що не містить початку   координат. У нашому випадку 3*0 + 2*0 ≤ 14.

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

Таким чином, геометрично, задача звелася до того, щоб у межах багатокутника ОАВС знайти точку х* = (x1*, x2*), у якій цільова функцій f(x*)  отримає максимальне значення.

Завдяки властивості 1.3  ми заздалегідь знаємо, що точкою максимуму нашої цільової функції є одна або деякі з вершин О,А,У або С. Для того, щоб визначити цю вершину, проведемо будь-яку лінію рівня цільової функції, тобто проведемо пряму f(x) = с1, де с=const. Для простоти візьмемо с=0, тоді лінія рівня є x1-x2 = 0. Збільшуючи праву частину цього рівняння (наприклад, x1-x2 = 1, x1-x2 = 3 і т.д.), ми знайдемо паралельний зсув лінії рівня вниз, причому, чим більше права частина, тим далі. Якщо ж зменшимо праву частину (наприклад, x1 --- x2 = -1, x1-x2 = - 2 і т.д.), то спостерігаємо зсув нагору.

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

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

Для нашої цільової функції f(x) = x1-x2 градієнт f = (1,-1). Як відомо, градієнт, що  перпендикулярний лінії рівня і показує напрямок зростання функції, а антиградієнт, тобто вектор -f показує напрямок убування функції. Отже, зміщуючи лінію рівня x1-x2=0 у напрямку вектору f, знаходимо точку максимуму С.

Координати точки С знайдемо розв’язуючи спільно рівняння ліній 1 і 2, що перетинаються у точці З: 3x1+2x2 = 14; x1-4x2 = 0/

Відповідь: х* = (4, 1) - точка максимуму, f(x*) = 3 - максимальне значення цільової функції.

Приклад 2.2. (Нескінченна  множина оптимальних розв’язків):

min f(x) = -x1-2x2

за обмежень

x1+2x2 ≤ 7;

2x1+x2 ≤ 8;

 x2 ≤ 3;

x1, x2 ≥ 0.

Як видно з рисунку ліворуч найвлучнішим вбік антиградієнти - (f = (1,2)) місцем торкання лінії рівня f(x) = с з припустимою множиною OABCD є грань ВС (тобто опуклість вершин B = (l, 3) і С = (3,2)). Тому будь-яка точка грані ВС є точкою мінімуму цільової функції.

Відповідь: х*=(1,3)+(1-)(3,2) = (3-2, 2+) для кожного [0, 1] - точка мінімуму, f(x*) = -7 - мінімальне значення цільової функції.

Приклад 2.3.  (Випадок  відсутності оптимуму через необмеженість цільової функції на припустимій множині):

min f (x) = - x1-2x2

за обмежень:

x1+x2  1;

2x1-x2  -1;

x1-2x2 ≤ 0;

x1, x2 ≥ 0.

Припустима множина цієї задачі являє собою необмежений багатокутник (див. на рисунку праворуч). При паралельному переносі лінії рівня f(x) = с уздовж антиградієнта -f = (1,2) вона завжди перетинає припустиму множину, тобто немає найвіддаленішої точки торкання, а цільова функція нескінченно убуває.

Відповідь: Точки мінімуму немає; цільова функція необмежена знизу.

Приклад 2.4. (Випадок відсутності оптимального розв’язку через порожнечу припустимої множин B):

max f(x) = x1+x2

за обмежень:  

-x1+x2 ≤ -1;

-x1-x2 ≤ -1;  

x1, x2 ≥ 0.

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

2.3 Змістовний опис симплекс-методу розв’язання задач ЛП

Нехай задача ЛП має оптимальний розв`язок. З геометричної точки зору це означає, що існує вершина багатокутника розв`язків, де лінійна функція досягає оптимального значення. Кожній вершині  багатокутника відповідає опорний план. А кожний опорний план визначається системою m лінійно незалежних векторів, що містяться серед n векторів A1, A2, ..., An  системи обмежень. Щоб знайти оптимальний план, досить розглянути лише опорні плани. Їх кількість не перевищує . Для великих значень m і n знайти серед них оптимальний простим перебором дуже важко. Тому необхідно мати такий аналітичний метод, що дає можливість цілеспрямовано розглядати опорні плани. Таким методом є симплексний метод. Виходячи з одного (початкового) опорного плану, симплексний метод забезпечує побудову нового опорного плану, що надає лінійній функції менші значення у порівнянні з попереднім планом. Цей процес продовжується поки не буде знайдено оптимальний план.

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

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

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

2.4 Знаходження початкового опорного плану

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

AX = A0,  A0  0,  X  0,

і серед векторів A1, A2, ..., An є одиничний базис, то початковим опорним планом буде вектор X = (b1, b2, ..., bm, 0, ..., 0).

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

Якщо перше рівняння системи поділити на три, а друге - на два, то дістанемо систему

Тут вектори A1, A2 i A3 утворюють одиничний базис і всі вільні члени додатні. Поклавши, що  x4 = x5 = x6 = 0, знайдемо опорний план, що визначається як  X = (2, 4, 5, 0, 0, 0).

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

                            

Розв’язання. Застосуємо метод повного виключення Гауса. Результати обчислень наведено у табл. 2.1, де ведучий елемент узято у рамку. З таблиці видно, що після третьої ітерації перетворень системи методом повного виключення дістали одиничний базис: A1, A2, A5 йому відповідає план X = (20, 6, 0, 0, 26).

Якщо обмеження задачі ЛП задано у вигляді нерівностей

A1x1 + A2x2 + ... + Anxn   A0,  X 0,  A0  0,

то, додавши до лівої частини кожної нерівності по невід’ємній змінній xn+1, xn+2, ..., xn+m,  дістанемо розширену систему лінійних обмежень 

A1x1 + ... + Anxn + An+1xn+1 + ... + An+mxn+m = A0,  X 0,  A0  0.

Змінні xn+1, xn+2,..., xn+m називають додатковими змінними. У лінійну функцію вони входять з нульовими коефіцієнтами. Отже, початкова задача лінійного програмування перетворилась у розширену: знайти оптимальне значення лінійної функції

F = c1x1 + c2x2 +...+ cnxn + 0 * xn+1 +...+ 0 * xn+m

за обмежень (1.5.3). Додаткові вектори An+1, An+2, ..., An+m утворюють одиничний базис m-вимірного векторного простору, а вектор X=(x1=0;...; xm=0; xm+1=b1;...; xn+m = bn+m) є опорним планом розширеної задачі.

Таблиця 2.1

Ітерація

A1

A2

A3

A4

A5

A0

1

2

0

3

-1

6

11

1

1

3

1

4

-1

12

20

2

0

-1

12

-1

14

26

1

2

0

3

-1

6

11

2

0

1

1

1

0

6

9

0

-4

-1

6

1

2

4

1

0

-2

1

-1

-6

-7

3

0

1

1

1

0

6

9

0

0

3

10

1

26

40

1

0

1

11

0

20

33

4

0

1

1

1

0

6

9

0

0

3

10

1

26

40

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

Застосовуючи симплекс-метод до розширеної задачі, поступово замінюють у системі базисних векторів додаткові вектори An+1, An+2, ..., An+m векторами початкової системи обмежень. Якщо лінійна функція досягла свого оптимального значення, а в системі базисних векторів є хоча б один додатковий вектор, наприклад An+i, то це означає, що i-те обмеження в початковій задачі має сенс строгої нерівності. Отже, початкова задача матиме оптимальний розв`язок (якщо його має розширена задача) і тоді, коли не всі додаткові вектори виключено із базису.

Часто, виділивши в системі обмежень одиничний базис і відповідний йому базисний розв’язок можна побачити, що знайдений розв’язок не є опорним планом системи обмежень, бо серед його змінних є і від`ємні. Для цілеспрямованого пошуку опорного плану треба від знайденого одиничного базису перейти до іншого. Для цього застосовують метод симплексного перетворення. Оскільки симплексні перетворення виконують над векторами A1, A2, ..., An, A0  системи обмежень, то ці вектори зведемо в табл. 2.2.

Таблиця 2.2

№ рядка

   A0

  A1

  A2

  ...

   Aj

  ...

An

1

  b1

  a11

  a12

  ...

  a1j

  ...

  a1n

2

  b2

  a21

  a22

  ...

  a2j

  ...

  a2n

...

  ...

  ...

  ...

  ...

  ...

  ...

  ...

...

...

I

  bi

  ai1

  ai2

  ...

  aij

  ...

  ain

...

  ...

  ...

  ...

  ...

  ...

  ...

  ...

...

...

M

  bm

  am1

  am2

  ...

  amj

  ...

amn

Нехай вектор A0  0, тобто всі bi  0, (i = 1, 2, ..., m). Цього можна досягти, помноживши рівняння з від`ємними членами на -1. Тепер у табл. 2.2 виділимо одиничний базис, не порушуючи невід’ємність компонент вектора A0. Зробити це можна за таким алгоритмом.

1. З неодиничних векторів A1, A2, ..., An взяти той, у якого є хоча б один додатний елемент. Нехай таким вектором буде Aj. Якщо такого вектора в таблиці немає, то це означає, що система обмежень несумісна і процес симплексного перетворення завершено.

2. Знайти відношення i елементів вектора A0 до відповідних додатних елементів вектора Aj, записати їх у відповідному рядку стовпця  і взяти з них найменше. Нехай таким буде деяке відношення     = bi / aij. Тоді елемент aij - ведучий, а рядок і стовпець таблиці, на перетині яких лежить aij, відповідно ведучі рядок і стовпець.

3. Коефіцієнти ведучого рядка (крім  i) таблиці поділити на ведучий елемент і записати у відповідному рядку нової таблиці.

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

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

Приклад 2.5. Знайти початковий опорний план для системи обмежень

.

Розв`язання. Записуємо коефіцієнти системи обмежень у табл.2.3. За ведучий візьмемо перший стовпець, оскільки вектор A1 має додатні компоненти. Знайдемо відношення 1=6/1=6 i 3=2. Менше з них знаходиться  у третьому рядку. Отже, ведучий елемент a31=1. Над елементами вихідної системи виконаємо симплексні перетворення. Після першої ітерації перетворень одиничними є вектори A1 і A5. Намагаючись знайти базис з векторів A2, A3, A4, візьмемо A2, що має додатний елемент a22 =2, який і буде ведучим. Виконавши симплексні перетворення, після другої ітерації маємо одиничний базис A1, A2, A5  і опорний план X = (2; 2; 0; 0; 6), що йому відповідає.

                                          Таблиця 2.3

Ітерація

Рядок

A0

A1

A2

A3

A4

A5

1

   6

   1

  -1

   1

  -1

1

   7

6

1

2

   4

   0

   2

  -1

  -3

0

   2

3

   2

1

   0

   2

   1

0

   6

2

1

   4

   0

  -1

  -1

  -2

1

   1

2  

2

   4

   0

2

  -1

  -3

0

   2

2

3

   2

   1

   0

   2

   1

0

   6

1

   6

   0

   0

 -3/2

 -7/2

1

   2

3

2

   2

   0

   1

 -1/2

 -3/2

0

   1

3

   2

   1

   0

   2

   1

0

   6

2.5 Знаходження оптимального плану

Розглянемо симплекс-метод знаходження оптимального плану на прикладі задачі ЛП:

F = c1x1 + c2x2 + ... + cnxn  min

за обмежень                                                            

де

                                  xj  0, ( j = 1, 2, ...,n ).

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

A1x1 + A2x2 + ... + Amxm + Am+1xm+1 + ...+Anxn = A0, X 0,

де

, , ..., ,

,

,

.

Вектори A1, A2, ..., Am – лінійно-незалежні одиничні вектори m-вимірного простору, і тому вони утворюють базис цього простору. За базисні змінні в системі обмежень виберемо x1, x2, ..., xm, а вільні змінні xm+1, ..., xn дорівнюємо до нуля. З урахуванням того, що bi 0 (i = 1, ..., m), знаходимо початковий план

X0 = (x1 = b1; x2 = b2; ...;  xm = bm;  xm+1 = 0; ...;  xn = 0).        (2.9)

Йому відповідає лінійна комбінація

x1A1 + x2A2 + ... + xmAm = A0 ,                             (2.10)

у якій вектори A1, A2, ..., Am лінійно незалежні. Отже, побудований початковий план є опорним. Він надає лінійній функції

F(X0) = c1x1 + c2x2 + ... + cmxm = f0 ,                           (2.11)

значення якої залежить тільки лише від значень m перших компонент вектору C = (c1, c2, ...,cn). Оскільки оптимальний план належить до опорних, то і оптимальне значення лінійної функції залежатиме від відповідних компонент вектора C.

Розглянемо, тепер, яким чином, виходячи з початкового опорного плану  (2.9), можна побудувати інший опорний план, який надасть лінійній функції значення меншого, ніж попередній план. Початковий опорний план визначається базисними векторами A1, A2, ..., Am.

Побудувати наступний опорний план, виходячи з початкового, можна завдяки переходу від базису A1, A2, ..., Am до нового базису. Такий перехід здійснюється за допомогою вибору вектора, який вводять у базис, і вибору вектору який виводять з нього. Знайдемо критерій вибору таких векторів.

Оскільки вектори A1, A2, ..., Am утворюють базис m-вимірного простору, то будь-який вектор системи A1, A2, ..., An  однозначно лінійно визначається через базисні

Aj = x1jA1 + x2jA2 + ... + xmjAm,  j = 1,2,...,n.                     (2.12)

Зауважимо, що коефіцієнти xij (i = 1, 2, ..., m) є компонентами вектору Aj в базисі A1, A2, ..., Am. У виразі  (2.12) вектору Aj відповідає єдине значення лінійної функції

 fj = c1x1j + c2x2j + ... + cmxmj,  j = 1,2,...,n.                   (2.13)

де ci  (i = 1, 2, ..., m) - коефіцієнти лінійної функції, що відповідають базисним векторам Ai  (i = 1, 2, ..., m). 

Значення fj знайдемо, якщо у вираз лінійної функції замість змінних підставимо відповідні коефіцієнти подання j-го вектору через базисні вектори. Нехай для деякого вектора, що не входить у базис, наприклад, Ak (k > >m), хоча б один з коефіцієнтів xik у виразі

x1k A1 + x2k A2 + ... + xmk Am = Ak                                 (2.14)

додатний. Виразу  (2.14) відповідає значення лінійної функції

c1x1k + c2x2k + ... + cmxmk = fk.                                 (2.15)

Задамо деяке, поки що невідоме додатне число . Помножимо на нього обидві частини рівностей  (2.14) і  (2.15) і результати віднімемо від  (2.10) і (2.11) відповідно:

     (x1 -  x1k)A1 + (x2 -  x2k)A2 + ... + (xm -  xmk)Am +  Ak = A0,   

 (x1 -  x1k)c1 + (x2 -  x2k)c2 + ... + (xm -  xmk)cm = f0 -  fk.       (2.16)

В останній рівності до обох частин додамо   ck:

  (x1 -  x1k)c1 + (x2 -  x2k)c2 + ... + (xm -  xmk)cm +  ck = f0 - (fk - ck). (2.17)

Лінійній комбінації відповідає новий план

X1 = (x1 -  x1k; x2 -  x2k; ...; xm -  xmk ;  0, ..., , ..., 0),

якщо його коефіцієнти невід`ємні. Ті компоненти вектору X1, до яких входять недодатні xik, будуть невід`ємними, бо  > 0. Компоненти вектору X1 з додатними xik  (i = 1, 2, ..., m) будуть невід`ємними, якщо

  ,                                               (2.18)

де мінімум береться серед тих i, для яких xik > 0. Отже, під час виконання даної умови вектор X1  буде опорним планом. Опорний план не може мати m+1 додатних компонент. Тому в плані X1 треба хоча б одну з компонент перетворити в нуль. Це можна зробити, якщо  вибрати так:

                  .                                         (2.19)

Оскільки розглядається невироджена задача, тобто всі її опорні плани містять рівно m додатних компонент, то мінімум в  (2.19) досягатиметься для єдиного значення i. Нехай i = l (1  l  m). Тоді для  0 = xl / xlk відповідні коефіцієнт виразу  (2.16) і компонента плану X1 перетворяться в нуль. Підставивши значення 0  в план X1, дістанемо лінійну комбінацію

x’1A1 + ... +  x’l-1Al-1 + x’l+1Al+1 + ... +x’mAm + x’kAk = A0 ,

і відповідний їй опорний план

X1 = (x’1,..., x’l-1, 0,x’l+1,..., x’m, 0,..., x’k,..., 0),

де

                                     (2.20)                                    

План X1 надає лінійній функції F значення  f0 -  0(fk - ck).

Отже, дістали новий опорний план, базис якого складається з векторів A1, A2, ..., Al-1, Al+1, ..., Am, Ak. Новий план X1 надає лінійній функції F значення F(X1) = f0 - 0(fk - ck), яке буде менше від F(X0), якщо fk - ck > 0. Величина різниці fk - ck називається оцінкою плану. Якщо для деякого вектора Ak оцінка плану fk - ck > 0, то план X0 не є оптимальним і можна побудувати новий план X1 такий, що F(X1)<F(X0). 

План X1 побудовано завдяки заміні вектора з початкового базису новим вектором. Критерій заміни векторів сформулюємо таким чином:

- у новий базис вводять вектор Ak , для якого оцінка плану додатна;

- із старого базису виводять той вектор Ai, для якого відношення xi / xik з додатними xik набуває найменшого значення.

Процес заміни векторів продовжують доти, поки всі оцінки плану не стануть від`ємними або нулями, або для деякої оцінки fj-cj >0 усі xij стануть не додатними, що означає, що побудований план є оптимальним.

Якщо на деякому кроці заміни для будь-якого j оцінка fj - cj >0 і усі xij  0, то це означає, що лінійна функція необмежена знизу на багатокутнику розв`язків і її значення може бути як завгодно малим. Зазначимо, що коли є кілька додатних оцінок плану, то вибирають найбільшу з них і той вектор, який відповідає цій найбільшій оцінці, вводять у новий базис. Якщо є кілька однакових найбільших оцінок, то можна вводити в новий базис будь-який з векторів, що відповідає цим найбільшим оцінкам. Якщо для деякого вектора Aj з додатною оцінкою плану є кілька однакових найменших відношень xi / xij, то з базису можна вивести будь-який з відповідних векторів, однак при цьому може виникнути явище зациклювання.

Нагадаємо, що компоненти нового плану можна обчислити за формулами  (2.20). Для перевірки побудованого плану на оптимальність треба знайти компоненти усіх векторів Aj  (j = 1, 2, ..., n) у новому базисі. Їх можна обчислити за формулами:

a’ij = aij - alj, i  l,                          (2.21)

a’ij = aij / alk, i = l.                                    (2.22)

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

Приклад 2.6. Знайти мінімум функції 

F=2x1+3x2+x3+4x4  

за такими обмеженнями:

Розв`язання. Відповідно загальним позначенням маємо

X = (x1, x2, x3, x4), C = (2; 3; 1; 4),

                , , , , .

Система обмежень містить два одиничні лінійно незалежні вектори A3  і  A4, які утворюють базис двовимірного векторного простору. Тоді вектори Aj  (j = 1, 2, ..., 4) описуються через базисні

A0 = x3A3 + x4A4 = 70A3 + 45A4,

A1 = x31A3 + x41A4 = 4A3 + 2.5A4,

A2 = x32A3 + x42A4 = 11A3 + 8A4,

A3 = x33A3 + x43A4 = 1*A3 + 0*A4,

A4 = x34A3 + x44A4 = 0*A3 + 1*A4.

Поклавши у системі обмежень x1=x2=0, дістанемо початковий опорний план X0 = (0, 0, 70, 45). Значення цільової функції F дорівнює F(X0) = =20 + 30 + + 170 + 445 = 250. Знайдемо оцінки початкового опорного плану. Для цього обчислимо значення fj (j = 1, ..., 4) за формулою  (2.13) як суму добутків компонент вектора Aj  на компоненти вектора C, які відповідають базисним векторам

f1 = 1  4 + 4  2.5 = 14;   f2 = 1 11 + 4 8 = 43;

f3 = 11 + 4  0 = 1;   f4 = 1 0 + 4 1 = 4.

Тоді оцінки плану визначаться як  f1  - c1 = 12,  f2 - c2 = 40,  f3 - c3 = 0,  f4 - c4 = 0. Серед них є дві додатні. Більшою є оцінка f2 - c2, що відповідає вектору A2. Отже, його вводимо в базис.

Щоб визначити, який з векторів A3, A4 треба вивести з базису, обчислимо відношення xi / xi2 (i =3, 4) для додатних xi2, тобто поділимо компоненти вектору A0 на відповідні додатні компоненти вектора A2: ,  . Меншим з обчислених відношень є відношення x4 / x42, яке відповідає вектору A4. Таким чином, замість вектора A4  як базис вводимо вектор A2. Новий базис утворюють вектори A2 і A3. У новому базисі вектори Aj  (j = 0, 1, ..., 4) мають такі вирази:

A0 = x’2A2 + x’3A3 ,

A1 = x’21A2 + x’31A3 ,

A2 = x’22A2 + x’32A3 = A2 + 0  A3 ,

A3 = x’21A2 + x’31A3 = A3 + 0  A2 ,

A4 = x’21A2 + x’31A3 ,

де x’i обчислюються за формулами  (2.20), а x’ij - згідно з формулами  (2.21) і  (2.22). Новий опорний план X1, який визначається базисними векторами A1 і A2, має вигляд X1 = (0, x’2, x’3,0). Обчислимо його компоненти: , .  

Отже, , а F(X1) = c2x’2 + c3x’3 =.

Обчислимо тепер компоненти векторів A1 i A4 у новому базисі:

 ,    ,

,   .

Тепер знаходимо значення   fj  (j = 1, 2, 3, 4):

,   f2 = 3 1+ 1 0 = 3,  f3 = 1 1 + 3 0 = 1; .

Нарешті, визначимо оцінку плану X1:  f1 - c1 =1 - 2= -1,  f2 - c2 = 0,  f3 - - c3 = 0,  f4 - c4 = -5.

Усі оцінки опорного плану X1 не додатні. Це означає що побудований план є оптимальним, тобто мінімум функції Fmin = 25 досягається за планом .

2.6 Застосування  симплекс-таблиць 

Розглянемо задачу лінійного програмування на знаходження мінімуму лінійної функції F = c1x1 + c2x2 + ... + cnxn  за системою обмежень

                              (2.23)

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

A1x1 + A2x2 + ... + Amxm + Am+1xm+1 + ...+Anxn = A0, X 0,       (2.24)

де              

, , ..., ,

,

,

Початковий опорний план X0 = (x1 = b1; ...; xm = bm;  0; ...; 0) задачі,  (2.23) визначається системою m-вимірних одиничних векторів A1, A2, ..., Am. Щоб дослідити його на оптимальність, треба вектори Aj  (j = 1, 2, ..., n) системи  (2.24) описати лінійною комбінацією базисних векторів і обчислити значення оцінок fj - cj.

Оскільки базис системи  (2.23) - одиничний, то коефіцієнтами у виразі вектора через базисні будуть його компоненти, тобто xij = aij (i = 1, 2, ..., m; j = 1, 2, ..., n). Обчислення наступного опорного плану та перевірку його оптимальності зручно виконувати, записавши умову задачі і дані, знайдені після побудови початкового опорного плану у симплексну таблицю. У першому її стовпці записано номери рядків таблиці. Стовпець базису містить базисні вектори. У стовпці C базису записано коефіцієнти даної лінійної функції, які відповідають базисним векторам. У стовпці A0 - початковий опорний план. У цьому самому стовпці в результаті обчислень знаходять оптимальний план.

Стовпці Aj  (j = 1, 2, ..., n) заповнено коефіцієнтами вектора Aj  через базисні вектори. У (m+1)-му рядку стовпця A0 записано значення лінійної функції F(X0), якого вона набуває при початковому опорному плані, а в стовпцях Aj - значення оцінок fj - cj. Оцінки можна обчислити, якщо від добутків елементів стовпця Aj на відповідні елементи стовпця C базису відняти відповідні коефіцієнти cj. Далі обчислення симплекс-методом слід здійснювати за таким алгоритмом.

1. Розглянути оцінку плану (m+1)-го рядка. Якщо всі оцінки не додатні, то опорний план X0 оптимальний і мінімум лінійної функції дорівнює F(X0). Якщо серед оцінок є хоча б одна додатна, то перейти до п.2.

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

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

3. Вибрати вектор з найбільшою додатною оцінкою. Нехай це буде вектор Ak. Перейти до п.4.

4. Обчислити відношення елементів стовпця A0 до відповідних додатних елементів стовпця Ak, результати записати у відповідних рядках стовпця   і перейти до п.5.

5. Серед векторів базису вибрати той, який відповідає найменшому з відношень, обчислених у п.4. Нехай це буде вектор Al. Перейти до п.6.

Коментар. Елемент xlk називається ведучим, рядок і стовпець, на перетині яких він міститься, називаються ведучими. Після визначення ведучого елемента заповнюють нову симплексну таблицю. Перші три стовпці нової таблиці відрізнятимуться від старої тільки рядком з номером l. У ньому замість елементів l, Ai, ci  будуть записані елементи l, Ak, ck. Інші клітини нової таблиці заповнюють згідно з пп.6 і 7.

6. Поділити елементи l-го рядка, які відповідають векторам Aj (j = 1, 2, ..., n), на ведучий елемент і результати записати у відповідні клітини l-го рядка нової таблиці. Перейти до п.7.

7. Для знаходження елементів і-го (i = 1, 2, ..., l-1, l+1, ..., m+1) рядка нової таблиці треба від елементів і-го рядка старої таблиці відняти відповідні елементи l-го рядка нової таблиці, помножені на xik (i  l). Після заповнення нової таблиці перейти до п.1.

Відзначимо, що коли у таблиці є кілька додатних оцінок плану, то під час обчислення у базис вводять вектор, якому відповідає максимальна оцінка. Завдяки такому вибору вектору можна досягти оптимального плану за мінімум ітерацій. Якщо ж є кілька рівних найбільших значень 0j(fj - cj), то з відповідних їм векторів вибирають той, якому відповідає min cj.

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

Задачу знаходження максимального значення лінійної функції можна розв`язати, не зводячи її до задачі мінімізації. План задачі знаходження максимуму буде оптимальним тільки тоді, коли його оцінки будуть невід`ємними. Якщо ж умова оптимальності не виконується, то під час обчислень в базис вводять вектор, якому відповідає min[0j(fj - cj)], де мінімум береться серед тих j, для яких fj - cj < 0. Якщо мінімальних оцінок кілька, то в базис вводять вектор, якому відповідає min cj.

Приклад 2.6. Знайти мінімум функції F=x1+x2+x3  за обмежень:

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

x1A1 + x2A2 + ... + x6A6 = A0 ,

де ; ; ; ; ; ; .

Дана система обмежень у явному вигляді містить одиничний базис A1 , A2 , A3 . Тому змінні x1 , x2 , x3 - базисні, а x4 , x5 , x6 - вільні змінні. Поклавши  x4 = x5 = x6 = 0, знайдемо початковий опорний план X0=(x1=0; x2=0; x3=0; x4=0; x5=0; x6=0), якому відповідає комбінація  x1A1 + x2A2 + x3A3 = A0  і значення функції F(X0) = 15 +13 + 15 = 13.

Для перевірки плану X0 на оптимальність заповнимо першу симплексну таблицю (табл. 2.4) і обчислимо значення оцінок:

f4 - c4 = 1(-1) + 12 + 12 - 0 = 3;

f5 - c5 = 10 + 1(-3) + 1(-5) - 0 = -8;

f6 - c6 = 1(-2) + 11 + 16 - 0 = 5.

Таблиця 2.4

Ітерація

Рядок

Базис

С базису

c1 = 1

c2 = 1

c3 = 1

c4 = 0

C5 = 0

c6 = 0

A0

A1

A2

A3

A4

A5

A6

1

1

A1

1

5

1

0

0

-1

0

-2

3

2

A2

1

3

0

1

0

2

-3

1

4

3

3

A3

1

5

0

0

1

2

-5

6

9

5/6

4

fj  -

cj

13

0

0

0

3

-8

5

13

2

1

A1

1

20/3

1

0

1/3

-1/33

-5/33

0

6

2

A2

1

13/6

0

1

-1/6

5/3

-13/ 6

0

5/2

13/10

3

A3

0

5/6

0

0

1/6

1/3

-5/6

1

3/2

5/2

4

fj  -

cj

53/6

0

0

-5/6

4/3

-23/6

0

11/2

3

1

A1

1

71/10

1

1/5

3/10

0

-21/10

0

13/2

2

A2

0

13/10

0

3/5

-1/10

1

-13/10

0

3/2

3

A3

0

2/5

0

-1/5

1/5

0

-2/5

1

1

4

fj  -

cj

71/10

0

-4/ 5

-7/10

0

-21/10

0

7/2

Для базисних векторів значення оцінок нульові. Серед обчислених оцінок є дві додатні. Більша з них  f6 - с6 = 5 відповідає вектору А6, який і введемо в базис. Для визначення вектора, який треба вивести з базису, обчислимо 06 . Мінімальне відношення відповідає вектору А3 базису. Отже, його треба замінити вектором А6. Ведучим елементом у першій симплексній таблиці є число 6, яке стоїть на перетині третього рядка і стовпця А6. Виконаємо одну ітерацію симплексних перетворень і заповнимо другу симплекс-таблицю. Нові елементи ведучого рядка знайдемо, поділивши елементи ведучого рядка початкової симплекс-таблиці на ведучий елемент (число 6). За допомогою обчисленого рядка знайдемо елементи інших рядків другої таблиці методом симплексних перетворень: помножимо його елементи на 2 і додамо до відповідних елементів першого рядка початкової симплекс-таблиці; віднімемо його елементи від відповідних елементів другого рядка; помножимо його на мінус 5 і додамо до четвертого рядка. В результаті дістанемо заповнену другу таблицю. Правильність проведених обчислень контролюємо за допомогою стовпця , кожний елемент якого обчислюється двома способами: за допомогою симплексних перетворень та додаванням елементів відповідних рядків. У другій симплексній таблиці маємо новий опорний план Х1=(20/3, 13/6, 0, 0, 0, 5/6), якому відповідає значення лінійної функції F(X1)=53/6< <F(X0)=13. У четвертому рядку таблиці маємо додатну оцінку f4 - с4 = 4/3.

Отже, вектор А4 вводимо до базису. Знайшовши 04, побачимо, що вектор А2 треба вивести із базису. Ведучий елемент стоїть на перетині другого рядка і стовпця  А4. Виконаємо один крок симплексних перетворень. У результаті дістанемо план Х2=(71/10,0,0, 13/10, 2/5). У четвертому рядку останньої симплекс-таблиці усі оцінки не додатні. Отже, план Х2 - оптимальний. Він надав лінійній функції значення F(X2)=71/10. На основі оцінок цього плану робимо висновок, що оптимальний план є єдиним, оскільки нульові оцінки відповідають тільки базисним векторам.

Приклад 2.7. Знайти максимум лінійної функції F = 40x1 + 30x2 за обмежень

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

Запишемо систему у векторній формі

x1A1 + x2A2 + ... + x5A5 = A0 ,

де ; ; ; ; ; . Одиничні вектори A3, A4, A5 утворюють базис тривимірного простору. Вони задають початковий опорний план Х0=(0; 0; 30; 24;20). Значення лінійної функції F(X0)=400+300=0. Для перевірки плану X0 на оптимальність складаємо симплекс-таблицю (табл. 2.5). Обчислимо значення оцінок плану f1=05+02+04=0, f2=06+06+02=0, f1 - - c1 =-40, f2 - c2 =-30.

Таблиця 2.5

Ітерація

Рядок

Базис

С базису

c1 = 1

c2 = 1

c3 = 1

c4 = 0

c5 = 0

A0

A1

A2

A3

A4

A5

1

1

A3

0

30

5

6

1

0

0

42

6

2

A4

0

24

2

6

0

1

0

33

12

3

A5

0

20

4

2

0

0

1

27

5

4

fj  -

cj

0

-40

-30

0

0

0

-70

2

1

A3

0

5

0

7/2

1

0

-5/ 4

33/4

10/7

2

A4

0

14

0

5

0

1

-1/2

39/2

14/5

3

A1

40

5

1

1/2

0

0

1/4

27/4

10

4

fj  -

cj

200

0

-10

0

0

10

200

3

1

A3

30

10/7

0

1

2/7

0

-5/14

33/14

2

A4

0

48/7

0

0

-10/7

1

9/7

54/7

3

A1

40

30/7

1

0

-1/ 7

0

3/7

39/7

4

fj  -

cj

1500/7

0

0

20/7

0

45/7

1565/7

Для векторів базису оцінки дорівнюють нулю. Серед обчислених оцінок дві від'ємні:  f1 - c1 = -40,  f2 - c2 = -30. Отже, опорний план Х0 не є оптимальним. Найменша оцінка відповідає вектору А1, який введемо в базис. Визначимо вектор, виключений з базису. Для цього обчислимо 01 = = min (30/5, 24/2, 20/4). Найменше з відношень відповідає вектору А5, тому його замінюємо вектором  А1. Ведучим елементом є число 4, яке стоїть на перетині третього рядка і стовпця А1. Складаємо другу симплекс-таблицю. Обчислимо нові значення ведучого рядка. Для цього елементи ведучого рядка поділимо на 4 і запишемо в третьому рядку другої таблиці. Тепер за допомогою цього рядка виконаємо одну ітерацію симплексних перетворень, тобто помножимо його елементи на 5 і віднімемо від першого рядка першої ітерації, потім помножимо його елементи на 2 і віднімемо від другого рядка першої ітерації, помножимо його на 40 і додамо до четвертого рядка першої ітерації. Правильність проведених обчислень контролюємо за допомогою стовпця , кожний елемент якого обчислюється двома способами: за допомогою симплексних перетворень і підсумовуванням елементів відповідних рядків.

Після завершення другої ітерації дістали план Х1=(5; 0; 5; 14; 0), якому відповідає значення лінійної функції F(Х1)=200. У четвертому рядку  f2-c2=-10 < 0, тому  план  Х1   не  є  оптимальним  і  вектор  А2   слід ввести в базис. Обчислимо 02 =min(10/7, 14/5, 10)=10/7. Число 7/2 стоїть на перетині першого рядка і стовпця А2, є ведучим. Вектор А3 вилучаємо з базису. Виконавши третю ітерацію симплексних перетворень, дістанемо нову таблицю. Оскільки в четвертому рядку всі оцінки плану  Х2 = ( 30/7; 10/7; 0; 48/7; 0)  невід’ємні, то опорний план Х2 - оптимальний, йому відповідає значення лінійної функції F(Х2)=1500/7.

Зазначимо, що кожне число, записане в таблиці, має не тільки математичний. а й певний економічний зміст. Так, у четвертому рядку першої ітерації симплексної таблиці 5 є дві від’ємні оцінки:  f11=-40, f2-c2=-30. Число 40  означає,  що від включення до плану  виробництва одиниці  продукції  Р1 прибуток збільшиться  на 40 у.о. Якщо включити до плану виробництва одиницю продукції Р2, то прибуток збільшиться на 30 у.о. Тому з економічного погляду доцільніше включати до плану продукцію Р1. Цей висновок цілком узгоджується із формальним критерієм оптимальності опорного плану симплексного методу, оскільки найменша оцінка відповідає вектору А1. Число 01=5  означає, що максимальна кількість продукції, яку можна включити до плану виробництва, дорівнює п’яти одиницям. При цьому сировину третього  виду буде використано  повністю.

Після завершення другої ітерації у колонці А0 дістали опорний план Х1=(5; 0; 5; 14; 0). Згідно з цим планом виробляється 5 одиниць продукції Р1 і залишається невикористаною 5 одиниць сировини S1 і 14 одиниць сировини S2. Прибуток від реалізації виробленої продукції становить 200 у.о. В результаті симплексних перетворень змінилася не тільки колонка А0, а й інші колонки таблиці. Їх економічний зміст став ще складнішим.  Розглянемо, наприклад, колонку А2. Число Ѕ в третьому рядку показує, на скільки одиниць треба зменшити виробництво продукції Р1, якщо запланувати випуск продукції Р2. Числа 7/2 і 5 у першому і другому рядках  колонки А2 означають, скільки треба витратити одиниць сировини  S1 і S2 відповідно, якщо запланувати  виготовлення одиниці продукції  Р2.  Число 10 у четвертому рядку означає, що прибуток, який буде одержано від реалізації одиниці продукції  Р2, становитиме 10 у.о. Інакше кажучи, включення до плану  виробництва одиниці продукції Р2 зумовлює зменшення  випуску продукції Р1 на Ѕ одиниці і додаткові затрати 7/2 одиниць сировини S1 і 5 одиниць сировини S2, а загальний прибуток від реалізації продукції відповідно  до нового плану зросте  на 10 у.о. Дещо інший економічний зміст мають числа, записані в колонці А5. Число 1/4 в третьому рядку цієї колонки означає, що збільшення обсягу сировини  S3  на  1 одиницю дасть змогу збільшити випуск  продукції Р2 на 1/4 одиниці. Одночасно треба буде додатково взяти 5/4 одиниці сировини S1 і 1/2 одиниці сировини S2. Збільшення випуску продукції Р2 на  1/4 одиниці забезпечить збільшення прибутку на 10 у.о. З економічного аналізу даних таблиці після другої ітерації випливає, що план Х1 не є оптимальним. Це видно і з четвертого рядка симплекс-таблиці, оскільки у колонці  А2 - від’ємна оцінка плану.

Після третьої  ітерації знайшли оптимальний план Х2=(30/7, 10/7, 0, 48/7, 0) випуску продукції, який включає виробництво 30/7 одиниць продукції Р1 і 10/7 одиниць продукції Р2. При такому плані  випуску продукції буде повністю використано сировину першого і третього видів  і залишиться невикористаною 48/7 одиниць сировини другого виду. Прибуток від реалізації запланованої продукції становитиме 1500/7 у.о.

2.7 Метод штучної бази

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

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

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

Зауваження до симплекс-методу.

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

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

3. Слабкі змінні зі знаком " + ", що вводяться для канонізації нерівностей можна використовувати як базисні.

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

2.8 Двоїсті (спряжені) задачі лінійного програмування

Модель пари двоїстих задач у загальній формі. В загальному випадку для кожної задачі ЛП у загальній формі запису можна поставити у відповідність двоїсту (спряжену) для неї задачу (табл.2.6, 2.7).

Таблиця 2.6

Вихідна задача ЛП

Спряжена задача ЛП

Таблиця 2.7

Моделі спряжених задач

Симетричні моделі

Несиметричні моделі

Вихідна

Спряжена

Вихідна

Спряжена

Правила формування двоїстих задач формулюються таким чином.

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

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

3. Коефіцієнти лінійної форми спряженої задачі є вільними членами системи обмежень вихідної задачі.

4. Вільні члени системи обмежень спряженої задачі є коефіцієнтами лінійної форми вихідної задачі.

5. Кожній змінній прямої задачі відповідає одне обмеження спряженої задачі, причому якщо j-а змінна невід’ємна, то j-им обмеженням спряженої задачі буде нерівність із знаком  (не менше) і навпаки; змінним, які не мають обмеження на знак, відповідають обмеження рівності.

6. Кожному обмеженню прямої задачі відповідає одна змінна спряженої задачі, причому, якщо і-е обмеження нерівністю типу  (не більше), то і-а змінна спряженої задачі – невід’ємна; обмеженням у вигляді рівностей відповідають змінні без обмеження на знак.

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

Основні теореми двоїстості. Властивості основної теореми двоїстості можна описати у вигляді таблиці (табл. 2.8).

  Таблиця 2.8

Двоїста задача

Пряма задача

Має плани

Немає планів

Має плани

max F(x)=min G()

min G()

Немає планів

Max F(x)

Можливо

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

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

Наприклад, у задачі               

розв’язок якої наведено у таблиці нижче, з останньої таблиці знаходимо, що  . Аналогічно з індексного рядка кінцевої таблиці, що відповідає оптимальному плану двоїстої задачі, маємо, що xj*=  m+jпод , j=1,n. 

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

I

Б

C

X

3

2

0

0

Р1

Р2

Р3

Р4

1

Р3

0

2

1

-1

1

0

2

Р4

0

6

2

1

0

0

m+1

0

-3

-2

0

0

I

Б

C

X

3

2

0

0

1

Р3

3

2

1

-1

1

0

2

Р4

0

2

0

3

-2

1

m+1

6

0

-5

3

0

I

Б

C

X

3

2

0

0

Р1

Р2

Р3

Р4

1

Р3

3

8/3

1

0

1

1/3

2

Р4

2

2/3

0

1

-2/3

1/3

m+1

6

0

0

-1/3

5/3

I

Б

C

X

3

2

0

0

Р1

Р2

Р3

Р4

1

Р3

0

8

3

0

1

1

2

Р4

2

6

2

1

0

2

m+1

6

1

0

0

3

Приклад 2.8. Сформулюємо задачу, двоїсту до такої задачі:

Перепишемо систему обмежень у вигляді

Тоді двоїста задача набуде вигляду

Приклад 2.9. Розв'язати ЗЛП за допомогою геометричної інтерпретації двоїстої задачі:

Двоїста їй задача має вигляд:    

а її геометрична інтерпретація зображена на рисунку нижче.

Пряма рівняння G() досягає найменшого значення в точці А, де ,. Тоді  G()=23  внаслідок основної теореми F(X*)=23.

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

З оптимального плану спряженої задачі маємо, що в другому та третьому співвідношеннях виконується рівність, тоді X2, X3, в той час як X1= 0,  X4=0 оскільки в першому та четвертому співвідношеннях рівність не виконується.

З другої групи умов доповняльної нежорсткості маємо

Оптимальні значення змінних вихідної задачі знайдемо з рівнянь

Тобто, x2 = 4, x3 = 7. Оптимальний план вихідної задачі  X* = (0, 4, 7, 0); L(X*)= 23.

Приклад 2.10. Критерій оптимальності плану ЗЛП.

Перевірити, чи буде план Х =(0,1,0,3) оптимальним планом для наведеної нижче задачі лінійного програмування.

Сформулюємо двоїсту задачу:

1 +2  min,

31 +2  1,

1 –22  4,

                                            1  1, 2  –1,

Як наслідок другої теореми двоїстості маємо з умов додатності змінних x2 та x4, що друге та четверте обмеження двоїстої задачі мають виконуватися як рівності, тобто:  Розв’язок цієї системи рівнянь 2 -1. Він задовольняє також перше й третє обмеження-нерівності двоїстої задачі. Умови ж другої теореми повністю задовольняються, що свідчить про оптимальність плану  Х.

РОЗДІЛ 3.

ТРАНСПОРТНІ  ЗАДАЧІ  (Т-ЗАДАЧІ)

3.1 Математична структура Т-задач 

Припустимо, що деякий однорідний продукт (вантаж), який зосереджено у m постачальників, по ai одиниць у кожного (), потрібно перевезти n споживачам у кількості не менше як bi одиниць у кожному (). Відома вартість перевезення одиниці вантажу від і-го постачальника до j-го споживача cij. Необхідно знайти такий план перевезень продукції від постачальників до споживачів, за яким загальні витрати Z на транспортування були б мінімальними.

Для побудови математичної моделі такої задачі введемо матрицю плану перевезень X = (xij), елементи якої означають обсяг перевезень продукції від і-го постачальника до j-го споживача. Тоді для загальних транспортних витрат для обсягу продукції, що вивозиться від кожного постачальника і для обсягу продукції, яка надходить до кожного із споживачів можна записати такі вирази:

        

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

.

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

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

  1.  Загальний запас продукції в постачальників перевищує загальні потреби з боку споживачів:

У даному випадку, якщо ввести до розгляду додаткового (n+1)-го фіктивного споживача з потребою

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

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

У таких випадках може виникати інша задача: як оптимальним чином перевезти наявну продукцію (можливо і недостатню для задоволення потреб). Така нова задача може бути розв’язана введенням фіктивного (m+1) постачальника із запасом продукції am+1. При цьому, питомі вартості перевезень за фіктивними маршрутами вважаються рівними нулю, а обсяги перевезень xm+1,j за цими маршрутами розглядаються для відповідних споживачів як недопостачання продукції через її дефіцит.

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

Таблиця 3.1

Пункти

відправлення (ПВ)

Пункти доставки (ПД)

Запаси аі

B1

Bk

Bn

A1

c11

x11

c1k

x1k

C1n

x1n

a1

Al

cl1

xl1

clk

xlk

cln

xln

aL

Am

cm1

xm1

cmk

xmk

cmn

xmn

am

Потреби bj

B1

bk

bn

a

3.2.  Визначення початкового опорного плану Т-задачі

Розв’язання Т-задачі починається з побудови опорного плану. Опорний план містить не більше ніж m+n -1 (значення рангу системи обмежень Т-задачі) додатних компонент: невироджений план містить m+n-1, а вироджений план - менше ніж m+n-1. Є кілька простих способів знаходження початкового опорного плану Т-задачі, серед яких найпоширенішими є діагональний метод північно-західного кута, метод мінімальної вартості і метод подвійних позначок.

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

1. Знаходимо x11 початкового плану, що дорівнює меншому з чисел a1,b1, тобто x11=min(a1,b1), а всі інші елементи першого стовпця (якщо a1>b1 , то x11=b1), або першого рядка (якщо a1<b1 то x11=a1), або і першого стовпця і першого рядка (якщо a1=b1, то x11=a1=b1) матриці перевезень покладемо такими, що дорівнюють нулю. Визначимо a(1)1=a1 - x11, b(1)1=b1 -x11.

2. Далі розглянемо незаповнену частину таблиці після k ітерацій, тобто ту частину, що містить ще невизначені елементи матриці перевезень. Нехай її верхній лівий елемент є x (k+2). Виконаємо (k+1) ітерацію. Повторимо всі кроки першої ітерації, тобто знайдемо

Якщо a(k) b(k) то заповнюємо нулями -й рядок, починаючи з (+1)-го елемента. Якщо ж a(k) >b(k) то заповнюємо нулями -й стовпець. Коли ж х=a(k)=b(k) , то нулями заповнюються як -й рядок так і -й стовпець. Обчислюємо , . На цьому (к+1) ітерація закінчується.

Через обмеженість числа елементів  ai, i=1,m та bj, j=1,n описаний алгоритм скінчений. Так, наприклад, для  задачі, вихідні дані якої задані в табл. 3.2, початковий опорний план, побудований методом північно-західного кута, ілюструється у табл. 3.3.

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

Таблиця 3.2

ПВ

ПД

ai

B1

B2

B3

B4

A1

7

4

2

3

50

A2

1

5

6

2

50

A3

3

8

7

6

100

bj

90

80

20

10

200

Таблиця 3.3

ПВ

ПД

ai

B1

B2

B3

B4

A1

50

50

A2

40

10

50

A3

70

20

10

100

bj

90

80

20

10

200

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

Таблиця 3.4

ПВ

ПД

ai

B1

B2

B3

B4

A1

(10)7

(6)4

20

(3)2

20

(4)3

10

50

A2

(1)1

50

(7)5

(8)6

(2)2

50

A3

(5)3

40

(12)8

60

(11)7

(9)6

100

bj

90

80

20

10

200

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

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

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

Таблиця 3.5

ПВ

ПД

ai

B1

B2

B3

B4

A1

7

*       4

30

**    2

20

3

50

A2

**     1

50

5

6

*      2

50

A3

*       3

40

8

50

7

6

10

100

bj

90

80

20

10

200

3.3 Властивості опорних планів Т-задач

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

Сукупність усіх базисних клітинок та однієї вільної клітинки Транспортної задачі завжди утворює цикл. Позначимо приєднану небазисну клітинку знаком "+", наступну в утвореному циклі (базисну клітинку) - знаком "-", третю - знаком "+" тощо. Оскільки число клітинок циклу парне, то він розпадається на два півцикли з однаковою кількістю клітинок – від’ємний півцикл, утворений клітинками із знаком "-", і додатний, утворений клітинками із знаком "+".

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

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

3.4 Розв’язання Т-задач методом потенціалів

Метод потенціалів грунтується на розв’язанні двоїстої до транспортної задачі, яка має вигляд

для системи обмежень

i+j сij , i=1,m,  j=1,n,

де i  - потенціали постачальників, j - потенціали споживачів.

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

1. Для базисних клітинок, де xij>0, i+jij.

2. Для небазисних клітинок, де xij=0, i+j сij.  

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

Алгоритм методу потенціалів

1. Знаходимо опорний план транспортної задачі, який би задовольняв першу умову потенціальності плану для базисних клітинок, загальна кількість яких m+n-1, тобто i+jij.

2. Утворена система рівнянь містить m+n невідомих ai , , та bj, . Оскільки рівнянь на одне менше, ніж змінних, то значення однієї із незалежних змінних обираємо довільно (наприклад, беремо, що воно дорівнює нулю) і знаходимо розв’язок системи.

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

2. Якщо існують небазисні клітинки, де умови потенціальності порушуються, то ознакою змінної, яку слід ввести в базис, є максимум порушення умови потенціальності (за модулем). Тобто, в базис вводиться та клітинка, де виконується mіn(-ij)=min(). Ця клітинка разом з базисними утворює цикл, за яким треба перемістити найменше перевезення  з від’ємного півциклу.

5. Для нового опорного плану знову проводимо перевірку на потенціальність згідно із кроками 1-3.

6. Кроки 1-5 повторюємо поки не дістанемо оптимальний план.

Зауваження 3.1. Розв'язок транспортної задачі при цілочислових значеннях запасів і потреб завжди буде цілочисловим.

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

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

Для задачі з перевищенням суми запасів над сумою потреб вводиться фіктивний пункт доставки Bф=Bn+1 з потребою   

,

при цьому усі величини сi.n-1=0, .

Якщо є задача з перевищенням потреб над запасами, то аналогічно, вводячи фіктивний пункт відправлення Aф=Am+1 з фіктивним запасом

і поклавши сm+1.j=0, приходимо до закритої транспортної задачі.

Зауваження 3.4. Якщо маємо вироджений опорний план, то для розв'язування транспортної задачі методом потенціалів слід деякі вільні клітинки таблиці вважати за базиси, щоб загальна кількість базисних клітинок була m+n -1. Для цього вводяться в ці клітинки значення перевезень  , 2, ..., де  = 0 в оптимальному плані.

Зауваження 3.5. Для кожної небазисної клітинки транспортної таблиці завжди існує цикл (тільки один), одна клітинка якого небазисна, а всі інші - базисні.

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

Приклад 3.1. Знайти методом потенціалів оптимальний план перевезень для транспортної задачі, початковий опорний план якої, поєднаний з матрицею вартостей перевезень та запасів і потреб, наведено в табл. 3.5. Складемо систему рівнянь для визначення потенціалів:

Поклавши , дістанемо розв'язок:

1(0)= –4, 2(0)= –2, 1(0)= 3, 2(0)= 8, 3(0)= 6, 4(0)= 6.

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

Найбільшу невідповідність (за модулем) дає клітинка таблиці (3.4):

Отже, її треба ввести в базис. Складемо цикл із клітинок (2,4), (3,4), (3,1), (2,1) і визначимо =10  (табл. 3.6). Знайдемо нові значення перевезень циклу: x21=50-10=40, x42=0+10=10, x31=40+10=50, x33=10–10=0.

  Таблиця 3.6

ПВ

ПД

ai

i(0)

B1

B2

B3

B4

A1

– 1         7

4          4 30

2          2   20

2          3

50

– 4

A2

1   (–)  1

50

6          5

4          6

4  ( +)  2

50

– 2

A3

3  (+)  3

40

8          8

50

6          7

6   (–)  6

10

100

0

bj

90

80

20

10

200

j(0)

3

8

6

6

Новий опорний план, де клітинка (2,4) буде базисною, а клітинка  (3,4) - вільною, наведено у табл. 3.7.

Знаходимо нову систему чисел-потенціалів і . Їх нові значення записані у табл. 3.7. Як легко побачити, умову потенціальності порушено тільки в одній клітинці (2,2), де

Складаємо цикл із клітинок (2,2), (3,2), (3,1), (2,1) і визначаємо  = 40. Змінюючи на цю величину значення перевезень у клітинках визначеного циклу, отримаємо опорний план, що наведений у табл. 3.8. А, знайшовши нові значення потенціалів і , записуємо їх в табл. 3.8, де наведено оптимальний план, у чому легко переконатися, перевіривши його на умови потенціальності.

  Таблиця 3.7

ПВ

ПД

ai

i(0)

B1

B2

B3

B4

A1

– 1        7

4          4   30

2          2   20

0          3

50

– 4

A2

1  (–)  1

40

6  (+) 5

4          6

2          2

10

50

– 2

A3

3  (+)  3

50

8  (–)  8

50

6          7

4          6

100

0

bj

90

80

20

10

200

j(0)

3

8

6

4

  Таблиця 3.8

ПВ

ПД

ai

i(0)

B1

B2

B3

B4

A1

– 1        7

4         4   30

2          2   20

1          3

50

4

A2

0          1

5          5

40

3          6

2          2

10

50

5

A3

3          3

90

8          8

10

6          7

5          6

100

8

bj

90

80

20

10

200

j(0)

–5

0

–2

–3

Зауваження до методу потенціалів:

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

2. У випадку виродженого ОП слід ввести фіктивні перевезення з таким розрахунком, щоб  однозначно обчислити всі потенціали.

3. Цикл завжди існує та єдиний для кожної вільної клітинки таблиці (для не виродженого ОП).

4. Якщо для якоїсь вільної клітинки (xij = 0) оптимального ОП у співвідношеннях досягається строга рівність, то це говорить про не одиничність оптимального ОП.

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

3.5 Т-задачі з обмеженими пропускними здатностями 

Постановка Т-задачі з обмеженими пропускними спроможностями (ТЗО). У пункті Pi (i=1,...,m) виробляється ai одиниць деякого продукту, а в пункті Qj (j=1,...,n) споживається bj одиниць того ж продукту. Транспортні витрати на перевезення одиниці продукту з пункту Pi в пункт Qj становлять cij одиниць. Комунікація PiQj має пропускну здатність rij. Вважаючи, що сумарний об'єм виробництва дорівнює сумарному об'єму споживання, потрібно скласти план перевезень продукту, що мiнiмiзує сумарні транспортні витрати. Математична модель ТЗО має вигляд:

L(x) = c11 x11 +...+ c1n x1n +...+ cm1 xm1 +...+ cmn xmn  min,

xi1 +...+ xin  = ai, i=1,...,m,

x1j +...+ xmj = bj, j=1,...,n,

0xijrij, i=1,...,m, j=1,...,n,

a1 +...+ am = b1 +...+ bn.

Остання умова визначає збалансовану ТЗО.

Крiм векторів перевезень x, виробництва-споживання b, комунікацій Aij та транспортних витрат c, визначення яких наведені при формулюванні звичайної збалансованої транспортної задачі, введемо вектор обмежень пропускних здатностей комунікацій

r=(r11,...,r1n,...,rm1,...,rmn).

Поряд з векторами x, c, r будемо також розглядати i матриці X=||xij||, C=||cij||, R=||rij||, i=1,...,m, j=1,...,n.

Основні означення

Допустимий розв'язок ТЗО x=||xij||, i=1,...,m, j=1,...,n, базисний, якщо його перевезенням xij, які задовольняють умову 0<xij<rij, відповідає системі лінійно незалежних векторів комунікацій Aij.

Послiдовнiсть різних комунікацій називається маршрутом, що зв'язує пункти i .

Маршрут, до якого додана комунікація , називається замкненим маршрутом (циклом).

Комунiкацiя PiQj називається основною комунікацією розв'язку x, якщо для цього розв'язку 0<xij<rij.

Аналогічні визначення справедливі i для клітинок Т-таблиці.

Властивості ТЗО та основні теореми

1. Ранг складеної з векторів Aij матриці A обмежень транспортної задачі дорівнює m+n1, звідки випливає, що допустимий базисний розв'язок задачі (якщо він існує) має не більше m+n1 перевезень xij, які задовольняють умову 0<xij<rij.

2.  Розв'язок ТЗО є базисним, якщо з його основних комунікацій неможливо скласти замкнений маршрут (цикл).

3.  Допустимий базисний розв’язок (ДБР) x=(xij, i=1,...,m, j=1,...,n) оптимальний тоді i тільки тоді, коли існують потенціали ui, vj такі, що

                vj  ui = cij, якщо xij  базисне перевезення,

          vj  ui  cij, якщо xij = 0, небазисне перевезення,

          vj  ui  cij, якщо xij = rij, небазисне перевезення.

Метод пошуку вихідного ДБР. Вихiдний  ДБР ТЗО (на відміну від ТЗ без обмежень), якщо він існує, знаходиться суттєво складніше. Його пошук Здійснюється за два етапи.

Перший етап (попередній) нагадує метод мінімального елемента в ТЗ без обмежень i в загальному випадку не дає допустимого розв'язку.

Другий етап містить ряд iтерацiй методу потенціалів, який застосовується до деякої розширеної ТЗО, побудованої за результатами першого етапу.

Вихiдний ДБР ТЗО. I етап. На множині невикреслених клітинок транспортної таблиці знаходять клітинку (i1,j1) з мінімальними транспортними витратами .

Припускають .

Якщо , то викреслюють i1-й рядок транспортної таблиці.

Якщо , то викреслюють j1-й стовпець Т-таблиці.

Якщо , то викреслюють тільки клітинку (i1, j1) транспортної таблиці.

Якщо , то у довільну, не викреслену на попередніх кроках клітинку, яка лежить або в i1- у рядку або в j1- у стовпчику, заносять нульове базисне перевезення.

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

Вихiдний ДБР ТЗО. II етап. Нехай X=||xij||, i=1,...,m, j=1,...,n, - матриця перевезень, що побудована на першому етапi. Покладемо

xi,n+1  = ai  ( xi1 +...+ xin ),  i=1,...,m,

xm+1,j = bj  ( x1j +...+ xmj ), j=1,...,n.

Позначимо  = x1,n+1 +...+ xm,n+1 = xm+1,1 +...+ xm+1,n.

Якщо  =0, то x  вихідний ДБР.

Якщо  >0, то вихідна ТЗ розширюється за рахунок фіктивних пунктів виробництва Pm+1 та споживання Qn+1 з am+1 = bn+1 = , де

ci,n+1  = M,    ri,n+1  = ,  i=1,...,m,

cm+1,j = M,    rm+1,j = ,  j=1,...,n,

cm+1,n+1 = 0,    rm+1,n+1 = ,

M  досить велике додатне число,   нескінченність.

Нерозподiленi на першому етапі залишки продукту (як по об'ємах виробництва, так i по об'ємах споживання) розподіляються по фіктивних пунктах Pm+1 та Qn+1. Відповідні заповнені клітинки вважаються базисними (оскільки пропускні здатності відповідних їм комунікацій необмежені) i приєднуються до сукупності базисних клітинок заповнених на першому етапі. Якщо після цього загальна кількість базисних клітинок не рівна (m+1)+(n+1)1, то множину базисних клітинок доповнюють до цього числа за рахунок незаповнених клітинок або заповнених до пропускної здатності, але так, щоб розширена множина базисних клітинок не містила циклів. Розширена ТЗ розв'язується методом потенціалів.

Якщо в оптимальному розв'язку x*m+1,n+1=, то, відкидаючи фіктивні пункти, отримаємо вихідний ДБР, інакше, ТЗО не має розв'язкiв.

Потенцiали. Потенцiали рядків ui, i=1,...,m, та колонок vj, j=1,...,n, визначаються як розв'язок системи vjui=cij, де i та j приймають такі значення, що клітинки (i,j)  базисні.

Вказана система містить m+n1 рівнянь (за числом базисних клітинок) та m+n змінних. Тому одна із змінних задається довільно (u1=0).

Оцiнки. Оцiнки ij змінних xij для всіх небазисних клітинок обчислюються за формулою ij=cijvj+ui(оцінки базисних змінних – нульові). Поточний ДБР X=||xij||, i=1,...,m, j=1,...,n, оптимальний, коли

ij=0, якщо xij  базисне перевезення,

ij0, якщо xij = 0, небазисне перевезення,

ij0, якщо xij = rij, небазисне перевезення.

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

Новий ДБР. Серед всіх клітинок (i,j), для яких не виконується критерій оптимальності, обирають клітинку, що відповідає найбільшою за модулем оцінки ij. Позначимо таку клітинку через (i0,j0).

Нехай клітинка (i0,j0), для якої приєднується до сукупності базисних клітинок. Знаходиться цикл, що утворюється цими клітинками. Цикл розбивається на додатний (C+) та від'ємний (C) пiвцикли, клітинки яких чергуються одна з одною, причому клітинка (i0,j0) відноситься до додатного пiвциклу. Обчислюються величини

1 = min{xij}           по C,

2 = min{rij  xij} по C+,

  = min{1, 2}.

Далі збiльшують на значення   перевезення xij в клітинках пiвциклу C+ i зменшують їх на те ж значення в клітинках C.

Для клітинки (i0,j0) такої, що відміна полягає у тому, що вона відноситься до від'ємного пiвциклу.

У результаті виконання вказаних процедур клітинка (i0,j0) вводиться до множини базисних, а клітинка, пов'язана з , стає небазисною. Якщо  досягається на клітинці (i0,j0), то множина базисних клітинок не змінюється після перерозподілу перевезень вздовж циклу на сталу  i новий ДБР матиме ту ж саму систему потенціалів i ті ж самі оцінки, що i попередній. Тому у цьому випадку після обчислення нового ДБР безпосередньо переходять до перевірки його на оптимальність.

Алгоритм методу потенціалів:

1. Будується вихідний ДБР.

2. Далі метод складається з однотипних кроків, на кожному з яких:

І) Обчислюються потенціали ui, i=1,...,m, та vj, j=1,...,n;

ІІ) Обчислюються оцінки ij змінних xij, i=1,...,m, j=1,...,n;

ІІІ) Аналiзуються знайдені оцінки ij. Якщо оцінка ij0 для  xi =0 та ij0 для xij = rij, то поточний ДБР є оптимальним. Інакше, переходять до покращання поточного ДБР (п. п. IV та V).

IV) Будується цикл.

V) Знаходиться новий  ДБР.

Крок закінчено. Перехiд до пункту I).

3.6 Задача про оптимальні призначення

Постановка задачі про призначення. Знайти вектор (матрицю) X=(xij, i,j=1,...,n), що мiнiмiзує цільову функцію

L(X) = c11 x11 +...+ c1n x1n +...+ cn1 xn1 +...+ cnn xnn

i задовольняє систему обмежень

xi1 + ... + xin = 1,  i=1,...,n,

x1j + ... + xnj = 1,  j=1,...,n,

xij = 0 або 1,  i,j=1,...,n,

де cij  витрати, пов'язані з використанням i-го виконавця для виконання j-ї роботи (i,j=1,...,n). Елементи cij утворюють матрицю витрат C.

Наведена задача може бути розв'язана угорським методом, що грунтується на тому факті, що віднімання числа ai, i=1,...,n, від кожного елемента i-го рядка та числа bj, j=1,...,n, від кожного елемента j-го стовпця матриці витрат C не змінює множини оптимальних призначень, тобто вказані дії перетворюють матрицю витрат C в еквівалентну їй матрицю, яку також називають матрицею витрат.

Алгоритм угорського методу.

1.  В матриці C вiднiмаємо від кожного елемента i-го рядка мінімальний елемент цього рядка (i=1,...,n).

2. від кожного елемента j-го стовпця перетвореної матриці витрат вiднiмаємо його мінімальний елемент (j=1,...,n). В результаті виконання двох пунктів кожний рядок та кожний стовпець матриці витрат мають принаймні один 0.

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

4. Дії п. 3 повторюємо для всіх стовпцiв матриці витрат.

5. Дії п.п. 3 та 4 повторюємо послідовно (якщо необхідно) поки не трапиться один з трьох можливих випадків:

i) кожний рядок має призначення (має 0 з позначкою *);

ii) є принаймні два непозначених нулі в деяких рядках i деяких стовпцях матриці витрат;

iii) немає непозначених нулів i повне призначення ще не отримане (число нулів з позначкою * менше n).

6. У випадку i) задача про оптимальні призначення розв'язана: xij, що відповідають 0*, дорівнюють 1, решта – 0, кінець. У випадку ii) довільно вибираємо один з непозначених нулів, позначаємо його позначкою *, закреслюємо решту нулів в тому ж рядку i в тому ж стовпчику  i повертаємося до п. 3. У випадку iii) переходимо до п. 7.

7. Позначаємо позначкою # рядки, для яких не отримане призначення (в яких немає 0*). Такі рядки вважаємо позначеними, решту – непозначеними. Аналогiчно називаються i стовпчики матриці витрат.

8. Позначаємо позначкою # ще не позначенi стовпчики, які мають закреслений 0 (позначений позначкою ^) у позначених рядках.

9. Позначаємо позначкою # ще не позначенi рядки, які мають призначення (тобто 0*) у позначених стовпцях.

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

11. Викреслюємо (за допомогою позначки &) не позначенi рядки i позначені стовпчики матриці витрат.

12. Знаходимо мінімальний не викреслений елемент матриці витрат, віднімаємо його від елементів кожного з не викреслених рядків, додаємо до елементів всіх викреслених стовпчикiв i переходимо до п. 3. При цьому позначки елементів матриці витрат (* та ^) втрачають свою силу.

Зауваження

1. Якщо в задачі (3.1)(3.4) цільову функцію (3.1) треба максимiзувати, то для її розв'язання можна застосувати угорський метод, замінивши матрицю C на C.

2. За означенням в задачі (3.1)(3.4) матриця витрат квадратна. Якщо це не так, то вона перетворюється до такої додаванням необхідного числа додаткових рядків або стовпчикiв з відповідними елементами cij=0.

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

Задача про призначення може бути розв'язана, також, і методом Мака.

Алгоритм методу Мака.

1. Позначаємо мінімальний елемент рядка позначкою *. Якщо мінімальних елементів декілька, позначаємо будь-який з них.

2. Дії п. 1 повторюємо для всіх рядків матриці витрат.

3. Якщо рядок має ще один мінімальний елемент, проглядаємо стовпець, до якого цей елемент належить. Можливі випадки:

i) Стовпець не має позначених елементів;

ii) Стовпець має принаймні один позначений елемент.

4. У випадку i) позначаємо мінімальний елемент рядка позначкою *. Всі інші позначки в цьому рядку знімаються.

У випадку ii) позначаємо мінімальний елемент рядка позначкою ^, якщо елемент цього рядка з позначкою * не є єдиним позначеним елементом у своєму стовпцi.

5. Дії п.п. 3 та 4 повторюємо послідовно для всіх рядків, що мають більше одного мінімального елемента.

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

7. Позначаємо (позначкою &) стовпцi, що мають більше одного позначеного елемента. Вони утворюють множину В, інші стовпцi матриці витрат утворюють множину A.

8. Проглядаємо послідовно рядки матриці витрат, починаючи з першого, i знаходимо рядок, в якому елемент з позначкою * належить множині В.

9. Знаходимо для рядка мінімальну різницю між елементами множини A i елементом з позначкою *.

10. Дії п.п. 8 та 9 повторюємо послідовно для всіх рядків, що мають властивості, які вказані в п. 8.

11. Вибираємо найменшу з мінімальних різниць.

12. Додаємо це число до кожного елемента множини В.

13. Повертаємось до п. 3.

Зауваження до методу Мака аналогічні угорському методу.

3.7 Задача про максимальний потік. Метод Форда-Фалкерсона

Постановка задачі про максимальний потік на мережі.

На мережі, що задається графом (I,U), де I – множина вершин, U – множина дуг, з визначеною на ній функцією пропускних спроможностей rij ((i,j) –дуга з U), зафіксовані дві вершини – i1 та in.

Вершина i1 (джерело) має інтенсивність d, вершина in (стік) – інтенсивність – d, всі інші вершини нейтральні. Треба знайти максимальну інтенсивність джерела d, при якій мережа допускає потік. Потiк, що відповідає такому максимальному значенню інтенсивності d*, називається максимальним потоком, а саме значення d*величиною цього потоку.

Алгоритм Форда-Фалкерсона застосовується для побудови максимального потоку на мережі із заданої початкової вершини-джерела в задану кінцеву вершину-стiк.

Будемо вважати, що вершиною-джерелом є 1-а вершина, вершиною-стоком – вершина з номером n.

Вхідні дані.

Для роботи алгоритму необхідно задати таку інформацію:

1. Число вершин мережі.

2. Матрицю суміжностей С, елементи якої сij визначаються співвідношеннями:

сij=1, якщо існує дуга (i,j);

сij=0, якщо дуга (i,j) відсутня.

3. Величини rij пропускних спроможностей дуг (i,j).

4. Початковий потік на мережі, тобто величини xij, що задовольняють умови:

a)                                              0xijrij;

b) для довільної вершини (крім першої i останньої) потік, що входить у вершину, дорівнює потоку, що виходить з неї.

Виклад алгоритму Форда-Фалкерсона.

Алгоритм складається з послідовних iтерацiй, які проводяться до тих пір, поки не буде виконуватись ознака оптимальності.

На кожній iтерацiї можна виділити два етапи.

Етап 1 (етап виставлення позначок).

1. В кожний момент часу кожна вершина може знаходитись в одному з трьох положень:

а) не позначена;

б) позначена, але не проглянута;

в) позначена i проглянута.

Загальний вигляд позначки j-ї вершини: [i+,j], або [i,j], де i  номер деякої позначеної вершини, при прогляданнi якої була позначена вершина j. Вершина 1 завжди позначена та має позначку [1+,1], де 1 рівне +  (нескінченності).

2. Проглядання довільної позначеної вершини j полягає у такому:

a) довільна непозначена вершина k, для якої існує дуга (j,k) i має місце нерівність xjk<rjk, отримує позначку вигляду [j+,k], де

k=min {j, rjk  xjk};

б) довільна непозначена вершина k, для якої існує дуга (k,j) i має місце умова xkj>0, отримує позначку вигляду [j,k], де

k=min {j, xkj}.

3. Виставлення позначок закінчується в одному з двох випадків:

а) вершина з номером n позначена;

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

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

Етап 2 (етап зміни потоку).

Потiк в мережі змінюється на величину n відповідно правилу. Якщо вершина n має позначку [k+,n], де k – номер деякої вершини, то xkn=xkn+n. Якщо позначка має вигляд [k,n], то xnk=xnkn. Переходимо до вершини з номером k. Якщо позначка вершини k має вигляд [j+,k], то xjk=xjk+n; якщо вона дорівнює [j,k], то xkj=xkjn. Подібні дії продовжуємо доти, поки не буде досягнута початкова вершина. В цьому випадку всі старі позначки витираємо i повертаємось до першого етапу.

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

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

3.8 Задача про найкоротший шлях на мережi. Метод Мiнтi

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

На мережі, що задається графом (I,U), де I – множина вершин, U – множина дуг, з визначеною на ній функцією вартості cij ((i,j) –дуга з U), для фіксованих i1 та is знайти шлях

L = ((i1,i2),(i2,i3),...,(is-1,is))

із вершини i1 у вершину is, довжина якого

найменша.

Алгоритм методу Мiнтi.

Методом Мiнтi розв'язується задача побудови дерева найкоротших шляхів на мережі з коренем у фіксованій вершині i1.

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

Нехай Pr – множина вершин, позначених на кроцi r, а Ir – множина вершин, позначених за r кроків.

Крок 0. Корiнь дерева (вершина i1) позначається сталою величиною h1=0; i1(h1)=i1(0). Пiсля нульового кроку P0={i1(0)}, I0={i1(0)}.

Нехай виконано r кроків, за які побудована множина

Ir={i1(0),...,ik(hk),...}

позначених вершин ik(hk), кожній з яких поставлене у відповідність число hk (чисельно рівне довжині найкоротшого шляху із вершини i1 у вершину ik).

Крок r+1. Будується розріз мережі, який породжується множиною позначених вершин Ir i визначається множина Jr={...,im,...} непозначених вершин im мережі, в які заходять дуги розрізу. Для кожної дуги (ik,im) розрізу обчислюють суму hk+ i позначають ті з дуг, для яких ця сума мінімальна. Потім, виділяють позначені дуги так, щоб в кожну непозначену вершину множини Jr, в яку заходять позначені дуги розрізу, заходила б тільки одна виділена дуга. Пiсля виділення дуг позначають вершини – кінці виділених дуг. Величина позначки рівна мінімальній із сум hk+, обчислених для всіх дуг розрізу. Об'єднуючи множину Ir з множиною Pr+1 вершин, позначених на (r+1)-у кроцi, отримують множину Ir+1 вершин, позначених за (r+1) кроків. Переходять до наступного кроку, якщо існує розріз, що породжується множиною Ir+1.

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

Якщо деяка вершина in мережі залишилась непозначеною після закінчення процедури Мiнтi, то шляху, що починається у вершині i1 i закінчується у вершині in, не існує.

РОЗДІЛ 4. ДИСКРЕТНЕ ПРОГРАМУВАННЯ

Під час розв’язання задач ЛП часто висувається вимога дискретності (цілочисельності) змінних, що входять у розв’язок. Множиною планів такої задачі буде система точок із цілочисловими координатами, що належать опуклому багатокутнику допустимих розв’язків відповідної недискретної задачі. Якби можна було визначити гіперплощини, що проходять через зовнішні точки такої системи точок цілочислової задачі, причому так, щоб зовнішні точки цієї системи потрапили до нового опуклого багатокутника, то задачу можна було б розв’язати за допомогою звичайного симплекс-методу. У цьому випадку всі крайні точки опуклого багатокутника були б цілочисловими і розв'язок можна було б знайти за скінчене число кроків. Ця ідея послідовного відсікання частин вихідного багатокутника планів, що не містять допустимих цілочислових планів, покладена в основу методів Гоморі, які реалізуються за рахунок побудови додаткових обмежень-нерівностей, які визначають гіперплощини, що відсікають. Ці обмеження мають задовольняти дві умови: відсікання, що полягає у тому, що вони не повинні задовольняти план недискретної задачі; правильності відсікання, що полягають у тому, що вони мають задовольняти всі цілочислові плани задачі.

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

4.1 Задача дискретного ЛП. Метод Гоморi-1)

Постановка задачі дискретного ЛП (ДЗЛП). Необхідно знайти вектор x=(x1,...,xn), що мiнiмiзує цільову функцію

L(x) = c1x1 + ... + cnxn                                        (4.1)

i задовольняє систему обмежень

a11x1  + . . . + a1n xn = a10,

. . . . . . . . . . . . . . . . . . . . . . . ,                                   (4.2)

am1x1 + . . . + amnxn = am0,

xj0, j=1,...,n,                                                   (4.3)

xj  цілі                                                               (4.4)

Виклад методу Гоморi-1. Розв'язується ЗЛП (4.1)-(4.3), яку отримують з вихідної задачі ДЗЛП (4.1)-(4.4) відкиданням умови дискретності змінних (4.4). Якщо оптимальний розв'язок ЗЛП – дискретний, то він буде і розв'язком вихідної ДЗЛП. Якщо ж отриманий розв'язок задачі не дискретний, то від розв'язаної ЗЛП переходять до нової ЗЛП, що отримується додаванням додаткового лінійного обмеження, яке задовольняє дискретні розв'язки вихідної ДЗЛП i яке не задовольняє отриманий недискретний  розв'язок ЗЛП. Це додаткове лінійне обмеження визначає деяку площину, що  відсікаає, i називається правильним відсіканням. Приєднання нових правильних відсікань до вихідної ЗЛП здійснюється до тих пір, поки на деякому кроцi не буде отримано дискретний  розв'язок ЗЛП, який, як очевидно, буде оптимальним розв'язком вихідної ДЗЛП. В методі Гоморi-1 правильне відсікання будується таким чином.

Нехай на останній iтерацiї симплекс-методу під час розв'язання допоміжної ЗЛП непрямі обмеження цієї задачі набули вигляду:

xi   + ai,m+1 xm+1 +...+ ain xn = ai0,  i=1,...,m,

i розв'язком допоміжної ЗЛП є вектор x = (a10 ,..., am0, 0,...,0 ).

Нехай існує номер r такий, що ar0 – дріб, i, як завжди, {z} – дробова частина z. Тоді правильне вiдсікання за методом Гоморi-1 задається такою нерівністю:

{ ar,m+1} xm+1 +...+ { arn} xn  { ar0} .

Алгоритм методу Гоморi-1.

1. Розв'язуємо допоміжну ЗЛП (4.1)(4.3). Нехай x(0) – її оптимальний розв'язок. Якщо оптимальний розв'язок не існує, то вихідна ДЗЛП також не має оптимального розв'язку.

2. Нехай на s-й iтерацiї маємо розв'язок допоміжної ЗЛП, що має M обмежень i N змінних, x(s) – її оптимальний розв'язок.

Будемо вважати, що x(s) визначається канонічними обмеженнями останньої iтерацiї, тобто: xi   + bi,M+1 xM+1 +...+ biN xN