3.2. Транспортная задача
В т пунктах отправления А\, А2, ...,Ат, которые в дальнейшем будем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим а* (і — 1, 2, ..., т). Данный продукт потребляется в п пунктах В\, В2, ..., Вп, которые будем называть потребителями; объем потребления обозначим bj (j = 1, 2, ..., п). Известны расходы на перевозку единицы продукта из пункта At в пункт Bj, которые равны ci; и приведены в матрице транспортных расходов С = (ci;).
Требуется составить такой план прикрепления потребителей к поставщикам, т.е. план перевозок, при котором весь продукт вывозится из пунктов Аі в пункты Bj в соответствии с потребностью и общая величина транспортных издержек будет минимальной.
Обозначим количество продукта, перевозимого из пункта А; в пункт Bj, через xtj. Совокупность всех переменных Хц
для краткости обозначим X , тогда целевая функция задачи будет иметь вид
т. п
пх) = min' (ЗЛ6)
i=l;=l
а ограничения выглядят следующим образом:
т.
=&;;;• = 1,п, (3.17)
г=1
п
^хц:= at; і = 1,т, (3.18)
і=і
хч > 0.
Условия (3.17) означают полное удовлетворение спроса во всех пунктах потребления; условия (3.18) определяют полный вывоз продукции от всех поставщиков.
Необходимым и достаточным условием разрешимости задачи (3.16) — (3.18) является условие баланса:
І>І=І*Г <319>
1=1 ;=1
Транспортная задача, в которой имеет место равенство (3.19), называется закрытой и может быть решена, как задача линейного программирования с помощью симплексного метода.
Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения. Наиболее применяемым методом является метод потенциалов, при котором каждой і- й строке (і-му поставщику) устанавливается потенциал иІУ который можно интерпретировать как цену продукта в пункте поставщика, а каждому столбцу j (j-му потребителю) устанавливается потенциал Vj, который можно принять условно за цену продукта в пункте потребителя. В простейшем случае цена продукта в пункте потребителя равна его цене в пункте поставщика плюс транспортные расходы на его доставку, т.е.Vj — щ + с^. (3.20)
Алгоритм метода потенциалов для закрытой транспортной задачи детально описан в ряде учебных пособий (см., например, [6]). Первым этапом этого алгоритма является составление начального распределения (начального плана перевозок); для реализации этого начального этапа имеется в свою очередь ряд методов: северо-западного угла, наименьших стоимостей, аппроксимаций Фогеля и др. Вторым этапом служат построение системы потенциалов на основе равенства (3.20) и проверка начального плана на оптимальность; в случае его неоптимальности переходят к третьему этапу, содержание которого заключается в реализации так называемых циклов перераспределения (корректировка плана прикрепления потребителей к поставщикам), после чего переходят опять ко второму этапу. Совокупность процедур третьего и второго этапов образует одну итерацию; эти итерации повто- ряются, пока план перевозок не окажется оптимальным по критерию (3.16).
Если баланс (3.19) не выполняется, то ограничения (3.17) или (3.18) имеют вид неравенств типа «меньше или равно»; транспортная задача в таком случае называется открытой. Для решения открытой транспортной задачи методом потенциалов ее сводят к закрытой задаче путем ввода или фиктивного потребителя, если в неравенства превращаются условия (3.18), или фиктивного поставщика — в случае превращения в неравенства ограничений (3.17).
Рассмотрим этапы реализации метода потенциалов для закрытой транспортной задачи более подробно. Прежде всего следует отметить, что при условии баланса (3.19) ранг системы линейных уравнений (3.17), (3.18) равен т + п - 1; таким образом из общего числа т х п неизвестных базисных неизвестных будет т + п - 1. Вследствие этого при любом допустимом базисном распределении в матрице перевозок (таблице поставок), представленной в общем виде в табл. 3.5, будет занято ровно т + п - 1 клеток, которые будем называть базисными в отличие от остальных свободных клеток; занятые клетки будем отмечать диагональной чертой.
Таблица 3.5 Мощности поставщиков Мощности потребителей by Ь2 ... Ъп а1 Cll ^^ ^^ хи Cl2 ^^ Х12 Сіп ^^
^^ Х1 п аг С21
Х21 с22
*22 С2п
х2п ат Ст1 ^^ Хт1 ст2
^^ хт2 стп ^^ ^^ хтп