Торговая компания "ОптТранс Сервис"

Пусть имеются m поставщиков и n потребителей однородного продукта. Известны мощность i-го поставщика А (i=\, 2,..., m и потребность 1-ro потребителя В, (/=1, 2,..., n). Все поставщики
связаны транспортной сетью со своими потребителями, причем для каждой транспортной коммуникации известны удельные показатели эффективности ее использования Сц. Требуется составить такой план прикрепления потребителей к поставщикам, т. е. найти такие объемы поставок продукта Хц от i-ro поставщика 1-му потребителю, который дает наибольший эффект (либо минимум грузооборота, либо минимум суммы тарифных плат и т. д.).
Из многих методов решения матричных задач наиболее широко применяется метод потенциалов и метод условно-оптимальных планов.
Рассмотрим решение матричной транспортной задачи методом потенциалов. Порядок вычислений следующий.
1. Построение начального плана. Существует несколько способов составления начального плана прикрепления потребителей к поставщикам: диагональный, двойного предпочтения, наименьшего значения показателя оптимальности и др. В рассматриваемом примере (табл. 19.1) начальный план составлен способом наименьшего значения показателя оптимальности. Сущность его состоит в следующем. В матрице находим клетку с минимальным значением Сц, это клетка 2—2 со значением критерия C22=l (значения C,, показаны в правом верхнем углу клеток). Записываем в нее максимально возможную поставку *22=26 и второй столбец дальше не рассматриваем. В оставшейся части матрицы вновь отыскиваем минимальное значение С,,, которое обнаруживаем в клетке 3—1. Записываем в эту клетку максимально возможную поставку Jt31 = H, и столбец четвертый исключаем из рассмотрения. Продолжаем таким образом до тех пор, пока не будет распределен весь объем поставок. Последней заполняем клетку 4—5. При этом исключаются из рассмотрения сразу четвертая строка и пятый столбец. Число заполненных клеток должно быть равно m+n—1.