Двойственная задача.

Каждой задаче линейного программирования соответствует другая задача, называемая двойственной или сопряжённой по отношению к исходной. Теория двойственности полезна для проведения качественных исследований ЗЛП. В главе I пункте 2) рассмотрена задача об использовании ресурсов. Предположим, что некоторая организация решила закупить ресурсы и необходимо установить оптимальные цены на эти ресурсы y_1, y₂, y₃. Очевидно, что

покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах 180, 210, 236 по ценам соответственно y_1, y₂, y₃ были минимальными, т.е. Z= 180y₁+210y₂+236y₃→ min. С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не мене той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции А расходуется 4кг. ресурса 1, 3кг. ресурса 2, 1кг. ресурса 3 по цене соответственно y_1, y₂, y₃. Поэтому, для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении единицы продукции, должны быть не менее её цены 10у.е., т.е. 4 y₁+3 y₂+ y₃≥ 10.

Аналогично можно составить ограничения в виде неравенств по каждому виду продукции. Экономико-математическая модель исходной задачи и полученной двойственной задачи приведены в таблице.

Задача I (исходная)

Задача II (двойственная)

F= 10x1+14x2+12x3→ max При ограничениях: 4х1+2х2+х3≤ 180 3х1+х2+3х3≤ 210 х1+2х2+5х3≤ 236 и условие неотрицательности переменных x1≥ 0, x2≥ 0, х3≥ 0. Для производства трёх изделий А, В, С используются три вида сырья. каждый из них используется в объёме, не превышающем 180, 210 и 236кг. Определить план выпуска изделий, обеспечивающий получение оптимального дохода при условии, что потребление ресурсов по каждому виду продукции не превзойдёт имеющихся запасов.

Z= 180y1+210y2+236y3→ min При ограничениях: 4y1+3y2+y3≥ 10 2y1+y2+2y3≥ 14 y1+3y2+5y3≥ 12 и условие неотрицательности переменных y1≥ 0, у2≥ 0, у3≥ 0. Найти такой набор цен ресурсов, при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли от реализации этой продукции.

Обе задачи, представленные в таблице обладают следующими свойствами:

1. В одной задаче ищут максимум линейной функции, в другой минимум.

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

3. Каждая из задач задана в стандартной форме, причём в задаче максимизации – все неравенства вида «≤», а в задаче минимизации – все неравенства вида «≥».

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

Для задачи I А= , для задачи II А =

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

6. Условия неотрицательности переменных имеются в обеих задачах.

Две задачи I и II линейного программирования, обладающие указанными свойствами, называются симметричными взаимодвойственными задачами.

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

1. Приводят все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задач ищут максимум линейной функции, то все неравенства системы ограничений приводят к виду «≤», а если минимум – к виду «≥».

2. Составляют расширенную матрицу системы А₁, в которую включают матрицу коэффициентов при переменных, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.

3. Находят матрицу А , транспонированную к матрице А₁.

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=1, 2, …, m и j=1, 2, …, n: если > 0, то =0; если > 0, то =0, и аналогично, если > 0, то =0; если > 0, то =0.

□ Выразим дополнительные переменные из системы ограничений (3.11) исходной задачи I и (3.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+i y_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+1(x₁, x_2, …, х_n) ≥ b_m+1,

…………………………

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

g_k+1(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₂ при ограничениях

, .

x₂=

= - ; () = - ;

= - ; x₀= ; x₂=2 .

Тогда L= +2∙ 2 =5 .

Ответ: Минимум достигается в точке О(0; 0), глобальный максимум, равный 5 , в точке А(; 2 ).

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

x₁+x₂≤ 8

3 x₁+x₂ ≤ 15

x₁+x₂ ≥ 1

.

Решение. ОДР – многоугольник ABCDE. Линии уровня представляют собой окружности (x₁-6)²+(x₂-2)²=С с центром в точке О₁(6; 2). Возьмём, например, С=36, видим, что максимум достигается в точке А(0; 4), которая лежит на окружности наибольшего радиуса, пересекающую ОДР. L(A)=(0-6)²+(4-2)²=40. Минимум - в точке F, находящейся на пересечении прямой 3x₁+x₂ =15 и перпендикуляра к этой прямой, проведённого из точки О₁. Т.к. угловой коэффициент равен -3, то угловой коэффициент перпендикуляра равен . Из уравнения прямой, проходящей через данную точку О₁ с угловым коэффициентом , получим (x₂-2)= (x₁-6). Найдём координаты точки Е

х₁-3х₂=0

3 x₁+x₂ =15.

Решив систему, получаем Е(4.5; 1.5).

L (E) = (4.5-6)²+ (1.5-2)²=2.5.

Ответ: Минимум, равный 2.5 достигается в точке (4.5; 1.5), максимум, равный 40, в точке (0; 4).

3. Найти экстремумы функции L=(x₁-1)²+(x₂-3)²

при ограничениях , .

Решение: ОДР является часть круга, с центром в начале координат, с радиусом 5, расположенная в I четверти. Линии уровня – это окружности с центром в точке О₁ и радиуса С, т.к. (x₁-1)²+(x₂-3)²=С. Точка О₁ – это вырожденная линия уровня, соответствующая минимальному значению С=0. глобальный максимум достигается в точке А, лежащей на пересечении ОДР с линией уровня наибольшего радиуса. При этом

L(A)=(5-1)²+(0-3)²=25.

Ответ: Минимум, равный 0, достигается в точке (1; 3),

Максимум, равный 25, - в точке А(5; 0).

4. Предприниматель решил выделить на расширение своего дела 150 тыс.руб. известно, что если на приобретение нового оборудования затратить х тыс. руб., а на зарплату вновь принятых работников у тыс. руб., то прирост объёма продукции составит Q=0.001x^0.6·y^0.4. Как следует распределить выделенные денежные ресурсы, чтобы прирост объёма продукции был максимальным.

Решение: Целевая функция имеет вид 0.001x^0.6·y^0.4 → max при ограничениях x+y≤ 150,

.

ОДР – треугольник. Линии уровня будут иметь вид 0.001x^0.6·y^0.4 =С. Выразив отсюда у, получим у= . Т.к. максимум достигается в точке касания линии уровня с ОДР, то условие касания имеет вид =-1. Найдя производную, получаем = -1. Выразив х, получим х= . у= = .

Ответ: Факторы х и у следует распределить в отношении 2: 3.

5. Предприятие выпускает изделия А и Б, при изготовлении которых используется сырьё S₁ и S₂. Известны запасы b_i (i=1, 2) сырья, нормы его расхода на единицу изделия a_ij (j=1, 2), оптовые цены p_j на изделия и их плановая себестоимость с . Как только объём выпускаемой продукции перестаёт соответствовать оптимальному размеру предприятия, дальнейшее увеличение выпуска х_j ведёт к повышению себестоимости продукции b, в первом приближении фактическая себестоимость с_j описывается функцией с_j= с + с х_j, где с_j – некоторая постоянная. Все числовые данные приведены в таблице

b1	b2	a11	a12	a21	a22	p1	p2	с	с	с	с
										0.2	0.2

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

Решение: С оставим математическую модель задачи.

Пусть Z – прибыль, получаемая предприятием после реализации х₁ выпущенных изделий А и х₂ изделий Б.

Z=(12-(7+ 0, 2 х₁)) х₁+(10-(8+ 0, 2 х₂)) х₂ → max,

при ограничениях 13 х₁+ 6 х₂≤ 90,

8 х₁+ 11 х₂≤ 88 _,

Преобразуя целевую функцию, получим:

Z=5х₁-0, 2х +2 х₂-0, 2х → max

ОДР – многоугольник ОАВD. Для построения линий уровня функции, приведём функцию к следующему виду:

(х₁-12, 5)²+(х₂-5)²=181, 25-5Z.

Линиями уровня будут окружности с центром в точке О₁(12, 5; 5) и радиуса . Окружность наибольшего радиуса будет проходить через точку М, находящейся на пересечении прямой ВD и прямой O₁М, перпендикулярной к BD. Найдём координаты точки М.

13х₁+ 6х₂=90

х ₂-5=6/13(х₁-12, 5). Решив систему, получим, М(6; 2).

Z(М)=30-7, 2-2, 8+4=26.

Ответ: Для получения предприятием максимальной прибыли, составляющей 26 ден.ед., следует выпустить 6 ед. изделия А и 2 ед. изделия Б.

5) Задача на условный экстремум.

Если система ограничений (3.1) задана в виде равенств, то это задача на условный экстремум. В случае функцииn независимых переменных (x₁, x_2, …, х_n) задача на условный экстремум формулируется следующим образом:

L=f(x₁, x_2, …, х_n)→ max (min)

при условиях: g _i (x₁, x_2, …, х_n)=0, i= . (m< n).

В конце XVIII века Лагранж предложил остроумный метод решения задачи на условный экстремум. Суть метода Лагранжа состоит в построении функции L(x₁, x_2, …, х_n)= f(x₁, x_2, …, х_n)+ g_i(x₁, x_2, …, х_n), где λ _i неизвестные постоянные, и нахождении экстремума функции L.

Верна следующая теорема: если точка ( ) является точкой условного экстремума функции f(x₁, x_2, …, х_n) при условии g(x₁, x_2, …, х_n)=0, то существует значение λ _i такие, что точка ( ) является точкой экстремума функции L( ).

Рассмотрим метод Лагранжа для функции двух переменных.

L(x₁, x₂, λ)= f(x₁, x₂)+λ g(x₁, x₂)

Таким образом, для нахождения условного экстремума функции f(x₁, x₂) при условии g(x₁, x₂)=0 требуется найти решение системы

L =f (x₁, x₂)+λ g (x₁, x₂)=0, (3.18)

L =f (x₁, x₂) +λ g (x₁, x2) =0,

L = g(x₁, x₂) =0. [4]

Есть и достаточные условия, при выполнении которых решение (x₁, x₂, λ) системы (3.18) определяет точку, в которой функция f достигает экстремума, для этого нужно вычислить значения и составить определитель

=- .

Если < 0, то функция имеет в точке () условный максимум, если > 0 – то условный минимум.

Решим задачу методом множителей Лагранжа.

Общие издержки производства заданы функцией Т=0, 5х²+0, 6ху+0, 4у²+ +700х+600у+2000, где х и у соответственно количество товаров А и В. Общее количество произведённой продукции должно быть равно 500 единиц. Сколько единиц товара А и В нужно производить, чтобы издержки на их изготовление были минимальными?

Решение: составим функцию Лагранжа.

L(x, y, λ) =0, 5х²+0, 6ху+0, 4у²+ +700х+600у+2000+λ (х+у-500). Приравнивая к нулю её частные производные, получим

х+0, 6у+700+ λ =0,

0, 6х+0, 8у+600+ λ =0,

х+у-500=0.

Решив систему, найдём (0, 500, -1000).

Воспользуемся достаточным условием для определения найденного значения L (x₀, y₀)=1, L (x₀, y₀)=0.8, L (x₀, y₀)=0.6. Функция g= х+у-500. g =1, g =1.

= -(0·L ·L + g ·L · g + g ·g ·L - g ·L ·g -0·L ·L - g · g ·L )=0, 6> 0

Значит, в точке (0; 500) функция L имеет условный минимум.

Ответ: Выгодно производить только 500 ед. товара В, а товар А не производить.

Наиболее простым способом нахождения условного экстремума функции двух переменных является сведение задачи к отысканию экстремума функции одной переменной. Пусть уравнение g(x₁, x₂)=0 удалось разрешить относительно одной из переменных, например, выразить х₂ через х₁: х₂=φ (х₁). Подставив полученное выражение в функцию, получим y=f(x₁, x₂)= y=f(x₁, φ (х₁)), т.е. функцию одной переменной. Её экстремум и будет условным экстремумом функции y=f(x₁, x₂).

Проиллюстрируем данный метод на конкретной задаче.

Фирма реализует автомобили двумя способами: через розничную и оптовую торговлю. При реализации х₁ автомобилей в розницу расходы на реализацию составляют (4 х₁+х ) у. е., а при продаже х₂ автомобилей оптом – х у. е. Найти оптимальный способ реализации автомобилей, минимизирующий суммарные расходы, если общее число, предназначенных для продажи автомобилей составляет 200шт.

Решение: Составим функцию L(х₁, х₂)=4 х₁+х +х и будем находить её минимум. Т.к. для продажи предназначено 200 автомобилей, то х₁+х₂=200. Разрешим данной уравнение относительно переменной х₂: х₂ = 200-х₁. Подставим полученное выражение в функцию L, получим L=4 х₁+ х + (200- х₁)²=2х --396 х₁+40000, х₁ 0.

Найдём экстремум данной функции.

L =4 х₁-396.

Приравняв её к нулю, получим х₁=99.

Ответ: оптимальный способ реализации автомобилей – это 99 автомобилей в розницу и 101 автомобиль оптом (х₂=200-99). Расходы составят 20398 р.

В экономических задачах, в которых отыскивается оптимум функции f =(x₁, x_2, …, х_n), где n 2, полагают, что найденное единственное решение, удовлетворяющее необходимому условию экстремума, является оптимальным.