Курсовая работа: Проектирование модели для определения времени простоя станков на машиностроительном предприятии

Комбинаторика – раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.

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

Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем (диссертация “Комбинаторное искусство”), Я. Бернулли (работа “Искусство предположений”), Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейб-ница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало одному из основных методов перечисления комбинаторных конфигураций – методу производящих функций.

Возвращение интереса к комбинаторному анализу относится к 50-м годам ХХ в. в связи с бурным развитием кибернетики и дискретной математики и широким использованием электронно-вычислительной техники. В этот период активизировался интерес к классическим комбинаторным задачам.

Классические комбинаторные задачи – это задачи выбора и расположения элементов конечного множества, имеющие в качестве исходной некоторую формулировку развлекательного содержания типа головоломок.

В 1859 г. У. Гамильтон придумал игру “Кругосветное путешествие”, состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, изображенного на рис. 1, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами .

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

Задача коммивояжера (в дальнейшем сокращённо - ЗК) является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы.

Постановка задачи следующая.

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

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

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

Сij ³0; Cjj =∞

(2)

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

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

Сij = Сji .

((3)

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

Сij + Сjk ³Cik

((4)

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

Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры 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 . Найти гамильтонов цикл минимальной длины.

В несимметричной ЗК вместо “цикл” надо говорить “контур”, а вместо “ребра” - “дуги” или “стрелки”.

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

Жадный алгоритм

Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. “Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

Рисунок 3

Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится в стратегию “иди в ближайший (в который еще не входил) город”. Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рисунке 3, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди вы ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

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

Как видим, жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно, что полученный им тур хуже минимального, положим, в 1000 раз? Мы докажем, что этого доказать нельзя, причем не только для жадного алгоритма, а для алгоритмов гораздо более мощных. Но сначала нужно договориться, как оценивать погрешность неточных алгоритмов, для определенности, в задаче минимизации. Пусть f_B - настоящий минимум, а f_A - тот квазиминимум, который получен по алгоритму. Ясно, что f_A /f_B ≥1, но это – тривиальное утверждение, что может быть погрешность. Чтобы оценить её, нужно зажать отношение оценкой сверху:

fA /fB ≥1+ nε,

(5)

где, как обычно в высшей математике, ε≥0, но, против обычая, может быть очень большим. Величина ε и будет служить мерой погрешности. Если алгоритм минимизации будет удовлетворять неравенству (5), мы будем говорить, что он имеет погрешность ε.

Предположим теперь, что имеется алгоритм А решения ЗК, погрешность которого нужно оценить. Возьмем произвольный граф G (V,E) и по нему составим входную матрицу ЗК: