Линейное программирование в экономике презентация. Решение задач линейного программирования графическим методом презентация к уроку по алгебре на тему

Описание презентации по отдельным слайдам:

1 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Линейное программирование К этому классу линейного программирования (75% решаемых американцами задач) относятся задачи, в которых целевая функция Wm(x), m=1,2,...,M, ограничения в виде равенств hk(x)=0, k=1,2...K, и неравенств gj(x)>0, j=1,2,...J, - линейны и нет математического решения. Возможные тематики задач ЛП: рациональное использование сырья и материалов; задачи оптимизации раскроя; оптимизации производственной программы предприятий; оптимального размещения и концентрации производства; на составление оптимального плана перевозок, работы транспорта; управления производственными запасами; и многие другие, принадлежащие сфере оптимального планирования. Постановка задачи ЛП (определение показателя эффективности, переменных задачи, задание линейной целевой функции W(x), подлежащей минимизации или максимизации, функциональных hk(x), gj(x) и областных xli

2 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Пример задачи ЛП Пример – Оптимизация размещения побочного производства лесничества Лесничество имеет 24 га свободной земли под паром и заинтересовано извлечь из нее доход. Оно может выращивать саженцы быстрорастущего гибрида новогодней ели, которые достигают спелости за один год, или бычков, отведя часть земли под пастбище. Деревья выращиваются и продаются в партиях по 1000 штук. Требуется 1.5 га для выращивания одной партии деревьев и 4 га для вскармливания одного бычка. Лесничество может потратить только 200 ч. в год на свое побочное производство. Практика показывает, что требуется 20 ч. для культивации, подрезания, вырубки и пакетирования одной партии деревьев. Для ухода за одним бычком также требуется 20 ч. Лесничество имеет возможность израсходовать на эти цели 6 тыс. руб. Годовые издержки на одну партию деревьев выливаются в 150 руб. и 1,2 тыс. руб. на одного бычка. Уже заключен контракт на поставку 2 бычков. По сложившимся ценам, одна новогодняя ель принесет прибыль в 2,5 руб., один бычок - 5 тыс. руб.

3 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Постановка задачи 1. В качестве показателя эффективности целесообразно взять прибыль за операцию (годовую прибыль с земли в рублях). 2. В качестве управляемых переменных задачи следует взять: x1 - количество откармливаемых бычков в год; x2 - количество выращиваемых партий быстрорастущих новогодних елей по 1000 шт. каждая в год. 3. Целевая функция: 5000 x1 + 2500 x2  max, где 5000 - чистый доход от одного бычка, руб.; 2500 - чистый доход от одной партии деревьев (1000 шт. по 2,5 руб.). 4. Ограничения: 4.1. По использованию земли, га: 4 x1 + 1,5 x2  24 4.2. По бюджету, руб.: 1200 x1 + 150 x2  6000 4.3. По трудовым ресурсам, ч: 20 x1 + 20 x2  200 4.4. Обязательства по контракту, шт.: x1  2 4.5. Областные ограничения: x1  0, x2  0

4 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Графическое решение задачи ЛП Отображая на графике прямые, соответствующие следующим уравнениям, 4 x1 + 1,5 x2 = 24 1200 x1 + 150 x2 = 6000 20 x1 + 20 x2 = 200 x1 = 2 x2 = 0 заштриховываем область, в точках которой выполняются все ограничения. Каждая такая точка называется допустимым решением, а множество всех допустимых решений называется допустимой областью. Очевидно, что решение задачи ЛП состоит в отыскании наилучшего решения в допустимой области, которое, в свою очередь, называется оптимальным. В рассматриваемом примере оптимальное решение представляет собой допустимое решение, максимизирующее функцию W=5000 x1 + 2500 x2. Значение целевой функции, соответствующее оптимальному решению, называется оптимальным значением задачи ЛП.

5 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Графическое решение задачи ЛП

6 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Графическое решение задачи ЛП Перебор всех угловых точек области допустимых решений приводит к нахождению максимального дохода в размере 34 тыс. руб. (W=5000x1+2500x2), которое лесничество может извлечь, выращивая 3,6 бычка и 6,4 партии новогодних елей. Целочисленные методы (например, перебор) дают x1=3 и x2=6, что приводит к доходу в 30 тыс. руб., x1=4 и x2=5 приводит к более оптимальному результату в 32,5 тыс. руб., точка x1=3 и x2=7 приводит к аналогичному результату. Графический метод ввиду большой размерности реальных практических задач ЛП достаточно редко применяется, однако он позволяет ясно уяснить одно из основных свойств ЛП - если в задаче ЛП существует оптимальное решение, то по крайней мере одна из вершин допустимой области представляет собой оптимальное решение. Несмотря на то, что допустимая область задачи ЛП состоит из бесконечного числа точек, оптимальное решение всегда можно найти путем целенаправленного перебора конечного числа ее вершин. Рассматриваемый далее симплекс-метод решения задачи ЛП основывается на этом фундаментальном свойстве.

7 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Решение задачи ЛП в MS Excel Одной из встроенных функций редактора электронных таблиц MS Excel (необходимо отметить галочку во время установки MS Office) является "Поиск решения". Этот пакет позволяет быстро решать задачи линейного и нелинейного программирования.

8 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Задача ЛП в стандартной форме Задача ЛП в стандартной форме с m ограничениями и n переменными имеет следующий вид: W = c1x1 + c2x2 + ... + cnxn  min (max) при ограничениях a11x1 + a12x2 + ... + a1nxn = b1; a21x1 + a22x2 + ... + a2nxn = b2; ... am1x1 + am2x2 + ... + amnxn = bm; x10; x20;...; xn0 b10; b20;...; bm0 В матричной форме W = cx  min (max) при ограничениях Ax = b; x0; b0, где A - матрица размерности m*n, x - вектор-столбец переменных размерности n*1, b - вектор-столбец ресурсов размерности m*1, с - вектор-строка оценок задачи ЛП 1*n.

9 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Преобразование неравенств Ограничения в виде неравенств можно преобразовать в равенства при помощи введения так называемых остаточных или избыточных переменных. Уравнение из предыдущего примера 4x1 + 1,5x2  24 можно преобразовать в равенство при помощи остаточной неотрицательной переменной 4x1 + 1,5x2 + x3 = 24. Переменная x3 неотрицательна и соответствует разности правой и левой частей неравенства. Аналогично x1  2 можно преобразовать путем введения избыточной переменной x4: x1 - x4 = 2.

10 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Преобр-е неогр. по знаку перем-х Преобразование неограниченных по знаку переменных Переменные, принимающие как положительные, так и отрицательные значения, следует заменять разностью двух неотрицательных: x = x+ - x-; x+0; x-  0. Пример. 3x1+4x2+5x3+4x4  max 2x1+x2+3x3+5x4  5 5x1+3x2+x3+2x4  20 4x1+2x2+3x3+x4 = 15 x10; x20; x3 0; x4 =  знак -3x1-4x2+5x3-4x4  min 2x1+x2-3x3+5x4-x5 = 5 5x1+3x2-x3+2x4+x6 = 20 4x1+2x2-3x3+x4 = 15 x10; x20; x30; x4 =  знак; x4 =x8-x7 -3x1-4x2+5x3-4x8+4x7 min 2x1+x2-3x3+5x8-5x7-x5 = 5 5x1+3x2-x3+2x8-2x7+x6 = 20 4x1+2x2-3x3+x8-x7= 15 x1,x2,x3,x5,x6,x7,x80; x4=x8 -3x1-4x2+5x3-4x4+4x7 min 2x1+x2-3x3+5x4-5x7-x5 = 5 5x1+3x2-x3+2x4-2x7+x6 = 20 4x1+2x2-3x3+x4-x7= 15 x1,x2,x3,x4,x5,x6,x70; x8 заменили на x4

11 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Симплекс-метод ЛП Симплекс-метод представляет собой итеративную процедуру решения задач ЛП, записанных в стандартной форме, система уравнений в которой и с помощью элементарных операций над матрицами приведена к каноническому виду: x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. Переменные x1, x2,...,xm, входящие с единичными коэффициентами только в одно уравнение системы и с нулевыми - в остальные, называются базисными. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Остальные n-m переменных (xm+1, ...,xn) называются небазисными переменными. Для приведения системы к каноническому виду можно использовать два типа элементарных операций над строками: Умножение любого уравнения системы на положительное или отрицательное число. Прибавление к любому уравнению другого уравнения системы, умноженного на положительное или отрицательное число.

12 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Симплекс-метод ЛП Запись задачи в виде уравнений x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. тождественна записи в виде матриц 1 0 .. 0 a1,m+1 .. a1s .. a1n x1 b1 0 1 .. 0 a2,m+1 .. a2s .. a2n x2 = b2 . . .. . . .. . .. . .. .. 0 0 .. 1 am,m+1 .. ams .. amn xn bm

13 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Алгоритм симплекс-метода 1. Выбираем начальное допустимое базисное решение. Базисным решением называется решение, полученное при нулевых значениях небазисных переменных, т.е. xi=0, i=m+1,...,n. Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных неотрицательны, т.е. xj = bj  0, j=1,2,...,m. В этом случае целевая функция примет следующий вид: W=cbxb=c1b1+c2b2+...+cmbm. Заполняем первоначальную таблицу симплекс - метода:

14 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Алгоритм симплекс-метода 2. Вычисляем вектор относительных оценок c при помощи правила скалярного произведения сj = сj - cbSj, где сb - вектор оценок базисных переменных; Sj - j-тый столбец из коэффициентов aij в канонической системе, соответствующей рассматриваемому базису. Дополняем первоначальную таблицу c - строкой.

15 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Алгоритм симплекс-метода 3. Если все оценки cj  0 (cj  0), i=1,...,n, то текущее допускаемое решение - максимальное (минимальное). Решение найдено. 4. В противном случае в базис необходимо ввести небазисную переменную xr с наибольшим значением cj вместо одной из базисных переменных (см. таблицу).

16 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Алгоритм симплекс-метода 5. При помощи правила минимального отношения min(bi/air) определяем переменную xp, выводимую из базиса. Если коэффициент air отрицателен, то bi/air=. В результате пересечение столбца, где находится вводимая небазисная переменная xr, и строки, где находится выводимая базисная переменная xp, определит положение ведущего элемента таблицы. 6. Применяем элементарные преобразования для получения нового допускаемого базового решения и новой таблицы. В результате ведущий элемент должен равняться 1, а остальные элементы столбца ведущего элемента принять нулевое значение. 7. Вычисляем новые относительные оценки с использованием правила скалярного преобразования и переходим к шагу 4.

17 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Пример реш-я симплекс-методом Пример – Оптимизация размещения побочного производства лесничества 3. Целевая функция: 5000 x1 + 2500 x2  max, 4. Ограничения: 4.1. По использованию земли, га: 4 x1 + 1,5 x2  24 4.2. По бюджету, руб.: 1200 x1 + 150 x2  6000 4.3. По трудовым ресурсам, ч: 20 x1 + 20 x2  200 4.4. Обязательства по контракту, шт.: x1  2 4.5. Областные ограничения: x1  0, x2  0 Приведем задачу к стандартной форме: 4 x1 + 1,5 x2 +x3= 24 1200 x1 + 150 x2 +x4= 6000 20 x1 + 20 x2 +x5= 200 x1 – x6= 2 x1 ... x6  0 Первые три уравнения имеют соответственно по базисной переменной x3, x4, x5, однако в четвертом она отсутствует ввиду того, что при переменной x6 стоит отрицательный единичный коэффициент. Для приведения системы к каноническому виду используем метод искусственных переменных. x1 – x6+x7= 2, ввели искусственную переменную x7.

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


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

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



Неравенства

Линейные неравенства – это неравенства вида ∑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 некоторую стратегию, т.е. пользуется при выборе решения чистой стратегией. При этом решение игры будет в чистых стратегиях. Поскольку интересы игроков противоположны, то первый игрок стремится максимизировать свой выигрыш, а второй игрок, наоборот, минимизировать свой проигрыш. Решение игры состоит в определении наилучшей стратегии каждым игроком. Выбор наилучшей стратегии одним игроком проводится при полном отсутствии информации о принимаемом решении вторым игроком.