Презентация на тему «Тема «Линейное программирование. Презентация: Линейное программирование, решение задач симплексным методом Презентация графического метода линейного программирования
Линейное программирование▪ Задача линейного программирования – 3 слайд.
▪ Геометрический метод решения ЗЛП – 26 слайд.
▪ Задача линейного программирования в стандартной форме – 32 слайд.
▪ Симплексный метод решения ЗЛП – 42 слайд.
▪ Метод Гаусса – 48 слайд.
▪ Симплекс метод – 58 слайд.
▪ Метод искусственного базиса – 76 слайд.
▪ Двойственность задач линейного программирования – 87 слайд.
Задача линейного программирования (ЛП)
▪Задачи ЛП – самая обширная часть оптимизационных (примерно 70%)
Этапы построения математической модели
1. Определение переменных задачи.2. Представление ограничений в виде линейных уравнений
или неравенств.
3. Задание линейной целевой функции и смысла
оптимизации.
Классические задачи линейного программирования
▪ Задача технического контроля (слайд 6);▪ Транспортная задача (слайд 13);
▪ Задача о диете (слайд 16);
▪ Задача об использовании сырья (слайд 19).
Задача технического контроля
Примечание: ОТК – Отдел Технического Контроля В ОТК некоторой фирмы работают контролеры 1 и 2 разрядов (К1 иК2);
Норма выработки ОТК за 8 часов (раб. день) составляет не менее
1800 изделий;
К1 проверяет 25 изделий/час (точность 98%);
К2 проверяет 15 изделий/час (точность 95%);
Заработная плата К1 равна 4$ / час;
Заработная плата К2 равна 3$ / час;
При каждой ошибке контролера фирма несет убыток в 2$;
Фирма может использовать не более 8 - К1 и 10 - К2;
Определить оптимальный состав ОТК,
при котором общие затраты на контроль будут минимальны.
Решение систем линейных неравенств
Неравенства
Линейные неравенства – это неравенства вида ∑ai xi +b≥c
Задание системы линейных неравенств с двумя или тремя неизвестными означает задание выпуклой многоугольной области на плоскости или, соответственно, выпуклого многогранного тела в пространстве.
Начиная с середины 40-х годов этого столетия, возникла новая область прикладной математики – линейное программирование – с важными приложениями в экономике и технике. В конечном счете линейное программирование – это всего лишь один из разделов (хотя и очень важный) теории систем линейных неравенств.
Рассмотрим уравнение первой степени с двумя неизвестными x и y
Истолковывая x и y как координаты точки
на плоскости, можем сказать, что
множество точек, определяемых уравнением (1), есть прямая линия на плоскости.
Геометрический смысл уравнения первой степени
Аналогично для неравенства ax+by+c≥0. (2)
Если b≠0, то данное неравенство приводится к одному из видов у≥kх+p или у≤kх+р.
Первому из этих неравенств удовлетворяют все точки, лежащие «выше» прямой у=kх+р или же на этой прямой, а второму – все точки, лежащие «ниже» прямой у=kх+р или на этой прямой.
Если же b=0, то неравенство приводится к одному из видов х≥h или х≤h. Первому из них удовлетворяют все точки, лежащие «правее» прямой х=h или на этой прямой, второму – все точки, лежащие «левее» прямой х=h или на этой прямой.
Геометрический смысл системы линейных неравенств
Пусть дана система неравенств с двумя неизвестными х и у. a1 x+b1 y+c1 ≥0,
a2 x+b2 y+c2 ≥0,
………….........
am x+bm y+cm ≥0.
Первое неравенство системы определяет на координатной плоскости хОу некоторую полуплоскость П1 , второе – полуплоскость П2 и т.д. Если пара чисел х, у удовлетворяет всем неравенствам системы, то соответствующая точка М(х, у) принадлежит всем полуплоскостям П1 ,П2 ,...,Пm одновременно. Другими словами, точка М принадлежит пересечению (общей части) указанных полуплоскостей. Легко видеть, что пересечение конечного числа полуплоскостей есть некоторая многоугольная область.
Пример
Вдоль контура области изображены штрихи, идущие внутрь области. Они одновременно указывают, с какой стороны от данной прямой лежит соответствующая полуплоскость; то же самое указано и с помощью стрелок.
Неограниченная область решений
Область К называется областью решений системы неравенств. Сразу же отметим, что область решений не всегда бывает ограничена; в результате пересечения нескольких полуплоскостей может возникнуть и неограниченная область.
Принятие решений в условиях неопределенности Если первый субъект имеет m стратегий, а второй - n стратегий, то говорят, что мы имеем дело с игрой m x n. Рассмотрим игру m x n. Пусть заданы множество стратегий: для первого игрока {Аi}, для второго игрока {Bj}, платежная матрица, где aij – выигрыш первого игрока или проигрыш второго игрока при выборе ими стратегий Аi и Bj соответственно. Каждый из игроков выбирает однозначно с вероятностью I некоторую стратегию, т.е. пользуется при выборе решения чистой стратегией. При этом решение игры будет в чистых стратегиях. Поскольку интересы игроков противоположны, то первый игрок стремится максимизировать свой выигрыш, а второй игрок, наоборот, минимизировать свой проигрыш. Решение игры состоит в определении наилучшей стратегии каждым игроком. Выбор наилучшей стратегии одним игроком проводится при полном отсутствии информации о принимаемом решении вторым игроком.
Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com
Подписи к слайдам:
Решение простейших задач линейного программирования графическим методом 17.04.2012г.
Если система ограничений задачи линейного программирования представлена в виде системы линейных неравенств с двумя переменными, то такая задача может быть решена геометрически.
Задача. Имеется 14 каналов радиорелейной связи (РРС) и 9 каналов тропосферной. По ним необходимо передать информацию 3 видов: А, В, С. Причем информация А равна 600 у.е., В – 3000 у.е., С – 5500 у.е. (под информацией можно понимать число телефонных разговоров, передачу данных и пр.). Возможности каналов и затраты на обслуживание каждого канала заданы в таблице. Требуется отыскать задействованное количество каналов обоих видов, необходимое для передачи требуемой информации, чтобы стоимость эксплуатации была минимальной.
Виды информации Каналы связи Требуемое количество информации, у.ед. Тропосферная РРС А 80 40 600 В - 1000 3000 С 300 800 5500 Затраты на обслуживание одного канала, руб. 3000 2000
Этапы решения ЗЛП: Построить ОДР. Построить вектор-градиент целевой функции в какой-нибудь точке Х 0 принадлежащей ОДР – (c 1 ;c 2) . Построить прямую c 1 x 1 + c 2 x 2 = h, где h - любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений.
Перемещать найденную прямую параллельно самой себе в направлении вектора-градиента до тех пор, пока прямая не покинет ОДР (при поиске максимума) или в противоположном ему (при поиске минимума) . В предельной точке целевая функция достигает максимума(минимума), либо устанавливается неограниченность функции на множестве решений. Определить координаты точки максимума (минимума) функции и вычислить значение функции в этой точке.
По теме: методические разработки, презентации и конспекты
Данная разработка может применяться как обобщающий урок по теме "Системы неравенств с двумя переменными" в 9 классе (алгебра 9 под ред. Теляковского) и как урок повторения по данной теме в 10 классе. ...
материал предназначен для студентов повышенного уровня. в программе рассмотрен алгоритм составления базисного и опорного плпна разными методами и нахождение оптимального решения...
Рабочая тетрадь к уроку математики на тему «Задачи линейного программирования» разработана мною для одноимённого урока математики (повышенный уровень). может быть использована как на уроке, семинарско...