Решение транспортной задачи

Имеется m поставщиков определенного вида продукции. Максимальные объемы возможных поставок заданы и равны соответственно a_i, i=1,2,…,m. Эта продукция используется n потребителями. Объемы потребностей заданы и равны соответственно b_i, j=1,2,…n. Стоимость перевозки единицы продукции от i-го поставщика к j-му потребителю известна для всех i=1,2,…,m и всех j=1,2,…n и равна с_ij. Требуется установить такие объемы перевозок х_ij от каждого поставщика к каждому потребителю, чтобы суммарные затраты на перевозки были минимальными и потребности всех потребителей были бы удовлетворены (если только общий объем возможных поставок покрывает общий объем возможных потребителей).

Математическая модель этой задачи такова:

Очевидно, что эта задача линейного программирования с mn переменными и m+n непрямыми ограничениями.

В литературе описан ряд классических транспортных задачи методов их решения. І

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

2. Задача о назначениях. Имеется n различных транспортных средств, которые требуется распределить между m маршрутами. Известно, что на j-м маршрутами i-е транспортное средство будет приносить доход с_ij. Требуется так распределить транспортные средства, чтобы максимилизировать суммарный доход.

3. Задача о коммивояжере. Имеются города, пронумерованные числами0, 1, 2, …, n. Выехав из города 0, коммивояжер должен объехать все остальные города, побывав в каждом из них по одному разу, и вернуться в исходный город. Известны расстояние с_ij между городами i и j (i,j = 0, 1, 2, …, n). Требуется найти самый короткий маршрут.

4. Задача о четырех красках. В 1976 г. была доказана замечательная теорема: любую географическую карту можно раскрасить, используя не более четырех различных красок. Тем самым была решена одна из наиболее знаменитых и старых математических проблем. Показательно, что обоснование этого результата проделано с помощью ЭВМ: после теоретических рассуждений осталось большое, но конечное число карт, относительно которых не было известно лишь то, можно ли их раскрасить четырьмя красками. С помощью ЭВМ был получен положительный ответ, который и дал окончательное решение проблемы.

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

Задача о назначениях или задача выбора

Пусть имеется n видов работ и n претендентов (рабочих, механизмов и др.) для их выполнения, причем каждый претендент может использоваться на любой работе. Известна производительность i – го претендента на j – й работе (с_ij). Требуется так распределить претендентов по работам, чтобы суммарная производительность была максимальной. При этом каждого претендента можно назначить только на одну работу и на каждую работу можно назначить только одного претендента.

Построим математическую модель этой задачи. Введем переменные:

1, если i – й претендент назначен на j – ю работу, (7.2)

х_ij = 0 – в противном случае,

где i,j = 0, 1, 2, …, n

Требуется максимизировать выражение

Z (x) = (7.3)

при условиях

(7.4)

Условие (7.4) означает, что каждый претендент назначается на одну работу, а условие (7.5) – что на каждую работу назначается один претендент. Условия (7.2) выводят задачу из класса задач линейного программирования, так как они нелинейные, т.е. формально задачу о назначениях можно отнести к классу задач линейного программирования с булевыми переменными. Однако практически задачу о назначениях моно рассматривать как частный случае транспортной (и, следовательно, просто линейной) задачи, в который m=n, а все a_i=b_i=1, если условия (7.2) заменить условиями неотрицательности переменных:

(7.5)

Задача (7.3) при выполнении условий (7.4) – (7.6), как и любая транспортная задача с целыми a_i и b_i, всегда имеет целочисленное решение. Оптимальный план задачи о назначениях представляет собой матрицу Х = (), у который в каждой строке и каждом столбе стоит только один ненулевой элемент, равный единице.

Математически задача о назначенных формулируется следующим образом. Требуется выбрать такую последовательность элементов {С_{ij 1,} С2_j2, Сnj_n} из квадратной матрицы

С₁₂ С12 … С1n

С = С21 С22 … С2n

… …. … ….

Сn1 Сn1 … Сnn

чтобы jk ≠ jl при k≠1 и при этом величина была максимальной.

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

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

Введем следующие определения:

1. Нулевые элементы Ζ1, Ζ2, …, Ζk квадратной матрицы С будем называть независимыми нулями, если для любого 1 ≤ i ≤ k строка и столбец, на пересечении которых лежит элемент Z_i, не содержит элементов Z_k для всех k ≠ i.

2. Две прямоугольные матрицы С - (с_ij) и С” = (с_ij”) размером m х n назовем эквивалентными (С~С”), если с”_ij = с_ij +α_i + β_i ; i = 1,2,…,m; j = 1, 2,..., n.Задачи выбора, определяемые матрицами, являются эквивалентными, так как можно доказать, что множества оптимальных назначений двух задач выбора с эквивалентными матрицами совпадают.

З. В процессе решения задачи некоторые строки (столбцы) матрицы С и эквивалентных ей матриц будут выделяться значком «+», стоящим справа от соответствующей строки (над соответствующим столбцом). Элементы, расположенные в выделенных строках или столбцах, будем называть выделенными элементами.

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

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

Первое преобразование проделывается со всеми столбцами матрицы С. Из максимального элемента j-го столбца (i = 1,2…n) вычитаются элементы этого столбца:

С = (с_ij) → С = (с^′_ij) = (max_i с_ij - с_ij). (6)

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

Второе преобразование производится со строками матрицы С’. Из элементов i-й строки матрицы С’ вычитается минимальный элемент этой строки:

С′ = (с′_ij) → С′′ = (с′′_ij) = (с′_ij – max_j с′_ij). (6)

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

В результате предварительных преобразований мы переходим от задачи выбора на максимум с матрицей С к задаче выбора на минимум с матрицей С′′. Наименьшее возможное значение суммы n элементов неотрицательной матрицы равно, очевидно, нулю. Следовательно, наша задача сводится к выбору в матрице С” (или в эквивалентной ей матрице с неотрицательными элементами) n нулевых элементов, во одному в каждой строке и каждом столбце.

Отмечаем произвольный нуль в первом столбце звездочкой (*). Затем просматриваем второй столбец, и если в нем есть нуль, расположенный в строке, где нет 0′, то отмечаем его звездочкой. Аналогично просматриваются один за другим все остальные столбцы матрицы С′′. Очевидно, что нули матрицы С′′, отмеченные звездочкой, по построению являются независимыми. (k +1 ) - я итерация

Допустим, что 1-я итерация проведена n в результате получена матрица С. Если в матрице С имеется ровно n нулей со звездочкой, то процесс решения заканчивается. Если же число нулей звездочкой меньше n, то переходим к (k +1)-й итерации. Каждая итерация начинается первым и заканчивается вторым этапом. Между ними может несколько раз проводиться пара этапов: третий—первый. Перед началом итерации знаком «+» в выделяют столбцы матрицы С, которые содержат нули со звездочкой.

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

а) строка, содержащая нывыделенный нуль, содержит также нуль со звездочкой;

б) эта строка не содержит нуля со звездочкой.

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

1А — имеется невыделенный нуль в строке, где нет нуля со звездочкой. В этом случае переходят ко второму этапу, отметив последний по порядку нуль штрихом.

1В — все нули матрицы С выделены, т. е. находятся в выделенных строках или столбцах. При этом переходят к третьему этапу.

В случае (6), отметив невыделенный нуль штрихом, сразу переходят ко второму этапу.

Второй этап. Строят следующую цепочку из нулевых элементов матрицы С: отмеченный последним нуль со штрихом, нуль со звездочкой, расположенный в одном столбце с ним, нуль со штрихом, расположенный в одной строке с предшествующим нулем со звездочкой, и т. д. Итак, цепочка образуется передвижением от О′ к О^* по столбцу, от 0′ к О′ по строке и т. д. При этом цепочка всегда начинается и заканчивается нулем со штрихом (возможно, она будет состоять из одного нуля со штрихом). Далее, над элементами цепочкистоящими на нечетных местах (0'), ставят звездочки, уничтожая их над четными элементами (0').Затем уничтожают все штрихи над элементами матрицы С_k и знаки «+». При этом количество независимых нулей будет увеличено на единицу; (k+1)- я итерация закончена.

Третий этап. К этому этапу переходят после первого, если все нули матрицы С_k выделены, т.е. находятся в выделенных строках или столбцах. В таком случае среди невыделенных элементов матрицы С_k выбирают минимальный и обозначают его h > 0. Далее величину h вычитают из всех элементов матрицы С_k, расположенных в невыделенных строках, и прибавляют ко всем элементам, расположенным в выделенных столбцах. Получают новую матрицу С_k⁽¹⁾ эквивалентную С_k.

Поскольку среди невыделенных элементов матрицы С_k⁽¹⁾ появятся новые нули, переходят к первому этапу, при этом вместо матрицы С_k рассматривают матрицу С_k⁽¹⁾.Завершив первый этап, либо переходят ко второму этапу, либо вновь возвращаются к третьему этапу, если все нули матрицы С_k⁽¹⁾ оказываются выделенными.

После конечного числа построений очередной первый этап обязательно закончится переходом на второй этап и количество независимых нулей увеличится на единицу, т. е. (k+1)- я итерация будет завершена. Обоснование отдельных этапов алгоритма венгерского метода для задачи выбора приведено в [100, с. 172-176]

Исходные данные

Вариант 1 Вариант 2 Вариант 3

3 9 5 2 5 3 6 7 9 2 7 7 3 8 2 4 4 8 2 6 2

3 7 6 7 3 8 6 4 3 7 2 3 6 9 2 5 7 8 6 6 6

4 2 5 5 9 2 6 8 5 6 4 9 6 4 2 6 7 8 8 2 7

С = 6 9 3 6 6 3 3 С= 3 7 4 2 4 5 7 С = 2 6 6 2 5 6 5

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

4 8 8 2 7 4 6 6 2 5 5 4 5 8 5 3 6 7 2 7 2

6 9 4 8 8 5 4 5 5 6 3 7 6 2 9 5 5 6 5 6 8

Вариант 4 Вариант 5 Вариант 6

5 5 5 6 5 6 9 3 5 4 9 4 5 8 6 2 3 7 7 3 5

5 5 5 2 3 3 3 2 7 5 9 9 7 6 5 8 5 6 6 5 4

3 3 2 6 7 9 6 7 7 9 9 8 9 8 9 8 2 9 4 5 4

С= 5 5 6 6 5 7 3 С= 6 8 8 3 2 5 2 С= 2 3 3 9 8 6 4

4 4 2 5 4 7 6 7 7 3 6 5 8 4 9 7 4 5 6 3 6

5 9 2 9 2 4 9 4 9 9 6 8 4 5 9 2 9 5 9 6 9

7 3 3 4 5 8 4 6 3 3 2 7 8 3 3 5 3 7 5 3 6

Вариант 7 Вариант8 Вариант 9

2 9 6 6 9 4 9 4 4 6 7 8 5 5 7 8 2 8 5 9 3

9 9 8 9 9 4 8 2 6 6 4 8 6 8 8 7 9 6 9 8 9

8 2 7 5 5 9 7 5 7 2 3 8 7 9 8 8 5 5 3 6 4

С = 2 7 7 2 7 2 3 С = 6 7 8 8 9 6 2 С = 3 7 3 3 9 2 9

5 9 5 4 3 7 4 7 4 5 9 9 4 5 9 2 2 3 6 5 5

5 5 4 8 9 5 7 3 4 4 6 2 8 8 4 2 8 4 5 5 5

6 5 9 4 8 8 9 3 6 6 6 7 7 9 7 3 4 4 8 6 3

Вариант 10 Вариант 11 Вариант 12

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

3 2 5 4 8 3 6 6 5 4 6 2 3 7 2 5 3 3 8 8 7

4 5 8 3 8 4 6 3 8 5 8 9 4 3 3 3 9 9 6 8 4

С= 9 7 9 3 3 4 3 С= 5 5 6 4 7 2 7 С= 2 5 4 3 6 5 8

3 3 6 2 5 8 7 3 7 2 8 5 2 4 3 4 9 4 3 8 5

7 6 4 8 4 2 9 2 8 9 3 8 2 6 7 8 3 6 8 3 6

4 4 4 2 8 5 5 6 8 2 5 9 4 4 4 6 2 7 6 8 6

Вариант 13 Вариант 14 Вариант 15

3 7 8 8 4 2 3 7 3 5 7 6 3 2 7 9 8 7 5 4 9

7 7 5 8 9 6 2 8 3 6 8 3 5 9 3 7 3 4 5 4 3

9 2 9 4 9 4 5 2 3 6 4 6 7 6 8 7 3 6 5 6 3

С= 7 7 5 6 7 6 5 С= 5 6 3 6 2 7 4 С= 4 8 8 9 7 7 5

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

3 2 8 7 5 7 5 6 7 7 4 3 7 4 4 7 2 8 9 6 2

6 7 6 2 5 3 5 7 4 4 9 3 9 9 2 5 4 2 7 2 4

Вариант 16 Вариант 17 Вариант 18

9 6 4 6 3 7 4 4 8 3 6 7 7 8 5 3 5 7 2 8 9

3 5 5 4 7 5 2 7 8 2 5 7 5 4 9 9 6 7 2 5 6

2 7 8 4 4 9 4 5 8 2 8 6 8 6 4 3 9 9 7 8 8

С= 8 3 7 9 7 6 9 С= 2 2 5 3 6 8 9 С= 9 8 6 6 8 8 5

4 3 8 3 4 7 2 6 5 4 9 9 9 7 6 2 2 7 5 6 3

8 8 8 9 3 9 6 7 4 4 5 5 5 9 4 4 7 5 8 4 6

5 4 8 3 5 8 4 8 7 7 8 7 4 6 9 6 6 8 9 4 9

Вариант 19 Вариант 20 Вариант 21

2 4 7 2 6 2 4 6 3 7 5 8 2 4 7 2 3 9 6 3 3

2 8 2 6 4 4 7 3 3 6 8 9 3 3 7 3 7 9 8 3 4

6 4 7 6 4 9 3 4 8 5 4 3 4 4 3 8 4 5 5 6 2

С= 9 6 2 3 5 2 8 С= 4 4 6 2 6 5 2 С= 7 9 6 8 8 3 8

5 9 4 3 6 9 4 3 9 3 6 2 7 8 9 4 7 3 9 7 8

3 2 3 6 3 8 9 5 3 8 9 4 2 8 7 2 6 4 7 7 9

8 4 5 3 5 6 5 3 9 3 2 7 9 6 8 2 5 2 5 4 6

Вариант 22 Вариант 23 Вариант 24

3 6 5 4 9 2 8 3 9 8 7 5 4 9 4 8 7 9 5 9 5

5 3 2 9 9 3 7 5 9 3 8 2 9 5 8 8 2 9 4 2 6

9 3 7 9 4 9 3 2 9 4 6 5 2 4 2 2 8 4 5 5 6

С= 5 9 7 4 9 8 9 С= 7 2 8 4 5 7 5 С= 6 2 4 2 8 9 6

7 9 8 4 6 7 2 6 2 6 6 7 5 4 8 6 4 9 5 5 6

7 8 6 2 4 6 2 3 4 2 9 9 7 2 5 5 6 7 5 8 5

2 2 2 4 2 4 6 3 7 6 6 3 8 4 5 2 6 2 3 7

Вариант 25 Вариант 26 Вариант 27

9 6 3 7 7 4 4 6 3 7 5 2 2 6 6 8 2 3 7 6 6

8 5 8 6 3 5 5 3 9 8 3 6 2 3 2 4 8 2 5 2 7

6 8 9 2 3 3 2 2 6 9 5 3 7 9 7 4 4 6 8 7 7

С= 7 3 8 4 7 7 5 С= 3 5 3 7 3 8 5 С= 6 9 2 2 7 5 5

9 6 6 4 7 7 9 2 7 8 8 3 6 3 3 4 3 2 7 3 8

4 5 5 5 3 5 7 9 9 8 7 3 9 3 4 7 3 5 8 7 3

4 7 5 2 8 7 6 9 6 5 6 4 6 8 2 3 6 7 7 7 8

Вариант 28 Вариант 29 Вариант 30

9 4 2 3 3 2 7 3 7 4 4 4 5 5 3 5 2 5 6 7 8

6 8 9 4 4 8 7 5 5 3 6 3 3 6 4 3 4 2 4 7 9

5 4 6 5 2 7 2 9 5 6 7 3 6 7 8 6 5 9 7 6 2

С= 4 4 7 2 7 3 4 С= 8 8 8 9 4 5 2 С= 9 2 9 7 3 7 9

2 4 8 5 3 6 4 2 4 9 8 3 9 2 8 5 6 7 9 7 2

7 5 3 6 5 7 4 2 8 4 6 3 2 8 9 8 4 7 6 7 7

6 8 3 3 6 5 8 5 6 9 3 7 5 5 5 7 3 5 3 6 6