Презентация на тему линейное программирование. Презентация на тему "задачи линейного программирования". Задача оптимального распределения ресурсов

Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) 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 классе. ...

материал предназначен для студентов повышенного уровня. в программе рассмотрен алгоритм составления базисного и опорного плпна разными методами и нахождение оптимального решения...

Рабочая тетрадь к уроку математики на тему «Задачи линейного программирования» разработана мною для одноимённого урока математики (повышенный уровень). может быть использована как на уроке, семинарско...

Нажав на кнопку "Скачать архив", вы скачаете нужный вам файл совершенно бесплатно.
Перед скачиванием данного файла вспомните о тех хороших рефератах, контрольных, курсовых, дипломных работах, статьях и других документах, которые лежат невостребованными в вашем компьютере. Это ваш труд, он должен участвовать в развитии общества и приносить пользу людям. Найдите эти работы и отправьте в базу знаний.
Мы и все студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будем вам очень благодарны.

Чтобы скачать архив с документом, в поле, расположенное ниже, впишите пятизначное число и нажмите кнопку "Скачать архив"

Подобные документы

Задачи оптимизации. Ограничения на допустимое множество. Классическая задача оптимизации. Функция Лагранжа. Линейное программирование: формулировка задач и их графическое решение. Алгебраический метод решения задач. Симплекс-метод, симплекс-таблица.

реферат , добавлен 29.09.2008


Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.

курсовая работа , добавлен 27.03.2011


Общие задачи линейного программирования. Описание алгоритма симплекс-метода, записанного в канонической форме с односторонними ограничениями. Алгоритм построения начального опорного плана для решения задачи. Расширенный алгоритм искусственного базиса.

курсовая работа , добавлен 24.10.2012


Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.

реферат , добавлен 21.08.2008


Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.

курсовая работа , добавлен 05.01.2015


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

курсовая работа , добавлен 11.02.2011


Понятие теории оптимизации экономических задач. Сущность симплекс-метода, двойственности в линейном программировании. Элементы теории игр и принятия решений, решение транспортной задачи. Особенности сетевого планирования и матричное задание графов.

Принятие решений в условиях неопределенности Если первый субъект имеет m стратегий, а второй - n стратегий, то говорят, что мы имеем дело с игрой m x n. Рассмотрим игру m x n. Пусть заданы множество стратегий: для первого игрока {Аi}, для второго игрока {Bj}, платежная матрица, где aij – выигрыш первого игрока или проигрыш второго игрока при выборе ими стратегий Аi и Bj соответственно. Каждый из игроков выбирает однозначно с вероятностью I некоторую стратегию, т.е. пользуется при выборе решения чистой стратегией. При этом решение игры будет в чистых стратегиях. Поскольку интересы игроков противоположны, то первый игрок стремится максимизировать свой выигрыш, а второй игрок, наоборот, минимизировать свой проигрыш. Решение игры состоит в определении наилучшей стратегии каждым игроком. Выбор наилучшей стратегии одним игроком проводится при полном отсутствии информации о принимаемом решении вторым игроком.

Решение систем линейных неравенств



Неравенства

Линейные неравенства – это неравенства вида ∑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 одновременно. Другими словами, точка М принадлежит пересечению (общей части) указанных полуплоскостей. Легко видеть, что пересечение конечного числа полуплоскостей есть некоторая многоугольная область.



Пример

Вдоль контура области изображены штрихи, идущие внутрь области. Они одновременно указывают, с какой стороны от данной прямой лежит соответствующая полуплоскость; то же самое указано и с помощью стрелок.



Неограниченная область решений

Область К называется областью решений системы неравенств. Сразу же отметим, что область решений не всегда бывает ограничена; в результате пересечения нескольких полуплоскостей может возникнуть и неограниченная область.

Линейное программирование▪ Задача линейного программирования – 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;
Определить оптимальный состав ОТК,
при котором общие затраты на контроль будут минимальны.