додати матеріал


Проектування моделі для визначення часу простою верстатів на машинобудівному підприємстві

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

КУРСОВИЙ ПРОЕКТ
з предмету «Моделювання виробничих та економічних процесів»
студента групи 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 на останньому верстаті. Вона збігається з часом закінчення її обробки на передостанньому верстаті.
Щоб не збільшувати тривалість обробки деталей, доцільно на останньому верстаті обробляти деталі у черговості їх надходження на цей верстат
,
де

Оцінка визначається наступним чином.
Спочатку порівнюємо з .
Якщо , То час завершення обробки двох деталей i 1 і на останній операції буде дорівнює часу закінчення обробки деталі i 2, т. е.
.
Якщо , То .
Далі порівнюємо час завершення обробки на останньому верстаті двох перших деталей i 1 і i 2 з часів завершення обробки на передостанньому страйку деталі i 3. Тут можливі два випадки:
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 залишилася деталі на першому верстаті, отримаємо нижню межу для кожного розкладу і виберемо з усіх розкладів те, для якого
.
Деталь k 2 планується до обробки другий. Виконаємо ці розрахунки для нашого прикладу.
Вирішуючи конфлікт для деталі 2, побудуємо для неї календарний розклад з урахуванням того, що деталь 1 вже призначена до обробки першої, і знайдемо його нижню межу. Отримаємо
, .
Вирішуємо конфлікт на користь деталі 3:
, .
Вирішуємо конфлікт на користь деталі 4:
, .
Зіставимо отримані розкладу та їх оцінки з вершинами дерева, розливає з вершини (Рисунок 1).
Так як оцінки для всіх варіантів однакові, байдуже, який з деталей віддати перевагу. Нехай деталь 2 планується до запуску на першому верстаті другий.
П'ятий крок. Аналогічним чином визначимо деталь, що запускається на першому верстаті третьою.
Вирішуємо конфлікт щодо деталі 3:
, .
Вирішуємо конфлікт щодо деталі 4:
, .
Зіставляємо отримані розкладу та їх оцінки з вершинами дерева, що розвиваються з вершини (Рисунок 1). Так як оцінки, пов'язані з запуском на першому верстаті трьох перших детальний в черговості 1, 2, 3 або 1, 2, 4, однакові, байдуже, який з них віддати перевагу. Нехай вибрана перша з них, k 3 = 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 = (j 1, j 2, .., j n, j 1), причому всі j 1 .. j n - різні номери; повторюється на початку і в кінці j 1, показує, що перестановка зациклена. Відстані між парами вершин З ij утворюють матрицю С. Завдання полягає в тому, щоб знайти такий тур t, щоб мінімізувати функціонал

Щодо математизувати формулювання ЗК доречно зробити два зауваження.
З ij ³ 0; C jj = ∞
(2)
По-перше, у постановці З ij означали відстані, тому вони повинні бути невід'ємними, тобто для всіх jÎТ:
(Останнє рівність означає заборону на петлі в турі), симетричними, тобто для всіх i, j:
З ij = С ji.
((3)
і задовольняти нерівності трикутника, тобто для всіх:
З ij + С jk ³ C ik
((4)
У математичній постановці йдеться про довільної матриці. Зроблено це тому, що є багато прикладних задач, які описуються основною моделлю, але всім умовам (2) - (4) не задовольняють. Особливо часто порушується умова (3) (наприклад, якщо С ij - не відстань, а плата за проїзд: часто туди квиток коштує одну ціну, а назад - іншу). Тому ми будемо розрізняти два варіанти ЗК: симетричну задачу, коли умова (3) виконано, і несиметричну - в іншому випадку. Умови (2) - (4) за замовчуванням ми будемо вважати виконаними.
Друге зауваження стосується числа всіх можливих турів. У несиметричною ЗК всі тури t = (j 1, j 2, .., j n, j 1) і t '= (j 1, j n, .., j 2, j 1) мають різну довжину і повинні враховуватися обидва . Різних турів очевидно (n-1)!.
Зафіксуємо на першому і останньому місці в циклічній перестановці номер j 1, а решта 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, але це - тривіальне твердження, що може бути похибка. Щоб оцінити її, потрібно затиснути ставлення оцінкою зверху:
f A / f B ≥ 1 + nε,
(5)
де, як зазвичай у вищій математиці, ε ≥ 0, але, проти звичаю, може бути дуже великим. Величина ε і буде служити мірою похибки. Якщо алгоритм мінімізації буде задовольняти нерівності (5), ми будемо говорити, що він має похибка ε.
Припустимо тепер, що є алгоритм А рішення ЗК, похибка якого потрібно оцінити. Візьмемо довільний граф G (V, E) і по ньому складемо вхідну матрицю ЗК:

Якщо в графі G є гамільтонів цикл, то мінімальний тур проходить по цьому циклу і f B = n. Якщо алгоритм А теж завжди буде знаходити цей шлях, то за результатами алгоритму можна судити, чи є гамільтонів цикл в довільному графі. Однак, неперебiрний алгоритм, який міг би відповісти, чи є гамільтонів цикл в довільному графі, до цих пір нікому не відомо. Таким чином, наш алгоритм А повинен іноді помилятися і включати в тур хоча б одне ребро довжини 1 + nε. Але тоді f A ³ (n-1) + (1 + nε) так що f A / f B = 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.
Доказ. Візьмемо мінімальний тур довжини f B і вилучимо з нього максимальний ребро. Довжина вийшла гамильтоновой ланцюга L HC менше f B. Але цю ж ланцюг можна розглядати як кістяк, тому що цей ланцюг досягає всі вершини і не має циклів. Довжина найкоротшого кістяка L MT менше або дорівнює L HC. Маємо ланцюжок нерівностей
f B> L HC ³ L MT
(6)
Але подвоєне дерево - воно ж Ейлером граф - ми звели до туру допомогою випрямлення, отже, довжина отриманого за алгоритмом туру задовольняє нерівності
2L MT> f A
(7)
Множачи (6) на два і з'єднуючи з (7), отримуємо ланцюжок нерівностей
2f B> 2L HC ³ 2L MT ³ f A
(8)
Тобто 2f B> f A, тобто f A / f B> 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!
~ 10 лютого
~ 10 червня
~ Жовтня 1912
~ 18 жовтня
~ 10 125
~ Жовтня 1932
~ Жовтня 1940
~ Жовтня 1947
~ Жовтня 1956
~ Жовтня 1964
Щоб проводити повний перебір у ЗК, потрібно навчитися (зрозуміло, без повторень) генерувати всі перестановки заданого числа m елементів. Це можна зробити декількома способами, але найпоширеніший (тобто застосовний для переборних алгоритмів вирішення інших завдань) - це перебір у лексикографічному порядку.
Нехай є деякий алфавіт і набори символів алфавіту (літер), звані словами. Букви в алфавіті впорядковані: наприклад, у російській алфавіті порядок букв аμбμя (символ μ читається "передує)". Якщо заданий порядок букв, можна впорядкувати і слова. Скажімо, дано слово u = (u 1, u 2, .., u m) - що складається з букв u 1, u 2, .., u m - і слово v = (v 1, v 2, .., v b). Тоді якщо u 1 μv 1, то і uμv, якщо ж u 1 = v 1, то порівнюють другий букви і т.д. Цей порядок слів і називається лексикографічним. Тому в російських словниках (лексиконів) слово "абажур" варто раніше слова "абака". Слово "бур" варто раніше слова "бура", тому що пробіл вважається попереднім будь букві алфавіту.
Розглянемо, скажімо, перестановки з п'яти елементів, позначених цифрами 1 .. 5. Лексикографічно перший перестановкою є 1-2-3-4-5, другий - 1-2-3-5-4, ..., останньою - 5-4-3-2-1. Потрібно усвідомити загальний алгоритм перетворення будь перестановки в безпосередньо наступну.
Правило таке: скажімо, дана перестановка 1-3-5-4-2. Потрібно рухатися по перестановці справа наліво, поки вперше не побачимо число, менше, ніж попереднє (у прикладі це 3 після 5). Це число, P i -1 треба збільшити, поставивши замість нього якесь число з розташованих правіше, від P i до P n. Число більше, ніж P i -1, безсумнівно, знайдеться, так як P i - 1 <P i. Якщо є кілька великих чисел, то, очевидно, треба ставити менше з них. Нехай це буде P j, j> i-1. Потім число P i - 1 і всі числа від P i до P n, не рахуючи P j потрібно упорядкувати за зростанням. У результаті вийде безпосередньо наступна перестановка, у прикладі - 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 містить відстані - поточні найкоротші відстані від v i до відповідної вершини, третій масив c містить номери вершин - k-й елемент c k є номер передостанній вершини на поточному найкоротшому шляху з v i в v k. Матриця відстаней D ik задає довжини дуг d ik; якщо такої дуги немає, то d ik присвоюється велика кількість Б, рівне "машинної нескінченності".
Тепер можна описати:
Алгоритм Дейкстри
1. Ініціалізація.
У циклі від одного до n заповнити нулями масив а; заповнити числом i масив з: перенести i-ту рядок матриці D в масив b;
a [i]: = 1; c [i]: = 0; {i-номер стартовою вершини}
2. Загальний крок.
Знайти мінімум серед невідміченим (тобто тих k, для яких a [k] = 0); нехай мінімум досягається на індексі j, тобто b j £ b k; a [j]: = 1;
якщо b k> b j + d jk то (b k: = b j + d jk; c k: = j) {Умова означає, що шлях v i .. v k довший, ніж шлях v i .. v j, v k. Якщо все a [k] відзначені, то довжина шляху v i .. v k дорівнює b [k]. Тепер треба перерахувати вершини, що входять в найкоротший шлях}
3. Видача відповіді.
{Шлях v i .. v k видається у зворотному порядку такої процедури:}
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 = (j 1, j 2, .., j n, j 1). Після закінчення виробництва фарби i і перед початком виробництва фарби j треба відмити обладнання від фарби i. Для цього потрібен час C [i, j]. Очевидно, що C [i, j] залежить як від i, так і від j, і що, взагалі кажучи, C [i, j] ≠ C [j, i]. При деякому вибраному порядку доведеться на цикл виробництва фарб витратити час

Де t k - Чистий час виробництва k-ої фарби (не рахуючи переналагоджень). Проте друга сума в правій частині постійна, тому повний час на цикл виробництва мінімізується разом із загальним часом на переналагодження.
Таким чином, ЗК та завдання щодо мінімізації часу переналагодження - це просто одна задача, тільки варіанти її описані різними словами.
Задача про діропробивні пресі. Діропробивний прес виробляє велику кількість однакових панелей - металевих листів, в яких послідовно по одному пробиваються отвори різної форми і величини. Схематично прес можна представити у вигляді столу, який рухався незалежно за координатами x, y, і що обертається над столом диска, по периметру якого розташовані діропробивні інструменти різної форми і величини. Кожен інструмент присутня в одному екземплярі. Диск може обертатися однаково в двох напрямках (координата обертання z). Є власне прес, який натискає на підвішений під нього інструмент тоді, коли під інструмент підведена потрібна точка аркуша.
Операція пробивання j-того отвору характеризується четвіркою чисел (x j, y j, z j, t j),, де x j, y j - координати потрібного положення столу, z j - координата потрібного положення диска і t j - Час пробивання j-того отвору.
Виробництво панелей носить циклічний характер: на початку і наприкінці обробки кожного аркуша стіл повинен знаходитися в положеннях (x 0, y 0) диск в положенні z 0 причому в цьому положенні отвір не пробивається. Це початковий стан системи можна вважати пробивкой фіктивного нульового отвори. З параметрами (x 0, y 0, z 0, 0).
Щоб пробити 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 Умова задачі
Завдання
Визначити оптимальну послідовність запуску деталей у виробництво, якщо задана матриця витрат на переналагодження устаткування:

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с.

ДОДАТОК А
(Обов'язковий)
Текст програми
Схема програми
Опис програми
Інструкція користувачеві

ДОДАТОК Б
(Обов'язковий)
Вхідна інформація

ДОДАТОК В
(Обов'язковий)
Вихідна інформація
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
187.3кб. | скачати


Схожі роботи:
Проектування двошвидкісного асинхронного двигуна для приводу деревообробних верстатів
Визначення норми витрат матеріалу на виріб і проектування технологічного процесу виготовлення Характеристика моделі
Проектування моделі для складання оптимального раціону годівлі худоби
Основні засоби як об`єкт обліку на машинобудівному підприємстві
Організація системи управління на сучасному машинобудівному підприємстві
Основні принципи організації і функціонування виробництва на машинобудівному підприємстві
Проектування електропостачання цеху металорізальних верстатів
Проектування електропостачання цеху металорізальних верстатів
Визначення норм точності і методів випробувань металорізальних верстатів колесотокарний верстат
© Усі права захищені
написати до нас
Рейтинг@Mail.ru