Введение в методы оптимизации

ции F[x^,x2) - вектора с = (4;-2), найдем такое ее положе­ ние, при котором множество М будет лежать по одну сторону от прямой, имея с ней хотя бы одну общую точку. Это поло­ жение соответствует прямой Ax^ - Ix^ = 24, имеющей с пяти­ угольником М общий отрезок, соединяющий точки (6;0) и (8;4). Любая точка этого отрезка доставляет максимальное значение линейной функции на множестве М, равное 24. Перемещая прямую 4х^ - I x^ =0 таким же образом в обрат­ ную сторону, т.е. в направлении вектора (-4; 2), получим прямую 4х, -2x2 =-14, имеющую с множеством М общую точку (0;7). Эта точка доставляет минимальное значение це­ левой функции на множестве М, равное -14. В данном примере наименьшее значение функции F (x,,J2) множестве М достигается в единственной точ­ ке (0;7), являющейся угловой точкой М. Наибольшее зна­ чение достигается на отрезке, который содержит угловые точки (б;0) и (8;4) множества М. Таким образом, в данном примере среди точек множества М, в которых достигаются наибольшее и наименьшее значения F(x, ,Х2), имеется хотя бы по одной угловой точке. Доказывается, что при выпол­ нении некоторых дополнительных условий среди точек, в которых достигается минимум (или максимум) линейной функции F{x) на множестве М с:Е„, заданном условиями (2.2) ~ (2.5), всегда имеется хотя бы одна угловая точка М. На описанной геометрической интерпретации основан графический метод решения ЗЛП. Этот метод имеет ограни­ 36