Некоторые задачи оптимизации в экономике

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

Основное неравенство теории двойственности. Пусть имеется пара двойственных задач I и II. Покажем, что для любых допустимых решений Х= (x1,x2, …,хn) и У=(y1,y2,…,ym)исходной и двойственной задачи справедливо неравенство F(X) ≤ Z(Y) или

≤ (3.6)

□ Возьмём неравенства системы ограничений исходной задачи ≤bi и умножим соответственно на переменные y1,y2,…,ym и, сложив правые и левые части полученных неравенств, имеем

≤. (3.7)

Аналогично умножаем систему ограничений двойственной задачи на переменные x1,x2, …,хn , получим

≥ (3.8)

Т.к. левые части неравенств (3.7) и (3.8) представляют одно и тоже выражение уj, то в силу транзитивности неравенств получим доказываемое неравенство (3.6).■

Теперь докажем признак оптимальности решений.

Достаточный признак оптимальности.

Если X*=(x, x,…, x) и У*=(у, у,…, у) – допустимые решения взаимно двойственных задач, для которых выполняется равенство

F(X*) =Z(Y*) (3.9)

то Х* оптимальное решение исходной задачи I, а У* - двойственной задачи II.

□ Пусть Х1 любое допустимое решение исходной задачи I. Тогда на основании основного неравенства (3.6) получим F(X1) ≤ Z(Y*). Однако Х1 - произвольное решение задачи I. Аналогично доказывается, что решение У* оптимально для задачи II.■

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

Ответ на эти вопросы даёт следующая теорема.

Первая (основная) теорема двойственности. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причём оптимальные значения их линейных функций равны:

Fmax=Zmin или F(X*) =Z(Y*) (3.10)

Если линейная функция одной из задач не ограничена, то система ограничений другой задачи противоречива.

Из первой части утверждения теоремы следует, что равенство (3.9) является не только достаточным, но и необходимым признаком оптимальности взаимно двойственных задач.

□ Докажем утверждение второй части методом от противного. Предположим, что в исходной задаче линейная функция не ограничена, т.е. Fmax=∞, а условия двойственной задачи не являются противоречивыми, т.е. существует хотя бы одно допустимое решение У=(y1,y2,…,ym). Тогда в силу основного неравенство теории двойственности (3.6) F(X) ≤ Z(Y), что противоречит условию неограниченности F(X). Следовательно, при Fmax=∞ в исходной задаче, допустимых решений в двойственной задаче быть не может. ■

Экономический смысл первой теоремы двойственности состоит в следующем: план производства X*=(x, x,…, x) и набор цен ресурсов У*=(у, у,…, у) оказываются оптимальными тогда и только тогда, когда прибыль от продукции, найденная при ценах с1, с2,…, сn,«внешних» (известных заранее), равна затратам на ресурсы по «внутренним»(определяемым только из решения задачи) ценам y1,y2,…,ym . Для всех же других планов Х и У обеих задач в соответствии с основным неравенством (3.6) теории двойственности прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы.

Экономический смысл первой теоремы двойственности можно интерпретировать и так: предприятию безразлично, производить ли продукцию по оптимальному плану X*=(x, x,…, x) и получать максимальную прибыль Fmax либо продавать ресурсы по оптимальным ценам У*=(у, у,…, у) и возместить от продажи равные ей минимальные затраты на ресурсы Zmin.

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

Пусть даны две взаимно двойственные задачи I и II. Если каждую из них решать симплексным методом, то необходимо привести их к каноническому виду, для чего в систему ограничений задачи I следует ввести m неотрицательных переменных xn+1, xn+2, … , xn+m, а в систему ограничений задачи II - n неотрицательных переменных ym+1, ym+2,…,ym+n. Системы ограничений двойственных задач примут вид:

+xn+i=bi, i=1,…,m (3.11) -ym+j=cj, j=1,…,n (3.12).

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

 Скачать реферат