Решение транспортной задачи закрытого типа методом «наименьшей стоимости»

Таблица 3 – Нахождение первой минимальной оценки

Поставщики	Потребители				Запас груза ai
	B1	B2	B3	B4
A1	2	1      min 35	2	2	50
A2	1	3 ——	4	4	40
A3	3	4 ——	5	1	20
Потребность в грузе bj	15	35	20	40

 

Находим следующую минимальную  оценку. В соответствующую клетку таблицы записываем перевозку =15. Так как запросы потребителя удовлетворены исключаем его из рассмотрения.  Запасы 2-го поставщика теперь  а₂-в₁= 40-15=25.

Таблица 4 - Нахождение минимальной оценки

Поставщики	Потребители				Запас груза ai
	B1	B2	B3	B4
A1	2 ——	1 35	2	2	50
A2	1    min 15	3 ——	4	4	40
A3	3 ——	4 ——	5	1	20
Потребность в грузе bj	15	35	20	40

 

Далее снова находим  минимальную оценку и рассматриваем  соответствующую строку и столбец. Теперь запасы 3-го поставщика исчерпаны, исключаем его из рассмотрения.

Таблица 5 - Нахождение минимальной оценки

Поставщики	Потребители				Запас груза ai
	B1	B2	B3	B4
A1	2 ——	1 35	2	2	50
A2	1   15	3 ——	4	4	40
A3	3 ——	4 ——	5 ——	1     min 20	20
Потребность в грузе bj	15	35	20	40

 

В оставшейся части матрицы  минимальной оценкой является с=2  записываем в данную клетку таблицы перевозку х₁₄=min{a₁;b₃}= 15. Исключаем  1-го поставщика из рассмотрения.

 

 

 

 

Таблица 6 - Нахождение минимальной оценки

Поставщики	Потребители				Запас груза ai
	B1	B2	B3	B4
A1	2 ——	1 35	2     min 15	2     ——	50
A2	1   15	3 ——	4	4	40
A3	3 ——	4 ——	5 ——	1 20	20
Потребность в грузе bj	15	35	20	40

 

В оставшейся части матрицы  минимальной оценкой min{c_ij}=min{a₂;b₃}=4 и min{a₂;b₄}=4, заполняем их. Записываем в клетку таблицы (2,3) перевозку х₂₃=5.Теперь у 3-го поставщика остаётся запас=20. Так как запрос 3-го потребителя исчерпан, следовательно исключаем его из  рассмотрения. В матрице С остаётся единственный элемент с₂₄=4  записываем в клетку таблицы (2,4) перевозку х₂₄=20.

Таблица 7 - Нахождение минимальной оценки

Поставщики	Потребители				Запас груза ai
	B1	B2	B3	B4
A1	2 ——	1 35	2 15	2    ——	50
A2	1   15	3 ——	4     min 5	4     min 20	40
A3	3 ——	4 ——	5 ——	1 20	20
Потребность в грузе bj	15	35	20	40

 

Проверяем правильность построения опорного решения. Число  занятых клеток равно N=m+n-1=3+4-1=6 (см. табл.3). Следовательно, решение является опорным.

 

 

 

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

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

Переход от одного опорного решения к другому

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

Означенный цикл

Цикл называется означенным, если его угловые клетки пронумерованы по порядку и нечетным клеткам приписан знак «+», а четным - знак «-» (рис.1)

Сдвигом по циклу на величину Q называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», на Q  и уменьшение объемов перевозок во всех четных клетках, отмеченных знаком «-», на Q.

               Рис.1

Метод минимальной стоимости не оптимален, он только позволяет найти  опорное решение, для полного  решение транспортной задачи нужно  продолжить решение методом потенциалов[5].

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

Данный метод используется для вычисления оценок свободных  клеток

• для каждого пункта отправление А1, А2, … Аn ставим в соответствие потенциала λ1, λ2, … λm.  Для пунктов назначения    Ai  - λi, Bj - βj ставим соответствия.
• составляем систему уравнения λi+Bj=Cij для каждой базисной переменной клетки. Количество полученных уравнений будет равно М+N-1, а неизвестных в системе М+N, т.е. на одну больше. Для того чтобы решить систему задаем значение любого потенциала, обычно λi=0 и, исходя отсюда находим остальные потенциалы. Желательно выполнить проверку[6].

Поставщики	Потребители				Запас груза ai
	B1	B2	B3	B4
A1	4	3 0	2 50	6	50
A2	2 0	4	5	1 70	70
A3	3 40	6 60	7	5	100
Потребность в грузе bj	40	60	50	70

 

Оценки свободных клеток находим с помощью метода потенциалов:

   

 

 

 

 

 

 

 

Записываем потенциалы в таблицу:

Поставщики	Потребители				Запас груза ai
	β1=0	Β 2=3	β 3=2	β 4=-1
α1=0	4 4	3 0	2 50	6 7	50
α 2=2	2 0	4 -1	5 1	1 70	70
α 3=3	3 40	6 60	7 2	5 3	100
Потребность в грузе bj	40	60	50	70

 

1.3  Производственно-транспортная задача

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

Такие задачи математически  могут быть представлены в двух видах: в сетевой и матричной постановке. Будучи основанными, на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов.

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

 

2 АЛГОРИТМ РЕШЕНИЯ ТРАНСПОРТНОЙ  ЗАДАЧИ

1. Является ли модель транспортной задачи закрытой (т.е. если А=В), если модель открытая т(т.е. А≠В), то введением фиктивного пункта или назначения с нулевыми удельными стоимостями делаем модель задачи закрытой:

1. если А>В, то вводим фиктивный пункт B_n+1 с объёмом груза А-В,  удельные стоимости для этого пункта C_ij=0;

2. если А<В, то вводим фиктивный пункт А_m+1 с объёмом груза В-А , удельные стоимости для этого пункта C_ij=0;