4.3. Геометрическая интерпретация симплекс-метода
Рассмотренная задача ЛП в стандартной модели была решена геометрически (рис.2.5.). Многоугольник решений имеет пять вершин с координатами О (0; 0), В3 (0; 21), Е (12; 18), С (22,5; 7,5), А1 (25; 0). Целевая функция достигает максимального значения в точке Е (12; 18). В модели участвовали только две переменные х1 и х2.
Теперь обратимся к симплекс-таблицам и запишем опорные решения, которые там получились:
Хопор1 = (0, 0, 300, 120, 252) (таблица 4.3.);
Хопор2 = (0, 21, 216, 36, 0) (таблица 4.4);
Хопор3 = Хmах = (12, 18, 84, 0, 0) (таблица 4.5.).
Вывод: переход от одной симплекс-таблицы к другой геометрически соответствует переходу от одной вершины многоугольника к другой:
;
;
.
Таким образом, переход осуществляется по вершинам многоугольника ОВ3ЕСА1, достигая своего максимального значения. На каждом шаге происходит переход к соседней вершине по ребру многоугольника. При этом целевая функция уменьшается.
5. Метод искусственного базиса
5.1. Постановка задачи
Для того чтобы привести задачу ЛП к канонической форме, необходимо предварительно найти некоторое начальное опорное решение этой задачи. Мы можем ввести в модель искусственные переменные, которые должны быть базисными и неотрицательными. Исключение искусственных переменных производится с помощью преобразования симплекс-таблиц. Процесс решения содержит два этапа: переход от основной модели к канонической решение задачи.
Пусть исходная система имеет следующий вид:
(5.1)
Без
ограничения общности можно считать,
что
.
Для отыскания опорного решения строим
вспомогательную задачу:
(5.2)
Свойства вспомогательной задачи:
1. Вспомогательная задача всегда имеет оптимальное решение.
2.
Вектор
является опорным решением задачи (5.2).
Таким образом, принимая этот вектор за начальное опорное решение, вспомогательную задачу можно решить симплекс-методом.
Пусть
оптимальное
опорное решение задачи (5.2). Тогда, если
,
то
опорное решение исходной задачи (5.1).
Если же среди чисел
есть положительные, то задача (5.1) не
имеет допустимых решений. Таким образом,
всегда можно либо найти опорное решение
исходной задачи (5.1), либо установить ее
неразрешимость.
5.2. Теоремы метода
Теорема
1.
Для того, чтобы исходная система имела
опорные решения, необходимо и достаточно,
чтобы
(минимальное значение функции во
вспомогательной задаче равно нулю).
Теорема 2. Если исходная система имеет опорные решения, то существует равносильная ей каноническая система, получаемая из завершающей таблицы вспомогательной задачи.
Замечания к теоремам
Замечание 1. Если φmin вспомогательной задачи не равна 0, то исходная задача не обладает опорным решением (несовместна).
Замечание 2. Если при решении вспомогательной задачи:
а) в завершающей симплекс-таблице все вспомогательные переменные вышли из базиса, тогда, полагая их равными 0, получаем каноническую задачу для исходной;
б) вспомогательная переменная в некотором уравнении осталась в базисе, тогда необходимо левую часть ограничения приравнять к 0 и путем преобразований выделить базисную переменную для данного уравнения.
Следовательно, из завершающей таблицы вспомогательной задачи получим каноническую форму задачи (5.1).