• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Тема 4. Теорія двоїстості та аналіз лінійних оптимізаційних задач

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

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

Якщо пряма задача ЛП має вигляд

Z = c₁x₁ + c₂x₂ + … + c_nx_n ® max

,

то двоїстою до неї буде:

F = b₁y₁ + b₂y₂ + … + b_my_m ® min

.

Приклад 4.1

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

Z = 6x₁ – 4x₂ ® min

Розв’язання

Помножимо другу нерівність на -1, щоб звести задачу до стандартного вигляду. Для зручності можна написати цільову функцію після системи обмежень. Стовпчики прямої задачі стануть рядочками двоїстої, а рядочки – стовпчиками. Знаки нерівностей в обмеженнях зміняться на протилежні.

Z = 6x₁ – 4x₂ ® min

Двоїста задача виглядатиме наступним чином:

F = 2y₁ – 8y₂ ® min

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

Розглянемо економічну інтерпретацію двоїстої задачі.

Приклад 4.2

Підприємство виготовляє 4 види продукції, використовуючи для цього три види ресурсів 1, 2, 3 (табл. 4.1). Визначити план виробництва продукції, що забезпечує підприємству найбільший дохід. Ціна одиниці продукції становить відповідно 7, 4, 2 та 1 у. о.

Таблиця 4.1

Норми витрат ресурсів на одиницю продукції та їх запаси

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

Розв’язання

Складемо економіко-математична модель прямої задачі:

Остання симплекс-таблиця прямої задачі має наступний вигляд (табл. 4.2):

Таблиця 4.2

Застосування симплекс-методу – остання ітерація

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

Економіко-математична модель двоїстої задачі наступна:

Змінна y₁двоїстої задачі пов’язана з x₅прямої, y₂– з х₆, y₃– з х₇.

Таким чином, оптимальний план двоїстої задачі y₁= 1½, y₂=2, y₃=0. Третя сировина не повністю використовується у виробництві, тому є недефіцитною.

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

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

Читайте також:

1. ABC-XYZ аналіз
2. E) теорія раціонального вибору.
3. I етап. Аналіз впливу типів ринку на цінову політику.
4. I. Теорія граничної продуктивності і попит на ресурси
5. II. Багатофакторний дискримінантний аналіз.
6. II. Критерій найбільших лінійних деформацій
7. III етап. Аналіз факторів, що визначають цінову політику підприємства.
8. SWOT-аналіз у туризмі
9. SWOT-аналіз.
10. Tема 4. Фації та формації в історико-геологічному аналізі
11. V теорія граничної корисності визначає вартість товарів ступенем корисності останньої одиниці товару для споживача.
12. V. Нюховий аналізатор

Переглядів: 673