Решение

1. Построим область допустимых решений (ОДР) в плоскости xOy, определяемую системой неравенств. Каждое линейное неравенство на плоскости задает полуплоскость, все точки которой обращают неравенство в верное числовое неравенство.

Рассмотрим первое неравенство 4y – x ≤ 20.

Границей полуплоскости является прямая 4y – x = 20. Построим эту прямую по двум точкам. Составим таблицу и выполним построение[1] (рис. 1):

Рис. 1	Рис. 2

Определим, какую полуплоскость задает первое неравенство: выше построенной прямой или ниже ее. Для этого подставим в неравенство координаты любой точки, не лежащей на построенной прямой. Обычно берут начало координат: (0; 0):

.

Получили верное числовое неравенство, значит рассматриваемое линейное неравенство определяет полуплоскость, которой принадлежит начало координат, т.е. расположенную ниже построенной прямой (рис. 1).

Аналогично определим полуплоскости, задаваемые вторым и третьим неравенствами: 4x + y ≤ 22 и х – у ≤ 3 (рис. 2).

Оставшиеся ограничения: х ≥ 0, у ≥ 0 задают первую координатную четверть. Область допустимых решений изображена на рисунке 3 – многоугольник OABCD.

Рис. 3	Рис. 4

2. Построим в критериальной плоскости область, соответствующую области допустимых решений OABCD. Для этого необходимо найти координаты вершин.

В нашем случае очевидно, что O(0; 0), A(0; 5), B(4; 6), C(5; 2), D(3; 0), т.к. часть этих точек использовалась при построении прямых. В общем случае координаты точки пересечения двух прямых определяют совместным решением их уравнений, например, для точки С = B₁, которая является точкой пересечения (2) и (3) прямых (рис. 2):

Найдем координаты образов точек O, A, B, C, D в линейном преобразовании, определяемом целевыми функциями:

O(0; 0):

Таким образом, O(0; 0) → O¢(0; 0).

A(0; 5):

Таким образом, A(0; 5) → A¢(–10; –5).

B(4; 6):

Таким образом, B(4; 6) → B¢(–4; –14).

C(5; 2):

Таким образом, C(5; 2) → C¢(6; –12).

D(3; 0):

Таким образом, D(3; 0) → D¢(6; –6).

По найденным координатам точек построим в критериальной плоскости UOV образ многоугольника OABCD – многоугольник O¢A¢B¢C¢D¢ (рис. 4).

3. В критериальной плоскости найдем границу Парето – северо-восточную границу области O¢A¢B¢C¢D¢.

Рис. 5	Рис. 6
Рис. 7	Рис. 8

Точкой утопии, в которой достигается максимум одновременно по двум критериям U и V, является точка P (рис. 6): через самую высокую (северную) точку области O¢A¢B¢C¢D¢ провели горизонтальную прямую (через точку O¢) и через самую правую (восточную) точку области O¢A¢B¢C¢D¢ провели вертикальную прямую (через точки C¢ и D¢); точка – точка пересечения горизонтальной и вертикальной прямой.

4. На границе Парето найдем идеальную точку – точку, наиболее близко расположенную к точке утопии. В нашем случае это основание перпендикуляра, опущенного из точки утопии Р на отрезок O¢D¢ – точка M¢ (рис. 7).

Найдем координаты точки M¢. Для этого найдем уравнение прямой O¢D¢. Воспользуемся уравнением прямой, проходящей через две точки:

O¢(0; 0), D¢(6; –6)

Найдем уравнение перпендикуляра, опущенного из точки утопии P на отрезок O¢D¢. Воспользуемся уравнением прямой с точкой и вектором нормали:

,

Координаты точки М¢:

Т.е.: М¢(3; –3), а значит компромиссное решение позволит достигнуть значений целевых функций: U = 3, V = –3.

«»»»»»»»»»»»»»»»»»»»»»»»»

Пример вывода уравнения прямой, которая перпендикулярна заданной и проходит через заданную точку

3x-y+6=0
Q=(-2,1)

Решение:
y=3x+6
k=-1/3
y=-1/3x+b
1=(-2)*(-1/3)+b
1=2/3+b
b=1/3
то есть в итоге получаем y=-1/3x+1/3

5. Найдем координаты точки в плоскости xOy, которой соответствует точка М¢ критериальной плоскости. Для этого решим систему уравнений:

Получили, что компромиссным решением метода идеальной точки является M(1,5; 0), в которой критерии достигают значений U = 3, V = –3.

Эта точка принадлежит отрезку OD (рис. 8).

Ответ: M(1,5; 0), U = 3, V = –3.

[1] Все чертежи подготовлены в программе GeoGebra

Поиск по сайту: