Глава 2 Транспортная задача

При определении опорного плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем строкам и всем строкам находим разность между двумя минимальными коэффициентами затрат. Эти разности записываем в специально отведённые для этого строку и столбец таблицы поставок 30. Среди полученных разностей выбираем максимальную. В строке (или столбце), которой данная разность соответствует, заполняем клетку с минимальным коэффициентом затрат.

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

Таблица 30

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

Таблица 31

В строке А₁ минимальный коэффициент затрат равен 9, а следующий за ним равен 16, разность между ними 16 – 9 = 7. В строке А₂ разность равна 12 – 7 = 5, и так далее. Вычислив все разности, видим, что наибольшая из них соответствует строке А₁. В этой строке минимальный коэффициент затрат находится в клетке (1; 5) и равен 9. Отправим в эту клетку максимально возможную поставку x₁₅ = min{200, 190} = 190. При этом потребности пятого потребителя полностью удовлетворены, и он исключается из рассмотрения, а запасы пункта А₁ равны 200 – 190 = 10.

Второй этап. Снова вычисляем разности между минимальными коэффициентами затрат (табл. 32) и видим, что наибольшая из них соответствует строке А₂. В этой строке минимальный коэффициент затрат находится в клетке (2; 1) и равен 7. Отправим в эту клетку максимально возможную поставку x₂₁ = min{300, 120} = 120. При этом потребности первого потребителя полностью удовлетворены, и он исключается из рассмотрения, а запасы пункта А₂ равны 300 – 120 = 180.

Таблица 32

Продолжая итерационный процесс (табл. 33), последовательно заполняем клетки (3; 2), (1; 3), (3; 4), (2; 3), (2; 4) поставками x₃₂ = min{200, 110} = 110, x₁₃ = = min{10, 80} = 10, x₃₄ = min{90, 200} = 90, x₂₃ = min{110, 70} = 70, x₂₄ = 110.

Отметим, что на этапе V появляются строка и столбец, у которых разности максимальны. Поэтому выбирает клетку с минимальным коэффициентом затрат. В данном случае таких клеток две – (2; 3) и (3; 4). Нас интересует та, в которую можно отправить максимально возможную поставку, то есть клетка (3; 4).

Таблица 33

В результате получаем опорный план, в котором заполненными (базисными) являются 7 клеток.

Соответствующее значение целевой функции равно F_Ф = 7·120+8·110+ +16·10+19·70+23·110+19·90+9·190 = 9160.

Оптимизируем план, полученный методом наименьших затрат (табл. 29), используя метод потенциалов.

Методом наименьших затрат получен опорный план:

, F_o =9300 .

Согласно методу потенциалов каждой строке i и каждому столбцу j ставятся в соответствие числа u_i, v_j (потенциалы). Для каждой базисной переменной x_ij потенциалы u_i, v_j удовлетворяют уравнению:

c_ij + u_i + v_j = 0.

Так как базисных переменных n + m – 1 = 7, а потенциалов n+m = 8, то присвоим одному из потенциалов произвольное значение (например, u₁ = 0) и вычислим значения остальных потенциалов:

Результаты вычислений занесём в таблицу 34.

Таблица 34

Далее, используя полученные значения потенциалов, для каждой свободной переменной вычисляем оценки d_ij по формуле:

d_ij = c_ij + u_i + v_j .

Результаты заносим в матрицу оценок (d_ij), проставив в клетках базисных переменных прочерки:

.

Так как в матрице оценок есть отрицательный элемент d₂₃ = – 2, то опорный план неоптимальный. Для получения нового плана необходимо свободную переменную x₂₃ перевести в базис. Чтобы определить, какую переменную нужно вывести из базиса, строим для клетки (2;3) цикл пересчёта.

Цикл пересчёта – это ломаная линия, вершины которой расположены в занятых клетках таблицы поставок (кроме одной, предназначенной для заполнения), а звенья – вдоль строк и столбцов, причём в каждой вершине цикла встречается лишь два звена, одно из которых находится в строке, а другое – в столбце, и в каждых строке и столбце чётное число вершин. Перемещение по циклу производится по следующим правилам:

– каждой из вершин, связанной циклом с данной свободной клеткой, приписывают определённый знак, причём свободной клетке соответствует знак «+», а далее – поочерёдно то «–», то «+»;

– в данную свободную клетку переносится меньшее из значений x_ij, стоящих в клетках со знаком «–», а соответствующая переменная x_ij становится свободной. Одновременно это число добавляется ко всем значениям x_ij, стоящим в клетках со знаком «+», и вычитается из всех значений x_ij, стоящих в клетках со знаком «–».

В данном случае цикл пересчёта и перемещение по циклу представлены в таблице 35.

Таблица 35

Учитывая, что min{180, 70} = 70, в свободные переменные переходит x₃₃. В результате получаем новый план, F₁ = F₀ + x’₂₃ d₂₃ = 9300 + 70·(–2) = = 9160 (см. табл. 36).

Таблица 36

Вычислим значения потенциалов для полученного плана:

и составим матрицу оценок:

.

Так как в матрице оценок нет отрицательных элементов, то полученный план:

оптимальный, и минимальное значение целевой функции F^* = 9160.

Однако в матрице оценок присутствует элемент d₂₂ = 0, что говорит о том, что оптимальный план не единственный. Для получения нового оптимального плана необходимо свободную переменную x₂₂ перевести в базис. Чтобы определить, какую переменную нужно вывести из базиса, строим для клетки (2;2) цикл пересчёта в таблице 37 по сформулированным выше правилам.

Таблица 37

Учитывая, что min{110, 110} = 110, в свободные переменные переходит любая из переменных x₃₂ или x₂₄, например, x₂₄, при этом в клетку (3;2) отправляем фиктивную поставку (табл. 38), то есть x₃₂ = 0 (если не сделать этого, число базисных переменных станет равным шести, а не семи, как должно быть в данной задаче). В результате получаем новый план, F₂ = F₁ + x’₂₂ d₂₂ = = 9300 + 110·0 = 9160.

Таблица 38

Вычислим значения потенциалов для полученного плана:

и составим матрицу оценок:

.

Так как в матрице оценок нет отрицательных элементов, то полученный план:

оптимальный, и минимальное значение целевой функции F^* = 9160.

Однако, продолжив решение, получаем предыдущий план (предлагаем убедиться самостоятельно).

В таблице поставок (табл. 42) находим клетки с наименьшим коэффициентом затрат. Это клетка (1;2) с коэффициентом затрат, равным 3, причём x₁₂ = min{150, 70} = 70.

Таблица 42

Тогда спрос второго потребителя полностью удовлетворён, и второй столбец исключён из рассмотрения.

В оставшейся таблице 43 наименьший коэффициент затрат равен 9 и находится в клетке (1;3), x₁₃ = min{80, 130} = 80. При этом из рассмотрения выбывает первая строка.

Таблица 43

Продолжая заполнение таблицы 43 шаг за шагом, получаем x₂₃ = = min{150,50} = 50, x₂₁ = min{100,100} = 100, x₂₁ = 0 (фиктивная поставка), x₃₄ = min{200,110} = 110, x₃₅ = 90. В результате получаем опорный план, в котором заполненными (базисными) являются 7 клеток.

Соответствующее значение целевой функции равно F_нз = 3·70+9·80+ +14·100+12·50+25·0+16·110+48·90 = 9010.

3 метод. Метод аппроксимации Фогеля