Решение оптимизационных экономических задач методами линейного программирования

Графический метод решения  ЗЛП состоит из следующих этапов.

1. Строится многоугольная область допустимых решений ЗЛП – ОДР,
2. Строится вектор-градиент ЦФ в  какой-нибудь точке Х₀  принадлежащей ОДР.
3. Линия уровня C₁x₁+C₂x₂ = а (а–постоянная величина) - прямая, перпендикулярная  вектору –градиенту – передвигается в направлении  этого вектора в случае максимизации f(x_1,x₂)   до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума f(x_1,x₂).

4.  Для нахождения  ее координат достаточно решить  два уравнения прямых, получаемых  из соответствующих ограничений и дающих в пересечении точку максимума.  Значение f(x_1,x₂), найденное в получаемой точке, является максимальным.

При минимизации f(x_1,x₂) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая при своем движении не покидает ОДР, то соответствующий максимум или минимум f(x_1,x₂)  не существует.

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

Решим задачу ЛП графическим способом.

При откорме  каждое животное должно получить не менее 5 ед. питательного вещества S₁, не менее 15 ед. вещества S₂ и не менее 14 вещества S₃. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 килограмме каждого вида корма и стоимость одного килограмма корма дана в таблице 4.

Таблица 4 – Исходные данные

Питательные вещества	Количество единиц питательных  веществ в 1 кг. корма		Требуемое количество питательных  веществ, ед
	корм 1	корм 2
S1	1	1	5
S2	6	1	10
S3	3	2	14
Стоимость 1 кг. корма	9	7

 

Составить рацион минимальной стоимости.

 

Введем следующие обозначения:

х₁ – количество единиц корма 1;   

x₂ - количество единиц корма 1.

Стоимость корма 1 составляет 9х₁, а корма 2 - 7х₂, т.е. необходимо минимизировать целевую функцию

 

                                 9x₁ + 7x₂ - > min                                                      (21)

 

Ограничения задачи имеют вид:

 

                                     x₁ + x₂ ≥ 5

                                     6x₁ + x₂ ≥ 10                                                          (22)                                   

                                     3x₁ + 2x₂ ≥ 14

                                     x₁ ≥ 0, x₂ ≥ 0

 

Первое ограничение  по питательному веществу S1  х₁   +  х₂ ≥ 5. Прямая х₁   +  х₂ = 5 проходит через точки (5, 0) и (0, 5).

Второе ограничение  по питательному веществу S2 6х₁ + х₂ ≥ 10.           Прямая 6х₁ + х₂ = 15  проходит через точки (1,67, 0) и (0, 10).

Третье ограничение  по питательному веществу S3 3x₁+2x₂≥14. Прямая 3x₁+2x₂=14 проходит через точки (4,67, 0) и (0, 7).

Для определения направления  движения к оптимуму построим вектор-градиент Ñ, координаты которого являются частными производными целевой функции, т.е. = (9;7).

Что бы построить этот вектор, нужно  соединить точку (9;7) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации — в противоположном направлении. Для удобства можно строить вектор, пропорциональный вектору Ñ. Так, на рисунке 1 изображена область допустимых решений и линия уровня.

Рисунок 1 – Область  допустимых решений и линия уровня

 

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

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

                                       

                                                    x₁ + x₂ ≥ 5                                               (23)                                                                               

                                                   3x₁ + 2x₂ ≥ 14

 

Отсюда легко записать решение исходной ЗЛП: min F(x) = 43 и достигается при x₁=4 и x₂=1.

 

4 Симплексный метод решения задач ЛП

 

Для решения ЗЛП существует универсальный метод  – метод  последовательного улучшения плана  или симплекс-метод, который состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод). 

Выбор конкретной вычислительной процедуры осуществляется после  приведения исходной ЗЛП к каноническому  виду (КЗЛП):

 

                                                                                                 (24)

                                     

                             

В теории линейного программирования показано, что оптимальное решение ЗЛП связано с угловыми (крайними) точками многогранника решений, которым отвечают опорные планы (неотрицательные базисные решения системы уравнений КЗЛП). Каждый из опорных планов определяется системой m линейно независимых  векторов, содержащихся в данной системе из n векторов  А1, А2,…, Аn. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний С_nm.

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

Для определенности предположим, что  первые  m векторов матрицы системы  уравнений составляют единичную  матрицу. Тогда первоначальный опорный план очевиден  – (b1, b2 ,…, bm ,0,…,0).

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

Математический признак оптимальности  состоит из следующих двух теорем:

1. Если для всех векторов А₁, А₂,…, А_n выполняется условие

 

                                 где   ,                               (25)

 

то полученный опорный план является оптимальным.

2. Если для некоторого вектора, не входящего в базис, выполняется условие

 

                                                            ,                                         (26)

 

то можно получить новый опорный план, для которого значение ЦФ будет больше исходного, при этом могут быть два случая:

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

На основании признака оптимальности в базис вводится вектор А_к , давший минимальную отрицательную величину симплекс разности:

 

                                                              (27)

 

Чтобы выполнялось условие  неотрицательности значений опорного плана, выводится из базиса вектор А_r, который дает минимальное положительное оценочное отношение

 

                                        (28)

     

Строка А_r называется направляющей, столбец А_к и элемент a_rк – направляющими.

Элементы направляющей строки в  новой симплекс-таблице вычисляются по формулам:

 

                                                                                 (29)

 

 а элементы  i-й  строки  – по формулам:

 

                                                                        (30)

 

Значения нового опорного плана рассчитываются по формулам:

 

                                                    для  i = r ;                             (31)

 

                                                   (32)

 

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

Для использования приведенной  процедуры к минимизации линейной функции  F (x) следует искать максимум  - F (x), затем полученный максимум взять с противоположным знаком. Оптимальное решение то же.

 

Для изготовления 4-ёх видов продукции P₁, P₂, P₃, P₄  используют два вида сырья: S₁ и S₂. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 5.

 

Таблица 5 – Исходные данные

Вид сырья	Запас сырья	Количество единиц сырья, идущих на изготовление единицы продукции
		P1	P2	P3	P4
S1	9	6	1	6	3
S2	7	3	1	1	2
Прибыль от единицы продукции		27	5	10	14

 

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

 

Решение.

Сформулируем ЗЛП.

Целевая функция: F(x) = 27x₁ + 5x₂ + 10x₃ + 14x₄ -> max                    (33)

Ограничения:                  6 x₁ + x₂ + 6x₃ + 3x₄ ≤ 9

                                           3x₁ + x₂ + x₃ + 2x₄ ≤ 7                               

                                                  x₁, x₂, x₃, x₄ ≥ 0

  

Приведем ее к каноническому виду путем введения дополнительных переменных x₅ и x₆:

                           F(x) = 27x₁ + 5x₂ + 10x₃ + 14x₄ + 0х₅ + 0х₆-> max        (34)

                                             6x₁ + x₂ + 6x₃ +3 x₄ + х₅ = 9

                                             3x₁ + x₂ + x₃ + 2x₄ + х₆ = 7                               

                                              x₁, x₂, x₃, x₄ , х₅, х₆ ≥ 0