Основной математической моделью оптимального прикрепления потребителей к поставщикам является так называемая транспортная задача линейного программирования, которая в общем виде формулируется следующим образом:
В т пунктах отправления (А1, А2 ... Ат), которые в дальнейшем будем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим ai (i = 1, 2 ... m).
Данный продукт потребляется в n пунктах (В1, B2 ... Вn), которые будем называть потребителями; объем потребления обозначим через bj (j = 1, 2 ... n).
Известны расходы на перевозку единицы продукта из пункта Аi в пункт Вj, которые равны cij и приведены в матрице транспортных расходов С = (сij).
Требуется составить такой план прикрепления потребителей к поставщикам (другими словами, план перевозок), при котором весь продукт вывозится из пунктов Ai в пункты Bj в соответствии с потребностью и общая величина транспортных издержек минимальна.
Обозначим количество продукта, перевозимого из пункта Ai в пункт Bj, через Хij. Совокупность всех переменных хij для краткости обозначим символом Х, тогда целевая функция задачи приобретет вид:
А ограничения выглядят следующим образом:
Условия (31) означают полное удовлетворение спроса во всех пунктах потребления; условия (30) определяют больший вывоз продукции от всех поставщиков.
Необходимым и достаточным условием разрешимости задачи (30) – (32) является условие баланса:
Транспортная задача, в которой имеет место равенство (33), называется закрытой и в качестве ЗЛП может быть решена с помощью симплексного метода. Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения.
Чаще всего применяется метод потенциалов, при котором каждой i-й строке (i-му поставщику) устанавливается потенциал Ui, который можно интерпретировать как цену продукта в пункте поставщика, а каждому столбцу j (j-му потребителю) устанавливается потенциал Vj, принимаемый условно за цену продукта в пункте потребителя. В простейшем случае цена продукта в пункте потребителя равна его цене в пункте поставщика плюс транспортные расходы на его доставку, т.е.:
Алгоритм метода потенциалов для закрытой транспортной задачи детально описан в ряде учебных пособий.
Первым этапом этого алгоритма является начальное распределение (составление начального плана перевозок). Для этого имеется ряд методов: северо-западного угла, наименьших стоимостей, аппроксимаций Фогеля и др. Второй этап – построение системы потенциалов на основе равенства (34), а третий – проверка начального плана на оптимальность, причем в случае его неоптимальности переходят к четвертому этапу, содержание которого заключается в реализации так называемых циклов перераспределения плана прикрепления потребителей к поставщикам, после чего переходят опять к третьему этапу. Совокупность процедур четвертого и третьего этапов образует одну итерацию, и эти итерации повторяются, пока план перевозок не окажется оптимальным по критерию (30)
Если баланс (33) не выполняется, то ограничения (31) или (32) имеют вид неравенств типа «меньше или равно»; транспортная задача в таком случае называется открытой. Для решения открытой транспортной задачи методом потенциалов ее сводят к закрытой задаче путем ввода или фиктивного потребителя, если в неравенства превращаются условия (31), или фиктивного поставщика в случае превращения в неравенства ограничений (32).
