Студопедия

КАТЕГОРИИ:


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

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

Читайте также:
  1. ABC-метод контроля товарно-материальных запасов
  2. I. Место и роль истории в системе человеческих знаний. Предмет и задачи курса истории Отечества.
  3. I. Метод уравнения.
  4. I. Общие цели и задачи обучения физики
  5. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКАЯ ЧАСТЬ.
  6. I. ОСНОВНЫЕ ЗАДАЧИ ВНЕШНЕЙ ПОЛИТИКИ
  7. I. Предмет и задачи дисциплины спутниковая геодезия.
  8. I. Предмет и методы статистической науки
  9. I.2. Метод вариации произвольных постоянных
  10. I.3. Метод исключения
  11. II Графоаналитические методы
  12. II. Метод замены переменной (метод подстановки)



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

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

(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; Просмотров: 1020; Нарушение авторских прав?;


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



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


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



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