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

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

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

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

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

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

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

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

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

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

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

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

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

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

сй*

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

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

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

? — С,,*,, + С|2*!2 Т С)3Х13 + С2[*21 Т С22*22 ^23“^23 ^*ц ”*~

+ 4х12 + 6х13 + 6х21 + 4х22 + 5х23

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

*11

+ *12

+ *13

= я,

II

4#

*21

+ *22

+ *23

= а2

= 20,

*11

+ х21

= ьх

= ю,

*12

+ *22

- Ь2

= 14,

*13

+ *23

II

= 11,

*11

, *12 5

*13, X

21 ’ %

22 ’ *23 - 0

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

СиСп- • -С] .. .Сп

хпхх2...хХ] ...хХп

С 21С 22 •• - си ' • • С2п

X 21 X 29 • • • X 2j • • • X 2 а

С =

, Х =

^71 С12 * * * ^7/ • • * п

*^71 *7 2 * • • *7/ * * * *7л

С т 1 С т 2 * * * С Пу * * * ^ пт

•* т 1 */ц 2 * * * * пу * * * * тп

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

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

7=1

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

т п

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

м 7=1

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

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

7=1

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

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

ы

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

т п

(6.22)

г =

п

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

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

= аі’ ' = Ь 2’ •••»

)=1 а;/

= Ь]’ І = Ь 2

хи > 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

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

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

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

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

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

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

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

ОС: : — •

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

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

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

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

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

Представим задачу о назначениях в виде паросочетания в двудольном графе (рис. 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. В задаче требуется найти такое паросочетание, которое дает минимальные суммарные затраты.

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

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

3

7

5

8

3

0

4

2

5

0*

2

2

2

с =

2

4

4

5

2^с =

0

2

2

3

-^С2 =

0

0*

2

0

4

7

2

8

2

2

5

0

6

2

3

0*

3

9

7

3

8

3

6

4

0

5

6

2

0

2

0 2 0 3

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

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

А* А

) О

и 2* х

о п*

- А

> П

и и а

  • 2 3 (
  • 6 2 (

- и

Г 3

) 2

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

-2

0

2

0

0*

2

4

2

-2

-2

2

-2

, С5 =

0

0*

4

0

0

1

0

1

0

1

0*

1

4

0

0

0

4

0

0

0*

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

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

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

п

равна сххх + с2х2+...+ с]х} +...+ спхп = 'LcJxJ?

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

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

7=1

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

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

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

п

г = XС1Х>

7=1

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

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

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

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

 
< Пред   СОДЕРЖАНИЕ     След >