Задача о коммивояжере (стр. 4 )

3. Дайте определения понятиям: подмножество маршрутов, нижняя оценка стоимости маршрута, константа приведения, приведенная матрица затрат, штраф «за неиспользование», оптимальный маршрут.

4. В каком случае при решении задачи о коммивояжере методом ветвей и границ выполняется возврат на предыдущий шаг решения, возврат по дереву?

5. Почему метод ветвей и границ называют «эффективным методом перебора»?

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

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

Постановка задачи. Имеется m пунктов производства (складов) некоторого одного продукта, задан ai – объем производства в i-м пункте производства, . Есть n пунктов потребления этого продукта, задан bj – объем потребления (поданные заявки на поставку продукта) в j-м пункте потребления, .

Пункты производства связаны с пунктами потребления сетью дорог с определенными тарифами на перевозки. Стоимость перевозки одной единицы продукта (груза) из i –го пункта производства в j-ый пункт потребления равна сij. Необходимо найти оптимальный план перевозок продукции, при котором транспортные издержки минимальны, продукция полностью вывозится из пунктов производства и полностью удовлетворяется потребность в продукции.

Математическая модель задачи. В качестве переменных выбираются элементы матрицы перевозок: .

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

Модель задачи:

()

Первые m ограничений задают условие: из каждого i-го пункта производства вывезен весь продукт. Например (рис. 1), из первого пункта производства с объемом производства a1 продукт может быть перевезен в 1–n-ый пункты потребления. Объемы перевозок неизвестны и составляют: – количество единиц продукции, перевезенных из первого пункта производства в первый пукнт потебления; – количество единиц продукции, перевезенных из первого пункта производства во второй пункт потребления; – количество единиц продукции, перевезенных из первого пункта производства в n-ый пункт потребления. Сумма всех перевезенных единиц продукции должна быть равна a1 : .

Рис. 1

Следующие n ограничений задают условие: в каждый j-й пункт потребления завезен весь необходимый продукт.

Размерность задачи: . Транспортная задача – частный случай задачи линейного программирования, в которой все ограничения типа равенства. В отличие от общего случая решения задачи ЛП оптимальное решение транспортной задачи всегда существует

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

Открытая и закрытая транспортные задачи. Существует два типа ТЗ: открытая ТЗ и закрытая ТЗ.

Транспортная задача называется закрытой, если выполняется условие баланса: суммарный объем производства равен суммарному объему потребления:

. ()

Обратите внимание, математическая модель () задает закрытую транспортную задачу.

Открытая ТЗ может быть задана в двух вариантах.

Первый вариант. Суммарный объем производства меньше суммарного объема потребления:

. ()

Для решения транспортной задачи необходимо свести открытую транспортную задачу к закрытой, для чего вводится фиктивный пункт производства m+1 с объемом произвоства:

. ()

Второй вариант. Суммарный объем производства больше суммарного объема потребления:

. ()

Для сведения к закрытому типу вводят фиктивный пункт потребления n+1 с объемом потребления:

. ()

Определение опорного плана транспортной задачи. Решение транспортной задачи, как и всякой задачи ЛП начинается с нахождения опорного решения (опорного плана). Рассмотрим два метода нахождения опорного плана транспортной задачи: метод северо-западного угла и метод ми­нимального элемента.

Введем основные определения и обозначения.

Условие транспортной задачи задают в виде транспортной таблицы (табл. 1) вида:

Таблица 1.

объем объем потребления производства			…
	с11	с12	…	с1n
	с21	с22	…	c2n
…	…	…	…	…
	сm1	сm2	…	cmn

Решение транспортной задачи задают в виде матрицы (плана перевозок):

или в виде таблицы плана перевозок (табл. 2):

Таблица 2.

объем объем потребления производства			…
	x11	x12	…	x1n
	x21	x22	…	x2n
…	…	…	…	…
	xm1	xm2	…	xmn

Элементы матрицы плана перевозок (ячейки, клетки таблицы) называют базисными, если они отличны от нуля; нулевые клетки таблицы называют свободными.

План перевозок – допустимый, если он удовлетворяет балансовым условиям (): все заявки удовлетворены, все запасы исчерпаны.

Допустимый план – опорный, если в нем отличны от нуля не более чем r=m+n-1 базисных перевозок , а остальные перевозки равны нулю. Если отличных от нуля перевозок менее чем r=m+n-1, то такой план называют вырожденным опорным планом.

Оптимальный план перевозок – план с наименьшей стоимостью из всех допустимых планов перевозок.

Метод северо-западного угла.

Шаг 0. Условие транспортной задачи задают в виде транспортной таблицы (табл. 1).

Шаг 1. Проверяют выполнение условия баланса (). Если условие баланса не выполняется, т. е. задача открытая, то ее сводят к закрытому типу.

Шаг 2. Создают таблицу плана перевозок (табл. 2), в которой заполнены только объемы производства и объемы потребления. Далее начинают заполнять таблицу перевозок с левого верхнего (северо-западного) угла. При заполнении двигаются по строке вправо и по столбцу вниз. В клетку, находящуюся на пе­ресечении первой строки и первого столбца, помещают мак­симально возможное число единиц продукции, разрешенное ог­раничениями на предложение и спрос: .

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

Пример 1. Определить опорный план по методу северо-западного угла для транспортной задачи, заданной в табл. 3

Таблица 3.

объем объем потребления производства	120	50	110	190
200	7	8	3	2
40	4	5	9	8
110	9	2	1	6

На первом шаге проверяют выполнение балансовых условий. Суммарный объем производства составляет: 200+40+110=350 условных единиц; суммарный объем потребления равен: 120+50+190+110=470. Следовательно, ТЗ – открытая. Для ее сведения к закрытому типу необходимо ввести четвертый пункт производства с объемом производства равным: =470-350=120 условных единиц. Так как пункт производства фиктивен, то стоимости перевозок продукции из этого пункта в пункты потребления нулевые (табл. 4).

Таблица 4.

объем объем потребления производства	120	50	110	190
200	7	8	3	2
40	4	5	9	8
110	9	2	1	6
120	0	0	0	0

На втором шаге создают пустую таблицу плана перевозок и начинают ее заполнение (табл. 5).

Таблица 5.

объем объем потребления производства	120	50	110	190
200	120	50	30	0
40	0	0
110	0	0
120	0	0

В первую клетку помещают: (табл. 5). Заявки пер­вого потребителя полностью удовлетворены, остальные клетки первого столбца заполняют нулями. Остаток продукции в первом пункте составляет: 200-120=80 условных единиц груза.

Далее дви­гаются по первой строке вправо и заполняют клетку (1,2): . Заявки второго потребителя полностью удовлетворены, оставшиеся клетки второго столбца заполняют нулями. Остаток продукции в первом пункте равен: 80-50=30 условных единиц груза.