Решение задач Линейного программирования графическим методом

 

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

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

В общем виде модель записывается следующим образом:

1) целевая функция:

Z(x) = c₁x₁ + c₂x₂ +... + c_nx_n → max(min);

(1)

2) ограничения

(2)

 

3) требование неотрицательности

x_j ≥ 0, (3)

При этом a_ij, b_i, cj ( ) - заданные постоянные величины.

 

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

Систему ограничений (2) называют функциональными ограничениями задачи, а ограничения (3) - прямыми.

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

Если система ограничений задачи линейного программирования представлена в виде системы линейных неравенств с двумя переменными, то такая задача может быть решена геометрически. Таким образом, данный метод решения ЗЛП имеет очень узкие рамки применения.

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

Геометрический (или графический) метод предполагает последовательное выполнение ряда шагов. Ниже представлен порядок решения задачи линейного программирования на основе ее геометрической интерпретации.

1. Сформулировать ЗЛП.

2. Построить на плоскости {х1, х2} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

3. Найти полуплоскости, определяемые каждым из ограничений задачи.

4. Найти область допустимых решений.

5. Построить прямую c₁x₁ + c₂x₂ = h, где h - любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений.

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

7. Определить координаты точки максимума (минимума) функции и вычислить значение функции в этой точке.