Транспортная задача линейного программирования

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

В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с m баз [pic 1] к  n  потребителям [pic 2].

Различают два типа транспортных задач:

1) По критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию).

2) По критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).

        Количество груза на каждой из баз – а;

        Заказы каждого из потребителей – b;

При условии, что [pic 3] мы имеем закрытую модель, а при условии, что [pic 4] имеем открытую модель транспортной задачи. Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза [pic 5], либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены [pic 6].

В случае выполнения открытой модели баланс транспортной задачи может нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок (транспортная задача с избытком запасов):

2. Сумма поданных заявок превышает наличные запасы (транспортная задача с избытком заявок): 

Рассмотрим последовательно эти два случая:

1) Транспортная задача с избытком запасов.

2) Транспортная задача с избытком заявок.

Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например – склад.

Для решения транспортной задачи необходимо кроме запасов и потребностей знать также и тарифы Cij, т. е. стоимость перевозки единицы груза с базы Ai потребителю Bi.

Решение транспортной задачи начинается с отыскания опорного плана (исходного базиса):

Диагональный метод, или метод северо-западного угла

При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного X11 и заканчивается в клетке неизвестного Xmn, т.е. идет как бы по диагонали таблицы перевозок.

Метод наименьшей стоимости

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

В данном случае заполнение таблицы начинается с клетки для неизвестного X32, для которого мы имеем значение [pic 15], наименьше из всех значений Cij. Эта клетка находится на пересечении третьей строки и второго столбца, соответствующим третьей базе A3 и второму заказчику B2. Третья база A3 может полностью удовлетворить потребность второго заказчика B2 [pic 16]. Полагая [pic 17], вписываем это значение в клетку [pic 18] и исключаем из рассмотрения второй столбец. На базе A3 остается изменённый запас [pic 19]. В оставшейся новой таблице с тремя строками [pic 20] и четырьмя столбцами [pic 21] клеткой с наименьшим значением Cij клетка, где[pic 22]. Заполняем описанным выше способом эту клетку и аналогично заполняем следующие клетки. В результате оказываются заполненными (в приведенной последовательности) следующие клетки: