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

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

Розглянемо таку умовну задачу.

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

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

Таблиця 1

Ресурс	Вид продукції				Обсяг ресурсу
	1	2	3	4
Обладння (верстато-год) Метал (кг) Електроенергія (кВт) Прибуток (грн.)	2 1 3 5	3 4 4 6	4 5 2 7	3 1 2 4	780 850 790

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

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

Для того, щоб скласти математичну модель задачі, тобто вико­нати другий етап економіко-математичного моделювання, уведемо змінні:

х_j — шукана кількість продукції j-го виду згідно з планом вироб­ництва = ;

Z — прибуток від реалізації плану виробництва.

У цих позначеннях математична модель задачі має такий вигляд:

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

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

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

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

Це перетворення задач інтерпретується так: і враховуючи, що 780 — тривалість роботи облад­нання, а другий доданок — витрати часу роботи обладнання на весь план виробництва, то – виражає невикористаний час роботи облад­нання. Непрацююче обладнання прибутку не створює, тому у цільову функцію входить із нульовим коефіцієнтом. За аналогією встановлюють економічний зміст змінних і .

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

Таблиця 2

Б	СБ	План Х	5	6	7	4	0	0	0
	0	780	2	3	4	3	1	0	0	390	260	195	260
	0	850	1	4	5	1	0	1	0	850	212	170	850
	0	790	3	4	2	2	0	0	1		197,5	395	395
		0	-5	-6	-7	-4	0	0	0	-1316	-1185	-1190	-1040

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

За початковим планом Х° нічого не виробляється і ресурси зовсім не використовуються. Тому оцінки ресурсів дорівнюють нулю, тобто

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

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

З останньої формули випливає, що потрібно перейти до такого опорного плану, для якого величина при розв'язанні задачі на максимум цільової функції буде найменшою з від'ємних, що спри­чинить максимальне збільшення . Тому з'являється така стра­тегія: оскільки > 0, то заповнюють стільки стовпців « », скільки видів продукції мають від'ємну оцінку. Заповнюють стовпець « » діленням елементів стовпця «План» на відповідні додатні елементи стовпця « » — відповідної продукції. У табл.2 усі чотири види про­дукції мають від'ємні оцінки, тому маємо чотири стовпці « »: « », « », « », « » (для кожного виду). Вибираємо найменше число в кожному стовпці « », помножуємо на відповідну оцінку і за­писуємо в індексному рядку на перетині відповідних стовпців.

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

Економічна інтерпретація цього переходу така: діленням еле­ментів стовпця «План» на елементи стовпця « » фактично діляться обсяги ресурсів на питомі норми їх витрат на виробництво продукції першого виду. У результаті в стовпці « » дістаємо числа, які визна­чають, скільки одиниць продукції першого виду можна випустити за рахунок кожного ресурсу окремо. Вибір найменшого числа в стовпці « » ( ) визначає максимально можливу кількість продукції першого виду, отриману за рахунок обсягу всіх ресурсів у сукупності (принцип «вузького місця»). Абсолютна величина добутку ( ) є максимально можливим прибутком підприємства від включення в план виробництва тільки продукції першого виду. Ана­логічно інтерпретуються елементи стовпців « », « » та « ». Вибір визначає максимально можливий прибуток від включення в план виробництва тільки одного виду продукції, якому відповідає максимально можливий прибуток. За правилом заповнення наступних симплексних таблиць заповнюємо другу симплексну табли­цю (табл. 3).

Таблиця 3

Б	СБ	План Х	5	6	7	4	0	0	0
	0		0				1	0		95	135
	0		0				0	1		135	1760
	5		1				0	0		345	395
			0				0	0		-348	-101

Згідно з другим опорним планом виробляється одиниці про­дукції першого виду; інша продукція не виробляється, тобто . При цьому електроенергія використовується пов­ністю (х₇ = 0), а обладнання і метал недовикористовуються відповідно на 760/3 і 1760/3 (х₅ = 760/3; х₆ = 1760/3). Електроенергія стає дефіцитним ресурсом — оцінка цього ресурсу становить 5/3.

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

Розглянемо зміст елементів стовпців « », . З точки зору математики — це коефіцієнти розкладання векторів за векторами базису. Немає потреби аналізувати всі стовпці. Достатньо виконати аналіз одного з них, наприклад «х₃» (ключового), і перенести на інші. Розглянемо елемент, що розміщується на перетині рядку «х₁» і стовпця “х₃” (2/3). Він показує, наскільки зменшиться кількість одиниці про­дукції першого виду, якщо в план увести одну одиницю продукції третього виду. Іншими словами, включення в план однієї одиниці про­дукції третього виду через дефіцитність електроенергії витісняє 2/3 одиниці продукції першого виду. Важливість цього моменту полягає в тому, що вивільнюються ресурси всіх видів в кількості, потрібній для виробництва 2/3 одиниці продукції першого виду. Відомо, що на виробництво одиниці продукції третього виду витрачаються ресурси за заданими питомими нормами, але величина кожної норми в другій і наступних таблицях складається з двох частин: одна — кількість одиниць ресур­су, що вивільнюються від витіснення 2/3 одиниці продукції першого виду, а інша — кількість одиниць ресурсів фонду. Це підтверджують такі прості розрахунки.

Справді, щодо об­ладнання

де 2 — кількість верстато-годин на одиницю продукції першого виду;

2/3 — кількість одиниць продукції першого виду, що витісняється;

8/3 — кількість верстато-годин з обсягу часу роботи обладнання;

щодо металу

щодо електроенергії

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

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

Усе викладене ілюструє табл. 4

Таблиця 4

Б	СБ	План Х	5	6	7	4	0	0	0
	0	95	0		1			0
	0	175	0		0			1
	5	200	1		0			0
		1665	0		0			0

Розглянемо, наприклад, стовпець «х₄». Оцінка свідчить про неефективність включення в план продукції х₄, оскільки зменшення прибутку від включення одиниці продукції четвертого виду в план , а прибуток від реалізації одиниці продукції С₄ = 4 = 32/8, тобто втрата прибутку становитиме Z₄ - С₄ = 45/8 - 32/8 = 13/8.

Включення в план одиниці продукції четвертого виду вивільнить стільки одиниць усіх ресурсів, скільки їх потрібно для виробництва 1/4 одиниці продукції першого виду і 5/8 одиниці продукції третього виду. Виконаємо відповідні розрахунки за ресурсами:

щодо обладнання

(питома норма);

щодо металу

щодо електроенергії

У 4-й усі оцінки невід'ємні, отже, одержаний план є оптимальним. Згідно з цим планом виробництва продукція першого виду становить 200 одиниць (х₁= 200), третього — 95 одиниць (х₃ = 95), а продукцію другого та четвертого виду виробляти невигідно: х₂ = х₄ = 0. Залишок металу становитиме 175 кг (х₆=175); максимальний прибуток – 1665.

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

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

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

грн/верстато-год — втрати прибутку від дефіцитності часу ро­боти обладнання;

грн/кг — втрата прибутку від дефіцитності металу;

грн/кВт — втрата прибутку від дефіцитності електроенергії.

Економіко-математичний аналіз розв’язку ЗЛП: ЕМА проводиться за допомогою властивостей двоїстих оцінок (об’єктивно-обумовлених оцінок за виразом Л.В. Кантаровича), які є оптимальним планом двоїстої задачі.

Властивості двоїстих оцінок:

1. оцінка як міра дифіцитності ресурсів – ця властивість випливає із співвідношення 2.76 – 2.77: якщо оцінка і-того ресурсу >0, тобто y_i^* >0, то для виконання умов 2.77 необхідно щоб витрати ресурса і-того виду на весь план виробництва дорівнював його запасу в_і. Тому якщо оціка y_i^* >0, то цей ресурс використаний повністю і він є дифіцитним. Якщо ж витрати ресурсу і-того виду на весь план виробництва меньше його запасу, то для виконання умови 2.77 необхідна рівність нулю y_i^*, тільки якщо y_i^*=0, то і-ий ресурс повністю не використаний, він є в надлишку;

2. оцінка як міра впливу обмеження на цільову функцію

3. оцінка як інструмент аналізу різних варіантів плана виробництва

4. оцінка як інструмент балансування сумарних витрат і сумарного ефекту – випливає із І теореми двоїстості Z_max=F_min;

5. оцінка як міра взаємозамінності ресурсів.

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

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

Верхню межу збільшення визначаємо за формулою:

для ;

Нижню межу визначаємо за формулою:

для ;

Обладнання.

При цьому матриця

Інтервал стійкості оцінок стосовно першого обмеження .

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

Нижня межа

Інтервал стійкості оцінок стосовно другого обмеження

[850- 175, 850] = [675, 850].

Електроенергія. Нижня та верхня межі відповідно

Інтервал стійкості оцінок стосовно третього обмеження

.

Оцінюємо ефективність заходів щодо розшивки вузьких місць. Нехай, наприклад, є можливість одержати перший ресурс в обсязі 30 верстато-год по ціні 1 грн. за 1 верстато-год. З'ясуємо, як це впли­не на прибуток підприємства. Збільшення ресурсу перебуває в межах стійкості оцінок. Звідси

грн.

Водночас витрати на цей захід грн. Тоді

грн.

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

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

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

Цікавим є випадок одночасної зміни лімітів за кількома видами ресурсів. Розглянемо цей випадок у загальному вигляді. Нехай обме­ження змінюються у фіксованій пропорції k₁:k₂:…:k_m. Зміну мат­риці обмежень позначимо , що означатиме зміну окремого і-го об­меження на величину Тоді співвідношення, які визначають нижню границю зменшення В ( ) і верхню границю збільшення В ( ), набудуть вигляду відповідно

для

для

Проілюструємо це на прикладі.

Припустимо, є можливість замість 8 кг металу придбати 6 верстато-год роботи обладнання і 10 кВт електроенергії. Це означає, що обмеження змінюватимуться у фіксованій пропорції k₁:k₂:k₃ = 6 : (-8) : 10.

Тоді дістаємо:

Для

Для

Для

Отже, змінні і визначають верхню межу зміни матриці обмежень

а змінна — нижню межу:

Інтервали зміни обмежень при незмінних двоїстих оцінках такі:

Для b₁

;

для b₂ розрахуємо нижню межу, оскільки верхня може бути будь-якою:

;

для b₃

.

Здобуті інтервали досить широкі і включають вищі зміни ре­сурсів.

Сукупний ефект

грн.

Отже, такий захід ефективний.

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

, тоді , тобто , , , ;

На цій властивості оцінок можна побудувати також інші комбінації економіко-математичного аналізу.

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

1. а налізувати потребу в зміні технології виробництва. Припустимо, наприклад, що при виробництві продукції х₁ можлива заміна однієї верстато-години на 2Кв/год. Це еквівалентно збільшенню обсяга обладнання на одну верстато-годину і зменьшенню обсягу електроенергії на 2Кв/год. Єфект від такої заміни, тобто приріст прибутку за одиницю продукції складе С=1*11/8-2*3/4. Єфективність такого заходу негативна.

2. Внесення в план виробництва нової продукції. Наприклад, внести в план виробництво продукції х₈ , яка характеризується такою технологією (витратами ресурсів):

a₁₈=1

a₂₈=2

a₃₈=1

Прибуток за одиницю 3грн.

Обчислимо оцінку усієї продукції Z₈-C₈= 1*11/8+2*0+1*3/4-3=-7/8/ Втрата прибутку від внесення в план виробництва нової продукції є від’ємне число, тому цей захід - ефективний.

Виконання 4 властивості слідує із першої таореми двоїстості, яка стверджує, що екстримальні значення цільових функцій співпадає, тобто Z_max=F_min

7*95+5*200 = 780*11/8+790*3/4

1665 = 1665

В нашій задачі можна говорити про взаємозамінність обладнання і електроененргії, так як вони дефіцитні і їхні оцінки не рівні нулю. Обладнання і електроенергія взаємозамінні з коефіціентом взаємозамінності (11/8) / (3/4)=11/6.

Враховуючи те, що додаткові змінні двоїстої задачі розміщуються в рядку останньої симплексної таблиці розв’язку вихідної задачі в стовпцях продукції, тобто в стовпцях “ ” – “ ”, то їх оптимальні значення , , , . Тому продукція ІІ-го та IV-го видів, нерентабельна, а продукція І-го то ІІІ-го видів рентабельна, оскільки для продукції ІІ-го та IV-го видів втрата прибутку додатня.