ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Тема 2. Линейное программирование

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

Рассмотрим систему уравнений и неравенств с переменными (неизвестными):

(1)

и линейную функцию:

(2)

Требуется найти решение системы (1) при котором целевая функция принимает оптимальное значение (максимальное или минимальное).

Такая задача называется задачей линейного программирования в общем виде. Система (1) называется системой ограничений (областью допустимых решений). Функция (2) называется целевой функцией.

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

Рассмотрим задачу ЛП в стандартной форме для случая двух переменных :

(9)

(10)

Пусть система неравенств (10) совместна (имеет хотя бы одно решение). Любое неравенство этой системы геометрически определяет полуплоскость с граничной прямой Условия не отрицательности определяют полуплоскости с соответственными граничными прямыми и .

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

Решение ЗЛП геометрически представляет собой поиск такой точки многоугольника решений, координаты которой доставляют целевой функции наибольшее (наименьшее) значение. Причем допустимым решением являются все точки многогранника.

Рассмотрим так называемую линию уровня целевой функции z, то есть линию, вдоль которой эта функция принимает одно и то же фиксированное значение : или

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

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

целевой функции z в любой точке область допустимых решений.

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

3. Для нахождения координат оптимальной точки, надо решить систему уравнений, которая соответствует прямым, пересечение которых образует эту точку. Значение целевой функции в этой точке будет оптимальным, а сами координаты точки будут являться решением задачи ЛП.

Пример. Решить геометрически задачу:

Построим многоугольник всех допустимых решений OABCD и направляющий вектор целевой функции (Рис. 1). Направление вектора-градиента указывает направление возрастания целевой функции. Так как рассматриваемая задача на отыскание максимума, то прямую, перпендикулярную вектору перемещаем в направлении этого вектора параллельно самой себе до тех пор, пока эта прямая не покинет область допустимых решений. На границе области, в нашем случае в точке С, и будет решение задачи. Точка C находится на пересечении прямых и . Следовательно, ее координаты определяются решением системы этих уравнений уравнении:

откуда т.е. точка С имеет координаты (6, 4).

Рис. 1

Максимум (максимальное значение целевой функции) равен: Ответ: при оптимальном решении т.е. максимальна прибыль может быть достигнута при производстве 6 единиц первой и 4 единиц второй продукции.

Решить геометрически задачу линейного программирования:

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

Ответ запишется следующим образом: конечного оптимума целевая функция не имеет,

Замечание.В некоторых случаях неограниченности области допустимых решений целевая функция может достигать своего оптимума.

Рис. 2