Математические методы в библиотечной работе. Елизаров А.М - 262 стр.

      Рис. 75. Основная за-   Рис. 76. Первая пато-
             дача ЛП                   логия

тора до искомой точки (рис. 75). Какие же точки
будут искомыми? Кажется очевидным, что минималь-
ного значения функция f достигает в крайней точке
многоугольника М. Строгое обоснование этому нa-
блюдению содержится в приведенной выше теореме 5.
Из этой теоремы вытекает, что для решения задачи
линейного программирования необходимо исследовать
лишь крайние точки многоугольника допустимых
решений и выбирать из них те, в которых прямая,
параллельная прямой f = 0, является опорной. На
рис. 75 это прямые L1 и L2. Минимальное значение
для f достигается на прямой L 1 .
   Рассмотренный случай неявно предполагал, что
область решений М является ограниченным выпуклым
многоугольником. Что же может произойти, если
М — неограниченный выпуклый многоугольник? Ока-
зывается, могут встретиться две различные ситуации.
   1. Прямая f = const при передвижении в направ-
лении вектора N постоянно пересекает многоуголь
ник решений и ни в одной крайней точке не является
опорной к многоугольнику. В этом случае линейная
функция основной задачи линейного программирова-
ния принимает любые значения, а сама задача решения
не имеет (рис. 76).
   2. Прямая f = const при передвижении в направ-
лении вектора N становится опорной, но линейная
функция принимает значения, ограниченные лишь с
одной стороны (или снизу, или сверху) (рис. 77).
В этом случае задача линейного программирования
может иметь решение лишь на отыскание или мини-
мума, или максимума (но не того и другого сразу).
262