КУРСОВОЙПРОЕКТ
по предмету«Моделирование производственных и экономических процессов»
студента группы1ПМ-03
ЛитюкаАлександра Сергеевича
код 2372
2006
Министерствообразования и науки Украины
Восточноукраинскийнациональный университет
имениВладимира Даля
Колледж
Специальность: «Прикладная математика»
ПРОЕКТИРОВАНИЕ МОДЕЛИ ДЛЯ ОПРЕДЕЛЕНТЯ ВРЕМЕНИ ПРОСТОЯСТАНКОВ НА МАШИНОСТРОИТЕЛЬНОМ ПРЕДПРИЯТИИПояснительная запискаКП.5.080202.МП.15.02.ПЗ
Руководитель
____________Латкова А.А.
15.12.06.
Выполнил студент
группы1ПМ-03
____________Литюк А.С.
11.12.06.
2006
15.02Министерство обраования и науки Украины
Восточноукраинскийнауциональный университет
имениВладимира Даля
Колледж
ЗАДАНИЕ
Длякурсового проекта
по предмету “Моделированиепроизводственных и экономических процессов”
Студента специальности 5.080202 группы1ПМ-03___________________Литюку АлександруСергеевичу__________________________________
Темазадания: «Проектирование модели для определения времени простоя станков намашиностроительном предприятии»_______________________
__________________________________________________________________________________________________________________
Литература
1.ЛяшенкоИ.Н.Линейное и нелинейное программирование.– Киев: Вища школа ,1975.-370с _________________________________________________
2.ДегтяревЮ.И. Исследование операций –Москва: Вища школа ,1986_________
3.БалашевичВ.А._____________________________________________
_________________________________________________________
Курсовой проект на указанную тему выполняется в следующемобьеме _________________________________________________________
1 Пояснительная записка
Введение
1 Постановка задачи о переналадке станков как задачидинамического программирования.
2 Методы решения задачи. Метод ветвей и границ.
3Алгоритм метода ветвей и границ. Схема алгоритма
4Решение поставленной задачи
4.1Условие задачи
4.2Решение задачи вручную
5Выводы
Литература
Приложения (текст программы, схема программы, расшифровкапеременных, описание программы, инструкция пользователю, входная и выходнаяинформация)
2 Расчетная часть
Задача
Определить оптимальнуюпоследовательность запуска деталей в производство, если задана матрица затратна переналадку оборудования:№ 1 2 3 4 5 6 7 1 ∞ 21 11 18 8 15 9 2 19 ∞ 8 3 7 15 25 3 13 18 ∞ 16 1 13 20 4 16 5 14 ∞ 26 14 17 5 17 9 5 6 ∞ 12 19 6 19 7 21 13 24 ∞ 21 7 10 29 25 11 14 17 ∞
Сделать анализ решенной задачи.
3 Графическая часть
Лист1 Схема алгоритмаметода ветвей и границ_____________________
_________________________________________________________
Лист2 Схемапрограммы_______________________________________
Датавыдачи «_1_»_____09______2006г.
Срококончания «15»______11____2006г.
Зав.отделением ______________
Руководительпроекта ______________
УТВЕРЖДАЮ
Зав. отделением
……………………………….
«__»_________200_г.
График
работы над курсовым проектом
студента группы 1ПМ-03 Литюка А.С.
№№
п-п Разделы, графы проекта Характер работы Объём работы Срок выполения Отметка руководителя о выполнении 1 Введение Опис. часть 5 1.09-5.09 2 Постановка задачи Опис. часть 5 6.09-17.09 3 Методы решения задачи Опис. часть 9 18.09-20.09 4 Алгоритм метода ветвей и границ Опис. часть 9 21.09-22.09 5 Схема алгоритма Граф. часть 4 23.09-24.09 6 Решение поставленной задачи Расчет. часть 13 25.09-30.09 7 Составление программы Расч. на ЭВМ 20 1.10-15.10 8 Отладка программы Расч. на ЭВМ 17 16.10-19.10 9 Инструкция пользователю Опис. часть 2 20.10-24.10 10 Граф-кая часть А1 Граф. часть 5 25.10-26.10 11 Оформл. Тит.л. и л. содержания Графич. часть 4 27.10-1.11 12 Выводы Опис. часть 2 2.11-6.11 13 Оформление курсового проекта 5 7.11-8.11
Срок сдачи проекта на проверку __9.11-15.11________
День защиты проекта_____16.11-24.11_____________
Руководитель______________________________
Содержание
Введение
1Постановка задачи о переналадке станков как задачи линейного программирования
2 Методырешения задачи. Метод ветвей и границ
3 Алгоритмметода ветвей и границ. Схема алгоритма
4 Решениепоставленной задачи
4.1 Условиезадачи
4.2 Решениезадачи вручную
5 Выводы
Литература
Приложение А Текстпрограммы
Схемаалгоритма
Описаниепрограммы
Инструкцияпользоватедлю
Приложение Б Входнаяинформация
Выходнаяинформация
ПриложениеВ Графическая часть (1А1)
ВВЕДЕНИЕ
Наиболее распространенная формаорганизации основного процесса производства-переменно-поточное производство,отличительная особенность которого заключается в периодической перенастройке(переналадке) всего процесса в связи с переходом на другой вид изделий.
Переход с изготовления изделий одноговида на другой (с одной серии на другую) сопровождается потерями идополнительными издержками производства, к числу которых относятся потери отпростоев оборудования, потери от брака в начальный период перехода, расходы поуправлению производством.
По существу на любом предприятии каждаяиз поточных линий время от времени вынуждена перестраиваться с выработкиизделий одного вида на другой. Каждый переход, независимо от того, после какойпо размеру серии он происходит, вызывает потери времени и дополнительныерасходы. Причем суммарные потери, связанные с заданной серией переходов,зависят от последовательности переходов. Если бы этой зависимости не было, тосуммарные потери равнялись бы во всех последовательностях одному и тому жечислу, и не возникло бы проблемы установления оптимальной последовательностизапуска деталей.
1 ПОСТАНОВКА ЗАДАЧИ О ПЕРЕНАЛАДКЕ СТАНКОВ КАК ЗАДАЧИ ДИНАМИЧЕСКОГОПРОГРАММИРОВАНИЯ
Наибольшеераспространение в решении задачи календарного планирования обработки т деталейна п станках имеют приближенные методы, основанные главным образом наиспользовании различных правил предпочтения. Лишь в последнее время сталипоявляться методы, гарантирующие сходимость к точному решению за конечное числошагов. Рассмотрим один из таких методов, базирующийся на идеях метода ветвей играниц.
Пусть на участке споследовательным движением производства обрабатываются детали с одинаковымитехнологическими маршрутами. Передача деталей со станка на станокосуществляется транспортными партиями, совпадающими с партиями обработки.Задана матрица />, где />—продолжительностьобработки партии деталей i-гонаименования на j-м станке. В одини тот же момент на станке обрабатывается только одна деталь. Требуется найтикалендарное расписание работы участка в виде матриц />и/> , элементы которыхпоказывают соответственно время начала и окончания обработки каждой детали накаждом станке. Из всех допустимых расписаний необходимо выбрать обеспечивающеенаименьшую совокупную длительность производственного цикла обработки всехдеталей.
При описании алгоритмарешения будет использовано понятие «конфликтующие детали». Его сущность можно пояснитьна примере. Пусть для матрицы продолжительностей обработки
/>
составлено расписание окончания обработки
/>
Из анализа матрицы С видно, что длякаждой отдельной детали расписание се обработки является наилучшим, так какобработка планируется таким образом, чтобы детали не пролеживали. В то же времяэто расписание недопустимо, так как имеются отрезки времени, когда на одномстанке должны обрабатываться обе детали одновременно — детали «конфликтуют».Действительно, на первом станке предусмотрена обработка одной детали винтервале (0—3), а другой — в интервале (0—6), на втором станке первая детальобрабатывается в интервале (3—8). а вторая — в интервале (С—10).
Следовательно, возникает конфликт, который можноликвидировать, сделав расписание допустимым за счет предпочтения какой-либодетали. Если отдать предпочтение первой детали, расписание примет вид
/>
а есливторой, то времяокончания операций будет
/>
В первом случаесовокупная длительность никла 13 часов. во втором— 15. Следовательно, главныйвопрос при разрешении конфликта состоит в выборе детали, которой следует отдатьпредпочтение для обработки на данном станке. В общем случае любая деталь нанекотором станке может конфликтовать с несколькими другими. Ниже на числовомпримере рассматривается процесс последовательного устранения конфликтов,приводящий в соответствии со схемой метода ветвей и границ к допустимомуоптимальному расписанию работы оборудования.
Пустьдана матрица продолжительностей обработки четырех партий деталей на трехстанках
/>,
Требуетсяопределить порядок обработки партий деталей на каждом станке, обеспечивающийнаименьшую длительность совокупного цикла.
Первыйшаг. Составляем для каждой отдельно взятой детали наилучшее расписание времениокончания ее обработки на каждом из станков в виде матрицы С, элементы которой
/>
определяютсяисходя из возможности обработки каждой детали без пролеживания.
Получаемматрицу
/>.
Второй шаг. Проверяем наличие конфликта напервом станке. Поскольку каждая деталь рассматривалась независимо от остальных,то их обработка на первом станке начинается одновременно и протекает впромежутки времени (0—2). (0—4), (0—9). (0—2). Следовательно, все деталиконфликтуют друг с другом.
Третийшаг. Разрешая поочередно конфликт в пользу каждой из деталей, находим тудеталь, которую целесообразно на первом станке обрабатывать первой. Для этоговыполняем т раз следующие два действия.
1.Строим календарное расписание /> окончанияобработки деталей на каждой операции при условии, что на первом станке деталь l запускается первой.
Элементыэтой матрицыопределяются из соотношения
/>
Предположим, что деталь 1 запускается на первом станкепервой. Тогда
/>.
Врезультате деталь 1 не конфликтует ни с какими другими деталями на нервомстанке.
2.Каждому календарному расписанию /> приписываемего оценку /> в виде минимальновозможного времени окончания Обработки деталей на последнем станке n в предположении, что на первых п — 1станках конфликты отсутствуют.
Изматрицы /> известно возможное времяначала обработки любой детали i напоследнем станке. Оно совпадает с временем /> окончанияее обработки на предпоследнем станке.
Чтобы не увеличивать длительностьобработки деталей, целесообразно на последнем станке обрабатывать детали вочередности их поступления на этот станок
/>,
где
/>
Оценка /> определяетсяследующим образом.
Первоначально сравниваем /> с />.
Если /> , то время завершения обработки двухдеталей i1 и /> напоследней операции будет равно времени окончания обработки детали i2, т. е.
/>.
Если /> , то />.
Далее сравниваем время завершенияобработки на последнем станке двух первых деталей i1 и i2 с временам завершения обработки напредпоследнем стачке детали i3.Здесь возможны два случая:
1) если/>., то /> ;
2)если />, то /> , и т.д.
Врезультате такого цепного расчета получим минимально возможное время обработкивсех деталей /> для варианта расписания /> предположении, что всеконфликты в нем на первых п — 1 станках устранены. Эту величину и принимаем занижнюю границу времени окончания обработки деталей по расписанию />
/>.
Каквидно из матрицы />, моментызавершения обработки деталей на предпоследнем, втором станке упорядоченыследующим образом:
/>,
т. е.детали на последний станок поступают в очередности 1, 3, 2, 4. Выбираем первыедве детали 1 и 3 и определяем момент завершения их обработки на последнемстанке.
Таккак />, то />.
Включаем в рассмотрение третью попорядку деталь 2. Поскольку, />томинимально возможное время обработки первых трех деталей (1, 3, 2) будет
/>.
Рассматривая последнюю деталь, видим,что />.
Следовательно, />.
Отсюдаполучаем
/>.
Повторимдействия I и 2 для остальных вариантов, когда первой на первом станке обрабатываетсядеталь 2, 3 или 4.
Разрешая конфликт в пользу детали 2, получаем
/>, />.
Отдавая предпочтение па первом станке детали3, получаем расписание и его опенку в виде
/>, />.
Разрешаемконфликт в пользу детали 4:
/>, />.
3.Сопоставляем расписания />, /> и их оценки /> с вершинами дерева,изображающего процесс ветвления всего множества вариантов расписания наподмножества (рисунок 1).
/>
Рисунок 1
Извсех рассмотренных календарных расписаний /> выбираемтакое />, для которого
/>.
Поскольку наименьшей оценкой является />, предпочтение к запуску напервом станке отдается детали l=1.Остальные m-1=3 детали продолжают конфликтоватьпа первом станке.
Четвертыйшаг. В качестве исходного календарного расписания для дальнейших расчетов беремматрицу />, на основе которой будемопределять деталь, подлежащую запуску на нервом станке второй. Для этогопостроим календарные расписания в виде матриц />,элементы которых находятся по правилу
/>
Разрешаяконфликты для каждой из т—1 оставшейся детали на первом станке, получим нижнююграницу для каждого расписания /> и выберем из всех расписаний то, для которого
/>.
Деталь k2 планируется к обработке второй. Выполним эти расчеты длянашего примера.
Разрешаяконфликт для детали 2, построим для нее календарное расписание с учетом того,что деталь 1 уже назначена к обработке первой, и найдем его нижнюю границу.Получим
/>, />.
Разрешаемконфликт в пользу детали 3:
/>, />.
Разрешаемконфликт в пользу детали 4:
/>, />.
Сопоставимполученные расписания и их оценки с вершинами дерева, разливаемыми из вершины /> (рисунок 1).
Таккак оценки для всех вариантов одинаковы, безразлично, какой из деталей отдатьпредпочтение. Пусть деталь 2 планируется к запуску на первом станке второй.
Пятыйшаг. Аналогичным образом определим деталь, запускаемую на первом станкетретьей.
Разрешаемконфликт относительно детали 3:
/>, />.
Разрешаемконфликт относительно детали 4:
/>, />.
Сопоставляемполученные расписания и их оценки с вершинами дерева, развиваемыми из вершины /> (рисунок 1). Так какоценки, связанные с запуском на первом станке трех первых детален в очередности1, 2, 3 или 1, 2, 4, одинаковы, безразлично, какой из них отдать предпочтение.Пусть выбрана первая из них, k3=3, тогда последовательностьобработки деталей на первом станке будет 1, 2, 3, 4, с нижней границей, равной38.
Шестой шаг. В результате предыдущих шаговполучено календарное расписание /> ипоследовательность запуска партий деталей на первом станке />.
Далеепровернем и последовательно разрешаем конфликты на втором станке.
Детали1, 2, 3, 4 планируются к обработке в интервалах времени соответственно (2—5),(6—15), (15—18),(17—36).
Следовательно,на втором станке деталь 2 запускается после детали I, а детали 3 и 4конфликтуют.
Разрешимконфликт относительно детали 3.
Дляэтого на базе /> составимрасписание, в котором элементы /> дляданной детали и деталей, не участвующих в конфликте, остаются без изменения, аэлементы /> и /> возрастают на величинузадержки в поступлении детали 4 на второй станок, которая равна в данном случаеразности />—/> == 1. Получим расписание иоценку нижней границы:
/>, />.
Разрешаяконфликт в пользу детали 4, задерживаем подачу детали 3 ко второму станку на36—15=21, в результате чего расписание и его оценка принимают вид
/>, />.
Сопоставляяэти расписания и оценки с вершинами графа, развиваемыми из вершины />, выбираем расписание />, предусматривающееобработку на втором станке третьей по порядку детали 3.
Таким образом, на этом шаге упорядоченаочередность запусков партий на втором станке в виде последовательности деталей1. 2, 3, 4 с оценкой времени совокупного цикла />.
Седьмойшаг. Отправляясь от расписания />,проверяем наличие конфликтующих детален на третьем станке.
Детали1, 2, 3, 4 планируются к обработке в интервалах времени соответственно (5—18),(15—26), (18—26),(37—38).
Конфликтуюттри первые детали. Разрешаем конфликт в пользу детали 1:
/>, />.
Разрешаемконфликт в пользу детали 2:
/>, />.
Разрешаемконфликт в пользу детали 3:
/>, />.
Разветвляемвершину /> дерева решений (рисунок 1)в соответствии с полученными оценками. Для определения детали, запускаемой патретьем станке второй, выбираем расписание />,имеющее меньшую нижнюю границу.
Рассматриваяего, видим, что на третьем станке конфликтуют детали 2 и 3, обрабатываемые винтервалы времени соответственно (15—29) и (18—26).
Разрешимконфликт, отдавая предпочтение детали 2.
Получимрасписание и его оценку:
/>, />.
Разрешимконфликт в пользу детали 3:
/>, />.
Таким образом, безразлично, какой деталиотдать предпочтение. Пусть второй обрабатывается деталь 2. Проверяя расписание />, устанавливаем отсутствиеконфликтов па третьем станке.
Мынашли один из вариантов календарного расписания. Чтобы убедиться в егооптимальности, рассмотрим дерево ветвлений и проанализируем значения нижнихграниц для всех его оборванных ветвей. Поскольку все нижние оценки не меньшеполученной, считаем расписание /> оптимальным.Начало времени обработки партий деталей
/>.
Календарный график работы оборудования,соответствующий расписаниям /> и А..
Цифрынад прямоугольниками — номера деталей, внутри прямоугольника — время начала иокончания обработки партии деталей.
2 МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ. МЕТОД ВЕТВЕЙ ИГРАНИЦ
Комбинаторика – раздел математики, посвящённыйрешению задач выбора и расположения элементов некоторого, обычно конечногомножества в соответствии с заданными правилами.
Каждое такое правило определяетспособ построения некоторой конструкции из элементов исходного множества,называемой комбинаторной конфигурацией. Поэтому можно сказать, что цельюкомбинаторного анализа является изучение комбинаторных конфигураций. Этоизучение включает в себя вопросы существования комбинаторных конфигураций,алгоритмы их построения, оптимизацию таких алгоритмов, а также решение задачперечисления, в частности определение числа конфигураций данного класса.Простейшим примером комбинаторных конфигураций являются перестановки, сочетанияи размещения.
Большой вклад в систематическоеразвитие комбинаторных методов был сделан Г. Лейбницем (диссертация“Комбинаторное искусство”), Я. Бернулли (работа “Искусство предположений”), Л.Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейб-ницакомбинаторные методы выделились в самостоятельную часть математики. В работахЛ.Эйлера по разбиениям и композициям натуральных чисел на слагаемые былоположено начало одному из основных методов перечисления комбинаторныхконфигураций – методу производящих функций.
Возвращение интереса к комбинаторномуанализу относится к 50-м годам ХХ в. в связи с бурным развитием кибернетики идискретной математики и широким использованием электронно-вычислительнойтехники. В этот период активизировался интерес к классическим комбинаторнымзадачам.
Классическиекомбинаторные задачи – это задачи выбора ирасположения элементов конечного множества, имеющие в качестве исходнойнекоторую формулировку развлекательного содержания типа головоломок.
В 1859 г. У. Гамильтон придумал игру“Кругосветное путешествие”, состоящую в отыскании такого пути, проходящегочерез все вершины (города, пункты назначения) графа, изображенного на рис. 1,чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути,обладающие таким свойством, называются гамильтоновыми циклами.
Задача о гамильтоновых циклах в графеполучила различные обобщения. Одно из этих обобщений – задача коммивояжера,имеющая ряд применений в исследовании операций, в частности при решениинекоторых транспортных проблем.
Задача коммивояжера (в дальнейшем сокращённо — ЗК) являетсяодной из знаменитых задач теории комбинаторики. Она была поставлена в 1934году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики.В своей области (оптимизации дискретных задач) ЗК служит своеобразнымполигоном, на котором испытываются всё новые методы.
Постановка задачи следующая.
Коммивояжер (бродячий торговец) должен выйти из первогогорода, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первыйгород. Расстояния между городами известны. В каком порядке следует обходитьгорода, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
Чтобы привести задачу к научному виду, введём некоторыетермины. Итак, города перенумерованы числами jÎТ=(1,2,3..n). Тур коммивояжера может быть описан циклическойперестановкой t=(j1,j2,..,jn,j1), причём все j1..jn – разные номера; повторяющийся в начале и в конце j1,показывает, что перестановка зациклена.Расстояния между парами вершин С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=(j1,j2,..,jn,j1) и t’=(j1,jn,..,j2,j1) имеют разную длину и должны учитываться оба. Разных туровочевидно (n-1)!.
Зафиксируем на первом и последнемместе в циклической перестановке номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможнымиспособами. В результате получим все несимметричные туры. Симметричных туровимеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.
Можно представить, что С состоиттолько из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если Сij=0 и не проведено,если Сij=1. Тогда, если существует тур длины 0, то он пройдёт поциклу, который включает все вершины по одному разу. Такой цикл называетсягамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновойцепью (гамильтоновым путём).
В терминах теории графовсимметричную ЗК можно сформулировать так:
Дана полная сеть с n вершинами, длина ребра (i,j)= Сij. Найтигамильтонов цикл минимальной длины.
В несимметричной ЗК вместо “цикл”надо говорить “контур”, а вместо “ребра” — “дуги” или “стрелки”.
Некоторые прикладные задачиформулируются как ЗК, но в них нужно минимизировать длину не гамильтоновацикла, а гамильтоновой цепи. Такие задачи называются незамкнутыми. Некоторыемодели сводятся к задаче о нескольких коммивояжерах, но мы здесь их рассматриватьне будем.
Жадный алгоритм
Жадный алгоритм – алгоритмнахождения наикратчайшего расстояния путём выбора самого короткого, ещё невыбранного ребра, при условии, что оно не образует цикла с уже выбраннымирёбрами. “Жадным” этот алгоритм назван потому, что на последних шагахприходится жестоко расплачиваться за жадность.
/>
Рисунок 3
Посмотрим, как поведетсебя при решении ЗК жадный алгоритм. Здесь он превратится в стратегию “иди вближайший (в который еще не входил) город”. Жадный алгоритм, очевидно, бессиленв этой задаче. Рассмотрим для примера сеть на рисунке 3, представляющую узкийромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди вы ближайший город”выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить зажадность, возвращаясь по длинной диагонали ромба. В результате получится некратчайший, а длиннейший тур.
В пользу процедуры“иди в ближайший” можно сказать лишь то, что при старте из одного города она неуступит стратегии “иди в дальнейший”.
Как видим,жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно, чтополученный им тур хуже минимального, положим, в 1000 раз? Мы докажем, что этогодоказать нельзя, причем не только для жадного алгоритма, а для алгоритмовгораздо более мощных. Но сначала нужно договориться, как оценивать погрешностьнеточных алгоритмов, для определенности, в задаче минимизации. Пусть fB- настоящий минимум, а fA — тот квазиминимум, который получен по алгоритму. Ясно, что fA/ fB≥1,но это – тривиальное утверждение, что может быть погрешность. Чтобы оценить её,нужно зажать отношение оценкой сверху:
fA/fB ≥1+ nε, (5)
где, как обычно в высшей математике,ε≥0, но, против обычая, может быть очень большим. Величина ε ибудет служить мерой погрешности. Если алгоритм минимизации будет удовлетворятьнеравенству (5), мы будем говорить, что он имеет погрешность ε.
Предположим теперь, чтоимеется алгоритм А решения ЗК, погрешность которого нужно оценить. Возьмемпроизвольный граф G (V,E) и по нему составим входную матрицу ЗК:
/>
Если в графе G есть гамильтонов цикл, то минимальный тур проходит по этомуциклу и fB = n. Если алгоритм А тоже всегда будет находить этот путь, то порезультатам алгоритма можно судить, есть ли гамильтонов цикл в произвольномграфе. Однако, непереборного алгоритма, который мог бы ответить, есть лигамильтонов цикл в произвольном графе, до сих пор никому не известно. Такимобразом, наш алгоритм А должен иногда ошибаться и включать в тур хотя бы одно ребродлины 1+nε. Но тогда fA³(n-1)+(1+nε)так что fA/fB=1+nε т.е. превосходит погрешность ε на заданнуюнеравенством (5). О величине ε в нашем рассуждении мы не договаривались,так что ε может быть произвольно велик.
Таким образом доказана следующаятеорема.
Либо алгоритм Аопределяет, существует ли в произвольном графе гамильтонов цикл, либопогрешность А при решении ЗК может быть произвольно велика.
Это соображение было впервыеопубликовано Сани и Гонзалесом в 1980 г. Теорема Сани-Гонзалеса основана натом, что нет никаких ограничений на длину ребер. Теорема не проходит, еслирасстояния подчиняются неравенству треугольника (4).
Если онособлюдается, можно предложить несколько алгоритмов с погрешностью 12. Прежде,чем описать такой алгоритм, следует вспомнить старинную головоломку. Можно линачертить одной линией открытый конверт? На рисунке 4 видно, что можно (цифрына отрезках показывают порядок их проведения). Закрытый конверт одной линиейнарисовать нельзя и вот почему. Будем называть линии ребрами, а их перекрестья– вершинами. />
Рисунок 4
Когдачерез точку проводится линия, то используется два ребра – одно для входа ввершину, одно – для выхода. Если степень вершины нечетна – то в ней линиядолжна начаться или кончиться. На рис. 3 вершин нечетной степени две: в однойлиния начинается, в другой – кончается. Однако на рисунке 4 имеется четыревершины степени три, но у одной линии не может быть четыре конца. Если же нужнопрочертить фигуру одной замкнутой линией, то все ее вершины должны иметь четнуюстепень.
Верно и обратноеутверждение: если все вершины имеют четную степень, то фигуру можно нарисоватьодной незамкнутой линией. Действительно, процесс проведения линии можеткончиться, только если линия придет в вершину, откуда уже выхода нет: всеребра, присоединенные к этой вершине (обычно говорят: инцидентные этойвершине), уже прочерчены. Если при этом нарисована вся фигура, то нужноеутверждение доказано; если нет, удалим уже нарисованную часть G’. После этого от графа останетсяодна или несколько связных компонент; пусть G’ – одна из таких компонент. В силу связности исходного графаG, G’ и G’’имеют хоть одну общую вершину, скажем, v. Если в G’’удалены какие-то ребра, то по четному числу от каждой вершины. Поэтому G’’ – связный и все его вершины имеютчетную степень. Построим цикл в G’’(может быть, не нарисовав всего G’’) ичерез v добавим прорисованную часть G’’ к G’. Увеличивая таким образом прорисованную часть G’, мы добьемся того, что G’ охватит весь G.
Эту задачу когда-то решилЭйлер, и замкнутую линию, которая покрывает все ребра графа, теперь называюэйлеровым циклом. По существу была доказана следующая теорема.
Эйлеров цикл в графесуществует тогда и только тогда, когда (1) граф связный и (2) все его вершиныимеют четные степени.
Деревянныйалгоритм
Теперь можно обсудить алгоритм решения ЗК черезпостроение кратчайшего остовного дерева. Для краткости будет называть этоталгоритм деревянным.
Вначале обсудим свойствоспрямления. Рассмотрим какую-нибудь цепь, например, на рис.5. Если справедливонеравенство треугольника, то d[1,3]£d[1,2]+d[2,3] и d[3,5]£d[3,4]+d[4,5] Сложив эти два неравенства, получим d[1,3]+d[3,5]£d[1,2]+d[2,3]+d[3,4]+d[4,5].По неравенству треугольника получим. d[1,5]£d[1,3]+d[3,5]. Окончательно
d[1,5]£ d[1,2]+d[2,3]+d[3,4]+d[4,5]
Итак, если справедливо неравенствотреугольника, то для каждой цепи верно, что расстояние от начала до конца цепименьше (или равно) суммарной длины всех ребер цепи. Это обобщение расхожегоубеждения, что прямая короче кривой.
Вернемся к ЗК и опишем решающий еедеревянный алгоритм.
1. Построим на входной сети ЗКкратчайшее остовное дерево и удвоим все его ребра. Получим граф G – связный и с вершинами, имеющимитолько четные степени.
2. Построим эйлеров цикл G, начиная с вершины 1, цикл задаетсяперечнем вершин.
3. Просмотрим перечень вершин, начиная с1, и будем зачеркивать каждую вершину, которая повторяет уже встреченную впоследовательности. Останется тур, который и является результатом алгоритма.
Теорема. Погрешность деревянного алгоритма равна 1.
Доказательство.Возьмем минимальный тур длины fBи удалим из негомаксимальное ребро. Длина получившейся гамильтоновой цепи LHCменьше fB. Но эту же цепь можно рассматривать как остовное дерево, т.к. эта цепь достигает все вершины и не имеет циклов. Длина кратчайшегоостовного дерева LMT меньше или равна LHC. Имеем цепочку неравенств
fB>LHC³LMT (6)
Но удвоенное дерево – оно же эйлеровграф – мы свели к туру посредством спрямлений, следовательно, длина полученногопо алгоритму тура удовлетворяет неравенству
2LMT>fA (7)
Умножая (6)на два и соединяя с (7), получаем цепочку неравенств
2fB>2LHC³2LMT³fA (8)
Т.е. 2fB>fA, т.е. fA/fB>1+e; e=1.
Теорема доказана.
Таким образом, мы доказали, чтодеревянный алгоритм ошибается менее, чем в два раза. Такие алгоритмы уженазывают приблизительными, а не просто эвристическими.
Известно еще несколько простыхалгоритмов, гарантирующих в худшем случае e=1. Для того, чтобы найти среди нихалгоритм поточнее, зайдем с другого конца и для начала опишем “brute-force enumeration” — “перебор животной силой”, как егоназывают в англоязычной литературе. Понятно, что полный перебор практическиприменим только в задачах малого размера. Напомним, что ЗК с n городами требует при полном переборерассмотрения (n-1)!/2 туров в симметричной задаче и(n-1)! Туров в несимметричной, афакториал, как показано в следующей таблице, растет удручающе быстро:5! 10! 15! 20! 25! 30! 35! 40! 45! 50!
~102
~106
~1012
~1018
~10125
~1032
~1040
~1047
~1056
~1064
Чтобы проводить полныйперебор в ЗК, нужно научиться (разумеется, без повторений) генерировать всеперестановки заданного числа mэлементов. Это можно сделать несколькими способами, но самый распространенный(т.е. приложимый для переборных алгоритмов решения других задач) – это переборв лексикографическом порядке.
Пусть имеется некоторыйалфавит и наборы символов алфавита (букв), называемые словами. Буквы в алфавитеупорядочены: например, в русском алфавите порядок букв аµбµя (символ µ читается “предшествует)”. Если задан порядок букв, можно упорядочить ислова. Скажем, дано слово u=(u1,u2,..,um) – состоящее из букв u1,u2,..,um — и слово v =(v1,v2,..,vb). Тогда если u1µv1, то и uµv, если же u1=v1, то сравнивают вторые буквы и т.д. Этот порядок слов иназывается лексикографическим. Поэтому в русских словарях (лексиконах) слово“абажур” стоит раньше слова “абака”. Слово “бур” стоит раньше слова “бура”,потому что пробел считается предшествующим любой букве алфавита.
Рассмотрим, скажем,перестановки из пяти элементов, обозначенных цифрами 1..5. Лексикографическипервой перестановкой является 1-2-3-4-5, второй – 1-2-3-5-4, …, последней –5-4-3-2-1. Нужно осознать общий алгоритм преобразования любой перестановки внепосредственно следующую.
Правило такое: скажем, данаперестановка 1-3-5-4-2. Нужно двигаться по перестановке справа налево, покавпервые не увидим число, меньшее, чем предыдущее (в примере это 3 после 5). Эточисло, Pi-1 надо увеличить, поставив вместо негокакое-то число из расположенных правее, от Pi до Pn. Число большее, чем Pi-1, несомненно, найдется, так как Pi-1i-1. Затем число Pi-1и все числа от Pi до Pn, не считая Pj нужно упорядочить по возрастанию. Врезультате получится непосредственно следующая перестановка, в примере – 1-4-2-3-5.Потом получится 1-4-2-5-3 (тот же алгоритм, но упрощенный случай) и т.д.
Нужно понимать, что в ЗК с n городами не нужны все перестановкииз n элементов. Потому что перестановки,скажем, 1-3-5-4-2 и 3-5-4-2-1 (последний элемент соединен с первым) задают одини тот же тур, считанный сперва с города 1, а потом с города 3. Поэтому нужнозафиксировать начальный город 1 и присоединять к нему все перестановки изостальных элементов. Этот перебор даст (n-1)! разных туров, т.е. полный перебор в несимметричной ЗК(мы по-прежнему будем различать туры 1-3-5-4-2 и 1-2-4-5-3).
Данный алгоритм описан наязыке Паскаль (см. Приложения).
Пример 2. Решим ЗК, поставленную в Примере 1лексикографическим перебором. Приведенная выше программа напечатает города,составляющие лучший тур: 1-2-6-5-4-3 и его длину 36.
Желательно усовершенствовать перебор,применив разум. В следующем пункте описан алгоритм, который реализует простую,но широко применимую и очень полезную идею.
Алгоритм Дейкстры
Одним из вариантов решения ЗК является вариант нахождениякратчайшей цепи, содержащей все города. Затем полученная цепь дополняетсяначальным городом – получается искомый тур.
Можно предложить много процедур решения этой задачи,например, физическое моделирование. На плоской доске рисуется карта местности,в города, лежащие на развилке дорог, вбиваются гвозди, на каждый гвоздьнадевается кольцо, дороги укладываются верёвками, которые привязываются ксоответствующим кольцам. Чтобы найти кратчайшее расстояние между i и k, нужно взять I в одну руку и k в другую и растянуть.Те верёвки, которые натянутся и не дадут разводить руки шире и образуюткратчайший путь между i и k. Однако математическая процедура, которая промоделирует этуфизическую, выглядит очень сложно. Известны алгоритмы попроще. Один из них –алгоритм Дейкстры, предложенный Дейкстрой ещё в 1959г. Этот алгоритм решаетобщую задачу:
В ориентированной, неориентированной или смешанной (т. е.такой, где часть дорог имеет одностороннее движение) сети найти кратчайший путьмежду двумя заданными вершинами.
Алгоритм использует три массива из n (= числу вершин сети)чисел каждый. Первый массив a содержит метки с двумя значениями: 0 (вершина ещё нерассмотрена) и 1 (вершина уже рассмотрена); второй массив b содержит расстояния –текущие кратчайшие расстояния от vi до соответствующей вершины; третий массив c содержит номеравершин – k-й элемент ck есть номер предпоследней вершины на текущем кратчайшем путииз vi в vk. Матрица расстояний Dikзадаёт длины дуг dik; если такой дуги нет, то dikприсваивается большое число Б, равное “машинной бесконечности”.
Теперь можно описать:
Алгоритм Дейкстры
1. Инициализация.
В цикле от одного до n заполнить нулямимассив а; заполнить числом i массив с: перенести i-тую строку матрицы D в массив b;
a[i]:=1; c[i]:=0; {i-номер стартовойвершины}
2. Общий шаг.
Найти минимум среди неотмеченных (т. е. тех k, для которых a[k]=0); пусть минимумдостигается на индексе j, т. е. bj£bk; a[j]:=1;
если bk>bj+djk то (bk:=bj+djk; ck:=j) {Условие означает, что путь vi..vkдлиннее, чем путь vi..vj,vk. Если все a[k] отмечены, то длина пути vi..vkравна b[k]. Теперь надо перечислить вершины, входящие в кратчайшийпуть}
3. Выдача ответа.
{Путь vi..vkвыдаётся в обратном порядке следующей процедурой:}
3.1. z:=c[k];
3.2. Выдать z;
3.3. z:=c[z]; Если z = 0, то конец, иначе перейти к 3.2.
Для выполнения алгоритма нужно n раз просмотреть массив b из n элементов, т. е.алгоритм Дейкстры имеет квадратичную сложность.
Таким образом, для решения ЗК нужно n раз применитьалгоритм Дейкстры следующим образом.
Возьмём произвольную пару вершин
j,k. Исключимнепосредственное ребро C[j,k]. С помощью алгоритма Дейкстры найдём кратчайшее расстояниемежду городами j..k. Пусть это расстояниевключает некоторый город m. Имеем часть тура j,m,k. Теперь для каждой пары соседних городов (в данном примере– для j,m и m,k) удалим соответственное ребро и найдём кратчайшеерасстояние. При этом в кратчайшее расстояние не должен входить ужеиспользованный город.
Далее аналогично находим кратчайшее расстояние между парамивершин алгоритмом Дейкстры, до тех пор, пока все вершины не будутзадействованы. Соединим последнюю вершину с первой и получим тур. Чаще всегоэто последнее ребро оказывается очень большим, и тур получается с погрешностью,однако алгоритм Дейкстры можно отнести к приближённым алгоритмам.
Практическое применение задачи коммивояжера
Кроме очевидного применения ЗК на практике, существует ещёряд задач, сводимых к решению ЗК.
Задача о производстве красок.Имеется производственная линия для производства n красок разного цвета;обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать однимпроцессором… Будем считать также, что единовременно процессор производиттолько одну краску, поэтому краски нужно производить в некотором порядкеПоскольку производство циклическое, то краски надо производить в циклическомпорядке p=(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))
Теперь, как и в предыдущем случае, задача составленияоптимальной программы для дыропробивного пресса сводится к ЗК (здесь — симметричной).
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 Условие задачи
Задача
Определить оптимальнуюпоследовательность запуска деталей в производство, если задана матрица затратна переналадку оборудования:№ 1 2 3 4 5 6 7 1 ∞ 21 11 18 8 15 9 2 19 ∞ 8 3 7 15 25 3 13 18 ∞ 16 1 13 20 4 16 5 14 ∞ 26 14 17 5 17 9 5 6 ∞ 12 19 6 19 7 21 13 24 ∞ 21 7 10 29 25 11 14 17 ∞
Сделать анализ решенной задачи.
ВЫВОДЫ
В результате выполненной работы былиизичуны эврестический, приближенный и точный алгоритмы решения задачкоммивояжера. Точные алгоритмы решения задач коммивояжера – это полный переборили усовершенствованный перебор. Оба они, особенно первый, не эффективны прибольшом числе вершин графа.
Для малого числа вершин наиболееэффективный точный метод лексического перебора, для большого числа вершинрациональнее применять метод ветвей и границ. Изучены практические применениязадач коммиявожера и задачи nстанков.
Особенно рассмотренметод ветвей и границ в задачах коммивояжера. Приведен алгоритм данного метода,схема алгоритма, а также решена задача на определение оптимальнойпоследовательности запуска деталей в производство, если задана матрица затратна переналадку оборудования. После чего был произведен анализ решенной задачи.
Также прилагаетсяпрограммана решающая задачу о коммивояжере методом ветвей и границ. Дляразработки данной программы была использованя среда разработки Delphi версии 6.0.
Delphi 6.0 представляет собой уникальную систему разработки, вкоторой технология высокопроизводительной оптимизмпующей компиляции сочетаетсяс визуальными средствами разработки и масштабируемым процессом баз данных.
Данная программа решаетзадачи разной размерности, что доказывает её универсальность для любых задачданного типа.
ЛИТЕРАТУРА:
1 Балашевич В.А.,Алгоритмизация математических методов планирования и управления. — Минск:Вышэйшая школа,1979.-286с
2 Дегтярев Ю.И.,Исследование операций.- Москва: Высшая школа,1986.-270с.
3 Ляшенко И.Н.Линейное и нелинейное программирование – Киев: Вища школа,1975.-370с.
ПРИЛОЖЕНИЕ А
(обязательное)
Текст программы
Схема программы
Описание программы
Инструкция пользователю
ПРИЛОЖЕНИЕ Б
(обязательное)
Входнаяинформация
ПРИЛОЖЕНИЕВ
(обязательное)
Выходнаяинформация