Практическая работа 1

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

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

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

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

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

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

Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи и записывается в общем виде как

При ограничениях:

где x_j — неизвестные; a_ij, b_i, c_j — заданные постоянные величины. Все или некоторые уравнения системы ограничений могут быть записаны также в виде неравенств.Математическая модель в более краткой записи имеет вид:

  при ограничениях: 

Совокупность значений неизвестных (x₁, x_2,…,x_n), удовлетворяющих системе ограничений, называется допустимым решением, или планом задачи линейного программирования, а ограничения определяют область допустимых решений(ОДР).Допустимое решение задачи линейного программирования называется оптимальным, если оно обеспечивает максимальное(минимальное) значение целевой функции.

Если все ограничения заданы уравнениями и переменны еx_j неотрицательные, то модель называется —канонической. Если хотя бы одно ограничение является неравенством, то модель называется —неканонической.

 Для составления математической модели необходимо:

 Обозначить переменные;

 Составить целевую функцию исходя из цели задачи;

 Записать систему ограничений, учитывая имеющие в условии задачи показатели и их количественные закономерности.

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

Графический метод основан на геометрическом представлении допустимых решений и целевой функции задачи. Каждое из неравенств задачи линейного программирования определяет на координатной плоскости (x₁, x₂) некоторую полуплоскость. Пересечение этих полуплоскостей задает область допустимых решений(ОДР),то есть любая точка из этой области является решением системы ограничений.

В общем случае область допустимых решений может быть представлена одной из следующих фигур: выпуклым многоугольником, неограниченной многоугольной областью, лучом, отрезком, точкой или пустой областью.В последнем случае говорят, что ограничения несовместны.Если система ограничений включает равенства, то они определяют на координатной плоскости(x₁,x₂)прямую линию. Область допустимых решений всегда представляет собой выпуклую фигуру.

 

 Рис.1.Геометрическая интерпретация ограничений и целевой функции задачи линейного программирования

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

Целевая функция задачи линейного программирования при фиксированном значении L определяет на плоскости прямую линию L = c₁ x₁ + c₂ x₂. Изменяя значения L, получим семейство параллельных прямых, называемых линиями уровня.

 Для нахождения экстремального значения целевой функции используют вектор 푔⃗⃗⃗⃗푟⃗⃗푎⃗⃗⃗푑⃗퐿=⃗퐶наплоскостиX₁OX₂, который показывает направление наискорейшего изменения целевой функции, он равен:

 Где e₁и e₂—единичные векторы по осям ОX₁и ОX₂.Таким образом,

Координатами вектора 퐶 являются коэффициенты целевой функцииL(x).

Алгоритм решения задачи ЛП графическим методом

 

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

Для этого каждое из неравенств системы заменяем равенством и строим соответствующие этим равенствам граничные прямые. Каждая из построенных прямых делит плоскость на две полуплоскости. Чтобы графически определить, по какую сторону от граничной прямой располагается полуплоскость, содержащая решения, удовлетворяющие рассматриваемому неравенству, достаточно проверить одну какую-либо точку, не лежащую на прямой (например (0,0)). Если при подстановке ее координат в левую часть неравенства оно выполняется, то надо заштриховать полуплоскость, содержащую данную точку. Если же неравенство не выполняется, надо заштриховать полуплоскость, не содержащую данную точку. Отмечаем общую область для всех не равенств. Таким образом, получим область допустимых решений рассматриваемой задачи ЛП.

 

 Формируем графическое изображение целевой функции.

Приравняем целевую функцию к постоянной величине L:L=c₁x₁+c₂x₂. Это уравнение при фиксированном значении L определяет прямую, а при изменении L семейство параллельных прямых, каждая из которых называется линией уровня. Проводим линию уровня L_0.

 

 Определяем направление возрастания целевой функции (вектор퐶).

Для определения направления максимального возрастания значения целевой функции строим вектор-градиент целевой функции, который начинается в точке (0,0), заканчивается в точке (c₁, c₂). Если линия уровня и вектор-градиент построены верно, то они будут перпендикулярны.

 Находим оптимальное решение задачи ЛП.

Линию уровня перемещаем по направлению вектора 퐶 для задач на максимум и в направлении, противоположном 퐶, для задач на минимум. Перемещение линии уровня производится до тех пор, пока у нее окажется

Только одна общая точка с областью допустимых решений(ОДР).Эта точка

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

  Находим координаты точки экстремума и значение целевой функции в этой точке.

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

  Задача1.

Найти наибольшее значение функции L=x₁+x₂ при ограничениях:

x1	+	3 x2	≤	6,
2 x1	+	x2	≤	8,

x₁ ≥0                          x₂ ≥ 0.

 Решение:

 Рассмотрим первое не равенство системы ограничений.

x₁ + 3 x₂≤6.

Построим прямую:x₁ + 3 x₂ = 6.Пусть x₁ =0 => 3 x₂ = 6 => x₂ = 2.Пустьx₂ =0=>x₁ =6.

Найдены координаты двух точек(0,2)и(6,0).Соединяем их и получаем

Необходимую прямую(1).

Вернемся к исходному неравенству

x₁+3x₂≤6,3x₂≤-x₁+6,

x₂≤-1/3x₁+2.

Знак не равенства «≤», следовательно, решение не равенства–множество точек, расположенных ниже прямой (1),включая эту прямую.

 Рассмотрим второе не равенство системы ограничений.

2 x₁ + x₂ ≤8.

Построим прямую:                                     2x₁ + x₂= 8.

Пусть x₁ =0=>x₂ =8.

Пусть x₂ =0=>2x₁= 8=> x₁ = 4.

Найдены координаты двух точек(0,8)и(4,0). Соединяем их и получаем

Необходимую прямую(2).

Вернемся к исходному не равенству.

2 x₁ + x₂≤8,x₂≤-2x₁+8.

Знак не равенства «≤», следовательно, решение не равенства–множество точек, расположенных ниже прямой(2), включая эту прямую.

 Строим вектор 퐶 {1;1}, координатами которого являются коэффициенты функции L.

 Перемещаем линию уровня (красную прямую),перпендикулярно данному вектору, от левого нижнего угла к правому верхнему.

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

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

Функция L достигает наибольшего значения в точке A.(см.рисунок справа)

Точка A одновременно принадлежит прямым(1) и (2).Составим систему уравнений:

x1	+	3 x2	=	6		x1= 18/5
2 x1	+	x2	=	8	=>	x2=4/5

 

Вычислим значение функции L в точке A(18/5; 4/5).

L(A)= 1 ∙18/5+1∙4/5=22/5.

 Ответ:x₁= 18/5; x₂= 4/5; L_max= 22/5.

 Задача 2.

Найти наименьшее значение функции L=x₁+x₂ при ограничениях:

 

x1	+	3 x2	≥	6,
2 x1	+	x2	≥	4,
2 x1	+	3 x2	≤	12,

x₁ ≥0                         x₂ ≥ 0.

Решение:

 Рассмотрим первое не равенство системы ограничений.

x₁ + 3 x₂≥6.

Построим прямую:                                     x₁ + 3 x₂ = 6.

Пусть x₁ =0=>3x₂= 6=> x₂ = 2.

Пусть x₂ =0=>x₁ =6.

Найдены координаты двух точек(0,2)и(6,0).Соединяем их и получаем

прямую(1).

Вернемся к исходному не равенству.

x₁+3x₂≥6,3x₂≥-x₁+6,

x₂≥-1/3x₁+2.

Знак не равенства « ≥»,следовательно, решение не равенства–множество точек, расположенных выше прямой(1),включая эту прямую.

 Рассмотрим второе не равенство системы ограничений.

2 x₁ + x₂ ≥4.

Построим прямую:                                     2x₁ + x₂= 4.

Пусть x₁ =0=>x₂ =4.

Пусть x₂ =0=>2x₁= 4=> x₁ = 2.

Найдены координаты двух точек(0,4)и(2,0).Соединяем их и получаем

прямую(2).

Вернемся к исходному не равенству.

2 x₁ + x₂≥4,x₂≥-2x₁+4.

Знак не равенства «≥», следовательно, решение не равенства–множество точек, расположенных выше прямой(2),включая эту прямую.

 Рассмотрим третье не равенство системы ограничений.

2x₁ +3x₂≤12.

Построим прямую:                                     2x₁ +3x₂ =12.

Пусть x₁ =0=>3x₂=12=>x₂ =4.

Пусть x₂ =0=>2x₁=12=>x₁ =6.

Найдены координаты двух точек(0,4)и(6,0).Соединяем их и получаем

прямую(3).

Вернемся к исходному не равенству.

2 x₁ +3x₂≤12,

3 x₂ ≤-2x₁ +12,

x₂≤-2/3x₁+4.

Знак не равенства «≤»,следовательно, решение не равенства–множество точек, расположенных ниже прямой(3),включая эту прямую.

 

 Строим вектор 퐶 {1;1}, координатами которого являются коэффициенты функции L.

 Перемещаем линию уровня(красную прямую),перпендикулярно данному вектору, от левого нижнего угла к правому верхнему.

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

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

Функция L достигает наименьшего значения в точке A.

Точка A одновременно принадлежит прямым(1)и(2).Составим систему уравнений:

x1	+	3 x2	=	6		x1=6/5
2 x1	+	x2	=	4	=>	x2=8/5

 

Вычислим значение функции L в точке A(6/5;8/5).

L(A)= 1 ∙6/5 +1∙8/5=14/5.

 Ответ:x₁= 6/5;x₂=8/5;L_min = 14/5.

Задача 3.

 

Решение:

 Рассмотрим первое не равенство системы ограничений.

3x₁ +4x₂≥18.