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

и целевая функция g = b1у1 + ... + bkyk. Найти среди
всех неотрицательных решений y 1 , ..., у k данной
системы такое, которое дает g наибольшее значение.
   Сравнение двойственных задач показывает, что:
1) коэффициенты при j-м неизвестном в i-м уравнении
системы (3) и при i-м неизвестном в j-м уравнении
системы (3') одинаковы; 2) свободные члены нера-
венств в каждой из задач совпадают с коэффициен-
тами при неизвестных в линейной функции другой
задачи; 3) в задаче А идет речь о минимизации функ-
ции f, а в задаче А' — о максимизации функции g.
   Одна из основных теорем теории линейного
программирования позволяет сводить решение задачи
А к решению задачи А' и наоборот.
   Теорема двойственности. Если задача А
имеет решение, то и двойственная задала А' разре-
шима. При этом минимум функции f равен макси-
муму функции g.
   Доказательство теоремы требует привлечения
некоторых специальных разделов линейной алгебры,
поэтому мы его не приводим. Рассмотрим примеры
применения теоремы двойственности.
   Пример 1. Пусть при планировании работы
отдела возникла задача с ограничениями



Требуется найти неотрицательные значения x1, х2, х3, при
которых функция f = 3х1 + 2x2 принимает наибольшее
значение.
   Пусть возникшая задача будет задачей А. Двой-
ственная к ней задача А' имеет следующий вид: при
ограничениях




найти неотрицательные значения y1, y2, при которых
функция g = 2y1 + y2 принимает наименьшее значение.
Тогда по теореме двойственности искомый mах f
= = min g.
   Решим задачу А' графическим методом. Для этого
построим многоугольник допустимых решений М
                                                     265