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

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

Найти  минимальное  значение  линейной  функции

 {spoiler=Подробнее}

Z=C₁x₁+ C₂x₂+ ... + C_nx_n                                                            (1)

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

           (2)

X_j³ 0(j=1, 2,.....,n).                                              (3)

Совокупность чисел  x₁,x₂,....,x_n,  удовлетворяющих ограничениям (2) и (3), называется  решением. Если система неравенств (2)  при условии (3) имеет хотя бы одно решение, она называется совместной, в противном случае - несовместимой. Рассмотрим на плоскости x₁,Ox₂, совместную систему          

Это все равно, что в системе (2)-(3) положить n = 2. Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой a_j1x₁+ a_j2x₂=bi(i=1,2....,m) Условия не отрицательности  определяют полуплоскости соответственно  с граничными прямыми x₁=0, x₂=0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы (рис. 1). Совокупность этих точек (решений) назовем многоугольником решений. Он может быть точкой, отрезком, лучом , многоугольником, ограниченной многоугольной  областью.

Если в системе ограничений

(2)-(3) , n=3, то каждое неравенство геометрически представляет полупространство трехмерного  пространства, граничная плоскость которого a_j1x₁+ a_j2x₂ +a_j3x₃=b_i(i=1,2....,m), a   условия неотрицательности -полупространства с граничными плоскостями cсоответственно x_j=0(j=1,2,3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью.

Пусть в системе ограничений (2)-(3)  n>3; тогда каждое неравенство определяет  полупространство n-мерного пространства с граничной  гиперплоскостью a_i1x_i+ a_i2x₂ +.....+a_inx_n=b_i(i=1,3....,m), а условия не отрицательности -полупространства с граничными гиперплоскостями x_j=0(j=1,2,....,n).                              .

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

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

Свойства решений задачи линейного программирования.

Теорема.  Множество всех планов задачи  линейного программирования выпукло.

Доказательство.  Необходимо доказать, что если х₁  и х₂  -планы задачи линейного  программирования, то их выпуклая линейная комбинация х=l₁х₁+l₂х₂,  l₁³0,  l₂³0 l₁ + l₂ =1 также план задачи.

Так как х₁  и х₂  - планы задачи, то выполняются соотношения Aх₁=A₀х₁³0;    Aх₂=A₀ х₂³0.

Перемножая Aх=A(l₁х₁+l₂x₂)=l₁Ax₁₊l₂Ax₂=l₁A₀+l₂A₀=(l₁+l₂)A₀=A₀.

получаем, что x  удовлетворяет системе. Но так как x ³ 0; x₂³0, l₁³0, l₂³0, то и x³0,  т.е. удовлетворяет и условию. Таким образом x- план задачи линейного программирования.

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

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

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

Найти минимальное значение функции  Z=C₁x₁+ C₂x₂            (1)   при

                                     (2)

x_i³ 0, x_i³ 0.                                               (3)

Допустим, что система (2) при условии (3) совместна и ее многоугольник ограничен. Каждое из неравенств (2) и (3)как отмечалось выше, определяет полуплоскость с граничной прямой: a_i1x_i+a_i2x₂=b_i(i=1,2....,m), x₁=0,  x₂=0. Линейная функция (1) при фиксированных значениях  Z является уравнением прямой линии: C₁x₁+ C₂x₂=const. Построим многоугольник решений системы ограничений (2) и график линейной функции (1) при Z=0. Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая C₁x₁+ C₂x₂=const-опорная и функция Z при этом  достигает  минимума.

Значения Z= C₁x₁+ C₂x₂  возрастают в направлении вектора N= (C₁, C₂), поэтому прямую Z=0  передвигаем параллельно самой себе в направлении вектора N.

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

Координаты точки А (х₁; х₂ ) находим, решая систему уравнений прямых АB и АЕ.

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

Случай 1. Прямая C₁x₁+ C₂x₂=const , передвигаясь в направлении  вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу .

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

Пример  задач,  решаемых  графических  методом

Решим графическим методом задачи использования сырья и составления рациона.

Задачи использования сырья.. Найти максимальное значение линейной функции Z=50x₁+40x₂  при ограничениях

Решение. Построим многоугольник решений . Для этого в системе координат на плоскости изобразим граничные прямые

Взяв какую-нибудь точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство (эти полуплоскости на рис. показаны стрелками). Многоугольником решений данной задачи является ограниченный пятиугольник ОАВСД.

Для построения прямой  50x₁+40x₂=0 строим радиус вектор     N  =(50 ; 40)=10 (5; 4) и через точку О проводим прямую, перпендикулярную ему. Построенную прямую Z=0    перемещаем параллельно самой себе в направлении вектора  N  . Из рис. следует, что опорной по отношению к многоугольнику решений эта прямая становится в точке С, где функция  Z    принимает максимальное значение. Точка С лежит на пересечении прямых      L₂  и  L₃. Для определения ее координат решим систему уравнений

Оптимальный план задачи: x₁=90/23»3,9; x₂=40/23»1,7.Подставляя значения x₁ и x₂ в линейную функцию получаем Z_max=50´3,9+40*1,7»260,3

Таким образом, для того чтобы получить максимальную прибыль в размере 260.3 сум., необходимо запланировать производство 3.9 ед. продукции P₁ и 1.7 ед. продукции  P₂      .

Задачи составления рациона.  Найти минимальное значение линейной функции Z=4x₁+6x₂   при ограничениях

Решение. Построим многоугольник решений (рис.). Для этого в системе координат x₁Ox₂ на плоскости изобразим граничные прямые

3x₁+x₂=9(L₁);

x₁+2x₂=8(L₂);    x₁>=0;  x₂>=0

x₁+6x₂=12(L₃);

и установим, какую полуплоскость определяет каждое неравенство относительно граничной прямой. В результате получим неограниченную многоугольную область с угловыми точками А, В, С, Д.

Построим вектор    N = ( 4 ; 6) и прямую   4x₁+6x₂=0(Z)

Перемещаем прямую Z параллельно самой себе в направлении вектора N. Из рис. следует , что она впервые коснется многогранника решений и станет опорной по отношению к нему в угловой точке В, если прямую

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

Точка В лежит на пересечении прямых L₁ и L₂, для определения ее координат решим систему уравнений

Имеем  x₁=2, x₂=3.  Подставляя найденные значения в линейную функцию, получаем Z_min=4*2+6*3=8+18=26.

{/spoilers}