Алгоритм двойственного симплексного метода

Для того чтобы решить задачу линейного программирования двойственным симплексным методом, необходимо выполнить следующее:

1. Привести задачу к каноническому виду.

2. Найти ПДОР с базисом из единичных векторов, вычислить оценки векторов-условий по базису этого решения и, если они согласуются с признаком оптимальности, то решать задачу двойственным симплексным методом.

3. Если ПДОР не имеет отрицательных координат, то оно является допустимым и оптимальным (по теореме 5.3). Решение задачи заканчивается.

4. Если ПДОР имеет отрицательную координату < 0, для которой соответствующие коэффициенты разложений всех векторов условий неотрицательные ( ), то задача не имеет решения ввиду несовместности системы ограничений. Решение задачи прекращается.

5. Если хотя бы одна координата ПДОР отрицательна, т. е.
< 0 и при этом найдется хотя бы один отрицательный коэффициент разложений векторов условий по базису решения, то переходят к новому решению, на котором значение целевой функции будет ближе к оптимальному. Номер вектора , вводимого в базис, находится с использованием параметра

.

Номер вектора , выводимого из базиса, находится из условия в задаче на максимум или в задаче на минимум.

Далее переходят к пункту 3 данного алгоритма.

Пример 5.7. Решить двойственным симплексным методом

Решение. Приводим задачу к каноническому виду, для чего вводим в левые части ограничений-неравенств неотрицательные дополнительные переменные :

Для нахождения ПДОР с единичным базисом умножим каждое из ограничений на -1

Находим начальное ПДОР с базисом .

Вычисляем оценки разложений векторов условий по базису ПДОР и заполняем первую симплексную таблицу (табл. 5.5).

Т а б л и ц а 5.5

Оценки для векторов условий, не входящих в базис, положительные. Следовательно, условия применимости двойственного симплексного метода к задаче на отыскание максимума выполнены. Начальное ПДОР не будет оптимальным, так как не удовлетворяет условиям неотрицательности переменных задачи. Переходим к новому ПДОР с неотрицательными оценками для векторов-условий. Для того чтобы оценки остались неотрицательными, необходимо номер k вектора , вводимого в базис, выбирать из условия

.

При этом номер l вектора , выводимого из базиса, должен соответствовать отрицательной координате ПДОР. В данном случае отрицательными являются три координаты х₄ = –3, х₅ = –4, х₆ = –4,. Для соответствующих строк (1-й, 2-й, 3-й) симплексной таблицы находим

при j = 1;

при j = 2;

при j = 1.

Отсюда следует, что оценки для, не входящих в базис векторов-условий, останутся положительными, если при выведении первого вектора базиса ввести в базис вектор или при выведении второго вектора базиса ввести вектор , или при выведении третьего вектора базиса ввести вектор . Для обеспечения наибольшего приближения к экстремуму целевой функции задачи на отыскание максимума номер l вектора, выводимого из базиса, определим из условия (5.29)

,

где - приращение целевой функции при введение в базис ПДОР вектора .

Вычисляем при l = 1, 2.

Номер вектора определяется неоднозначно. По своему усмотрению выбираем l = 1, так как с разрешающим элементом легче производить дальнейшие вычисления, чем с разрешающим элементом .

Приходим ко второму ПДОР (табл.5.6).

Т а б л и ц а 5.6

Второе ПДОР не будет оптимальным, так как не удовлетворяет условию неотрицательности. Для второй строки симплексной таблицы (табл. 5.6) , в которой расположена отрицательная координата решения , находим

при j = 2.

Таким образом, из базиса ПДОР выводим вектор , а вводим вектор , соответствующий минимуму отношения . Приходим к третьему ПДОР (табл. 5.7).

Т а б л и ц а 5.7

Полученное решение является оптимальным, так как удовлетворяет признаку оптимальности, т. е. не имеет отрицательных координат.

Ответ: max Z(X) = -7 при .

Пример 5.8. Решить двойственным симплексным методом

Решение. Приводим задачу к каноническому виду

Для нахождения ПДОР с единичным базисом умножим первое и третье ограничение на -1,

Задача имеет начальное ПДОР с базисом из единичных векторов. Оценки разложений векторов-условий , не входящих в базис , отрицательны (табл. 5.8). Следовательно, данную задачу на отыскание минимума можно решить двойственным симплексным методом. Решение задачи приведено в табл. 5.8.

Т а б л и ц а 5.8

Начальное ПДОР не является оптимальным, так как не удовлетворяет условиям неотрицательности. Переходим к следующему ПДОР. Необходимо один из векторов или , которые соответствуют отрицательным координатам , решения , заменить одним из векторов или . Номер k вектора , вводимого в базис, выбираем, используя условие (5.27). Находим

при j = 1.

при j = 2.

Номер k вектора , вводимого в базис, выбираем, используя условие (5.27). Находим

при j = 1.

при j = 2.

Отсюда следует, что для того, чтобы оценки при переходе к новому решению оставались неположительными, необходимо либо вектор заменить на , либо вектор на . Для обеспечения наибольшего приближения к оптимальному решению в задаче на минимум номер l, выводимого из базиса вектора , определяется из условия (5.30)

.

Вычисляем

при l = 3.

Третий (l = 3) вектор базиса заменяем вектором
( при j = 2). Выполняем преобразование Жордана с разрешающим элементом , получаем ПДОР , которое не является оптимальным. Для второй строки второй симплексной таблицы, содержащей отрицательную координату решения , находим

при j = 3.

Выводим из базиса решения вектор , вводим вектор , переходим к ПДОР , которое является оптимальным, так как удовлетворяет условиям неотрицательности.

Ответ: min Z(X) = 26 при .

Лекция №10