- •Математические модели задач лп
- •1.1. Постановка задачи лп
- •1.2. Рекомендации к составлению математических моделей
- •1.3. Пример задачи лп --- задача о диете
- •Графическое решение задач лп
- •2.1. Каноническая форма задачи лп
- •2.2 Пример
- •2.3. Общие рекомендации к графическому решению задач лп
- •2.4. Пример
- •3. Численные методы решения задач лп
- •3.1. Симплекс – метод
- •3.2. Алгоритм симплекс-метода для задачи на минимум
- •3.3. Алгоритм симплекс-метода для задачи на максимум
- •На шаге 2::
- •На шаге 4: .
- •3.4. Пример
- •3.5. Метод искусственного базиса
- •3.6. Пример
- •3.7. Двойственный симплекс-метод
- •3.8. Пример
- •4. Двойственность в лп
- •4.1. Постановка задачи
- •4.2. Пример
- •4.3. Теоремы двойственности
- •4.4. Пример
- •4.5. Пример
- •5. Метод Гомори
- •5.1. Постановка задачи цлп
- •5.2. Алгоритм метода Гомори
- •Замечания.
- •5.3. Пример
- •6. Транспортная задача лп
- •6.1. Постановка задачи
- •6.2. Построение опорного плана транспортной задачи
- •6.3. Метод северо-западного угла
- •6.4. Пример
- •6.5. Метод минимальной стоимости
- •6.6. Пример
- •6.7. Метод потенциалов
- •6.8. Вычислительная схема метода потенциалов
- •6.9. Пример
- •7. Задания для самостоятельной работы
- •7.1. Построить математическую модель задачи
- •7.2. Привести задачу лп к канонической форме
- •Список литературы
3.7. Двойственный симплекс-метод
Метод работает с теми же симплексными таблицами, что и прямой симплекс - метод для задачи на минимум. Сначала определяется переменная, подлежащая выводу из базиса, а затем переменная, вводимая в базис [1,3].
Вычислительная схема двойственного симплекс – метода
Шаг 0. Начинаем с симплексной таблицы
|
B |
… | ||
L |
… | |||
… | ||||
… |
… |
………….. | ||
… |
где .
Шаг 1. Проверка на оптимальность. Если, то решение- оптимальное.
Шаг 2. Выбор ведущей строки. Выбираем среди номеровi, для которых, номерkс максимальным по модулю значением
Строка kобъявляетсяведущей.
Шаг 3.Проверка на неразрешимость. Если в строкенет отрицательных элементов, то двойственная целевая функция неограничена и, следовательно, прямая задача не имеет допустимых решений. Процесс решения завершается.
Шаг 4.Выбор ведущего столбцаs. Выбираем среди отрицательных элементов строкиэлемент с номеромs, для которого выполняется равенство
Столбец sобъявляетсяведущим, а элемент-ведущимэлементом.
Шаг 5.Проводим стандартное преобразование симплексной таблицы (Шаг 6 из прямого симплекс-метода).
3.8. Пример
Решить задачу ЛП двойственным симплекс-методом.
Приводим задачу к каноническому виду:
Знаки в ограничениях заменили на противоположные для того, чтобы переменные иможно было взять в качестве базисных. Симплексная таблица имеет вид
|
b | |||
L |
0 |
-1 |
-1 |
0 |
-2 |
-1 |
1 |
-1 | |
-1 |
-2 |
-1 |
1 |
Таблица двойственно-допустимая, но не оптимальная. Выбираем ведущую строку – это строка переменной , ведущий столбец – это столбец переменной. После преобразования таблица принимает вид
|
b | |||
L |
0 |
-1 |
-1 |
0 |
2 |
1 |
-1 |
-1 | |
-3 |
-3 |
0 |
1 |
Так как в столбце bесть отрицательная переменная, то эту строку выбираем ведущей, а столбец переменнойбудет ведущим столбцом. После преобразования получаем таблицу:
|
b | |||
L |
1 |
-1/3 |
-1 |
-1/3 |
1 |
1/3 |
-1 |
-2/3 | |
1 |
-1/3 |
0 |
-1/3 |
которая является оптимальной. Соответствующее оптимальное решение имеет вид .
4. Двойственность в лп
4.1. Постановка задачи
Рассмотрим пару задач ЛП вида:
(I) (II)
… …
… …
… …
… …
Задачу (I) называютпрямойзадачей ЛП, а (II) –двойственной. Неравенства задач (I) и (II), соответствующие друг другу (по стрелке), называются сопряженными. Заметим, что задача двойственная к (II), есть исходная прямая задача, т.е. соотношение двойственности взаимное. Поэтому можно любую из такой пары задач считать прямой, а другую двойственной.
4.2. Пример
Построить двойственную задачу к следующей задаче ЛП.
Прежде чем приступать с построению двойственной задачи, необходимо упорядочить запись исходной: согласовать знаки неравенств в ограничениях задачи с целевой функцией. Так как ЦФ минимизируется, то неравенства должны быть записаны с помощью знака . Для этого второе неравенство умножим на -1:
Теперь, вводя двойственные переменные , запишем в соответствии с указанным правилом пару двойственных задач:
| ||
| ||
| ||
| ||
| ||
| ||
| ||
|
Задача слева – исходная прямая задача, задача справа – двойственная к исходной задаче.