Основные методы решения транспортной задачи

 

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

1) распределительный метод;

2) метод потенциалов.

Для решения транспортной задачи, как и любой задачи линейного программирования, требуется предварительно определить начальное допустимое базисное решение. Начальное допустимое базисное решение можно найти двумя методами:

1) диагональным методом (метод северо-западного угла);

2) методом наименьшей стоимости (метод наименьшего элемента).

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

Пример 8.1. Сталеплавильная компания располагает тремя предприятиями , способными произвести за некоторый период времени 30, 40, 20 тыс.т стали соответственно. Свою продукцию компания поставляет четырем потребителям , потребности которых составляют соответственно 20, 30, 30, 10 тыс.т стали. Стоимость транспортировки 1 тыс.т стали с различных предприятий различным потребителям приведена в матрице (табл. 8.1).

Таблица 8.1

Поставщики	Потребители
	2	2	2	4
	3	2	5	1
	4	3	2	6

Требуется составить такой план перевозки грузов, при котором суммарные затраты по перевозке были бы минимальными.

Решение

Решение транспортной задачи осуществляется в три этапа.

Этап 1.  Определение типа модели транспортной задачи и сведение открытой модели к закрытой.

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

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

Этап 2. Выбор метода нахождения начального допустимого базисного решения.

Диагональный  метод

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

1. Ресурс пункта отправления больше потребности пункта назначения, т.е. .

В этом случае принимается . Тогда потребность j-го пункта назначения будет полностью удовлетворена, а ресурс i-го пункта отправления исчерпан не полностью. Поэтому следует перейти к заполнению клетки (i, j+1).

2. Ресурс пункта отправления меньше потребности пункта назначения, т.е. .

В этом случае принимается . Тогда ресурс i-го пункта отправления полностью исчерпан, а потребность j-го пункта назначения удовлетворена не полностью. Поэтому следует перейти к заполнению клетки (i+1, j).

3. Ресурс пункта отправления равен потребности пункта назначения, т.е. .

В этом случае принимается . Тогда ресурс i-го пункта отправления будет полностью исчерпан и полностью удовлетворена потребность j-го пункта назначения. Поэтому следует перейти к заполнению клетки (i+1, j+1).

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

Таблица 8.2

Поставщики	Потребители				Ресурс
	20	10	-	-	30
	-	20	20	-	40
	-	-	10	10	20
Потребности	20	30	30	10

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

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

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

Таблица 8.3

Поставщики	Потребители				Ресурс
	2 0	3	2 30	4	30
	3	2 30	5	1 10	40
	4 20	3 0	2	6	20
Потребности	20	30	30	10

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

,

где   -  число потребителей,

  -  число поставщиков.

Для рассматриваемой задачи ранг матрицы

.

Для начального допустимого базисного решения, найденного диагональным методом, количеством базисных переменных совпадает с рангом матрицы, а для начального допустимого базисного решения, найденного методом наименьшей стоимости, количество базисных клеток первоначально равнялось 4. Значит, остальные две базисные клетки, имеют величину перевозимого груза, равную нулю (нулевая базисная клетка). В качестве нулевых базисных клеток выбирают обычно клетки с наименьшей стоимостью перевозки. Обычно после такого выбора обязательно необходимо проверить, чтобы базисные клетки образовывали вычеркиваемую комбинацию. Комбинация клеток называется вычеркиваемой, если строки и столбцы матрицы можно вычеркнуть. Сначала рассматриваются все строки и вычеркиваются те из них, в которых содержится не более одной базисной клетки. Затем рассматриваются все столбцы и вычеркиваются те из них, в которых содержится не более одной базисной клетки. Опять переходят к строкам и т.д. до тех пор, пока не будут вычеркнуты все строки и столбцы матрицы. Если же этого сделать нельзя, то комбинация строк и столбцов не вычеркивается, т.е. начальное базисное решение получено неверно. В этом случае в качестве нулевых клеток следует взять другие свободные клетки и опять проверить, получилась ли вычеркиваемая комбинация клеток или нет.

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

Этап 3. Выбор метода нахождения оптимального решения транспортной задачи.

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

Распределительный метод

Пусть начальное допустимое базисное решение было найдено диагональным методом. Матрицу стоимости следует совместить с матрицей начального базисного решения (табл. 8.4).

Таблица 8.4

Поставщики	Потребители				Ресурс
	2 20	3 10	2	4	30
	3	2 20	5 20	1	40
	4	3	2 10	6 10	20
Потребности	20	30	30	10

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

1. Ломаная − связанная, т.е. нет изолированных звеньев.

2. Из каждой вершины ломаной линии исходят два звена, одно из которых расположено в строке, а другое − в столбце матрицы.

3. Для каждой свободной клетки первая вершина цикла пересчета расположена именно в этой свободной клетке. Все остальные вершины находятся в базисных клетках.

4. Вершине цикла пересчета, расположенной в свободной клетке, присваивается знак "+", всем остальные вершинам − знак "+" или "−" в зависимости от того, четная эта вершина ("−") или нечетная ("+").

Соблюдая вышеперечисленные требования, получаем

Так как существуют отрицательные оценки свободных клеток, следовательно, начальное базисное решение неоптимально. Для улучшения решения транспортной задачи выбирается клетка, имеющая самую отрицательную оценку, т.е. кл. (2,4), и для нее строится цикл пересчета

Перемещаемое число  определяется как минимальное из всех чисел, расположенных в отрицательных вершинах цикла, т.е. . Число  перемещается по циклу пересчета, при этом к значениям , расположенным в положительных вершинах цикла, число  прибавляется, а в отрицательных вершинах цикла − вычитается. После перемещения  по циклу получается следующее базисное решение (табл. 8.5).

Таблица 8.5

Поставщики	Потребители
	2 20	3 10	2	4
	3	2 20	5 10	1 10
	4	3	2 20	6

Определяем оценки свободных клеток матрицы

Полученное решение не является оптимальным. Строится цикл пересчета для клетки (1,3)

Получается новое базисное решение (табл. 8.6).

Таблица 8.6

Поставщики	Потребители
	2 20	3 0	2 10	4
	3	2 30	5	1 10
	4	3	2 20	6

Определяем оценки свободных клеток матрицы

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

 ден.ед.

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

Пусть начальное допустимое базисное решение было найдено методом наименьшей стоимости. Совместим матрицу стоимости с матрицей начального базисного решения (табл. 8.7).

Таблица 8.7

Поставщики	Потребители
	2 0	3	2 30	4
	3	2 30	5	1 10
	4 20	3 0	2	6

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

,

где   - потенциал k-гo поставщика;

  -  потенциал l-го потребителя;

  -  стоимость перевозки единицы груза от k-го поставщика  к  i-му  потребителю.

Приняв , можно легко определить потенциалы каждого поставщика и потребителя (табл. 8.8).

Таблица 8.8

	2	1	2	0
0	2 0	3	2 30	4
1	3	2 30	5	1 10
2	4 20	3 0	2	6

Затем определяются оценки всех свободных клеток матрицы по следующему правилу: если  − свободная клетка, то

;

;        ;

;     ;

;      .

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

Получается следующее базисное решение (табл. 8.9).

Таблица 8.9

	2	3	2	2
0	2 0	3	2 10	4
-1	3	2 30	5	1 10
0	4	3 0	2 20	6

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

;     ;    ;

;     ;     .

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

 ден.ед.

Задача 8.1. Три потребителя получают сырье для производства продукции от четырех поставщиков. Определить оптимальный план перевозок сырья, если известно, что потребность трех предприятий в сырье составляет соответственно 30, 60 и 50 тыс.т, а поставщики могут снабдить потребителей сырьем в количестве 40, 20, 30 и 50 тыс.т соответственно.

Стоимость транспортировки 1 тыс.т с различных предприятий различным потребителям приведена в матрице (табл. 8.10).

Таблица 8.10

Поставщики	Потребители
	4	3	1
	1	2	5
	3	2	4
	4	5	2

Задача 8.2. Чугунолитейная компания располагает тремя предприятиями, способными произвести за год соответственно 100, 50 и 50 тыс.т чугуна. Компания поставляет чугун трем потребителям, потребности которых составляют  соответственно  10,  50  и  30 тыс.т.  Стоимость  транспортировки 1 тыс.т чугуна с различных предприятий различным потребителям приведена в матрице (табл. 8.11).

Таблица 8.11

Поставщики	Потребители
	1	8	6
	7	3	4
	4	2	5

Требуется составить такой план перевозок грузов, при котором суммарные затраты были бы минимальными.

Задача 8.3. Четыре потребителя получают сырье для производства продукции от трех поставщиков. Определить оптимальный план перевозок сырья, если известно, что потребность трех предприятий в сырье составляет соответственно 20, 40, 80 и 60 тыс.т, а поставщики могут снабдить потребителей сырьем в количестве 50, 70 и 50 тыс.т соответственно.

Стоимость транспортировки 1 тыс.т с различных предприятий различным потребителям приведена в матрице (табл. 8.12).

Таблица 8.12

Поставщики	Потребители
	2	4	6	7
	5	1	2	4
	1	4	3	1

Задача 8.4. Три машиностроительных предприятия, производящие за год соответственно 20, 10 и 70 тыс. комплектующих изделий, поставляют свою продукцию трем потребителям. Каждому потребителю для бесперебойной работы необходимо 100 тыс. комплектующих изделий. Стоимость транспортировки 1 тыс. комплектующих изделий от различных поставщиков различным потребителям приведена в матрице (табл. 8.13).

Таблица 8.13

Поставщики	Потребители
	2	3	4
	2	6	2
	5	1	4

Требуется составить оптимальный план перевозок комплектующих изделий.

Задача 8.5. Производственные объединения "Альфа", "Сигма" и "Омега" выпускают взаимозаменяемое нестандартное оборудование для четырех строящихся объектов. Перевозки оборудования от складов готовой продукции до строительных площадок выполняются на специальных машинах (по одному комплекту на каждой) со средней скоростью 50 км/ч. На время транспортировки движение перекрывается, однако не более чем на три часа. За каждые 10 мин задержки производственное объединение платит штраф в размере 200 руб. Протяженности (в км) возможных маршрутов от складов до строительных площадок для ПО "Альфа", "Сигма" и "Омега" приведены в матрицах протяженности (табл. 8.14 - 8.16).

Таблица 8.14

Номер строительной площадки ПО "Альфа"	Номер маршрута
	1	2	3	4
1	115	190	135	-
2	185	181	190	179
3	115	90	98	-
4	189	190	-	-

Таблица 8.15

Номер строительной площадки ПО "Сигма"	Номер маршрута
	1	2	3	4
1	90	80	75	100
2	70	60	-	-
3	118	120	100	90
4	15	20	16	-

Таблица 8.16

Номер строительной площадки ПО "Омега"	Номер маршрута
	1	2	3	4
1	30	45	-	-
2	16	20	17	25
3	100	118	120	-
4	190	185	187	-

На первом, втором и третьем складах имеется соответственно 5, 4 и 6 единиц оборудования; для установки на первой, второй, третьей и четвертой строительных площадках необходимо соответственно 4, 2, 3 и 4 единиц.

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

ПРОИЗВОДСТВЕННЫЕ ФУНКЦИИ