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

и вектор N = (4, 6). Перемещаем прямую f = 0 па-
раллельно самой себе в направлении вектора N.
Построенный многоугольник показывает, что прямая
f = const впервые коснется многоугольника решений
и станет опорной по отношению к нему в точке С.
Если прямую f перемещать далее в направлении N,
то значения f возрастут, следовательно, в точке С
линейная функция f принимает наименьшее значение.
Вычислим его.
    Точка С лежит на пересечении прямых L 1 и L2 .
Для нахождения ее координат решим правильную
подсистему уравнений


Для этого из второго уравнения выразим х1 = 8 — 2x2 и
подставим в первое. Получим 24 — 5х2 = 9, откуда х2
= 3. Следовательно, х1 = 8 — 2 • 3 = 2. Вычисляя значение f
= 4х1 + 6х2 для х1 = 2 и х2 = 3, находим, чтo f m i n = 2 6 .
    4. Теорема двойственности. Мы уже сталкивались
в разделах, связанных с алгеброй множеств или ал-
геброй высказываний, с двойственными утвержде-
ниями. Они представляли правила, позволяющие по
одному утверждению теории построить другое утверж-
дение таким образом, что из истинности одного не-
медленно следовала истинность другого. Познако-
мимся с теоремой подобного рода в линейном про-
граммировании.
    Предположим, нам необходимо решить задачу
линейного программирования с системой ограничений
(3) и целевой функцией f = с1х1 + с2х2 + ... + спхп.
Необходимо отыскать среди всех неотрицательных
решений x1, x2, ..., хп данной системы такое, которое
дает f наименьшее значение. Назовем исходную за-
дачу задачей А.
    Свяжем с задачей А новую, двойственную задачу
А', которая будет заключаться в следующем. Даны
система ограничений

                                                         (3')

264