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

и линейная функция f = сГх1 + с2х2 + ... + спхп. Требуется
найти такие неотрицательные значения х1 ≥ 0, x2 ≥ 0, ...,
хп ≥ 0, при которых функция f принимает наименьшее
значение.
    Геометрическая интерпретация. Как уже отмеча-
лось в п. 1, область решений системы линейных
уравнений (4) представляет собой выпуклый много-
гранник допустимых решений. Поэтому геометри-
чески решение задачи линейного программирования
представляет собой отыскание такой точки много-
гранника решений, координаты которой доставляют
линейной функции минимальное значение. Эта точка и
представляет собой оптимальное решение.
    В теории линейного программирования доказана
важная
   Теорема 5. Линейная функция задачи линейного
программирования достигает минимального значения
в крайней точке выпуклого многогранника решений.
Если эта функция принимает минимальное значение
более чем в одной точке, то она достигает того
же значения в любой точке, являющейся линейной
комбинацией этих крайних точек.
   Таким образом, для решения задач линейного
программирования важно уметь отыскивать крайние
точки. Опишем общий способ нахождения этих точек.
Для этого перепишем систему ограничений в виде

                                                                        (5)
где А 1 = (а 11 , а 21 , ..., а k1 ), ..., А п = (а 1n , а 2n , ..., а kn ),
А0 = (b1, ..., bk), X = (x 1 , ..., xn). Справедлива следую-
щая общая
    Теорема 6. Если система векторов А1, ..., А m (т ≤ п) в
представлении системы ограничений (5) линейно
независима и такова, что х 1 А 1 + ... + х т А т = А 0 и все
xi ≥ 0, то точна Х0 == (х1, х2, ..., хт, 0, ..., 0) является
крайней точкой многогранника решений. Если Х = (x1,
..., xn) — крайняя точка многогранника ре-шений, то
векторы в разложении (5), соответствую-щие
положительными xi, линейно независимы.
     В простейшем случае с данной теоремой мы по-
 знакомились в п. 1 при описании способа нахождения
 крайних точек области М; в общем случае доказа-
 тельство теоремы гораздо более сложное. Теорема 6
 260