Моделей нелинейного программирования

Тема 3.4. Примеры экономико-математических

Задача. Предприятие имеет возможность доставить свою продукцию в количестве 400 тонн потребителю двумя видами транспорта (железнодорожным и автомобильным). Транспортные расходы при перевозке х ₁ тонн груза по железной дороге равны 100 х ₁ денежных единиц, а транспортные расходы при перевозке х ₂ тонн груза автомашинами равны денежных единиц. Найти оптимальный план перевозки продукции при котором транспортные расходы были бы наименьшими.

Решение. В данной задаче надо найти минимум функции при условии, что х ₁ + х ₂ = 400. Для этого составляем функцию Лагранжа

и находим ее частные производные.

; ; .

Решаем систему уравнений:

Получаем:

l =-100; х ₂=50, х ₁=350.

Следовательно,

f = f (350; 50) = 100×350 + 50² = 37500 –

наименьшие транспортные расходы, а (350; 50) – оптимальный план доставки продукции.

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

Таблица 3.1

Тип оборудования	Затраты времени на обработку одного изделия (час.)	Ресурсы времени (час.)
А	В
I			£20
II			³5
III			£30
Затраты на производство одного изделия (тыс. руб)

Определить сколько изделий каждого вида надо изготовить, чтобы средние затраты на производство одного изделия были наименьшими.

Решение. Пусть (х ₁, х ₂) – план производства изделий. Тогда 2 х ₁+3 х ₂ – общие затраты денежных средств на производство изделий А и В, а – средние затраты на производство одного изделия. Для решения поставленной задачи надо найти наименьшее значение функции f при условии, что

Строим область ограничений в системе координат х ₁ ох ₂. Она представляет собой треугольник АВС с уравнениями сторон: 2 х ₁ + 4 х ₂ = 20, х ₁ + х ₂ = 5, 8 х ₁ + 4 х ₂ = 30 (см. рис. 3.6.).

Рис.3.6. Геометрический метод

Выразим х ₂ через х ₁ и f. Получим:: fx ₁+ fx ₂ = 2 x ₁+ 3 x ₂, , x ₂ = kx ₁, где . Уравнение х ₂ = kx ₁ представляет собой при переменном значении k пучок прямых с центром в начале координат. Выразим f через k. Получим: . Найдем производную от f по k. Получим:

.

Так как , то f возрастает при возрастании k. Следовательно, при вращении прямой х ₂ = kx ₁ против часовой стрелки целевая функция возрастает, поэтому f _min = f (С). Находим координаты точки С, решая систему уравнений

Получаем, . Следовательно и –

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

Тема 3.5. Задача выпуклого программирования

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

Напомним, что множество называется выпуклыми, если отрезок, соединяющий любые его точки, принадлежит этому множеству. Таким образом, если Х – выпуклое множество, а и любые его две точки, то при любом t Î[0; 1] точка = (1- t)+ tпринадлежит множеству Х.

Если для любого t Î(0; 1) и любых двух точек , выпуклого множества Х выполняется соотношение:

f ((1- t)+ t) £ (1- t) f () + tf (),

то функция f () называется выпуклой, а если выполняется соотношение:

f ((1- t)+ t) ³ (1- t) f () + tf (),

то функция f () называется вогнутой.

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

Задачу математического программирования в общем виде можно сформировать так: найти оптимальное (наибольшее или наименьшее) значение целевой функции f () на множестве Х и точку , в которой оно достигается.

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

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

Отметим, что вогнутость функций системы ограничений обеспечивает выпуклость области ограничений. Действительно, если , Î Х, т.е. j_i ()³0 и j_i ()³0 для , то: , так как 1- t ³0, ³0, ³0, t ³0.

Для формулировки критерия оптимальности целевой функции, т.е. теоремы Куна-Таккера, нам понадобится понятие седловой точки функции.

Определение. Пара , , называется седловой точкой функции F (,) на множестве всех , принадлежащих некоторому выпуклому множеству п -мерных векторов Х и , принадлежащих множеству т -мерных векторов с неотрицательными координатами , если ÎХ, Îи F (, )£ F (, )£ F (, ) для всех ÎХ и Î.

Последнее неравенство можно записать в следующей форме: .

Теорема Куна–Таккера. Если в задаче выпуклого программирования

,,

множество Х обладает свойствами регулярности, т.е. для каждого существует такая точка , что , то необходимым и достаточным условием оптимальности точки Î Х является существование такого ³0, чтобы пара , являлась седловой точкой функции Лагранжа

F (, ) = f ()-на множестве , .

Теорема Куна-Таккера занимает важное место в теории выпуклого программирования. Она представляет собой обобщение классического метода множителей Лагранжа на случай, когда ограничения на переменные являются не только уравнениями, но и неравенствами.

Теперь сформулируем условие существования седловой точки.

Теорема. Для того, чтобы пара , (,) была седловой точкой непрерывно дифференцируемой функции , которая выпукла для всех Îи вогнута по для всех Î, необходимо и достаточно чтобы при =, =выполнялись условия:

1) ; 2) ; 3) ; 4) .

Пример. Найти наименьшее значение функции

f (x ₁, x ₂) = , если x ₁ ³ 0, х ₂ ³ 0, х ₁ + х ₂ ³ 4.

Решение. Так как функция выпуклая и ограничения задаются линейными, следовательно вогнутыми, функциями, то рассматриваемая задача является основной задачей выпуклого программирования. Составим функцию Лагранжа и найдем ее частные производные.

;

; ;

; ; .

Случай 1. x ₁>0 и х ₂>0. Тогда из условия следует, что

и .

Так как

, , ,

то из условий

, l ₁ ³ 0, l ₂ ³ 0, l ₃ ³ 0

следует, что l ₁ = l ₂ = 0,

и так как

x ₁ ¹ 0 и x ₂¹0, 2 x ₁ - l ₁ + l ₃ = 0 и 2 x ₂ - l ₂ - l ₃ = 0, то l ₃ ¹ 0. Следовательно,. Из системы уравнений

следует, что х ₁ = х ₂ = 2, l ₃ = 4. Так как все условия минимума целевой функции выполняются, то f _min = f (2; 2) = 2² + 2² = 8.

Случай 2. х ₁ = 0, х ₂ ³ 4. Тогда из условий

, ,

следует, что

, т.е. 2 х ₂ - l ₂ - l ₃=0.

Так как

, ,

и 0 = l ₁×0 + l ₂(- х ₂) + l ₃(- х ₂ + 4) = 0, и , то l₂ = 0 и тогда . Следовательно, l ₃ ¹ 0, и l ₃ = 8, х ₂ = 4. Но f (0; 4) = 0²+4² = 16 > f (2; 2) = 8.

Случай 3. х ₁ ³ 4, х ₂ = 0. Тогда, как и выше получим, что

х ₁ = 4, однако f (4; 0) = 4² + 0² = 16 > f (2; 2) = 8.

Рассмотрев три случая, приходим к выводу, что

f _min = f (2; 2) = 8.

Этот пример имеет простое графическое решение. Действительно, графиком функции при условии, что

х ₁ ³ 0, х ₂ ³ 0, х ₁ + х ₂ ³ 4 является часть параболоида вращения, лежащая в первом октанте перед вертикальной плоскостью

х ₁ + х ₂ = 4, (рис. 8.) при этом ее самой нижней точкой является точка М(2; 2; 8). Поэтому f _min = f (2; 2) = 8 при выполнении данных условий - неравенств.

Рис. 3.7. Геометрический метод.

Дата добавления: 2014-10-31