Метод резолюции для анализа устойчивости задач 0-1 программирования

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

Full description

Saved in:

Bibliographic Details
Published in:	Компьютерная математика
Date:	2017
Main Authors:	Михайлюк, В.А., Лищук, Н.В.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2017
Subjects:	Теория и методы оптимизации
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/168464
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:	Метод резолюции для анализа устойчивости задач 0-1 программирования / В.А. Михайлюк, Н.В. Лищук // Компьютерная математика. — 2017. — № 2. — С. 127-136. — Бібліогр.: 17 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859951563592695808
author	Михайлюк, В.А. Лищук, Н.В.
author_facet	Михайлюк, В.А. Лищук, Н.В.
citation_txt	Метод резолюции для анализа устойчивости задач 0-1 программирования / В.А. Михайлюк, Н.В. Лищук // Компьютерная математика. — 2017. — № 2. — С. 127-136. — Бібліогр.: 17 назв. — рос.
collection	DSpace DC
container_title	Компьютерная математика
description	Поскольку метод резолюции для линейных задач 0-1 программирования полный, то представляет интерес его изучение и использование. Приведены такие изменения ограничений и целевой функции, при которых оптимальное решение остается неизменным. При этом возмущения ограничений и целевой функции удовлетворяют системе линейных неравенств. Оскільки метод резолюції для лінійних задач 0-1 програмування є повним, представляє інтерес його вивчення і використання. Наведені такі зміни обмежень та цільової функції, при яких оптимальний розв’язок залишається без змін. При цьому зміни обмежень та цільової функції задовольняють системі лінійних нерівностей. Since the resolution method for 0-1 linear programming problems is complete, it is of interest to study and use it. Such changes of constraints and objective function are given that optimal solution remains unchanged. The perturbations of the constraints and the objective function satisfy a system of linear inequalities.
first_indexed	2025-12-07T16:17:22Z
format	Article
fulltext	Компьютерная математика. 2017, № 2 127 Поскольку метод резолюции для линейных задач 0-1 программиро- вания полный, то представляет интерес его изучение и использо- вание. Приведены такие измене- ния ограничений и целевой функ- ции, при которых оптимальное решение остается неизменным. При этом возмущения ограниче- ний и целевой функции удовлетво- ряют системе линейных нера- венств.  В.А. Михайлюк, Н.В. Лищук, 2017 УДК 519.854 В.А. МИХАЙЛЮК, Н.В. ЛИЩУК МЕТОД РЕЗОЛЮЦИИ ДЛЯ АНАЛИЗА УСТОЙЧИВОСТИ ЗАДАЧ 0-1 ПРОГРАММИРОВАНИЯ Введение. Термин анализ устойчивости не отделим от процедуры решения задачи, где находится оптимальное решение, и вы- полняются дополнительные вычисления для определения зависимости оптимального решения от изменений входных данных. Цель анализа устойчивости состоит в опре- делении таких изменений входных данных, при которых оптимальное решение остается неизменным [1]. Как правило устойчивость оптимального или приближенного к нему решения харак- теризуется некоторыми параметрами: об- ласть, шар, радиус устойчивости и т. д. [2 – 4]. В работе [2] рассмотрены общие по- нятия теории устойчивости, введено важное понятие радиуса устойчивости задачи. Изу- чаются вопросы вычисления радиуса устой- чивости  -приближенного решения для не- которого класса дискретных экстремальных задач в [3]. Определены необходимые и дос- таточные условия, при выполнении которых радиус устойчивости равен нулю или беско- нечности. Предложен алгоритм вычисления радиуса устойчивости и выделен класс задач, для которых этот алгоритм является полино- миальным. При этом все изучаемые величи- ны касаются изменений коэффициентов це- левой функции задачи. Представлены и изу- чены алгоритмы вычисления радиуса устой- чивости  -оптимального решения для оптимизационной задачи с разными целевы- ми функциями [4]. При этом также изменя- ются значения коэффициентов целевой функции задачи. В работах [5, 6] получены результаты относительно устой- чивости локальных решений задач цело- В.А. МИХАЙЛЮК, Н.В. ЛИЩУК 128 Компьютерная математика. 2017, № 2 численного программирования. Важное значение уделяется оценкам сложности анализа устойчивости дискретных задач оптимизации. Для NP -трудных задач это сводится к анализу существования полиномиальных алгоритмов нахождения оптимальных решений измененных задач, исходя из оптимальных решений исходной задачи. В работе [7] приводятся результаты по сложности анализа устойчивости 0/1 задач с линейной целевой функцией при изменении значений целевого вектора. Показано, что является NP -трудным (не существует полино- миального алгоритма при P NP ) определить остается ли оптимальное реше- ние неизменным для NP -трудных задач при произвольном изменении вектора значений целевой функции. Подобных результатов по изменению коэффициен- тов вектора ограничений или вообще нет, или они малочисленны. В этом на- правлении следует отметить работы [8 – 11]. С понятием стойкости тесно связа- но понятие постоптимального анализа задач дискретной оптимизации [12]. П. Пардалос и Б. Гольденгорин [13 – 15] разработали группу толерантных методов (методы допустимых отклонений, tolerance-based methods). Верхняя толерантность, верхнее допустимое отклонение (the upper tolerance) по отношению к элементу ,e который входит в оптимальное решение, – макси- мальное увеличение веса ( ( )),e c e при котором оптимальное решение остается оптимальным (весовые коэффициенты остальных элементов – неизменны). Нижняя толерантность, нижнее допустимое отклонение (the lower tolerance) по отношению к элементу, который не входит в оптимальное решение, – макси- мальное уменьшение веса ( ( )),e c e при котором прежнее оптимальное решение остается неизменным. Роль толерантностей. 1. Они используются для нахождения «хороших» или оптимальных реше- ний задач. Для эвристических методов – определяется какие элементы сохраня- ются в каждой итерации. Для методов ветвей и границ они используются для определения какие элементы следует включить или исключить в шаге ветвле- ния. Верхние толерантности определяют какие элементы сохраняются. Нижние толерантности определяют какие элементы не следует выбирать. 2. Толерантности могут быть использованы для определения нижних оценок целевых функций (для задачи минимизации). 3. Могут быть использованы для частичного анализа устойчивости комби- наторных задач. Tolerance-based methods используют релаксацию. Например, это (Assignment Problem, проблема о назначениях) для решения MSTP (Minimum Spanning Tree Problem) и ATSP (Asymmetric Traveling Salesman Problem). Выигрыш в сложно- сти в n раз дает решение AP с использованием двойственного подхода (см. ст. «The reduction of computation times of upper...») в сравнении с тем, если бы толе- рантности находились независимо от нахождения оптимального решения исходной задачи. Tolerance-based methods классифицируются: МЕТОД РЕЗОЛЮЦИИ ДЛЯ АНАЛИЗА УСТОЙЧИВОСТИ ЗАДАЧ ... Компьютерная математика. 2017, № 2 129 а) числом вычисленных толерантностей (от некоторых до всех верхних и нижних); б) частотой вычисленных толерантностей (только на начальном шаге или во всех итерациях). Подход к исследованию устойчивости, основанный на применении метода резолюции и элементов теории выводимой двойственности (inference duality) рассмотрен в работах [16, 17]. В данной работе используется и развивается именно этот подход. Постановка задачи. Выводимая двойственность. Рассмотрим общую оптимизационную задачу программирования вида. min ( ),f x ( ),C x ,x D (1) где )(xC задает допустимое решение ,x D задает ограничения на компоненты вектора x (целочисленность, булевость и т. д.). Выводимая двойственность к за- даче )1( : максимизировать нижнюю оценку ( ),f x которая может быть выведена из ограничений. Это задача поиска доказательства оптимальности оценки. Двой- ственная задача может быть записана в виде. vmax ( ) ( ( ) ),PC x f x v   PRv , , (2) где ))(()( vxfxC P  означает, что доказательство P выводит vxf )( из )(xC . Область действия переменной P – семейство доказательств Ρ и двой- ственное решение – это пара ( , ).v P Когда прямая задача )1( – недопустима, двойственная )2( – не ограничена, и двойственное решение содержит для про- извольного x схему доказательства ,P которая выводит vxf )( из )(xC для произвольного данного .v Лемма 1 (слабость логического вывода). Оптимальное значение прямой задачи ограничено снизу оптимальным значением любой двойственной задачи. Разрыв между оптимальным значением z прямой и оптимальным значени- ем v двойственной – разрыв двойственности. Разрыв может существовать, поскольку нет доказательства в ,Р что выводит )( zxf  из ,C если даже из C следует ( ) .f x z Это может случиться, когда схема доказательств Ρ является неполной, и означает то, что она не может вывести все ограничения, которые подразумеваются. Отсутствие разрыва двойственности называется сильной двойственностью. Теорема 1 [17]. Предположим, что семейство доказательств  является полным по отношению к ограничениям ( ) .f x v Тогда прямая задача )1( и двойственная )2( имеют одинаковые оптимальные значения. Более того до- пустимое решение x задачи )1( оптимально тогда и только тогда, когда )2( имеет допустимое решение ( , )v P с ( ).v f x В.А. МИХАЙЛЮК, Н.В. ЛИЩУК 130 Компьютерная математика. 2017, № 2 Сертификаты, выводимая двойственность и сложность задач. Сертифи- кат допустимости для экземпляра задачи – это информация для проверки, что эк- земпляр действительно допустимый (принадлежит допустимой области). Напри- мер, сертификат может быть множеством переменных, которые удовлетворяют ограничению. Сертификат недопустимости это доказательство, что экземпляр за- дачи не имеет допустимого решения. Сертификат оптимальности – специальный случай: если v (возможно бесконечное) оптимальное значение целевой функции ( ),f x сертификат оптимальности это доказательство, что экземпляр задачи недо- пустим, когда )( vxf  добавляется к ограничениям. Оптимизационная проблема принадлежит ,NP если существует полиноми- альный сертификат допустимости для любого данного допустимого экземпляра задачи. Оптимизационная проблема принадлежит ,co NP если существует полиномиальный сертификат оптимальности для данного экземпляра. Теорема 2 [17]. Оптимизационная задача )1( принадлежит NPco  тогда и только тогда, когда )2( принадлежит NP для некоторого .P Интересе факт, что большинство известных комбинаторных задач принад- лежат не ,co NP а .NP Другими словами комбинаторная задача в основном принадлежит ,NP а ее выводимая двойственность – нет. Общий переборный алгоритм для решения прямой задачи. В общем случае можно охарактеризовать прямой метод решения задачи как метод, прове- ряющий возможные значения переменных и двойственный метод, проверяющий возможные доказательства оптимальности без интерпретации переменных. В классической оптимизации метод ветвей и границ прямой, а метод отсекаю- щих плоскостей двойственный [17]. Двойственно выводимая дискретная опти- мизация может быть решена прямым методом, в частности, с помощью дерева перебора. Рассмотрим задачи. min ,cx 0,Ax  0,x  (3) zmax ( , 0) , nRAx a x cx z    (4) где nmA  матрица. Один из способов решения )1( – перебор значений переменных, пока не будут найдены все допустимые решения. Поиск повторяется, если допустимое решение найдено или некоторое ограничение нарушено. Наилучшее допустимое решение есть оптимальным. Пусть z оптимальное решение, найденное пере- числением. Для решения двойственной модифицируем дерево вариантов, чтобы оно отвергало ( ) .f x z Это делается просто добавлением ограничения tzxf )( к множеству ограничений C для каждого узла ,t для которого найде- но допустимое решение, где tz значение решения. Тогда  tzxf )( ограни- чение, которое нарушено на .t Существует по крайней мере одно ограничение, нарушенное на каждом концевом узле. МЕТОД РЕЗОЛЮЦИИ ДЛЯ АНАЛИЗА УСТОЙЧИВОСТИ ЗАДАЧ ... Компьютерная математика. 2017, № 2 131 Алгоритм 1. Пусть )(xC множество ограничений, определяющих допустимость )1( . 2. Пусть L список активных узлов, изначально содержащих корневой узел, ассоциирующийся с пустым множеством приписываний (меток). 3. Пусть z – верхняя оценка оптимального значения; первоначально z ∞. 4. Пока L не есть пустым, то исключаем узел с L и пусть A – это множест- во меток ассоциированных с узлом. 5. Если приписывание в A не нарушает огранчений в ,C то если A припи- сывание значений nvv ,...,1 к каждому nxx ,...,1 так чтобы, удовлетворить каждое ограничение. 6. Тогда выполнить )},...(,min{ 1 nvvfzz  , иначе выбрать переменную jx , к которой не приписано значение. 7. Для каждого : jxv D добавить узел к L и ассоциировать его с }{ vxA j  . 8. Если z ∞, то z оптимальное значение )1( . Иначе )1( – несовместима. Метод резолюции [16]. Пропозициональная логика состоит из переменных с отрицаниями ( jx и jx ), а также логических связок {  ,, }. Логический клоз – дизъюнкция литералов, например, конъюнкция 1 2 3( )x x x   2 3( )x x   двух клозов эквивалентна первой конъюнкции. Первая конъюнкция может быть опущена без эффекта, потому что она поглощается второй. Клоз 1C заключает в себе клоз 2C (из 1C следует 2C ) тогда и только тогда, когда 1C поглощает 2C или все литералы 1C встречаются в 2.C Пустой клоз не содержит литералов и при необходимости – ложный. Метод Куайна выдает все импликации данного множества клозов. Резольвента (по jx ) состоит из дизъюнкции литералов кроме клозов с jx и jx . Например, клозы 321 xxx  и 421 xxx  получают резольвенту 432 xxx  . В примере 1x либо ложно, либо истина. Если ложно с первого клоза следует 2 3.x x Если истина, со второго клоза следует 2 4.x x В обоих случаях следует абсорбция. Алгоритм резолюции применяется к мно- жеству клозов S таким образом. Определяем пару клозов в ,S имеющих резо- люцию ,R которая не поглощается. Удаляем из S все клозы поглощаемые R и добавляем R к .S Продолжаем пока не появляются такие пары. Куайн пока- зал, что алгоритм является полным: если он начинается с S и заканчивается ',S то любой клоз, который следует с S поглощается некоторым клозом '.S В част- ности S – невыполнимая тогда и только тогда, когда 'S содержит пустой клоз. В.А. МИХАЙЛЮК, Н.В. ЛИЩУК 132 Компьютерная математика. 2017, № 2 Пример. Бракованные ограничения (nogood constraints). Успешные оптимизаци- онные комбинаторные методы почти всегда прямо-двойственные методы: они комбинируют поиск относительно решений с выводом и релаксацией с точки зрения решения выводимо двойственной или релаксационно двойственной, так как они решают прямые задачи. Поиск в направлении улучшения ограничений – это ключевое понятие бракованных ограничений и используется в методе резолюции. Если z оптимальное решение прямой задачи (1), решение двойст- венной )2( равнозначно нахождению решения ( ) ,f x z используя ограниче- ния и передаваемые посылки. Это предполагает правила вывода, полные в соот- ветствующем виде: они предполагают путь получения действительных импли- каций вида zxf )( от типа ограничений задачи. Метод доказательства резолю- ций сам по себе не нужен для анализа устойчивости. Он необходим для знания предпосылок (какие ложные клозы используются в узлах). Поскольку правило резолюции продолжает выполняться, когда данные изменяются при доступных предпосылках неравенства, ассоциированные с каждым узлом, продолжают выполняться при ложных клозах. Ложные клозы (nogood constraints) получаются с помощью резольвент. Рассмотрим пример: 1 2 3min3 5 7 ,x x x  (а) 1 2 32 5 3,x x x   (b) 1 2 34 4,x x x    (c) 1 2 3 2,x x x   3{0,1} .x Оптимальное значение равно 12 (получено переборным алгоритмом). Дока- зательство, что zz 12 (для данного 0z ) может быть ассоциировано для каждого узла неравенством, которое нарушается в данном узле. С каждым недо- пустимым узлом ассоциируем нарушенные ограничительные неравенства. С каждым допустимым узлом ассоциируем неравенство ,cx z z     где z~ значение функции цели в этом узле; 0, 0, 0, 0.z z       Неравенства вида cx z z     будем записывать .cx z z      Поскольку дерево поиска является исчерпывающим неравенства в узлах должны быть изменчивыми. Доказательство их изменчивости доказывает оценку zz 12 и, следователь- но, решает выводимо двойственную. Лемма 2 [17]. Простой способ проверки следует ли с ax   клоз, который фальсифицируется для 1 1 ( ,..., ) ( ,..., ). dd j j jj x x v v Пусть J множество индексов j с 1{ ,..., ),dj j для которых 0,ja  если 1jv и 0ja , если 0.jv  Пусть )(vx j есть jx , если 1v и ,jx если 0.v  Тогда )1( jjJj vx   – требуемый клоз, если max{0, } ,j j jj J j J a v a       иначе не существует такого клоза. МЕТОД РЕЗОЛЮЦИИ ДЛЯ АНАЛИЗА УСТОЙЧИВОСТИ ЗАДАЧ ... Компьютерная математика. 2017, № 2 133 Оставшиеся ограничения (еще не нарушенные) отмечены для каждого узла, ограничения нарушенные в каждом узле обозначены звездочками; если нет на- рушенных ограничений показано целевую функцию z (рисунок). В таблице в каждом узле показаны такие нарушения (им соответствуют бракованные огра- ничения, nogood constraints). Опишем все бракованные ограничения таблицы. 1 )(),(),( cba 11 x 01 x 2 )(),(),( cba )(),(),( cba 3 12 x 02 x 12 x 02 x 4 )(b 5 )(,)( ba 6 )(),( cb )(,)( ca 7 13 x 03 x 13 x 03 x )(b * )(,)( cb 8 15z 9 10 12z 11 РИСУНОК ТАБЛИЦА Узел 1 Ǿ Узел 2 1x Узел 3 1x Узел 4 21 xx  Узел 5 )( 21 xx  Узел 6 21 xx  Узел 7 )( 21 xx  Узел 8 )( 321 xxx  Узел 9 )( 321 xxx  Узел 10 )( 321 xxx  Узел 11 )( 321 xxx  В.А. МИХАЙЛЮК, Н.В. ЛИЩУК 134 Компьютерная математика. 2017, № 2 Резольвенту конъюнкций 1K и 2K будем обозначать ),Re( 21 KK . Имеем систему резольвент для данной задачи. 1. 21321321 ),Re( xxxxxxxx  . 2. 12121 ),Re( xxxxx  . 3. 21321321 ),Re( xxxxxxxx  . 4. 12121 ),Re( xxxxx  . 5.  ),Re( 11 xx Ǿ. Ограничение )(c не ассоциировано ни с каким узлом и двойственное дока- зательство сохраняет предпосылки (не изменяется), если даже )(c удалить из задачи. Таким образом, )(c излишне и может быть удалено без изменения опти- мального решения. Дальше рассмотрим ограничение ( ),b которое связано с узлами 9 и 11. Фальсифицированный клоз в узле 9 – 321 xxx  , в узле 11 – 321 xxx  . Тогда )(b может быть изменено любым способом так, что оно продолжает имплицировать эти два клоза без изменения оценки 12.z  Предпо- ложим, что )(b изменилось до 1 1 2 2 3 3( 1 ) (1 ) (4 )b x b x b x          4 .   Легко видеть с леммы 2, что с измененного неравенства следует 1 2 3x x x   тогда и только тогда, когда 1 2( 1 ) (1 ) 4 .b b         Аналогично следует 321 xxx  тогда и только тогда, когда 2(1 ) 4 .b     Таким образом, изменения ,b  допустимы, если они удовлетворяют линейной системе: 1 2 4b b      , 2 3 .b    (5) Целевую функцию можно описать следующим образом. Поскольку толерантность z определена, целевая функция может быть изменена к любой функции 332211 )7()5()3( xcxcxc  такой, что 1 1(3 )c x    2 2 3 3(5 ) (7 ) 15c x c x z           продолжает следовать 321 xxx  и 1 1 2 2 3 3(3 ) (5 ) (7 ) 12c x c x c x z              продолжает следовать 1 2 3.x x x  Это достигается при 1 2 3 ,c c c z       zcc  32 . Выводы. Успешные оптимизационные комбинаторные методы почти все- гда прямо-двойственные методы: они комбинируют поиск относительно решений с выводом и релаксацией с точки зрения решения выводимо двойст- венной или релаксационно двойственной, так как они решают прямые задачи. МЕТОД РЕЗОЛЮЦИИ ДЛЯ АНАЛИЗА УСТОЙЧИВОСТИ ЗАДАЧ ... Компьютерная математика. 2017, № 2 135 Для решения двойственно выводимой задачи необходимо: идентифи- цировать правила вывода, которые являются полными для типа ограничений в задачах; использовать правила для доказательства оптимальности. Поиск в направлении улучшения ограничений – ключевое понятие брако- ванных ограничений и используется в методе резолюции. Если z оптимальное решение прямой задачи (1), решение двойственной )2( равнозначно нахожде- нию решения ( ) ,f x z используя ограничения и передаваемые посылки. Это предполагает правила вывода, полные в соответствующем виде: они предпола- гают путь получения действительных импликаций вида zxf )( от типа огра- ничений задачи. Метод доказательства резолюций сам по себе не нужен для анализа устойчивости. Он необходим для знания предпосылок (какие ложные клозы используются в узлах). Поскольку правило резолюции продолжает вы- полняться, когда данные изменяются при доступных предпосылках неравенства, ассоциированные с каждым узлом, продолжают выполняться при ложных кло- зах. Ложные клозы (nogood constraints) получаются с помощью резольвент. При различных z получаются различные оценки 12 .z z   При их совпадении получаем последовательность решений, которые и есть множеством устойчивых задач. Представляет интерес вывод таких классов функций )}({ xf , для которых применим подход из данной статьи. В частности, представляют интерес функ- ции «на узкие места» bottleneck (min-max) с целевыми коэффициентами вида 1max .i n i ic x   В.О. Михайлюк, Н.В. Ліщук МЕТОД РЕЗОЛЮЦІЇ ДЛЯ АНАЛІЗУ СТІЙКОСТІ ЗАДАЧ 0-1 ПРОГРАМУВАННЯ Оскільки метод резолюції для лінійних задач 0-1 програмування є повним, представляє інтерес його вивчення і використання. Наведені такі зміни обмежень та цільової функції, при яких оптимальний розв’язок залишається без змін. При цьому зміни обмежень та цільової функції задовольняють системі лінійних нерівностей. V.A. Mikhailyuk, N.V. Lishchuk RESOLUTION METHOD FOR THE ANALYSIS OF SENSITIVITY OF 0-1 PROGRAMMING PROBLEMS Since the resolution method for 0-1 linear programming problems is complete, it is of interest to study and use it. Such changes of constraints and objective function are given that optimal solution remains unchanged. The perturbations of the constraints and the objective function satisfy a system of linear inequalities. 1. Fernandez-Baca D., Benkatachalam B. Sensitivity analysis in combinatorial optimization. Handbook of Approximation Algorithms and Metaheuristics (ed. T. Guzalez). 2007. Chap- man&Hall/CRC Computer and Information Science Series. P. 30-1 – 30-29. В.А. МИХАЙЛЮК, Н.В. ЛИЩУК 136 Компьютерная математика. 2017, № 2 2. Леонтьев В.К., Мамутов К.Х. Устойчивость решений в задачах линейного булева про- граммирования. Вычислительная математика и математическая физика. 1988. Т. 28, № 10. С. 1475 – 1481. 3. Сотсков Ю.Н. Исследование устойчивости приближеного решения булевой задачи минимизации линейной формы. Вычислительная математика и математическая фи- зика. 1993. Т. 33, № 5. С. 785 – 795. 4. Chakravarti N. and Wagelmans A.P. M. Calculation of stability radii for combinatorial optimi- zation problems. Operations Research Letters. 1998. 23. P. 1 – 7. 5. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимиза- ции. Киев: Наук. думка, 1985. 210 с. 6. Сергиенко И.В., Филоненко Н.В. Решение некоторых задач устойчивости в целочислен- ном линейном программировании. Докл. АН УССР. Сер. А. 1982. № 6. С. 79 – 82. 7. Van Hoesel S., Wagelmans A. On the complexity of postoptimality analysis of 0/1 programs. Discrete Applied Mathematics. 1999. 91. P. 251 – 263. 8. Blair C. Sensitivity analysis for knapsack problems: a negative result. Discrete Applied Mathe- matics. 1998. 81. P. 133 – 139. 9. Woeginger G.J. Sensitivity analysis for knapsack problems: another negative result. Discrete Applied Mathematics. 1999. 92. P. 247 – 251. 10. Михайлюк В.А. Общий подход к оценке сложности постоптимального анализа дискрет- ных задач оптимизации. Кибернетика и системный анализ. 2010. 46, № 2. С. 134 – 141. 11. Михайлюк В.A., Лищук Н.В. Анализ устойчивости задачи о ранце: один отрицательный результат. Кибернетика и системный анализ. 2013. 49, № 2. С.48 –51. 12. Михайлюк В.О., Сергієнко І.В. Постоптимальний аналіз та наближені алгоритми реоптимізації для задач дискретного програмування. Київ: Наукова думка, 2015. 248 с. 13. Remco Germs, Boris Goldengorin, Marcel Turkensteen. Lower tolerance-based Branch and Bound algorithms for the ATSP. Computer&Operations Research. 2012. 39, P. 291 – 298. 14. Gerold Jager, Boris Goldengorin, Panos M. Pardalos. The theory of Set Tolerances. LION 2014, LNCS 8426, 2014. P. 362 – 377 15. Marek Libura. Sensitivity analysis for minimum Hamiltonian path and traveling salesman prob- lems. Discrete Applied Mathematics. 1991. 30. P. 197 – 211. 16. Chvatal V. Resolution Search. Discrete Applied Mathematics. 1997. 73. P. 81 – 99. 17. John N. Hooker. Integrated Methods for Optimization /Springer Science+Business Media, LLC, 233 Spring Street, New York NY 10013, USA, 2007. Получено 12.10.2017 Об авторах: Михайлюк Виктор Алексеевич, доктор физико-математических наук, доцент, заведующий кафедрой прикладной математики и информатики Восточноевропейского национального университета имени Леси Украинки, Е-mail: mikhailyukvictor2@gmail.com Лищук Наталия Викторовна, аспирантка Восточноевропейского национального университета имени Леси Украинки. Е-mail: lnatalkav@mail.ru
id	nasplib_isofts_kiev_ua-123456789-168464
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	2616-938Х
language	Russian
last_indexed	2025-12-07T16:17:22Z
publishDate	2017
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Михайлюк, В.А. Лищук, Н.В. 2020-05-02T19:12:46Z 2020-05-02T19:12:46Z 2017 Метод резолюции для анализа устойчивости задач 0-1 программирования / В.А. Михайлюк, Н.В. Лищук // Компьютерная математика. — 2017. — № 2. — С. 127-136. — Бібліогр.: 17 назв. — рос. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/168464 519.854 Поскольку метод резолюции для линейных задач 0-1 программирования полный, то представляет интерес его изучение и использование. Приведены такие изменения ограничений и целевой функции, при которых оптимальное решение остается неизменным. При этом возмущения ограничений и целевой функции удовлетворяют системе линейных неравенств. Оскільки метод резолюції для лінійних задач 0-1 програмування є повним, представляє інтерес його вивчення і використання. Наведені такі зміни обмежень та цільової функції, при яких оптимальний розв’язок залишається без змін. При цьому зміни обмежень та цільової функції задовольняють системі лінійних нерівностей. Since the resolution method for 0-1 linear programming problems is complete, it is of interest to study and use it. Such changes of constraints and objective function are given that optimal solution remains unchanged. The perturbations of the constraints and the objective function satisfy a system of linear inequalities. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Метод резолюции для анализа устойчивости задач 0-1 программирования Метод резолюції для аналізу стійкості задач 0-1 програмування Resolution method for the analysis of sensitivity of 0-1 programming problems Article published earlier
spellingShingle	Метод резолюции для анализа устойчивости задач 0-1 программирования Михайлюк, В.А. Лищук, Н.В. Теория и методы оптимизации
title	Метод резолюции для анализа устойчивости задач 0-1 программирования
title_alt	Метод резолюції для аналізу стійкості задач 0-1 програмування Resolution method for the analysis of sensitivity of 0-1 programming problems
title_full	Метод резолюции для анализа устойчивости задач 0-1 программирования
title_fullStr	Метод резолюции для анализа устойчивости задач 0-1 программирования
title_full_unstemmed	Метод резолюции для анализа устойчивости задач 0-1 программирования
title_short	Метод резолюции для анализа устойчивости задач 0-1 программирования
title_sort	метод резолюции для анализа устойчивости задач 0-1 программирования
topic	Теория и методы оптимизации
topic_facet	Теория и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/168464
work_keys_str_mv	AT mihailûkva metodrezolûciidlâanalizaustoičivostizadač01programmirovaniâ AT liŝuknv metodrezolûciidlâanalizaustoičivostizadač01programmirovaniâ AT mihailûkva metodrezolûcíídlâanalízustíikostízadač01programuvannâ AT liŝuknv metodrezolûcíídlâanalízustíikostízadač01programuvannâ AT mihailûkva resolutionmethodfortheanalysisofsensitivityof01programmingproblems AT liŝuknv resolutionmethodfortheanalysisofsensitivityof01programmingproblems

Метод резолюции для анализа устойчивости задач 0-1 программирования

Institution

Similar Items