Розглянемо задачу наступного вигляду
F = C ∙ X"max (3.1)
A ∙ X ≤ B (3.2)
X ≥ 0 (3.3)
За допомогою введення додаткових змінних ця задача приводиться до канонічного вигляду. Розмірність задачі збільшується. Після розв’язування нової задачі додаткові змінні виключаються (відкидаються) з отриманого оптимального плану.
Приклад.
Уведемо додаткові змінні x3 і x4 і перетворимо обмеження в рівності:
Додамо формально нульові доданки в цільову функцію:
F = 2x1 + 3x2 + 0∙ x3 + 0∙ x4 "max
Вважаючи xj ≥0 для j = 1,2,3,4, розв’яжемо отриману задачу табличним симплексом-методом.
Базис
С баз
В
А1
А2
А3
А4
!
А3
А4
Fj - Cj
-2
-3
↑
!
А2
А4
1/2
1/2
1/2
-1/2
Fj - Cj
-1/2
↑
3/2
A2
A1
-1
-1
Fj - Cj
,
План не оптимальний. Виконаємо поліпшення плану. Вектор А3 виводиться з базису; уводиться вектор А2 .
;
План не оптимальний. Виводимо з плану вектор А4 ; уводимо вектор А1 .
Отриманий план є оптимальним.
Для первинної задачі ;
Оптимальний розв’язок єдиний.
Читайте також:
Вибір форми перетину гірничої виробки та вигляду крепі. Види наступного аналізу Види наступного аналізу Визначення якості антифризу по зовнішньому вигляду Відповідно до ст. 69 ЦПК перебіг процесуального строку починається з наступного дня після відповідної календарної дати або настання події, з якою пов'язано його початок. Зведення рівняння другого порядку до канонічного вигляду Зв’язок вигляду М:М Існує кілька методів розрахунку складних електричних кіл. Розглянемо основні з них. Обробка переривань з переключенням на нову задачу. Означення. Лінійною комбінацією векторів векторного простору називається вектор вигляду Поняття про двоїсту задачу лінійного програмування. Поняття про редукційну задачу
Не знайшли потрібну інформацію? Скористайтесь пошуком google: