Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Создание схемы логических элементов
Примеры решений Теория игр Решение интегралов Пределы онлайн
Деление столбиком онлайн Транспортная задача Двойственная задача
Графический метод онлайн Производная онлайн Симплекс-метод

Метод идеальной точки

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

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

Инструкция. Выберите количество строк (количество ограничений).
Количество ограничений
Если ограничение двойное, например, 1 ≤ x1 ≤ 4, то оно разбивается на два: x1 ≥ 1, x1 ≤ 4 (т.е. количество строк увеличивается на 1).
Найти компромиссное решение многокритериальной задачи оптимизации методом идеальной точки.

Пример оформления в Word

Вместе с этим калькулятором также используют следующие:
Симплексный метод решения ЗЛП

Решение транспортной задачи

Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.

Экстремум функции двух переменных

Вычисление пределов
Задачу максимизации можно путем умножения целевой функции на (–1) преобразовать в задачу минимизации, решаемую при тех же самых ограничениях. Это связано с наличием следующего свойства: функция (-f) достигает наибольшего значения в тех точках, в которых функция f принимает наименьшее значение, и наоборот. Это означает, что условия [f → min] и [(-f) → max] равносильны. Следовательно, поменяв знак целевой функции на противоположный, любую двухкритериальную задачу можно свести к задаче максимизации с двумя целевыми функциями.

Применение метода идеальной точки

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

Пример 1. Найти значения переменных, при которых функции
L1=2x1+x2+1→ max;
L2= x1-x2+5→ max
при ограничениях:

Решение. Введем на плоскости прямоугольную систему координат Ox1x2 и построим множество X — область допустимых решений данной задачи в указанной системе координат. Ограничительные условия определяют на плоскости многоугольник ABCDE (Рис. 1), вершины которого имеют соответственно координаты: (0; 0), (0; 3), (2; 3), (6; 1), (6; 0). Следовательно, X представляет собою многоугольник ABCDE.

Рис. 1. Область допустимых решений на плоскости Ox1x2
Подвергнем координаты каждой точки плоскости Ox1x2 преобразованиям L1=2x1+x2+1 и L2= x1-x2+5. Получим плоскость OL1L2. При этом в силу линейности проводимых преобразований прямоугольная система координат Ox1x2 перейдет в прямоугольную систему координат OL1L2, а многоугольник ABCDE в многоугольник A*B*C*D*E*, вершины которого имеют соответственно координаты: (1; 5), (4; 2), (8; 4), (14; 10), (13; 11) (рис. 2). Для наглядности укажем описанное соответствие вершин: A(0; 0) → A*(1; 5), B(0; 3) → B*(4; 2), C(2; 3) → C*(8; 4), D(6; 1) → D*(14; 10), E(6; 0) → E*(13; 11).
Таким образом, все точки, координаты которых удовлетворяют условиям L1=2x1+x2+1, L2= x1-x2+5 и (x1, x2) ∈ X, определяют на плоскости многоугольник A*B*C*D*E*. Следовательно, область допустимых решений L данной задачи в системе координат OL1L2 (пространстве критериев) представляет собою многоугольник A*B*C*D*E*.

Рис. 2. ОДР в пространстве критериев и множество Парето
Находим множество Парето. Это отрезок D*E*. В условии задачи
не сказано, что считать точкой утопии. Поэтому выбираем комбинацию наилучших значений всех критериев. В данном случае это точка U с координатами (14; 11).
Теперь необходимо найти во множестве Парето точку, расположенную ближе всех к точке утопии U. Из рис. 2 видно, что точка I(I1,I2), являющаяся основанием перпендикуляра, проведенного из точки U (14; 11) к прямой D*E*, принадлежит отрезку D*E*. Это означает, что точка I — искомая. Найдем ее координаты.
Воспользуемся уравнением прямой, проходящей через две заданные точки. Имеем
,
где L1D*, L2D* и L1E*, L2E* — координаты точек D* и E* соответственно. Подставляя сюда числовые значения для координат D* и E*, находим:
, или L1+L2=24.
Нормальным вектором прямой D*E* является вектор N(1; 1), направляющим вектором для прямой UI. Следовательно, ее каноническое уравнение имеет вид:
,
где L1U, L2U — координаты точки U. Подставляя сюда числовые значения для координат U, находим:
, или L1-L2=3.
Точка I принадлежит прямым D*E* и UI (рис. 3). Поэтому ее координаты удовлетворяют системе уравнений

Отсюда находим L1=27/2, L2=21/2.

Рис. 3. Идеальная точка
Расстояние d между точками I(27/2; 21/2) и U(14; 11) равно длине вектора U = (14-27/2; 11-21/2) = (½ ; ½), которая, в свою очередь, равна корню квадратному из суммы квадратов его координат. Поэтому
Соответствующие значения x1, x2 найдем из системы линейных уравнений

Имеем x1=6, x2
Таким образом, Парето-оптимальное решение L1=27/2, L2=21/2 достигается при x1=6, x2=½, а идеальная точка (27/2; 21/2) находится от точки утопии (14; 11) на расстоянии .

Замечание 2. При нахождении расстояния между точкой утопии
и идеальной точкой, учитывая топологию множества Парето, был применен «геометрический» метод. В общем случае задача нахождения расстояния между указанными точками решается как экстремальная. Необходимо найти на множестве Парето точку, такую, что расстояние между ней и точкой утопии минимально:
→ min,
или, опуская знак квадратного корня,
→ min,
где I1 и I2 — неизвестные координаты искомой точки I, а U1 и U1 — уже найденные координаты точки утопии U.

Пример 2. Найти значения переменных, при которых функции
L1=2x1+x2+1→ max;
L2= x1-x2+5→ min
при тех же ограничениях, что и в примере 1.
Решение. Введем функцию L2’= -x1+x2-5. Тогда, согласно замечанию 1, исходная задача преобразуется в задачу максимизации
L1=2x1+x2+1→ max;
L2’= -x1+x2-5→ max.
Рис. 4. Геометрическая интерпретация задачи максимизации
Ограничительные условия те же, что и в примере 1. Они определяют на плоскости Ox1x2 многоугольник ABCDE (рис. 1), который функции L1=2x1+x2+1 и L2’= -x1+x2-5 переводят в многоугольник A*B*C*D*E*. Еговершины в плоскости OL1L2’ (пространстве критериев) имеют соответственно координаты: (1; -5), (4;-2), (8;-4), (14; -10), (13; -11) (рис. 4).
Множество Парето образуют точки ломаной B*C*D*. Как и в примере 1, в условии не сказано, что считать точкой утопии. Поэтому снова выбираем комбинацию наилучших значений всех критериев. В данном случае это точка U с координатами (14;-2) (заметим, что в исходной задаче ей соответствует точка с координатами (14;2), и, следовательно, в исходной задаче точкой утопии является она). Из рис. 4 видно, что точка, принадлежащая ломаной B*C*D* и находящаяся на минимальном расстоянии от точки утопии, должна принадлежать отрезку C*D*. Обозначим ее через I(I1; I2). Для отыскания ее координат воспользуемся способом, описанным в замечании 2. Согласно этому способу, нужно минимизировать функцию расстояния d между точкой I(I1; I2) и точкой U(14;-2):
→ min,
или
→ min.
Составим уравнение прямой C*D* (подробности см. в примере 1). Имеем
, или L1+L2’=4.
Точка Iпринадлежит множеству точек отрезка C*D*.Следовательно, ее координаты удовлетворяют уравнению прямой C*D*: I1+I2= 4, или I1=I2+4. Это означает, что минимизируется функция y=2(I2)2+24I2+104 на отрезке [-10;-4]. Вычисляем производную y′=4I2+24 и находим стационарную точку: I2=-6. Легко видеть, что y’<0 на промежутке [-10;-6) и y’>0 на промежутке (-6; -4]. Следовательно, (-6) — точка минимума функции y(I2) на отрезке [-10;-4], а (10;-6) — точка минимума функции y(I1, I2) = (-I1-10)2+(I2+2)2 в замкнутой области, определяемой неравенствами 8≤I1≤14 и -10≤I2≤-4, при этом dmin=d(10;-6) = . Заметим, что в исходной задаче точке (10;-6) соответствует точка (10; 6).
Соответствующие значения x1, x2 найдем из системы линейных уравнений

Имеем x1 =10/3, x2=7/3
Таким образом, Парето-оптимальное решение L1=10, L2=6 достигается при x1 =10/3, x2=7/3. При этом идеальная точка (10;6) находится от точки утопии (14;2) на расстоянии .

Пример решения экономической задачи с двумя критериями эффективности

В качестве примера рассмотрим конкретную задачу из практики действующего предприятия (задачу регионального уровня).
Задача 1. ОАО «Мукомольный завод „Балашовский“» реализует хлебопекарную муку высшего сорта двумя способами: через сеть магазинов и через прямые поставки по договорам неторговым организациям. Известно, что ежемесячно магазины могут реализовать не более 50 тыс.,
а ежемесячные поставки неторговым организациям не должны превышать 35 тыс. т муки. Для продажи в каждом месяце выделяется не более 45 тыс. т муки. Предприятие выработало определенную политику в области ценообразования, которой собиралось следовать. Однако в связи
с сильно изменившейся экономической ситуацией, затраты на реализацию увеличились, а мука вошла в перечень продуктов, которые должны продаваться по ранее установленной цене, регулируемой местной властью. При продаже одной тонны муки через магазины расходы на реализацию стали составлять 7 тыс. руб., а цена осталась прежней — 10 тыс. руб.; при втором способе реализации расходы и цена составили 4 и 6 тыс. руб. соответственно. Необходимо определить, сколько тонн муки следует продавать каждым способом, чтобы расходы были минимальными, а выручка от продажи — максимальной.
Решение. Составим математическую модель задачи.
Пусть x1 и x2 — объемы (тысячи тонн) реализуемой в ноябре хлебопекарной муки высшего сорта через сеть магазинов и через прямые поставки по договорам неторговым организациям соответственно.
Тогда целевые функции имеют вид:
L1=7x1+5x2→ min;
L2=10x1+8x2→ max
при ограничениях:

Введем функцию L1= -7x1-5x2. Тогда исходная задача преобразуется в задачу максимизации
L1= -7x1-5x2→ max;
L2=10x1+8x2→ max.
Ограничительные условия остаются прежними. Они определяют на плоскости Ox1x2 многоугольник ABCD (рис. 5), который функции L1и L2 переводят в многоугольник A*B*C*D* плоскости OL1 L2:
A(0; 0) → A*(0; 0), B(0; 35) → B*(–175; 280),
C(10; 35) → C*(–245; 380), D(45; 0) → D*(–315; 450) (Рис. 5).

Рис. 5. ОДР на плоскости Ox1x2

Рис. 6. Геометрическая интерпретация задачи максимизации, эквивалентной задаче 1
Множество Парето образуют точки ломаной A*B*C*D*. Выбираем комбинацию наилучших значений всех критериев. В данном случае это точка U с координатами (0;450). Необходимо найти во множестве Парето точку, расположенную ближе всех к точке утопии U. Обозначим ее через I(I1; I2). Для отыскания координат указанной точки минимизируем функцию расстояния d между точкой I(I1; I2) и точкой U(0;415):
→ min,
или
y=I21+(I2-450) → min.
Из рис. 6 видно, что искомая точка находится на отрезке B*C*.
Составим уравнение прямой B*C*. Имеем
, или 10L1’+7L2=210.
Точка Iпринадлежит множеству точек отрезка B*C*. Следовательно, ее координаты удовлетворяют уравнению прямой B*C*: 10L1’+7L2=210, или . Это означает, что на отрезке [-245;-175] минимизируется функция . Вычисляем производную и находим стационарную точку: . Из того, что y’<0 на промежутке [–245; ) и y’>0 на промежутке (; –175], следует: — точка минимума функции y(I1) на отрезке [-245;-175]. Тогда — искомая точка, что соответствует точке в исходной задаче.
Соответствующие значения x1,x2 найдем из системы линейных уравнений

Имеем x1=3 196/1043, x2=35
Таким образом, объемы реализации хлебопекарной муки высшего сорта ОАО «Мукомольный завод „Балашовский“» должны составить: ≈ 3,19 тыс. т через сеть магазинов и 35 тыс. т через прямые поставки по договорам неторговым организациям. При таких способах и объемах реализации расходы будут минимальными (составят ≈ 197,32 тыс. руб.), а выручка — максимальной (составит ≈ 311,88 тыс. руб.).

Пример 3. Фирма имеет возможность реализовывать свои товары на 4-х различных рынках. Затраты на рекламу на этих рынках составляют соответственно 7, 5, 9, и 6 тыс. денежных единиц, доля рынка - 45, 40, 50 и 45 процентов, а объем продаж - 90, 85, 80 и 83 тыс. штук. При этом ставятся одновременно следующие цели: минимизация затрат на рекламу, завоевание максимальной доли рынка и максимизация объема продаж в течение планируемого периода.