Файл: Автоматизация складского учета (Способы решения транспортных задач).pdf

1.9 Транспортная задача. Решение транспортных задач

1.9.1 История развития транспортной задачи

При ведении хозяйственной деятельности человек всегда испытывает недостаток средств. При этом возникает необходимость в решении задачи для определения максимального эффекта при заданных ограничениях на ресурсы. В результате анализа предметной области формулируется целевая функция и уравнения, описывающие область определения. В случае если целевая функция и уравнения линейны, то тогда эта задача относится к задачам линейного программирования. Кроме того, в ней имеется одна особенность - коэффициенты в ограничениях равны единице. По этой причине из множества задач линейного программирования выделяется подмножество транспортных задач, решение которых можно осуществлять с помощью метода потенциалов. Этот метод не отличается от симплекс-метода, с помощью которого можно решить любую задачу линейного программирования, в том числе и транспортную задачу. Однако из-за наличия особенности в ограничениях этих задач был разработан метод потенциалов, в котором используется форма представления данных, отличная от формы представления данных симплекс-метода. Использование этой формы позволяет существенно упростить решение транспортной задачи, по сравнению с симплекс-методом. Кроме того, новая форма очень удобна для визуализации процесса решения. Транспортная задача ассоциируется с перемещением груза от поставщиков к потребителям. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортировки товаров, устранить чрезмерно дальние, встречные и повторные перевозки. Всё это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьём, материалами, топливом, оборудованием и т.д. Вместе с тем алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых задач, не имеющих ничего общего с транспортировкой груза. Всё зависит от того, как интерпретируются так называемые тарифы. Так, например, при решении задачи обеспечения материальными ресурсами при производстве продукции товары, находящиеся на складе, физически не перемещаются, но при этом увеличивается их стоимость в результате расходов на хранение. Таким образом, товар как бы перемещается во времени, а значит, задачу по минимизации расходов на осуществление процесса обеспечения ресурсами можно решить с помощью транспортной задачи.

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году.

Впервые высказывание о важности решения задач линейного программирования и, в частности, транспортной задачи было сделано в прошлом веке. Тогда же были предложены методы решения этих задач. У истоков создания теории линейного программирования стоял русский учёный - Л. В. Канторович. Широкое практическое использование этой теории началось после появления вычислительных машин. Это связано с тем, что при реализации методов линейного программирования требуется выполнять многочисленные последовательные арифметические операции. Ошибка в одном действии приводила к неверному результату и поиску верного решения путём повторного утомительного расчёта.

1.9.2 Виды транспортных задач

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

Транспортная задача в которой имеет место равенство называется закрытой и может быть решена как задача линейного программирования.

Если уравнение баланса не выполняется, то транспортная задача называется открытой. Для решения такой задачи ее сводят к закрытой путем ввода или фиктивного потребителя или фиктивного поставщика.

Решение транспортной задачи состоит из нескольких этапов:

• первоначальное распределение поставок (метод северо-западный)

• улучшение первоначального плана методом потенциалов.

К задачам транспортной логистики относятся:

• выбор вида и типа транспортных средств;

• совместное планирование транспортного процесса со складским и производственным процессами;

• совместное планирование транспортных процессов на различных видах транспорта (в случае смешанных перевозок);

• обеспечение технологического единства транспортно-складского процесса;

• определение рациональных маршрутов доставки.

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

• базисных условий поставки;

• характера груза - его консистенции, веса, объема, габаритов и т.д.;

• количества отправляемых партий груза;

• места нахождения точки, в которую должен быть доставлен груз, его погодных,

• климатических, сезонных характеристик;

• расстояния, на которое должен быть доставлен груз;

• ограничений скорости перевозки груза;

• ценности груза;

• близости расположения точки доставки груза к железнодорожной сети, магистральным автомобильным дорогам, морским и речным портам и т.д.

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

Данные задачи, с математической точки зрения, являются прикладными задачами линейного программирования. Для их решения применяются различные методы. Заложенные в Excel математические методы и алгоритмы обеспечивают успешное решение таких задач.

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

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

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

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. Тогда получаем систему уравнений:

·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,1x1+a1,2x2+...a1,nxn+ xn+1=b1,1x1+a2,2x2+...a2,nxn+xn+2=b2

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

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

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

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

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

F=a0,1x1+a0,2x2+...a0,nxn+b0→ max,1x1+a1,2x2+...a1,nxn+xn+1=b1,1x1+a2,2x2+...a2,nxn+xn+2=b2

.......................................,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)

,l=min{a0,i}

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

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

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

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

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

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

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