Метод потенциалов решения

Пример

Построение начального плана перевозок.

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

1. Метод северо-западного угла.

О. Алгоритм, по которому элементы плана x_ij определяют, начиная с левого верхнего угла таблицы, называют методом северо-западного угла (тарифы не учитываются).

О. Ненулевые перевозки x_ij принято называть базисными, а нулевые – свободными.

Начальный план перевозок, составленный по методу северо-западного угла, является допустимым.

О. План перевозок, в которых число базисных неизвестных равно m + n – 1 называется невырожденным. Если меньше этого числа, то план вырожденный и значит, ввести перевозку с нулевым тарифом.

На складах А₁, А₂, А₃ имеются запасы продукции в количествах 90, 400, 110 т. соответственно. Потребители В₁, В₂, В₃ должны получить эту продукцию в количествах 140, 300, 160 т. соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1т. продукции заданы матрицей (усл. ед.)

Решение:

Запишем исходные данные в распределительную таблицу:

Uj Ai	U1	U2	U3	Запасы
A1	90 ^2	^5	^2
A2	50 ^4	300^1	50 ^5
A3	^3	^6	110 ^8
Потребности

2. Метод минимального элемента для составления первоначального плана перевозок.

1. В плане заполняется клетка, которая соответствует min тарифу.

2. Затем заполняется клетка с min тарифом среди оставшихся и т.д.

3. Если на некотором шаге возникнет ситуация, когда несколько min элементов одинаковых, то min тот, у которого меньше индекс i.

4. В общем случае, нельзя сказать, какой план перевозок ближе к оптимальному. Чаще оказывается ближе метод min элемента.

Bj Ai	B1	B2	B3	Запасы
A1	90 ^2	^5	^2
A2	^4	300 ^1	100 ^5
A3	50 ^3	^6	60 ^8
Потребности

усл. ед.

Посмотрим, сколько заполнено клеток:

m + n – 1 = 3 + 3 – 1 = 5.

Дата добавления: 2014-11-08