Пример № 4. Транспортная задача открытого типа, представленная в матричной форме без ограничений пропускной способности

Перед рассмотрением транспортных задач открытого типа необходимо заметить, что такие задачи на практике встречаются чаще, чем задачи закрытого типа.

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

В озможны два варианта транспортной задачи открытого типа. Если ,

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

m in (max)

и следующую систему ограничений:

, (i = 1,2,...,m),

, (j = 1,2,...,n),

.

Е сли , то система ограничений будет записана иначе:

, (i = 1,2,...,m),

, (j = 1,2,...,n),

.

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

Стоимость перевозки в клетках, связанных с фиктивным потребителем (поставщиком), принимается равной нулю.

Однако более удобным при решении транспортных задач открытого типа представляется метод условно-оптимальных пленов, разработанный А.Л. Лурье.

Рассмотрим решение транспортных задач открытого типа на примерах.

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

составить математическую модель задачи;

• составить начальный план, рассчитать суммарную себестоимость перевозок;

• решить задачу методом условно-оптимальных планов, рассчитать суммарную себестоимость перевозок конечного плана;

• проверить полученный план на оптимальность методом потенциалов;

• проанализировать начальный и оптимальный варианты.

Данные по объему производства и потребления и матрица себестоимостей перевозок приведены в табл.16.

Таблица 16

Объем отправления и потребления грузов

Станция отправления	Ресурсы, тыс. т	Станция назначения
		В1	В2	В3	В4	В5	В6	В7
		Объем потребления, тыс. т
		80	90	190	130	150	160	150
А1	200	80	40	90	100	35	75	80
А2	250	10	30	45	40	30	65	30
А3	100	20	35	60	60	80	30	70
А4	250	40	25	10	25	65	50	60
А5	200	15	50	20	20	40	80	20

 

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

тыс. т,

тыс. т.

Суммарный объем производства превышает суммарный объем потребления на 50 тыс. т. Эта задача открытого типа.

Целевой функцией будет являться минимальная суммарная себестоимость перевозок

, при следующих ограничениях, (i = 1,2,...,5),

, (j = 1,2,...,7), .

Решение задачи методом условно-оптимальных планов начинается с составления исходного плана. Методика построения исходного плана перевозок вытекает из сущности метода условно-оптимальных планов, которая заключается в следующем.

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

При построении исходного плана в каждом j-м столбце матрицы стоимостей находится клетка с минимальным критерием стоимости и в неё записывается перевозка, равная полной потребности данного столбца, x_ij = b_j. При наличии нескольких клеток с минимальной стоимостью поставка b_j распределяется между ними произвольно. Так, для потребителя В₁ это будет клетка А₂В₁ с себестоимостью 10 руб./т, для потребителя В₂ это клетка А₄В₂ с себестоимостью 25 руб./т и т.д.

Исходный план перевозок представлен в табл.17

Таблица 17

Исходный план перевозок

Начальное значение целевой функции составит

C_нач = f (x) = 80· 10 + 90· 25 + 190· 10 + 130· 20 + 150· 30 + 160· 30 + 150· 20 = = 19850 тыс. руб.

Значение целевой функции данного начального плана является минимальным, т.е. отвечает критерию оптимальности, но не отвечает существующей системе ограничений. Следовательно, необходимо продолжить решение. Задача решается методом условно-оптимальных планов.