Задача 1. Решить транспортную задачу по критерию стоимости. Матрица цен:
A – запасы груза, В – потребность в грузе.
Составление опорного плана Количество запасов больше, чем потребностей, поэтому введем фиктивный пункт назначения, которому припишем фиктивную заявку, равную избытку запасов над заявками, со стоимостью равной нулю.
Метод северо-западного угла Метод состоит в следующем. Просматривается матрица тарифов перевозок C, начиная с левого верхнего угла (клетки). В эту клетку записывается величина D=min(ai,bj). Из запасов соответствующего склада и потребностей магазина вычитается величина D. Если запас товара на складе исчерпан, то эта строка исключается из дальнейшего рассмотрения и продвижение происходит вниз по столбцу. Если потребность магазина в товаре удовлетворена полностью, то этот столбец исключается из дальнейшего рассмотрения и продвижение происходит вправо по строке. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс опять повторяется для левой верхней клетки оставшейся матрицы, и так до тех пор, пока не будет исчерпан весь запас товаров на складах и не будет удовлетворена потребность всех магазинов. Может быть случай, когда одновременно исключаются и строка и столбец, этот случай называется вырожденным. По полученной матрице перевозок вычисляется целевая функция задачи Z.
Метод минимальных стоимостей Алгоритм метода минимальных стоимостей состоит в следующем. Просматривается вся матрица тарифов перевозок, и из нее выбирается позиция с наименьшим значением тарифа C, затем просматриваются значения наличия запасов на складе A и потребности у потребителя B, затем в данную клетку записывается величина D=min(ai,bj). Из запасов соответствующего склада и потребностей магазина вычитается величина D. Если запас товара на складе исчерпан, то эта строка исключается из дальнейшего рассмотрения. Если потребность магазина в товаре удовлетворена полностью, то этот столбец исключается из дальнейшего рассмотрения. В дальнейшем весь процесс повторяется до тех пор, пока не будет исчерпан весь запас товаров на складах и не будет удовлетворена потребность всех магазинов. По полученной матрице перевозок вычисляется целевая функция задачи Z.
Метод Фогеля Метод состоит в следующем. Просматриваются все строки и столбцы матрицы тарифов, вычисляется разность между двумя наименьшими элементами в строке или в столбце. Затем из всех этих разностей выбирается строка или столбец с максимальной разностью. В выбранной строке или столбце, как и в методе минимальных стоимостей, заполняется клетка с наименьшим значением тарифа. Затем обнулившаяся строка или столбец исключаются из рассмотрения, и весь процесс повторяется до полного исчерпания запаса товаров на складах. По полученной матрице перевозок вычисляется целевая функция Z.
Для оптимизации выберем опорный план, составленный по методу Фогеля, так как для него значение целевой функции наименьшее.
Метод потенциалов Критерий оптимальности плана формулируется следующим образом: допустимый план перевозок тогда и только тогда является оптимальным, когда каждому пункту отправления и назначения можно сопоставить величину, характеризующую уровень оценки груза в нем (потенциал) так, что множество этих потенциалов удовлетворяет следующим условиям. 1. Разность потенциалов пунктов назначения и отправления, между которыми запланированы перевозки, равна затратам по транспортировке единицы груза между этими пунктами. 2. Аналогичные разности для всех остальных пар пунктов, между которыми не запланированы перевозки, не превосходят затрат по транспортировке. Иначе говоря, если обозначить через ui потенциал для i-го пункта отправления, а через vj - для j-го пункта назначения, то эти условия запишутся так: vj-ui≤cij причем vj-ui=cij, если перевозка из пункта в пункт предусмотрена в плане ( ). Для каждой базисной переменной xij потенциалы ui и vj удовлетворяют уравнению vj - ui = cij. Чтобы найти значения потенциалов из системы таких уравнений, нужно присвоить одному из них произвольное значение (обычно полагают ui = 0) и затем последовательно вычислять значения остальных потенциалов. Далее, используя вычисленные значения потенциалов, для каждой небазисной переменной вычисляются величины vj -ui - cij. Для того чтобы некоторый допустимый план транспортной задачи был оптимальным необходимо и достаточно, чтобы выполнялось условие vj - ui- cij ≤ 0 (i=1,m; j=1,n). Если данное условие не выполняется, то план можно улучшить перемещением перевозок по циклу. Количество единиц груза, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла. Таким образом, проверка условия оптимальности выполняется до тех пор, пока не будет выполняться условие vj - ui - cij ≤ 0 для всех небазисных клеток. vj-ui=cijбазисные переменные vj-ui≤cijсвободныепеременные u1=0 v3=u1+c13=0+10=10 v4=u1+c14=0+13=13 v5=u1+c15=0+12=12 u2=v42-c24=13-10=3 u5=v4-c54=13-10=3 v1=u5+c51=3+10=13 u4=v1-c41=13-10=3 uф=v5-cф5=12-0=12 v6=uф+cф6=0+12=12 u3=v3-c33=10-10=0 v2=u3+c32=0+11=11
Критерий оптимальности выполняется для всех пустых клеток, значит план оптимальный, окончательная стоимость 1443 единицы.
Задача 2. Найти Гамильтонов контур минимальной длины методом динамического программирования. Матрица расстояний:
Нумерация городов, через которые проходит маршрут коммивояжера, − числа , , , . Без ограничения общности полагаем, что любой маршрут начинается и заканчивается в городе с номером . Задача состоит в минимизации функции
на множестве возможных перестановок чисел , , . Введем следующие обозначения: − длина кратчайшего из путей, соединяющих города и и проходящих в произвольном порядке через города , , ; − перестановка городов , , , соответствующая кратчайшему пути. Предполагается, что числа , , , , попарно различны при , . Рекуррентное уравнение (1) выражает свойство оптимальных многошаговых процессов принятия решения и называется принципом оптимальности или уравнением Беллмана. Согласно (1) какими бы ни были решение, принятое на последнем шаге, и состояние процесса перед последним шагом, предыдущие решения должны составлять оптимальное относительно этого состояния поведение. Кроме того, какими бы ни были решение, принятое на первом шаге, и состояние процесса после первого шага, последующие решения должны составлять оптимальное относительно этого состояния поведение. Решение задачи о коммивояжере состоит в отыскании перестановки , которая задает кратчайший маршрут, и величины , являющейся длиной этого маршрута. Вычислительный алгоритм состоит из следующих этапов. 1. В маршрут входит один узел – рассчитываются значения . 2. В маршрут входит два узла (первый шаг) – вычисляются значения . Полагают, что . 3. В маршрут входят узлов (шаги ) − рассчитываются с помощью уравнения (1). В силу симметричности по аргументам , , достаточно рассмотреть значения , , , такие, что . Строится также таблица оптимальных перестановок . Например, если из чисел под знаком минимума в уравнении (1) минимально первое, то . 4. На -м шаге (замкнутый маршрут) вычисляется по уравнению (1) при искомая величина и искомая перестановка . 5. Определяется гамильтонов маршрут. Дана матрица расстояний при 6 узлах сети связи − (нумерация строк и столбцов в матрицеС − ). а) заполнение таблицы Номер узла, входящего в маршрут, − i Начало маршрута – узел с номером 0
1 0
2 0
3 0
4 0
б) первый этап (k=1) − заполнение таблицы Узел, входящий в маршрут, − i Узел, добавляемый в маршрут, − j
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3
в) второй этап (k=2) − заполнение таблицы Узлы, входящие в маршрут, − i1, i2 Узел, включаемый в маршрут, − j Варианты перестановок i1, i2
1, 2 3
1, 2 4
1, 3 2
1, 3 4
1, 4 2
1, 4 3
2, 3 1
2, 3 4
2, 4 1
2, 4 3
3, 4 1
3, 4 2
г) третий этап (k=3) − заполнение таблицы Узлы, входящие в маршрут, − i1, i2, i3 Узел, включаемый в маршрут, − j Варианты перестановок i1, i2, i3
1, 2, 3 4
1, 2, 4 3
1, 3, 4 2
2, 3, 4 1
д) четвертый этап (k=4) − заполнение таблицы
Узлы, входящие в маршрут, i1, i2, i3, i4, i5 Варианты перестановок i1, i2, i3, i4
1, 2, 3, 4
е) длина гамильтонова контура L=55 (см. п. д)) существует 1 альтернативный маршрут (перестановки узлов выписываются, проходя последовательно пп. д), г), в), б) и а)) 0-3-4-2-1-0 узлы 1-4-5-3-2-1
