Проверяемый текст
Дмитриев Дмитрий Сергеевич. Обеспечение экономической устойчивости промышленного предприятия на основе оптимизации размещения производственных объектов (Диссертация 2010)
[стр. 80]

ему города и вернуться назад за минимальное время или с наименьшими затратами на проезд.
Другими словами, задача коммивояжера это поиск пути, связывающего два или более узла, с использованием критерия оптимальности.
Данная задача формулируется следующим образом.
Имеется граф, узлы которого представляют собой точки (города), которые должен посетить коммивояжер.
Ребра графа образуют пути, связывающего два или более узла.
Требуется найти путь, который минимизирует (или максимизирует)
некоторый критерий оптимальности (время, стоимость переезда, совокупный критерий и т.д.).
При этом на допустимые маршруты могут быть наложены некоторые ограничения, например, запрет возвращения к уже пройденному узлу
[110, с.
145].
Задача коммивояжера считается одной из самых сложных в математическом программировании, поскольку вычислительные затраты
нелинейно возрастают с ростом числа узлов, которые должны быть включены в маршрут.
Чтобы привести задачу к научному виду, введём некоторые термины.
Города обозначены числами jeT=(l,2,3..n).
Тур коммивояжера может быть описан циклической перестановкой
t=(ji,J2,..,jnji), причём все ji...j n — разные номера; повторяющийся в начале и в конце j b показывает, что перестановка зациклена.
Расстояния между парами вершин Су образуют матрицу С.
Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал:
L = L{t) = ±CjKj^.
(34) Относительно математизированной формулировки задачи коммивояжера уместно сделать два замечания.
Во-первых, в постановке Су означали расстояния, поэтому они должны быть: неотрицательными, т.е.
для
BcexjeT: Су>0;С0=«> (последнее равенство означает запрет на петли в туре); 80 (35)
[стр. 95]

Итак, в настоящее время широкое распространение получили методы линейного и математического обоснования высоким программирования, размещения В применяемые оборудования свою для на экономического предприятии с стратегии уровнем формализации.
очередь, оптимизация планировки оборудования симплексным методом и методом полного перебора снижает транспортные расходы, и длительность прямоточность себестоимость производственного производственного цикла, обеспечивает процесса, а ритмичность следовательно, снижает продукции и увеличивает прибыль.
Более подробно рассмотрим классическую задачу анализа данных и математического программирования.
2.3.
Оптимизационные модели в производственной деятельности промышленного предприятия Одной из знаменитых задач теории о гамильтоновых циклах в графе является задача коммивояжера.
Она была поставлена в 1934 году.
Задача коммивояжера это классическая задача анализа данных и математического программирования, которая заключается в определении оптимального маршрута для коммивояжера, который должен объехать все порученные ему города и вернуться назад за минимальное время или с наименьшими затратами на проезд.
Другими словами, задача коммивояжера это поиск пути, связывающего два или более узла, с использованием критерия оптимальности.
Данная задача формулируется следующим образом.
Имеется граф, узлы которого представляют собой точки (города), которые должен посетить коммивояжер.
Ребра графа образуют пути, связывающего два или более узла.
Требуется найти путь, который минимизирует (или максимизирует)
95

[стр.,96]

некоторый критерий оптимальности (время, стоимость переезда, совокупный критерий и т.д.).
При этом на допустимые маршруты могут быть наложены некоторые ограничения, например, запрет возвращения к уже пройденному узлу
[75, с.
145;.
Задача коммивояжера считается одной из самых сложных в математическом программировании, поскольку вычислительные затраты
быть нелинейно возрастают с ростом числа узлов, которые должны включены в маршрут.
Чтобы привести задачу к научному виду, введём некоторые термины.
Города обозначены числами jeT=(l,2,3..n).
Тур коммивояжера может быть описан циклической перестановкой
t=(jbJ2,..,jn,ji), причём все j i .
.
.
j n разные номера; повторяющийся в начале и в конце j
i, показывает, что перестановка зациклена.
Расстояния между парами вершин Су образуют матрицу С.
Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал:
i = i(') = £ c , , „ (39) Относительно математизированной формулировки задачи коммивояжера уместно сделать два замечания.
Во-первых, в постановке Су означали расстояния, поэтому они должны быть: неотрицательными, т.е.
для
всех j е Т: С, > О; С„ = « (40) (последнее равенство означает запрет на петли в туре); симметричными, т.е.
для всех 1, j : С,=С,; (41) 96

[Back]