Теоретические сведения

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

Если число входных параметров (искомых переменных) равно двум, то задача линейного программирования имеет наглядное графическое решение.

Пример:

где D - область допустимых значений переменных х₁, х₂.

Построим систему координат x₁0x ₂,. так как x_i ≥ 0, то вся область D принадлежит первому координатному углу.

1-й этап. Изображение области В на плоскости.

Обозначим D₁- множество точек (x₁, х₂), удовлетворяющих неравенству (1). Вся плоскость разбивается на множество точек, принадлежащих D ₁ (условие выполняется) и не принадлежащих D₁ (условие не выполняется). Построим границы области D₁. На плоскости это будет прямая х₁-2х₂=1 или х₁= 1+2x₂. Ее можно построить по двум точкам: (0; -0,5), (1; 0). Полученная прямая делит плоскость на две полуплоскости. Одна из них удовлетворят условию, а вторая - нет. Чтобы проверить, какая полуплоскость удовлетворяет условию, надо взять любую точку плоскости и подставить ее координаты в условие (1.1). Если условие выполняется, то точка находится в полуплоскости принадлежащей В. Например, подставим точку (0, 0) - неравенство выполняется, следовательно, D₁ находится выше прямой.

Аналогичным образом строятся неравенства (2) и (3). Область D - точки, которые одновременно принадлежат D₁, D₂ и D₃ (рис. 1).

Замечание: Если условие имеет вид равенства, то множество точек, удовлетворяющих ему - это прямая.

Условия (1.1) и (1.3) дают треугольник ОАВ. Второе условие дает прямую х₁=х₂. Так как условия должны выполняться одновременно, то областью D будет отрезок ОС внутри D₁.

Рис. 1.1 - Область допустимых значений

2-й этап. Изображение целевой функции.

Целевая функция - это функция, для которой нужно найти min или mах. Если она зависит от двух переменных, то ее изображают в виде линий равного уровня - таких линий, в каждой точке которых функция имеет одинаковое значение.

Рассмотрим способ построения линий равного уровня. Зафиксируем любое значение q, например, q= 0. Получим уравнение x₁ - х₂ = 0 - это будет линия q = 0. Зафиксируем другое значение, например, q = -1. Получим две линии уровня - параллельные прямые. При переходе от линии q = 0 к линии q=-1 целевая функция уменьшается, и т. к. нужно найти минимум, то она "улучшается", т. е. при перемещении линии уровня в направлении, указанном стрелкой (рис. 1.2), целевая функция уменьшается.

Для решения задачи ЛП надо найти такую точку, чтобы она лежала на границе области D и через нее проходила линия равного уровня с минимальным значением q. Очевидно, что линия q = -1 не является оптимумом. Этим свойством будет обладать линия, проходящая через точку b.