Задачи транспортировки грузов, назначения и планирования производства

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

Смысл транспортной задачи заключается в следующем. Имеется т пунктов производства некоторой однородной продукции, например, цемента, кирпича, металлопроката и т. п. Имеется п пунктов использования этой продукции. Для каждого пункта производства / = 1, 2, ..., т и каждого пункта потребления у = 1, 2, п заданы: а_; объем производства продукции в пункте / и объем ее потребления Ь_] в пункте у.

Имеется парк транспортных средств для доставки продукции из пунктов производства в пункты потребления. Затраты с_и перевозки единицы объема груза из пункта производства /' в пункт потребления у также известны.

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

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

Имеется два пункта производства продукции 1 и 2 с известными ее объемами а_х =15, а₂ =20. Произведенную продукцию используют три потребителя 1, 2, 3 с объемами потребления Ь_х =10, Ь₂ - 14, Ь₃ =11. Затраты на перевозки грузов из пункта 1 в пункты 1, 2, 3 следующие: с_п =5, с₁₂ - 4, с,₃ = 6. Затраты на перевозку грузов из пункта 2 в пункты 1, 2, 3 такие: с₂₁ - 6, с₂₂ = 4, с₂₃ = 5. Геометрическое представление задачи показано на рис. 6.10. Как видим, оно являет собой двудольный ориентированный граф. Направления перевозок из каждого пункта производства в пункты потребления указаны дугами.

Введем переменные х_и, представляющие собой объемы перевозок от каждого производителя / к каждому потребителю у. Рису-

Рис. 6.10. Геометрическое представление транспортной задачи

нок 6.10 показывает, что из пункта производства 1 можно перевозить грузы в пункты его потребления 1, 2, 3. Объемы этих грузов соответственно будут равны: х_и, х₁₂, х₁₃. Из пункта производства 2 также можно перевозить грузы в пункты потребления 1, 2, 3. Объемы этих грузов будут равны: х₂₁, х₂₂, х₂₃. Всего из пункта производства 1 может быть вывезено х_м + х,₂ + х₁₃ = я, = 15 объемов груза. Из пункта производства 2 может быть вывезено *2, + *22 ⁺ *23 = ^аг - 20 единиц такого объема.

В каждом из пунктов потребления 1, 2, 3 принимаются грузы, привезенные из пунктов производства 1, 2. Объем груза в пункте потребления 1 будет равен *_п + *₂₁ = Ь_х - 10, в пункте потребления 2 — *,₂ + *22 - Ь₂- 14, в пункте потребления 3 — х₁₃ + х₂₃ - Ь₃ = 11.

Затраты на перевозку груза объемом х,, равны с,,*,, = 5х_п, объемом х_|2 — с_|2*,2 = 4х,₂, объемом х₁₃ — с₁₃х_п = 6х_|3 и т. д.

В связи с тем, что перевозка осуществляется из двух пунктов производства продукции 1,2, общие затраты на перевозку будут равны

с_й*

^С12*12 ^С13*13 ”*~^С21*21 З^- С₂₂*22 ^С23*23 ^— ^*ц 4*_]2 + 6х,₃ +

+ 6х_2| + 4х₂₂ + 5х₂₃. Так как требуется минимизировать эти затраты, обеспечив потребителей продукцией в полном объеме и не превысить возможностей производства, получаем следующую задачу.

Минимизировать функцию

? — С,,*,, + С|2*!2 Т С₎₃Х₁₃ + С₂[*21 Т С22*22 ^23“^23 ^— ^*ц ”*~

+ 4х₁₂ + 6х₁₃ + 6х₂₁ + 4х₂₂ + 5х₂₃

при условиях:

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

На пересечении /-й строки и у'-го столбца матриц С, X находятся соответственно затраты с_и на перевозку единицы объема груза х_и от /-го производителя к у-му потребителю. Тогда сумма попарных произведений каждой строки матриц С, X, например,

с_пх_п + с,₂х,₂+...+ с_их_и+...+ ^с,_пх_т =^а_их_и будет определять за-

7=1

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

т п

ны X сумме затрат по каждой строке матриц С, X, т. е. ^^с₍₇х₍₇.

м 7=1

То требование, что сумма объемов продукции, поставляемых от каждого производителя, например /-го, ко всем потребителям, должна соответствовать объему производства а₁, на основании

матрицы X записывается так: х_п + х_п +...+ х₀ +...+ х_ш = V х,₇ = я,,

7=1

/ = 1, 2, ..., т. Запись суммы объемов грузов, принимаемых, например, у'-м потребителем от всех т производителей, которая должна соответствовать объему потребления Ь_], на основании матрицы X будет иметь такой вид:

Х_ч +Ху+..Л х_т] = |>,₇ = Ь_}, у = 1, 2, ..., п.

ы

Таким образом, в общем виде транспортная задача формулируется так: максимизировать функцию

т п

(6.22)

г =

п

• (6.23)
• (6.24)
• (6.25)

при условиях:

= ^аі’ ' = Ь ²’ •••»

)=1 а;/

= ^Ь]’ І = Ь ²’

х_и > 0, / = 1, 2, ..., т, у = 1, 2, ..., /7.

Из записи задачи следует, что она содержит пт переменных, значения которых необходимо найти, пт уравнений (6.23), (6.24) и пт неравенств (6.25), которым должны удовлетворять эти переменные.

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

Задача о назначениях формулируется следующим образом. Имеется п работ и п кандидатов для выполнения этих работ. Назначение кандидата / = 1, 2, ..., п на работу у = 1, 2, ..., п связано с затратами с_и. Требуется найти такое назначение кандидатов на все работы, которое приведет к минимальным суммарным затратам. При этом каждого кандидата можно назначить только на одну работу, и каждая работа может быть занята только одним кандидатом.

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

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

Любой кандидат, претендующий на выполнение работ, может быть назначен на одну из п работ, т. е. его назначение может быть выполнено п способами. Если это назначение уже сделано, то останется п - 1 работ и п -1 кандидатов. Назначение одного из этих кандидатов может быть уже выполнено п - 1 способами. В результате по закону произведения назначение двух кандидатов может быть осуществлено п(п - 1) способами. Рассуждая подобным образом, получим, что назначение всех п кандидатов на п работ может быть выполнено п(п - )(п — 2)-...-1 = /7! способами. При этом назначение всех кандидатов на работы одним способом представляет собой перестановку п целых чисел.

Например, если имеется 4 работы 1,2, 3, 4, то назначение 1-го кандидата на 2-ю работу, 2-го кандидата на 3-ю работу, 3-го кандидата на 1-ю работу, а 4-го кандидата на 4-ю работу даст перестановку 3, 1,2, 4.

Таким образом, множеством решений задачи о назначениях является множество всех перестановок п целых чисел, мощность которого равна п Каждое назначение, т. е. перестановка, связана с суммарными затратами. Для удобства записи этих затрат представим исходные расходы с_і], /' = 1, 2, ..., п, у = 1, 2, ..., п в виде матрицы С, состоящей из п строк и п столбцов.

Номера строк матрицы означают номера кандидатов на работы, а номера ее столбцов — номера работ. В задаче, например, из трех работ и трех кандидатов на их выполнение эта матрица будет

^сч (Сп) ^С13

иметь такой вид: С =

32

, где, к примеру, элемент с₂₃

означает, что назначение кандидата 2 на работу 3 приводит к расходам с₂₃. Тогда при назначении, например, кандидатов 3, 1, 2 получаем следующие суммарные расходы: с₃₁ +с₁₂ + с₂₃.

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

Таким образом, задача о назначениях — это задача о поиске лучшей перестановки п чисел на множестве всех перестановок п!. Очевидное решение этой задачи — полный перебор перестановок с сопутствующим вычислением расходов для каждой из них и выделении по данному показателю лучшей перестановки. Однако такой подход ограничен числом работ п. По возможностям современных персональных компьютеров он может быть применен до « = 18-13.

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

Сформулируем задачу в терминах целочисленного линейного программирования. Для этого введем переменную

[1, если /-й кандидат назначен на у-ю работу

ОС: : — •

¹ (0, в противном случае

Все элементы х_и, у = 1, 2, ..., п представим матрицей X = х_и

с п строками и п столбцами. При этом номер строки матрицы X означает номер кандидата, а номер столбца — номер работы. В связи с тем что каждый кандидат может быть назначен только на одну работу, для каждой строки матрицы Xдолжно выполнят-

П

ся условие ^х_и = 1. С другой стороны, поскольку каждую работу

7=1

может выполнять только один кандидат, для каждого столбца

п

матрицы также должно выполняться условие = '• Общие за-

/=і

траты в связи с каким-либо назначением определяются как ±±‘и*и-

>= I 7=1

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

при условиях:

5>/у = 1, / = 1, 2, ..., п, (6.27)

/= 1

(6.28)

Xх_и = 1, У = 1, 2, ..., п.

7=1

В этой задаче среди п² переменных х_и необходимо найти такой набор из п переменных, который удовлетворяет условиям (6.27)—(6.28) и минимизирует значение функции ъ

На первый взгляд кажется, что сформулированная задача не может быть решена при помощи общих методов линейного программирования. Однако на самом деле это не так. Задача о назначениях в представленном виде — это частный случай транспортной задачи, в котором т - п, а₁ = Ь, = 1, / = 1, 2, ..., п, а условие це-лочисленности заменено условием х_и > 0, / = 1, 2, ..., п,

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

Кроме решения задачи о назначениях, как транспортной задачи, — универсальным симплекс-алгоритмом — ее часто представляют, как задачу о взвешенном паросочетании в двудольном графе и решают специальным методом, получившим название «венгерский» по имени венгерского математика Эгервари. Венгерский метод позволяет решить задачу о назначениях за время 0(п³).

Представим задачу о назначениях в виде паросочетания в двудольном графе (рис. 6.11), состоящем из двух множеств У_а, , каждое из которых включает по четыре вершины.

Рис. 6.11. Взвешенное парасочетание в двудольном графе и матрица затрат С

• 3 7 5 8 2 4 4 5
• 4 7 2 8 9 7 3 8

Вершины множества У_а интерпретируются как кандидаты, а вершины множества — как работы. Матрица затрат С приведена рядом с графом.

Как видно из рисунка, паросочетание в графе определяет некоторое назначение кандидатов на работы: 1-й — на третью, 2-й — на первую, 3-й — на четвертую, 4-й — на вторую работу. Суммарные затраты этого назначения 2 + 5 + 7 + 8 = 22. В задаче требуется найти такое паросочетание, которое дает минимальные суммарные затраты.

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

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

0 2 0 3

В полученной матрице С² сделаем нулевые назначения так, чтобы в каждой строке и в каждом столбце было ровно по одному нулю. Эти назначения пометим звездочками. Как видим, в четвертой строке такое назначение сделать не удалось. Это значит, что оптимальное решение не получено.

Согласно венгерскому алгоритму необходимо найти минимальное количество тех строк и столбцов матрицы С², которые содержат все нули, и вычеркнуть эти строки и столбцы. По матрице С² видно, что это первая и вторая строки и третий столбец. Поэтому получаем:

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

В матрице С⁵ делаем нулевые назначения и отмечем их звездочками. Таким образом, рассматриваемая задача о назначениях решена: 1-й кандидат — на первую работу, 2-й — на вторую, 3-й — на третью и 4-й — на четвертую работу. Суммарные расходы по этому назначению находим по исходной матрице затрат С. Они равны с, | + с22 + с₃₃ + с₄₄ =3 + 4 + 2 + 8 = 17.

Задача планирования производства, иначе называемая как задача формирования производственной программы предприятия или набора портфеля заказов, формулируется следующим образом. Некоторое предприятие изготавливает п типов продуктов, для чего используют т видов ресурсов. Известны затраты а_и /-го вида ресурса / = 1, 2, ..., т для изготовления единицы продукта у'-го типа, у = 1, 2, ..., п. Известны наличные объемы каждого вида ресурса Ь_п которым располагает на данный момент предприятие. Имеются сведения о прибыли с_], которая может быть получена от продажи каждого изделия. Для каждого вида продукта у заданы нижняя граница с!_] его изготовления. Требуется составить такую производственную программу, т. е. выбрать такие изделия для изготовления и такое их количество, чтобы обеспечить наибольшую прибыль предприятия от продажи всех изделий.

Для представления задачи в математической форме введем целочисленные переменные х_], у = 1, 2, ..., п — количества изделий, которые составят производственную программу предприятия. Тогда прибыль, полученная от продажи этих изделий, будет

п

равна с_хх_х + с₂х₂+...+ с_]х_} +...+ с_пх_п = 'L^cJ^xJ?

Суммарное количество /'-го вида ресурса, затрачиваемое на изготовление набора изделий х_], у = 1, 2, п, равно а_пх_{ +а_пх₂ +

+...+ а_их_] +...+ а_шх_п = оно должно быть меньше Ь₁ или

7=1

равно объему ресурса, которым располагает предприятие.

Количество каждого типа изделий х_], согласно условиям задачи, должно быть больше с1₁.

В результате получаем следующую экстремальную задачу: требуется найти максимум функции

п

г = X^С1^Х>

7=1

при условиях:

• — ^/5 I ~ 1? 2, ..., /72,
• 7 = 1

х_] > (1_] ,у = 1, 2, ..., п.

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