Теоретическая основа линейного программирования, Симплекс метод - Линейное программирование

Симплекс метод

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

Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с 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

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

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

1

X1

X2

Xm

Xm+1

Xn

X0

A0, 0

0

0

0

A0, m+1

A0, n

X1

A1, 0

1

0

0

A1, m+1

A1, n

X2

A2, 0

0

1

0

A2, m+1

A2, n

Xm

Am, 0

0

0

1

Am, m+1

Am, n

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

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

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

Похожие статьи




Теоретическая основа линейного программирования, Симплекс метод - Линейное программирование

Предыдущая | Следующая