Основная задача линейного программирования

Занятие № 8

Тема «Основная задача линейного программирования»

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

Цель развития: Развитие логического мышления

Цель воспитания: Воспитание интереса к предмету, к экономическим процессам.

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

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

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

a₁₁x₁ + a₁₂x₂ +… + a_1nx_n b₁

a₂₁x₁ + a₂₂x₂ +… + a_2nx_n b₂

…………………………………………….

a_m1x₁ + a_m2x₂ +… + a_mnx_n b_m

Среди неотрицательных решений этой системы требуется найти такое решение, при котором линейная функция (целевая функция)

L = c₁x₁ + c₂x₂ + … +c_nx_n+ c₀

принимает наибольшее (наименьшее) значение или, как говорят, максимизировать (минимизировать0 линейную форму L.

Графическое решение основной задачи линейного программирования.

Рассмотрим систему линейных неравенств с двумя переменными. Пусть, кроме того задана линейная функция L = c₁x₁ + c₂x₂ + c₀. Найдём среди множества точек (х₁; х₂) из области решений совместной системы неравенств такие, которые придают заданной линейной функции наименьшее (наибольшее) значение. Для каждой точки плоскости функция L принимает фиксированное значение L = L₁. Множество всех таких точек есть прямая c₁x₁ + c₂x₂ + c₀ = L₁, перпендикулярная вектору C(c_1; c₂), выходящему из начала координат. Если эту прямую передвигать параллельно самой себе в положительном направлении вектора С, то линейная функция L = c₁x₁ + c₂x₂ + c₀ будет возрастать, а в противоположном направлении – убывать. Пусть при движении прямой L в положительном направлении вектора С она впервые встретится с многоугольником решений в его вершине, тогда в этом положении L₁ прямая L становится опорной, и на этой прямой функция L принимает наименьшее значение. При дальнейшем движении в том же направлении (положительном) прямая L пройдёт через другую вершину многоугольника решений, выходя из области решений, и станет также опорной прямой L₂; на ней функция L принимает наибольшее значение среди всех значений, принимаемых на многоугольнике решений.

Таким образом, минимизация и максимизация линейной функции L = c₁x₁ + c₂x₂ + c₀ на многоугольнике решений достигаются в точках пересечения этого многоугольника с опорными прямыми, перпендикулярными вектору C(c_1; c₂). Опорная прямая может иметь с многоугольником решений либо одну общую точку (вершину многоугольника), либо бесконечное множество точек (это множество есть сторона многоугольника).

Многоугольник решений называется областью Парето.

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

Задача 1. Максимизировать линейную форму Z = 2x₁ + x₂ при ограничениях: 3х₁ + х₂ ; 2х₁ + 4х₂ х₁

Задача 2. Максимизировать линейную форму L = 2x₁ + x₂ при ограничениях:

3х₁ - 2 х₂ ; 3х₁ + х₂ 3; х₁

Задача 3. Минимизировать линейную форму L = 12x₁ + 4 x₂ при ограничениях: х₁ + х₂ 2; х₁ ; х₂ х₁ – х₂ 0;

Задача 4. Минимизировать линейную форму L = x₁ + 2x₂ при ограничениях: 3х₁ + 4х₂ -6х₁ + 5х₂ 12; 4х₁ + 3х₂ 24;