Презентация Графический метод решения ЗЛП Лекция 5 онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Графический метод решения ЗЛП Лекция 5 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 29 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:29 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:258.00 kB
- Просмотров:112
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Графический метод решения ЗЛП
Лекция 5
№2 слайд
Содержание слайда: Рассмотрим ЗЛП на плоскости.
при ограничениях
№3 слайд
Содержание слайда: Каждое неравенство системы ограничений геометрически определяет полуплоскость с граничными прямыми
Условия неотрицательности определяют полуплоскости с граничными прямыми
Если система ограничений совместна, то область ее решения есть множество точек, принадлежащих всем указанным полуплоскостям. Совокупность этих точек называют многоугольником решений. Или областью допустимых решений (ОДР) ЗЛП.
№4 слайд
Содержание слайда: Опр. Множество точек называется выпуклым, если вместе с любыми двумя точками оно содержит и весь отрезок. Тогда ОДР может быть вида:
Выпуклый многоугольник;
Выпуклая многоугольная неограниченная область;
Пустая область;
Отрезок;
Единственная точка.
№5 слайд
Содержание слайда: Целевая функция
определяет на плоскости семейство прямых, одна из которых проходит через начало координат. Эта прямая называется основной.
Прямая эта перпендикулярна нормальному вектору .
Этот вектор указывает направление наискорейшего возрастания функции, а противоположный ему –направление наискорейшего убывания. Так что это вектор вида
№6 слайд
Содержание слайда: Прямая , перпендикулярная градиенту, является линией уровня целевой функции и поэтому во всех своих точках принимает одно и тоже значение. Приравнивая целевую функцию к постоянной , а затем меняя ее, получим семейство прямых, каждая из которых является линией уровня, которые обладают свойством: при смещении в одну сторону уровень только возрастает, а в другую- только убывает.
№7 слайд
Содержание слайда: Геометрическая интерпретация ЗЛП:
Среди множества решений, которые находятся в многоугольнике решений, следует отыскать точку многоугольника, координаты которой обращают в максимум или минимум целевую функцию.
Теорема. Если ЗЛП имеет оптимальный план, то целевая функция принимает свое оптимальное значение в одной из вершин многоугольника решений.
№8 слайд
Содержание слайда: Для определения этой вершины строится основная прямая
,
которую перемещают в направлении градиента до тех пор, пока она не коснется последней крайней точки многоугольника решений. Это может быть вершина многоугольника, координаты которой и определяют максимальное значение целевой функции. Может быть и такой случай, когда последняя точка лежит на стороне многоугольника, и тогда целевая функция принимает максимальное значение на всей этой прямой. Если же в направлении градиента многоугольник решений неограничен, то
.
№9 слайд
Содержание слайда: Графический метод решения ЗЛП
Нахождение решения ЗЛП на основе ее геометрической интерпретации включает следующие этапы:
1).Строят прямые, уравнения которых получаются в результате замены в ограничениях задачи знаков неравенств на знаки равенств.
2).Находят полуплоскости, определяемые из ограничений задачи.
3).Находят многоугольник решений.
4). Строят вектор .
5). Строят прямую , проходящую через многоугольник решений.
6).Передвигают эту прямую в направлении градиента.
7)Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.
№10 слайд
Содержание слайда: Пример. Задача о костюмах.
Намечается выпуск двух видов костюмов - мужских и женских.. На женский костюм требуется 1м шерсти, 2м полиэстера и 1человеко-день трудозатрат. На мужской –3,5м шерсти, 0,5м полиэстера и 1 человеко-день трудозатрат. Всего имеется 350м шерсти, 240 м полиэстера и150 человекодней трудозатрат.
№11 слайд
Содержание слайда: Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского-20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.
№12 слайд
Содержание слайда: Решение.
Обозначим: -число женских и число мужских костюмов соответственно.
Целевая функция .
Ограничения
№13 слайд
Содержание слайда: Построим прямые
Первая прямая пересекает оси координат в точках (350;0) и (0;100), вторая – в точках (120;0) и (0;0;480), третья – в точках (150;0) и (0;150).Четвертая прямая проходит параллельно оси .
№14 слайд
Содержание слайда: Строим все прямые и получаем четырехугольник, все точки которого удовлетворяют всем четырем функциональным ограничениям. Легко проверить: например, т.(0;0) лежит ниже всех трех первых прямых, но не удовлетворяет последнему соотношению. Так что, все точки внутри многоугольника удовлетворяют всем четырем неравенствам. Теперь построим градиент целевой функции (10;20).
Для этого соединим точку (10,20) с началом координат. Можно построить вектор, пропорциональный этому вектору, т.е. длиннее или короче в зависимости от масштаба
№15 слайд
Содержание слайда: Затем перпендикулярно ему основную прямую и будем перемещать ее в направлении градиента до ее выхода из ОДР. Это произойдет в точке пересечения прямых
№16 слайд
Содержание слайда: Решим систему двух уравнений
и получим точку
При этих значениях
№17 слайд
Содержание слайда:
№18 слайд
Содержание слайда: Пример
Найти максимум и минимум функции
при ограничениях
№19 слайд
Содержание слайда: Решение. Строим многоугольник решений. Для этого изобразим прямые
Первая из них проходит через токчи (8;0) и (0;8), вторая – через точки (0,5;0) и (0;-1), третья –через точки (2;0) и (0;-1).
Далее изобразим градиент (3;3) и линии уровня.
№20 слайд
Содержание слайда:
№21 слайд
Содержание слайда: Передвигая линию уровня в направлении
возрастания , т.е. в направлении градиента, получаем, что целевая функция достигает максимального значения вдоль прямой
На прямой возьмем точку , например В, координаты которой можно найти из системы уравнений
Целевая функция здесь имеет значение
№22 слайд
Содержание слайда: При решении данной задачи на минимум целевой функции линию уровня
следует двигать в направлении, обратном направлению градиента. Целевая функция достигает минимума в точке D пересечения прямой с осью , т.е. в точке ((0,5;0). Тогда
№23 слайд
Содержание слайда: Пример.
Найти максимум функции
при ограничениях
№24 слайд
Содержание слайда: Эта задача не имеет решения, т.к. целевая функция не ограничена сверху на ОДР. Это означает, что
№25 слайд
Содержание слайда:
№26 слайд
Содержание слайда: Найти максимум функции
при ограничениях
№27 слайд
Содержание слайда: Строим прямые, заменив знаки неравенств на знаки равенства, а затем закрасим область допустимых решений. Очевидно, начало координат находится ниже прямой , не удовлетворяет второму неравенству
, поэтому точки области лежат правее этой прямой. Последнему неравенству удовлетворяет и поэтому получаем область на рисунке
№28 слайд
Содержание слайда:
№29 слайд
Содержание слайда: Из рисунка видим, что множество планов пусто, т.к.закрашенные области не имеют общих точек.
Скачать все slide презентации Графический метод решения ЗЛП Лекция 5 одним архивом:
