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

Розв’язування задач на мінімум цільової функції

Розглянемо задачу:

Z = C ∙ X " min

AX ≤ B

X ≥ 0

Позначимо F = - Z.

Тоді max F= -min Z, і можна розв’язувати задачу (3.1)-(3.3)

3. Розглянемо пари симетричних задач.

F = C ∙ X"max (3.1) Z = Y ∙ B " min (3.4) (3.4)

A ∙ X ≤ B (3.2) Y∙A ≥ C (3.5) (3.5)

X ≥ 0 (3.3) Y ≥ 0 (3.6) (3.6)

де

Кожна задача називається двоїстою стосовно іншої. Якщо вихідна задача (3.1)-(3.3) є задачею про оптимальний план випуску продукції, то двоїста (3.4)-(3.6) є задача про використання ресурсів.

y_i- ціна (оцінка) відповідного ресурсу, а Z=Y∙ В - вартість усіх ресурсів.

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

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

Теорема. Якщо з пари двоїстих задач в одній є оптимальний план, то й інша має розв’язок, при цьому min Z=max F.

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

Теорема справедлива і для пари несиметричних задач:

F = С ∙ X ® max Z = Y ∙ У ® min

А ∙ X = В Y ∙ A ³ C

X 0

Умова невід’ємності для другої задачі відсутня.

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

4. Приклад

Z = x₁ + 2x₂ + 3x₃ ®min

x_j ³ 0; j = 1,2,3.

Складемо і розв’яжемо двоїсту задачу.

F = 2y₁ + 3у₂ + 6у₃ + 3у₄ ® max

у_i ³ 0; i = 1,2,3,4

Уводимо додаткові змінні.

F = 2y₁ + 3у₂ + 6у₃ + 3у₄ +0×у₅+0×у₆+0×у₇® max

План не є оптимальним F (Y₀) = 0.

План не є оптимальним F (Y₁) = 6.

План оптимальний F (Y₂) = 10,5.

Одержали розв’язок двоїстої задачі.

; F_max = F (Y^*) = 10,5.

Для вихідної задачі Z_min = 10,5.

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

х₁ = 1,5+0 = 1,5

х₂ = 4,5+0 = 4,5

х₃ = 0+0 = 0 Z_min = Z (X^*) = 10,5

Контрольні запитання

1. Як перетворити неканонічну ЗЛП у канонічну за допомогою додаткових змінних?

2. Яким є алгоритм розв’язування задач ЛП на мінімум цільової функції?

3. Що таке симетричні задачі ЛП?

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

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

1. I. Застосування похідної та інтеграла до роз’язування задач елементарної математики.
2. А) Задачі, що розкривають зміст дій
3. АВТОМАТИЗАЦІЯ РОЗВ’ЯЗУВАННЯ КОМПЛЕКСУ ЗАДАЧ З ОБЛІКУ ОСНОВНИХ ЗАСОБІВ ТА НЕМАТЕРІАЛЬНИХ АКТИВІВ
4. Автоматизоване робоче місце (АРМ) бухгалтера: призначення, функції та його рівні
5. Адвокатура в Україні: основні завдання і функції
6. Адміністративна відповідальність: поняття, мета, функції, принципи та ознаки.
7. Алгоритм знаходження ДДНФ (ДКНФ) для даної булевої функції
8. Алгоритм розв’язання задачі
9. Алгоритм розв’язання задачі
10. Алгоритм розв’язання розподільної задачі
11. Алгоритм розв’язування задачі
12. Алгоритм розв’язування задачі

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