Рабочие листы
к вашим урокам
Скачать
1 слайд
“Nапрако ехати-коня теряти, Nалеко ехати-женату быть, прямо ехати- убиту быть. ”
2 слайд
издержки поиска
перебор вариантов
выигрыш
опыт и интуиция
оптимального решения.
3 слайд
Тема урока:
Решение задач линейного программирования – симплекс-методом.
обучающиеся должны уметь:
выделять задачи линейного программирования из ряда предложенных задач;
владеть приемами постановки задач организационного управления;
на основе описательных задач строить математические модели;
проводить численные исследования математических моделей;
проводить анализ результатов вычислений;
выбрать наиболее эффективное управляющее решение
4 слайд
минимум затрат
максимум результата
Леонид Витальевич Канторович
(1912—1986)
«Метод линейного программирования».
5 слайд
поиск оптимума
Трудовые затраты
Общественные
потребности
Стоимостные
затраты
Полезности продукта
для потребителей
6 слайд
Математическое программирование — область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.
Математическая модель задачи — это отражение оригинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математического программирования включает:
1) совокупность неизвестных величин;
2) целевую функцию.
7 слайд
Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит в следующем:
1) умение находить начальный опорный план;
2) наличие признака оптимальности опорного плана;
3) умение переходить к нехудшему опорному плану.
8 слайд
Теорема. Если в оптимальном плане М-задачи все переменные искусственные, то план является оптимальным планом исходной задачи
Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.
Признаки оптимальности
Теорема. Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки неотрицательны, то такой план оптимален.
Теорема. Если исходная задача решается на минимум и для некоторого опорного плана все оценки неположительны, то такой план оптимален.
9 слайд
1.2 Общий вид задач линейного программирования
В общем случае задача линейного программирования может быть записана в таком виде(формула 1.1)
Z(X)=c1x1+c2x2+…+cnxn→ max(min), (1.1)
a11x1+a12x2+…+a1nxn=b1,
…………………………
ai1x1+ai2x2+…+ainxn=bi,
a(i+1)1x1+a(i+1)2x2+…+a(i+1)nxn≤bi+1(1.2)
………………………..
am1x1+am2x2+…+amnxn≤bm
xj≥0, j=1,2,…,t; t≤n.(1.3)
10 слайд
Каноническая задача линейного программирования в матричной записи имеет вид (формулы 1.5, 1.6):
Z(X)=CX → max(min),(1.5)
AX=A0, Y≥θ,
A= , X= , A0= (1.6)
Здесь:
А — матрица коэффициентов системы уравнений
Х — матрица-столбец переменных задачи
Ао — матрица-столбец правых частей системы ограничений
11 слайд
Задача. В цехе предприятия решено установить дополнительное оборудование,
для размещения которого выделено S кв.м площади. На приобретение оборудования
предприятие может израсходовать A руб. при этом оно может купить оборудование n
видов. Единица оборудования i-го вида стоит ai руб. Приобретение оборудования i-го
вида позволяет увеличить выпуск продукции в смену на bi ед. Для установки одного
оборудования i-го вида требуется ci кв.м. площади. Определить сколько единиц
оборудования каждого вида необходимо закупить, чтобы максимально увеличить
выпуск продукции.
Построение математической модели.
Предположим, что предприятие закупит оборудование i-го вида в количестве xi шт.
Целевая функция задачи описывает увеличение объема выпуска продукции, которое
должно быть максимальным, т.е.
F = b1 x1 + b2 x2 + … + bn xn → max.
Запишем теперь ограничения задачи. Первое ограничение относится к стоимости
оборудования и выделенной для этой цели денежных средств:
a1 x1 + a2 x2 + … + an xn ≤ A.
Второе ограничение относится к размеру площади, которое может быть выделено под
оборудование:
c1 x1 + c2 x2 + … + cn xn ≤ S .
12 слайд
Тема урока:
Решение задач линейного программирования – симплекс-методом.
обучающиеся должны уметь:
выделять задачи линейного программирования из ряда предложенных задач;
решать простейшие задачи линейного программирования.
13 слайд
Фирма набирает штат сотрудников и располагает 4 группами различных должностей, а в каждой группе 5, 3, 6, 4 вакансий. Кандидаты на должность проходят тестирование, по результатам которого их разделяют на 3 группы, по 7, 5, 6 человек в каждой группе. Для каждого кандидата отобранных в i-ю группу требуются определенные затраты cij, долл. на обучение для занятия должности в j-ой группе
Необходимо распределить кандидатов на должности, затратив минимальные средства на их обучение.
14 слайд
Фирма набирает штат сотрудников и располагает 4
группами различных должностей, а в каждой
группе 15, 8, 11, 10 вакансий. Кандидаты на
должность проходят тестирование, по результатам
которого их разделяют на 3 группы, по 23, 9, 12
человек в каждой группе. Для каждого кандидата
отобранных в i-ю группу требуются определенные
затраты cij, долл. на обучение для заняти должности
в j-ой группе
Необходимо распределить кандидатов на
должности, затратив минимальные средства на их обучение.
15 слайд
Для перевозки пассажиров по трем маршрутам аэропорт
располагает тремя типами самолетов. Вместимость
самолета i-го типа, i = 1, 2, 3, равна 150, 200 и 300
пассажиров соответственно, а потребность в перевозке
пассажиров по j-му маршруту, j = 1, 2, 3, за сезон
составляет соответственно 5600, 7000 и 6500 человек.
Эксплуатационные расходы самолета i-го типа на j-ом
маршруте равны cij денежных единиц и представлены
матрицей.
Парк самолетов каждого типа составляет 35, 38 и 25
единиц соответственно.
Определить сколько самолетов каждого типа
использовать на каждом из маршрутов, чтобы затраты на
перевозку пассажиров были минимальными.
16 слайд
Требуется распределить самолеты трех типов по
авиалиниям так, чтобы при минимальных
суммарных эксплуатационных расходах
перевезти по каждой из четырех авиалиний
соответственно не менее 300, 200, 900 и 600 ед.
груза.
Матрица эксплуатационных расходов на один
рейс по каждому маршруту, долл. имеет вид
17 слайд
Необходимо распределить самолеты трех типов
по четырем авиалиниям так, чтобы при
минимальных суммарных эксплуатационных
расходах перевезти по каждой из четырех
авиалиний соответственно не менее 300, 200,
1000 и 500 ед. груза.
Матрица эксплуатационных расходов на один
рейс по каждому маршруту, долл. имеет вид
.
18 слайд
Мясокомбинат имеет в своем составе четыре
завода, на каждом из которых может изготавливаться три
вида колбасных изделий. Мощности каждого из заводов
соответственно равны 320, 280, 270 и 350 т/сут.
Ежедневные потребности в колбасных изделиях каждого
вида также известны и соответственно равны 450, 370 и
400 т. Зная себестоимость 1 т каждого вида колбас на
каждом заводе, которые определяются матрицей
Найти такое распределение выпуска колбасных изделий
между заводами, при котором себестоимость
изготавливаемой продукции является минимальной.
Рабочие листы
к вашим урокам
Скачать
6 667 985 материалов в базе
Настоящий материал опубликован пользователем Коренькова Галина Николаевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материалВаша скидка на курсы
40%Курс профессиональной переподготовки
500/1000 ч.
Курс повышения квалификации
72 ч.
Курс повышения квалификации
72/108 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Мини-курс
6 ч.
Мини-курс
4 ч.
Мини-курс
3 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.