Як підсумок наведемо етапи розв’язку задачі лінійного програмування симплексним методом у вигляді схеми: Зведення задачі лінійного програмування до стандартної форми

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

Встановлення опорності

(критерієм опорності плану задачі є невід’ємність колонки вільних членів симплексної таблиці)

Знаходження оптимального плану (критерій оптимальності – невід’ємність елементів цільового рядка симплексної таблиці)

Знаходження оптимального плану (критерій оптимальності – недодатність елементів цільового рядка симплексної таблиці)

на max на min

Рис. 2.8. Етапи розв’язку залачі лінійного програмування

симплекс-методом

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

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

(1)

..................................................

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

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

(2)

..................................................

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

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

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

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

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

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

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

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

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

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

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

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

Перша теорема подвійності

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

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

Економічний зміст першої теореми двоїстості такий: план виробництва Х та набір цін (оцінок) ресурсів Y будуть оптимальними тоді і тільки тоді, коли загальний прибуток від реалізації продукції збігається із затратами на ресурси за “внутрішніми”, що визначені під час розв’язку задачі цінами на ресурси.

Цей зміст можна інтерпретувати і так: фірмі байдуже, чи виробляти продукцію за оптимальним планом Х і отримати максимальний прибуток, чи продати ресурси виробництва за оптимальними цінами Y.

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

Друга теорема подвійності

Для того, щоб плани Х та Y були оптимальними, необхідно і достатньо виконання таких співвідношень, що називають умовами доповнюючої нежорсткості:

;

Ці умови дають можливість, знаючи оптимальний план однієї із пари подвійних задач, знайти оптимальний план другої .

Із другої теореми подвійності випливають такі вимоги до оптимального плану Х та оптимального вектора цін Y:

Я кщо Y_i>0, i=1,…..,m;

Якщо , то Y_i=0, i=1,…..,m;

Я кщо Х_j>0, , j=1,…..,n;

Якщо , то Х_j=0, j=1,…..,n.

Першу групу умов можна інтерпретувати: якщо оцінка Y_i одиниці ресурсу додатна, то при оптимальній виробничій програмі цей ресурс використовується повністю, в протилежному випадку – його оцінка дорівнює 0.

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

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

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

Третя теорема подвійності (теорема про оцінки)

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

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

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

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

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

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

Модифіковані жорданові вилучення відрізняються від звичайних лише:

• формуванням скороченої симплексної таблиці;

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

Розглянемо приклад:

Побудувати задачу, подвійну до заданої, знайти її розв’язок.

Пряма задача Подвійна задача

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

		y1	y4	W
		-x3	-x2	1
y3	х1	1 -1	-1 3	2 2
y2	x4
1	Z	3	2	6

		y3	y4	W
		-x1	-x2	1
y1	x3	1 1	-1 2	2 4
y2	x4
1	Z	-3	1	0

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

		y1	y2	W
		-x3	-x4	1
y3	x1	2/3 -1/3	1/3 1/3	8/3 2/3
y4	x2
1	Z	7/3	2/3	22/3

Для поглибленого вивчення методів оптимізації лінійних за­дач можна скористатися літературними джерелами [3; 8; 9].

Заключні зауваження

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

Графічний метод є важливим для осмислення сутності оптимі-зації, геометричної інтерпретації постановки та розв'язку задач лінійного програмування.

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

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

Двоїс­тість у лінійному програмуванні була розроблена академіком Л.В. Канторовичем ще в 1933 році.

У 1975 році Л.В. Канторович і американський математик Г. Купманс за відкриття теорії двоїс­тості та її застосування в економічних дослідженнях одержали Нобелівську премію.

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

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

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

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