-
Краткая характеристика симплексного м-метода линейного программирования. Геометрическая интерпретация симплексного метода.
При графическом способе решения ЗЛП решению всегда соответствует одна из угловых точек пространства решения. Именно этот результат положен в основу решения симплекс методом. В его вычислительной схеме реализуется упорядоченный процесс, при кот., начиная с некоторой исходной угловой точки (обычно (0,0)), осуществляют последовательные переходы от одной экстремальной точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.
Симплексный м-метод позволяет найти оптимальный план за наименьшее количество пересчетов. В этом методе применяются искусственные переменные с коэффициентом М (очень большое число), что и дало название методу: Симплексный М-метод. Смысл ввода коэффициента М при искусственной перемененной: при решении задачи на max, если в оптимальном плане окажется какая-либо искусственная переменная >0, то значение функционала будет резко уменьшено, а знак при решении на max «-»; при решении задачи на min, коэффициент М берется со знаком «+» и если искусственная переменная окажется в плане, то значение функции цели будет большим.
Геометрическая интерпретация симплекс-метода.
Фундаментом универсального метода решения задач линейного программирования, который называется симплекс-методом, является метод направленного перебора. (По латыни симплекс означает — простои, что в данном случае интерпретируется как простой выпуклый многогранник.) Геометрическая интерпретация симплекс-метода состоит в последовательном переходе от одной вершины многогранника к другой (от первоначально выбранной вершины к одной из соседних вершин, а именно к той, у которой линейная функция принимает лучшее или, по крайней мере, не худшее значение). Этот процесс происходит до тех пор, пока не будет найдено оптимальное решение — вершина, где достигается оптимальное значение функции (если задача имеет конечный оптимум).
-
Критерий оптимальности. Возможность решения задач с различными целевыми функциями в одной и той же области допустимых решений. Случай многокритериальных задач.
Критерий оптимальности (критерий оптимизации) — характерный показатель решения задачи, по значению которого оценивается оптимальность найденного решения, то есть максимальное удовлетворение поставленным требованиям. В одной задаче может быть установлено несколько критериев оптимальности.
Все факторы, входящие в описание процесса, можно разделить на две группы:
av а2,... - постоянные факторы (условия проведения операции), на которые мы влиять не можем.
xv х2,... - зависимые факторы (элементы решения).
Критерий эффективности, выражаемый целевой функцией Z, зависит от факторов обеих групп:
Z = f(a1, а2,..., xv х2,...).
Требуется найти решение (х/, х2*,..., хп*), удовлетворяющие системе неравенств (уравнений) ф,- (Ху х2,..., хп) < Ь„ / = 1, 2,..., т и обращающие в максимум (или минимум) целевую функцию, т.е. Z = f(xv х2,..., хп) ->max (min).
Многокритериальные задачи ЭММ
Подход 1. Сведение к задаче с одним критерием эффективности.
•Критерии располагаются в порядке убывания приоритетов f^x), f2(x),..., fn(x) (х - условный аргумент). В качестве целевой функции выбирается критерий, обладающий наиболее высоким приоритетом -f^x).
•Рассматривается комбинация («свертка») критериев
f (х) = ш^х) + U)2f2(x) + ... + U)nfn(x), где ы1; ш2,..., ып - некоторые коэффициенты (веса).
Подход 2. Из множества допустимых решений отбрасываются заведомо неудачные решения, уступающие другим по всем критериям. В результате остаются эффективные (или «паретовские») решения, множество которых (множество Парето) обычно существенно меньше исходного. Окончательный выбор «компромиссного» решения осуществляет Л ПР.