Геометрическая интерпретация задач оптимизации

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

Общая задача теории оптимизации может быть сформулирована следующим образом.

Дана система неравенств и уравнений с n переменными.

 

(2.1)

и функция .

В области решений системы ограничений (2.1) требуется найти такое решение, при котором целевая функция z принимает наибольшее или наименьшее значение.

Для геометрической интерпретации задач оптимизации рассмотрим двухмерный случай. Изобразим на плоскости множество X решений системы (2.1) и несколько линий уровня целевой функции , k = 1, 2, 3…

 

Рис. 2.1

Задача оптимизации сводится к нахождению максимального (минимального) z^* среди всех z_k, для которых линии уровня пересекаются с областью X. При этом любая точка , лежащая в X на линии уровня , является оптимальным решением задачи.

На геометрическом толковании основан соответствующий метод решения задач оптимизации. В качестве примера рассмотрим линейную задачу:

→ min(max) (2.2)

(2.3)

Область решений системы (2.3) представляет собой гипермногогранник (полиэдр) в n – мерном пространстве, а целевая функция задает в этом пространстве гиперплоскость. Если n=2, то решение системы (2.3) есть плоский многогранник, а целевая функция при каждом фиксированном значении z описывает прямую на плоскости. В случае n=3 решение системы (2.3) образует многогранник в пространстве. При этом целевая функция (2.2) при различных значениях z образует семейство параллельных плоскостей в трехмерном пространстве.

Применим графический метод для решения задачи.

С целью обеспечения высокого объема перевозок железная дорога имеет возможность рекламировать свою деятельность, используя местные радио и телевизионные сети. Затраты на рекламу ограничены величиной 3000 условных денежных единиц. Каждая минута радиорекламы обходится в 20 условных денежных единиц, а минута телерекламы – в 60 единиц. Исходя из своих конъюнктурных соображений, железная дорога хотела бы использовать радиосеть по крайней мере в 2 раза чаще, чем телесеть. Радиокомпания согласна предоставить рекламное время в объеме не более 100 минут. Одна минута телерекламы обеспечивает объем перевозок в 6 раз превышающий объем перевозок, обеспечиваемый радиорекламой. Найти оптимальное распределение финансовых средств между телевизионной и радиорекламой.

Обозначим за х₁ и х₂ количество времени, затрачиваемого на радио и телерекламу, соответственно. Если W – объем перевозок, обеспечиваемый 1 мин. радиорекламы, а z – общий объем перевозок, то целевая функция может быть записана в виде

.

Так как величина W считается постоянной, вместо функции можно рассматривать функцию

,

максимум которой в некоторой области достигается в тех же точках, что и функцией .

Из условия задачи можно записать ограничения в виде неравенств, связанные с ограниченностью средств на рекламу

,

а так же с конъюнктурными интересами железной дороги

.

Кроме того, имеются ограничения, связанные с объемом времени на рекламу

; ; .

Таким образом, рассматриваемая задача записывается в виде

 

(2.4)

 

(2.5)

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

 

20х₁+60х₂=3000

х₁-2х₂=0

х₁=100 (2.6)

х₁=0

х₂=0

 

 

y=60

x1

Рис. 2.2.

Решение системы неравенств (2.5) образует на плоскости четырехугольник OPRS, а целевая функция при различных значениях у образует на плоскости параллельные прямые (рис. 2.2). При этом значение у возрастет в направлении вектора

Отыскав направление возрастания функции у, будем перемещать вдоль этого вектора прямую, соответствующую целевой функции у, до тех пор, пока она не выйдет за пределы области OPRS. Это происходит в точке P, в которой и достигается максимальное значение функции у (а вместе с ней и z) в области OPRS.

Уточним координаты точки Р. Для этого учтем, что она является точкой пересечения прямых, описываемых уравнениями

Решив систему, найдем координаты точки Р (60; 30). Это означает, что для получения наибольшего объема перевозок необходимо выделить средства на 60 мин. радиорекламы в размере 1200 условных единиц и на 30 мин. телерекламы в размере 1800 условных единиц.

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

⇐ Предыдущая123456Следующая ⇒

Поделиться:

Популярное:

1. E) тело, размерами которого можно пренебречь в условиях данной задачи
2. I. ОСНОВНЫЕ ЗАДАЧИ ВНЕШНЕЙ ПОЛИТИКИ
3. II. Основные цели и задачи Совета
4. II. Цели и задачи выпускной квалификационной работы
5. II. Цели и задачи настоящей Концепции
6. III. Задачи, определяемые возрастом воспитанников
7. III. Решение логических задач с помощью рассуждений
8. PR – отношения с общественностью. Цели, задачи, функции, методы
9. Авторитарно-ориентированный менеджер, который прежде всего концентрирует свое внимание на решении производственных задач.
10. Аджиевская интерпретация (с. 50)
11. Адлер выделил три основные жизненные цели (задачи): работу, дружбу и любовь.
12. Активное использование речевых средств и средств информационно- коммуникационных технологий (далее – ИКТ) для решения коммуникативных и познавательных задач.