Алгоритм решения ЗЛП графическим методом.

1) Записывают уравнения прямых, соответствующих ограничениям (3.3.4), и строят их на плоскости x ₁ ox _3.

2) Определяют области, в которых выполняются ограничения задачи. Для этого выбирают произвольную точку на плоскости х₁ох₂ и подставляют ее координаты в первую часть одного из неравенств. Если неравенство верно, то искомая полуплоскость находится с той же стороны от прямой, что и точка; в противном случае искомая полуплоскость лежит с противоположной стороны от прямой. Эти действия последовательно выполняются для всех неравенств (3.3.4).

3) Определяют область допустимых решений задачи как область пересечения т полуплоскостей, соответствующих т ограничениям задачи.

4) Определяют направление возрастания (убывания) целевой функции f. Это можно сделать двумя способами. Можно построить вектор-нормаль , его направление показывает направление возрастания функции f, и противоположном направлении функция убывает. Можно просто построить две линии уровня функции f = K₁; f = K₂; (K₁, K₂ – произвольные константы, K₁ K₂), и по их расположению определить направление возрастания (убывания) функции.

5) Определяют граничную точку (точки) области допустимых решений, в которых целевая функция принимает максимальное или минимальное значение.

6) Вычисляют значения найденной точки, решая совместно уравнения, задающие прямые, на пересечении которых находится эта точка, или выявляя уравнение граничной прямой области допустимых решений, с которой совпадает линия уровня целевой функции.

Возможны следующие варианты областей допустимых решений (рис. 3.2):

 

Рис. 3.2. Варианты областей. а – область допустимых решений
– замкнутое множество (многоугольник); б – область допустимых решений – открытое множество; в – область допустимых решений – пустое множество (система ограничений (3.18) несовместна);
г – область допустимых решений состоит из единственной точки А

На рис. 3.2 показаны варианты пересечения линии уровня целевой функции с областью допустимых решений. Может быть единственное решение – точка В, бесконечно много решений – отрезок CD (рис. 3.2, а), максимальным (минимальным) значением целевой функции может быть бесконечность (рис. 3.2, б). Область ограничений несовместимо (допустимых решений нет, рис. 3.2, в). И может быть только одна допустимая точка (рис. 3.2, г)

 

Симплексный метод решения задач линейного программирования

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (симплекс-метод) [simplex method] — вычислительная процедура, основанная на принципе последовательного улучшения решений — перехода от одной базисной точки (см. Базисное решение) к другой, для которой значениецелевой функции больше (эти операции фиксируются в симплексной таблице). Доказано, что еслиоптимальное решение существует, то оно обязательно будет найдено через конечное число шагов (за исключением т. н. вырожденной задачи, при которой возможно явление “ зацикливания ”, т. е. многократного возврата к одному и тому же положению). Название метод получил от термина “n-мерныйсимплекс”. Геометрическая интерпретация метода состоит в последовательном движении по вершинамсимплекса.

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

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от cпорождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

1. нахождение исходной вершины множества допустимых решений,

2. последовательный переход от одной вершины к другой, ведущий к оптимизации значения целевой функции.

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

Теоретические основы симплексного метода

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: