5.3. Линейное программирование

Рассмотрим систему неравенств вида где — матрица размерностью действительными элементами, X — вектор-столбец размерностью , состоящий из неизвестных действительных чисел, заданная вектор-строка размерностью . В общем случае и система является неопределенной. Решения находятся по значениям некоторой функции дохода, т. е. по специальному фактору, значение которого должно быть максимальным.

Пример. Мастерская по производству нестандартной мебели получила одновременно два заказа. Для изготовления одного комплекта первого типа нужно одиннадцать заготовок и работы, для второго —4 заготовки и работы. В распоряжении мастера имеется 46 заготовок и времени; кроме того, он знает, что в первом заказе он получит за каждую вещь, а во втором — только Как он должен организовать свою работу?

Если — число предметов мебели, сделанных по каждому из заказов, мы получаем

1) (условие по фурнитуре),

2) (условие по времени),

3) (условие максимума).

Пусть имеется некоторая система линейных неравенств типа при Поскольку равенствами манипулировать Проще, чем неравенствами, обычно вводят вспомогательные переменные называемые невязками, с помощью которых нашу систему можно записать в следующем виде:

или, если использовать матричную запись,

Идея состоит в том, чтобы, исходя из очевидного решения , улучшить его счет максимально возможного увеличения значения той переменной, кото рая дает наибольщее приращение функции дохода

Используемый нами градиент в данном случае задается непосредственно последней строкой, и очевидно, что на первом Зтапе йаиболее «доходной» является переменная Итак, запишем

или, в матричной форме,

Следовательно, функция дохода равна 644/11, когда стремится к своему максимальному значению, т. е. остается равным 0, а На самом деле мы осуществили обычное перемещение вдоль оси которое показывает, что может продолжать увеличиваться — на этот раз при возрастании чей градиент составляет

Теперь коэффициент при во втором уравнении равен 5 —

— 12/11, или 43/11, и мы получаем

В матричной форме имеем

Это новое преобразование и вытекающие из него линейные комбинации показывают, что все градиенты, все относительные выигрыши в (последняя строчка предыдущей матрицы) отрицательны или равны нулю. Таким образом, оптимум достигнут; он составляет

при

В двумерном пространстве мокно непосредственно изобразить пространство поиска и интерпретацию этого градиентного алгоритме, (разработанного Данцигом (1959) и известного как симплекё-метод (рис. 5.5)).

Выйдя из начала координат (точка мы следуем по линии самого крутого склона (в соответствии с выражением и попадаем в точку а затем в точку которая является допустимой, удовлетворяет уравнениям и находится на максимальном расстоянии от начала прямой

Система уравнений имеет решение только в действительных числах.

Рис. 5.5. Симплекс-матод в линейном программировании.

Приемлемое для мастера решение получается только в том случае, если заказы первого и второго типов повторяются достаточно часто, чтобы разумно округлять получаемые количества предметов мебели до соответствующих целых: В противном случае задача, в которой могут быть только целыми числами, существенно отличается от предыдущей, поскольку пространство поиска не является в этом случае непрерывным и йряд ли может быть выпуклым. Принципиально другие методы, используемые для задач последнего типа, рассмотрены в гл. 8.

В матричной форме симплекс-метод легко может быть распространен на случай произвольного числа переменных и уравнений. Процедура сводится к последовательности линейных комбинаций, которые выбираются по результатам проверки значений градиентов. Когда они все становятся отрицательными, процедура завершается.

5.3.1. Формализация симплекс-алгоритма

Симплекс-алгоритм сложность которого не является полиномиальной, использует несколько простых свойств, выполняющихся для линейных задач.

1. Неравенства определяют ограниченные гиперплоскостями замкнутые выпуклые подпространства на

2. На пересечении некоторого конечного числа выпуклых подпространств образуется выпуклое тело, которое мы будем называть полиэдром, если оно ограничено, и политопом — в противном случае.

3. Любая точка некоторого полиэдра может быть описана как линейная комбинация вершин, или точек-экстремумов, торые являются пересечениями исходных гиперплоскостей. Число этих точек конечно и не превышает (если мы имеем гиперплоскостей (неравенств)).

4. Оптимум не может быть достигнут в точке, расположенной строго внутри политопа (см определение выше), потому что тогда мы могли бы с помощью линейной комбинации построить на границе полиэдра точку, в которой функция дохода принимала бы более высокое значение. Нели задача не вырождена, т. е. если ранг (детерминант) матрицы А не равен то значение может быть улучшено за счет продвижения по гиперребру до следующей вершины.

5. Мы будем называть базовой квадратной матрицей матрицы А любое подмножество индексов из множества которому соответствует базовая квадратная матрица В, выделенная из А и имеющая ранг Сказанное выше эквивалентно утверждению. «Оптимум системы линейных неравенств может быть достигнут при решении уравнения с базовой квадратной матрицей матрицы А». Если матрица А разбивается на матрицы В и и система записывается в виде

то базовое решение определяется единственным способом:

Симплекс-алгоритм работает только с базовыми квадратными матрицами, имеющими решение (т. е. с такими, в которых и переходит от одйой вершины к другой, используя метрд градиента. На каждом этапе из базовой квадратной матрицы удаляется один индекс: одна из переменных обращается в нуль, а другая попадает в базовую квадратную матрицу, т. е. произвольная переменная принимает ненулевое значение. Сходимость обеспечивается конечностью числа вершин политопа.