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

Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи С = (с_ij), i =1,2, …, т, j = 1,2,..., п. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости , и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения. Аналогично с потребителем.

Теорема. Решение транспортной задачи, построенное методом минимальной стоимости, является опорным.

Пример. Используя метод минимальной стоимости, построить начальное опорное решение транспортной задачи, исходные данные которой приведены в таблице:

bj ai

Решение. Запишем отдельно матрицу стоимостей для того, чтобы удобнее было выбирать минимальные стоимости, вычеркивать строки и столбцы:

Среди элементов матрицы стоимости выбираем наименьшую стоимость с ₁₁=1, отмечаем ее кружочком. Это стоимость перевозки груза от 1-го поставщика 1-му потребителю. В соответствующую клетку (1,1) записываем максимально возможный объем перевозки х ₁₁ = min { a ₁, b ₁} = min {60, 40} = 40.

bj ai

Запасы 1-го поставщика уменьшаем на 40, т.е. а '₁ = а ₁ — b ₁ = 60 — 40 =20. Исключаем из рассмотрения 1-го потребителя, так как его запросы удовлетворены. В матрице С вычеркиваем 1-й столбец.

В оставшейся части матрицы С минимальной является стоимость с ₁₄ = 2. Максимально возможная перевозка, которую можно осуществить от 1-го поставщика 4-му потребителю, равна х ₁₄ = min {a' ₁, b ₄} = min {20, 60} = 20. В соответствующую клетку таблицы записываем перевозку х ₁₄ = 20. Запасы 1-го поставщика исчерпаны, исключаем его из рассмотрения. В матрице С вычеркиваем первую строку. Запросы 4-го потребителя уменьшаем на 20, т.е. b '₄ = b ₄—

— а' ₁ = 60 — 20 = 40.

В оставшейся части матрицы С минимальная стоимость с ₂₄ = с ₃₂ = 3. Заполняем одну из двух клеток таблицы (2, 4) или (3, 2). Пусть в клетку (2, 4) записываем х ₂₄ = min { а ₂, b ₄} = min {80, 40} = 40. Запросы 4-го потребителя удовлетворены, исключаем его из рассмотрения, вычеркиваем четвертый столбец в матрице С. Уменьшаем запасы 2-го поставщика а '₂= а ₂ - b ₄ = 80 - 40 = 40.

В оставшейся части матрицы С минимальная стоимость min { с_ij } =с₃₂ = 3. Записываем в клетку таблицы (3, 2) перевозку х ₃₂=min{ a ₃, b ₂}=min {100,60}=60. Исключаем из рассмотрения 2-го потребителя, а из матрицы С второй столбец. Вычисляем а' ₃= а ₃ — b ₂= 100 — 60 = 40.

В оставшейся части матрицы С минимальная стоимость min { с_ij } = с ₃₃ = 6. Записываем в клетку таблицы (3, 3) перевозку х ₃₃=min{ a '₃, b ₃} =min{40, 80}=40. Исключаем из рассмотрения 3-го поставщика, а из матрицы С третью строку. Определяем b' ₃ = b ₃ — а '₃ = 80 — 40 = 40.

В матрице С остается единственный элемент с ₂₃ =8. Записываем в клетку таблицы (2, 3) перевозку х ₂₃ = 40.

Проверяем правильность построения опорного решения. Число занятых клеток таблицы равно N = т + п -1 = 3 + 4-1=6. Методом вычеркивания проверяем линейную независимость векторов-условий, соответствующих положительным координатам решения. Порядок вычеркивания показан на матрице X:

Решение является «вычеркиваемым» и, следовательно, опорным.

Дата добавления: 2014-01-04