Xreferat.com » Рефераты по экономико-математическому моделированию » Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

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

/>. Аналогічне міркування проведемо для (3.27), після чого можна висновувати, що Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів.

Достатність. За умовою виконуються рівняння


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

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


Необхідно довести, що X* та Y* – оптимальні плани відповідно прямої (3.20) та двоїстої (3.21) задач. У кожному рівнянні розкриємо дужки та підсумуємо перше рівняння по Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів, а друге – по Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів. Отримаємо:


Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів;

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


Ліві частини цих рівнянь однакові, отже, Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планівДвоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів. Тоді за першою теоремою двоїстості, оскільки значення цільових функцій цих задач збігаються, можна висновувати, що X* та Y* – оптимальні плани спряжених симетричних задач. Теорему доведено.

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

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

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

Економічний зміст другої теореми двоїстості стосовно оптимального плану Х* прямої задачі. Якщо для виготовлення всієї продукції в обсязі, що визначається оптимальним планом Х*, витрати одного і-го ресурсу строго менші, ніж його загальний обсяг Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів, то відповідна оцінка такого ресурсу Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів(компонента оптимального плану двоїстої задачі) буде дорівнювати нулю, тобто такий ресурс за даних умов для виробництва не є «цінним».

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

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

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


3.3 Третя теорема двоїстості


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

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

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів(3.28)

Доведення. Розглянемо задачу лінійного програмування, подану в канонічній формі:


Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів(3.29)


Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів(3.30)


Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів(3.31)


Двоїсту задачу до задачі (3.29) – (3.31) сформулюємо так: знайти оптимальний план Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів, за якого мінімізується значення


Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів(3.32)


за умов:

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів(3.33)


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

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

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

або


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


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


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


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

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

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

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

Отже, за умови незначних змін Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планівзамість задачі (3.29) – (3.31) маємо нову задачу, де Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планівзамінено на Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів. Позначимо через Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планівоптимальний план нової задачі. Для визначення Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планівне потрібно розв’язувати нову задачу лінійного програмування, а достатньо скористатися формулою Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів, де Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів – оптимальний план задачі (3.29) – (3.31).


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


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

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


max Z = – 5x1 + 2x2;

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


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


max Z = – 5x1 + 2x2;

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


Тепер за відповідними правилами складемо двоїсту задачу:


min F = – y1 + 5y2;

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

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


1. max Z = – 5x1 + 2x2 + 0x3 + 0x4;

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


2. Векторна форма запису системи обмежень має вигляд:


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

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


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

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


maxZ = – 5x1 + 2x2 + 0x3 + 0x4 – Мx5;

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


У цій задачі х4 та х5 – базисні змінні, а х1, х2, х3 – вільні. Нехай х1 = х2 = х3 = 0, тоді х4 = 5; х5 = 1.

Перший опорний план задачі:

X0 = (0; 0; 0; 5; 1), Z0 = – M.

З останньої симплекс-таблиці запишемо оптимальний план прямої задачі:

Х* = (0; 5/3; 2/3; 0), Zmax = 10/3.

Згідно зі співвідношенням двоїстості за першою теоремою можна висновувати, що оптимальний план двоїстої задачі існує і min F = max Z = 10/3.

Компоненти вектора Y* (оптимальний план двоїстої задачі) визначимо за формулою:


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


де Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планівта міститься в стовпчику «сбаз» останньої симплекс-таблиці;

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

Матриця D– 1 також міститься в останній симплекс-таблиці у стовпчиках змінних «x5» та «x4», які утворювали початковий базис.

Отже,


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

min F = – 1 х 0 + 5 х 2/3 = 10/3.


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

До заданої задачі лінійного програмування записати двоїсту задачу. Розв’язавши двоїсту задачу графічно, визначити оптимальний план прямої задачі.


min Z = x1 + 2x2 + 2x3;

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

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

mах F = y1 + 4y2;

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

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

Двоїста задача має дві змінні, а отже, її можна розв’язати графічно (рис. 3.2).


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

Рис. 3.2


Найбільшого значення цільова функція двоїстої задачі F досягає в точці В багатокутника ABCD. Її координати визначимо розв’язанням системи рівнянь:


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

Отже, Y* = (– 2/3; 4/3); mах F = 1 х (– 2/3) + 4 х 4/3 = 14/3.

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

Підставимо Y* у систему обмежень двоїстої задачі і з’ясуємо, як виконуються обмеження цієї задачі:

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


Оскільки перше обмеження для оптимального плану двоїстої задачі виконується як строга нерівність, то висновуємо, що перша змінна прямої задачі дорівнюватиме нулю х1 = 0 (перша частина другої теореми двоїстості).

Тепер проаналізуємо оптимальний план двоїстої задачі. Оскільки друга компонента плану у2 = 4/3 додатна, то друге обмеження прямої задачі для Х*виконуватиметься як строге рівняння (друга частина другої теореми двоїстості).

Об’єднуючи здобуту інформацію, можна записати систему обмежень прямої задачі як систему двох рівнянь, в якій х1 = 0, та визначити решту змінних:


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


тобто Х* = (0; 5/3; 2/3), min Z = 1 х 0 + 2 х 5/3 + 2 х 2/3 = 14/3.

Умова min Z = max F = 14/3 виконується, і тому Х* = (0; 5/3; 2/3); Y* = (– 2/3; 4/3) є оптимальними планами відповідно прямої та двоїстої задач.

Визначити, чи є оптимальними такі плани сформульованої задачі лінійного програмування:


min Z = 12x1 – 4x2 + 2x3;

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


а) Х = (8/7; 3/7; 0); б) Х = (0; 1/5; 8/5); в) Х = (1/3; 0; 1/3).

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

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

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

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

Запишемо двоїсту задачу до прямої задачі лінійного програмування:

max F = y1 + 2y2;

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

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

Перевіримо запропоновані плани на оптимальність.

1. Х = (8/7; 3/7; 0). Підставимо його в систему обмежень прямої задачі:

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

Обидва обмеження виконуються, і тому Х = (8/7; 3/7; 0) є допустимим планом прямої задачі. Припустимо тепер, що зазначений план є оптимальним планом прямої задачі. Тоді розрахуємо для нього величину цільової функції: Z = 12 х 8/7 – 4 х 3/7 + 2 х 0 = 12.

Скористаємося другою теоремою двоїстості та визначимо відповідний план двоїстої задачі. Оскільки x1 = 8/7 > 0; x2 = 3/7 > 0, то згідно з другою частиною другої теореми двоїстості можна записати перше та друге обмеження як рівняння і визначити у1 та у2:

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

Підставимо ці значення в третє обмеження системи двоїстої задачі:

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів;

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

Для визначених значень у1 = 4; у2 = 4 це обмеження не

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: