Презентация Классификация оптимизационных задач онлайн

Содержание слайда: КЛАССИФИКАЦИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ Лекция 1

Содержание слайда: Пахомова Наталья Алексеевна Пахомова Наталья Алексеевна

Содержание слайда: История возникновения 1885г. Фредерик Тейлор – вывод о возможности применения научного анализа в сфере производства.

Содержание слайда: Методы оптимальных решений рассматривают следующие задачи: Задачи управления запасами Задачи распределения ресурсов Задачи ремонта и замены оборудования Задачи массового обслуживания Задача составления расписаний движения транспорта (грузового, пассажирского, смешанного). Задачи сетевого планирования или управления Задачи выбора оптимального маршрута

Содержание слайда: Оптимальное математическое программирование ЦЕЛЬ (критерий, целевая функция) F(x1;x2;…;xn) → экстремум ОГРАНИЧЕНИЯ (условия, требования) Gj(x1;x2;…;xn) [>;≥;=;<;≤] bj где j = 1,2,…,m ТРЕБОВАНИЯ К ПЕРЕМЕННЫМ xi≥0 не отрицательность xi – целые, xi – выражены через параметры, xi – случайные и т.д.

Содержание слайда: Полное решение поставленной задачи не найдено, но получены существенные результаты во множестве частных случаев Если функции F и Gj линейные, то в этом случае задача носит название задачи линейного программирования. Если F дробно-линейная, а Gj – линейные, то это задача дробно-линейного программирования. Если F квадратичная функция, а Gj линейные, то это задача квадратичного программирования. Если xi – целые, то это задача целочисленного программирования. Если xi – выражены через параметры, то это задача параметрического программирования. Если хотя бы одна из xi - случайная величина, то это задача стохастического программирования. Если результат многоэтапного решения зависит от оптимального выбора на каждом этапе, то это задача динамического программирования.

Содержание слайда: История линейного программирования КАНТОРОВИЧ Леонид Витальевич (1912-86), российский математик и экономист, академик АН СССР. Положил начало линейному программированию. Один из создателей теории оптимального планирования и управления народным хозяйством, теории оптимального использования сырьевых ресурсов.

Содержание слайда: Задача линейного программирования имеет следующий вид 1) Целевая функция Z= → экстремум (оптимум) 2) Ограничения [>≥=<≤] bj , где j=1,2,…,m 3) Требования к переменным xi≥0 (не отрицательность).

Содержание слайда: СПОСОБЫ РЕШЕНИЯ ЛИНЕЙНЫХ ЗАДАЧ Графический способ Средствами Excel (Поиск решения) Средствами MathCAD (функция Minimize) Способ Жордановых исключений

Содержание слайда: Пример:

Содержание слайда: Графический способ

Содержание слайда: Найдем графическое решение неравенств

Содержание слайда: Графиком целевой функции является семейство параллельных прямых

Содержание слайда: Точка входа – точка минимума

Содержание слайда: Точка выхода – точка максимума

Содержание слайда: СПОСОБ ЖОРДАНОВЫХ ИСКЛЮЧЕНИЙ (СИМПЛЕКСНЫЙ) Симплексный метод требует преобразования имеющейся модели к каноническому виду. каждое неравенство должно быть приведено к виду ≥0, уравнение – приравнено к 0. целевая функция должна стремиться к минимуму.

Содержание слайда: Последовательное преобразование Жордановой таблицы Задача считается решенной, если коэффициенты при переменных в целевой строке не отрицательны, и при этом все свободные члены дополнительных переменных также не отрицательны. Все преобразования таблиц основаны на так называемых разрешающих элементах.

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

Содержание слайда:

Содержание слайда:

Содержание слайда: Меняем заголовки строки и столбца, соответствующие R

Содержание слайда: На место R ставим обратную величину

Содержание слайда: Разрешающий столбец делим на R

Содержание слайда: Разрешающую строку делим на число, противоположное R

Содержание слайда: Остальные элементы находим по правилу прямоугольника

Содержание слайда: Основная форма представления задачи линейного программирования Исходная форма Каноническая форма Z=x1+x2→min Z=x1+x2→min 3x1+x2≥8 y1=3x1+x2-8 x1-4x2≤19 y2=-x1- 4x2 -19 2x1+3x2≤28 y3=-2x1+3x2-28 x1-x2≤4 y4=-x1- x2 - 4 x1+3x2≥8 y5= x1+3x2-8

Содержание слайда: Основная форма представления задачи линейного программирования Исходная форма Каноническая форма Z=x1+x2→min Z=x1+x2→min 3x1+x2≥8 y13x1 + x2- 8 ≥0 x1-4x2≤19 y2=-x1- 4x2 -19 ≤0 2x1+3x2≤28 y3-2x1+3x2-28 ≤0 x1-x2≤4 y4=-x1 - x2 - 4 ≤0 x1+3x2≥8 y5= x1+3x2 - 8 ≥0

Содержание слайда: Основная форма представления задачи линейного программирования Исходная форма Каноническая форма Z=x1+x2→min Z=x1+x2→min 3x1+x2≥8 y1 3x1+ x2-8 ≥0 x1-4x2≤19 y2 -x1+4x2+19 ≥0 2x1+3x2≤28 y3=-2x1-3x2+28 ≥0 x1-x2≤4 y4= -x1+x2+4 ≥0 x1+3x2≥8 y5= x1+3x2-8 ≥0

Содержание слайда: Исходная форма Каноническая форма Z=x1+x2→min Z=x1+x2→min 3x1+x2≥8 y1=3x1+x2 ─ 8 x1-4x2≤19 y2= ─ x1+4x2+19 2x1+3x2≤28 y3= ─ 2x1 ─ 3x2+28 x1-x2≤4 y4= ─ x1+x2+4 x1+3x2≥8 y5= x1+3x2 ─ 8

Содержание слайда: Все коэффициенты канонической формы заносят в Жорданову таблицу В заголовках столбцов этой таблицы ставят имена определяемых переменных: х1 , х2, а также заголовок столбца свободных членов всех ограничений или, его еще называют столбцом единиц. В заголовках строк таблицы записывают имена введенных, дополнительных переменных: y1, y2,y3, y4, y5 и имя целевой функции Z. При заполнении таблицы обязательно учитывать знаки каждого коэффициента.

Содержание слайда: Для нашей задачи таблица будет выглядеть следующим образом

Содержание слайда: Для нашей задачи таблица будет выглядеть следующим образом

Содержание слайда: Для нашей задачи таблица будет выглядеть следующим образом

Содержание слайда: Для нашей задачи таблица будет выглядеть следующим образом

Содержание слайда: Для нашей задачи таблица будет выглядеть следующим образом

Содержание слайда: Для нашей задачи таблица будет выглядеть следующим образом

Содержание слайда: Для нашей задачи таблица будет выглядеть следующим образом

Содержание слайда: Для нашей задачи таблица будет выглядеть следующим образом

Содержание слайда: Рассмотрим первую таблицу нашей задачи

Содержание слайда: Меняем заголовки

Содержание слайда: На место разрешающего элемента пишем обратный

Содержание слайда: Столбец делим на разрешающий элемент

Содержание слайда: Сроку делим на (– R)

Содержание слайда: Остальные элементы находим по правилу прямоугольника

Содержание слайда: Остальные элементы находим по правилу прямоугольника

Содержание слайда: Остальные элементы находим по правилу прямоугольника

Содержание слайда: Остальные элементы находим по правилу прямоугольника

Содержание слайда: Остальные элементы находим по правилу прямоугольника

Содержание слайда: Остальные элементы находим по правилу прямоугольника

Содержание слайда: Остальные элементы находим по правилу прямоугольника

Содержание слайда: Остальные элементы находим по правилу прямоугольника

Содержание слайда: Остальные элементы находим по правилу прямоугольника

Содержание слайда: Вторая таблица:

Содержание слайда: Наибольшее из всех возможных отношений соответствующих свободных членов к отрицательным элементам такого столбца -8/3

Содержание слайда: Наибольшее из всех возможных отношений соответствующих свободных членов к отрицательным элементам такого столбца -51/13, -8/3

Содержание слайда: Наибольшее из всех возможных отношений соответствующих свободных членов к отрицательным элементам такого столбца -12/4, -51/13, -8/3

Содержание слайда: Наибольшее из всех возможных отношений соответствующих свободных членов к отрицательным элементам такого столбца -16/8, -12/4, -51/13, -8/3; наибольшее число -16/8=-2

Содержание слайда: Разрешающий элемент (– 8 )

Содержание слайда: Третья таблица:

Содержание слайда: Третья таблица: В последней таблице в столбце свободных членов нет отрицательных элементов, поэтому она демонстрирует так называемое «допустимое» решение. Кроме того, в последней таблице в строке целевой функции также нет отрицательных элементов, значит, имеющееся решение есть не только допустимое, но и оптимальное. Заметив этот факт, мы не стали заполнять все остальные клетки таблицы, т.к. ответ уже получен.

Содержание слайда: Третья таблица: В последней таблице в столбце свободных членов нет отрицательных элементов, поэтому она демонстрирует так называемое «допустимое» решение. Кроме того, в последней таблице в строке целевой функции также нет отрицательных элементов, значит, имеющееся решение есть не только допустимое, но и оптимальное. Заметив этот факт, мы не стали заполнять все остальные клетки таблицы, т.к. ответ уже получен.

Содержание слайда: Третья таблица:

Содержание слайда: Третья таблица:

Содержание слайда: Третья таблица: В последней таблице в столбце свободных членов нет отрицательных элементов, поэтому она демонстрирует так называемое «допустимое» решение. Кроме того, в последней таблице в строке целевой функции также нет отрицательных элементов, значит, имеющееся решение есть не только допустимое, но и оптимальное.

Содержание слайда: Оформление результата решения Результат решения определяют из последней таблицы следующим образом: переменная, стоящая в заголовке строки равна свободному члену этой строки, переменная в заголовке столбца принимается равной нулю. Таким образом, по нашей задаче решением будет следующий результат: X1=2, X2=2, Y1=0, Y2=25, Y3=18, Y4=4, Y5=0, Zmin=4.

Содержание слайда: Проверка: 3*2+2=8, 8=8, различия левой и правой частей нет, значит Y1=0, и в последней таблице Y1 стоит в заголовке столбца. 2-4*2=-6<19, Y2=25, но то же самое и по последней таблице. 2*2+3*2=10<28 на 18, следовательно, Y3=18, так же и в таблице. 2-2=0<4 на 4, Y4=4, что подтверждается таблицей. 2+3*2=8, 8=8, Y5=0. Наконец, z=2+2=4, но и по таблице тот же результат. Таким образом, полученное решение удовлетворяет всем ограничениям задачи и обеспечивает минимум целевой функции равный 4.

Содержание слайда: Решение задач линейного программирования в Excel В настоящее время наиболее мощным средством решения таких задач на компьютере является пакет Excel с его надстройкой «Поиск решения». Для решения задачи в Excel необходимо правильно поместить математическую модель по ячейкам электронной таблицы при этом целесообразно придерживаться примерно следующей схемы заполнения ячеек

Содержание слайда: Установка Поиска решения

Содержание слайда: Установка Поиска решения

Содержание слайда: Установка Поиска решения

Содержание слайда:

Содержание слайда: Окно Поиска решения

Содержание слайда: Результат В ячейке D4 имеем минимальное значение целевой функции равное 4. Оптимальные значения переменных в ячейках B3 и C3 равны по 2. Все ограничения выполняются. В частности, 2-ое ограничение: по его формуле результат равен –6, а его объем равен 19, следовательно, левая часть меньше правой на 25, но именно такой же результат был получен и предыдущим способом.