Студопедия

КАТЕГОРИИ:


Архитектура-(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)

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




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

найти наибольшее и наименьшее значения функции

(4)

при ограничениях

(5)

. (6)

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

При использовании графического метода применяются линии уровня и градиент.

Для линейной функции вектор градиент , координатами которого являются коэффициенты в целевой функции, показывает направление наискорейшего изменения целевой функции.

Линией уровня функции называется множество всех точек , в которых функция принимает постоянное значение. Для функции линии уровня - это прямые, перпендикулярные градиенту.

Алгоритм графического метода решения задачи линейного программирования (ЗЛП).

1. Построить область допустимых решений (ОДР) задачи в соответствии с системой неравенств .

 

В

 

 

A

 

 

 

Рисунок 1 – Графический метод решения задачи

 

2. Строим градиент и перпендикулярно ему линию уровня – прямую .

3. Линию целевой функции (линия уровня) перемещаем по направлению градиента для задачи на максимум целевой функции и в противоположном направлении - для задач на минимум целевой функции.

4. Параллельным перемещением линии уровня в направлении вектора найдем первую точку «встречи» прямой с ОДР. Это – точка минимума целевой функции . Значение функции является наименьшим значением функции в ОДР.

5. Продолжая передвигать линию уровня, найдем последнюю точку выхода прямой из ОДР. Это - точка максимума целевой функции .

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

7. Находим координаты точки экстремумадля или для и вычисляем значение целевой функции в этой точке.

 

Пример 2. Найти наибольшее и наименьшее значения функции в области решений системы линейных неравенств

1. Построим область решений системы линейных неравенств.

у

 

 

1

О 2 x

Рисунок 2 – Графическое решение ЗЛП

 

Прямая () , точки для построения и . Так как верно, то полуплоскость обращена в сторону точки .

Прямую () строим по точкам и ; неравенство верное, полуплоскость направлена к началу координат.



Прямая () построена по точкам и ; полуплоскость обращена в сторону .

Неравенства и показывают, что искомая область (пересечение всех полуплоскостей) находится в первой координатной четверти.

2. Построим градиент функции . Это вектор с координатами с началом в точке . Перпендикулярно градиенту построим линию уровня функции.

3. Параллельным движением линии уровня в направлении градиента найдем точку «входа» линии уровня в область – это точка О(0,0). Вычислим значение функции в этой точке: .

4. Продолжая движение линии уровня в направлении градиента , найдем точку «выхода» линии уровня из области – это точка А. Для определения ее координат решим систему уравнений прямых и , пересекающихся в точке А: Решение системы уравнений и .

5. Вычислим значение функции в точке : .

Ответ: , .





Дата добавления: 2014-01-07; Просмотров: 910; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.198.118.102
Генерация страницы за: 0.091 сек.