1.9.3 Способы решения транспортных задач

Решение задач симплекс-методом

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

Cимплекс-метод имеет следующий вид:

F=c1·x1+c2·x2+c3·x3>max a11·x1+a12·x2+a13·x3?b1 a21·x1+a22·x2+a23·x3?b2 a31·x1+a32·x2+a33·x3?b3 x1? 0; x2? 0; x3? 0;

Чтобы преобразовать неравенства в равенства, вводят неотрицательные переменные x4?0; x5?0; x6?0. Тогда получаем систему уравнений:

a11·x1+a12·x2+a13·x3+x4=b1 a21·x1+a22·x2+a23·x3+x5=b2 a31·x1+a32·x2+a33·x3+x6=b3 x1?0;x2?0;x3? 0;x4?0;x5?0; x6?0

Они определяют пересечение трех плоскостей в 6-ти мерном пространстве. Поскольку линейные функции не имеют локальных экстремумов, то экстремум целевой функции может быть только на границе, определяемой неравенствами x1?0;x2?0;x3?0;x4?0;x5?0;x6?0. На этой границе три из шести переменных равны нулю. Значения остальных, которые называются базисом, получаются из решения системы уравнений. Решение симплекс методом выполняется в два этапа:

* Выбирается начальный базис. В данном случае это x4=b1,x5=b2,x6=b3 (при этом x1=0;x2=0;x3=0).

* Выполняется поиск решения в симплекс таблице. Если базис не дает оптимального решения, выбирается новый базис, составляется новая симплекс таблица до получения оптимального решения.

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

Поэтому одна из модификаций симплекс-метода получила название табличный симплекс-метод.

Задача линейного программирования в каноническом виде:

F=a0,1x1+a0,2x2+...a0,nxn+b0> max

a1,1x1+a1,2x2+...a1,nxn+ xn+1=b1

a2,1x1+a2,2x2+...a2,nxn+xn+2=b2

.................................................

am,1x1+am,2x2+...am,nxn+xn+m=bm

Исходная таблица для задачи имеет следующий вид:

x1,x2,xn - исходные переменные, xn+1,xn+2,xn+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы, а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам.

Алгоритм симплекс-метода.

Приводим задачу ЛП к каноническому виду

F=a0,1x1+a0,2x2+...a0,nxn+b0> max

a1,1x1+a1,2x2+...a1,nxn+xn+1=b1

a2,1x1+a2,2x2+...a2,nxn+xn+2=b2

.......................................

am,1x1+am,2x2+...am,nxn+xn+m=bm

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов ограничивающих условий со знаком "?" так же меняются на противоположные. В случае если условие содержит знак "?" - коэффициенты запишутся без изменений.

Шаг 1. Составляем симплексную таблицу, соответствующую исходной задаче

Шаг 2. Проверка на допустимость.

Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных, то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент ak,l- он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно правилам.

Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.

Если после перерасчета в столбце свободных членов остались отрицательные элементы, то переходим к первому шагу, если таких нет, то ко второму.

Шаг 3. Проверка на оптимальность.

На предыдущем этапе найдено допустимое решение.

Проверим его на оптимальность. Если среди элементов симплексной таблицы, находящихся в строке F (не беря в расчет элемент b0- текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.

Если в строке F есть отрицательные элементы то решение требует улучшения.

Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b0)

a0,l=min{a0,i}

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

bk/ak,l=min {bi/ai,l}при ai,l>0, bi>0

k - cтрока, для которой это отношение минимально - ведущая. Элемент ak,l- ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис.

Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 3.

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

Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

Правила преобразований симплексной таблицы.

При составлении новой симплекс-таблицы в ней происходят следующие изменения:

* Вместо базисной переменной xkзаписываем xl; вместо небазисной переменной xl записываем xk.

ведущий элемент заменяется на обратную величину ak,l= 1/ak,l

все элементы ведущего столбца (кроме ak,l) умножаются на -1/ak,l

все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l

оставшиеся элементы симплекс-таблицы преобразуются по формуле

ai,j= ai,j- ai,l xak,j/ ak,l.

Таким образом, транспортные задачи позволяют производителям эффективно использовать все ресурсы при минимальных затратах на транспортировку товаров. Такая проблема берет свое начало ещё в 1781 г. Ею занимались Гаспар Монже и Л.В. Канторович.

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

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