Некоторые задачи оптимизации в экономике (стр. 6 из 12)

4. Формулируют двойственную задачу на основании полученной матрицы А

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

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

Основное неравенство теории двойственности. Пусть имеется пара двойственных задач I и II. Покажем, что для любых допустимых решений Х= (x₁,x_2, …,х_n) и У=(y_1,y₂,…,y_m)исходной и двойственной задачи справедливо неравенство F(X) ≤ Z(Y) или

≤

(3.6)

□ Возьмём неравенства системы ограничений исходной задачи

≤b_iи умножим соответственно на переменные y_1,y₂,…,y_mи, сложив правые и левые части полученных неравенств, имеем

≤

. (3.7)

Аналогично умножаем систему ограничений двойственной задачи на переменные x₁,x_2, …,х_n , получим

≥

(3.8)

Т.к. левые части неравенств (3.7) и (3.8) представляют одно и тоже выражение

у_j, то в силу транзитивности неравенств получим доказываемое неравенство (3.6).■

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

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

Если X^*=(x

, x

,…, x

) и У^*=(у

, у

,…, у

) – допустимые решения взаимно двойственных задач, для которых выполняется равенство

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

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

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

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

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

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

F_max=Z_min или F(X^*) =Z(Y^*) (3.10)

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

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

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

Экономический смысл первой теоремы двойственности состоит в следующем: план производства X^*=(x

, x

,…, x

) и набор цен ресурсов У^*=(у

, у

,…, у

) оказываются оптимальными тогда и только тогда, когда прибыль от продукции, найденная при ценах с₁, с₂,…, с_n,«внешних» (известных заранее), равна затратам на ресурсы по «внутренним»(определяемым только из решения задачи) ценамy_1,y₂,…,y_m . Для всех же других планов Х и У обеих задач в соответствии с основным неравенством (3.6) теории двойственности прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы.

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

, x

,…, x

) и получать максимальную прибыль F_max либо продавать ресурсы по оптимальным ценам У^*=(у

, у

,…, у

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

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

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

+x_n+i=b_i, i=1,…,m (3.11)

-y_m+j=c_j, j=1,…,n (3.12).

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

Переменные исходной задачи I
Первоначальные	Дополнительные
x1 x2 … xj… хn↕ ↕ ↕ ↕ym+1ym+2 … ym+j … ym+n	xn+1xn+2 … xn+I … xn+m↕ ↕ ↕↕ y1 y2… yj ym
Дополнительные	Первоначальные
Переменные исходной задачи II

Теорема. Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых i=1,2,…,mи j=1,2,…,n: если

>0, то =0; если >0, то =0, и аналогично, если >0, то =0; если >0, то =0.

□ Выразим дополнительные переменные из системы ограничений (3.11) исходной задачи I и (3.12) двойственной задачи, представленных в каноническом виде: