LP: графическое разрешение

Графическое разрешение

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

  1. Реализуемый домен
  2. Постройте целевую функцию
  3. Определить оптимальное решение

Реализуемый домен

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

давайте возьмем это линейная программа следующий :

Линейное программирование в реализуемой области с графическим разрешением

Нарисуем область определения:

Добавлено первое ограничение и тип переменных

Линейное программирование в реализуемой области с графическим разрешением

Добавлено второе ограничение

Линейное программирование в реализуемой области с графическим разрешением

Добавлено третье ограничение

Линейное программирование в реализуемой области с графическим разрешением

Постройте целевую функцию

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

Линейное программирование в реализуемой области с графическим разрешением

Градиент целевой функции равен (350 300). Таким образом, значение z увеличивается, когда целевая функция перемещается в том же направлении, что и вектор (350 300), то есть движется к северо-восточному углу. Мы ясно видим на следующем рисунке, что значение z увеличивается, если взять еще одну прямую линию целевой функции.

Линейное программирование в реализуемой области с графическим разрешением

Затем мы получаем глобальное оптимальное решение (я). Если целевая функция снова построена в соответствии с градиентом, прямая линия окажется за пределами области определения.

Оптимальные решения

Оптимальное решение (решения) - это последняя точка (точки) перед тем, как прямая целевой функции покинет область определения.

Линейное программирование в реализуемой области с графическим разрешением

Оптимальное решение находится на пересечении первого и второго ограничений, поэтому удовлетворяет обоим ограничениям. Вектор решения есть решение системы:

Линейное программирование в реализуемой области с графическим разрешением

Решением этой системы является (122,78), что дает z = 66100.

Четыре возможности оптимального решения

Есть четыре возможности:

  • либо существует единственное решение (точка);
  • либо бесконечность решений (одна грань);
  • либо решение не ограничено, линия целевой функции всегда будет находиться в области определения, следующей за градиентом;
  • либо решения нет, например если домен пустой.
Делиться
ru_RURU
%d такие блоггеры, как: