МЕТОДИЧНІ ВКАЗІВКИ ДО САМОСТІЙНОЇ РОБОТИ

Таблиця 3 – Граничні значення випуску за потужністю устаткування

та за попитом на продукцію підприємства, од.

де Х1, Х2, Х3, Х4, Х5, Х6 – плановий обсяг виробництва продукції А, В, С, D, E, F.

Коефіцієнти при невідомих Х1 – Х6 у вираженні (3) – прибуток від одиниці виробленої продукції (див. передостанній стовпець табл. 1).

Уведемо обмеження до заданої цільової функції:

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

8478,10Х1 + 238,61Х2 + 1494,27Х3 + 570,71Х4 + 5381,02Х5 + 1587,59Х6 ≤ 267525600.

(4)

Обмеження на виплати із заробітної плати таке:

850,66Х1 + 23,94Х2 + 149,93Х3 + 57,26Х4 + 539,91Х5 + 159,29Х6 ≤ 31983840.

(5)

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

236,71Х1 + 6,66Х2 + 41,72Х3 + 15,93Х4 + 150,24Х5 + 44,33Х6 ≤ 276312200.

(6)

2) обсяги виробництва в оптимальній виробничій програмі повинні бути невід'ємні та обмежені реальним попитом на продукцію підприємства у

11

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

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

атакож на випуск кожного виду продукції (7).

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

Кожна задача лінійного програмування пов’язана з іншою задачею, так званою двоїстою задачею. Економічну інтерпретацію прямої виробничої задачі та її математичну модель (2) було розглянуто вище (див. розділ 1). Обговоримо тепер ту саму задачу з іншої позиції. Припустимо, що за певних умов доцільно продавати деяку частину чи всі наявні ресурси підприємства. Слід визначити цінність ресурсів. Кожному ресурсу bj (j = 1, 2, … , m) поставимо у відповідність його оцінку Yj [2; 3; 4; 5].

На виготовлення одиниці i-го виду продукції Xi витрачається згідно з моделлю (2) усі m видів ресурсів у кількості, відповідно, a1i, a2i, … , ami. Оскільки ціни одиниці кожного виду ресурсів за припущенням дорівнюють Yj, то загальна вартість ресурсів, що витрачені на виробництво одиниці i-го виду продукції,

обчислюється як

12

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

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

Загальна вартість ресурсів виражається величиною

Модель (11) тлумачиться наступним чином: визначити, які мінімальні ціни можна встановити для одиниці кожного j-го виду ресурсу Yj, щоб продаж ресурсів був доцільнішим за виробництво продукції. Причому відомо: загальна кількість кожного ресурсу bj, нормативи використання j-го виду ресурсу на кожен i-й вид продукції ajі, а також сi – ціна реалізації одиниці продукції.

Зауважимо, що справжній зміст величин Yj – умовна ціна, що виражає міру цінності відповідного ресурсу для даного виробництва. Англійський термін

«shadow prices» у літературі перекладається, як оцінка, або тіньова, неявна, ціна.

13

Один із фундаторів теорії лінійної оптимізації Л. Канторович називав величини Yj

об’єктивно обумовленими оцінками.

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

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

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

навпаки.

Початкова постановка задачі і математична модель може мати вигляд як (2),

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

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

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

1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі.

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

2. Кожній змінній прямої задачі відповідає обмеження двоїстої задачі,

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

14

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

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

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

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

Процес побудови математичної моделі двоїстої задачі зручно зобразити

схематично (рис. 1).

Рис. 1 – Схема переходу від математичної моделі прямої задачі лінійної

оптимізації до двоїстої задачі

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

несиметричних задачах обмеження прямої задачі можуть бути записані як

15

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

Розглянемо постановку задачі та математичну модель двоїстої задачі по відношенню до задачі визначення оптимального плану виробництва продукції підприємства (3) – (6), (7). Згідно зі схемою на рис. 1 можемо записати:

Зміст завдання оптимізації за моделлю (12) полягає в наступному:

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

Зв’язок між оптимальними розв’язками прямої та двоїстої задач встановлюють леми і теореми двоїстості, результати яких тут наведено без доведення [2; 3; 4; 6; 7; 8]. Розглянемо економічні задачі лінійної оптимізації виробництва, що виражені спряженими моделями (2) і (11).

Основна нерівність теорії двоїстості стверджує: якщо X = (X1, X2, … , Xn)

та Y = (Y1, Y2, … , Ym) – допустимі розв’язки, відповідно, прямої і двоїстої задач,

то виконується нерівність Z (X ) ≤ F (Y).

Достатня умова оптимальності. Якщо X٭ = (X1٭, X2٭, … , Xn٭) і Y٭ = (Y1٭,

Y2٭, … , Ym٭) – допустимі розв’язки прямої та двоїстої задач, для яких

16

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

то він є цінним для виробництва і його оцінка Yj٭ буде строго більше нуля.

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

Якщо витрати на виробництво i-го виду продукції дорівнюють її питомому прибутку ci, то її необхідно виготовляти в кількості, що визначає оптимальний план прямої задачі Xi٭ > 0.

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

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

Дане твердження формулюється у вигляді третьої теореми двоїстості:

компоненти оптимального плану двоїстої задачі Yj٭ дорівнюють значенням частинних похідних від цільової функції F (b1, b2, … , bm) за відповідними аргументами bj, тобто ∂F/∂bj = Yj٭.

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

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

люд.-год., га тощо.

18

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

числові значення двоїстих оцінок показують, на яку величину змінюється цільова функція при зміні обсягу відповідного даній оцінці ресурсу Yj٭ = ∂F/∂bj.

Таким чином, при малій зміні bj замість задачі (2), поданої в канонічній формі, отримаємо нову задачу, де bj замінено на bj′ = bj + ∆bj′. Позначимо X′ –

оптимальний план нової задачі. Для визначення цільової функції Z (X′) не потрібно розв’язувати нову задачу лінійного програмування, достатньо скористатись формулою

де X٭ – оптимальний план задачі (2).

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

3. Розв’язання задачі оптимізації виробничого плану підприємства за

допомогою програми «Поиск решения» редактора Excel

Знайти розв'язок задачі лінійного програмування можна різними способами.

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

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

Щоб активізувати програму «Поиск решения», виконайте такі кроки:

• натисніть поле «Параметры Excel», а потім виберіть категорію «Надстройки»;

19

•у полі «Управление» виберіть значення «Надстройки Excel» та натисніть кнопку «Перейти»;

•у полі «Доступные надстройки» встановіть прапорець поруч із пунктом

«Поиск решения» та натисніть кнопку ОК;

•у головному меню редактора Excel при вибої категорії «Данные» в кінці

панелі з'являється розділ «Анализ» з опцією «Поиск решения».

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

max Z = 13600Х1 + 591Х2 + 3086Х3 + 1107Х4 + 8290Х5 + 5429Х6 8478,10Х1 + 238,61Х2 + 1494,27Х3 + 570,71Х4 + 5381,02Х5 + 1587,59Х6 ≤ 267525600

Безпосереднє використання програми «Поиск решения» складається з двох

етапів:

1)побудова у відкритому листі редактора Excel допоміжної електронної таблиці з вихідними даними;

2)застосування керуючої панелі «Параметры поиска решения», що з'являється при натисканні на поле «Поиск решения» в розділі «Анализ».

Перший етап використання програми «Поиск решения» виконується на

основі даних моделі (15) (див. табл. 4).

20