Определение оптимального плана перевозок

ЛАБОРАТОРНАЯ РАБОТА

ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ПЛАНА ПЕРЕВОЗОК

(ТРАНСПОРТНАЯ ЗАДАЧА)

Цель работы

1. Познакомиться с общей постановкой транспортной задачи.

2. Решить задачу методом северо-западного угла

3. Решить задачу методом потенциалов

4. Дать анализ результатов расчетов

Постановка транспортной задачи

Пусть в пунктах А₁ , А₂ ,…,А _m производится некоторая однородная продукция. Таким образом, имеется m поставщиков А _i , где = . Объем производства в пункте А _i составляет a_i единиц. Величину a_i называют мощностью поставщика, а - суммарной мощностью всех поставщиков. Допустим, что выпускаемая продукция потребляется в пунктах В₁ , В₂ , …, В _n , причем в пункте В _j , составляет b_j единиц продукции. Величина b_j называется емкостью (спросом) потребителя В _j , где . Общий объем потребления (суммарная емкость) составляет .

В практике встречаются два типа транспортных задач.

1. Объем производства совпадает с объемом потребления, то есть

=.

Такой тип задач называется закрытыми транспортными задачами.

2. Объем производства не совпадает с объемом потребления, то есть

.

Такой тип задач называется закрытыми транспортными задачами.

Рассмотрим принцип решения закрытой транспортной задачи (1 тип).

При этом предполагается:

- от каждого поставщика возможна перевозка к любому потребителю;

- стоимость перевозки единицы продукции от поставщика А _i к потребителю В _j известна и составляет C_ij денежных единиц. ( В некоторых случаях вместо стоимости перевозки может быть указано расстояние от А _i до В _j .)

Условия задачи могут быть записаны в виде таблицы 1.

Таблица 1.

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

Пусть объем перевозок из пункта А _i