Теоретическая основа линейного программирования

Постановка задачи

Постановка практической задачи ЛП включает следующие основные этапы:

• · определение показателя эффективности, переменных задачи,
• · задание линейной целевой функции S (x), подлежащей минимизации или максимизации,
• · задание ограничений.

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

Дана система линейных уравнений с n неизвестными:

a11×1 + a11×2 + … + a11 xn = b1,.

a21×1 + a22×2 + … + a2n xn = b2,.

am1 x1 + am2 x2 + … + amn xn = bm,.

и линейная функция.

f = c1 x1 + c2 x2 +…+ cn xn (1.2).

Требуется найти такое неотрицательное решение системы.

x1 ?0, x2 ?0, xn ?0 (1.3).

при котором функция f принимает наименьшее значение.

Уравнения (1.1) называют системой ограничений данной задачи; функцию f — целевой функцией (или линейной формой).

Методы решения задач линейного программирования

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

Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1,…, Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1,…, Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1:

X0 + A0, m+1*Xm+1 +… + A0, n*Xn = A0,0.

X1 + A1, m+1*Xm+1 +… + A1, n*Xn = A1,0.

Xi + Ai, m+1*Xm+1 +… + Ai, n*Xn = Ai, 0.

Xm + Am, m+1*Xm+1 +… + Am, n*Xn = Am, 0.

Данная формальная модель задачи линейного программирования обычно задается в форме так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода:

Симплекс-таблица 4.

Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X1,…, Xm). Сверху от таблицы приведен набор всех переменных задачи, где Xm+1,…, Xn — свободные переменные задачи.

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

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

Геометрический метод Применяется дя задач с двумя переменными. Метод решения состоит в следующем:

На плоскости Ох1×2 строятся прямые, которые задают соответствующие ограничения:

a11×1 + a11×2 + … + a11 xn = b1,.

a21×1 + a22×2 + … + a2n xn = b2,.

am1 x1 + am2 x2 + … + amn xn = bm.

Находим множество всех точек х1, х2, удовлетворяющим всем неравенствам. Такое множество называется областью допустимых решений. Строим вектор и перемещаем линию уровня, который задается уравнением: с1×1+с2×2 = const в направлении вектора до последней точки пересечения с ОДР. Эта точка и дает решение задачи Lmax = значению L в этой точки.