Контрольная работа № 4

Транспортная задача

Решить закрытую транспортную задачу

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

С трех складов A₁, A₂, A₃ необходимо доставить овощи в пять торговых точек B₁, B₂, B₃, B₄, B₅. Требуется закрепить склады так, чтобы общая сумма затрат на перевозку была минимальной.

Числовые данные задачи представлены в следующей таблице:

Математическая модель задачи

Пусть x_ij - количество единиц груза , которое необходимо доставить от i-го поставщика к j-му потребителю.

Тогда суммарные затраты на перевозку Z составят:

Алгоритм решения

1. Определяем характер транспортной задачи. Модель транспортной задачи называют закрытой, если . В противном случае модель транспортной задачи называю открытой. Если , то открытая транспортная задача сводиться к закрытой путем введения фиктивного потребителя с объемом потребностей и стоимостями перевозок равными 0. Если , то открытая транспортная задача сводиться к закрытой путем введения фиктивного потребителя с объемом потребностей и стоимостями перевозок равными 0.

2. Составим первый опорный план методом «минимальной стоимости».

3. Проверим полученный опорный план на невырожденность. План называется невырожденным, если выполняется условие k=m+n-1 , где k - это число заполненных ячеек, m - число поставщиков, n - число потребителей. Если опорный план вырожденный (условие не выполняется), необходимо перейти от него к невырожденному опорному плану. Для этого незаполненную ячейку с минимальной стоимостью перевозок заполняем нулем, но без образования замкнутого цикла с опорными вершинами в заполненных ячейках.

4. Определим потенциалы поставщиков u_i и потребителей v_j из уравнений . При этом предполагается, что .

5. Проверим опорный план на оптимальность, вычислив оценки свободных ячеек: . Если , то найденный план оптимальный. При этом если какая-либо оценка , то оптимальный план неединственный. В случае если все оценки , то оптимальный план единственный.

6. Если какая-либо из оценок , то план неоптимальный и необходимо произвести перераспределение поставок (произвести загрузку свободной ячейки с отрицательной оценкой).

7. Шаги алгоритма 4-6 повторяем до тех пор, пока не будет получен оптимальный опорный план.

Решение

Задача является закрытой, т.к. .

Первый опорный план:

Т.к. (т.е. опорный план невырожденный). Определим потенциалы поставщиков u_i и потребителей v_j.

Оценки свободных ячеек:

S₁₁=-1;

S₁₂=4;

S₁₄=6;

S₁₅=-2;

S₂₁=-1

S₂₃=-2;

S₃₂=6

S₃₄=10

Полученный опорный план неоптимальный, т.к. среди оценок свободных ячеек есть отрицательные, возьмем самую минимальную из них, это S₁₅=-2;и

S₂₃=-2; мы используем S₁₅=-2.

Произведем перераспределение поставок. Для этого построим замкнутый цикл.

Произведем загрузку свободной ячейки с отрицательной оценкой. Поставку, передаваемую по циклу, определяем как min{40,30}=30; Определим потенциалы поставщиков u_i и потребителей v_j. В результате преобразований получим следующую таблицу.

S₁₁=1;

S₁₂=6;

S₁₄=8;

S₂₁=-1

S₂₃=-2;

S₃₂=6;

S₃₄=10;

Полученный опорный план неоптимальный, т.к. среди оценок свободных ячеек есть отрицательные, возьмем самую минимальную из них, это S₂₃=-2; Произведем перераспределение поставок. Для этого построим замкнутый цикл.

S₁₁=-1;

S₁₂=2;

S₁₄=4;

S₂₁=1;

S₂₅=4;

S₃₂=4;

S₃₄=8;

Полученный опорный план неоптимальный, т.к. среди оценок свободных ячеек есть отрицательные, возьмем самую минимальную из них, это S₁₁=-1;

Произведем перераспределение поставок. Для этого построим замкнутый цикл.

S₁₂=3;

S₁₃=1;

S₁₄=5;

S₂₁=1;

S₂₅=3;

S₃₂=4;

S₃₄=8;

Все полученные оценки неотрицательные , значит найденный опорный план оптимальный и единственный.

Оптимальный план распределения:

Для него значение целевой функции (минимальные транспортные издержки) руб.