Алгоритмизация приближенных методов решения задачи унификации
В.
Н. ИзотовБиблиографическое описание статьи для цитирования:
Изотов
В.
Н.,
Морозова
Т.
В. Алгоритмизация приближенных методов решения задачи унификации // Научно-методический электронный журнал «Концепт». –
2015. – № 10 (октябрь). – С.
21–25. – URL:
http://e-koncept.ru/2015/15339.htm.
Аннотация. Рассмотрены алгоритмы приближенных методов решения одноуровневой многомерной задачи унификации. Приведено обоснование алгоритма отбора переменных, использующего приближённые алгоритмы. Доказана точность получаемых решений, найденных с помощью алгоритма отбора переменных. Исследована эффективность алгоритма.
Ключевые слова:
задача унификации, алгоритм решения, доказательство алгоритма, исследование эффективность алгоритма
Текст статьи
Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 1
ART15339УДК 330.42:519.71
Изотов Виктор Николаевич,
доктортехническихнаук, профессор кафедрыэкономикии финансовТульскогофилиалаФГБОУ ВПО «Российская академия народного хозяйства и государственной службы при Президенте Российской Федерации», г. Тулаizotovvntula@mail.ru
Морозова Татьяна Владиславовна,начальник аналитического отдела ГУТульской области «Тулаупрадор», г. Тула
tanek171290@yandex.ru
Алгоритмизация приближенных методов решения задачи унификации
Аннотация.Рассмотрены алгоритмы приближенных методов решения одноуровневой многомерной задачи унификации. Приведено обоснование алгоритма отбора переменных, использующего приближённые алгоритмы. Доказана точность получаемых решений, найденных с помощью алгоритма отбора переменных. Исследована эффективность алгоритма.Ключевые слова:задача унификации, алгоритм решения, доказательство алгоритма, исследование эффективности алгоритма.Раздел:04 экономика.
Среди приближенных методов решения задачи унификации наибольшее распространение получили алгоритмы с апостериорной оценкой их точности [1]. Относительная точность определяется в них по формуле учитывается, что xi=1yi):.(1)В основу первого приближенного алгоритма положен тот факт, что,исходя из особенностей построения оценочной матрицы W, единичные компоненты вектора , минимизирующего целевую функцию, следует искать после построения W, прежде всегосреди элементов множества . Поэтому целесообразно ограничиться рассмотрением только таких допустимых решений, для которых . Алгоритм, учитывающий данное обстоятельство,должен включать следующие этапы:1.Вычисление значения (W) .2.Исключение из рассмотрения всех строк матрицы и элементов вектора с номерами, не принадлежащими множеству I0(W . При этом получается новая исходная пара , .3.Применение алгоритма ветвей и границ к решению задачи с новой исходной парой для получения приближенного решения.Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 2
Этот метод дает наилучшее приближение, однакотрудоемкость вычисления существенно влияет на время решения задачи, так как построение осуществляется на каждом шаге вычисления, хотя число шагов и уменьшается в результате 2го этапа приближенного алгоритма.Второй приближенный алгоритм, в основе которого лежит идея «движения по градиенту», на 3м этапе вместо схемы ветвей и границ включает ряд шагов итерационного процесса, количество которых не может быть больше m. На первом этапе осуществляется построение оценочной матрицы, которая позволяет получить оценку «снизу» целевой функции на множестве продолжений частичного решения Z1,..., Zk). На втором этапе производится вычисление нижней границы H(Z1, ... , Zk и значений фиксируемых свободных переменных Zk+1, ... , Zp. На третьем этапе выполняется ряд шагов итерационного процесса, количество которых не может быть больше m. На первом шаге в качестве приближенного решения рассматривается вектор ,такой, что xi 1 , если ,и xi= 0 –в противном случае. Далее, для всех вычисляются показатели
,характеризующие степень изменения целевой функции при удалении iго типа изделия из предварительно полученного типоразмерного ряда. Затем определяется
.Если , то улучшить имеющее решение невозможно,и алгоритм заканчивает работу. Если , то отыскивается номер i0, для которого ,и для него полагается 0. При этом получается новое приближенное решение с меньшим значением S(x1, ... , xm . После этого переходят ко второму шагу и т.д. Этот алгоритм позволяет получить если не наилучшее как первый метод приближенное решение, то достаточно хорошее. Точность метода существенно зависит от точности построения Wна первом этапе. Здесь матрицаWстроится один раз. Третий приближенный алгоритм основан на вычислении специальных показателей Pi, характеризующих изменение величины S(x1, ... , xm при условии xi= 0 .
где –множество индексов переменных xi, вошедших в допустимое решение со значением xi=1;BD–множество индексов переменных xi , не вошедших еще в допустимое решение, то есть значения которых пока не определены.На каждом шаге алгоритма при условии элементы iвыводятся из множества BDи вводятся во множество D, а затем из множества BDудаляется элемент i0 , для которого.Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 3
Алгоритм заканчивает свою работу, когда все элементыiбудут введены из множестваBD. При этом множество Dбудет содержать решение задачи.На эффективность приближенных методов значительное влияние оказывает метод построения нижней границы, используемой для отсечения неперспективных ветвлений.Решение задачи унификации приближенными методами хотя и занимает незначительное время, но не всегда удовлетворяет требованиям точности. Решение же задач большой размеренности более 100x100 методом ветвей и границ требует относительно много машинного времени. Сокращение числа переборов допустимых решений в методе ветвей и границ может быть достигнуто применением дополнительной проверки на каждом шаге ветвления допустимого решения на оптимальность путем направленного решения двойственной задачи. Приближенное решение двойственной задачи сравнивается с найденным на данном шаге допустимым решением исходной задачи, и случай совпадения указывает на оптимальность целочисленного решения исходной задачи. В противном случае решение задачи продолжается методом ветвей и границ, причемпоиск и уточнение допустимого решения исходной задачи целесообразно осуществлять одним из приближенных методов.Рассматривая сущность направленного решения двойственной задачи,можно заметить, что это есть не что иное, как построение оценочной матрицы W, а приближенное двойственное решение есть результат вычисления оценки «снизу» целевой функции. Учитывая, что в основе применяемой усовершенствованной стратегии, обеспечивающей наибольшую точность нижней оценки, лежит идея «движения» в направлении получения максимальной величины (W, имеет смысл в качестве метода для нахождения допустимого решения исходной задачи выбрать второй приближенный метод, применяя в нем для повышения точности ту же усовершенствованную стратегию. Кроме того, анализируя алгоритм, а также принимая во внимание указанные особенности усовершенствованной стратегии и второго приближенного алгоритма, представляется возможным разработать новый алгоритм, включающий в себя достоинства приближенных методов и обеспечивающий получение точного решения задачи унификации.Алгоритм, основанный на использовании двойственного решения для отбора переменных, включаемых в решение задачи унификации, содержит следующие этапы:1.Нахождение двойственного решения(W с применением усовершенствованной стратегии. 2.Определение допустимого решения Sdс помощью второго приближенного алгоритма.3.Проверка допустимого решения на оптимальность путем сравнения с двойственным решением.4.Отбор переменных, включаемых в решение задачи.Алгоритм заканчивает работу, если доказана оптимальность допустимого решенияили все переменные после отбора включены в решение задачи. Если в результате отбора не все переменные вошли в решение, то к оставшимся переменным применяется тот же алгоритм, начиная с 1го этапа.2.Определение допустимого решения Sdс помощью второго приближенного алгоритма.3.Проверка допустимого решения на оптимальность путем сравнения с двойственным решением.4.Отбор переменных, включаемых в решение задачи.Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 4
Алгоритм заканчивает работу, если доказана оптимальность допустимого решения или все переменные после отбора включены в решение задачи. Если в результате отбора не все переменные вошли в решение, то к оставшимся переменным применяется тот же алгоритм, начиная с 1го этапа.Алгоритм отбора переменных представляет собой следующую последовательность действий.Если (W) , то вычислить .1.Просматриваются элементы вектора , полученного после построения матрицы W:аесли 0 и , то полагается xi 0 , а номер строки вводится во множество ;бесли 0 , вычислить –двойственное решение задачи при условии, что номер iисключен из множества U;весли , то полагается xi 1 , а номер iвводится во множество .2.Оставшиеся номера , не вошедшие во множества D0и D1, вводятся во множество . Затем для всех переменных алгоритм отбора повторяется, начиная с вычисления новых значений (W) , и , рассчитываемых для множества U= .Алгоритм заканчивает работу, когда множество пустое. Это означает, что получено оптимальное решение .Рассмотрим некоторые особенности применения данного алгоритма. Допустим, что заданы ограничения, когда, например, невозможно применение изделий iго типа для выполнения работ jго вида то есть исходные данные содержат элементы Gij= . Задача решается обычным способом, но во время решения может оказаться,что (W) = = . Тогда номера из множества вводятся во множестваD0и D1по правилу, определяемому элементами вектора , полученного на предыдущем этапе алгоритма.Необходимо доказать, что алгоритм отбора переменных за конечное число шагов обеспечивает нахождение точного решения задачи унификации. Для доказательства используется понятие тупиковой матрицы [2]. ОценочнуюматрицуWназывают тупиковой, если для всякого :1..2.
при ; Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 5
где –множество номеров i, для которых ;
–множество номеров i, соответствующих минимальным элементам в jм столбце матрицы W;
–минимальный элемент в jм столбце. Тупиковые матрицы в них дальнейшее увеличение (W невозможно являются наиболее перспективными –в смысле наилучшего (W) –оценочными матрицами. В такой матрице величины распределяются наиболее экономичным образом, поскольку в процессе построения матрицы Wк элементу wijдобавляется величина не более той, которая необходима для увеличения значения минимума в jм столбце. В наибольшей степени этим требованиям удовлетворяютматрицы, построенные с применением усовершенствованной стратегии. Для обоснования алгоритма отбора переменных необходимо доказать теорему.Теорема.Тупиковая матрица, построенная для оценки полинома целевой функциина множестве продолжений частичного решения , где , при k= m–1, приводит к точной оценке этого полинома.Полином может быть представлен в виде .(2)Необходимо определить, какой должна быть тупиковая матрица , построенная для оценки полинома , чтобы величина при произвольном значении представляла собой точную оценку.Вопрос о нижней оценке полинома целевой функции на множестве продолжений частичного решения Z1, ... , Zk сводится к вопросу о нижней оценке полинома на всем множестве решений, определяемом вектором .Определение. Матрица называется единичной, если для всякого число ненулевых компонентов вектора , где , не более единицы. Существует доказательство [3], чтоесли –единичная матрица, то оценка точная, а ее значение определяется по формулеИзотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 6
,
(3)где –множество номеров jiй строки матрицы , которые соответствуют минимальным элементам jго столбца.Если теперь рассмотреть вектор , где yi= 0, когда , и yi= 1–в противном случае, то нетрудно заметить, что вектору, минимизирующему полином , в качестве оптимального типоразмерного ряда соответствует множество , а в качестве областей использования изделий соответствуют множества . Другими словами, только единичная тупиковая матрица дает точную оценку полинома .Следовательно, при k= m–1 значение нижней границы для частичного решения (Z1, ... , Zk)
всегда будет точной оценкой, поскольку в этом случае тупиковая матрица всегда будет единичной.Из доказательства теоремы следует основной вывод, используемый при обосновании алгоритма отбора переменных. Если каждый элемент из множества рассматривать как последний элемент в этом множестве, а оставшиеся элементы–как частичное решение, то при наличии правила, устанавливающего оптимальное значение этого элемента в предположении, что частичное решение также оптимально, появится возможность поочередного отбора всех переменных для включения их в решение задачи унификации. Как следует из 3, указанное правило целесообразно основать на учете особенностей получаемого результата построения матрицы Wвектора , нулевые компоненты которого определены множеством . При этом нулевые значения вектора следует искать прежде всегосреди номеров , а единичные − среди номеров . Учитывая факт совпадения прямого и двойственного решения для оптимального вектора , целесообразно использовать их для поочередного установления оптимального значения каждого yi. Действительно, если после построения матрицы Wоставшаяся величина , то при yi= 1 Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 7
произойдет совпадение прямого и двойственного решенияв предположении, что частичное решение Z1, ... , Zk без элемента yiоптимально. Если же соотношение прямого и двойственного решений таково, что при , то удаление номера iиз типоразмерного ряда нецелесообразно, то есть принимается yi 0, что также обеспечивает совпадение этих решений в предположении оптимальности вектора Z1, ..., Zk при k=m–1. Поскольку вектор содержит конечное число элементов, с помощью данного алгоритма будет найдено точное решение задачи унификации за конечное число шагов. Результаты проверки эффективностиалгоритма приведены в таблице.
Результаты проверки эффективности метода отбора переменных
m
n
Алгоритм ветвей и границ,мин.\с.Предлагаемый метод, с.Время поиска 1го допустимого решения, с.
,
%
5
4
5–6
1–6
0\0,25
0,14
0,01
0
10
10
0,3–0,7
0,2–1
0\0,72
0,24
0,07
0
30
30
0–1
0–8
0\18,69
3,15
0,1
2,5
50
50
0,3–0,7
0,2–1
5\22,29
30,02
0,3
2,8
Проверка эффективности предлагаемого алгоритма показывает, что при небольших значениях mxnне более 20x20 для 80% решенных задач первое допустимое решение, получаемое с помощью второго приближенного алгоритма, совпадает с оптимальным. В остальных случаях отклонение 1го допустимого решения от оптимального не превышает 4%. Наибольшая эффективность алгоритмаотмечается при больших значениях размеренности матрицы .Таким образом, алгоритм отбора переменных может быть применен для получения точного решения многомерной задачи унификации изделий, в том числе и системного ПО, по экономическому критерию. Использование в этом методе усовершенствованного алгоритма построения оценочной матрицы и второго приближенного алгоритма увеличивает число включаемых в решение переменных за один просмотр множества, посколькуи в томи в другом алгоритмах учтены свойства единичных тупиковых матриц.В результате анализа особенностей и способов совершенствования алгоритмов решения задачи унификации можно сделать следующие выводы:1.Наиболее предпочтительными методами решения одноуровневой задачи унификации являются метод ветвей и границ, а также приближенные методы, основанные на его идеях. В этих методах нет необходимости применять особые требования к свойствам матриц исходных данных.Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 8
2.Для улучшения метода ветвей и границ предлагается эффективная стратегия построения оценочной матрицы, позволяющая получить более точную оценку нижней границы, а также оптимизировать функцию ветвления. 3.Проверка эффективности разработанного нового алгоритматочного решения задачи унификации, так называемого алгоритма отбора переменных, показывает, что наибольший эффект от применения алгоритма отмечается при больших значениях размеренности исходной матрицы более 50х50).
Ссылки на источники1.Изотов В.Н., Петухов А.В. Повышение эффективности приближенного алгоритма решения задачи унификации ЭВМ в компьютерных сетях // НТС № 14.–Тула: ТАИИ, 1997.–C.110–113. 2.Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. –Новосибирск: Наука. 1978. –335 с.3.Там же.
Viktor Izotov,Doctor of Engineering Sciences,Professor, the Tula branch of Russian Presidential Academy of National Economy and Public Administration, Tulaizotovvntula@mail.ruTatianaMorozova, Headof Analytical Department, the State Institution of the Tula Region "Tulauprador",Tulatanek171290@yandex.ru
The algorithmof close methods of unitization tasks solutionAbstract.The algorithms of close methods of decision of onelevel multidimensional task of unitization are consideredin the paper. The groundof the algorithm of selection of variables, using close algorithms, is given. Exactness of the got decisions found by means of the algorithm of selection of variables is wellproven. Efficiency of the algorithm is investigational.Keywords:task of unitization, algorithm of decision, proof of algorithm, research of algorithmefficiency.References1.zotov, V. N. & Ptuhov, A. V. 1997 “Povyshni jffktivnosti priblizhnnogo algorita rshnija zadachi unifikacii JeVM v komp'juternyh setjah”, NTS № 14,TAII, Tula, pp. 110–113(inRussian). 2.Beresnev,V. L., Gimadi, Je. H. &Dement'ev,V. T.(1978)Jekstremal'nye zadachi standartizacii, Nauka,Novosibirsk,335 p.(inRussian).3.Ibid.
Рекомендованокпубликации:
Некрасовой Г. Н., докторомпедагогических наук,членомредакционной коллегиижурнала «Концепт»
Поступила в редакциюReceived12.08.15Получена положительная рецензияReceived a positive review14.08.15ПринятакпубликацииAccepted for publication14.08.15ОпубликованаPublished31.10.15
© Концепт, научнометодический электронный журнал, 2015©Изотов В. Н., Морозова Т. В., 2015
www.ekoncept.ru
ART15339УДК 330.42:519.71
Изотов Виктор Николаевич,
доктортехническихнаук, профессор кафедрыэкономикии финансовТульскогофилиалаФГБОУ ВПО «Российская академия народного хозяйства и государственной службы при Президенте Российской Федерации», г. Тулаizotovvntula@mail.ru
Морозова Татьяна Владиславовна,начальник аналитического отдела ГУТульской области «Тулаупрадор», г. Тула
tanek171290@yandex.ru
Алгоритмизация приближенных методов решения задачи унификации
Аннотация.Рассмотрены алгоритмы приближенных методов решения одноуровневой многомерной задачи унификации. Приведено обоснование алгоритма отбора переменных, использующего приближённые алгоритмы. Доказана точность получаемых решений, найденных с помощью алгоритма отбора переменных. Исследована эффективность алгоритма.Ключевые слова:задача унификации, алгоритм решения, доказательство алгоритма, исследование эффективности алгоритма.Раздел:04 экономика.
Среди приближенных методов решения задачи унификации наибольшее распространение получили алгоритмы с апостериорной оценкой их точности [1]. Относительная точность определяется в них по формуле учитывается, что xi=1yi):.(1)В основу первого приближенного алгоритма положен тот факт, что,исходя из особенностей построения оценочной матрицы W, единичные компоненты вектора , минимизирующего целевую функцию, следует искать после построения W, прежде всегосреди элементов множества . Поэтому целесообразно ограничиться рассмотрением только таких допустимых решений, для которых . Алгоритм, учитывающий данное обстоятельство,должен включать следующие этапы:1.Вычисление значения (W) .2.Исключение из рассмотрения всех строк матрицы и элементов вектора с номерами, не принадлежащими множеству I0(W . При этом получается новая исходная пара , .3.Применение алгоритма ветвей и границ к решению задачи с новой исходной парой для получения приближенного решения.Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 2
Этот метод дает наилучшее приближение, однакотрудоемкость вычисления существенно влияет на время решения задачи, так как построение осуществляется на каждом шаге вычисления, хотя число шагов и уменьшается в результате 2го этапа приближенного алгоритма.Второй приближенный алгоритм, в основе которого лежит идея «движения по градиенту», на 3м этапе вместо схемы ветвей и границ включает ряд шагов итерационного процесса, количество которых не может быть больше m. На первом этапе осуществляется построение оценочной матрицы, которая позволяет получить оценку «снизу» целевой функции на множестве продолжений частичного решения Z1,..., Zk). На втором этапе производится вычисление нижней границы H(Z1, ... , Zk и значений фиксируемых свободных переменных Zk+1, ... , Zp. На третьем этапе выполняется ряд шагов итерационного процесса, количество которых не может быть больше m. На первом шаге в качестве приближенного решения рассматривается вектор ,такой, что xi 1 , если ,и xi= 0 –в противном случае. Далее, для всех вычисляются показатели
,характеризующие степень изменения целевой функции при удалении iго типа изделия из предварительно полученного типоразмерного ряда. Затем определяется
.Если , то улучшить имеющее решение невозможно,и алгоритм заканчивает работу. Если , то отыскивается номер i0, для которого ,и для него полагается 0. При этом получается новое приближенное решение с меньшим значением S(x1, ... , xm . После этого переходят ко второму шагу и т.д. Этот алгоритм позволяет получить если не наилучшее как первый метод приближенное решение, то достаточно хорошее. Точность метода существенно зависит от точности построения Wна первом этапе. Здесь матрицаWстроится один раз. Третий приближенный алгоритм основан на вычислении специальных показателей Pi, характеризующих изменение величины S(x1, ... , xm при условии xi= 0 .
где –множество индексов переменных xi, вошедших в допустимое решение со значением xi=1;BD–множество индексов переменных xi , не вошедших еще в допустимое решение, то есть значения которых пока не определены.На каждом шаге алгоритма при условии элементы iвыводятся из множества BDи вводятся во множество D, а затем из множества BDудаляется элемент i0 , для которого.Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 3
Алгоритм заканчивает свою работу, когда все элементыiбудут введены из множестваBD. При этом множество Dбудет содержать решение задачи.На эффективность приближенных методов значительное влияние оказывает метод построения нижней границы, используемой для отсечения неперспективных ветвлений.Решение задачи унификации приближенными методами хотя и занимает незначительное время, но не всегда удовлетворяет требованиям точности. Решение же задач большой размеренности более 100x100 методом ветвей и границ требует относительно много машинного времени. Сокращение числа переборов допустимых решений в методе ветвей и границ может быть достигнуто применением дополнительной проверки на каждом шаге ветвления допустимого решения на оптимальность путем направленного решения двойственной задачи. Приближенное решение двойственной задачи сравнивается с найденным на данном шаге допустимым решением исходной задачи, и случай совпадения указывает на оптимальность целочисленного решения исходной задачи. В противном случае решение задачи продолжается методом ветвей и границ, причемпоиск и уточнение допустимого решения исходной задачи целесообразно осуществлять одним из приближенных методов.Рассматривая сущность направленного решения двойственной задачи,можно заметить, что это есть не что иное, как построение оценочной матрицы W, а приближенное двойственное решение есть результат вычисления оценки «снизу» целевой функции. Учитывая, что в основе применяемой усовершенствованной стратегии, обеспечивающей наибольшую точность нижней оценки, лежит идея «движения» в направлении получения максимальной величины (W, имеет смысл в качестве метода для нахождения допустимого решения исходной задачи выбрать второй приближенный метод, применяя в нем для повышения точности ту же усовершенствованную стратегию. Кроме того, анализируя алгоритм, а также принимая во внимание указанные особенности усовершенствованной стратегии и второго приближенного алгоритма, представляется возможным разработать новый алгоритм, включающий в себя достоинства приближенных методов и обеспечивающий получение точного решения задачи унификации.Алгоритм, основанный на использовании двойственного решения для отбора переменных, включаемых в решение задачи унификации, содержит следующие этапы:1.Нахождение двойственного решения(W с применением усовершенствованной стратегии. 2.Определение допустимого решения Sdс помощью второго приближенного алгоритма.3.Проверка допустимого решения на оптимальность путем сравнения с двойственным решением.4.Отбор переменных, включаемых в решение задачи.Алгоритм заканчивает работу, если доказана оптимальность допустимого решенияили все переменные после отбора включены в решение задачи. Если в результате отбора не все переменные вошли в решение, то к оставшимся переменным применяется тот же алгоритм, начиная с 1го этапа.2.Определение допустимого решения Sdс помощью второго приближенного алгоритма.3.Проверка допустимого решения на оптимальность путем сравнения с двойственным решением.4.Отбор переменных, включаемых в решение задачи.Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 4
Алгоритм заканчивает работу, если доказана оптимальность допустимого решения или все переменные после отбора включены в решение задачи. Если в результате отбора не все переменные вошли в решение, то к оставшимся переменным применяется тот же алгоритм, начиная с 1го этапа.Алгоритм отбора переменных представляет собой следующую последовательность действий.Если (W) , то вычислить .1.Просматриваются элементы вектора , полученного после построения матрицы W:аесли 0 и , то полагается xi 0 , а номер строки вводится во множество ;бесли 0 , вычислить –двойственное решение задачи при условии, что номер iисключен из множества U;весли , то полагается xi 1 , а номер iвводится во множество .2.Оставшиеся номера , не вошедшие во множества D0и D1, вводятся во множество . Затем для всех переменных алгоритм отбора повторяется, начиная с вычисления новых значений (W) , и , рассчитываемых для множества U= .Алгоритм заканчивает работу, когда множество пустое. Это означает, что получено оптимальное решение .Рассмотрим некоторые особенности применения данного алгоритма. Допустим, что заданы ограничения, когда, например, невозможно применение изделий iго типа для выполнения работ jго вида то есть исходные данные содержат элементы Gij= . Задача решается обычным способом, но во время решения может оказаться,что (W) = = . Тогда номера из множества вводятся во множестваD0и D1по правилу, определяемому элементами вектора , полученного на предыдущем этапе алгоритма.Необходимо доказать, что алгоритм отбора переменных за конечное число шагов обеспечивает нахождение точного решения задачи унификации. Для доказательства используется понятие тупиковой матрицы [2]. ОценочнуюматрицуWназывают тупиковой, если для всякого :1..2.
при ; Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 5
где –множество номеров i, для которых ;
–множество номеров i, соответствующих минимальным элементам в jм столбце матрицы W;
–минимальный элемент в jм столбце. Тупиковые матрицы в них дальнейшее увеличение (W невозможно являются наиболее перспективными –в смысле наилучшего (W) –оценочными матрицами. В такой матрице величины распределяются наиболее экономичным образом, поскольку в процессе построения матрицы Wк элементу wijдобавляется величина не более той, которая необходима для увеличения значения минимума в jм столбце. В наибольшей степени этим требованиям удовлетворяютматрицы, построенные с применением усовершенствованной стратегии. Для обоснования алгоритма отбора переменных необходимо доказать теорему.Теорема.Тупиковая матрица, построенная для оценки полинома целевой функциина множестве продолжений частичного решения , где , при k= m–1, приводит к точной оценке этого полинома.Полином может быть представлен в виде .(2)Необходимо определить, какой должна быть тупиковая матрица , построенная для оценки полинома , чтобы величина при произвольном значении представляла собой точную оценку.Вопрос о нижней оценке полинома целевой функции на множестве продолжений частичного решения Z1, ... , Zk сводится к вопросу о нижней оценке полинома на всем множестве решений, определяемом вектором .Определение. Матрица называется единичной, если для всякого число ненулевых компонентов вектора , где , не более единицы. Существует доказательство [3], чтоесли –единичная матрица, то оценка точная, а ее значение определяется по формулеИзотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 6
,
(3)где –множество номеров jiй строки матрицы , которые соответствуют минимальным элементам jго столбца.Если теперь рассмотреть вектор , где yi= 0, когда , и yi= 1–в противном случае, то нетрудно заметить, что вектору, минимизирующему полином , в качестве оптимального типоразмерного ряда соответствует множество , а в качестве областей использования изделий соответствуют множества . Другими словами, только единичная тупиковая матрица дает точную оценку полинома .Следовательно, при k= m–1 значение нижней границы для частичного решения (Z1, ... , Zk)
всегда будет точной оценкой, поскольку в этом случае тупиковая матрица всегда будет единичной.Из доказательства теоремы следует основной вывод, используемый при обосновании алгоритма отбора переменных. Если каждый элемент из множества рассматривать как последний элемент в этом множестве, а оставшиеся элементы–как частичное решение, то при наличии правила, устанавливающего оптимальное значение этого элемента в предположении, что частичное решение также оптимально, появится возможность поочередного отбора всех переменных для включения их в решение задачи унификации. Как следует из 3, указанное правило целесообразно основать на учете особенностей получаемого результата построения матрицы Wвектора , нулевые компоненты которого определены множеством . При этом нулевые значения вектора следует искать прежде всегосреди номеров , а единичные − среди номеров . Учитывая факт совпадения прямого и двойственного решения для оптимального вектора , целесообразно использовать их для поочередного установления оптимального значения каждого yi. Действительно, если после построения матрицы Wоставшаяся величина , то при yi= 1 Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 7
произойдет совпадение прямого и двойственного решенияв предположении, что частичное решение Z1, ... , Zk без элемента yiоптимально. Если же соотношение прямого и двойственного решений таково, что при , то удаление номера iиз типоразмерного ряда нецелесообразно, то есть принимается yi 0, что также обеспечивает совпадение этих решений в предположении оптимальности вектора Z1, ..., Zk при k=m–1. Поскольку вектор содержит конечное число элементов, с помощью данного алгоритма будет найдено точное решение задачи унификации за конечное число шагов. Результаты проверки эффективностиалгоритма приведены в таблице.
Результаты проверки эффективности метода отбора переменных
m
n
Алгоритм ветвей и границ,мин.\с.Предлагаемый метод, с.Время поиска 1го допустимого решения, с.
,
%
5
4
5–6
1–6
0\0,25
0,14
0,01
0
10
10
0,3–0,7
0,2–1
0\0,72
0,24
0,07
0
30
30
0–1
0–8
0\18,69
3,15
0,1
2,5
50
50
0,3–0,7
0,2–1
5\22,29
30,02
0,3
2,8
Проверка эффективности предлагаемого алгоритма показывает, что при небольших значениях mxnне более 20x20 для 80% решенных задач первое допустимое решение, получаемое с помощью второго приближенного алгоритма, совпадает с оптимальным. В остальных случаях отклонение 1го допустимого решения от оптимального не превышает 4%. Наибольшая эффективность алгоритмаотмечается при больших значениях размеренности матрицы .Таким образом, алгоритм отбора переменных может быть применен для получения точного решения многомерной задачи унификации изделий, в том числе и системного ПО, по экономическому критерию. Использование в этом методе усовершенствованного алгоритма построения оценочной матрицы и второго приближенного алгоритма увеличивает число включаемых в решение переменных за один просмотр множества, посколькуи в томи в другом алгоритмах учтены свойства единичных тупиковых матриц.В результате анализа особенностей и способов совершенствования алгоритмов решения задачи унификации можно сделать следующие выводы:1.Наиболее предпочтительными методами решения одноуровневой задачи унификации являются метод ветвей и границ, а также приближенные методы, основанные на его идеях. В этих методах нет необходимости применять особые требования к свойствам матриц исходных данных.Изотов В. Н., Морозова Т. В.Алгоритмизация приближённых методов ре0шения задачи унификации // Концепт. 22015. 2№ 10 (октябрь).2ART15339. 20,4п.л. 2URL: http://ekoncept.ru/2015/15339.htm.2ISSN 2304120X. 8
2.Для улучшения метода ветвей и границ предлагается эффективная стратегия построения оценочной матрицы, позволяющая получить более точную оценку нижней границы, а также оптимизировать функцию ветвления. 3.Проверка эффективности разработанного нового алгоритматочного решения задачи унификации, так называемого алгоритма отбора переменных, показывает, что наибольший эффект от применения алгоритма отмечается при больших значениях размеренности исходной матрицы более 50х50).
Ссылки на источники1.Изотов В.Н., Петухов А.В. Повышение эффективности приближенного алгоритма решения задачи унификации ЭВМ в компьютерных сетях // НТС № 14.–Тула: ТАИИ, 1997.–C.110–113. 2.Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. –Новосибирск: Наука. 1978. –335 с.3.Там же.
Viktor Izotov,Doctor of Engineering Sciences,Professor, the Tula branch of Russian Presidential Academy of National Economy and Public Administration, Tulaizotovvntula@mail.ruTatianaMorozova, Headof Analytical Department, the State Institution of the Tula Region "Tulauprador",Tulatanek171290@yandex.ru
The algorithmof close methods of unitization tasks solutionAbstract.The algorithms of close methods of decision of onelevel multidimensional task of unitization are consideredin the paper. The groundof the algorithm of selection of variables, using close algorithms, is given. Exactness of the got decisions found by means of the algorithm of selection of variables is wellproven. Efficiency of the algorithm is investigational.Keywords:task of unitization, algorithm of decision, proof of algorithm, research of algorithmefficiency.References1.zotov, V. N. & Ptuhov, A. V. 1997 “Povyshni jffktivnosti priblizhnnogo algorita rshnija zadachi unifikacii JeVM v komp'juternyh setjah”, NTS № 14,TAII, Tula, pp. 110–113(inRussian). 2.Beresnev,V. L., Gimadi, Je. H. &Dement'ev,V. T.(1978)Jekstremal'nye zadachi standartizacii, Nauka,Novosibirsk,335 p.(inRussian).3.Ibid.
Рекомендованокпубликации:
Некрасовой Г. Н., докторомпедагогических наук,членомредакционной коллегиижурнала «Концепт»
Поступила в редакциюReceived12.08.15Получена положительная рецензияReceived a positive review14.08.15ПринятакпубликацииAccepted for publication14.08.15ОпубликованаPublished31.10.15
© Концепт, научнометодический электронный журнал, 2015©Изотов В. Н., Морозова Т. В., 2015
www.ekoncept.ru
