- •Предмет курса. Основные понятия. Общая схема решения задач. Производственная задача.
- •Графический метод.
- •Каноническая задача. Базисный план. Формула приращений
- •Формула приращений целевой функции
- •Критерий оптимальности.
- •Достаточное условие неограниченности. Алгоритм обратной м-цы.
- •Итерация. Симплекс-метод (алгоритм).
- •Конечность. Геометрическая интерпретация.
- •Двухфазный симплекс-метод.
- •Выводы и следствия двухфазного симплекс-метода.
- •Приведение задач к канонической форме. Табличная реализация симплекс-метода.
- •Двойственная задача. Взаимодвойственность.
- •Соотношения двойственности 1,2.
- •Соотношения двойственности 3,4.
- •Соотношения двойственности 5,6. Следствия соотношения 6
- •Теоремы Фаркаша.
- •Двойственный симплекс-метод. Определения. Формула приращений.
- •Критерий оптимальности. Условие пустоты.
- •Итерация. Задача о диете.
- •Транспортная задача. Условие общего баланса. Условия дефицита и перепроизводства.
- •Особенности. Транспортная задача. Лемма 1. Следствия.
- •Лемма 2. Базисный план перевозок.
- •Базисный план. Метод минимального элемента.
- •Метод потенциалов транспортной задачи.
Двухфазный симплекс-метод.
(1)
Симплекс-метод предполагает наличие начального базисного плана у задачи (1). Значит, его нужно построить. Но существуют задачи, у которых ограничения противоречивы, то есть планов, вообще, нет. Как быть? Прежде всего, можно попытаться выделить в основных ограничениях базисные переменные (то есть входящие лишь в одно уравнение с коэффициентом +1; им будут соответствовать единичные столбцы в матрице ). При этом, однако, надо следить, чтобы вектор оставался неотрицательным. Если удаётся построить в каждом основном ограничении по базисной переменной, то очевиден и базисный план: . В общем случае рекомендуется применить следующий метод.
По параметрам задачи (1) построим вспомогательную задачу: (18-задача 1-й фазы)
– вектор искусственных переменных, – искусственные переменные, а вектор , то есть .
То есть, мы искусственно в каждое основное ограничение прибавили по искусственной неотрицательной переменной и тогда вектор неизвестных в задаче (18) имеет вид: . А основные ограничения можно записать в виде: . Лемма 1. У задачи (18) с помощью симплекс-метода можно всегда построить оптимальный базисный план: ..
Лемма 2. Для того чтобы множество планов задачи (1) было не пусто, необходимо и достаточно, чтобы искусственные компоненты оптимального плана задачи (18) были нулевыми ( ).
Задача (18) называется задачей первой фазы для задачи (1).
Пусть мы решили задачу первой фазы и построили для неё оптимальный базисный план: .
Возможны следующие случаи:
, тогда согласно лемме 2 – это и будет для неё ответ;
и , то есть искусственные переменные не входят в базис. Тогда очевидно, что вектор будет планом задачи, причём базисным.
Выбирая его в качестве начального базисного плана, приступаем к решению задачи (1). Этот этап называется второй фазой. А вместе первая и вторая фазы образуют двухфазный метод решения канонической задачи.
, но в базис входит некоторая искусственная переменная .
Тогда согласно лемме 2 является планом задачи (1), но ещё не базисным, поскольку в базис обязательно должно входить переменных задачи (1).
Возможны два подслучая:
3 а) . Это значит, что в результате симплекс итерации (а при симплекс преобразованиях, на самом деле, при переходе от одного базисного плана к другому, осуществляется преобразование Гаусса основных ограничений ) одно из основных ограничений задачи (1) приняло вид , то есть это ограничение, а точнее, которое является линейной комбинацией остальных. Исключаем его из задачи (вычёркиваем) и тогда размерность уменьшиться на единицу . Если других переменных в базисе нет, то приходим к случаю 2. То есть вектор во множестве будет начальным базисным планом задачи (1) и переходим ко второй фазе.
3 б) , но существует . Тогда совершаем ещё одну симплекс итерацию по элементу и в результате переменная выйдет из базиса, а вместо неё войдет переменная (вместо искусственной переменной в базис войдёт переменная задачи (1)). Сам план не изменится, поскольку Если других искусственных переменных в базисе нет, то снова вектор , будет начальным базисным планом задачи (1). И опять приступаем ко второй фазе.