Графический метод решения задач ЛП

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Башкирский государственный аграрный университет

Графический метод решения задач ЛП

Голубцова Владислава Олеговна

бакалавр, студент

В данной статье рассматривается графический метод решения задач ЛП, а так же выявлены: методика решения задач ЛП графическим методом и его суть.

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

Каждое из неравенств задачи ЛП определяет на координатной плоскости (х1,х2) некоторую полуплоскость (рис. 1), а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена, выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

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

ЦФ L(x)=с1х1+с2х2 при фиксированном значении L(х)=L определяет на плоскости прямую линию с1х1+с2х2=L. Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

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

Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор C=(c1;c2) с координатами из коэффициентов ЦФ при х1 и х2 перпендикулярен к каждой из линий уровня. Направление вектора С совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора С .

Суть графического метода заключается в следующем. По направлению (против направления) вектора С в ОДР производится поиск оптимальной точки X=(х1;х2). Оптимальной считается точка, через которую проходит линия уровня Lmax(Lmin), соответствующая наибольшему (наименьшему) значению функции L(x). Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

При поиске оптимального решения задач ЛП возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптимум); ЦФ не ограничена; область допустимых решений - единственная точка; задача не имеет решений.

Рисунок 1. Допустимая область - полуплоскость

Методика решения задач ЛП графическим методом

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

Найдите и заштрихуйте полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого подставьте в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверьте истинность полученного неравенства.

Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

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

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

Если ОДР - не пустое множество, то постройте целевую прямую, т.е. любую из линий уровня с1х1+с2х2=L, где L- произвольное число, например, кратное с1 и с2, т.е. удобное для проведения расчетов. Способ построения аналогичен построению прямых ограничений.

Постройте вектор C=(c1,с2), который начинается в точке (0;0), заканчивается в точке (c1,с2). Если целевая прямая и вектор С построены верно, то они будут перпендикулярны.

При поиске max ЦФ передвигайте целевую прямую в направлении вектора С, при поиске min ЦФ - против направления вектора С. Последняя по ходу движения вершина ОДР будет точкой max или min ЦФ. Если такой точки (точек) не существует, то сделайте вывод о неограниченности ЦФ на множестве планов сверху (при поиске шах) или снизу (при поиске min).

Определите координаты точки max(min) ЦФX=(х1*;х2*) и вычислите значение ЦФl(x*). Для вычисления координат оптимальной точки X*решите систему уравнений прямых, на пересечении которых находится X*.

Найдем оптимальное решение задачи, математическая модель которой имеет вид L(Х)=3x1+2x2>max

х1+2х2<6,

2х1+х2<8,

-х1+х2<1,

х2<2,

х1>0, х2>0.

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис. 2 ).

х1+2х2=6,

2х1+х2=8,

-х1+х2=1,

х2=2.

х1=0, х1=6, х2=3, х2=0,

х1=0, х1=4, х2=8, х2=0,

х1=0, х1=-1, х2=1, х2=0,

Прямая проходит через точку х2=2 параллельно оси L(Х).

Рисунок 2. Графическое решение задачи

линейный программирование задача графический

Определим ОДР. Например, подставим точку (0;0) в исходное ограничение, получим 0<1, что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (3). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (рис. 2). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDEF.

Целевую прямую можно построить по уравнению

3х1+2x2=6,

Х1=0, х1=2,

Х2=3, х2=0,

Строим вектор С из точки (0;0) в точку (3;2). Точка Е - это последняя вершина многоугольника допустимых решений ABCDEF, через которую проходит целевая прямая, двигаясь по направлению вектора С. Поэтому Е -это точка максимума ЦФ. Определим координаты точки Е из системы уравнений прямых ограничений (1) и (2)

Х1+2х2=6, (1) х1=10/3=3 1/3, х2=4/3=1 1/3

2Х1+х2=8, (2) Е 3 1/3; 1 1/3

Максимальное значение ЦФ равно L(E)=3*10/3+2*4/3=12 2/3.

Список литературы

Аблеева, А. М. Формирование фонда оценочных средств в условиях ФГОС [Текст] / А. М. Аблеева, Г. А. Салимова // Актуальные проблемы преподавания социально-гуманитарных, естественно - научных и технических дисциплин в условиях модернизации высшей школы : материалы международной научно-методической конференции, 4-5 апреля 2014 г. / Башкирский ГАУ, Факультет информационных технологий и управления. - Уфа, 2014. - С. 11-14.

Ганиева, А.М. Статистический анализ занятости и безработицы [Текст] / А.М. Ганиева, Т.Н. Лубова // Актуальные вопросы экономико-статистического исследования и информационных технологий: сб. науч. ст.: посвящается к 40-летию создания кафедры "Статистики и информационных систем в экономике" / Башкирский ГАУ. - Уфа, 2011. - С. 315-316.

Исмагилов, Р. Р. Творческая группа - эффективная форма организации научных исследований в высшей школе [Текст] / Р. Р. Исмагилов, М. Х. Уразлин, Д. Р. Исламгулов // Научно-технический и научно-образовательный комплексы региона : проблемы и перспективы развития : материалы научно-практической конференции / Академия наук РБ, УГАТУ. - Уфа, 1999. - С. 105-106.

Исламгулов, Д.Р. Компетентностный подход в обучении: оценка качества образования [Текст] / Д.Р. Исламгулов, Т.Н. Лубова, И.Р. Исламгулова // Современный научный вестник. - 2015. - Т. 7. - № 1. - С. 62-69.

Исламгулов, Д. Р. Научно-исследовательская работа студентов - важнейший элемент подготовки специалистов в аграрном вузе [Текст] / Д. Р. Исламгулов // Проблемы практической подготовки студентов в вузе на современном этапе и пути их решения : сб. материалов науч.-метод. конф., 24 апреля 2007 года / Башкирский ГАУ. - Уфа, 2007. - С. 20-22.

Лубова, Т.Н. Основа реализации федерального государственного образовательного стандарта - компетентностный подход [Текст] / Т.Н. Лубова, Д.Р. Исламгулов, И.Р. Исламгулова// БЪДЕЩИТЕ ИЗСЛЕДОВАНИЯ - 2016: Материали за XII Международнанаучна практична конференция, 15-22 февруари 2016. - София: Бял ГРАД-БГ ООД, 2016. - Том 4 Педагогически науки. - C. 80-85.

Лубова, Т.Н. Новые образовательные стандарты: особенности реализации [Текст] / Т.Н. Лубова, Д.Р. Исламгулов // Современный научный вестник. - 2015. - Т. 7. - № 1. - С. 79-84.

Лубова, Т.Н. Организация самостоятельной работы обучающихся [Текст] / Т.Н. Лубова, Д.Р. Исламгулов // Реализация образовательных программ высшего образования в рамках ФГОС ВО: материалы Всероссийской научно-методической конференции в рамках выездного совещания НМС по природообустройству и водопользованию Федерального УМО в системе ВО. / Башкирский ГАУ. - Уфа, 2016. - С. 214-219.

Лубова, Т.Н. Основа реализации федерального государственного образовательного стандарта - компетентностный подход [Текст] / Т.Н. Лубова, Д.Р. Исламгулов, И.Р. Исламгулова // Современный научный вестник. - 2015. - Т. 7. - № 1. - С. 85-93.

Саубанова, Л.М. Уровень демографической нагрузки [Текст] / Л.М. Саубанова, Т.Н. Лубова // Актуальные вопросы экономико-статистического исследования и информационных технологий: сб. науч. ст.: посвящается к 40-летию создания кафедры "Статистики и информационных систем в экономике" / Башкирский ГАУ. - Уфа, 2011. - С. 321-322.

Фахруллина, А.Р. Статистический анализ инфляции в России [Текст] / А.Р. Фахруллина, Т.Н. Лубова // Актуальные вопросы экономико-статистического исследования и информационных технологий: сб. науч. ст.: посвящается к 40-летию создания кафедры "Статистики и информационных систем в экономике" / Башкирский ГАУ. - Уфа, 2011. - С. 323-324.

Фархутдинова, А.Т. Рынок труда в Республике Башкортостан в 2012 году [Электронный ресурс] / А.Т. Фархутдинова, Т.Н. Лубова // Студенческий научный форум. Материалы V Международной студенческой электронной научной конференции: электронная научная конференция (электронный сборник). Российская академия естествознания. 2013.

Размещено на Allbest.ru