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

Математически задача линейного программирования в общем виде формулируется следующим образом:

найти такие  которые при условиях

                                             (3.71)

            (3.72)

обеспечивают минимум суммы

                                             (3 73)

Здесь ,  и  — константы.

Сформулированная задача является главной и, как можно показать, используя принцип двойственности, математически эквивалентна следующей «двойственной задаче»:

найти такие  которые при условиях

                               (3.74)

обеспечивают максимум суммы

                                                              (3.75)

Фиг. 3.29. Геометрическая интерпретация метода линейного программирования.

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

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

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