Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Двойственный симплекс-метод
|
|
прямая задача: min z = CX;
двойственная задача: max u = BY;
пример: min z = 3 x 1 + 2 x 2 – x 3.
max u = 4 y 1 + 5 y 2
Утверждение: max u = min z.
Если в столбце X опт есть хотя бы один отрицательный элемент, а в строке оценок отрицательных элементов нет, то можно применять двойственный симплекс-метод.
1. (Находим перемененную, выводимую из базиса). В столбце X опт выбирается наибольший по модулю отрицательный элемент. Соответствующая строка разрешающая.
2. Ищут отношение элементов строки оценок к отрицательным элементам разрешающей строки. Столбец, в котором это отношение наибольшее (или наименьшее по модулю) – разрешающий.
Условие оптимальности: в столбце X опт и в строке оценок нет отрицательных элементов.
пример.
min z = 10 x 1 + 8 x 2; max (– z) = – 10 x 1 – 8 x 2.
| базис | С | X опт | – 10 | – 8 | |||
| x 1 | x 2 | s 1 | s 2 | s 3 | |||
| s 1 | – 5 | – 1 | – 2 | ||||
| s 2 | – 12 | – 2 | |||||
| s 3 | – 4 | – 1 | – 3 | ||||
| – z | |||||||
| s 1 | – 5/2 | – 1/2 | |||||
| x 1 | – 10 | – 1/2 | – 1/2 | ||||
| s 3 | – 7/2 | – 1/2 | |||||
| – z | – 60 |
Итак, x 1 = 6, x 2 = 0; s 1 = 1; s 3 = 2; max (– z) = – 60; min z = 60.