Задачи ЛП транспортного типа

Задачи ЛП транспортного типа

Задачи линейного программирования транспортного типа образуют широкий круг задач, общим для которых является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов.

Классическая транспортная задача имеет следующий вид.

Имеются m баз-поставщиков отправления груза (некоторого однородного ресурса), запасы которых составляют соответственно a₁, a₂, …, a_m. Имеются n заводов-потребителей грузов, потребности которых в грузах составляют соответственно b₁, b₂, …, b_n.

Задана матрица с стоимостей доставки по каждой паре поставщик – потребитель: , где – себестоимость перевозки единицы груза от i -го поставщика до j -го потребителя.

Обозначим через x_ij () – объем транспортируемого груза от i -го поставщика j -му потребителю.

Необходимо построить оптимальный план перевозок , при котором транспортные затраты будут минимальными.

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

Таблица

Таблица поставок

Потребители Поставщики	B1	B2	…	Bn	Запасы поставщиков
Потребности потребителей	b1	b2	…	bn

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

(1)

Если такое равенство не соблюдается, то задача является открытой.

Для того чтобы потребности всех потребителей были удовлетворены, необходимо выполнение следующей системы условий:

(2)

Аналогично, для того чтобы были задействованы все запасы складов-поставщиков, необходимо выполнение следующей системы условий:

(3)

По своей сущности искомые переменные не могут быть отрицательными величинами, т.е.

(4)

Введем функцию, отражающую суммарные транспортные затраты:

(5)

Таким образом, математическая модель данной задачи будет иметь вид:

 

 

Необходимо определить такой план перевозок , удовлетворяющий системам (6), (7), условию (9), при котором суммарные транспортные затраты будут минимальными.

Примечания:

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

Поэтому если транспортная задача открытого типа, то

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

.

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

.

При этом стоимости перевозок для каждой фиктивной пары склад-поставщик – потребитель принимаются, как правило, равными нулю.

2) Теорема 2. Ранг r системы уравнений (2), (3) при условии (1) равен:

.

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

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

4) В экономико-математической модели вместо матрицы стоимостей перевозок (С) может задаваться матрица расстояний. В данном случае в качестве целевой функции рассматривается минимум суммарной транспортной работы.

 

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

 

Наиболее распространенным методом решения задач ЛП транспортного типа является метод потенциалов, состоящий из следующих этапов:

1) проверка сбалансированности запасов и потребностей;

2) разработка исходного опорного плана;

3) проверка вырожденности опорного плана;

4) расчет потенциалов;

5) проверка плана на оптимальность;

6) поиск «вершины максимальной неоптимальности» (ВМН);

7) построение контура перераспределения поставок;

8) определение минимального элемента в контуре перераспределения и перераспределение поставок по контуру;

9) получение нового опорного плана.

Этапы 3-9 повторяются, пока не будет найдено оптимальное решение.

Рассмотрим перечисленные этапы.

Расчет потенциалов.

Расчет потенциалов выполняют по загруженным клеткам таблицы поставок, для которых:

 

 

где α_i, β_j – потенциал i -ой строки и j -ого столбца соответственно.

Для первой строки принимают α ₁=0, затем остальные потенциалы рассчитывают по загруженным клеткам в соответствии с указанной выше формулой ()

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

Таблица 6.2

Таблица поставок

Потребители Поставщики	B1	B2	…	Bn	Запасы поставщиков	αi
A1	c11 x11	c12 x12	…	c1n x1n	a1	α1
A2	c21 x21	c22 x22	…	c2n x2n	a2	α2
			…
Am	cm1 xm1	cm2 xm2	…	cmn xmn	am	αm
Потребности потребителей	b1	b2	…	bn
βj	β1	β2	…	βn

 

5. Проверка плана на оптимальность.

Проверка опорного плана на оптимальность осуществляется по незагруженным клеткам. Если для всех незагруженных клеток выполняется условие:

,

то найденный опорный план является оптимальным.

Оптимальное решение будет единственным, если для всех незагруженных клеток выполняется условие:

.

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

 

Пример решения задачи линейного программирования

Транспортного типа.

Дано: с трех складов А₁, А₂, А₃ необходимо доставить овощи в пять торговых точек В₁, В₂, В₃, В₄, В₅. Требуется закрепить склады за торговыми точками так, чтобы общая сумма затрат на перевозку была минимальной.

Числовые данные представлены в следующей таблице:

 

Заводы- потребители	В1	В2	В3	В4	В5	Запасы баз-поставщиков
Базы поставщики
А1
А2
А3
Потребности заводов-потребителей

 

Найти: оптимальный план доставки продукции, при котором совокупные транспортные затраты будут минимальными.

Решение:

Обозначим искомые объемы поставок от i -й базы–поставщика к j -му заводу-потребителю через x_ij

Суммарные затраты на перевозку грузов составят:

Мощности всех складов (баз-поставщиков) должны быть реализованы, спрос заводов-потребителей – удовлетворен, т.е.:

 

I итерация.

II итерация.

3 этап: проверка вырожденности опорного плана

Поскольку , следовательно, план невырожденный.

4 этап: расчет потенциалов баз-поставщиков и заводов-потребителей

Пусть

Занесем результаты расчетов в таблицу поставок:

 

Заводы- потребители	В1	В2	В3	В4	В5	Запасы баз-поставщиков
Базы поставщики
А1
А2							-1
А3							-2
Потребности заводов-потребителей

 

5 этап: проверка плана на оптимальность

Поскольку для всех незагруженных (незаполненных) ячеек соблюдается условие:

, то найденный опорный план является оптимальным.

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

Ответ: оптимальное распределение поставок

Данное распределение поставок обеспечит оптимальные транспортные затраты в размере 550 условных денежных единиц.

 

Задачи ЛП транспортного типа

Задачи линейного программирования транспортного типа образуют широкий круг задач, общим для которых является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов.

Классическая транспортная задача имеет следующий вид.

Имеются m баз-поставщиков отправления груза (некоторого однородного ресурса), запасы которых составляют соответственно a₁, a₂, …, a_m. Имеются n заводов-потребителей грузов, потребности которых в грузах составляют соответственно b₁, b₂, …, b_n.

Задана матрица с стоимостей доставки по каждой паре поставщик – потребитель: , где – себестоимость перевозки единицы груза от i -го поставщика до j -го потребителя.

Обозначим через x_ij () – объем транспортируемого груза от i -го поставщика j -му потребителю.

Необходимо построить оптимальный план перевозок , при котором транспортные затраты будут минимальными.

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

Таблица

Таблица поставок

Потребители Поставщики	B1	B2	…	Bn	Запасы поставщиков
Потребности потребителей	b1	b2	…	bn

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

(1)

Если такое равенство не соблюдается, то задача является открытой.

Для того чтобы потребности всех потребителей были удовлетворены, необходимо выполнение следующей системы условий:

(2)

Аналогично, для того чтобы были задействованы все запасы складов-поставщиков, необходимо выполнение следующей системы условий:

(3)

По своей сущности искомые переменные не могут быть отрицательными величинами, т.е.

(4)

Введем функцию, отражающую суммарные транспортные затраты:

(5)

Таким образом, математическая модель данной задачи будет иметь вид:

 

 

Необходимо определить такой план перевозок , удовлетворяющий системам (6), (7), условию (9), при котором суммарные транспортные затраты будут минимальными.

Примечания:

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

Поэтому если транспортная задача открытого типа, то

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

.

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

.

При этом стоимости перевозок для каждой фиктивной пары склад-поставщик – потребитель принимаются, как правило, равными нулю.

2) Теорема 2. Ранг r системы уравнений (2), (3) при условии (1) равен:

.

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

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

4) В экономико-математической модели вместо матрицы стоимостей перевозок (С) может задаваться матрица расстояний. В данном случае в качестве целевой функции рассматривается минимум суммарной транспортной работы.

 

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

 

Наиболее распространенным методом решения задач ЛП транспортного типа является метод потенциалов, состоящий из следующих этапов:

1) проверка сбалансированности запасов и потребностей;

2) разработка исходного опорного плана;

3) проверка вырожденности опорного плана;

4) расчет потенциалов;

5) проверка плана на оптимальность;

6) поиск «вершины максимальной неоптимальности» (ВМН);

7) построение контура перераспределения поставок;

8) определение минимального элемента в контуре перераспределения и перераспределение поставок по контуру;

9) получение нового опорного плана.

Этапы 3-9 повторяются, пока не будет найдено оптимальное решение.

Рассмотрим перечисленные этапы.