ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Общая постановка двойственной задачи

1 2 3 45

Предположим, что некоторая организация решила закупить ресурсы Р₁ , Р₂ ,…, Р_m фирмы; необходимо определить цены на ресурсы у₁, у₂,…, у_m. Естественно, что покупающая организация заинтересована в том, чтобы затраты на покупку ресурсов в объеме b₁, b₂,…, b_m по ценам у₁, у₂,…, у_m были минимальны, то есть Z = b₁y₁ + b₂y₂ + … + b_my_m ® min.

Предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не меньше той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции j-го вида расходуется сырье Р₁ в объеме а₁_j, сырье Р₂ – в объеме а₂_j, сырье Р_m – в объеме а_mj по цене у₁, у₂,…, у_m соответственно, то есть затраты на изготовление продукции П_j должны быть не меньше, чем цена ее реализации. Приходим к ограничениям следующего вида:

а₁_jу₁ + а₂_jу₂ + … + а_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 принимает минимальное значение.

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

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

Таблица 3

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

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

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

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

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

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

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

Таблица 4

Переменные двойственной задачи	Переменные прямой задачи
х₁	х₂	…	х_i	…	x_n
c₁	c₂	…	c_i	…	c_n
y₁ y₂ . . . y_n	a₁₁ a₂₁ . . . a_m1	a₁₂ a₂₂ . . . a_m2	… … … …	a_1i a_2i . . . a_mi	… … … …	a_1n a_2n . . . a_mn	b₁ b₂ . . . b_m
				j-е ограничение двойственной задачи			Коэффициенты целевой функции двойственной задачи

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

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

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

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

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

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

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

Если a_i₁ x₁^* + a_i₂ 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_i₂ 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.

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

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

1 2 3 45