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

см. Модели линейного программирования для решения задач раскроя .

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

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

Ширина рулона(м)	Варианты раскроя рулона						Минимальное количество рулонов
	1	2	3	4	5	6
0,5	0	2	2	4	1	0	150
0,7	1	1	0	0	2	0	200
0,9	1	0	1	0	0	2	300
Отходы в м	0,4	0,3	0,1	0	0,1	0,2	-

Определим переменные:
X j - количество стандартных рулонов, разрезаемых по варианту j, j =1, 2, 3,4,5, 6 .
Ограничения непосредственно связаны с требованием обеспечить изготовление требуемого количества нестандартных рулонов. Используя данные табл., получим:
2Х 2 + 2 Х 3 + 4 Х 4 + Х 5 = 150 - количество рулонов шириной 0,5 м,
X 1 + Х 2 + 2 Х 5 = 200 - количество рулонов шириной 0,7 м,
X 1 + Х 3 + 2 Х 6 =300 - количество рулонов шириной 0,9 м.

Выражение для суммарной величины потерь бумаги (отходы) (в м) имеет вид
0,4Х 1 + 0,3 Х 2 + 0,1 Х 3 + 0,1 Х 5 + 0,2 Х 6 .

Таким образом, математическая модель в общем виде имеет вид
min f(x) = 0,4 X 1 + 0,3Х 2 + 0,1Х 3 + 0,1Х 5 + 0,2Х 6 .
при ограничениях:
2Х 2 + 2 Х 3 + 4 Х 4 + Х 5 = 150
Х 2 + Х 2 + 2 Х 5 = 200
Х 2 + Х 3 + 2 Х 6 = 300

Задача о раскрое материалов

Данная задача состоит в разработке такого плана, который обеспечивает необходимый комплект изделий при минимальных отходах (по длине, площади, массе, стоимости и др.) при раскрое материалов или обеспечивает максимальное число комплектов изделий. Пример №2 . Требуется разработать оптимальный план раскроя стандартных листов стали, обеспечивая выход планового числа заготовок разного вида при минимальных суммарных отходах, если известно, что из партии листовой стали необходимо нарезать четыре вида различных заготовок в количестве b i (i = 1, 2,…,4) штук. Лист стали стандартных размеров может быть раскроен четырьмя способами. Каждому возможному способу раскроя соответствует карта раскроя. Из карт раскроя известен выход заготовок в штуках разных видов a ij (i = 1, 2,…4; j = 1,2,…,4), а также площадь отходов c j (j = 1, 2,…,n) при раскрое одного листа стали по j-му способу раскроя. Какое количество листов стали необходимо раскроить тем или иным способом, чтобы отходы были минимальными?

Таблица 3

Виды заготовок	План-задание по количеству заготовок (b 1)	Выход заготовок (шт) разных видов из карт раскроя (a ij)
		1	2	3	4
1	240	1	4	0	1
2	200	1	0	4	0
3	120	1	0	0	3
4	140	1	1	0	3
Площадь отходов, м 2 (c j)		1,4	0,1	2,1	0,1

Составим экономико-математическую модель задачи. Обозначим через x j – количество исходного материала (листов стали), которые необходимо раскроить по одному из способов j . Ограничения в задаче должны соответствовать плановому выходу заготовок различных видов. Целевая функция сводиться к нахождению минимума отходов при раскрое

F=1,4·x 1 +0,1·x 2 +2,1·x 3 +0,1·x 4 →(min)..
Ограничения по выходу заготовок i-го вида по всем j способам раскроя:

Пример №3 . На раскрой (распил, обработку) поступает материал одного образца в количестве a единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональных числам b 1 , b 2 ,…,b l (условие комплектности). Каждая единица материала может быть раскроена n различными способами, причем использование i -го способа (i = 1, 2,…,n) дает a ik единиц k-го изделия (k = 1, 2,…,l). Необходимо найти план раскроя, обеспечивающий максимальное число комплектов.
Составим экономико-математическую модель задачи.
Обозначим через x i – число единиц материала, раскраиваемых i-ым способом, и x – число изготавливаемых комплектов изделий. Тогда целевая функция сводиться к нахождению

F=x→(max),
при ограничениях: по общему количеству материала равного сумме его единиц, раскраиваемых различными способами; по требованию комплектности и не отрицательности переменных.

Пример №4 . На предприятии имеются бревна длиной L м, которые необходимо разрезать на заготовки длиной l 1 , l 2 , l 3 м в количестве p 1 , p 2 , p 3 соответственно.
Необходимо составить оптимальный план раскройки материала, который обеспечивает минимальные отходы, при условии выполнения плана по выходу заготовок. Исходные данные приведены в таблице.

Задача	Длина	Размеры заготовок, м			Количество заготовок, шт.
		l 1	l 2	l 3	p 1	p 2	p 3
68	6,5	2,1	2,3	1,4	600	720	900

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

Длина заготовки	Варианты раскроя							Количество заготовок
	1	2	3	4	5	6	7
2,1	3	2	2	1	1	0	0	600
2,3	0	1	0	1	0	2	1	720
1,4	0	0	1	1	3	1	3	900
Остаток, м	0,2	0	0,9	0,7	0,2	0,5	0

Обозначим через x i количество бревен, разрезанных по i-му варианту (i=1..7). Тогда суммарный остаток отходов запишется в виде линейной функции:
Z = 0,2x 1 + 0x 2 + 0,9x 3 + 0,7x 4 + 0,2x 5 + 0,5x 6 + 0x 7
При этом должны выполняться условия выполнения плана по количеству заготовок, т.е.
3x 1 + 2x 2 + 2x 3 + x 4 + x 5 = 600
x 2 + x 4 + 2x 6 + x 7 = 720
x 3 + x 4 + 3x 5 + x 6 + 3x 7 = 900

Таким образом, для решения поставленной задачи необходимо найти minZ при ограничениях. Поскольку minZ = -max(-Z(x)), то вместо задачи минимизации функции будем решать задачу максимизации функции:
Z = -(0,2x 1 + 0x 2 + 0,9x 3 + 0,7x 4 + 0,2x 5 + 0,5x 6 + 0x 7)

Пример №5 . Для пошива одного изделия требуется выкроить из ткани 6 деталей. На швейной фабрике были разработаны два варианта раскройки ткани. В таблице (расположенной ниже) приведены характеристики вариантов раскроя 10 м 2 ткани комплектность, т.е. количество деталей определенного вида, которые необходимы для пошива одного изделия. Ежемесячный запас ткани для пошива изделий данного типа составляет 405 м 2 . В ближайший вечер планируется сшить 90 изделий.
Построить математическую модель задачи, позволяющий в ближайший месяц выполнить план по пошиву с минимальным количеством отходов.

Таблица - Характеристики вариантов раскроя отрезков ткани по 10м 2

Вариант раскроя	Количество деталей, шт./отрез						Отходы, м 2 /отрез
	1	2	3	4	5	6
1	60	0	90	40	70	90	0,5
2	80	35	20	78	15	0	0,35
Комплектность, шт./изделие	1	2	2	2	2	2

Математическая постановка задачи

Переменные задачи
В данной задаче искомые величины явно не указаны, но сказано, что должен быть выполнен ежемесячный план по пошиву 90 изделий. Для пошива 90 изделий в месяц требуется раскроить строго определенное количество деталей. Крой производится из отрезков ткани по 10 м 2 двумя различными способами, которое позволяют получить различное число деталей. Поскольку заранее неизвестно, сколько ткани будет раскраиваться первым способом и сколько - вторым, то в качестве искомых величин можно задать количество отрезков ткани по 10м 2 , раскроенных каждым из способов:
x 1 - количество отрезков ткани по 10м 2 , раскроенных первым способом в течении месяца, [отрез./мес.];
x 2 - количество отрезков ткани по 10м 2 , раскроенных первым способом в течении месяца, [отрез./мес.];

Целевая функция
Целью решения задачи является выполнение плана при минимальном количестве отходов. Поскольку количество изделий строго запланировано (90 шт./мес.), то этот параметр не описывает ЦФ, а относится к ограничению, невыполнение которого означает, что задача не решена. А критерием эффективности выполнение плана служит параметр «количество отходов», который необходимо свести к минимуму. Поскольку при раскрое одного отреза (10м 2) ткани по 1-му варианту получается 0,5м 2 отходов, а по 2-му варианту - 0,35м 2 (см. таблицу 1), то общее количество отходов при крое (ЦФ) имеет вид
L(x) = 0.5x 1 + 0.35x 2 = min,

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

• Должен быть выполнен план по пошиву изделий, другими словами, общее количество выкроенных деталей должно быть таким, чтобы из него можно было пошить 90 изделий в месяц, а именно: 1-го вида должно быть как минимум 90 и деталей остальных видов - как минимум по 180 (см. комплектность в таблицу).
• Расход ткани не должен превышать месячного запаса на складе;
• Количество отрезков раскроенной ткани не может быть отрицательным.

Ограничение по плану пошива пальто имеют следующую содержательную форму записи.
(Общее количество деталей №1 выкроенных по всем вариантам)≥ (90 штук);
(Общее количество деталей №2 выкроенных по всем вариантам) ≥ (180 штук);
(Общее количество деталей №6 выкроенных по всем вариантам) ≥ (180 штук);

Математически эти ограничения записываются в виде :
60x 1 + 80x 2 ≥90;
35x 2 ≥180;
90x 1 + 20x 2 ≥180;
40x 1 + 78x 2 ≥180;
70x 1 + 15x 2 ≥180;
90x 1 ≥180;

Ограничение по расходу ткани имеет следующие формы записи:
Содержательную
(общее количество ткани, раскроенной за месяц)≤ (405м 2)
Математическую
x 1 +x 2 ≤405/10

Не отрицательность количества раскроенных отрезков задается в виде
x 1 ≥ 0, x 2 ≥ 0

Таким образом, математическая модель задачи имеет вид
L(x) = 0.5x 1 + 0.35x 2 = min [м 2 отх./мес.],
60x 1 + 80x 2 ≥90;
35x 2 ≥180;
90x 1 + 20x 2 ≥180;
40x 1 + 78x 2 ≥180;
70x 1 + 15x 2 ≥180;
90x 1 ≥180;
x 1 +x 2 ≤40,5
x 1 ≥ 0, x 2 ≥ 0

Пример №6 . Имеется 69 труб для отопительной сети по 1070 см каждая. Их необходимо разрезать на трубы по 130, 150 и 310 см. Найти такой вариант раскроя поступивших труб, при котором отходы были бы минимальными.

Этап 1. Определяем варианты оптимального распила труб.

Варианты раскроя	1	2	3	4	5	6	7	8	9	10	11	12	13
310	3	2	2	2	2	1	1	1	1	0	0	0	0
150	0	3	2	1	0	3	2	1	0	3	2	1	0
130	1	0	1	2	3	2	3	4	5	4	5	7	8
Остатки	10	0	20	40	60	50	70	90	110	100	120	10	30

Этап 2.
Составим экономико-математическую модель задачи. Обозначим через x j - количество труб, которые необходимо распилить по одному из способов j. Целевая функция сводиться к нахождению минимума отходов при распиле:
10x 1 + 20x 3 + 40x 4 + 60x 5 + 50x 6 + 70x 7 + 90x 8 + 110x 9 + 100x 10 + 120x 11 + 10x 12 + 30x 13 → min

x 1 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 + x 9 + x 10 + x 11 + x 12 + x 13 = 69

Ответ: необходимо использовать только второй вариант распила (нулевые отходы)

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

Основные схемы раскроя пиловочного сырья

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

Основные способы распиловки бревен
а — вразвал; б — с брусовкой; б’ — с получением двух брусьев; б» — вразвал брусьев; в — секторный; в’ — распиловка сектора на радиальные доски; в» — на тангентальные доски; г — сегментный; г’ — развально-сегментный; г» — брусово-сегментный; d — круговой; 1 — необрезные доски; 2 — обрезные доски; 3 — рейка; 4- брусья; 5 — части бревен в виде секторов; 6 — части бревен в виде сегментов; 7 — односторонне- обрезные доски

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

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

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

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

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

Индивидуальный раскрой крупных бревен и бревен, имеющих внутреннюю гниль, осуществляют круговым способом .

Переработка круглого леса методом фрезерования

Формирование сечения пиловочного сырья фрезерованием производят с совмещением этого метода с пилением. При этом применяют три основных схемы раскроя:

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

Двухкантный брус — это полуфабрикат для дальнейшего производства обрезных пиломатериалов делением бруса на доски.

Основные методы раскроя бревен фрезерованием
а — получение двухкантного бруса на головном станке; б — получение двухкантного бруса и необрезных досок; в — получение профильного бруса; г — получение длинных обрезных пиломатериалов; д — получение обрезных пиломатериалов различной длины; е — получение обрезных пиломатериалов различной длины и ширины; 1 — зона пиломатериалов; 2 — обрезные пиломатериалы; 3 — фигурный брус; 4 — двухкантный брус; 5- необрезные пиломатериалы

Понятие постава на распиловку круглого леса

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

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

При распиловке вразвал постав реализуется цифровым рядом, показывающим толщину выпиливаемых досок в миллиметрах:

19-19-32-32-19-19.

Данный ряд цифр означает, что из центральной части бревна выпиливаются две доски толщиной 32 мм, а из боковых частей – четыре доски толщиной 19 мм.

При развале с брусовкой, например, постав записывают двумя рядами из цифр, для распиловки бревна (первый проход) и бруса (второй проход):

19-19-150-19-19 (первый проход);

19-32-40-40-32-19 (второй проход).

Как и в предыдущем примере, данные цифры означают, что на головном станке первого ряда, на котором распиливается бревно, получают один брус толщиной 150 мм и, соответственно, четыре необрезные доски по 19 мм (по две с каждой стороны), а на станке второго ряда распиливают полученный брус на доски толщиной 40, 32 и 19 мм.

При распиловке бревна на однопильных станках постав определяет порядрк раскроя.

Составление поставов

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

Основные правила составления постава :

• поставы должны быть симметричными;
• в одном поставе не должно быть досок, различных по толщине менее чем на 5 мм;
• составление постава начинайте с наиболее крупных по сечению пиломатериалов;
• размеры толщин досок должны уменьшаться от оси бревна к периферии;
• не предусматривайте на краю постава выпиловку более двух тонких (16, 19 мм) досок при раскрое сырья на лесопильных рамах;
• высоту бруса на первом проходе выбирайте по ширине ведущих в спецификации по размерам толщин досок;
• пласть бруса, пропиленная на втором проходе, распиливайте на доски равной толщины;
• при составлении поставов на пиломатериалы без задания по спецификации применяйте табличный или графический способы;
• при распиловке с использованием метода с брусовкой толщину бруса определяйте из соотношения (0,06-0,08) вершинного диаметра бревна – d;
• постав не должен превышать величину максимального охвата диаметра бревна;
• наименьшие толщины центральных досок определяйте по данной таблице :

Графический метод составления поставов

Составить рациональный постав в соответствии с ГОСТами можно и без указания конкретных размеров по сечению (без заданий в виде спецификаций) – с помощью специальных графиков.

Пример использования графика предельных толщин пиломатериалов по П.П. Аксенову

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

График оптимальных толщин пиломатериалов по Г.Г. Титкову

Программа предназначена для оптимизации раскроя профиля и других длинномерных материалов (брус, бревно, труба, подоконник).
Использован алгоритм "плотной укладки", то есть взятое изделие укладывается на самый короткий остаток заготовки, на который она помещается. Если никуда не помещается, берется новая заготовка. Задачей оптимизации является нахождение последовательности изделий, при которой будет использовано меньше заготовок и будет больше длина деловых обрезков. На первом такте, изделия размещаются на хлыстах в случайном порядке. Возникает "начальная популяция". В процессе решения, популяция мутирует и размножается, неудачные экземпляры погибают, а лучшие продолжают эволюцию. Всё, как в животном и растительном мире + искусственный отбор.

Живое демо на сайте

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

Преимущества

• Окнософт:cutting обеспечивает карты распила высокого качества. Многочисленные внедрения подтверждают реальный коэффициент обрези не более 1% при оптимизации партий от 30 контуров (~120 отрезков)
• Для чтения исходных данных и записи результатов раскроя, программа использует простые форматы текстовых файлов, что упрощает интеграцию с учетными системами, внедренными у заказчика
• При необходимости, раскрой может выполняться под Linux или OS X в браузере или Node.js с передачей параметров через url, web-socket или объекты javascript

Алгоритмы линейного оптимизатора

В окнософт:каттинге использован генетический алгоритм. Суть его вот в чем:
Назовем каждое распределение изделий по хлыстам решением. Определим целевую функцию, позволяющую сравнивать качество решений. Сформируем несколько произвольных решений, назовем их поколением. Определим правила получения следующего поколения. Экземпляры с лучшей целевой функцией передают большую часть своего "генофонда", это наш "искусственный отбор". Теперь остается предоставить систему самой себе, пусть мутирует и оптимизирует результаты раскроя
В процессе разработки испытывался метод "Монте-Карло", когда наши "экземпляры" являются случайными и не зависят друг от друга и "Муравьиные алгоритмы"(ACO- ant colony optimisation). Все методы показали себя вполне работоспособным, но генетический алгоритм оказался чуть более эффективным

Варианты поставки

Есть два варианта поставки модуля раскроя Окнософт:cutting - в составе комплексного решения Управление позаказным производствм и в виде отдельного исполняемого файла. Взаимодействие с раскройной программой при первом сценарии, полностью скрыто от пользователя. Оператор работает со стандартными документами 1С:

• На основании заказов покупателей формируется план производства
• На основании плана - сменные задания со списком продукции и необходимых материалов
• Внутри задания на производство происходит оптимизация раскроя
• В процессе оптимизации, программа забирает из незавершенного производства деловую обрезь и помещает в ячеистый склад вновь образовавшиеся деловые обрезки
• Сменное задание умеет печатать бланки раскроя при ручном производстве или формировать файлы для станков с ЧПУ
• Так же, из сменного задания печатаются этикетки для отрезаемых изделий и схемы раскладки в телеги и пирамиды
• На основании заданий на производство формируются требования - накладные для передачи материалов в цех с учетом потребности и нормоупаковок

Программный интерфейс (API линейного раскроя)

Файл входных данных - setup.ini, помещается в папку с исполняемым файлом.
Файлы выходных данных - result.txt, resultproduct.txt и resultstick.txt - формируются в той же папке.
Скачать файлы с демо-данными Окнософт:cutting можно по ссылке в конце страницы. В файлх используются следующие теги:

• Outputvariant - структура выходного файла файла. Возможные значения: tab, oknosoft, по умолчанию oknosoft
  • В варианте "oknosoft", формируются файлы resultproduct.txt и resultstick.txt с информацией о размещении изделий на заготовках и образовавшейся обрези
  • В варианте "tab" выводятся пять значений, разделенных символами "tab": длина изделия, номер хлыста, длина хлыста, номер реза и остаток заготовки
• Algorithm - используемый алгоритм. Возможные значения: random, conservative, genetic, по умолчанию genetic
  • Random- случайный перебор вариантов
  • Conservative- экземпляры следующей итерации происходят от одного "родителя"
  • Genetic- от двух родителей
• Variation - изменчивость, параметр алгоритмов "conservative" и "genetic". Чем выше, тем меньше потомство "похоже" на родителей. По умолчанию 1.
• Generations - количество итераций алгоритма, по умолчанию 40000
• Persons - количество "экземпляров" в "популяции", количество решений используемых в одной итерации. В алгоритме "random" просто делается generations*persons итераций с одним экземпляром(решением)
• KnifeWidth - ширина пилы
• StickLength - длина нового хлыста
• Products - длина изделия
• Scraps - длина обрезка, используемого в раскрое
• Wrongsnipmin – минимальная длина «плохого» образка
• Wrongsnipmax – максимальная длина «плохого» обрезка
  В результатах оптимизации не будет обрезков с длиной между Wrongsnipmin и Wrongsnipmax

Парный раскрой

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

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

Раскрой большого числа изделий

С одной стороны, для достижения высокого качества оптимизации, на вход программы должно поступать значительное количество изделий разной длины, чтобы оптимизатору было "что сортировать". С другой, при очень больших партиях, снижается вероятность нахождения максимума при фиксированном числе итераций перебора. Эксперименты показали, что оптимальной является партия в 60 – 120 заготовок (что соответствует такту производства 30-60 изделий при парном раскрое). Если необходимо оптимизировать более 120 заготовок, лучших результатов можно добиться, разделив задачу на N частей и выполнив последовательные оптимизации для каждой части. Обработка формирования пачек заданий на производство умеет группировать продукции по видам профиля и подбирать в сменные задания изделия с максимальной дисперсией, избавляя оператора от рутинной работы по составлению производственных документов

Скачать примеры раскроя и документацию

• Демо карт одинарного и двойного распила: 60.01 Листы раскроя
• Документация и примеры файлов:

В математике сети дорог (автомобильных и не только) представляются взвешенным графом. Населенные пункты (или перекрестки) - это вершины графа, ребра - дороги, веса ребер - расстояния по этим дорогам.

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

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

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

Несколько важных понятий и условностей

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

2. Матрица кратчайших расстояний (МКР) – ее маленький и простой пример можно найти во многих дорожных атласах. Эта табличка обычно называется примерно так: «расстояния между наиболее важными городами». Она выглядит как часть матрицы ниже или выше главной диагонали (из верхнего левого в нижний правый угол), потому что с другой стороны главной диагонали точно такие же цифры, другими словами элемент М(i,j)= М(j,i). Это происходит, потому что граф, как говорят математики, неориентированный. Строки и столбцы соответствуют городам (вершинам графа). В реальности такая таблица намного больше, так как в вершины графа, кроме городов, входят все деревни и перекрестки, но напечатать такую большую таблицу в атласе, естественно, невозможно.

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

Наша МКР может быть: а) известна заранее, потому что мы ее подсчитали одним из методов поиска МКР; б) мы можем не знать МКР, а определять ее построчно по мере необходимости. Построчно – это значит, что для требуемой строки рассчитываются расстояния только от соответствующей ей вершины до остальных вершин, например, методом Дейкстры.

3. Еще пара понятий. Эксцентриситет данной вершины – это расстояние от этой вершины до самой удаленной от нее. Радиус графа – это наименьший из эксцентриситетов всех вершин. Центр графа – вершина, эксцентриситет которой равен радиусу.

Как это выглядит на практике. Центр дорожной сети – это город или перекресток, наименее удаленный от всех остальных пунктов этой сети. Радиус – максимальное расстояние от этого центрального узла до самого удаленного.

4. Степень вершины – количество ребер, которое присоединено к вершине.
У графов дорожных сетей, средняя степень всех вершин находится в районе от 2 до 4. Это вполне естественно – сложно и дорого строить перекрестки с большим количеством примыкающих дорог, не менее сложно потом пользоваться такой дорожной сетью. Графы, с невысокой средней степенью вершин называются разреженными, как видим, графы дорожных сетей именно такие.

Задача 1. Поиск радиус и центра графа по матрице кратчайших расстояний

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

Как задача решается в общем случае? Полным просмотром МКР. Ищется максимальный элемент в строке (эксцентриситет каждой вершины), а потом из этих максимальных элементов находится минимальный.

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

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

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

Допустим, мы нашли значения всего лишь в двух строках А и В. При этом, максимальное значение в строке А равно минимальному значению в строке В (эта величина будет стоять на пересечении столбца А и строки В). Несложно доказать, что А – центр графа, а найденное значение – его радиус. Задача решена.

Здорово, но такая ситуация на графах дорожных сетей маловероятна и решать задачу таким образом не получится. Поступим хитрее.
Возьмем пару строк В1 и В2. Из них сформируем вектор М таким образом: М(i)=max. Несложно доказать, что если для всех строк i значение min(M(i)) равно максимальному значению в столбце А, то, опять таки, А – центр, а найденное min(M(i)) – радиус.
Если пары строк окажется недостаточно, можно взять несколько строк, например три: B1, B2 и B3, тогда М(i)=max. Особенность графов дорожных сетей состоит в том, что много строк не понадобится (удастся уложиться в десяток). Это легко проверить, поэкспериментировав на существующих графах сетей, скачав их из интернета: ссылка .

В общем случае и с точки зрения математики это, конечно, не так. Вполне можно построить теоретический граф в котором придется использовать очень много строк В (почти все, кроме, А). Вот только невозможно построить реальную дорожную сеть такого вида - денег не хватит.

Осталась последняя задача. Как быстро найти эти удачные строки B1, B2 и т.д. Для графов реальных дорожных сетей это сделать очень просто и быстро. Это будут максимально удаленные друг от друга вершины, но не обязательно самые удаленные (говоря математически, находить диаметр графа нам не требуется). Берем любую вершину, находим для нее самую дальнюю, для новой опять самую дальнюю и так, пока пара вершин не окажется самой дальней друг для друга.

Мы получили пару вершин В1 и В2. Находим для пары вектор М, как описано выше. Строка, в которой мы нашли min(M(i)) - претендент на центр, обозначим его А. Если в столбце А значение min(M(i)) – максимальное, то уже найдены центр и радиус. Если же нет, значит максимальное значение в столбце А соответствует расстоянию до другой вершины (не B1 и не B2). Значит, мы получили новую вершину B3 в список на поиск вектора М. Как вариант, можно и для B3 поискать самую удаленную вершину и если она не В1 и не B2, добавить ее как В4. Таким образом, увеличиваем список вершин B, пока центр и радиус не будут найдены.

Более строго, с алгоритмом и нужными доказательствами этот алгоритм описан в , там же приведены результаты его использования на некоторых графах дорожных сетей США, а в ссылка и ссылка он описан менее академически, но более понятно.

Задача 2. Поиск матрицы кратчайших расстояний

Наиболее популярные алгоритмы поиска МКР (Флойда-Уоршелла, например) описаны . Все они универсальные, причем один из них – алгоритм Дейкстры с двоичной кучей – учитывает такое понятие как разреженный граф. Однако он тоже не использует особенности дорожных сетей.

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

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

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

Пусть А – вершина со степенью 2 и присоединена она в вершинам В1 и В2. Если маршрут В1-А-В2 длиннее или равен ребру В1-В2, через точку А не проходит никаких маршрутов, кроме маршрутов к самой точке А (все остальные проходят через В1-В2). Значит, точку А можно удалить. В ином случае, т.е. если В1-А-В2 короче В1-В2 или ребра В1-В2 вообще нет, вершину А можно удалить, установив вес ребра В1-В2 равным сумме весов: |В1-А|+|А-В2|. Маршрут от А до других точек проходит либо через В1, либо через В2, если будут известны расстояния для В1 и В2, расстояния от А так же легко вычислить.

По такому же принципу можно удалить вершину с любой степенью, заменяя, по мере необходимости, Вi-А-Вj на Bi-Bj. Правда, нужно понимать, что чем больше степень вершины, тем больше возможных ребер надо проверить. Для вершины степени n это число равно n(n-1)/2.

Теоретически, таким способом можно удалить все вершины в любом графе, однако, в общем случае, нас ждет неприятность, связанная с ростом числа ребер. При удалении вершины со степенью n, степень вершин, смежной с удаляемой, может: уменьшится на -1, не измениться, увеличится до n-2. Отсюда следует, что при удалении вершин со степенью 3 и выше, степень остальных вершин, в общем случае, растет, граф становится все менее разреженным и, в конце концов, удаление вершин превратится в довольно трудоемкую задачу. Алгоритм, в общем случае, является крайне трудоемким и практически бесполезным, но это именно в общем случае.

Графы дорожных сетей имеют уникальную особенность такого рода: многие вершины могут быть удалены не только без роста, но и с уменьшением степени смежных вершин. Причем, если некоторая вершина не может быть «успешно» удалена сейчас, она может быть «успешно» удалена позже, после удаления некоторых, смежных с ней вершин.

Соответственно, нам просто требуется на каждом шаге правильно выбирать вершины на удаление, начиная с тех, которые удаляются более «удачно».

Сам алгоритм более подробно можно посмотреть

Предыдущая статья: Углерод — характеристика элемента и химические свойства Следующая статья: Чему равна скорость света