Каждое оптимальное решение задач линейного программирования находится в угловой точке области ограничений. При малом количестве переменных и ограничений таких точек немного, и вполне возможно вручную найти координаты всех этих точек и подсчитать в них значение целевой функции.
Однако если в задаче будет 50 переменных и 20 ограничений, то угловых точек, в которых можно считать значение целевой функции, будет порядка 1014. И если время подсчета значения угловой функции в одной угловой точке будет 0,000001 с, то эту задачу придется решать 2 тыс. лет. Поэтому простой перебор оказывается неэффективным и необходим метод, с помощью которого за конечное число шагов можно прийти к оптимальному решению.
Любое базисное решение, с помощью которого переходят к наиболее оптимальному его варианту, называется опорным решением.
Основные этапы реализации симплекс-метода:
1) указывается способ приведения неканонической задачи к канонической;
2) указывается способ выбора любого опорного решения;
|
|
3) устанавливаются критерии оптимальности опорного решения;
4) приводится способ перехода от одного опорного решения к другому, более близкому к оптимальному.
Рассмотрим каноническую задачу линейного программирования для случая, когда значение целевой функции максимизируется:
С помощью элементарных преобразований систему можно привести к виду
В качестве базисных переменных выберем
И тогда базисное решение системы имеет вид
Итак,
Представим все результаты в виде симплекс-таблицы:
Базис | Цена | План | ||||
F |
Последняя строка в таблице называется индексной строкой.
По индексной строке симплекс-таблицы можно определить, является ли данное решение оптимальным.
Теорема I. Критерий оптимальности плана.
Если в индексной строке симплекс-таблицы нет положительных элементов, то базисный план, соответствующий этой таблице, оптимален.
Доказательство. Действительно, при любых отрицательных и и положительных x значение функции F будет меньше .
Пусть теперь , и имеется какое-то другое допустимое решение, например:
Подставим его в целевую функцию:
Так как нашлось решение, дающее большее значение целевой функции, то при наших предположениях о знаке и решение не является оптимальным. Что и требовалось доказать
Теорема 2. Критерий улучшения опорного плана.
Если в индексной строке имеется хотя бы один положительный элемент и в столбце над ним также имеется хотя бы один положительный элемент, то базисный план может быть улучшен, т.е. можно найти такое базисное решение, при котором значение целевой функции будет больше.
|
|
Теорема 3. Критерий отсутствия оптимального плана.
Если в индексной строке симплекс-таблицы имеется положительное число, а в столбце над ним нет ни одного положительного элемента, то задача оптимального плана не имеет.
Аналогичные теоремы можно привести и для случая, когда целевая функция минимизируется.
Теорема 4. Если в индексной строке симплекс-таблицы нет отрицательных элементов, то базисный план оптимален.
Теорема 5. Если в индексной строке симплекс-таблицы имеется хотя бы одно отрицательное число, а в столбце над ним имеется хотя бы одно положительное, то базисный план может быть улучшен.
Теорема 6. Если в индексной строке симплекс-таблицы имеется отрицательное число, а в столбце над ним нет ни одного положительного элемента, то задача оптимального плана не имеет.
Замечание. Переход к новому базису осуществляется с помощью линейных операций над уравнениями системы.
Алгоритм симплекс-метода
1. Привести задачу линейного программирования к канонической, вводя балансовые переменные.
2. Занести данные математической модели в симплекс-таблицу.
2.1. Столбец коэффициентов для базисных переменных имеет вид базисных векторов пространства: одна координата равна 1, а остальные - нулевые.
2.2. Число базисных переменных должно совпадать с числом уравнений в системе ограничений.
2.3. Если в первоначальной таблице нет достаточного количества базисных переменных, над строками выполняются соответствующие элементарные преобразования.
3. Сделать анализ индексной строки:
3.1. Если в индексной строке имеются только отрицательные числа (только положительные) и нули, то данная таблица представляет собой оптимальный план решения задачи на максимум (на минимум): базисным переменным ставится в соответствие число из столбца «План», все остальные переменные обращаются в ноль.
3.2. Если в индексной строке имеется хотя бы одно положительное (отрицательное) число, а в столбце над ним найдется хотя бы один положительный элемент, то базисный план может быть улучшен. Улучшение производится путем перевода основных переменных в базисные с помощью элементарных преобразований над строками расширенной матрицы системы.
3.3. Если в индексной строке имеется хотя бы одно положительное (отрицательное) число, а в столбце над ним нет ни одного положительного элемента, то задача оптимального решения не имеет.
Пример. Для изготовления шкафов и буфетов деревообрабатывающий завод использует древесину четырех видов.
Вид древесины | Запас | Количество древесины на единицу продукции | |
Шкаф | Буфет | ||
Прибыль |
В таблице указаны запасы древесины, технологические коэффициенты и прибыль от продажи одного буфета и шкафа.
Составить такой план выпуска изделий, при котором прибыль предприятия будет максимальной.
Решение. Пусть х1 - планируемое к выпуску количество шкафов; х2 - планируемое к выпуску количество буфетов. Составим математическую модель задачи:
Приведем задачу к канонической, введя балансовые переменные:
Заполним первую симплекс-таблицу. В базис отправлены балансовые переменные, так как их столбцы представляют собой единичные базисные векторы. В индексной строке имеется два положительных числа и над ними также есть положительные элементы. То есть, данный план может быть улучшен. Выберем наибольшее из положительных чисел в индексной строке и отметим его (это число 3). А в столбце над ним найдем такое число, для которого отношение плановой цифры к нему будет наименьшим (это число 4).
Б | Ц | П | д | |||||||
30(min) | ||||||||||
+I*(-1/2) | ||||||||||
+I*(1/2) | ||||||||||
F | 3 |
С помощью элементарных преобразований над строками превратим это число в 1, а остальные числа столбца - в 0 (столбец д). Получим вторую симплекс-таблицу.
|
|
Чтобы получить элементы индексной строки, подставим в целевую функцию новый базисный вектор:
. Заполняем и анализируем индексную строку.
Б | Ц | П | д | |||||||
1/4 | ||||||||||
160:4=40 | ||||||||||
-1/2 | 60:2=30 | +IV*(-4) | ||||||||
-1/2 | 20:1=20 | +IV*(-4) | ||||||||
F | 2 | -3/4 |
Видим, что в индексной строке появилось отрицательное число (-3/4). Но еще остался положительный элемент (2). И в столбце над ним также имеются положительные числа. Следовательно, план может быть улучшен. Действуем по тому же алгоритму, что и в первый раз. Получим третью симплекс-таблицу:
Б | Ц | П | д | ||||||
1/4 | +III*(1/2) | ||||||||
+III*(-4) | |||||||||
1/2 | |||||||||
-1/2 | +III | ||||||||
F | 1/4 | -2 |
Отмечаем, что в индексной строке имеется положительное число, также и в столбце над ним есть положительные элементы. Преобразуем столбец по известному алгоритму.
Б | Ц | П | д | ||||||
-1/2 | +III*(1/2) | ||||||||
-4 | +III*(-4) | ||||||||
-4 | |||||||||
-1 | +III | ||||||||
F | -1/2 | -1 |
В индексной строке только отрицательные числа и нули. Следовательно, план в данной таблице оптимален. Целевая функция будет принимать значение 140 при значениях переменных базисного столбца, равных соответствующим значениям столбца «План».
Проведем экономический анализ задачи. Подставим полученные значения переменных в систему ограничений;
|
|
Видим, что при плане изготовления 40 шкафов и 20 буфетов древесина II, III, IV видов будет использована полностью, а 40 единиц древесины I вида останется. Этот остаток и соответствует балансовой переменной
Замечание. Так как в задаче всего две основных переменных, она могла быть решена и графически (см. пример 1 п. 3.1).
Задачи линейного программирования могут иметь не единственное решение.
Теорема (о бесконечном множестве оптимальных планов)
Если в индексной строке симплекс-таблицы, содержащей оптимальный план, имеется хотя бы одна нулевая оценка, соответствующая свободной переменной, то задача линейного программирования имеет бесконечное множество оптимальных планов.