<<
>>

Теоретические замечания.

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

В этот тип попадают и такие реальные задачи, в которых ничего никуда не перевозится (примерами таких задач являются задачи 1.32, 2.1, 11.6 и 11.7, включенные в настоящий сборник).

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

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

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

Таблица перевозок Хц имеет те же размеры (тхп) и содержит переменные решения. Необходимо также задать запасы поставщиков, готовые к вывозу (на Рис. 64- это столбец ?г) и величины заказов потребителей (на рисунке - это строка

А).

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

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

Наконец, чтобы получить целевую функцию (суммарные издержки), необходимо рассмотреть суммы произведений каждой строки таблицы транспортных издержек на соответствующую строку таблицы перевозок и сложить их, суммируя по / от 1 до т. Это и даст двойную сумму, показанную на Рис. 64. При этом номер источника ( поставщика), 1< / <т, номер пункта назначения (потребителя), 1< у <п. Г с

и 11 С12 . С ^

L'1n Г x11 x12 . x >

• X1n Г S1 1 = С21 С22 . . С2

2 n , (xij) = x21 x22 . . x2n , (Si) = S2 V Cm1 Cm2 . . С )

mn V xm1 xm2 . . x

mn V° m J D, =( А А,)

n m

S (xij ~Si)=0 S(xv_D)=0, i = 1,2,•••m, j = 1,2, -n

j=1 i=1 mn

Mm-, c=SSxc

i =1 j =1

Рис. 64

Если задача сбалансирована и никаких других ограничений, кроме упомянутых выше нет, Поиск решения использует эффективный алгоритм решения для этой задачи, причем, если запасы и заказы выражены целыми числами, то и переменные решения xij получатся целыми, даже если не требовать этого специально. Кроме того, гарантировано, что количество ненулевых перевозок xij не будет превышать m+n-1, т.е.количество «игроков» (поставщиков и потребителей) минус 1.

Несбалансированность в транспортной задаче

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

В первом случае,

m n

S s.>S D,.

1=1 ,=1

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

Это можно трактовать так, как если бы появился еще один «фиктивный» потребитель.

Если потребовать, чтобы заказ этого «потребителя» в точности равнялся бы разности между суммой всех запасов и суммой всех заказов

о1,„=Е

1=1 j=l

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

Во втором случае, когда

т п

?

1=1 j=l

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

Это можно трактовать так, как если бы появился еще один «фиктивный» поставщик. Потребуем, чтобы запас этого «поставщика» в точности равнялся бы разности между суммой всех заказов и суммой всех запасов

пт

^-?8..

j=l 1=1

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

Заметим, что несбалансированные транспортные задачи можно, конечно, решать и просто заменив в соответствующих ограничениях знаки равенств на знаки нестрогих неравенств. Однако, при этом надо иметь в виду, что для решения такой задачи М8-Бхее1 будет применять общие методы решения ЛП- задач, а не специфические «транспортные» алгоритмы. В результате эффективность решения может быть значительно ниже, и получение целочисленного решения не гарантируется.

Еще одно возможное осложнение транспортной задачи - это запрещение определенной перевозки от /-го поставщика к у-му потребителю для составляемого плана перевозок (ремонт дороги, неплатеж и пр.). В этом случае, естественно, можно просто ввести ограничение Ху =0. Однако, вновь это означает невозможность использования эффективных «:транспортных» алгоритмов решения.

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

Подробнее о постановке и методах решения транспортной задачи читайте в учебных пособиях [1,2,7-11].

Задача о назначениях

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

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

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

Поэтому все “запасы” и все “заказы” равны 1.

Понятно, что все переменные решения в задаче о назначениях могут принимать только значения 1 или 0. На первый взгляд, это похоже на задачи целочисленного линейной оптимизации. Однако, в силу упомянутых выше особенностей структуры ограничений транспортной задачи, явно требовать целочисленности переменных решения (их равенства только нулю или единице) не требуется. Такие значения получаются при решении автоматически. При этом, разумеется, «транспортные» алгоритмы решения гораздо более эффективны, чем алгоритмы решения задач целочисленного линейной оптимизации.

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

Подробнее о задаче о назначениях читайте в учебных пособиях [1,2,7-11].

Задачи оптимизации логистики и цепочек поставок.

Задачи, возникающие в деятельности отдела логистики часто гораздо сложнее и разнообразнее, чем простая транспортная задача, хотя последняя очень часто может входить в них как составная часть. Всякий раз, когда это возможно, нужно стремиться использовать правила решения транспортной задачи, описанные выше. Даже если решаемая задача «не вполне транспортная», практика показывает, что выполнение этих прпавил способствует повышению эффективности решения. Однако нужно иметь в виду, что любое дополнительное ограничение сверх описанных выше ограничений транспортной задачи, заставляет Поиск решения отказаться от специфических «:транспортных» алгоритмов и решать задачу общим Симлекс-методом. Это, в свою очередь, означает, что переменные решения (объемы перевозок) могут оказаться нецелыми, а их количество будет превышать число поставщиков плюс число потребителей минус 1. В этом случае, неизбежно введение требования целочисленности переменных решения, что сильно усложняет задачи логистики.

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

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

<< | >>
Источник: Зайцев М.Г., Варюхин С.Е.. Методы оптимизации управления и принятия решений: примеры, задачи, кейсы: учебное пособие. — 2-е изд., испр. — М.: Издательство “Дело” АНХ. - 664 с.. 2008

Еще по теме Теоретические замечания.:

  1. Теоретические замечания.
  2. Теоретические замечания.
  3. Теоретические замечания.
  4. Теоретические замечания.
  5. Теоретические замечания
  6. Теоретические замечания.
  7. Статья 232. Рассмотрение замечаний на протокол
  8. Статья 231. Замечания на протокол
  9. 10. ДОПОЛНИТЕЛЬНЫЕ ЗАМЕЧАНИЯ
  10. 1. ТЕОРЕТИЧЕСКИЕ ПРОБЛЕМЫ
  11. 5.7. Теоретические кривые распределения
  12. Глава 18 ТЕОРЕТИЧЕСКОЕ И ПРАКТИЧЕСКОЕ
  13. Теоретический синтез
  14. Предварительные замечания
  15. Теоретические ошибки репрезентативности
  16. ПРЕДВАРИТЕЛЬНЫЕ ЗАМЕЧАНИЯ
  17. 3. Теоретическое содержание немецкой геополитики