Дипломная работа: Некоторые задачи оптимизации в экономике

Аналогично умножаем систему ограничений двойственной задачи на переменные 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).

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

Переменные исходной задачи I
Первоначальные	Дополнительные
x1                 x2           …         xj           …         хn ↕                    ↕                                   ↕                                ↕ ym+1     ym+2         …        ym+j           ym+n	xn+1         xn+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) двойственной задачи, представленных в каноническом виде:

xn+i=bi-, i=1,2,…,m                                  (3.13)

ym+j=-cj, j=1,…,n.                                (3.14)

Умножая каждое равенство системы (4.9) на соответствующие переменные уj≥0 и складывая полученные равенства, найдём

xn+iyi=biyi-yi                            (3.15)

Аналогично, умножая каждое неравенство системы (4.10) на соответствующие переменные xj≥0 и складывая полученные равенства, найдём

ym+j=yi-cj .                                          (3.16)

Равенства (4.11)и(4.12) будут справедливы для любых допустимых значений переменных, в том числе и для оптимальных значений ,,, . В силу первой теоремы двойственности (3.10) F(X*) =Z(Y*) или =, поэтому из записи правых частей равенств (3.15) и (3.16) следует, что они должны отличаться только знаком. С другой стороны, из неотрицательности выражений xn+i yi и ym+j, входящие в выражения (3.15) и (3.16), следует, что правые части этих равенств должны быть неотрицательны.

Эти условия могут выполняться одновременно только при равенстве этих правых частей для оптимального значения переменных нулю:

=0,

=0.                                          (3.17)

В силу условия неотрицательности переменных каждое из слагаемых в равенстве (4.13) должно равняться нулю:

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

=0,  j=1,2,…,n

Откуда и вытекает заключение теоремы. ■

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

Рассмотренная теорема является следствием следующей теоремы.

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

Метод, при котором вначале симплексным методом решается двойственная задача, а затем оптимум и оптимальное решение исходной задачи находятся с помощью теорем двойственности, называется двойственным симплексным методом. Этот метод бывает выгодно применять, когда первое базисное решение исходной задачи недопустимое или, например, когда число её ограничений m больше числа переменных n.

С помощью теорем двойственности найдём решение задачи II. Получаем следующий набор цен ресурсов (  ),  при котором минимальные затраты составят 1330.                                                                                                 [5]

4) Задача нелинейного программирования. (ЗНП)

Рассмотрим ЗНП и способы её решения. Математическая модель ЗНП в общем виде формулируется следующим образом:

f =(x1,x2, …,хn) → min (max). При этом переменные должны удовлетворять ограничениям:

g1(x1,x2, …,хn) ≤b1,

…………………………

gm(x1,x2, …,хn) ≤bm,

gm+1(x1,x2, …,хn) ≥bm+1,

…………………………                                                                                  

gk(x1,x2, …,хn) ≥bk,

gk+1(x1,x2, …,хn)=bk+1,

………………………

gp(x1,x2, …,хn)=bp.

x1,x2,…,хn ≥0,  где хотя бы одна из функций f, gi нелинейная.

Для ЗЛП нет единого метода решения. В зависимости от вида целевой функции и системы ограничений разработаны специальные методы решения, к которым относятся метод множителей Лагранжа, градиентные методы, приближённые методы решения, графический метод.

Рассмотрим основные идеи графического метода.

Максимум и минимум достигается в точках касания линии уровня с областью допустимых решений (ОДР), которая  задается системой ограничений. Например, если линии уровня - прямые, то точки касания можно определить, используя геометрический смысл производной.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8