Написание контрольных, курсовых, дипломных работ, выполнение задач, тестов, бизнес-планов

Двоїстість у лінійному програмуванні.

Тема 3. Двоїстість у лінійному програмуванні.

Мета: Навчитися будувати, інтерпретувати та розв’язувати двоїсті задачі ЛП (в т.ч. й засобами MS Excel).

План.

1. Побудова задачі, двоїстої до даної.

2. Визначення економічного змісту основних і додаткових змінних двоїстої задачі.

3. Аналіз задачі на чутливість за допомогою звітів, що генеруються Microsoft Excel.

 

1. Побудова задачі, двоїстої до даної.

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

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

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

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

.

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

.

2. Визначення економічного змісту основних і додаткових змінних двоїстої задачі.

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

Розтлумачимо економічний зміст двоїстої оцінки . Якщо збільшити кількість корму ІІ виду на одиницю, тобто якщо його кількість складатиме 241, то загальний прибуток збільшиться на 38/11 і складатиме 984+38/11=987 5/11 гр. од.. При цьому числа, що знаходяться у відповідному до змінної  стовпчику, показують, як при цьому зміниться план випуску продукції: залишок сировини першого виду збільшиться на 2/11 і складатиме , кількість продукції 1-го виду збільшиться на 7/22 і складатиме , кількість продукції другого виду зменшиться на 3/11 і складатиме .

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

Що показують додаткові змінні двоїстої задачі? Розглянемо першу нерівність двоїстої задачі:

.

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

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

 

3. Аналіз задачі на чутливість за допомогою звітів, що генеруються Microsoft Excel.

Для аналізу чутливості в середовищі електронних таблиць формуються наступні звіти (рис. 1): Звіт по результатам, звіт по сталості, звіт по границям.

Рис. 1. Результати пошуку розв’язку

Розглянемо звіт за результатами, що відповідає Типу отчета: Результаты (рис. 2).

Рис. 2 Звіт за результатами

Звіт за результатами містить інформацію про три компоненти задачі оптимізації: цільової функції (Целевая ячейка), розв’язку (Изменяемые ячейки), і обмежень (Ограничения).

1 – початкове значення цільової функції при початковому опорному плані (Исходное значение (3));

2 – максимальне або мінімальне значення (залежно від завдання) цільової функції. У нашому випадку — 285 грош. од.;

3 – початковий опорний план;

4 – оптимальний план (розв’язок) задачі. У даному випадку, щоб одержати максимальний прибуток у розмірі 285 грош. од., потрібно виготовляти 35 одиниць товару С и 45 одиниць товару Д (зрозуміло, що товар повинен бути в цілих одиницях, але якщо задати такий параметр, то звіти, які потрібні для аналізу й покращення отриманих результатів не генеруються);

5 – показує кількість використаних ресурсів на виробництво при оптимальному плані;

6 – формули обмежень;

7 – показує вплив обмежень на кінцевий результат. Якщо статус «связанное», тоді дане обмеження впливає на отриманий оптимальний план, якщо «не связан.» — не впливає. У даному прикладі ресурс 2 має статус «не связан.» — це означає, що цей ресурс не обмежує можливості у виробництві, що не можна сказати про ресурс 1 та 3, які використано повністю;

8 – різниця між наявною кількістю ресурсів і тією, що використана при отриманні оптимального плану. Для нашого прикладу бачимо, що ресурс 2 є ще в наявності на складі (30 ум. од.).

Розглянемо звіт по стійкості, що відповідає Типу отчета: Устойчивость (рис. 3).

Рис. 3 Звіт по стійкості

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

1 – оптимальний план (розв’язок) задачі. У даному випадку, щоб одержати максимальний прибуток у розмірі 285 грош. од., необхідно виготовляти 35 одиниць товару С та 45 одиниць товару Д;

2 – нормована вартість, яка стосується невідомих плану. Це невдалий переклад з оригіналу reduced cost, яку можна було перевести, як «ціна, що зменшує (цільову функцію)». Цей показник вказує на те, як зміниться оптимальне значення цільової функції при випуску продукції, якої немає в оптимальному плані. Так як нормована вартість товару А дорівнює – 5, то примусовий випуск 2 одиниць товару А (якого немає в оптимальному плані) привів би до зменшення Прибутку на 2·5=10 і становив би 285–10 = 275 грош. од. Так само, нормована вартість товару В дорівнює -2,5, то якщо б ми примусово випустили 2 одиниці товару В, то Прибуток зменшився б на 2·(-2,5) = 5 і становив би 285 – 5 = 280 грош. од.

3 – коефіцієнти цільової функції;

4, 5 – границі змін значень коефіцієнтів цільової функції за умови, що оптимальна кількість продукції (план) не зміниться. Наприклад, якщо цільовий коефіцієнт товару Д (КД) дорівнює 4 (ціна за 1 одиницю товару), то змінюючи його в рамках (Допустимое Увеличение, Допустимое Уменьшение)

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

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

6 – кількість використаних ресурсів;

7 – тіньова ціна стосується обмежень, тобто, певне значення вказує на «цінність» обмеженого ресурсу в порівнянні з іншими ресурсами. Цей показник указує на те, як зміниться оптимальне значення цільової функції (Прибуток) при зміні запасів ресурсів на 1 одиницю.

Наприклад, якщо збільшити запас ресурсу 3 на 10 одиниць, то прибуток збільшиться на 10·2=20 і буде становити 285+20=305 грош. од.

8 – запаси ресурсів;

9, 10 – задають діапазон для 8, у якому діє тіньова ціна (7) (аналогічно (4) та (5) для цільової функції).

Наприклад, діапазон ресурсу 1: 160 < ресурс 1 < 280. Якщо ресурс 1 збільшити на 10 одиниць, то прибуток збільшиться на 5 і буде становити 290. Якщо цей ресурс збільшити на 40 одиниць, то про прибуток нічого сказати не можна, оскільки ми вийшли за зазначені межі.

Розглянемо звіт по границям, що відповідає Типу отчета: Пределы (рис. 4).

Рис. 4 Звіт по границям

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

1 – значення цільової функції (Прибуток);

2 – оптимальний план задачі;

3 – найменше значення, що може прийняти невідоме (у даному випадку кількість товару А, В, С та Д має Нижню границю 0, оскільки в Параметрах Поиск решений зазначили невід’ємність значень);

4 – це значення, що буде знаходитись в цільовій клітинці (Прибуток), якщо невідоме дорівнюватиме Нижний предел;

5 – це найбільше значення, що можуть прийняти невідомі, щоб одержати максимальне значення цільової функції;

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

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

Випуск продукції А та В не передбачається, а С і Д у кількості відповідно 35 та 45 од. За такого оптимального плану виробництва продукції та використання ресурсів підприємство отримує найбільшу виручку у розмірі 285 ум. од.

Другий ресурс використовується у процесі виробництва продукції не повністю, а перший та третій ресурси – повністю.

Таким чином, виготовлення продукції А та В нерентабельне, а С та Д – рентабельне, при цьому ресурси 1 та 3 дефіцитні, а ресурс 2 – недефіцитний.

Примусовий випуск 1 одиниці товару А привів би до зменшення Прибуток на 5 грош. од. і становив би 285–5 = 280 грош. од. Примусовий випуск 1 одиниці товару В зменшить Прибуток на 2,5 грош. од. і становив би 285–2,5 = 282,5 грош. од.

Границі змін значень коефіцієнтів цільової функції за умови, що оптимальна кількість продукції (план) не зміниться:

при цьому план не зміниться, але значення прибутку може зменшитись або збільшитись.

Діапазон ресурсу 1: 160<ресурс 1<280, якщо ресурс 1 збільшити на 10 одиниць, то прибуток збільшиться на 5 і буде становити 290. Діапазон ресурсу 2: 250<ресурс 2<+∞. Збільшення одиниць ресурсу 2 не змінить прибуток. Діапазон ресурсу 3: 62,5<ресурс 1<125, якщо ресурс 3 збільшити на 10 одиниць, то прибуток збільшиться на 20 і буде становити 305.

Останні зауваження щодо зв’язку прямої та двоїстої задачі.

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

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

Зауваження 3. Можна використати змінну в якості базисної, якщо вона присутня тільки в одному обмеженні й з коефіцієнтом = 1, тобто

х3 – може бути базисною змінною, а х4 - ні.

 

Методичне забезпечення

  1. Сергієнко В.А. Математичне програмування. Конспект лекцій для студентів напряму підготовки 6.030601 „Менеджмент” денної та заочної форм навчання / В.А. Сергієнко, Л.П. Перхун, 2010. – 140 С.
  2. Лавров Є.А. Математичне програмування: навчальний посібник / Є.А. Лавров, Л.П. Перхун, В.А. Сергієнко / За ред. Є.А. Лаврова. – Суми, 2010. – 224 С.

 

Рекомендована література

Базова

  1. Бех О.Б. Збірник задач з математичного програмування. Навч. пос. / О.Б. Бех, Т.А. Огородня, А.Ф. Щебрак – К.: Видавництво Ліра-К, 2013. – 212 С.
  2. Бех О.Б. Математичне програмування. Пос. / О.Б. Бех, Т.А. Огородня, А.Ф. Щебрак – К.: Видавництво Ліра-К, 2013. – 200 С.
  3. Вдовин М. Л. Математичне програмування теорія та практикум. Пос. / М.Л. Вдовин, С.Г. Данилюк – К.: Видавництво Ліра-К, 2014. – 160 С.
  4. Глушик М. М. Математичне програмування. Підручник / М. М. Глушик, І.М. Копич, В.М. Сороківський – К.: Видавництво Ліра-К, 2014. – 280 С.
  5. Глушик М. Математичне програмування. Підручник / М. Глушик, І.Копич, О.Пенцак, В. Сорківський – К.: Видавництво Ліра-К, 2013. – 216 С.
  6. Копич І.М. Математичні моделі в менеджменті та маркетингу. Навч. пос. / І.М. Копич, В.М. Сороківський ,В.І.Стефаняк – К.: Видавництво Ліра-К, 2014. – 376 С.
  7. Кучма М.І. Математичне програмування: приклади та задачі. пос. / М.І. Кучма – К.: Видавництво Ліра-К, 2013. – 344 С.
  8. Мартиненко М.А. Математичне програмування: підручник / М.А. Мартиненко, О.М. Нещадим, В.М. Сафонов – К.: Видавництво Ліра-К, 2010. – 311 С.

 

Інформаційні ресурси

(в т.ч. електронна бібліотека СНАУ)

  1. http://web.archive.org/web/20070205063920/http://dims.karelia.ru/~alexmou/tpr/tpr_02_linear_programming.ppt – слайди по лінійному програмуванню
  2. Український інститут ІТ в освіті Економіко-математичне моделювання (Демо-версія)  [Електронний ресурс]. – Режим доступу: http://moodle.ipo.kpi.ua/moodle/mod/resource/index.php?id=125
  3. Іващук О.Т. Економіко-математичне моделювання [Електронний ресурс] / О.Т. Іващук. – Т.: ТНЕУ «Економічна думка», 2008. – 704 с.
  4. Курило А.О. Математичне програмування. Конспект лекцій. - Суми, 2015 рік 136 ст., табл. 51, рис. 36.
  5. Курило А.О. Математичне програмування. Частина 1: методичні вказівки щодо виконання практичних та самостійних робіт. – Суми, 2015, ст.76, табл. 20, рис. 11.
  6. Курило А.О. Математичне програмування. Частина 2: методичні вказівки щодо виконання практичних та самостійних робіт. – Суми, 2015, ст.84, табл. 16, рис. 13.
  7. Сергієнко В.А.  Математичне програмування. Конспект лекцій для студентів напряму підготовки 6.030601 „Менеджмент” денної та заочної форм навчання./ В.А.Сергієнко, Л.П. Перхун. 2009 – 149 с.
  8. Сергієнко В.А., Перхун Л.П. Електронний засіб навчального призначення: «Математичне програмування» для студентів денної та заочної форм навчання за напрямом підготовки 6.030601 «Менеджмент», 2010.