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

x_n+i=b_i-

, i=1,2,…,m (3.13)

y_m+j=

-c_j, j=1,…,n. (3.14)

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

x_n₊_iy_i=
b_iy_i-

y_i (3.15)

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

y_m₊_j=

y_i-
c_j.(3.16)

Равенства (4.11)и(4.12) будут справедливы для любых допустимых значений переменных, в том числе и для оптимальных значений

. В силу первой теоремы двойственности (3.10)F(X^*) =Z(Y^*) или

=
, поэтому из записи правых частей равенств (3.15) и (3.16) следует, что они должны отличаться только знаком. С другой стороны, из неотрицательности выражений
x_n₊_iy_iи
y_m₊_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 =(x₁,x_2,…,х_n)→ min (max). При этом переменные должны удовлетворять ограничениям:

g₁(x₁,x_2,…,х_n)≤b₁,

…………………………

g_m(x₁,x_2,…,х_n)≤b_m,

g_m₊₁(x₁,x_2,…,х_n)≥b_m₊₁,

…………………………

g_k(x₁,x_2,…,х_n)≥b_k,

g_k₊₁(x₁,x_2,…,х_n)=b_k+1,

………………………

g_p(x1,x_2,…,х_n)=b_p.

x₁,x_2,…,х_n ≥0, где хотя бы одна из функций f, g_i нелинейная.

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

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

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

Рассмотрим на примерах решение ЗНП.

1. Найти экстремумы функции L(x₁,x₂)=x₁+2x₂ при ограничениях

Решение. ОДР – это часть круга с радиусом 5, расположенная в I четверти. Найдём линии уровня функции L: x₁+2x₂=C. Выразим x₂=
. Линиями уровня будут параллельные прямые с угловым коэффициентом, равным -

. Минимум функции достигается в точке (0;0), L_min=0, т.к. градиент

(1,2) направлен вверх вправо. Максимум достигается в точке касания кривой х₂=

и линии уровня. Т.к. угловой коэффициент касательной к графику функции равен -

, найдём координаты точки касания, используя геометрический смысл производной.

; (

)

;

x₀=
; x₂=2
.