Портал готовых презентаций линейное программирование. Презентация на тему "задачи линейного программирования"
Нажав на кнопку "Скачать архив", вы скачаете нужный вам файл совершенно бесплатно.
Перед скачиванием данного файла вспомните о тех хороших рефератах, контрольных, курсовых, дипломных работах, статьях и других документах, которые лежат невостребованными в вашем компьютере. Это ваш труд, он должен участвовать в развитии общества и приносить пользу людям. Найдите эти работы и отправьте в базу знаний.
Мы и все студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будем вам очень благодарны.
Чтобы скачать архив с документом, в поле, расположенное ниже, впишите пятизначное число и нажмите кнопку "Скачать архив"
Подобные документы
-
Слайд 14
Допустим, что будет изготовлено изделий вида А, -изделий вида В и -изделий вида С. Тогда для производства такого количества изделий потребуется затратить станко-часов фрезерного оборудования. Так как общий фонд рабочего времени станков данного типа не может превышать 120, то должно выполняться неравенство
Слайд 15
Рассуждая аналогично, можно составить систему ограничений
Слайд 16
Теперь составим целевую функцию. Прибыль от реализации изделий вида А составит 10 , от реализации -изделий вида В -14 и от реализации -изделий вида С-12 Общая прибыль от реализации всех изделий составит
Слайд 17
Таким образом, приходим к следующей ЗЛП: Требуется среди всех неотрицательных решений системы неравенств найти такое, при котором целевая функция принимает максимальное значение.
Слайд 18
Пример 2
Продукцией гормолокозавода являются молоко, кефир и сметана, расфасованные в тару. На производство 1 т молока, кефира и сметаны требуется соответственно1010,1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино-часов. На расфасовке 1 т сметаны заняты специальные автоматы в течение 3,25 часов.
Слайд 19
Всего для производства цельномолочной продукции завод может использовать 136000 кг молока. Основное оборудование может быть занято в течение 21,4 машино-часов, а автоматы по расфасовке сметаны – в течение 16,25 часов. Прибыль от реализации 1 т молока, кефира и сметаны соответственно равна 30, 22 и 136 руб. Завод должен ежедневно производить не менее 100 т молока, расфасованного в бутылки. На производство другой продукции нет ограничений.
Слайд 20
Требуется определить, какую продукцию и в каком количестве следует ежедневно изготовлять заводу, чтобы прибыль от ее реализации была максимальной. Составить математическую модель задачи.
Слайд 21
Решение
Пусть завод будет производить т молока, т кефира и т сметаны. Тогда ему необходимо кг молока. Так как завод может использовать ежедневно не более 136000 кг молока, то должно выполняться неравенство
Слайд 22
Ограничения на время по расфасовке молока и кефира и по расфасовке сметаны. Так как ежедневно должно вырабатываться не менее100 т молока, то. По экономическому смыслу
Слайд 23
Общая прибыль от реализации всей продукции равна руб. Таким образом, приходим к следующей задаче: при ограничениях Так как целевая функция линейная и ограничения заданы системой неравенств, то эта задача является ЗЛП.
Слайд 24
Задача о смесях.
Имеетсядва вида продукции, содержащие питательные вещества (жиры, белки и т.д.)
Слайд 25
Таблица
-
Слайд 26
Решение
Общая стоимость рациона при ограничениях с учетом необходимого минимума питательных веществ
Слайд 27
Математическая постановка задачи: составить дневной рацион, удовлетворяющий системе ограничений и минимизирующий целевую функцию. В общем виде к группе задач о смесях относятся задачи по отысканию наиболее дешевого набора из определенных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Полученные смеси должны иметь в своем составе nразличных компонентов в определенных количествах, а сами компоненты являются составными частями m исходных материалов.
Слайд 28
Введем обозначения: -количество j-го материала, входящего в смесь; -цена материала j-го вида; -это минимально необходимое содержание i-го компонента в смеси. Коэффициенты показывают удельный вес i-го компонента в единице j-го материала
Слайд 29
Экономико-математическая модель задачи.
Целевая функция представляет собой суммарную стоимость смеси, а функциональные ограничения являются ограничениями по содержанию компонентов в смеси: смесь должна содержать компоненты в объемах, не менее указанных.
Слайд 30
Задача о раскрое
На швейной фабрике ткань может быть раскроена несколькими способами для изготовления нужных деталей швейных изделий. Пусть при j-ом варианте раскроя изготавливается деталей i-го вида, а величина отходов при данном варианте раскроя равна Зная, что деталей i-го вида следует изготовлять штук, требуется раскроить ткань так, чтобы было получено необходимое количество деталей каждого вида при минимальных общих отходах. Составить математическую модель задачи.
Слайд 31
Решение. Предположим, что по j-ому варианту раскраивается сотен ткани. Поскольку при раскрое ткани по j-ому варианту получается деталей i-го вида, по всем вариантам раскроя из используемых тканей будет получено Общая величина отходов по всем вариантам раскроя составит
Слайд 35
Основная задача ЛП
Опр.4. Основной, или канонической ЗЛП называется задача, состоящая в определении значения целевой функции при условии, что система ограничений представлена в виде системы уравнений:
Слайд 36
Если требуется для удобства или по смыслу задачи перейти от одной формы записи к другой, то поступают следующим образом. Если требуется найти минимум функции, то можно перейти к нахождению максимума, умножив целевую функции на (-1). Ограничение –неравенство вида можно преобразовать в равенство добавлением к его левой части неотрицательной дополнительной переменной, а ограничение неравенство вида - в ограничение- равенство вычитанием из его левой части дополнительной неотрицательной переменной.
Слайд 41
Опорный план называется невырожденным, если он содержит m положительных компонент. В противном случае он называется вырожденным. План, при котором целевая функция ЗЛП принимает свое максимальное (минимальное) значение, называется оптимальным.
Посмотреть все слайды
Задачи оптимизации. Ограничения на допустимое множество. Классическая задача оптимизации. Функция Лагранжа. Линейное программирование: формулировка задач и их графическое решение. Алгебраический метод решения задач. Симплекс-метод, симплекс-таблица.
реферат , добавлен 29.09.2008
Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.
курсовая работа , добавлен 27.03.2011
Общие задачи линейного программирования. Описание алгоритма симплекс-метода, записанного в канонической форме с односторонними ограничениями. Алгоритм построения начального опорного плана для решения задачи. Расширенный алгоритм искусственного базиса.
курсовая работа , добавлен 24.10.2012
Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.
реферат , добавлен 21.08.2008
Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.
курсовая работа , добавлен 05.01.2015
Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
курсовая работа , добавлен 11.02.2011
Понятие теории оптимизации экономических задач. Сущность симплекс-метода, двойственности в линейном программировании. Элементы теории игр и принятия решений, решение транспортной задачи. Особенности сетевого планирования и матричное задание графов.
Описание презентации по отдельным слайдам:
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; x10; x20;...; xn0 b10; b20;...; bm0 В матричной форме W = cx min (max) при ограничениях Ax = b; x0; b0, где 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 x10; x20; 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 x10; x20; x30; 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,x80; 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,x70; 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 классе. ... материал предназначен для студентов повышенного уровня. в программе рассмотрен алгоритм составления базисного и опорного плпна разными методами и нахождение оптимального решения... Рабочая тетрадь к уроку математики на тему «Задачи линейного программирования» разработана мною для одноимённого урока математики (повышенный уровень). может быть использована как на уроке, семинарско... Линейное программирование▪ Задача линейного программирования – 3 слайд. Слайд 2
Методы линейного программирования используют в прогнозных расчетах, при планировании и организации производственных процессов.
Линейное программирование – это область математики, в которой изучаются методы исследования и отыскания экстремальных значений некоторой линейной функции, на аргументы которой наложены линейные ограничения. Слайд 3
Такая линейная функция называется целевой, а набор количественных соотношений между переменными, выражающих определенные требования экономической задачи в виде уравнений или неравенств, называется системой ограничений.
Слово программирование введено в связи с тем, что неизвестные переменные обычно определяют программу или план работы некоторого субъекта. Слайд 4
Совокупность соотношений, содержащих целевую функцию и ограничения на ее аргументы, называется математической моделью задачи оптимизации.
ЗЛП записывается в общем виде так:
при ограничениях Слайд 5
Здесь -неизвестные, -заданные постоянные величины.Ограничения могут быть заданы уравнениями.
Наиболее часто встречаются задачи в виде: имеется ресурсов при ограничениях. Нужно определить объемы этих ресурсов, при которых целевая функция будет достигать максимума (минимума), т. е. найти оптимальное распределение ограниченных ресурсов. При этом имеются естественные ограничения >0. Слайд 6
При этом экстремум целевой функции ищется на допустимом множестве решений, определяемом системой ограничений, причем все или некоторые неравенства в системе ограничений могут быть записаны в виде уравнений. Слайд 7
В краткой записи ЗЛП имеет вид:
при ограничениях Слайд 8
Для составления математической модели ЗЛП необходимо:
1)обозначить переменные;
2)составить целевую функцию;
3)записать систему ограничений в соответствии с целью задачи;
4)записать систему ограничений с учетом имеющихся в условии задачи показателей.
Если все ограничения задачи заданы уравнениями, то модель такого вида называется канонической. Если хоть одно из ограничений дано неравенством, то модель неканоническая. Слайд 9
задача оптимального распределения ресурсов при планировании выпуска продукции на предприятии (задача об ассортименте);
задача на максимум выпуска продукции при заданном ассортименте;
задача о смесях (рационе, диете и т.д.);
транспортная задача;
задача о рациональном использовании имеющихся мощностей;
задача о назначениях. Слайд 10
Предположим, что предприятие выпускает различных изделий. Для их производства требуется различных видов ресурсов (сырья, рабочего и машинного времени, вспомогательных материалов). Эти ресурсы ограничены и составляют в планируемый период условных единиц. Известны также технологические коэффициенты, которые указывают, сколько единиц i-го ресурса требуется для производства изделия j-го вида. Пусть прибыль, получаемая предприятием при реализации единицы изделия j-го вида, равна. В планируемый период все показатели предполагаются постоянными. Слайд 11
Требуется составить такой план выпуска продукции, при реализации которого прибыль предприятия была бы наибольшей.
Экономико-математическая модель задачи Слайд 12
Целевая функция представляет собой суммарную прибыль от реализации выпускаемой продукции всех видов. В данной модели задачи оптимизация возможна за счет выбора наиболее выгодных видов продукции. Ограничения означают, что для любого из ресурсов его суммарный расход на производство всех видов продукции не превосходит его запасы. Слайд 13
Подписи к слайдам:
По теме: методические разработки, презентации и конспекты
▪ Геометрический метод решения ЗЛП – 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;
Определить оптимальный состав ОТК,
при котором общие затраты на контроль будут минимальны.
Линейное программирование
Примеры задач, которые сводятся к ЗПЛ.
1.Задача оптимального распределения ресурсов.
Примеры
