48382 (Проектирование модели для определения времени простоя станков на машиностроительном предприятии), страница 5

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

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

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

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

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

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

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

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

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

3 АЛГОРИТМ МЕТОДА ВЕТВЕЙ И ГРАНИЦ

Запишем алгоритм:

1. Положим k == 1.

2. Осуществим приведение матрицы С по строкам и столбцам образуя приведенную матрицу С^k.

3. Вычислим сумму приводящих констант h^(k)—это оценка для множества X, обозначим ее .

4. Выберем претендентов для включении и множество Y, т. е. все те (i,j), i=1. 2, ..., j==1, 2, ..., , для которых .

5. Для выделенных претендентов на включение в Y подсчитаем:

.

6. Выберем по всем i,j, у которых . Пара (k,l) включается в множество Y и является запретной для множества .

7. Подсчитаем оценку для множества Y, она равна ранее произведенным затратам для множества Х и , т. е.

.

8. Так как из каждого города можно выезжать только один раз, то естественно k-ю строку из дальнейшего рассмотрения исключить Так как в каждый город можно въезжать только один раз, то l-й столбец исключается.

Чтобы избежать образования замкнутых подциклов, естественно запретить переезд из l в k, т. е. клетку (l,k).

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

Итак, момент образования матрицы 2х2 является особым, поэтому в п.9 проверяем, имеет ли полученная усеченная матрица размерность 2х2. Если «да», то переходим к п. 11. Если «нет», то к п. 10.

10. Является ли полученная матрица приведенной? Если «да», то оценка для множества Y равна оценке того множества, из которого Y получено, т. е. . Если «нет», то осуществляется приведение только что полученной матрицы и подсчитывается , после чего

,

и переходим к п. 4.

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

Блок-схема метода приведена на рисунке 3. Некоторые замечания: блок «матрица 2х2» определяет момент получения замыкающих пар городов для образования замкнутого маршрута; к блоку «восстановление» осуществляется переход и том случае, когда перспективным для дальнейшего ветвления оказалось множество, принадлежащее к совокупности . В этом случае процесс выбора претендентов для дальнейшего ветвления требует восстановления исходной матрицы С. подсчета затрат q, необходимых для выполнение ранее построенного маршрута для множества Х, из которого построено, т. е.

.

После этого необходимо вычеркнуть строки и столбцы для пар, входящих в Х (аналогично п. 8), и привести полученную матрицу для выбора претендентов для ветвления.

4 РЕШЕНИЕ ПОСТАВЛЕННОЙ ЗАДАЧИ

4.1 Условие задачи

Задача

Определить оптимальную последовательность запуска деталей в производство, если задана матрица затрат на переналадку оборудования:

Сделать анализ решенной задачи.

ВЫВОДЫ

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

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

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

Также прилагается программана решающая задачу о коммивояжере методом ветвей и границ. Для разработки данной программы была использованя среда разработки Delphi версии 6.0.

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

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

ЛИТЕРАТУРА:

1 Балашевич В.А., Алгоритмизация математических методов планирования и управления. - Минск: Вышэйшая школа,1979.-286с

2 Дегтярев Ю.И., Исследование операций.- Москва: Высшая школа,1986.-270с.

3 Ляшенко И.Н. Линейное и нелинейное программирование – Киев: Вища школа,1975.-370с.

ПРИЛОЖЕНИЕ А

(обязательное)

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

Схема программы

Описание программы

Инструкция пользователю

ПРИЛОЖЕНИЕ Б

(обязательное)

Входная информация

ПРИЛОЖЕНИЕ В

(обязательное)

Выходная информация