Информация о математических методах и моделях в экономике из ГОС

а_1jу₁ + а_2jу₂ + … + а_mjу_m ≥ с_j ,     j=1,2,...,n.

 

 

 

Учитывая условия неотрицательности  цены единицы i-го ресурса, приходим к следующей задаче:

Найти такой вектор У = (у₁, у₂ ,..., у_m) – цен ресурсов, удовлетворяющий системе неравенств

    a₁₁у₁ + a₂₁у₂ + … + a_m1у_m ≥ c₁,

a₁₂y₁ + a₂₂y₂ + … + a_m2y_m  ≥ c₂,

 …   …   …   …   …   …   …

a_1jy₁ + a_2jy₂ + … + a_mjy_m ≥   c_j,

…   …   …   …   …   …   …

a_1ny₁ + a_2ny₂ + … + a_mny_m ≥ c_n,

                                               y_i ³ 0,   i = 1, 2, …, m,

при котором функция  Z = b₁y₁ + b₂y₂ + …+ b_my_m принимает минимальное значение.

Цены ресурсов в экономической  литературе имеют различные названия: учетные, неявные, теневые, объективно-обусловленные оценки (о-о оценки). Смысл этих названий состоит в том, что это условные (ненастоящие) цены. Эти цены определяются в ходе решения задачи, их называют оценками ресурсов.

Сопоставим общие представления  прямой и двойственной задач в табл. 3, причем прямая задача – это задача модели распределения ограниченных ресурсов.

                                                                                     Таблица 3

Прямая задача	Двойственная задача
Максимизировать F = при ограничениях ;    i=1,2,...,m xj ³ 0,   j = 1, 2, …, n,	Минимизировать Z = при ограничениях ;    j = 1, 2, …, n yi ³ 0,   i=1,2,...,m

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

1. Если первая задача имеет  размеры  (m–ограничений с n неизвестными), то вторая – размеры .

2. Матрицы из коэффициентов при  неизвестных в левых частях  ограничений обеих  задач являются взаимно транспонированными.

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

4. В прямой задаче  все ограничения  представляют собой неравенства  типа « », причем в этой задаче требуется достичь . Напротив, в двойственной задаче все ограничения суть неравенства типа « », причем требуется достичь .

Графически эти правила представлены в таблице 4.

                                                                                                                 Таблица 4

Переменные двойственной задачи	Переменные прямой задачи
	х1	х2	…	хi	…	xn
	c1	c2	…	ci	…	cn
y1 y2 . . . yn	a11 a21 . . . am1	a12 a22 . . . am2	… … …   …	a1i a2i . . . ami	… …   …   …	a1n a2n . . . amn	b1 b2 . . . bm
				j-е ограничение двойственной задачи			коэффициенты целевой  функции двойственной задачи

 

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

Из приведенных соотношений видно, что для всех допустимых решений прямой и двойственной задач значения целевой функции задачи минимизации всегда будет верхним пределом значения целевой функции задачи максимизации. Таким образом, итерационное решение задачи максимизации ведет к возрастанию значения целевой функции, а итерационное решение задач минимизации – к ее убыванию. В итоге, при успешном завершении процессов вычисления прямой и двойственной задач приходят к точке «равновесия», где значения целевых функций задач максимизации и минимизации становятся равными.

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

Теорема равновесия. Пусть Х^* – какое-нибудь допустимое решение прямой задачи, а Y^* – какое-нибудь допустимое решение двойственной задачи. Для одновременной оптимальности этих решений необходимо и достаточно выполнение равенств:

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

Учитывая условия неотрицательности  переменных и знаки сомножителей в произведениях,  можно получить следующее:

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

  Если     a_i1 x₁^* +  a_i2 x₂^*+ ...  + a_in x_n^* <  b_i  ,  то      y_i^* = 0 .

Если    a_1j y₁^*  + a_2j y₂^*+ … + a_mj y_m^*  >  c_j ,  то   x_j^* = 0 .

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

Если      y_i^*  > 0 ,    то   a_i1 x₁^* +  a_i2 x₂^*+ ...  + a_in x_n^* =  b_i .   

Если     x_j^* > 0 ,  то     a_1j y₁^*  + a_2j y₂^*+ … + a_mj y_m^*  =  c_j .   

Экономическое содержание теоремы  равновесия означает, что если по некоторому оптимальному плану Х^*  производства расход i-го ресурса строго меньше его запаса bi, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равно нулю. Если же в некотором оптимальном плане оценок его i-ая координата строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует, что двойственные оценки служат мерой дефицитности ресурсов. Дефицитный ресурс, который полностью используется по оптимальному плану производства, имеет положительную оценку, а избыточный ресурс, не используемый полностью, имеет нулевую оценку.

 

Пример 3. Используя теорему равновесия, решить пару двойственных задач (табл.5).

Таблица 5

Прямая задача	Двойственная задача
Максимизировать при ограничениях	Минимизировать  при ограничениях

 

Решим прямую задачу графическим  методом.

 

 

Рис. 6

 

Аналогично примеру 1 строим область  допустимых решений, которая представляет собой выпуклый многоугольник ОАВСD. Нормаль линии уровня (рис. 6).

Определяем координаты точки С как пересечение прямых  p₉ и  p₁₀. Для этого решаем систему

Получаем:

 

    

Следовательно, координаты точки  . Оптимальное решение х₁^* = 4, х₂^* = 1. Вычисляем максимум целевой функции прямой задачи:

По основной теореме двойственности Z(Y^*) = F(Х^*) = 3. Подставим Х^* = (4;1) в систему ограничений прямой задачи:

 

Первое ограничение прямой задачи на оптимальном плане выполняется как строгое неравенство, следовательно, соответствующая переменная двойственной задачи равна нулю: y₁^*= 0.

Второе и третье ограничение  прямой задачи обращается в точное равенство, следовательно, соответствующие переменные двойственной задачи положительны:  y₂^* > 0 и y₃^* > 0.

Условия равновесия можно записать в виде равенств:

Подставляя  y₁^*=0 в последнюю систему уравнений, получим систему:

 

откуда получаем, что y₂^* = , y₃^* = .

Оптимальное решение двойственной задачи Y^*= (0; ; ) при этом минимум целевой функции двойственной задачи: Z_min = Z(Y^*) = 3.

 

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

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