Стандартная транспортная задача

⇐ ПредыдущаяСтр 2 из 7Следующая ⇒

Среди задач ЛП одними из наиболее распространенных являются задачи транспортного типа. Задачи транспортного типа находят применение в самых разных областях человеческой деятельности.

Эти задачи отличаются большим количеством переменных и ограничений при малом количестве переменных в каждом из ограничений. Кроме того, каждая граничная точка области допустимых решений транспортной задачи определяется целочисленными значениями переменных, а коэффициенты в ограничениях равны нулю либо единице. Эти особенности позволили разработать для задач транспортного типа свои специфические методы решения, отличающиеся гораздо меньшими, по сравнению с симплекс-методом объемом вычислительной работы и гораздо большей точностью результатов. Методы решения многих задач ЛП транспортного типа по существу воспроизводят шаги алгоритма симплексного метода, но в несколько упрощенном варианте. Значительно проще в них оказывается и выбор начального опорного плана. Приведем пример задачи ЛП транспортного типа.

Пример 1. В каждом из двух складов сосредоточено по однотипных ресурсов. При решении логистической задачи необходимо перевести их в четыре города. В каждый j-й город требуется ресурсов. Стоимость перевозки из i-го склада в j-й город равна . Необходимо составить план перевозки из i-х пунктов в j-е точки, минимизирующий затраты. Исходные данные для примера заданы в табл.1.

Таблица 1

склад	Номер города

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

Пусть - количество средств, переводимых из i-го склада в j-й город. Тогда целевая функция, подлежащая минимизации, определяется соотношением

Поскольку из каждого i-го склада должно быть выведено средств, а в каждую j-й город поставлено средств, ограничения задачи представляют собой соотношения

, ,

где: , i = 1, 2, j = 1, 2, 3, 4.

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

Модель транспортной задачи наглядно изображается в виде сети с n исходными вершинами и m - конечными, (рис.1.) Дадим этой модели следующую экономическую интерпретацию. Каждой исходной i-ой вершине соответствует исходный i-й пункт с запасами продукции равными , каждой конечной j-ой вершине - конечный j - пункт с потребностью равной единиц продукции. Цена доставки единицы продукции из i-го пункта в j-й равна , количество продукции, доставленной из i-го пункта в j-й равно .

Рис. 1. Сетевая модель транспортной задачи

В этих обозначениях формулировка транспортной задачи имеет вид:

где: , i = 1, 2, …, n, j = 1, 2, …, m.

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

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

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

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

Если имеет место равенство

то ограничения преобразуются к виду:

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

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

⇐ Предыдущая 123 4 5 6 7 Следующая ⇒