Оптимизация транспортировки сельскохозяйственной продукции

; (4.5)

При этом система линейных уравнений (4.3) и неравенств (4.4), (4.5), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(X) называется целевой функцией, или критерием оптимальности.

В частном случае, если I = 0, то система (4.3) -- (4.4) состоит только из линейных неравенств, а если I= M, то - из линейных уравнений.

Если математическая модель задачи линейного программирования имеет вид:

(4.6)

;(4.7)

(4.8)

то говорят, что задача представлена в канонической форме. [6]

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

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

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

если некоторая переменная х_к не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными где - свободный индекс, [4]

1.1 Постановка задачи

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у производителей (поставщиков), по потребителям этих ресурсов.

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

Математическая задача ставится так. Имеется n поставщиков (пунктов отправления груза) и m потребителей (пунктов назначения). [8]

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

.(5.1)

Транспортная задача называется закрытой, если суммарный объем отправленных грузов равен суммарному объему потребности в этих грузах по пунктам назначения :

(5.2)

Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой, т. е.:

(5.3)

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

(5.4)

Все j пункты (потребители) должны быть обеспечены грузами в плановом объеме :

(5.5)

суммарные объемы отправления должны равняться суммарным объемам назначения:

(5.6)

Объемы перевозок - неотрицательные числа, так как перевозки из пунктов потребления в пункты производства исключены:

; (5.7)

Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):

(5.8)

В модели (5.4) - (5.8) вместо матрицы стоимостей перевозок () могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транспортной работы.[4]

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

Задачи транспортного типа широко распространены в практике. Кроме того, к ним сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.[6]

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

Структура ограничений задачи учитывается в ряде специальных вычислительных методов ее решения. Рассмотрим некоторые из них. Предварительно сделаем следующее замечание. Открытая транспортная модель может быть приведена к замкнутой модели добавлением фиктивного пункта отправления (потребления), от которого поступает весь недостающий продукт или в который свозится весь избыточный запас. Стоимость перевозок между реальными пунктами и фиктивным принимается равной нулю. Вследствие простоты перехода от открытой модели к замкнутой в дальнейшем рассматриваются методы решения замкнутой модели транспортной задачи.[4]

Как видно из выражения (5.7), уравнение является обязательным условием решения транспортной задач поэтому, когда в исходных условиях дана открытая задача, то необходимо привести к закрытой форме. В случае если

· потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

· запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.[4]

Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.

Транспортным задачам присущи следующие особенности;

· распределению подлежат однородные ресурсы;

· условия задачи описываются только уравнениями;

· все переменные выражаются в одинаковых единицах измерения;

· во всех уравнениях коэффициенты при неизвестных равны единице;

· каждая неизвестная встречается только в двух уравнениях системы ограничений.[9]

1.2 Методы решения транспортной задачи

Метод потенциалов. Идея этого метода заключается в том, что для проверки опорного плана на оптимальность определяется ряд чисел, называемых потенциалами. Сравнение этих потенциалов с оценками клеток транспортной таблицы и лежит в основе признака оптимальности решения задачи.

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

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

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

Существует ряд приемов определения опорного плана, общим для которых является соблюдение правила:

количество заполненных клеток должно соответствовать величине (т+п-1), где т- количество потребителей, п - количество поставщиков. [4]

Метод «северо-западного угла». Первая строка вычеркивается, и двигается по столбику вниз. В клетку, находящуюся на пересечение первого столбца и второй строки, помещается максимально возможное число единиц, размешенное ограничениями на предложение и спрос: х₁₂= min (a₂,b₁-a₁).Если b₁-a₁<a₂, то х₂₁=b₁- a₁. спрос первого потребителя удовлетворен. Первый столбец вычеркивают и двигаются по второй строке вправо. Заполнив клетку, стоящую на пересечение второй строки и второго столбца, переходят к заполнению следующей третьей клетки строки второй строки, либо второго столбца. Процесс продолжают до тех пор, пока не исчерпается предложение и не удовлетворится спрос. Последняя заполненная клетка находится в последнем n-ой строке. [3]

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

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

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

Определение 1. Если при решении транспортной задачи число заполненных клеток транспортной таблицы равно m+n-1, где т -- число поставщиков, п - число потребителей, то план перевозок невырожденный.

Определение 2. Если число заполненных клеток транспортной таблицы меньше га+п-1, то план перевозок вырожденный.

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

Для нахождения оптимального плана перевозок необходимо уметь оценивать полученный план на оптимальность. Как это сделать, не имея в распоряжении всех возможных планов перевозок, которые можно было бы сравнить между собой? Для оценки плана на оптимальность вводится понятие косвенных затрат. Косвенные затраты -- это затраты, получаемые для маршрутов, по которым не осуществляются перевозки при данном плане. Рассчитанные косвенные затраты сравниваются с реальными затратами, которые имели бы место, если бы перевозки по данным маршрутам осуществлялись. Если для всех невыбранных маршрутов косвенные затраты не больше реальных, то данный план перевозок является оптимальным. Если хотя бы для одного маршрута косвенные затраты больше реальных, то план перевозок может быть улучшен путем введения в него данного маршрута. Ввод нового маршрута в план перевозок соответствует вводу в список базисных переменных переменной транспортной задачи, соответствующей этому маршруту. Эти рассуждения лежат в основе ряда методов, применяемых для нахождения оптимального плана перевозок. Рассмотрим один из них -- метод потенциалов. [4]