Теоретические основы информатики
Замкова Л.И., кандидат технических наук, ассистент Южного федерального университета
ГЕОМЕТРИЧЕСКИЕ ИНТЕРПРЕТАЦИИ ДВУХКРИТЕРИАЛЬНЫХ ЗАДАЧ
В статье рассматриваются основы построения геометрических интерпретаций индивидуальной и массовой двухкритериальных задач. Формулируется и доказывается ряд теоретических положений, что является обоснованием способа построения геометрических интерпретаций.
Ключевые слова: массовая задача, индивидуальная задача, оптимальное решение, двухкритери-альная задача, геометрическая интерпретация.
GEOMETRICAL INTERPRETATIONS OF PROBLEMS WITH TWO CRITERIA
In clause the bases of construction of geometrical interpretations of a individual and general problem with two criteria are considered. Is formulated and a number of theoretical rules is proved, that is a substantiation of a way of construction of geometrical interpretations.
Key words: problem in the general formulation, individual problem, optimum decision, problems with two criteria, geometrical interpretations.
Процесс анализа оптимизационной задачи и поиска её решения с использованием геометрической интерпретации является более наглядным и быстрым по сравнению с процессом решения этой задачи вычислительными методами оптимизации. Это является важным при решении технических практических оптимизационных задач, таких как принятие решений при проектировании технических систем [1], анализ уязвимости многопродуктовых сетевых систем [2]. Существование геометрической интерпретации массовых задач даёт возможность применять её для анализа целого класса индивидуальных задач. В связи с этим далее выполняется построение геометрических интерпретаций для массовой и индивидуальной двухкритериальных задач.
Геометрическая интерпретация индивидуальной задачи
Рассмотрим индивидуальную двухкритериальную задачу, для которой известно решение (1):
C' = xj + 2 • x2 ^ max, C" = xj + 3• x2 ^ min,
xj < 4, (1)
x2 < 5,
xj > 0, x2 > 0.
В работе [3] задача решалась по двум критериям, причём первый считался предпочтительнее. При решении задачи методом последовательных уступок отклонение главного критерия от максимального значения должно было быть не больше 10%. В этом случае значение первого критерия C' с учётом уступки равно 12,6 (при максимальном
значении этого критерия 14) значение второго критерия С"равно 17,6 и оптимальное решение задачи (1) - ^1=2,6; х2=5.
Для построения геометрической интерпретации приведём задачу (1) к каноническому виду (2):
1 * х1 + 2 * х2 + 0 * х3 + 0 * х4 ^ тах,
1* х1 + 3 * х2 + 0 * х3 + 0 * х4 ^ тт,
1 * х1 + 0 * х2 +1 * х3 + 0 * х4 = 4,
0 * х1 +1 * х2 + 0 * х3 +1* х4 = 5,
х1 > 0, х2 > 0.
(2)
10 10 0 10 1
Ь1 = 4 ь2 = 5
В постановке задачи (2) С' = (1,2,0,0), С" = (1,3,0,0), А Введём обозначения: С = (сц, с2, с3, с4) - вектор коэффициентов первого критерия,
С" = (с" с" с" с" ) а
- вектор коэффициентов второго критерия,
^11 а^з
а21 а22 а23 а24
матрица коэффициентов ограничений, Ь1 и Ь2- свободные члены соответствующих ограничений. Введём новые переменные:
— ' а?12 * ^2 ^ ^13 ' Х3 ^ ^14 ' Х4,
и2 = ^21 * ^ ^22 * ^2 ^ ^23 * Х3 ^ ^24 ' Х4 ■
^3 = с1 * ^ с2 * ^2 ^ с3 * Х3 ^ с4 * Х4,
и 4 = с1 * ^ с2 * ^2 ^ с3 * Х3 ^ с4 * Х4.
(3)
Рассмотрим прямоугольную систему координат в трёхмерном пространстве с началом в точке О и осями ОХ, ОУ, OZ. В этой системе любому вектору
х = (х1, х2, х3, х4) сопоставляются две точки с координатами (и2, и3, и1) и (и2, и4, и1),
которые вычисляются по формулам (3). Образ (u2, и3^ и1) произвольного вектора
х ^х^ x2, xз, х4) с неотрицательными компонентами может быть представлен в виде
Л'.
суммы некоторых векторов, расположенных на лучах ] - ими являются векторы
х. * а2., х. * с., х. * ах.], . = 1,2,...,4. Аналогично для образа (u2, u4, и1) рассматривают-
Л] , = 12 4 | х, * а2 ., х, * с"., х, * а1 •] „ ся векторы на лучах ] , ] = ^...Д - ^ ] 2] ] ] ] 1]) . В результате получаем
два выпуклых четырёхгранных конуса. Таким образом, множеству векторов х = (хц, х2, х3, х4) с неотрицательными координатами соответствует множество точек трёхмерного пространства вида (u2, u3, и1), образующее один выпуклый четырёхгранный конус, и множество точек трёхмерного пространства вида kл2, u4, и1^ образующее другой конус.
Построим конус К ' (рис. 1), образованный лучами Л1 Л 2, Л 3, Л 4, на которых расположены векторы (0,1,1), (1,2,0), (0,0,1), (1,0,0). А также построим конус К '', образованный лучами Л1Л 2'Л3'Л 4, на которых расположены векторы (0,1,1), (1,3,0), (0,0,1), (1,0,0).
Рис. 1.
Проведём прямую линию C - графическое изображение первого критерия. Эта линия проходит через точку 0 Ь1) параллельно оси ОУ. Линия пересекает плоскость ОКЯ конуса К' в точке (5, 0, 4), приводя к значению 0 первого критерия, которое не является максимальным. Также линия C пересекает плоскость РБО конуса К'. Найдём аналитически точку пересечения плоскости РБО с прямой линией C. Зададим систему из двух уравнений, уравнения прямой C и плоскости РБО. Для этого используем формулы из [4], при этом поменяв первый и третий столбцы местами в уравнении плоско-
u
сти, так как по оси ОХ откладывается 2, а по оси ОZ - 1:
2 - 2-
1 _ У - У1
X - X
1
2 21 У2 У1 х2 х1
2 - 21 У - У1
х - X
22 21 У2 У1 х2 х1 23 - 21 У3 - У1 х3 - х1
0
(4)
Рассмотрим две точки на прямой С - (5, 0,4) и (5, 7, 4), вторая выбрана призвольно. В результате использования их координат, получаем уравнение прямой С:
г - 4 = у = х - 5
0 = 7 = 0 .
Аналогичное уравнение рассматривается в [5]. Подставив координаты точек О, Р, Б (рис. 1) во второе уравнение системы (4), получаем уравнение плоскости РБО :
г -1 у -1 х 1 1 1 1 -1 0
= 0
Далее решаем систему (5):
г - 4 _ у _ х - 5
0
7
г -1 у -1 х -1 1 1
-1 -1 0
= 0
(5)
Найденное решение - х = 5, г = 4, у = 14. С учётом того, что по оси ОХ откладыва-
ется и2, а по оси OZ - и1, максимальное значение 14 первого критерия задачи (1) по-
х = 4 х = 5
лучается при решении 1 , 2 . Действительно, на рисунке видно, что максимальное значение первого критерия может быть только в точке пересечения прямой С с плоскостью РБО. Далее анализируем в каком направлении двигать прямую С для того, чтобы в точке пересечения её с плоскостью РБО координата у = 12,6 (значение первого критерия с уступкой на 10 % от оптимального). Для этого составим и решим систему, выявляющую зависимость первого и второго критериев:
и
х1 + 2 * х2 = 12,6 х1 + 3 * х2 = у
Получаем следующие зависимости:
у -12,6 = х2 х1 = 12,6 - 2 * х2
На х2 в постановке задачи (1) наложено ограничение х2 - 5. Оценим как ведёт себя
переменная х1 при изменении х2. Возьмём х2 = 5, тогда х1 = 2,6 - 4, то есть удовлетво-
х
ряет ограничению исходной задачи (1). Оценим значение х1 при возможном изменении х2, то есть уменьшении относительно 5. Например, при х2 = 4 значение х1 = 4,6.
что
не удовлетворяет ограничению х1 — 4 задачи (1). Таким образом, единственное возмож-
0
ное значение х2 5. Заметим, что в результате анализа выявлено решение х1 2,6,
х2 _ 5, при котором С'_ 12,6, а С'' принимает минимальное значение. Поясним этот факт на геометрической интерпретации (рис. 1). Из предыдущего анализа следует, что сдвиг прямой С по линии Т приводит к пересечению прямой с плоскостью РБО в точке с координатами (5,12,6, 2). Найдём координату 2, составив и решив уравнение плоскости РБО:
2 -1 11,6 5 -1 1 1 -1 -1 0
_ 0
В результате решения уравнения получаем 2 _ 2,6. Таким образом, аналитические рассуждения подтверждаются исследованием геометрического построения - значение
12,6 первого критерия задачи (1) достигается при х1
2,6 х- _ 5
2 . Найдём точку пересе-
чения перемещённой прямой С с плоскостью ОМР. Значение координаты у - это минимальное значение второго критерия при значении первого 12,6. Для этого решим систему из двух уравнений перемещенной прямой С и плоскости ОМР :
2 - 2,6 _ у _ х - 5
0
7
2 -1 у -1 X -1 2 1 -1 -1 0
0
_ 0
В результате получаем х _ 5, 2 _ 2,6, у _ 17,6. Таким образом, решение задачи (1), полученное в результате анализа этой задачи по геометрической интерпретации -х1 _ х2 _ 5, С' _ 12,6, С" _ 17,6 . То есть совпадает с результатами решения примера из работы [3].
Используемый способ анализа задачи (1) позволил получить такое же решение как и вычислительные методы, но более быстро. Кроме того наглядность и общие принципы построения геометрической интерпретации дают возможность решать задачи класса (1) при варьировании коэффициентов. Далее обобщим положения, используемые в разделе 1, и построим геометрическую интерпретацию массовой двухкритериальной задачи.
Геометрическая интерпретация массовой двухкритериальной задачи
Рассмотрим оптимизационную задачу (6):
C — с- * х- + с 2 * ^ ••• ^ Cff * Xff C — с- * x- + с^ * Х2 ^ ••• ^ Cff *
aW *xi + a\2 *Х2 + ••+ a\n *xn — b- (6)
a2i * x- ^a22 *Х2 ^ ••• ^ a2n *Xn — b2 Xy > 0, j —1,2V„,n
В качестве основы построения геометрической интерпретации используются положения из работы [6] Для построения интерпретации введём переменные:
«1 — a- - * x- ^ a-2 * Х2 ^ ••• ^ a-n * Хп «2 — a2- * Х- ^ a22 * Х2 ^ ••• ^ a2n * xn
«3 — с- * Х- + С2 * Х2 ^ ••• ^ Cn * ХП u 4 — с- * Х- + С2 * Х2 ^ ••• ^ Сп * Хп
На основании системы (7) каждому вектору Х — (х-, Х2,•••, Хпj ставится в соответствие две тройки чисел - («2, «3, «1 j и («2, «4, «1 )• Введём в трёхмерном пространстве
прямоугольную систему координат (рис 2) с началом в точке О и осями ОХ, OY, OZ • В этой системе любому вектору X — (х-, Х2,•••, Хп j сопоставляются две точки с координатами («2, «3, «1 j и («2, «4, «1 j^ Образ («2, «3, «1 j произвольного вектора X — (х-, Х2,---, Хп j с неотрицательными компонентами может быть представлен в виде суммы некоторых векторов, расположенных на лучах Л j , j — 1,2V„,п - ими являются
векторы ^Xj * a2j, Xj * с'у, Xj *a-j|, j — 1,2V„,n • Аналогично для образа («2, «4, j рассматриваются векторы на лучах Л j, j — 1,2V„,n, то есть векторы
х] * а2], х. * с], х. * а1. ) . В результате построения получаем два выпуклых многогранных конуса К" и К . Таким образом, множеств
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.