Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Задача о коммивояжере - файл Курсовая коммивояжер чистовик.doc


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

Доступные файлы (1):

Курсовая коммивояжер чистовик.doc493kb.07.11.2008 20:20скачать

Курсовая коммивояжер чистовик.doc

  1   2
Содержание

Введение 2

1 Математические основы решение задачи коммивояжера 4

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

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

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

1.4 Условия существования гамильтонова контура 8

1.5 Метод ветвей и границ 10

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

2 Разработка и описание алгоритма работы программы 16

2.1 Содержательная постановка задачи 16

2.2 Построение математической модели задачи 17

2.3 Решение задачи вручную 17

2.4 Описание работы программы 20

2.5 Текст программы 22

3 Заключение 31

4 Литература 32

5 Приложение А (обязательное) 33

ВВЕДЕНИЕ

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

^ Математическое программирование — область мате­матики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограниче­ниями, т. е. задач на экстремум функции многих пере­менных с ограничениями на область изменения этих переменных.

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

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

Пусть задано некоторое непустое множество Х множество, состоящее из пар элементов множества X. Пары во множестве могут повторяться, и также могут повторяться элементы в парах. Множества Х задают граф 0=(Х, Y).

Элементы множества называют вершинами графа, элементы множества V — ребрами графа.

Если пары во множестве V повторяются, то граф С называют псевдографом или графом с кратными ребрами.

Если элементы в парах множества не упорядочены, то граф С называют неориентированным графом. Если они упорядочены, то граф О является ориентированным графом или орграфом, а эле­менты множества V называют дугами.

Графически граф задается в виде точек и линий, их соединяющих.

Введем ряд основных понятий для неориентированного графа. Ребро, начало и конец которого совпадают, называется петлей. Вершины называются смежными или соседними, если суще­ствует ребро, их соединяющее.

Если вершина является началом или концом ребра, то верши­на и ребро называются инцидентными.

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

Маршрутом в графе называется последовательность вершин и ребер, в которой конец предыдущего ребра совпадает с началом следующего), это не относится к первому и последнему ребру). Число ребер в маршруте определяет его длину.

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

Простой называется цепь, в которой все вершины попарно различны.

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

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

Расстоянием между вершинами связного графа называется длина самой короткой цепи, соединяющей вершины.

Диаметром графа называется максимальное расстояние между его вершинами.

Деревом называется связный граф без циклов

Граф называется регулярным степени i, если все его вершины имеют степень i.

Граф называется полным, если любые две его вершины соеди­нены ребром. Лесом называется граф без циклов, т.е. совокупность деревьев.

Регулярный граф, все вершины которого имеют степень 1, на­зывается паросочетанием. Граф называется двудольным, если мно­жество его вершин X может быть разделено на два непересекаю­щихся подмножества таким образом, что каждое ребро графа соединяет вершины из двух разных подмножеств.

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

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

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

Маршрут в ориентированном графе часто называют контуром, а цепь — путем.

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

Классическая постановка задачи о коммивояжере выглядит следующим образом:

Имеется N городов, выезжая из исходного города А1, коммивояжер должен побывать во всех городах по 1 разу и вернуться в город А1. Задача заключается в определении последовательности объезда городов, при которой коммивояжеру требуется минимизировать некоторый критерий эффективности: стоимость проезда, время пути, суммарное расстояние и т.д.

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

Чтобы привести задачу к научному виду, введём некоторые термины. Итак, города перенумерованы числами jТ=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j1,j2,..,jn,j1), причём все j1..jn – разные номера; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Расстояния между парами вершин Сij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал



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

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

Сij0; Cjj=∞

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

Сij= Сji.

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

Сij+ СjkCik

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

Задача коммивояжера может быть сформулирована как задача на графе в следующей постановке: построить граф G(X, A), вершины которого соответствуют городам в зоне коммивояжера, а дуги отображают коммуникации, соединяющие пары городов. Пусть длина a(х, у) > 0 каждой дуги (х, у) є А равна расстоя­нию, стоимости или времени. Контур, включающий каждую вершину графа G хотя бы один раз, называется маршрутом коммивояжера. Контур, включающий каждую вершину графа G ровно один раз, называется гамильтоновым контуром (по имени ирландского математика Вильяма Роуана Гамильтона, ко­торый в 1859 г. первым начал изучение этих задач).

Города – это вершины графа.

Дороги между городами – это ориентированные ребра графа.

Длина соответствующей дороги – это вес ребра.

Граф должен быть полным, т.е. в нем имеются все возможные ребра. Если граф не является полным, то его можно дополнить недостающими ребрами с весом =

Путь, который требуется найти, - это ориентированный оставный, простой цикл, минимального веса в графе. Такие циклы называются гамильтоновыми.

Оставным циклом называется такой цикл, который проходит через все вершины. Вес цикла – это сумма веса всех ребер.

^ 1.4 Условия существования гамильтонова контура

Введем ряд определений, которые впоследствии нам понадобятся. Граф называется сильно связным, если в нем для любых двух вершин х и у существует путь от х к у. Подмножество вершин xt некоторого графа называется сильно связным, если для любых пар вершин х xt и у xt существует путь из х в у и не является подмножеством никакого другого множества вер­шин, обладающего такими же свойствами.

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

Если граф не является сильно связным, то на нем отсутствует гамильтонов контур. Это следует из того, что гамильтонов контур включает путь между каждой парой вершин графа. Таким образом, необходимым условием существования гамильтонова контура является наличие в графе сильной связности. Так как, петлей является любая дуга, начальная и конечная вершины которой совпадают, т. е. дуга вида (х, х). Гамильтонов контур не может содержать петлю, и, следовательно, на существование гамильтонова контура в графе G не влияет добавление или ис­ключение петель. Если две вершины, скажем х и у, соединены более чем одной дугой (х, y)1 (х, y)2... одинакового направления, то исключение всех дуг, кроме одной дуги с наименьшей длиной, не влияет ни на существование гамильтонова контура, ни на длину оптимального гамильтонова контура графа (если он существует). Поэтому в графе G отсутствуют петли и что в нем имеется не более одной дуги от х к у для любых х и у.

Пусть через D-(x) обозначено множество всех таких вершин графа G = (X, А), что (х, у) А, т. е. множество всех вершин, «падающих на» вершину х. Пусть через D+(x) обозначено множест­во всех таких вершин у, что (х, у) А, т. е. множество всех вершин, «падающих из» вершины х.

Вершины, принадлежащие множествам D-(x) и D+(x), назы­ваются соответственно предшественниками и преемниками вер­шины х. Пусть D(x) = D-(x)٭ UD+(x). Как и ранее, пусть d-(x) = |D-(x), d+(x) = |D+(x)|и d(x) = |D(x)|. И наконец, пусть n — число вершин в графе G. Имея в виду эти определения сформулируем следующую весьма общую теорему Гуйя-Ури.

^ ТЕОРЕМА 1. Если граф G(X,A) удовлетворяет условиям:

I) граф G сильно связный,

II) d(x) ≥n для всех х X ,

то он содержит гамильтонов контур.

Доказательство. Доказательство проводится методом индукции по числу n вершин в графе G.

Справедливость теоремы для n = 2 и n = 3 очевидна. Теорема справедлива для всех графов с числом вершин меньше n (n ≥3). Пусть G — произвольный граф с n вершинами, удовлетворяющий условиям (I) и (II). Пусть через С обозначен простой контур графе G с наибольшим возможным числом дуг. Пусть x1, x2, ... xm — последовательность, в которой коммивояжер посещает вершины графа G, входящие в контур С. Если m = n, то теорема справедлива. В противном случае m<n и С не является гамильтоновым контуром.

Достаточные условия существования гамильтонова цикла на неориентированном графе сформулированы Квателем. Пусть, через n обозначено число вершин в графе. Прону­меруем вершины так, чтобы выполнялось соотношение d(х1)≤d(хi)≤…≤d(хn).

^ ТЕОРЕМА 2. Граф G = (X, Е) содержит гамильтонов цикл, если n≥3 и d(хk)≤k≤0,5n=>d(хn-k)≥n-k

Доказательство. Предположим, что граф G удовлетворяет условиям теоремы, но не содержит гамильтонова цикла. Рас­смотрим произвольное ребро (xi, хj), которое не принадлежит графу. Если добавление этого ребра не приводит к образованию гамильтонова цикла, то включим его в граф G. Повторим эту про­цедуру до тех пор, пока ни одно из ребер нельзя будет дополни­тельно включить в граф G. Заметим, что после добавления каждого нового ребра в граф G условие остается допустимым, так как его включение в граф не понижает степени любой из вершин. Назовем граф, получаемый в результате добавления ребер, графом G* = (X, Е*). В дальнейшем мы используем этот граф G* для того, чтобы показать наличие противоречия при принятом предположении. Пусть u и v — такие произвольные несмежные вершины графа, что d(u) + d(v) имеет максимальное значение. Предположим без нарушения общности, что d(u) ≤ d(v). Пусть G — простая цепь наибольшей длины, соединяющая вершины u и v. Поскольку в граф G* нельзя дополнительно включить ни одной дуги без образования гамильтонова цикла, то G включает все вершины в множестве X. Пусть последовательность u= u1, u2,…, un-1, un = v определяет порядок, в котором вершины обходятся в цепи C.

Пусть через S обозначено множество всех таких вершин ui, что вершина ui+l смежна с вершиной u. Через Т обозначим множество всех вершин, смежных с вер­шиной v. Отметим, что ни одна из вершин yj не может одновре­менно принадлежать S и Т, иначе цикл uj, uj-1,…, u1, uj+1,uj+2,…, un, uj был бы гамильтоновым циклом. Кроме того, S U Т ={u1, u2, …, un-1}. Поэтому d(u) + d(v) = |S| +|T|≤n. Сле­довательно, d(u) ≤ 1/2n. Поскольку ни одна из вершин uj не мо­жет одновременно входить в S и Т, то uj и v не смежны, если uj S. Из максимальных d(u) + d(v) следует, что d(uj) ≤d(u).

Таким образом, существует по крайней мере |S| вершин, степень которых не превышает степени вершины u. Примем k = d(u). Значит, d(xk) ≤ k. Из условия (4) следует, что d(xn-k)≥n —k. Таким образом, должно быть по крайней мере k + 1 вершин, степень которых не меньше чем (n —k). Так как d(u) = k, то вершина u не смежна ни с одной из этих вершин. Значит, сущест­вует некоторая вершина w, которая не смежна с u и при этом d(w)≥n—k. Отсюда d(u) + d(w)>d(u) + d(v), что противо­речит принятому предположению. Следовательно, граф G* должен содержать гамильтонов цикл. Теорема доказана .

^ 1.5 Метод ветвей и границ

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

Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной. Нам будет удобнее трактовать Сij как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру 5 долларов. Это означает, что любой тур подешевеет на 5 долларов, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j-го столбца матрицы С на 5. Если бы мэр хотел спровадить коммивояжеров из j-го города и установил награду за выезд в размере 10 долларов, это можно было бы выразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма. Вычитая любую константу из всех элементов любой строки или столбца матрицы С, мы оставляем минимальный тур минимальным. Для алгоритма нам будет удобно получить побольше нулей в матрице С, не получая там, однако, отрицательных чисел. Для этого мы вычтем из каждой строки ее минимальный элемент (это называется приведением по строкам, а затем вычтем из каждого столбца матрицы, приведенной по строкам, его минимальный элемент, получив матрицу, элементов матрицы С. Подчеркивание элемента означает, что в туре из i-го элемента идут именно в j-тый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. Стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором.

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

Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать «по нулю» из города 1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены правее и выше нуля (оценки нуля, равные нулю, не ставились).

Выберем максимальную из этих оценок (в примере есть несколько оценок, равных единице, выберем первую из них, в клетке (1,2)).

Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса – включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно сказать, что придется приплатить еще 1, так что туры этого класса стоят 35 или больше.

Что касается первого класса, то в нем надо рассмотреть матрицу с вычеркнутой первой строкой и вторым столбцом.

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

Кружки представляют классы: верхний кружок – класс всех туров; нижний левый – класс всех туров, включающих ребро (1,2); нижний правый – класс всех туров, не включающих ребро (1,2). Числа над кружками – оценки снизу.

Продолжим ветвление в положительную сторону: влево - вниз. Для этого оценим нули в уменьшенной матрице C[1,2]. Максимальная оценка в клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины есть 35+3=38. Для оценки левой нижней вершины нужно вычеркнуть из матрицы C[1,2] еще строку 3 и столбец 1, получив матрицу C[(1,2),(3,1)] В эту матрицу нужно поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е. [3,1,2], и нужно запретить преждевременное замыкание (2,3).

Оцениваем теперь нули в приведенной матрице C[(1,2),(3,1)] нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6). Эта матрица неприводима. Следовательно, оценка положительного варианта не увеличивается.

Оценивая нули в матрице, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу.

В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура [3,1,2,6,5] и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1→2→6→5→4→3→1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.

Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С[Not(1,2)], т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.

Для получения оценки положительного варианта исключаем из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием.


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

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

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



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

Таким образом, задача коммивояжера и задача о минимизации времени переналадки – это просто одна задача, только варианты ее описаны разными словами.

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

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

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

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

1. Переместить стол по оси x из положения xi в положение xj, затрачивая при этом время t(x)(|xi-xj|)=ti,j(x)

  1. Проделать то же самое по оси y, затратив время ti,j(y)

  2. Повернуть головку по кратчайшей из двух дуг из положения zi в положение zj, затратив время ti,j(z) .

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

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

Действия 1-3 (переналадка с i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому С[i,j] = max(t(x), t(y), t(z))

Теперь, как и в предыдущем случае, задача составления оптимальной программы для дыропробивного пресса сводится к задаче коммивояжера (здесь - симметричной).
^ 2 РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

2.1 Содержательная постановка задачи

На металлообрабатывающем оборудовании необходимо обработать шесть партий деталей. Переход на обработку новой партии деталей требует переналадки оборудования. Время переналадки оборудования (мин) при переходе от обработки i-й (i=1,6) партии деталей к обработке j-й (j=1,6) партии деталей представлено матрицей (табл.1).

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

Таблица 1

i

j

1

2

3

4

5

6

1

0

20

25

30

15

10

2

20

0

30

15

20

18

3

30

25

0

20

40

30

4

25

20

20

0

30

15

5

35

25

30

24

0

20

6

15

20

30

20

18

0

Примечание:

При решение вручную методом ветвей и границ необходимо заменить aii=0 (i=1,6)


^ 2.2 Построение математической модели задачи

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

Z=0x11+20x12+25x13+30x14+15x12+10x16+20x21+0x22+30x23+15x24+20x25+18x26+30x31+25x32+0x33+20x34+40x35+30x36+25x41+20x42+20x43+0x44+30x45+15x46+35x51+

+25x52+30x53+24x54+0x55+20x56+15x61+20x62+30x63+20x64+18x65+0x66min

Ограничения имеют вид:

x11+x12+x13+x14+x12+x16=1,

x21+x22+x23+x24+x25+x26=1,

x31+x32+x33+x34+x35+x36=1,

x41+x42+x43+x44+x45+x46=1,

x51+x52+x53+x54+x55+x56=1,

x11+x21+x31+x41+x51+x61=1,

x12+x22+x32+x42+x52+x62=1,

x13+x23+x33+x43+x53+x63=1,

x14+x24+x34+x44+x54+x64=1,

x15+x25+x35+x45+x55+x65=1,

x16+x26+x36+x46+x56+x66=1,

U2-U3+5*x234,

U2-U4+5*x244,

U2-U5+5*x254,

U2-U6+5*x264,

U3-U4+5*x344,

U3-U5+5*x354,

U3-U6+5*x364,

U4-U5+5*x454,

U4-U6+5*x464,

U5-U6+5*x564,

U6-U2+5*x624,

U6-U3+5*x634,

U6-U4+5*x644,

U6-U5+5*x654.

^ 2.3 Решение задачи вручную

Таблица 2




1

2

3

4

5

6

Ai

1



20

25

30

15

10

10

2

20



30

15

20

18

15

3

30

25



20

40

30

20

4

25

20

20



30

15

15

5

35

25

30

24



20

20

6

15

20

30

20

18



15


Таблица 3




1

2

3

4

5

6

1



10

15

20

5

0

2

5



15

0

5

3

3

10

5



0

20

10

4

10

5

5



15

0

5

15

5

10

4



0

6

0

5

15

5

3



Bj

0

5

5

0

3

0


Таблица 4




1

2

3

4

5

6

(R)=10+15+20++15+20+

15+5+5+3=

108

1



5

10

20

2

0(2)

2

5



10

0(2)

2

3

3

10

0(0)



0(0)

17

10

4

10

0(0)

0(5)



12

0(0)

5

15

0(0)

5

4



0(0)

6

0(5)

0(0)

10

5

0(2)




Таблица 5




1

2

3

4

5

6

Ai

()=5+

108

=113

1



5

10

20

2

0

0

2

5



10

0

2

3

0

3

10

0



0

17

10

0

4

10

0

0



12

0

0

5

15

0

5

4



0

0

6



0

10

5

0



0

Bj

5

0

0

0

0

0





Таблица 6




1

2

3

4

5

6

Ai

1



5

10

20

2



2

2

5



10

0

2

3

0

3

10

0



0

17

10

0

4

10

0

0



12

0

0

5

15

0

5

4



0

0

6



0

10

5

0



0

Bj

5

0

0

0

0

0





Таблица 7




1

2

3

4

5

6

(6,1)=2+5+108=115

1



3

8

18

0(5)



2

5



10

0(2)

2

3

3

10

0(0)



0(0)

17

10

4

10

0(0)

0(5)



12

0(0)

5

15

0(0)

5

4



0(0)

6

0(5)

0(0)

10

5

0(0)




Таблица 8




2

3

4

5

6

Ai

1

3

8

18





3

2



10

0

2

3

0

3

0



0

17

10

0

4

0

0



12

0

0

5

0

5

4





0


Таблица 9




2

3

4

5

6

()=110+2+3=115

1

3

8

18





2



10

0

2

3

3

0



0

17

10

4

0

0



12

0

5

0

5

4





Bj

0

0

0

2

0


Таблица 10




2

3

4

6

Ai

(1,5)=110

2



10

0(3)

3

0

3

0(0)



0(0)

10

0

4

0(0)

0(5)



0(0)

0

5

0(5)

5

4

0(0)

0

Bj

0

0

0

0





Таблица 11




2

3

4

6

Ai

()=110+4=

114

2



10

0

3

0

3

0



0

10

0

4

0

0



0

0

5



5

4



4

Bj

0

0

0

0





Таблица 12




2

3

4

6

Ai

(5,2)=110

2



10

0(3)

3

0

3

0(0)



0(0)

10

0

4

0(0)

0(10)



0(3)

0

5

0(4)

5

4



0

Bj

0

0

0

0






Таблица 13




3

4

6

Ai

2

5

0

3

0

3



0

10

0

4





0

0

Bj

5

0

0





Таблица 14




3

4

6

()=110+5=115

2

0(0)

0(0)

3

3



0(10)

10

4





0(3)


Таблица 15




3

4

6

Ai

2

10

0

3

0

3





5

5

4

0



0

0

Bj

0

0

0





Таблица 16




3

4

6

(4,3)=110+5= 115

2

10

0(3)

3

3





0(3)

4

0



0


Таблица 17




4

6

Ai

2



3

3

3



0

0


Таблица 18




4

6

2



0

3



0


Таким образом, получили такую последовательность запуска партий деталей: 1-5-3-2-4-6-1 и минимальное время на переналадку оборудования Tmin=115


^ 2.4 Описание работы программы
  1   2



Скачать файл (83.3 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации