Укрупненный алгоритм решения графическим методом

1) В ограничениях задачи (4.1) знаки неравенств заменяются на знаки равенств и строятся соответствующие прямые.

2) Находятся и выделяются полуплоскости, разрешенные каждым из ограничений-неравенств задачи (4.1). (Для этого подставляются в конкретное неравенство координаты точки (0,0), и проверяется выполнение рассматриваемого неравенства. Если неравенство выполнено, то выделяется полуплоскость, содержащая точку (0,0), иначе (если неравенство не выполнено) выделяется полуплоскость, не содержащая данную точку.)

Поскольку x₁ и x₂ должны быть неотрицательными, то допустимые значения всегда будут находиться в 1-м квадранте декартовой плоскости.

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

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

4) Если ОДР является непустым множеством, то строится линия уровня, задаваемая уравнением , где z₀ – произвольное заданное число не равное 0 (например, z ₀ кратное c₁ и c₂, т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

5) Строится вектор C=(c₁,c₂), с началом в точке (0,0). (Вектор C будет перпендикулярен линиям уровня.)

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

7) Определяются координаты точки, оптимизирующей ЦФ:

x_опт =(x_1опт, x_2опт).

Для вычисления координат точки x_опт решается система из двух уравнений прямых, на пересечении которых находится x_опт. На основании полученного результата вычисляется значение ЦФ в точке оптимума z(x_опт)

Дата добавления: 2015-07-15