8. Методы решения задач линейного программирования. Геометрическая интерпретация.

Сущ-ют 2 основных метода решения задачи ЛП: решение на основе геометрической интерпретации (геометрический способ) и симплекс-метод.

Геом. способ может быть применен только для двумерных задач, т.е. при n = 2. В этом случае область допустимых значений – выпуклый многоугольник на плоскости (х1,х2), являющийся результатом пересечения полуплоскостей, каждая из которых – решение соответствующего неравенства системы ограничений.

Целевая функция позволяет провести семейство параллельных прямых - так называемых линий уровня, отвечающих определенному значению линейной формы (т.е. целевой функции). При этом, смещение прямой по направлению нормального вектора, координаты которого равны коэффициентам при соответствующих переменных в целевой функции приводит к увеличению значения целевой функции; в противоположном направлении – к уменьшению.

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

Непустое множество задачи ЛП образует выпуклый многогранник. Каждая вершина многогранника представляет собой опорный план. В одной из вершин многоугольника (т.е. для одного из опорных планов значения целевой функции является максимальным (при условии, что функция ограничивает сверху на множестве планов.

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

Нахождение минимального значения F отличается от нахождения максимального ее значения при тех же ограничениях лишь тем, что ЛУ передвигается не в направлении С, в противоположном.

Этапы решения задачи ЛП на основе ее геометрической интерпретации

1. строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств;

2. находят полуплоскости, определяемые каждым из ограничений задачи;

3. находят многоугольник решений;

4. строят вектор С = (С₁, С₂);

5. строят прямую С₁Х₁ + С₂Х₂ = h, проходящую через многоугольник решений;

6. передвигают прямую С₁Х₁ + С₂Х₂ = h в направлении вектора С, в результате чего находят либо точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве планов; определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.

10. Выбор альтернатив в многокритериальных задачах.

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

Выбор в условиях нескольких критериев. Сложность отыскания наилучшей альтернативы возрастает, когда необходимо рассматривать альтернативы не по одному, а по нескольким критериям, качественно различающимся между собой. Например, выбор конструкции самолета предполагает учет многих критериев (технических - высота, скорость, маневренность, грузоподъемность), безопасности полетов, технологических, экологических, экономических, эргономических. В обыденной жизни - выбор подарка, выбор места для стоянки в турпоходе.

И так, пусть для оценивания альтернатив используется несколько критериев q_i(x), i= 1,2,3...,р. Теоретически можно представить себе случай, когда во множестве Х окажется одна альтернатива, обладающая наибольшими значениями р всех критериев; она и является наилучшей. Однако на практике такие случаи почти не встречаются, и возникает вопрос, как осуществлять выбор (например, на рис. 1 множеству Х соответствуют внутренние точки фигуры на плоскости значений двух критериев q₁ и q₂; оба критерия желательно максимизировать).