Теоретическая основа линейного программирования, Постановка задачи, Методы решения задач линейного программирования, Симплекс - метод, Геометрический метод - Использование методов линейного программирования

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

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

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

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

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

A11 x1 + a11 x2 + ...... + a11 xn = b1 ,

A21 x1 + a22 x2 + ...... + 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

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

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

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 - свободные переменные задачи.

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

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

Геометрический метод

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

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

A11 x1 + a11 x2 + ...... + a11 xn = b1 ,

A21 x1 + a22 x2 + ...... + a2n xn = b2 ,

Am1 x1 + am2 x2 + ...... + amn xn = bm.

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

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




Теоретическая основа линейного программирования, Постановка задачи, Методы решения задач линейного программирования, Симплекс - метод, Геометрический метод - Использование методов линейного программирования

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