Табличный симплекс-метод
Один из методов решения оптимизационных задач (как правило связанных с нахождением минимума или максимума ) линейного программирования называется . Симплекс-метод включает в себя целую группу алгоритмов и способов решения задач линейного программирования. Один из таких способов, предусматривающий запись исходных данных и их пересчет в специальной таблице, носит наименование табличного симплекс-метода .
Рассмотрим алгоритм табличного симплекс-метода на примере решения производственной задачи , которая сводится к нахождению производственного плана обеспечивающего максимальную прибыль.
Исходные данные задачи на симплекс-метод
Предприятие выпускает 4 вида изделий, обрабатывая их на 3-х станках.
Нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:
Фонд времени работы станков (мин.) задан в матрице B:
Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:
Цель производственной задачи
Составить такой план производства, при котором прибыль предприятия будет максимальной.
Решение задачи табличным симплекс-методом
(1) Обозначим X1, X2, X3, X4 планируемое количество изделий каждого вида. Тогда искомый план: (X1, X2, X3, X4 )
(2) Запишем ограничения плана в виде системы уравнений:
(3) Тогда целевая прибыль:
То есть прибыль от выполнения производственного плана должна быть максимальной.
(4) Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X5, X6, X7 ).
(5) Примем следующий опорный план :
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Занесем данные в симплекс-таблицу :
В последнюю строку заносим коэффициенты при целевой функции и само ее значение с обратным знаком;
(7) Выбираем в последней строке наибольшее (по модулю ) отрицательное число.
Вычислим b = Н / Элементы_выбранного_столбца
Среди вычисленных значений b выбираем наименьшее .
Пересечение выбранных столбца и строки даст нам разрешающий элемент. Меняем базис на переменную соответствующую разрешающему элементу (X5 на X1 ).
- Сам разрешающий элемент обращается в 1.
- Для элементов разрешающей строки – a ij (*) = a ij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные ).
- Для элементов разрешающего столбца – они просто обнуляются.
- Остальные элементы таблицы пересчитываем по правилу прямоугольника.
a ij (*) = a ij – (A * B / РЭ)
Как видите, мы берем текущую пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A * B ) делим на разрешающий элемент (РЭ ). И вычитаем из текущей пересчитываемой ячейки (a ij ) то, что получилось. Получаем новое значение - a ij (*) .
(9) Вновь проверяем последнюю строку (c ) на наличие отрицательных чисел . Если их нет – оптимальный план найден, переходим к последнему этапу решения задачи. Если есть – план еще не оптимален, и симплекс-таблицу вновь нужно пересчитать.
Так как у нас в последней строке снова имеются отрицательные числа, начинаем новую итерацию вычислений.
(10) Так как в последней строке нет отрицательных элементов, это означает, что нами найден оптимальный план производства! А именно: выпускать мы будем те изделия, которые перешли в колонку «Базис» - X1 и X2. Прибыль от производства каждой единицы продукции нам известна (матрица C ). Осталось перемножить найденные объемы выпуска изделий 1 и 2 с прибылью на 1 шт., получим итоговую (максимальную! ) прибыль при данном плане производства.
ОТВЕТ:
X1 = 32 шт., X2 = 20 шт., X3 = 0 шт., X4 = 0 шт.
P = 48 * 32 + 33 * 20 = 2 196 руб.
Галяутдинов Р.Р.
© Копирование материала допустимо только при указании прямой гиперссылки на
Для упрощения процесса решения исходные данные задачи линейного программирования при решении ее симплекс методом записываются в специальные симплекс-таблицы. Поэтому одна из модификаций симплекс метода получила название табличный симплекс метод. Задача линейного программирования в каноническом виде:
a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n + x n+1 =b 1
Исходная таблица для задачи имеет следующий вид:
| x 1 | x 2 | ... | x n-1 | x n | b | |
| F | -a 0,1 | -a 0,2 | ... | -a 0,n-1 | -a 0,n | -b 0 |
| x n+1 | a 1,1 | a 1,2 | ... | a 1,n-1 | a 1,n | b 1 |
| x n+2 | a 2,1 | a 2,2 | ... | a 2,n-1 | a 2,n | b 2 |
| ... | ... | ... | ... | ... | ... | ... |
| x n+m | a m,1 | a m,2 | ... | a m,n-1 | a m,n | b m |
x 1 , x 2 , x n - исходные переменные, x n+1 , x n+2 , x n+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные , а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным .
Алгоритм симплекс-метода.
Приводим задачу ЛП к каноническому виду
F=a 0,1 x 1 +a 0,2 x 2 +...a 0,n x n +b 0 → max
a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n +x n+1 =b 1
a 2,1 x 1 +a 2,2 x 2 +...a 2,n x n +x n+2 =b 2
.......................................
a m,1 x 1 +a m,2 x 2 +...a m,n x n +x n+m =b m
В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a 0,n =-a 0,n . Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений.
Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче
| x 1 | x 2 | ... | x n-1 | x n | b | |
| F | -a 0,1 | -a 0,2 | ... | -a 0,n-1 | -a 0,n | -b 0 |
| x n+1 | a 1,1 | a 1,2 | ... | a 1,n-1 | a 1,n | b 1 |
| x n+2 | a 2,1 | a 2,2 | ... | a 2,n-1 | a 2,n | b 2 |
| ... | ... | ... | ... | ... | ... | ... |
| x n+m | a m,1 | a m,2 | ... | a m,n-1 | a m,n | b m |
Шаг 1. Проверка на допустимость.
Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a k,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно .
Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.
Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.
Шаг 2. Проверка на оптимальность.
На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строке F (не беря в расчет элемент b 0 - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.
Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b 0)
a 0,l =min{a 0,i }
l - столбец в котором он находится будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответсвующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.
b k /a k,l =min {b i /a i,l } при a i,l >0, b i >0
k - cтрока, для которой это отношение минимально - ведущая. Элемент a k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x k) исключается из базиса, переменная соответствующая ведущему столбцу (x l) включается в базис.
Пересчитываем симплекс-таблицу по . Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2
Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу.
Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.
Правила преобразований симплексной таблицы.
При составлении новой симплекс-таблицы в ней происходят следующие изменения:
- Вместо базисной переменной x k записываем x l ; вместо небазисной переменной x l записываем x k .
- ведущий элемент заменяется на обратную величину a k,l "= 1/a k,l
- все элементы ведущего столбца (кроме a k,l) умножаются на -1/a k,l
- все элементы ведущей строки (кроме a k,l) умножаются на 1/a k,l
- оставшиеся элементы симплекс-таблицы преобразуются по формуле a i,j "= a i,j - a i,l x a k,j / a k,l
Схему преобразования элементов симплекс-таблицы (кроме ведущей строки и ведущего столбца) называют схемой ”прямоугольника”.
Преобразуемый элемент a i,j и соответствующие ему три сомножителя как раз и являются вершинами ”прямоугольника”.
. Алгоритм симплекс-метода
Пример 5.1. Решить следующую задачу линейного программирования симплекс-методом:
Решение:
I итерация:
х3 , х4 , х5 , х6 х1 ,х2 . Выразим базисные переменные через свободные:
Приведем целевую функциюк следующему виду:
На основе полученной задачи сформируем исходную симплекс-таблицу:
Таблица 5.3
Исходная симплекс-таблица
Оценочные отношения |
||||
Согласно определению базисного решения свободные переменные равны нулю, а значения базисных переменных – соответствующим значениям свободных чисел, т.е.:
3 этап: проверка совместности системы ограничений ЗЛП.
На данной итерации (в таблице 5.3) признак несовместности системы ограничений (признак 1) не выявлен (т.е. нет строки с отрицательным свободным числом (кроме строки целевой функции), в которой не было бы хотя бы одного отрицательного элемента (т.е. отрицательного коэффициента при свободной переменной)).
На данной итерации (в таблице 5.3) признак неограниченности целевой функции (признак 2) не выявлен (т.е. нет колонки с отрицательным элементом в строке целевой функции (кроме колонки свободных чисел), в которой не было бы хотя бы одного положительного элемента).
Так как найденное базисное решение не содержит отрицательных компонент, то оно является допустимым.
6 этап: проверка оптимальности.
Найденное базисное решение не является оптимальным, так как согласно признаку оптимальности (признак 4) в строке целевой функции не должно быть отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, согласно алгоритму симплекс-метода переходим к 8 этапу.
Так как найденное базисное решение допустимое, то поиск разрешающей колонки будем производить по следующей схеме: определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.3, таких колонок две: колонка «х1 » и колонка «х2 ». Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х2 » содержит наименьший элемент (–3) в сравнении с колонкой «х1
Для определения разрешающей строки находим положительные оценочные отношения свободных чисел к элементам разрешающей колонки, строка, которой соответствует наименьшее положительное оценочное отношение, принимается в качестве разрешенной.
Таблица 5.4
Исходная симплекс-таблица
В таблице 5.4 наименьшее положительное оценочное отношение соответствует строке «х5 », следовательно, она будет разрешающей.
Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент , который расположен на пересечении строки «х5 » и колонки «х2 ».
Разрешающий элемент показывает одну базисную и одну свободную переменные, которые необходимо поменять местами в симплекс-таблице, для перехода к новому «улучшенному» базисному решению. В данном случае это переменные х5 и х2 , в новой симплекс-таблице (таблице 5.5) их меняем местами.
9.1. Преобразование разрешающего элемента.
Разрешающий элемент таблицы 5.4 преобразовывается следующим образом:
Полученный результат вписываем в аналогичную клетку таблицы 5.5.
9.2. Преобразование разрешающей строки.
Элементы разрешающей строки таблицы 5.4 делим на разрешающий элемент данной симплекс-таблицы, результаты вписываются в аналогичные ячейки новой симплекс-таблицы (таблицы 5.5). Преобразования элементов разрешающей строки приведены в таблице 5.5.
9.3. Преобразование разрешающей колонки.
Элементы разрешающей колонки таблицы 5.4 делим на разрешающий элемент данной симплекс-таблицы, а результат берется с обратным знаком. Полученные результаты вписываются в аналогичные ячейки новой симплекс-таблицы (таблицы 5.5). Преобразования элементов разрешающей колонки приведены в таблице 5.5.
9.4. Преобразование остальных элементов симплекс-таблицы.
Преобразование остальных элементов симплекс-таблицы (т.е. элементов не расположенных в разрешающей строке и разрешающей колонке) осуществляется по правилу «прямоугольника».
К примеру, рассмотрим преобразование элемента, расположенного на пересечении строки «х3 » и колонки «», условно обозначим его «х3 ». В таблице 5.4 мысленно вычерчиваем прямоугольник, одна вершина которого располагается в клетке, значение которой преобразуем (т.е. в клетке «х3 »), а другая (диагональная вершина) – в клетке с разрешающим элементом. Две другие вершины (второй диагонали) определяются однозначно. Тогда преобразованное значение клетки «х3 » будет равно прежнему значению данной клетки минус дробь, в знаменателе которой разрешающий элемент (из таблицы 5.4), а в числителе произведение двух других неиспользованных вершин, т.е.:
«х3 »: .
Аналогично преобразуются значения других клеток:
«х3 х1 »: ;
«х4
»: 
;
«х4 х1 »: ;
«х6
»: 
;
«х6 х1 »: ;
«»: 
;
«х1
»: 
.
В результате данных преобразований получили новую симплекс- таблицу (таблица 5.5).
II итерация:
1 этап: составление симплекс-таблицы.
Таблица 5.5
Симплекс-таблица II итерации
Оценочные отношения |
||||
| ||||
|
|
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.5):
Как видно, при данном базисном решении значение целевой функции =15, что больше чем при предыдущем базисном решении.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.5 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.5 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.5) содержится отрицательный элемент: –2 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.
8 этап: определение разрешающего элемента.
8.1. Определение разрешающей колонки.
Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.5, такой колонкой является только одна колонка: «х1 ». Следовательно, ее принимаем в качестве разрешенной.
8.2. Определение разрешающей строки.
Согласно полученным значениям положительных оценочных отношений в таблице 5.6, минимальным является отношение, соответствующее строке «х3 ». Следовательно, ее принимаем в качестве разрешенной.
Таблица 5.6
Симплекс-таблица II итерации
Оценочные отношения |
||||
3/1=3 – min |
||||
9 этап: преобразование симплекс-таблицы.
Преобразования симплекс-таблицы (таблицы 5.6) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.7.
III итерация
По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:
Таблица 5.7
Симплекс-таблица III итерации
Оценочные отношения |
||||
| ||||
|
|
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.7):
3 этап: проверка совместности системы ограничений.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.7 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.7 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.
6 этап: проверка оптимальности найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.7) содержится отрицательный элемент: –3 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.
8 этап: определение разрешающего элемента.
8.1. Определение разрешающей колонки.
Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.7, такой колонкой является только одна колонка: «х5 ». Следовательно, ее принимаем в качестве разрешенной.
8.2. Определение разрешающей строки.
Согласно полученным значениям положительных оценочных отношений в таблице 5.8, минимальным является отношение, соответствующее строке «х4 ». Следовательно, ее принимаем в качестве разрешенной.
Таблица 5.8
Симплекс-таблица III итерации
Оценочные отношения |
||||
5/5=1 – min |
||||
9 этап: преобразование симплекс-таблицы.
Преобразования симплекс-таблицы (таблицы 5.8) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.9.
IV итерация
1 этап: построение новой симплекс-таблицы.
По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:
Таблица 5.9
Симплекс-таблица IV итерации
Оценочные отношения |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение, согласно таблице 5.9 решение следующее:
3 этап: проверка совместности системы ограничений.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.9 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.9 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.
6 этап: проверка оптимальности найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.9) нет отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается).
7 этап: проверка альтернативности решения.
Найденное решение является единственным, так как в строке целевой функции (таблица 5.9) нет нулевых элементов (свободное число данной строки при рассмотрении данного признака не учитывается).
Ответ: оптимальное значение целевой функции рассматриваемой задачи =24, которое достигается при.
Пример 5.2. Решить вышеприведенную задачу линейного программирования при условии, что целевая функция минимизируется:
Решение:
I итерация:
1 этап: формирование исходной симплекс-таблицы.
Исходная задача линейного программирования задана в стандартной форме. Приведем ее к каноническому виду путем введения в каждое из ограничений-неравенств дополнительной неотрицательной переменной, т.е.
В полученной системе уравнений примем в качестве разрешенных (базисных) переменные х3 , х4 , х5 , х6 , тогда свободными переменными будут х1 ,х2 . Выразим базисные переменные через свободные.
Если в условии задачи есть ограничения со знаком ≥, то их можно привести к виду ∑a ji b j , умножив обе части неравенства на -1. Введем m дополнительных переменных x n+j ≥0(j =1,m ) и преобразуем ограничения к виду равенств
(2)
Предположим, что все исходные переменные задачи x 1 , x 2 ,..., x n – небазисные. Тогда дополнительные переменные будут базисными, и частное решение системы ограничений имеет вид
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)
Так как при этом значение функции цели F 0 = 0 , можно представить F(x) следующим образом:
F(x)=∑c i x i +F 0 =0 (4)
Начальная симплекс-таблица (симплекс-табл. 1) составляется на основании уравнений (2) и (4). Если перед дополнительными переменными x n+j стоит знак «+», как в (2), то все коэффициенты перед переменными x i и свободный член b j заносятся в симплекс-таблицу без изменения. Коэффициенты функции цели при ее максимизации заносятся в нижнюю строку симплекс-таблицы с противоположными знаками. Свободные члены в симплекс-таблице определяют решение задачи.
Алгоритм решения задачи следующий:
1-й шаг. Просматриваются элементы столбца свободных членов. Если все они положительные, то допустимое базисное решение найдено и следует перейти к шагу 5 алгоритма, соответствующему нахождению оптимального решения. Если в начальной симплекс-таблице есть отрицательные свободные члены, то решение не является допустимым и следует перейти к шагу 2.
2-й шаг. Для нахождения допустимого решения осуществляется , при этом нужно решать, какую из небазисных переменных включить в базис и какую переменную вывести из базиса.
Таблица 1.
| базисные переменные | Свободные члены в ограничениях | Небазисные переменные | |||||
| x 1 | x 2 | ... | x l | ... | x n|||
| x n+1 | b 1 | a 11 | a 12 | ... | a 1l | ... | a 1n |
| x n+2 | b 2 | a 21 | a 22 | ... | a 2l | ... | a 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+r | b2 | a r1 | a r2 | ... | a rl | ... | a rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+m | b m | a m1 | a m2 | ... | a ml | ... | a mn |
| F(x) max | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Для этого выбирают любой из отрицательных элементов столбца свободных членов (пусть это будет b 2 ведущим, или разрешающим. Если в строке с отрицательным свободным членом нет отрицательных элементов, то система ограничений несовместна и задача не имеет решения.
Одновременно из БП исключается та переменная, которая первой изменит знак при увеличении выбранной НП x l . Это будет x n+r , индекс r которой определяется из условия
т.е. та переменная, которой соответствует наименьшее отношение свободного члена к элементу выбранного ведущего столбца. Это отношение называется симплексным отношением. Следует рассматривать только положительные симплексные отношения.
Строка, соответствующая переменной x n+r , называется ведущей, или разрешающей. Элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим, или разрешающим элементом. Нахождением ведущего элемента заканчивается работа с каждой очередной симплекс-таблицей.
3-й шаг. Рассчитывается новая симплекс-таблица, элементы которой пересчитываются из элементов симплекс-таблицы предыдущего шага и помечаются штрихом, т.е. b" j , a" ji , c" i , F" 0 . Пересчет элементов производится по следующим формулам:
Сначала в новой симплекс-таблице заполнятся строка и столбец, которые в предыдущей симплекс-таблице были ведущими. Выражение (5) означает, что элемент a" rl на месте ведущего равен обратной величине элемента предыдущей симплекс-таблицы. Элементы строки a ri делятся на ведущий элемент, а элементы столбца a jl также делятся на ведущий элемент, но берутся с противоположным знаком. Элементы b" r и c" l рассчитываются по тому же принципу.
Остальные формулы легко записать с помощью .
Прямоугольник строится по старой симплекс-таблице таким образом, что одну из его диагоналей образует пересчитываемый (a ji) и ведущий (a rl) элементы (рис. 1). Вторая диагональ определяется однозначно. Для нахождения нового элемента a" ji из элемента a ji вычитается (на это указывает знак « – » у клетки) произведение элементов противоположной диагонали, деленное на ведущий элемент. Аналогично пересчитываются элементы b" j , (j≠r) и c" i , (i≠l).
4-й шаг. Анализ новой симплекс-таблицы начинается с 1-го шага алгоритма. Действие продолжается, пока не будет найдено допустимое базисное решение, т.е. все элементы столбца свободных членов должны быть положительными.
5-й шаг. Считаем, что допустимое базисное решение найдено. Просматриваем коэффициенты строки функции цели F(x) . Признаком оптимальности симплекс-таблицы является неотрицательность коэффициентов при небазисных переменных в F-строке.
Рис. 1. Правило прямоугольника
Если среди коэффициентов F-строки имеются отрицательные (за исключением свободного члена), то нужно переходить к другому базисному решению. При максимизации функции цели в базис включается та из небазисных переменных (например x l), столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента c l в нижней строке симплекс-таблицы. Это позволяет выбрать ту переменную, увеличение которой приводит к улучшению функции цели. Столбец, соответствующий переменной x l , называется ведущим. Одновременно из базиса исключается та переменная x n+r , индекс r которой определяется минимальным симплексным отношением:
Строка, соответствующая x n+r , называется ведущей , а элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим элементом.
6-й шаг. по правилам, изложенным на 3-м шаге. Процедура продолжается до тех пор, пока не будет найдено оптимальное решение или сделан вывод, что оно не существует.
Если в процессе оптимизации решения в ведущем столбце все элементы неположительные, то ведущую строку выбрать невозможно. В этом случае функция в области допустимых решений задачи не ограничена сверху и F max ->&∞.
Если же на очередном шаге поиска экстремума одна из базисных переменных становится равной нулю, то соответствующее базисное решение называется вырожденным. При этом возникает так называемое зацикливание, характеризующееся тем, что с определенной частотой начинает повторяться одинаковая комбинация БП (значение функции F при этом сохраняется) и невозможно перейти к новому допустимому базисному решению. Зацикливание является одним из основных недостатков симплекс-метода, но встречается сравнительно редко. На практике в таких случаях обычно отказываются от ввода в базис той переменной, столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента в функции цели, и производят случайный выбор нового базисного решения.
Пример 1. Решить задачу
max{F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0}
Симплексным методом и дать геометрическую интерпретацию процесса решения.
Графическая интерпретация решения задачи представлена на рис. 2. Максимальное значение функции цели достигается в вершине ОДЗП с координатами . Решим задачу с помощью симплекс-таблиц. Умножим второе ограничение на (-1) и введём дополнительные переменные, чтобы неравенства привести к виду равенств, тогда
Исходные переменные x 1 и x 2 принимаем в качестве небазисных, а дополнительные x 3 , x 4 и x 5 считаем базисными и составляем симплекс-таблицу(симплекс-табл. 2). Решение, соответствующее симплекс-табл. 2, не является допустимым; ведущий элемент обведен контуром и выбран в соответствии с шагом 2 приведенного ранее алгоритма. Следующая симплекс-табл. 3 определяет допустимое базисное решение, ему соответствует вершина ОДЗП на рис. 2 Ведущий элемент обведен контуром и выбран в соответствии с 5-м шагом алгоритма решения задачи. Табл. 4 соответствует оптимальному решению задачи, следовательно: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.
Рис. 2. Графическое решение задачи
