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

позволяет отыскивать крайние точки многогранника
решений путем решения вопроса о линейной незави-
симости некоторой системы векторов A 1 , ..., А т ,
которые образуют базис некоторого m-мерного про-
странства. Эту задачу вполне можно решить при
помощи метода исключения Жордана — Гаусса (см.,
например, [8]).
   Однако в системе из n векторов содержится Сnm
(число сочетаний из n по т) систем т линейно не-
зависимых векторов. Для больших значений т и n
(что часто выполнено на практике) это число очень
велико, поэтому число крайних точек, соответствующих
таким системам, достаточно велико, и практическое
решение подобной задачи затруднительно. Необходим
общий метод целенаправленного перехода от одной
крайней точки к другой, учитывающий лишь
уменьшение на каждом шаге целевой функции. Тако-
вым является симплекс-метод, подробное описание
которого можно найти, например, в [8], куда мы и
отсылаем читателя.
   3. Графический метод решения. Он основан на
геометрической интерпретации задачи линейного
программирования и применяется в основном в случае
двух неизвестных.
   Построим многоугольник решений системы огра-
ничений



ограничиваясь, кроме того, случаем неотрицательных
значений х1 и х2. Мы знаем, что область решений есть
выпуклый многоугольник, лежащий в первом
координатном углу системы координат. Линейная
функция f = с1х1 + с2х2 задачи линейного программи-
рования при фиксированном значении f = const является
уравнением прямой линии с1х1 + с2х2 = const. Теперь
решаемой задаче можно придать следующую
интерпретацию: найти точку многоугольника М, че-
рез которую проходит прямая с1х1 + с2х2 = const и
значение f которой минимально. Значения f = c1x1 + +
с2х2 возрастают в направлении вектора N = (c1, c2),
поэтому следует взять прямую f = 0 и передвигать
ее параллельно самой себе в направлении этого век-
                                                  261