Понятия субоптимистического и субпессимистического решений и построение их в интервальной задаче булевого программирования

Abstract

RU: В работе рассмотрена интервальная задача булевого программирования. Даны некоторые экономические интерпретации этой задачи, в результате которых построена экономико-математическая модель. Введены понятия допустимого, оптимистического, пессимистического, субоптимистического и субпессимистического решений задачи булевого программирования с целочисленными интервальными данными. Разработаны два алгоритма построения субоптимистического и субпессимистического решений этой задачи. Естественно, что эти решения могут отличатся от оптимистического и пессимистического решений. Поэтому необходимо оценить относительные погрешности найденныx субоптимистических и субпессимистических решений от оптимистического и пессимистического, соответственно. С этой целью построена мажорирующая функция типа Лагранжа. Доказано, что минимальное значение этой функции является верхней границей оптимистического и пессимистического значений целевой функции, соответственно. Минимизацией этой функции находится верхняя граница субоптимистического и субпессимистического значений целевой функции. Проведены вычислительные эксперименты по решению задач различной размерности. UK: У роботі розглянута інтервальна задача булевого програмування. Дано деякі економічні інтерпретації цієї задачі, у результаті яких побудована економіко-математична модель. Уведено поняття припустимого, оптимістичного, песимістичного, субоптимістичного і субпесимістичного рішень задачі булевого програмування з цілочисленими інтервальними даними. Розроблено два алгоритми побудови субоптимістичного і субпесимістичного рішень цієї задачі. Природно, що ці рішення можуть відрізняться від оптимістичного і песимістичного рішень. Тому необхідно оцінити відносні погрішності знайдениx субоптимістичних і субпесимістичних рішень від оптимістичного і песимістичного, відповідно. З цією метою побудована мажорувальна функція типу Лагранжа. Доведено, що мінімальне значення цієї функції є верхньою межею оптимістичного і песимістичного значень цільової функції, відповідно. Мінімізацією цієї функції знаходиться верхня межа субоптимістичного і субпесимістичного значень цільової функції. Проведено обчислювальні експерименти з вирішення задача різної розмірності. EN: The work considers an interval examples of Bulian programming.Given some economic interpretation to this problem which result in the constructed economic-mathematical model.Introduced the definitions of optimistic, pessimistic, and suboptimistic, subpessimistic solutions for the Boolean programming problem with integer interval data are introduced. On the basis of the economic interpretation of the problem two algorithms are developed for the constructing of the suboptimistic and subpessimistic solutions of this task. Of course, when solutions may different from suboptimistic and subpessimistic solutions.It is therefore necessary to estimate the relative error of the found to estimate the error of the suboptimistic and subpessimistic solutions from optimistic and pessimistic solutions appropriately. For this purpose Lagrange type majoring function is constructed. It is proved, that the minimum value of this function is the upper bound of the optimistic and pessimistic values of the objective function appropriately. Minimization of this function is in the upper border of the suboptimistic and subpessimistic values of the performance function. Numerous computational experiments on the examples with different dimensions are provided.