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

                                                                        

КЗЛП имеет необходимое число единичных столбцов, т.е. обладает очевидным начальным опорным планом (0,0,0,0,9,7). Решение осуществляется симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах:

 

Таблица 6 – Нахождение оптимального плана симплекс - методом

Номер симплекс-таблицы	Базис	Сб	Б	x1	x2	x3	x4	x5	x6
				27	5	10	14	0	0
	x5	0	9	6	1	6	3	1	6
0	x6	0	7	3	1	1	2	0	1
		f(x)	0	-27	-5	-10	-14	0	0
	х1	27	1,500	1,000	0,167	1,000	0,500	0,167	1,000
I	х6	0	2,500	0,000	0,500	-2,000	0,500	-0,500	-2,000
		f(x)	40,5	0	-0,5	17	-0,5	4,5	27
	х1	27	0,67	1	0	1,67	0,33	0,33	1,67
II	х2	5	5	0	1	-4	1	-1	-4
		f(x)	43	0	0	15	0	4	25

 

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

Вывод: для получения  максимальной прибыли равной 43 руб. необходимо производить 0,67 ед. продукции Р₁ и 5 единиц продукции Р₂.

 

 

5 Теоремы двойственности и их использование в задачах ЛП 

 

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

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

Переменные двойственной задачи y_i называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.

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

Двойственная задача по отношению к исходной составляется согласно следующим правилам:

1) целевая функция  исходной задачи формулируется на максимум, а целевая функция двойственной задачи— на минимум, при этом в задаче на  максимум все неравенства в функциональных ограничениях имеют вид £, в задаче на минимум — вид ³;

2) матрица А, составленная  из коэффициентов при неизвестных  в системе ограничений исходной задачи и аналогичная матрица А^т в  двойственной задаче получаются друг из друга транспонированием;

3) число переменных  в двойственной задаче равно  числу функциональных ограничений исходной задачи, а число ограничений в системе  двойственной задачи — числу переменных в исходной задаче;

4) коэффициентами при  неизвестных в целевой функции   двойственной задачи являются  свободные члены в  системе  ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи — коэффициенты при неизвестных в целевой функции исходной задачи;

5) каждому ограничению  одной задачи соответствует переменная  другой задачи: номер переменной  совпадает с номером ограничения;  при этом ограничению, записанному в виде неравенства £, соответствует переменная, связанная условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственнвой; задачи может принимать как положительные, так и отрицательные значения

Модель исходной (прямой) задачи в общем виде может быть записана следующим образом:

 

                                                                                                (35)

                                                             (36)                     

 

Модель двойственной задачи имеет вид:

 

                                                                                                   (37)

 

                                                                            (38)

 

Две приведенные задачи образуют пару симметричных двойственных задач. Основные утверждения о взаимно двойственных задачах содержатся в двух следующих теоремах.

Первая теорема  двойственности.

Для взаимно двойственных задач имеет место один из взаимоисключающих случаев:

1. В прямой и двойственной  задачах имеются оптимальные  решения, при этом значения целевых функций на оптимальных решениях совпадают: f(x) = g(y).

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

3. В двойственной задаче  допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.

4.Обе из рассматриваемых  задач имеют пустые допустимые  множества.

Экономический смысл  первой теоремы двойственности следующий. План производства Х и набор оценок ресурсов У оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная, при известных заранее ценах продукции  равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов y_i. Для всех же других планов Х и У обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов:

 

                                                    f(X) < g(Y},                                            (39)

 

т. е. ценность всей выпущенной продукции не превосходит суммарной  оценки имеющихся ресурсов. Значит величина g(Y) - f(X) характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных оценок ресурсов.

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

Вторая теорема  двойственности (теорема о дополняющей  нежесткости)

Пусть X=(x₁,x₂,...x_n) - допустимое решение прямой задачи, а Y= (y₁,y₂,...y_m) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач необходимо и достаточно, чтобы выполнялись следующие соотношения:

 

                                                                  (40)     

                                                         (41)                      

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

Из второй теоремы  двойственности в данном случае следуют  такие требования на оптимальную производственную программу X=(X₁,X₂,...,X_n) и оптимальный вектор оценок Y=(Y₁,Y₂,...,Y_m):

 

                               если                                 (42)

                               если                   (43)

                                    если                           (44)

                               если                  (45)

 

Условия (42) и (43) можно интерпретировать так: если оценка yi единицы ресурса i-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью, если же ресурс используется не полностью, то его оценка равна нулю. Из условия (44) и (45) следует, что если j-й вид продукции вошел в оптимальный план, то он в оптимальных оценках неубыточен, если же j-й вид продукции убыточен, то он не войдет в план, не будет выпускаться.

Рассмотрим еще одну теорему.

Теорема об оценках.

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

 

                                                                                             (46)

 

Решая ЗЛП  симплексным  методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи y_i называют объективно обусловленными оценками.

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

 

Экономико-математическая модель исходной задачи.

  x_i – количество продукции i-го вида.

 

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

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

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

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

 

Экономико-математическая модель двойственной задачи.

 

                                        Z(y) = 9y₁ + 7y₂ -> min                                    (48)

      

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

Ограничения двойственной задачи:

 

6y₁ + 3y₂ ≥ 27

y₁ + y₂ ≥ 5

6y₁ + y₂ ≥ 10                                                 (49)

3y₁ + 2y₂ ≥ 14

y₁, y₂, y₃, y₄ ≥ 0

 

Решим задачу графическим  способом. Построим прямые ограничений на двумерной плоскости, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств. Находим полуплоскости, определяемые каждым из ограничений задачи и определяем область допустимых решений. Строим вектор S, который начинается в точке (0;0) и заканчивается в точке (c₁, с₂). Т.к. задача решается на минимум, то передвигаем прямую целевой функции   против направления вектора S. Последняя по ходу движения вершина ОДР будет точкой минимума ЦФ. Затем определяем координаты этой точки.

 

 

 

 

 

 

 

 

 

 

 

Рисунок 2 – Решение  двойственной задачи графическим способом

 

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

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

 

В результате получим:

6*4 + 3 * 1 = 27

4 + 1 = 5

6*4 + 1 = 25                                                 (50)