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

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

1. Огляд теми

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

1.1 Економічна інтерпретація задачі, двоїстої до задачі використання ресурсів.

1.2 Алгоритм побудови математичної моделі двоїстої задачі.

1.3 Зв’язок між розв’язками прямої та двоїстої задач.

1.4 Економічний зміст двоїстих оцінок.

1.5 Аналіз тривалості (стійкості) двоїстих оцінок.

1.6 Двоїстий симплексний метод.

1.1. Економічна інтерпретація задачі, двоїстої до задачі використання ресурсів

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

Згадаємо задачу про вирощування фермером норок і нутрій.

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

Вид корму

Добовий раціон

Запаси кормів

Норки

Нутрії

І

2

3

180

ІІ

4

1

240

ІІІ

6

7

426

Прибуток

16

6

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

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

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

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

.

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

.

1.2 Алгоритм побудови математичної моделі двоїстої задачі

Сформулюємо з Вами Алгоритм переходу від прямої до двоїстої задачі.

1)  Цільова функція прямої задачі прямує до максимуму, а цільова функція двоїстої задачі – до мінімуму.

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

Транспонування матриці – заміна рядків стовпчиками, а стовпчиків – рядками.

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

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

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

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

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

8)  Якщо -те співвідношення прямої задачі є нерівністю, то -та змінна двоїстої задачі . В протилежному випадку змінна може приймати як додатні, так і від’ємні значення.

Виходячи із побудованого алгоритму запишемо визначення двоїстої задачі по відношенню до загальної задачі ЛП:

Нехай задана задача:

(1.1)

Задача знаходження мінімального значення функції при заданих умовах:

(1.2)

1.3 Зв’язок між розв’язками прямої та двоїстої задач

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

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

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

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

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

В останню симплексну таблицю розв’язання задачі про норок і нутрій додамо ще один рядок:

Базис

Сб

План

16

6

0

0

0

Х1

Х2

Х3

Х4

Х5

1

Х3

0

30

0

0

1

2/11

-5/11

2

Х1

16

57

1

0

0

7/22

-1/22

3

Х2

6

12

0

1

0

-3/11

2/11

M+1

984

0

0

0

38/11

4/11

У4

У5

У1

У2

У3

В цей рядок під додатковими змінними прямої задачі () вписують основні змінні двоїстої (). І навпаки, під основними змінними прямої задачі () в останній рядок вписують додаткові змінні двоїстої задачі ().

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

1.4 Економічний зміст двоїстих оцінок

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

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

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

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

.

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

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

1.5 Аналіз тривалості (стійкості) двоїстих оцінок

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

Для відповіді на це питання і використовують так званий інтервал стійкості (незмінності) двоїстих оцінок.

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

В загальному випадку Зміна коефіцієнтів вихідної задачі Може призвести До однієї з Ситуацій:

1)  Поточний базисний розв’язок залишається допустимим.

2)  Поточний базисний розв’язок стає недопустимим.

3)  Поточний базисний розв’язок стає неоптимальним.

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

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

До Неприпустимості поточного Оптимального Розв’язку може Призвести:

A)  зміна правих частин обмежень (тобто зміна вектора );

B)  введення в систему обмежень нового обмеження.

Неприпустимість розв’язку виявляється в тому, що хоча б один елемент вектора „План” стає від’ємним, тобто одна або декілька базисних змінних набувають від’ємного значення.

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

Припустимо, що фермер планує розширити власне господарство за умов збільшення запасів кормів на 20%, тобто запаси кормів будуть складати 216, 288 та 511,2 ум. од. відповідно.

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

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

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

Перша нерівність перетворюється в .

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

Припустимо, що частину коштів, що витрачались на корм першого виду (його залишки складають 30 гр. од.), фермер вирішив витратити на закупку кормів 2 та 3 видів. Нехай нові запаси кормів складають 155, 250 і 450 ум. од. відповідно. Знайдемо новий розв’язок

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

1.6 Двоїстий симплексний метод

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

Особливості двоїстого симплексного методу:

1)  Критерій оптимальності: стовпчик „План” не містить від’ємних елементів.

2)  Правило вибору направляючого рядка: серед від’ємних елементів стовпчика „План” знаходимо найменший. Рядок, в якому він знаходиться, називається направляючим, а змінна, яка йому відповідає, виключається з базису.

3)  Правило вибору направляючого стовпчика: ділять почленно елементи (m+1)-го рядка, взяті із знаком „мінус”, на відповідні від’ємні елементи направляючого рядка. Серед отриманих часток обирають найменшу. Стовпчик, в якому вона знаходиться, називають направляючим, а змінна, яка йому відповідає, виводиться з базису.

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

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

Курносов А. П., Сысоев И. А. Вычислительная техника т экономико-математические методы в сельском хозяйстве. — М., 1989. Кузнецов Ю. Н., Кузобов В. И., Ермольев Ю. М. Математическое программирование. — М.: Высш. шк., 1976. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. Исследование операций в экономике: Учебн. пособие для вузов/ Н. Ш.Кремер, Б. А.Путко, И. М.Тришин. М. Н.Фридман; Под ред. проф. Н. Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. Акулич И. Л. Математическое программирование в примерах и задачах. — М.: Высш. Шк.», 1986, — 319 с . Ляшенко И. Н. Линейное и нелинейное программирование. — і К.: Вищашк., 1975,-371 с.

7.  Математическое моделирование экономических процессов в сельском хозяйстве/ Гатаулин А. М. и др.; Под ред. А. М.Гатаулина. – М.: Агропромиздат, 1990. – 432с.:ил.

8.  Эддоус М., Стэнфилд Р. Методы принятия решений/ Пер. с англ. под ред. член-корр. РАН И. И.Елисеевой. – М.: Аудит, ЮНИТИ, 1997. – 590с.

Крушевский А. В., Шевцов К. И. Математическое программирование и моделирование в экономике.: Учеб. пособие для вузов. – Киев: Высшая школа. Головное изд-во, 1979. – 456с. Курицкий Б. Я. Поиск оптимальных решений средствами Excel 7.0. – СПб.: ВНV – Санкт-Петербург, 1997. – 384с., ил. Ляшенко И. Н. Лінійне та нелінійне програмування. — К.: Вища шк., 1975. Степанюк В. В. Методи математичного програмування. — К.: Вища шк., 1984. Кузнецов Ю. Н., Кудрявцев В. И. Математическое программирование. — М., 1980. Франс Дж. и др. Математические модели в сельском хозяйстве. М.: Агропромиздат, 1987 Кравченко Р. Г. Математическое моделирование в сельском хозяйстве. М.:Колос, 1978. Кузнецов Ю. Н. Математические модели в с/х. М.: Высшая школа, 1981 Карпенко А. ф. Практикум по математическому моделированию экономических агропромышленных процессов в сельском хозяйстве. М.: Финансы и статистика, 1985.

Ви прочитали: "Двоїсті задачі"
Читати далі

Related Posts
Лекції