КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Графический (геометрический) метод решения задач ЛП
Пример 5.1. Решить следующую задачу линейного программирования геометрическим методом: . Решение: Задача линейного программирования задана в стандартной форме и имеет два проектных параметра, следовательно, возможно ее решение геометрическим методом. 1 этап: построение прямых, ограничивающих область допустимых решений (ОДР). Рассмотрим систему ограничений задачи линейного программирования (для удобства пронумеруем неравенства):
Рассмотрим первое ограничение, заменим знак неравенства знаком равенства и выразим переменную х2 через х1: . Для построения прямой по данному уравнению зададим две произвольные точки, к примеру: Аналогично определяем точки для остальных ограничений системы и строим по ним прямые, соответствующие каждому неравенству (рис. 5.1). Прямые пронумеруем согласно принятой ранее схеме. 2 этап: определение решения каждого из неравенств системы ограничений. Определим полуплоскости – решения каждого из неравенств. Рассмотрим первое неравенство системы ограничений задачи. Возьмем какую-либо точку (контрольную точку), не принадлежащую соответствующей данному неравенству прямой, например, точку (0; 0). Подставим ее в рассматриваемое неравенство: . При подстановке координат контрольной точки неравенство остается справедливым. Следовательно, множество точек, принадлежащих данной прямой (т.к. неравенство не строгое), а также расположенных ниже ее, будут являться решениями рассматриваемого неравенства (пометим на графике (рис. 5.1) найденную полуплоскость двумя стрелками направленными вниз рядом с прямой I)[1]. Аналогично определяем решения других неравенств и соответственно помечаем их графике. В результате график примет следующий вид:
3 этап: определение ОДР задачи линейного программирования. Найденные полуплоскости (решения каждого из неравенств системы ограничений) при пересечении образуют многоугольник ABCDEO, который и является ОДР рассматриваемой задачи. Рис. 5.1. Область допустимых решений задачи
4 этап: построение вектора-градиента. Вектор-градиент показывает направление максимизации целевой функции[2]. Определим его координаты: координаты начальной его точки (точки приложения) – (0; 0), координаты второй точки: Построим данный вектор на графике (рис. 5.2). 5 этап: построение прямой целевой функции. Рассмотрим целевую функцию данной задачи: . Зададим ей какое-либо значение, к примеру, . Выразим переменную х2 через х1: . Для построения прямой по данному уравнению зададим две произвольные точки, к примеру: Построим прямую соответствующую целевой функции (рис. 5.2).
Рис. 5.2. Построение целевой функции F(X) и вектора-градиента С
6 этап: определение максимума целевой функции. Перемещая прямую F(X) параллельно самой себе по направлению вектора-градиента, определяем крайнюю точку (точки) ОДР. Согласно графику (рис. 5.3), такой точкой является точка С – точка пересечения прямых I и II.
Рис. 5.3. Определение точки максимума целевой функции F(X)
Определим координаты точки С, с этой целью, решим следующую систему линейных уравнений: Подставим найденные координаты в целевую функцию и найдем ее оптимальное (максимальное) значение: Ответ: при заданных ограничениях максимальное значение целевой функции F (Х)=24, которое достигается в точке С, координаты которой х1 =6, х2 =4. Пример 5.2. Решить задачу линейного программирования геометрическим методом: Решение: Этапы 1-3 аналогичны соответствующим этапам предыдущей задачи. 4 этап: построение вектора-градиента.
Построение вектора-градиента осуществляется аналогично, как и в предыдущей задаче. Построим данный вектор на графике (рис. 5.4). Отметим также на данном графике стрелкой направление, обратное вектору-градиенту, – направление минимизации целевой функции F (X). 5 этап: построение прямой целевой функции. Построение прямой целевой функции F (X) осуществляется аналогично, как и в предыдущей задаче (результат построения приведен на рис. 5.4).
Рис. 5.4. Построение целевой функции F(x) и вектора-градиента С
6 этап: определение оптимума целевой функции. Перемещая прямую F(x) параллельно самой себе в направлении, обратном вектору-градиенту, определяем крайнюю точку (точки) ОДР. Согласно графику (рис. 5.5), такой точкой является точка О с координатами (0; 0).
Рис. 5.5. Определение точки минимума целевой функции
Подставляя координаты точки минимума в целевую функцию, определяем ее оптимальное (минимальное) значение, которое равно 0. Ответ: при заданных ограничениях минимальное значение целевой функции F (Х)=0, которое достигается в точке О (0; 0). Пример 5.3. Решить следующую задачу линейного программирования геометрическим методом: Решение: Рассматриваемая задача линейного программирования задана в канонической форме, выделим в качестве базисных переменные x1 и x2. Составим расширенную матрицу и выделим с помощью метода Жордана-Гаусса базисные переменные x1 и x2. Умножим (поэлементно) первую строку на –3 и сложим со второй: . Умножим вторую строку на : . Сложим вторую с первой строкой: . В результате система ограничений примет следующий вид: Выразим базисные переменные через свободные: Выразим целевую функцию также через свободные переменные, для этого подставим полученные значения базисных переменных в целевую функцию: . Запишем полученную задачу линейного программирования Так как переменные x1 и x2 неотрицательные, то полученную систему ограничений можно записать в следующем виде: Тогда исходную задачу можно записать в виде следующей эквивалентной ей стандартной задаче линейного программирования: Данная задача имеет два проектных параметра, следовательно, возможно ее решение геометрическим методом.
1 этап: построение прямых, ограничивающих область допустимых решений (ОДР). Рассмотрим систему ограничений задачи линейного программирования (для удобства пронумеруем неравенства): Построим прямые, соответствующие каждому неравенству (рис. 5.6). Прямые пронумеруем согласно принятой ранее схеме. 2 этап: определение решения каждого из неравенств системы ограничений. С помощью контрольных точек определим полуплоскости – решения каждого из неравенств, и пометим их на графике (рис. 5.6) с помощью стрелок. 3 этап: определение ОДР задачи линейного программирования. Найденные полуплоскости (решения каждого из неравенств системы ограничений) не имеют общего пересечения (так решения неравенства I противоречат в целом остальным неравенствам системы ограничений), следовательно, система ограничений не совместна и задача линейного программирования в силу этого не имеет решения.
Рис. 5.6. Фрагмент MathCAD-документа: построение области допустимых решений задачи
Ответ: рассматриваемая задача линейного программирования не имеет решения в силу несовместности системы ограничений.
Дата добавления: 2014-01-04; Просмотров: 301; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |