Построение логистической инфраструктуры в виде двумерной мозаики

Построение логистической инфраструктуры в виде двумерной мозаики

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

Full description

Saved in:
Bibliographic Details
Date:2014
Main Authors: Донец, А.Г., Шулинок, И.Э.
Format: Article
Language:Russian
Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2014
Series:Теорія оптимальних рішень
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/111513
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Построение логистической инфраструктуры в виде двумерной мозаики / А.Г. Донец, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 76-83. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-111513
record_format dspace
spelling nasplib_isofts_kiev_ua-123456789-1115132025-02-09T22:09:10Z Построение логистической инфраструктуры в виде двумерной мозаики Побудова логістичної інфраструктури у вигляді двовимірної мозаїки Building logistics infrastructure in a two-dimensional mosaic Донец, А.Г. Шулинок, И.Э. Рассматриваются методы построения дискретных образов из элементов, которые называются шаблонами. Проблема сводится к решению системы линейных уравнений в классе вычетов по конечному модулю 2. Розглядаються методи побудови дискретних образів з елементів, які називаються шаблонами. Проблема зводиться до розв’язання системи лінійних рівнянь у класі лишків за кінцевим модулем 2. Paper deals with constructing discrete images of the elements called templates. The problem is reduced to solving a system of linear equations over a finite residue class modulo 2. 2014 Article Построение логистической инфраструктуры в виде двумерной мозаики / А.Г. Донец, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 76-83. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/111513 519.8 ru Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description Рассматриваются методы построения дискретных образов из элементов, которые называются шаблонами. Проблема сводится к решению системы линейных уравнений в классе вычетов по конечному модулю 2.
format Article
author Донец, А.Г.
Шулинок, И.Э.
spellingShingle Донец, А.Г.
Шулинок, И.Э.
Построение логистической инфраструктуры в виде двумерной мозаики
Теорія оптимальних рішень
author_facet Донец, А.Г.
Шулинок, И.Э.
author_sort Донец, А.Г.
title Построение логистической инфраструктуры в виде двумерной мозаики
title_short Построение логистической инфраструктуры в виде двумерной мозаики
title_full Построение логистической инфраструктуры в виде двумерной мозаики
title_fullStr Построение логистической инфраструктуры в виде двумерной мозаики
title_full_unstemmed Построение логистической инфраструктуры в виде двумерной мозаики
title_sort построение логистической инфраструктуры в виде двумерной мозаики
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2014
url https://nasplib.isofts.kiev.ua/handle/123456789/111513
citation_txt Построение логистической инфраструктуры в виде двумерной мозаики / А.Г. Донец, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 76-83. — рос.
series Теорія оптимальних рішень
work_keys_str_mv AT donecag postroenielogističeskoiinfrastrukturyvvidedvumernoimozaiki
AT šulinokié postroenielogističeskoiinfrastrukturyvvidedvumernoimozaiki
AT donecag pobudovalogístičnoíínfrastrukturiuviglâdídvovimírnoímozaíki
AT šulinokié pobudovalogístičnoíínfrastrukturiuviglâdídvovimírnoímozaíki
AT donecag buildinglogisticsinfrastructureinatwodimensionalmosaic
AT šulinokié buildinglogisticsinfrastructureinatwodimensionalmosaic
first_indexed 2025-12-01T08:10:20Z
last_indexed 2025-12-01T08:10:20Z
_version_ 1850292697592496128
fulltext Теорія оптимальних рішень. 2014 76 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Рассматриваются методы построения дискретных образов из элементов, которые называются шаблонами. Проблема сводится к решению системы линейных уравнений в классе вычетов по конечному модулю 2.   А.Г. Донец, И.Э. Шулинок, 2014 УДК 519.8 А.Г. ДОНЕЦ, И.Э. ШУЛИНОК ПОСТРОЕНИЕ ЛОГИСТИЧЕСКОЙ ИНФРАСТРУКТУРЫ В ВИДЕ ДВУМЕРНОЙ МОЗАИКИ Логистическая инфраструктура представляет собой набор элементов, выполняющих важные задачи материально-технического обеспечения логистических процессов. Это определение свидетельствует о необходимости эффективного использования материально-технической инфраструктуры в процессе координации и обслуживания производственно-сбытовых цепочек. На основе ранее произведенных исследований в данной статье предлагается использовать методологию теории арифметических графов к оценке интегрального потенциала логистической инфраструктуры с учетом ее жизненного цикла. Пусть задано двумерное поле и рассмотрим вопрос о построении на нем дискретных образов. Как и раньше * , будем полагать, что поле   ,ij m n    задано в виде прямоугольника, разбитого на N mn клеток, где m – число последовательных горизонтальных клеток (строк), а n – число последовательных вертикальных клеток (столбцов). По умолчанию будем считать два поля с mnN  клетками идентичными. Множеству K цветов поставим в соответствие множество чисел  0,1,2,..., 1Q K  . Пусть имеется набор связных фигур, состоящих из клеток опре- деленного цвета (не равных 0) и называемых * Шулинок И.Э. Проблемы построения двухцветной линейной мозаики // Теория оптимальных решений. – К.: Ин-т кибернетики имени В.М. Глушкова НАН Украины, 2002. – № 9. – С. 126 – 135. ПОСТРОЕНИЕ ЛОГИСТИЧЕСКОЙ ИНФРАСТРУКТУРЫ… Теорія оптимальних рішень. 2014 77 блоками или шаблонами  1 2, , . . . , pS s s s . Здесь под связной фигурой подразумывается множество клеток, каждая из которых имеет общую сторону хотя бы с одной клеткой из этого множества. Предполагается, что количество каждого типа шаблонов ограничено числом  tr , где pt ,...,2,1 . Построение произвольных изображений осуществляется с помощью наложения на поле разных шаблонов, имеющих небольшие размеры и определенную раскраску. При этом операция наложения на одну клетку различных цветов задается как бинарная операция на множестве Q . Необходимо решить задачу, существует ли такой набор из наличного запаса шаблонов, который при определенном наложении на поле Π составил бы заданное изображение. Если в поле Π 1m , а 1n , то оно является строкой, и соответствующая задача называется задачей о построении линейной мозаики. Ее решению посвящена работа [*], где данная задача и решена. Если же 1, nm , то соответствующая задача называется задачей о двумерной мозаике. В данной статье вводятся необходимые определения, понятия и заложены основы ее решения. Прежде всего, необходимо точно определить операцию наложения цветов. В зависимости от конкретной задачи, под операцией накладывания (сложения) может подразумеваться различное содержание. В общем виде операцию накладывания можно задавать бинарной таблицей. Решить задачу о мозаике означает найти, как при заданном способе накладывания раскрашенных шаблонов построить заданный образ на плоскости Π. Операция накладывания цветов может задаваться произвольным способом в виде цветовой таблицы, бинарной таблицы и таблицы сложения в классе вычетов по определенному модулю. Далее приведен пример цветовой табл. 1, где в первом столбце и первой строке указаны цвета, а на пересечении соответствующей строки и соответствующего столбца указан цвет как результат накладывания (сложения). Первым указан белый цвет, играющий при сложении роль «нуля», так как он при сложении (обозначен +) не изменяет другой цвет. ТАБЛИЦА 1. Пример накладывания цветов  Белый Голубой Желтый Красный Синий Белый Белый Голубой Желтый Красный Синий Голубой Голубой Синий Красный Синий Красный Желтый Желтый Красный Голубой Белый Голубой Красный Красный Синий Белый Желтый Белый Синий Синий Красный Голубой Белый Красный Очевидно, что операция сложения должна отвечать некоторым правилам. Например, она должна быть коммутативной. В нашем примере это требование выполняется, так как таблица симметрична. Если перенумеровать цвета с А.Г. ДОНЕЦ, И.Э. ШУЛИНОК Теорія оптимальних рішень. 2014 78 условием, что белый цвет = 0, голубой = 1, желтый = 2, красный = 3 и синий = 4, то сложение цветов можно записать в виде бинарной табл. 2. ТАБЛИЦА 2. Числовое представление табл. 1 + 0 1 2 3 4 0 0 1 2 3 4 1 1 4 3 4 3 2 2 3 1 0 1 3 3 4 0 2 0 4 4 3 1 0 3 Однако данная таблица обладает недостатками, самый главный из которых состоит в том, что здесь сложение не удовлетворяет аксиоме ассоциативности. Например,   233321  . С другой стороны   2101321  . Поэтому к операции сложения выдвигаются требования, чтобы она была симметрична и ассоциативна. Таким свойством обладает групповая операция сложения, в качестве которой может выступать сложение в классе вычетов по конечному модулю K. Если переменные принимают два значения 0 или 1, то в качестве операции сложения можно выбрать логическую операцию дизъюнкции, когда xyyxyx  . Однако при этом происходит накопление единиц на клетках поля, которые нельзя в дальнейшем устранить. В практическом смысле эта операция мало привлекательна. Поэтому из всех возможных определений выберем наиболее существенное, когда эта операция идентична сложению двух чисел по Kmod . Рассмотрим сначала самый простой случай 2K . Тогда все шаблоны будут одноцветными, так как число 0, естественно, означает отсутствие какого-либо цвета (белый цвет). Так как шаблон можно накладывать любой стороной (внешней и обо- ротной), а также поворачивать в плоскости на любой угол, кратный 90 ° , то проще считать, что мы имеем дело с разными шаблонами, которые всегда располагаются фиксированным образом в пространстве. Определение. Назовем меткой шаблона самую левую среди самых верхних клеток шаблона. Заполним все поле всеми возможными способами множеством различных шаблонов. Каждому шаблону (точнее, его месту на плоскости П) поставим в соответствие переменную  rixi ,...,2,1 , равную 0 или 1. Тогда задача о возможности построения необходимой мозаики на поле Π при заданном множестве шаблонов  1 2, , . . . , pS s s s сводится к решению системы линейных уравнений ПОСТРОЕНИЕ ЛОГИСТИЧЕСКОЙ ИНФРАСТРУКТУРЫ… Теорія оптимальних рішень. 2014 79 1 ; 1,2,..., . r i j i x b j N    (1) Здесь сложение для каждой клетки происходит по заданной операции сложения, а i -ой шаблон учитывается только тогда, когда его пересечение с j - ой клеткой не пусто. В зависимости от видов и количества шаблонов возникает задача с огромным количеством переменных, число которых в большинстве случаев намного превышает число равенств. Решение задачи зависит от искусства определения ранга этой системы. Рассмотрим допустимое поле двумерных шаблонов и их уравнения. Поскольку шаблоны на плоском двумерном поле могут размещаться разными способами, необходимо ввести для каждого из них такое обозначение, чтобы однозначно определять на поле его каждую клетку, если известна координата его метки. Пусть задан образ, представленный на поле Π с размерами 42,N  где 7m и 6n (рис. 1). Несложно убедиться, что этот образ составлен с помощью 3-х типов шаблонов (на рис. 1, справа). В этом образе задействовано три шаблона первого типа, два из которых расположены так, как он представлен справа на рис. 1, а один в перевернутом виде. Остальные два типа представлены в единственном экземпляре, при этом второй в перевернутом виде. 1 . 2 . 3 . РИС. 1. Образ, составленный из 3-х типов шаблонов Будем считать два типа положений шаблона разными, если их нельзя совместить параллельным переносом. Очевидно, что таких типов не больше 8. Пронумеруем клетки поля от 1 до N сначала по первой строке, затем по второй и так до конца. Зная координату метки шаблона, можно однозначно расположить его на поле. А.Г. ДОНЕЦ, И.Э. ШУЛИНОК Теорія оптимальних рішень. 2014 80 Рассмотрим всевозможные положения указанных на рис. 1 шаблонов (рис. 2) (метка обозначена белым кружочком). В нашем примере шаблон 1s имеет 4 типа положений, шаблон 2s – 8 типов, а 3s – только один тип. Для простоты обозначений будем считать все типы положений новыми шаблонами. Таким образом, с учетом всех положений имеем 3 разных шаблона, превращающихся в 13 шаблонов, т. е.   131,  isS i . РИС. 2. Типы положений для каждого шаблона Рассмотрим подробнее шаблон 1 на рис.1, изображенный на рис. 3 в четырех возможных позициях. Обозначим их 1 2 3, ,s s s и 4s . Зная координату метки шаблона, можно однозначно расположить его на поле. Если координату произвольного шаблона обозначить , то любой шаблон можно задать его уравнением, которое в общем виде будет выражаться через данную координату. Для этого каждую клетку шаблона в порядке их следования на поле выразим через координату метки и параметры поля m и n . 1s s2 3s 4s РИС. 3. Шаблон и его возможные положения ПОСТРОЕНИЕ ЛОГИСТИЧЕСКОЙ ИНФРАСТРУКТУРЫ… Теорія оптимальних рішень. 2014 81         1 2 3 4 ( ) , 1, 1, 2 , 2 1 ; ( ) , 1, , 2 , 2 1 ; ( ) , 2, , 1, 2 ; ( ) , 1, 2, , 2 . s n n n s n n n s n n n s n n                                   (2) Для линейного поля, рассмотренного [*], можно также составить уравнение шаблона, не зависисящее от параметра ,n и может быть записано следующим образом:    , 1,..., 1 .i is s      В общем случае в зависимости от вида шаблона и величины поля координата  может принимать только ограниченные значения. Множество допустимых значений  определяет множество допустимых положений шаблона (или, точнее, его метки) на заданном поле. На рис. 4 показаны допустимые значения координаты  для каждого шаблона из рис. 3 на поле  размерности 1234 N . В сумме число положений шаблонов равно 14. 1 2 1 2 1 1 4 5 4 5 4 4 7 7 1( )s  2( )s  3( )s  4( )s  РИС. 4. Допустимые положения меток шаблона Обозначим изображение, которое необходимо построить с помощью шаблонов, вектором  1 2, , . . ., ,Nb b b b где ib   0,1 , 1 .i N  Каждому допустимому положению шаблона поставим в соответствие переменную ( 1,2,. . . ,14),jx i  принимающую значения 0 или 1 в зависимости от того, принимает ли данный шаблон участие в построении изображения. Если вместо координаты  для каждого шаблона подставить значения из рис. 4, то каждой переменной будет сопоставлен кортеж, определяющий номера клеток, на которые накладывается соответствующий шаблон . 1 2 3 4 5 6 7 8 9 10 11 12 13 (1,2,5,7,8), (2,3,6,8,9), (4,5,8,10,11), (5,6,9,11,12), (1,2,4,7,8), (2,3,5,8,9), (4,5,7,10,11), (5,6,8,11,12), (1,3,4,5,6), (4,6,7,8,9), (7,9,10,11,12), (1,2,3,4,6) , (4 c c c c c c с c c c c c c              14,5,6,7,9), (7,8,9,10,12).c  Суммируя для каждой клетки поля переменные, в кортежи которых входит номер этой клетки, получаем систему уравнений (mod2), 1,2, . . ., . i i j C j x b j N    (3) А.Г. ДОНЕЦ, И.Э. ШУЛИНОК Теорія оптимальних рішень. 2014 82 На рис. 5 показаны допустимые положения всех четырех шаблонов и указаны обозначающие их переменные. Внутри шаблона попадают номера клеток, определяющие каждый кортеж  Nici 1 . Следует заметить, что система (3) для произвольного множества шаблонов содержит N уравнений, а число переменных может быть произвольным в зависимости от количества допустимых положений меток шаблонов. Для единственности решения системы уравнений это обстоятельство иногда играет существенную роль. 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 4 5 6 4 5 6 4 5 6 4 5 6 4 5 6 4 5 6 4 5 6 7 8 9 7 8 9 7 8 9 7 8 9 7 8 9 7 8 9 7 8 9 1 0 1 1 1 2 1 0 1 1 1 2 1 0 1 1 1 2 1 0 1 1 1 2 1 0 1 1 1 2 1 0 1 1 1 2 1 0 1 1 1 2 1 x 2 x 3 x 4 x 5 x 6 x 7 x 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 4 5 6 4 5 6 4 5 6 4 5 6 4 5 6 4 5 6 4 5 6 7 8 9 7 8 9 7 8 9 7 8 9 7 8 9 7 8 9 7 8 9 1 0 1 1 1 2 1 0 1 1 1 2 1 0 1 1 1 2 1 0 1 1 1 2 1 0 1 1 1 2 1 0 1 1 1 2 1 0 1 1 1 2 8 x 9 x 10 x 11 x 12 x 13 x 14 x РИС. 5. Переменные для всех положений шаблона Теперь, глядя на рис. 5, можно легко составить систему уравнений (4) для наших шаблонов ПОСТРОЕНИЕ ЛОГИСТИЧЕСКОЙ ИНФРАСТРУКТУРЫ… Теорія оптимальних рішень. 2014 83 )4(.2mod ........ ....... ........ ...... ...... ....... ...... ....... ..... ......... ......... .......... 121484 11118743 10141173 914131110642 81410865321 714131110751 61312109842 5139876431 41312109753 312962 2126521 112951                                bxxx bxxxxx bxxxx bxxxxxxx bxxxxxxxx bxxxxxxx bxxxxxxx bxxxxxxxx bxxxxxxx bxxxx bxxxxx bxxxx В i -й строке суммируются переменные, кортежи которых содержат i -ю клетку, а в правой части должно быть ,1 .ib i N  Вопрос о существовании решения данной системы уравнений представляет самостоятельный интерес. Как правило, количество переменных в ней больше количества уравнений, что позволяет найти хотя бы одно решение. А.Г. Донець, І.Е. Шулінок ПОБУДОВА ЛОГІСТИЧНОЇ ІНФРАСТРУКТУРИ У ВИГЛЯДІ ДВОВИМІРНОЇ МОЗАЇКИ Розглядаються методи побудови дискретних образів з елементів, які називаються шаблонами. Проблема зводиться до розв’язання системи лінійних рівнянь у класі лишків за кінцевим модулем 2. A.G. Donets, I.E. Shulinok BUILDING LOGISTICS INFRASTRUCTURE IN A TWO-DIMENSIONAL MOSAIC Paper deals with constructing discrete images of the elements called templates. The problem is reduced to solving a system of linear equations over a finite residue class modulo 2. Получено 31.03.2014

Similar Items