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

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

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

1. На плоскости X₁0X₂ строят прямые.
2. Определяются полуплоскости.
3. Определяют многоугольник решений;
4. Строят вектор N(c₁,c₂), который указывает направление целевой функции;
5. Передвигают прямую целевую функцию c₁x₂+ c₂x₂ = 0 в направлении вектора N до крайней точки многоугольника решений.

Вычисляют координаты точки и значение целевой функции в этой точке.

Алгоритмический метод.

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

Рассмотренные выше методы служат для сбора информации о субъекте труда или профессиональной среде. Вместе с тем существует ряд методов упорядочения полученной информации. Одним из таких методов является алгоритмический анализ. Алгоритм — строгая последовательность действий, которая неизбежно приводит к решению задачи определенного класса. Эта последовательность действий может иметь словесное описание, в котором представлены все элементарные действия и логические условия, определяющие порядок этих действий, а может быть описана в символической форме или в виде графика. Метод дает возможность представить совокупность действий в компактной форме и понять их закономерные связи. Благодаря своей полноценности, конкретности и систематичности алгоритмы позволяют постепенно проследить характер операций, выполняемых работниками, и установить те звенья процесса, в которых наиболее часты аварии и брак и которые необходимо рационализировать или автоматизировать в первую очередь, либо функции, требующие перераспределения или изменения.

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

Введение в симплексный алгоритм.

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

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

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

Шаг 2. Проверим, нельзя ли за счет одной из переменных, при­равненной вначале к нулю, улучшить значение целевой функции, придавая ей отличные от нуля (причем положительные) значения. Если это возможно, перейдем к шагу 3. В противном случае прекра­тим вычисления.

Шаг 3. Найдем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Увеличение значения этой переменной допустимо до тех пор, пока одна из т переменных, вошедших в пробное решение, не обратится в нуль. Исключим из вы­ражения для целевой функции только что упомянутую переменную и введем в пробное решение ту переменную, за счет которой результат может быть улучшен.

Шаг 4. Разрешим систему т уравнений относительно переменных, вошедших в новое пробное решение. Исключим эти переменные из выражения для целевой функции. Вернемся к шагу 2.

Важно отметить, что при однозначном понимании данного пред­писания предложенный алгоритм действительно приводит к опти­мальному решению для любой модели линейного программирования за конечное число итераций. Такой способ решения задач линей­ного программирования часто называют симплексным алгорит­мом.

Обратимся вначале к одной простой задаче, не имеющей никаких «аномалий», и попытаемся с ее помощью получить общее представ­ление о симплексном методе. К более подробному анализу данного метода вернемся несколько позже.

Источник

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

Графический метод используется для решения задач с двумя переменными вида: ; Данный метод основывается на возможности графического изображения области допустимых решений задачи и нахождении среди них оптимального решения. Область допустимых решений задачи строится как пересечение (общая часть) областей решений каждого из заданных ограничений. Областью решений линейного неравенства является одна из двух полуплоскостей, на которые прямая,соответствующая данному неравенству, делит всю координатную плоскость. Для того, чтобы определить, какая из двух координатных полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство: если оно удовлетворяется, то областью решений является полуплоскость, содержащая данную точку, если же неравенство не удовлетворяется, то областью решений является полуплоскость, не содержащая данную точку. Областью допустимых решений задачи является общая часть полуплоскостей – областей решений всех неравенств системы ограничений. АЛГОРИТМ

1. Построить множество допустимых решений. В общем случае оно представляет собой выпуклый многоугольник. Если ограничения в задаче несовместны, множество допустимых решений является пустым множеством, а задача поиска экстремума не имеет смысла.
2. Найти градиент целевой функции , построить его.
3. Провести линию уровня целевой функции, перпендикулярную градиенту.
4. Перемещать линию уровня параллельно самой себе в направлении , найти точку, в которой f достигает максимума (минимума).
5. Найти координаты , решая систему уравнений прямых, пересекающихся в точке оптимума, вычислить .

В случае непустого множества допустимых решений возможны три типовых ситуации:

1. задача имеет единственное решение (линия уровня касается множества допустимых решений в одной точке);
2. задача имеет бесконечное множество решений (линия уровня касается множества допустимых решений вдоль стороны многоугольника);
3. задача не имеет решения (множество допустимых решений не ограничено).

Пример 1. Решить задачу линейного программирования ; Решение. Построим множество допустимых решений. Нумеруем ограничения задачи. В прямоугольной декартовой системе координат строим прямую , соответствующую ограничению (1). Находим, какая из двух полуплоскостей является областью решений неравенства. Так, прямая (1) не проходит через начало координат, подставляем координаты точки О (0, 0) в первое ограничение. Получаем верное строгое неравенство 0 > -2. Следовательно, точка О лежит в полуплоскости решений. Аналогично строим прямые (2) – (4). Рис. 1. Нашли , провели линию уровня функции, перпендикулярно градиенту, передвигаем ее параллельно самой себе в направлении. Эта прямая проходит через точку Х* пересечения прямых, ограничивающих область допустимых решений и соответствующих неравенствам (1) и (2). Определяем координаты точки Х*, решая систему. Получаем Х*(1, 3). Вычисляем. Ответ: при Х* = (1, 3). Задача линейного программирования не всегда задается в виде математической модели. Пример составления математической модели рассмотрен на примере транспортной задачи (п. 3).

Для продолжения скачивания необходимо пройти капчу:

Источник

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

Методы решения задач линейного программирования в зависимости от размерности задачи оптимизации подразделяются на графические и аналитические [1,2,7]. Графический метод оптимизации применяется только для двумерных задач, когда решение можно представить на плоскости. Это позволяет получить наглядное представление об оптимизационном решении задачи, что является основным достоинством метода. Но возможности применения метода ограничены, он может использоваться для простейших математических моделей на отдельных этапах анализа сложных оптимизационных процессов. Рассмотрим применение графического метода на примере задачи рационального распределения ресурсов. Условие задачи, связанной с рациональным использованием топлива на тепловых станциях энергосистемы для получения максимального суммарного отпуска электроэнергии, и исходные данные для простейшего случая двумерной задачи, представлены в табл.2.1 (численные значения параметров носят условный характер и определяются удобством проведения расчетов). Математическая модель задачи рационального распределения ресурсов включает в себя целевую функцию (2.2), ограничения (2.3-2.4) и граничные условия (2.5). Математически требуется найти решение W₁,W₂, удовлетворяющее системе неравенств (2.3-2.5), соответствующее максимуму F. Алгоритм графического метода сводится к следующим этапам:

• Построение области допустимых решений (ОДР):
  • отобразим графически на плоскости неравенство (2.3), для этого перейдем к уравнению вида:

, которое представим графически прямой (1) на рис 2.1 по точкам (W₁=750, W₂=0) и (W₁=0, W₂=1200). Неравенство (2.3) определяет полуплоскость, заштрихуем ту часть, которая не удовлетворяет неравенству (рис.2.1).

• аналогичные построения проведем для неравенства (2.4) – линия (2) рис.2.1 по точкам (W₁=1400,W₂=0) и (W₁=0, W₂=700);
• граничные условия соответствуют двум дополнительных неравенствам (2.5), которые определяют неотрицательность переменных W₁ и W₂, что отображено штриховкой на рис 2.1.

Координаты всех точек не заштрихованного многоугольника ABCO имеют такие значения W₁ и W₂, которые удовлетворяют системе неравенств (2.3-2.5) и образуют область допустимых решений.

• Построение графика целевой функции.

Графически видно, что оптимизационная задача имеет множество допустимых решений, из которых требуется найти оптимальное, удовлетворяющее в данном случае максимуму целевой функции. Для графического представления целевой функции зададимся произвольным значением F=12000 и построим линию (3), которая называется линией уровня целевой функции (рис.2.1): (2.6) по точкам (W₁=0, W₂=600) и (W₁=800, W₂=0) Возможное увеличение целевой функции связано с удалением прямой от начало координат. Убедимся в этом, построив еще одну линию уровня для значения F=15000 – линия (4) рис.2.1. (2.7) по точкам (W₁=0,W₂=750) и (W₁=1000,W₂=0) Стрелка на рис.2.1 указывает направление возрастания F. Максимума она достигает в вершине B многоугольника ABCO ОДР. Таким образом, полученное решение соответствует отпуску энергии с шин ТЭС: W₁=450 МВтч; W₂=470 МВтч; F_опт=16150 тыс.руб. На основании рассмотренного примера можно сделать вывод: оптимальным решением всегда являются координаты вершины области допустимых решений.

Источник