Математические методы в экономике

Линейные неравенства в системе (2) всегда можно записать в виде равенств вводя дополнительные переменные, тогда  ЗЛП может быть записана в матричной  форме в виде:

  f(x)=c₁x₁+c₂x₂+…+c_nx_n →max                                                             (3)

     Ax=b,

      x≥0,                                                                                                 (4)

где A=//aij//_i=1,m;j=1,n , x=(x₁,x₂,…,x_n)^T, b=(b₁,b₂,…,b_m)^T.

ЗЛП в форме (3),(4) называется ЗЛП  в канонической форме.

Система линейных ограничений ЗЛП  (2) задает в пространстве многогранное множество, и поскольку целевая  функция f(x) является линейной, то она не имеет максимума (или минимума) внутри множества (т.к. частные производные от f(x) по x_i  не все нули). Значит экстремум f(x) достигается на границе области допустимых решений, т.е. в одной из вершин многогранного множества. Следовательно, ЗЛП можно было бы решать сравнением значений целевой функции f(x) во всех вершинах множества допустимых решений, но нахождение всех вершин очень трудоемкая задача. Поэтому для решения ЗЛП разработаны специальные методы, позволяющие перебирать не все вершины, а только некоторые из них, увеличивающие значение f(x). Одним из таких методов является симплекс-метод. Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 1949 г., однако еще в 1939 г. идеи метода были разработаны советским математиком Леонидом Витальевичем Канторовичем. В 1975 г. Фактически за это открытие он был удостоен Нобелевской премии по экономике.

Если ЗЛП зависит от двух переменных x₁ и x₂ , то ее можно решать графически.

 

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

 

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

Задача линейного программирования (ЗЛП) с двумя переменными имеет вид:

 

f(x)=c₁x₁+c₂x₂ →max(min)

a_i1x₁+a_i2x₂ ≤ b_i,   i=1, m₁,

 

a_l1x₁+a_l2x₂ ≥ b_l,   l=m₁+1, m2,                                                                

 

a_k1x₁+a_k2x₂ = b_k, k=m₂+1, m,

 

x_j≥0, j=1,2.

 

Область допустимых решений задачи строится как пересечение областей решений каждого из заданных ограничений. Областью решений линейного неравенства a_i1x₁+a_i2x₂ ≤ b_i является одна из двух полуплоскостей, на которые прямая a_i1x₁+a_i2x₂ = b_i , соответствующая данному неравенству, делит всю координатную плоскость. Для  того чтобы определить, какая из двух координатных полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство. Если оно удовлетворяется, то областью решений является полуплоскость, содержащая данную точку; если же неравенство не удовлетворяется, то областью решений является полуплоскость, не содержащая данную точку. Областью допустимых решений задачи является общая часть полуплоскостей (областей решений всех неравенств системы ограничений) представляющая многогранник.

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

Градиентом линейной функции f(x)=c₁x₁+c₂x₂ является вектор, компонентами которого являются частные производные функции  f(x) по x₁ и x₂:

   f(x)=      .

f(x) линейной функции совпадает с вектором С=(С₁,С₂) и в точке x₀ показывает направление скорейшего возрастания функции в данной точке.

 

Линией  уровня f(x) называется такая линия, в каждой точке которой эта функция принимает одно и тоже значение: f(x)=const. Все линии уровня параллельны между собой.

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

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

Утверждение 1.   Область определения ЗЛП представляет собой выпуклый многогранник. Вершины многогранника (многоугольника) являются его угловыми точками.

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

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

Алгоритм  решения ЗЛП графическим способом:

а) Строим многоугольник решений.

б) Строим f(x) в точке (0,.0).

в) Проводим линию уровня, таким образом, чтобы она проходила хотя бы через одну точку допустимого многогранного множества.

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

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

Пример 1. Цех производит два вида изделий А и В. Их производство ограниченно наличием сырья и временем машинной обработки. Для каждого изделия вида А требуется 3 кг. металла, а для изделия вида В – 4 кг. Цех может получить от поставщиков до 1700 кг. металла в неделю. Для каждого изделия вида А требуется 12 мин. машинного времени, а для изделия вида В – 30 мин. В неделю можно использовать 160 часов машинного времени.

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

 

Решение. Пусть х₁ – количество выпущенных за неделю изделий вида А, х₂ – количество выпущенных за неделю изделий вида В. Задача состоит в том, чтобы найти х₁ и х₂ при которых f(x)=2x₁+4x₂ принимала бы максимальное значение.

Действительно, чтобы увеличить  функцию f(x), надо увеличить х₁ и х₂, но они не могут быть увеличены не ограниченно. Эти значения ограниченны в частности, лимитами на сырье и машинное время. Рассматриваем х₁≥0, х₂≥0 т.к. они выражают еженедельный объем выпускаемых изделий.  Окончательно мы получили типичную двумерную ЗЛП:

 

     f(x)=2x₁+4x₂→ max

3x₁+4x₂≤ 1700 (для сырья)

2x₁+5x₂≤ 1600 (для машинного времени)

х₁≥0, х₂≥0. 

f(x)=(2;4), где =2, =4; данный вектор указывает направление возрастания функции f(x). Линией уровня с наибольшим значением функции f(x), имеющей хотя бы одну общую точку с допустимой областью, является прямая L, проходящая через вершину В. На ней f(x) принимает значение 1400. Точка В, в которой х₁=300, а х₂=200, соответствует оптимальному решению задачи. Эти значения могут быть получены как решения системы уравнений:

3x₁+4x₂= 1700                                                                     

2x₁+5x₂= 1600                                                                      

 

Следовательно, максимальная прибыль составляет f(300;200)=2×300+4×200. При оптимальном решении оба ограничения превращаются в равенство, что означает полное использование сырья и машинного времени.

 

 

 

 

Рис. 1

 

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

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

 

Пример 2. (неограниченная целевая функция).

Найти максимум функции f(x)=3x₁+7x₂, при ограничениях

 

2x₁-3x₂≤ 0  (1)

   x₁+x₂ 5 (2)

   5х₁-х₂≥0 (3)

x₂-3≥0  (4)

 

Решение. Строим область допустимых решений (рис.2),   f(x)=(3; 7) и одну из линий уровня. В данной задаче необходимо найти максимум целевой функции, поэтому линию уровня перемещаем в направлении градиента f(x). Ввиду того, что в этом направлении область допустимых решений не ограничена, линия уровня уходит в бесконечность. Задача не имеет решения вследствие неограниченности целевой функции, т.е. необходимы дополнительные ограничения в экономической задаче.    

 

 

 

Рис. 2.

 

Ответ: f(x)= ∞.

 

Пример 3. (бесконечное множество решений).

 Решить ЗЛП :  f(x)= x₁+ x₂ → max,

x₂-x₁≤ 2        (1)

   3x₁+4x₂≤ 12     (2)

   0≤ х₁≤ 2, х₂≥0  (3)   

 

 

Решение. Строим область допустимых решений (рис.3)

 

Рис. 3

 

Т.к. f(x)  =      =  , то линии уровня будут ортогональны данному вектору. Перемещая линию уровня в направлении вектора градиента, получаем что она совпадает с опорной прямой и проходит через две угловые точки этой области А и В. Задача имеет бесконечное множество оптимальных решений, являющихся точками отрезка [A; B]. Эти точки А=(1)∩(2), В=(2)∩(3)  находятся, при решении соответствующих систем уравнений:

x₂-x₁=2      3x₁+4x2=12 

   3x₁+4x₂≤ 12     x₁=2

 

x = ,    x   = ,       x =2,    x = 1 ,     

A=      B=    

Ответ: f(x) = 4 при x=(1-t) A + tB, 0 ≤ t ≤ 1.

 

Пример 4. (нет решений).

 Решить ЗЛП  f(x)=7x₁+3x₂→ min,

2x₁ +3x₂≤ 2        (1)

3x₁-x₂≥ 0      (2)

х₁-2х₂≤ -2      (3)

х₁-х₂≥3      (4)

х₁≥0,0≤х₂≤4      (5)

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

 

Рис. 4

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

Ответ: система ограничений несовместна.

Замечание. Графическим методом можно решать ЗЛП с n>2 переменными, если в ее канонической записи число неизвестных n и число линейно независимых уравнений m связаны соотношением n-m ≤ 2.

 

 

5. Симплексный метод.

 

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

1. Определение какого-либо первоначального допустимого базисного решения задачи (опорного плана).
2. Правила перехода к лучшему решению.
3. Проверка оптимальности допустимого решения.

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

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

Пример 1.

f(x) = 6x₁+5x₂ min

5x₁+11x₂ ≥ 55 - x₃ 5x₁+11x₂ - x₃= 55

x₁+x₂ ≥ 8 - x₄ x₁+x₂- x₄ = 8

11x₁+3x₂ ≤ 32 + x₅ 11x₁+3x₂ + x₅= 32

x₁ ≥ 0, x₂ ≥ 0  x_j ≥ 0,j = 1, 2, 3, 4, 5

 

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

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

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

1. Построение начального опорного плана

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