Реферат Решение задач коммивояжёра, способов её решения

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 13.1.2025

Содержание
Введение

1. Теоретическая часть............................................................................... 6

1.1 Основные понятия теории графов....................................................... 6

1.2 Формулировка и некоторые свойства решений задачи коммивояжера.      8

1.3 Постановка задачи коммивояжера как задачи на графе...................... 10

1.4 Условия существования Гамильтонова контура.................................. 10

1.5 Метод ветвей и границ…………………………………………………. 11

1.6 Практическое применение задачи коммивояжера…………………… 17

2. Практическая часть ............................................................................... 20

Заключение

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

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

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

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

Рассмотрена задача коммивояжёра, а также приведён алгоритм метода ветвей и границ для решения задачи коммивояжёра.
1.
Теоретическая часть
1.1 Основные понятия теории графов



Многие задачи принятие решений можно решить с помощью теории графов.

Графические представления – наглядные отображения исследуемой системы процесса или явления на плоскость: рисунки, чертежи, схемы и блок-схемы, диаграммы, графы. На языке теории графов формируются и решаются многие технические задачи, задачи из области экономики, социологии, менеджмента и т.д. Графы используются для наглядного представления объектов и связи между ними.

Пусть G-неориентированный граф. Геометрически граф можно представить как набор вершин (точек), определенные пары которых соединены линиями. Например, сеть дорог, соединяющих города ,,,,, можно представить в виде графа следующим образом. Города обозначены точками (вершинами), а дороги – неориентированными линиями (рис 1.1).

рис 1.1 Сеть дорог между городами.

Неориентированные линии означают наличие двустороннего движения между соответствующей парой городов. Пересечения линий не считаются вершинами.

При изображении графа не имеет значение расположение вершин на плоскости, кривизна и длина ребер (рис 1.2).

рис 1.2 Изображение графов

      Вершины графов обозначаются буквами или натуральными числами. Ребра графа – пары чисел.

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

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

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

Граф называется сильно связным, если между каждой парой его вершин

, существует путь (

) такой, что

является начальной вершиной пути, а

- конечной.

Граф называется связным, если между парой его вершин

, существует такая последовательность элементов (дуг или ребер, или же и дуг, и ребер), что любая соседних элементов в этой последовательности имеет общую вершину. Очевидно, что любой сильно связный граф является связным. Связный неориентированный граф называется деревом, если он не имеет циклов. В дереве любые две вершины связаны единственной цепью.
1.2 Формулировка и некоторые свойства решений задачи коммивояжера
Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы привести задачу к научному виду, введём некоторые термины. Города перенумерованы числами j
Î
Т=(1,2,3..
n
). Тур коммивояжера может быть описан циклической перестановкой t
=(
j
₁
,
j
₂
,..,
j_n
,
j
₁
), причём все j
₁
..
j_n – разные номера; повторяющийся в начале и в конце j
₁,показывает, что перестановка зациклена. Расстояния между парами вершин С_ijобразуют матрицу С. Задача состоит в том, чтобы найти такой тур t:

             (1)

Относительно математизированной формулировки задачи коммивояжера уместно сделать два замечания.

1) В постановке С_ijозначали расстояния, поэтому они должны быть неотрицательными, т.е. для всех j
Î
Т:

С
_ij
³
0;
C_jj
=
∞              (2)

(последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i
,
j:

С
_ij
= С
_ji

                         (3)

и удовлетворять неравенству треугольника, т.е. для всех:

С
_ij
+ С
_jk
³
C_ik

(4)

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если С_ij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта задачи коммивояжера: симметричную задачу, когда условие (3) выполнено, и несимметричную - в противном случае. Условия (2)-(4) по умолчанию мы будем считать выполненными.

2) В несимметричной задаче коммивояжера все туры t
=(
j
₁
,
j
₂
,..,
j_n
,
j
₁) и t
’=(
j
₁
,
j
_n
,..,
j
₂
,
j
₁
) имеют разную длину и должны учитываться оба. Разных туров очевидно (n
-1)!.

Зафиксируем на первом и последнем месте в циклической перестановке номер j
₁, а оставшиеся n
-1 номеров переставим всеми (n
-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в

два раза меньше, т.к. каждый засчитан два раза: как t
и как t
’. Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i
,
j
) проведено, если С_ij
=0 и не проведено, если С_ij
=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).

В терминах теории графов симметричную задачу коммивояжера можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра (i
,
j
)=
С
_ij. Найти гамильтонов цикл минимальной длины. В несимметричной задаче коммивояжера вместо «цикл» надо говорить «контур», а вместо «ребра» - «дуги» или «стрелки».

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

Рис. 1.3
      Формулировка: Множество городов: . Расстояние между городами i и j: . П – множество перестановок элементов А, перестановка

Если городам поставить в соответствии вершины графа, а соединяющих их дорогам дуги, то в терминах теории графов задача заключается в определении гамильтонова контура минимальной длины. Гамильтоновым контуром называется путь, проходящий через все вершины графа, у которого начальная вершина совпадает с конечной. Здесь под длиной контура понимают не количество дуг, входящих в контур, а сумму их длин. Длина соответствующей дороги – вес ребра. Граф должен быть полным, т.е. в нем имеются все возможные ребра. Если же граф не является полным, то его можно дополнить недостающими ребрами с весом равным .
1.4 Условия существования Гамильтонова контура
Последовательность (путь), который требуется найти – ориентированный остовный простой цикл минимального веса в орграфе; такие циклы также называют гамильтоновыми. Очевидно, что в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о коммивояжере для полных орграфов. Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер приписать вес - это «компьютерная бесконечность», т.е. максимальное из всех возможных в рассмотрениях чисел. Если во вновь построенном полном орграфе найти теперь легчайший гамильтонов цикл, то при наличии у него ребер с весом можно будет говорить, что в данном, исходном графе «цикла коммивояжера» нет. Если же в полном орграфе легчайший гамильтонов цикл окажется конечным по весу, то он и будет искомым циклом в исходном графе. Гамильтоновым контуром называется путь, проходящий через все вершины графа, у которого начальная вершина совпадает с конечной. Здесь под длиной контура понимают не количество дуг, входящих в контур, а сумму их длин.

Цикл Гамильтона.

Пусть G-граф. Циклом Гамильтона называется простой цикл, который содержит все вершины данного графа.

Теорема 1.

Для того, чтобы в графе существовал цикл Гамильтона, необходимо, чтобы этот граф был связным.

Теорема 2.

В полном графе , если n>=3, цикл Гамильтона есть в полном двудольном при m>=1, цикл Гамильтона есть.
1.5
Метод ветвей и границ

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

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

Постановка задачи

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

В терминах теории графов задачу можно сформулировать следующим образом. Задано n вершин и матрица {c_ij}, где c_ij ≥0 – длинна (или цена) дуги (i, j), . Под маршрутом коммивояжера z будем понимать цикл i₁, i₂,…, i_n,
i₁точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера, длина маршрута l(z) равна сумме длин дуг, входящих в маршрут. Пусть Z – множество всех возможных маршрутов. Начальная вершина i₁ – фиксирована. Требуется найти маршрут z₀ Î Z, такой, что l(z₀)= min l(z), z Î Z
.

Решение задачи

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

состояло из маршрутов, содержащих некоторую дугу (i, j), а другое подмножество

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

оказываются не меньше нижней границы множества всех маршрутов, т.е. φ(Z)≤ φ (

), φ(Z) ≤ φ (

).

Сравнивая нижние границы φ () и φ (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

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

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

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

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

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

Константу приведения следует выбирать в качестве нижней границы длины маршрутов.
Разбиение множества маршрутов на подмножества
Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени Θ_ij нулевых элементов этой матрицы. Степень нулевого элемента Θ_ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов c_ij– не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.

Для получения платежной матрицы маршрутов, включающей дугу (i, j) вычеркиваем в матрице строку i и столбец j, а чтобы не допустить образования цикла в маршруте, заменяем элемент, замыкающий текущую цепочку на бесконечность.

Множество маршрутов, не включающих дугу (i, j) получаем путем замены элемента c_ij на бесконечность.

Пример решения задачи коммивояжера методом ветвей и границ

Коммивояжер должен объездить 6 городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей:

	A	B	C	D	E	F
A	∞	26	42	15	29	25
B	7	∞	16	1	30	25
C	20	13	∞	35	5	0
D	21	16	25	∞	18	18
E	12	46	27	48	∞	5
F	23	5	5	9	5	∞

Решение задачи

Для удобства изложения везде ниже в платежной матрице заменим имена городов (A, B, …, F) номерами соответствующих строк и столбцов (1, 2, …, 6).

Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r₁=15, r₂=1, r₃=0, r₄=16, r₅=5, r₆=5.

После их вычитания по строкам получим:

	1	2	3	4	5	6
1	∞	11	27	0	14	10
2	6	∞	15	0	29	24
3	20	13	∞	35	5	0
4	5	0	9	∞	2	2
5	7	41	22	43	∞	0
6	18	0	0	4	0	∞

Минимумы по столбцам: h₁=5, h₂=h₃=h₄=h₅=h₆.

После их вычитания по столбцам получим приведенную матрицу:

	1	2	3	4	5	6
1	∞	11	27	0	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

Найдем нижнюю границу φ(Z) = 15+1+0+16+5+5+5 = 47.

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, найдем степени Θ_ij нулевых элементов этой матрицы (суммы минимумов по строке и столбцу). Θ₁₄= 10 + 0,
Θ₂₄= 1 + 0, Θ₃₆= 5+0, Θ₄₁= 0 + 1, Θ₄₂= 0 + 0, Θ₅₆= 2 + 0, Θ₆₂= 0 + 0,
Θ₆₃= 0 + 9, Θ₆₅= 0 + 2. Наибольшая степень Θ₁₄= 10. Ветвление проводим по дуге (1, 4).

Нижняя граница для множества остается равной 47. Для всех маршрутов множества из города A мы не перемещаемся в город D. В матрице это обозначается выставлением в ячейку (1, 4) знака ∞. В этом случае выход из города A добавляет к оценке нижней границы по крайней мере наименьший элемент первой строки. φ () = 47 + 10.

В матрице, соответствующей полагаем c₁₄= ∞.

	1	2	3	4	5	6
1	∞	11	27	∞	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

После проведения процедуры приведения с r₁=10 получим новую нижнюю границу 57 + 10 = 67.

В матрице, соответствующей , вычеркиваем первую строку и четвертый столбец и положим c₄₁= ∞, чтобы предотвратить появления цикла 1→ 4 → 1. Получим новую платежную матрицу {c¹_ij}:

	1	2	3	5	6
2	1	∞	15	29	24
3	15	13	∞	5	0
4	∞	0	9	2	2
5	2	41	22	∞	0
6	13	0	0	0	∞

Для приведения надо вычесть минимум по первому столбцу: h₁=1. При этом нижняя граница станет равной 47+1 = 48. Сравнивая нижние границы
φ () = 67 и φ () = 48 < 67 выделяем подмножество маршрутов , которое с большей вероятностью содержит маршрут минимальной длины.

Рис. 1.4 Ветвление на первом шаге

Приведенная платежная матрица для

	1	2	3	5	6
2	0	∞	15	29	24
3	14	13	∞	5	0
4	∞	0	9	2	2
5	1	41	22	∞	0
6	12	0	0	0	∞

Далее продолжаем процесс ветвления. Найдем степени Θ_ij нулевых элементов этой матрицы Θ₂₁=16, Θ₃₆= 5, Θ₄₂= 2, Θ₅₆= 2, Θ₆₂= 0, Θ₆₃=9, Θ₆₅= 2. Наибольшая степень Θ₂₁. Затем множество разбивается дуге (2, 1) на два новых и .

В матрице для вычеркиваем строку 2 и столбец 1. дуги (1, 4) и (2, 1) образуют связный путь (2, 1, 4), положим c₄₂= ∞, чтобы предотвратить появления цикла 2→1→ 4 → 2.

	2	3	5	6
3	13	∞	5	0
4	∞	9	2	2
5	41	22	∞	0
6	0	0	0	∞

Для приведения надо вычесть минимум по строке 4: r₄=2. При этом нижняя граница станет равной 48+2 = 50.

Нижняя граница для , полученная как на предыдущем шаге ветвления, равна 48 + 16 = 64. Сравнивая нижние границы φ () = 64 и φ () = 50 < 64 выбираем для дальнейшего разбиения подмножество маршрутов .

Рис. 1.5 Ветвление на втором шаге
Приведенная платежная матрица для

	2	3	5	6
3	13	∞	5	0
4	∞	7	0	0
5	41	22	∞	0
6	0	0	0	∞

Степени Θ_ij нулевых элементов этой матрицы Θ₃₆= 5, Θ₄₅= 0, Θ₅₆= 22, Θ₆₂= 13, Θ₆₃=7, Θ₆₅= 0. Наибольшая степень Θ_56. Затем множество разбивается дуге (2, 1) на два новых и .

Нижняя граница для равна 50 + 22 = 72. В матрице для вычеркиваем строку 5 и столбец 6 и полагаем c₆₅= ∞. Получим матрицу:

	2	3	5
3	13	∞	5
4	∞	7	0
6	0	0	∞

Для приведения надо вычесть минимум по строке 3: r₃=5. При этом нижняя граница станет равной 50+5 = 55. Выбираем для дальнейшего разбиения подмножество маршрутов .

Рис. 1.6 Ветвление на третьем шаге
Приведенная платежная матрица для

	2	3	5
3	8	∞	0
4	∞	7	0
6	0	0	∞

Степени Θ_ij нулевых элементов этой матрицы Θ₃₅= 8, Θ₄₅= 7, Θ₆₂= 8, Θ₆₃=7. Выбираем Θ₃₅= 8. Разбиваем на и .

Нижняя граница для равна 55 + 8 = 64. В матрице для вычеркиваем строку 3 и столбец 5 и полагаем c₆₃= ∞. Получим

	2	3
4	∞	7
6	0	∞

Для приведения надо вычесть минимум по строке 4: r4=7. При этом нижняя граница станет равной 55+7 = 62. После приведения получим

	2	3
4	∞	0
6	0	∞

Из матрицы 2´2 получаем два перехода с нулевой длинной: (4, 3) и (6, 2).

Рис. 1.7 Ветвление на четвертом шаге

Рис. 1.8 Дерево ветвления с оценками
Полученный маршрутом коммивояжера z₀ = (1, 4, 3, 5, 6, 2, 1) или (A-D-C-E-F-B-A).

1.6 Практическое применение задачи коммивояжера

Кроме очевидного применения задачи коммивояжера на практике, существует ещё ряд задач, сводимых к решению задачи коммивояжера.
Задача о производстве красок
.

Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать одним процессором.. Будем считать также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке Поскольку производство циклическое, то краски надо производить в циклическом порядке p=(j₁,j₂,..,j_n,j₁). После окончания производства краски i и перед началом производства краски j надо отмыть оборудование от краски i. Для этого требуется время C[i,j]. Очевидно, что C[i,j] зависит как от i, так и от j, и что, вообще говоря,C[i,j]≠C[j,i]. При некотором выбранном порядке придется на цикл производства красок потратить время:

Где t_k- чистое время производства k-ой краски (не считая переналадок). Однако вторая сумма в правой части постоянна, поэтому полное время на цикл производства минимизируется вместе с общим временем на переналадку.

Таким образом, задача коммивояжера и задача о минимизации времени переналадки – это просто одна задача, только варианты ее описаны разными словами.
Задача о дыропробивном прессе.
Дыропробивной пресс производит большое число одинаковых панелей – металлических листов, в которых последовательно по одному пробиваются отверстия разной формы и величины. Схематически пресс можно представить в виде стола, двигающегося независимо по координатам x, y, и вращающегося над столом диска, по периметру которого расположены дыропробивные инструменты разной формы и величины. Каждый инструмент присутствует в одном экземпляре. Диск может вращаться одинаково в двух направлениях (координата вращения z). Имеется собственно пресс, который надавливает на подвешенный под него инструмент тогда, когда под инструмент подведена нужная точка листа.

Операция пробивки j-того отверстия характеризуется четверкой чисел (x_j,y_j,z_j,t_j),, где x_j,y_j- координаты нужного положения стола, z_j - координата нужного положения диска и t_j- время пробивки j-того отверстия.

Производство панелей носит циклический характер: в начале и конце обработки каждого листа стол должен находиться в положениях (x₀, y₀) диск в положении z₀причем в этом положении отверстие не пробивается. Это начальное состояние системы можно считать пробивкой фиктивного нулевого отверстия. С параметрами (x₀,y₀,z₀,0).

Чтобы пробить j-е отверстие непосредственно после i-того необходимо произвести следующие действия:

1.                  Переместить стол по оси x из положения x_i в положение x_j, затрачивая при этом время t⁽^x⁾(|x_i-x_j|)=t_i_,_j⁽^x⁾.

2.                  Проделать то же самое по оси y, затратив время t_i_,_j⁽^y⁾ .

3.                  Повернуть головку по кратчайшей из двух дуг из положения z_i в положение z_j, затратив время t_i_,_j⁽^z⁾ .

4.                  Пробить j-тое отверстие, затратив время t_j.

Конкретный вид функций t⁽^x⁾, t⁽^y⁾, t⁽^z⁾зависит от механических свойств пресса и достаточно громоздок. Явно выписывать эти функции нет необходимости

Действия 1-3 (переналадка с i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому

С[i,j] = max(t⁽^x⁾, t⁽^y⁾, t⁽^z⁾)

Теперь, как и в предыдущем случае, задача составления оптимальной программы для дыропробивного пресса сводится к задаче коммивояжера (здесь - симметричной).
2.
Практическая часть

Инвестор, располагающий суммой в 300 тысяч денежных единиц, может вложить свой капитал в акции автомобильного концерна А и строительного предприятия В. Чтобы уменьшить риск, акций А должно быть приобретено по крайней мере в два раза больше, чем акций В, причём последних можно купить не более чем на 100 тысяч денежных единиц. Дивиденды по акциям А составляют 8% в год, по акциям В – 10%. Какую максимальную прибыль можно получить в первый год?

Пусть цены на акции одинаковы для A и B и равны: ЦA = ЦB = 1 тыс.

Bukvasha