Симплекс-таблицы.
Процесс нахождения экстремума с помощью симплекс-метода оформляется в виде специальных симплекс-таблиц. Симплекс-таблица составляется для каждой итерации по определенным правилам, что облегчает перебор базисных решений и позволяет избежать случайных ошибок.
Рассмотрим следующую задачу линейного программирования:
(1)
Если в условии задачи есть ограничения со знаком ≥, то их можно привести к виду ∑ajibj, умножив обе части неравенства на -1. Введем m дополнительных переменных xn+j≥0(j =1,m) и преобразуем ограничения к виду равенств
(2)
Предположим, что все исходные переменные задачи x1, x2,..., xn – небазисные. Тогда дополнительные переменные будут базисными, и частное решение системы ограничений имеет вид
x1 = x2 = ... = xn = 0, xn+ j = bj , j =1,m. (3)
Так как при этом значение функции цели F0 = 0 , можно представить F(x) следующим образом:
F(x)=∑cixi+F0=0 (4)
Начальная симплекс-таблица (симплекс-табл. 1) составляется на основании уравнений (2) и (4). Если перед дополнительными переменными xn+j стоит знак «+», как в (2), то все коэффициенты перед переменными xi и свободный член bj заносятся в симплекс-таблицу без изменения. Коэффициенты функции цели при ее максимизации заносятся в нижнюю строку симплекс-таблицы с противоположными знаками. Свободные члены в симплекс-таблице определяют решение задачи.
Алгоритм решения задачи следующий:
1-й шаг. Просматриваются элементы столбца свободных членов. Если все они положительные, то допустимое базисное решение найдено и следует перейти к шагу 5 алгоритма, соответствующему нахождению оптимального решения. Если в начальной симплекс-таблице есть отрицательные свободные члены, то решение не является допустимым и следует перейти к шагу 2.
2-й шаг. Для нахождения допустимого решения осуществляется пересчет симплекс-таблицы, при этом нужно решать, какую из небазисных переменных включить в базис и какую переменную вывести из базиса.
Таблица 1.
базисные переменные | Свободные члены в ограничениях | Небазисные переменные | |||||
x1 | x2 | ... | xl | ... | xn | ||
xn+1 | b1 | a11 | a12 | ... | a1l | ... | a1n |
xn+2 | b2 | a21 | a22 | ... | a2l | ... | a2n |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
xn+r | b2 | ar1 | ar2 | ... | arl | ... | arn |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
xn+m | bm | am1 | am2 | ... | aml | ... | amn |
F(x)max | F0 | -c1 | -c2 | ... | -c1 | ... | -cn |
Для этого выбирают любой из отрицательных элементов столбца свободных членов (пусть это будет b2 < 0 ) и просматривают элементы строки, в которой он находится. В этой строке выбирают любой отрицательный элемент и соответствующий ему столбец определит переменную (например xl ), которую следует исключить из небазисных и ввести в базис на следующем шаге. Столбец, соответствующий переменной xl , называется ведущим, или разрешающим. Если в строке с отрицательным свободным членом нет отрицательных элементов, то система ограничений несовместна и задача не имеет решения.
Одновременно из БП исключается та переменная, которая первой изменит знак при увеличении выбранной НП xl . Это будет xn+r , индекс r которой определяется из условия
Строка, соответствующая переменной xn+r , называется ведущей, или разрешающей. Элемент симплекс-таблицы arl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим, или разрешающим элементом. Нахождением ведущего элемента заканчивается работа с каждой очередной симплекс-таблицей.
3-й шаг. Рассчитывается новая симплекс-таблица, элементы которой пересчитываются из элементов симплекс-таблицы предыдущего шага и помечаются штрихом, т.е. b'j , a'ji , c'i , F'0. Пересчет элементов производится по следующим формулам:
Сначала в новой симплекс-таблице заполнятся строка и столбец, которые в предыдущей симплекс-таблице были ведущими. Выражение (5) означает, что элемент a'rl на месте ведущего равен обратной величине элемента предыдущей симплекс-таблицы. Элементы строки ari делятся на ведущий элемент, а элементы столбца ajl также делятся на ведущий элемент, но берутся с противоположным знаком. Элементы b'r и c'l рассчитываются по тому же принципу.
Остальные формулы легко записать с помощью правила прямоугольника.
Прямоугольник строится по старой симплекс-таблице таким образом, что одну из его диагоналей образует пересчитываемый (aji ) и ведущий (arl ) элементы (рис. 1). Вторая диагональ определяется однозначно. Для нахождения нового элемента a'ji из элемента aji вычитается (на это указывает знак « – » у клетки) произведение элементов противоположной диагонали, деленное на ведущий элемент. Аналогично пересчитываются элементы b'j , ( j≠r) и c'i, (i≠l).
4-й шаг. Анализ новой симплекс-таблицы начинается с 1-го шага алгоритма. Действие продолжается, пока не будет найдено допустимое базисное решение, т.е. все элементы столбца свободных членов должны быть положительными.
5-й шаг. Считаем, что допустимое базисное решение найдено. Просматриваем коэффициенты строки функции цели F(x) . Признаком оптимальности симплекс-таблицы является неотрицательность коэффициентов при небазисных переменных в F-строке.
Рис. 1. Правило прямоугольника
Если среди коэффициентов F-строки имеются отрицательные (за исключением свободного члена), то нужно переходить к другому базисному решению. При максимизации функции цели в базис включается та из небазисных переменных (например xl ), столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента cl в нижней строке симплекс-таблицы. Это позволяет выбрать ту переменную, увеличение которой приводит к улучшению функции цели. Столбец, соответствующий переменной xl , называется ведущим. Одновременно из базиса исключается та переменная xn+r , индекс r которой определяется минимальным симплексным отношением:
Строка, соответствующая xn+r , называется ведущей, а элемент симплекс-таблицы arl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим элементом.
6-й шаг. Рассчитываем новую симплекс-таблицу по правилам, изложенным на 3-м шаге. Процедура продолжается до тех пор, пока не будет найдено оптимальное решение или сделан вывод, что оно не существует.
Если в процессе оптимизации решения в ведущем столбце все элементы неположительные, то ведущую строку выбрать невозможно. В этом случае функция в области допустимых решений задачи не ограничена сверху и Fmax->&∞.
Если же на очередном шаге поиска экстремума одна из базисных переменных становится равной нулю, то соответствующее базисное решение называется вырожденным. При этом возникает так называемое зацикливание, характеризующееся тем, что с определенной частотой начинает повторяться одинаковая комбинация БП (значение функции F при этом сохраняется) и невозможно перейти к новому допустимому базисному решению. Зацикливание является одним из основных недостатков симплекс-метода, но встречается сравнительно редко. На практике в таких случаях обычно отказываются от ввода в базис той переменной, столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента в функции цели, и производят случайный выбор нового базисного решения.
Пример 1. Решить задачу
max{F(x) = -2x1 + 5x2 | 2x1 + x2≤7; x1 + 4x2≥8; x2≤4; x1,2≥0}
симплексным методом и дать геометрическую интерпретацию процесса решения.Графическая интерпретация решения задачи представлена на рис. 2. Максимальное значение функции цели достигается в вершине ОДЗП с координатами [0,4]. Решим задачу с помощью симплекс-таблиц. Умножим второе ограничение на (-1) и введём дополнительные переменные, чтобы неравенства привести к виду равенств, тогда
Рис. 2. Графическое решение задачи
ДОБАВИТЬ КОММЕНТАРИЙ