1.7. Геометрическая интерпретация однородной задачи линейного программирования.
Рассмотрим вначале однородную задачу линейного программирования на плоскости.
Каждому ограничению вида неравенства:
,
(1)
- соответствует
замкнутая полуплоскость
границей, которой является прямая линия
,
определяемая соответствующим уравнением:
.
(2)
Системе ограничений однородной задачи:
(3)
- соответствует
пересечение полуплоскостей
Тривиальным ограничениям:
и
,
(4)
- также соответствуют
полуплоскости
и
При этом
называют, обычно, верхней (координатной)
полуплоскостью, а
- правой (координатной) полуплоскостью.
Таким образом, ОДР однородной задачи ЛП на плоскости представляет из себя пересечение конечного числа замкнутых полуплоскостей.
Очевидно, каждая полуплоскость является выпуклым множеством. По теореме 1 п. 1.5. их пересечение также выпукло.
Определение 1. Область, которая являеться пересечением конечного числа замкнутых полуплоскостей называется замкнутой выпуклой многоугольной областью.
Если замкнутая выпуклая многоугольная область ограничена, то она называется замкнутым выпуклым многоугольником.
В примере №1 п.1.4. это замкнутый выпуклый пятиугольник ОАВСД.
Целевой функции.
(5)
соответствует
вектор роста
и
линии уровня
(6)
На рисунке 1. п 1.4. это линии (А) и (В).
При этом значение
функции
растет
в направлении вектора роста
,
перпендикулярного линиям уровня.
Таким образом, геометрически однородная задача ЛП на плоскости может быть сформулирована следующим образом: найти крайнюю (угловую) точку, в которой линия уровня все еще пересекает замкнутую выпуклую многоугольную область при параллельном переносе этой линии в направлении вектора роста (или в противоположном направлении).
В трехмерном пространстве R3 каждому линейному неравенству
(7)
Соответствует одно из замкнутых полупространств, на которые делит все пространство R3 плоскость i , определенная уравнением:
(8)
Соответственно
вектор роста
перпендикулярен каждой поверхности
уровня целевой функции, задаваемой
уравнением:
,
(9)
где С – некая произвольная константа.
Определение 2. Область, которая являеться пересечением конечного числа замкнутых полупространств в R3 называется выпуклой многогранной областью. Ограниченная выпуклая многогранная область называется выпуклым многогранником.
Однородная задача ЛП в пространстве R3 может быть сформулирована так: найти крайнюю (угловую) точку, в которой поверхность уровня при движении в направлении вектора роста (или в противоположном направлении) все еще пересекает заданную выпуклую многогранную область.
Заметим, что при этом поверхность уровня представляет из себя плоскость, определяемую уравнением (9). Вектор роста является вектором нормали этой плоскости.
Соответствующая формулировка в n – мерном пространстве Rn фактически совпадает с данной. Единственное отличие состоит в том, что уравнение поверхности уровня:
(10)
задает не плоскость, а гиперплоскость в Rn.