Задачи линейного программирования

1. Определение

1.1. Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции.

1.2. Функция (8) называется целевой функцией (или линейной формой) задачи (8) – (11), а условия (9) – (11) – ограничениями данной задачи.

1.3. Стандартной (или симметричной} задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (9) и (11), где k = m и l = n.

1.4. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (10) и (11), где k = 0 и l = п.

1.5. Совокупность чисел , удовлетворяющих ограничениям задачи (9) – (11), называется допустимым решением (или планом).

1.6. План , при котором целевая функция задачи (8) принимает свое максимальное (минимальное) значение, называется оптимальным. Значение целевой функции (8) при плане Х будем обозначать через . Следовательно, X* – оптимальный план задачи, если для любого Х выполняется неравенство [соответственно ].

2. Примеры.

2.1. Записать в форме основной задачи линейного программирования следующую задачу: найти максимум функции при условиях

3. Теорема

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

3.2. Если система векторов в разложении (16) линейно независима и такова, что(18) где все то точка является вершиной многогранника решений.

3.3. Если – вершина многогранника решений, то векторы , соответствующие положительным в разложении (16), линейно независимы.

4. Методы решения задач

4.1. Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного итеративного процесса, необходимо улучшающего значение целевой функции на каждом шаге. Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с 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.2. Геометрический метод Применяется для задач с двумя переменными. Метод решения состоит в следующем: На плоскости Ох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 в этой точки.

4.3. Графический метод Если система ограничений задачи линейного программирования представлена в виде системы линейных неравенств с двумя переменными, то такая задача может быть решена геометрически. Таким образом, данный метод решения ЗЛП имеет очень узкие рамки применения. Однако метод представляет большой интерес с точки зрения выработки наглядных представлений о сущности задач линейного программирования. Геометрический (или графический) метод предполагает последовательное выполнение ряда шагов. Ниже представлен порядок решения задачи линейного программирования на основе ее геометрической интерпретации. 1. Сформулировать ЗЛП. 2. Построить на плоскости {х1, х2} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств. 3. Найти полуплоскости, определяемые каждым из ограничений задачи. 4. Найти область допустимых решений. 5. Построить прямую c1x1+ c2x2= h, где h - любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений. 6. Перемещать найденную прямую параллельно самой себе в направлении увеличения (при поиске максимума) или уменьшения (при поиске минимума) целевой функции. В результате, либо отыщется точка, в которой целевая функция принимает максимальное (минимальное) значение, либо будет установлена неограниченность функции на множестве решений. 7. Определить координаты точки максимума (минимума) функции и вычислить значение функции в этой точке.