Детерминированные модели

Сентябрь 6, 2022

Главная
Алгебра
Детерминированные модели

Содержание

2. 2. Классические задачи линейного программирования Целевая функция и ограничения линейны
3. В зависимости от вида целевой функции f и ограничений можно выделить несколько типов задач линейного программирования:
4. Задача оптимального использования ресурсов В распоряжении предприятия имеется определённое количество ресурсов нескольких видов. Предприятие может выпускать
7. Задача о составлении рациона (технологическая задача) Необходимо составить такой дневной рацион, имеющий минимальную стоимость, в котором
8. Тогда модель задачи будет иметь вид: f(x) = c1 x1 + c2x2 + … + cn
9. Методы решения задач линейного программирования: 1. Графичский метод 2. Симплекс метод 3. С помощью Excel 4.
10. 2. Специальные задачи линейного программирования 2.1. Траспортная задача
11. :
12. Алгоритм решения транспортной задачи состоит из 4 этапов: Этап 1. Представление данных в форме стандартной таблицы
13. Этап 3. Если полученное распределение ресурсов не является оптимальным, то ресурсы перераспределяются, снижая стоимость траспортировки Этап
14. Методы поиска допустимого распределения: 1. Метод минимальной стоимости 2. Метод северо-западного угла 3. Метод Фогеля
15. Метод Фогеля. Основан на «штрафной стоимости». Штрафная стоимость для каждой строки и столбца — разность между
16. 2.2. Задача о назначениях Особенность задачи о назначениях: 1. Число пунктов производства равно числу пунктов назначения.
17. Алгоритм решения задачи о назначении (Венгерский метод) Этап 1: 1.1. Формализация проблемы в виде транспортной таблицы
18. Этап 2 2.1. Найти строку, содержащую только 1 нулевое значение стоимости, и в клетку, соответствующую данному
19. Этап 3 3.1. Провести минимальное число прямых через строки и столбцы матрицы (не по диагоналям) таким
20. Пример решения задачи о назначениях Некоторая компания имеет 4 сбытовые базы и 4 заказа, которые необходимо
21. 3. Нелинейные модели Нелинейное программирование (НП) представляет собой раздел в теории математического программирования, предметом которого является
23. Алгоритм решения задачи НП Графическим методом Шаг 1. На плоскости х1Ох2 строят область допустимых решений, определенную
24. Пример решения задачи НП графическим методом Решить задачу нелинейного программирования
25. Алгоритм метода множителей Лангранжа Шаг 1.
26. Пример решения задачи методом Лангранжа
27. Пример решения задачи методом Лангранжа
28. Пример решения задачи методом Лангранжа
29. Методы поиска экстремального значения ЦФ Группа 1.Градиентные методы 1) метод градиента 2) метод наискорейшего пуска 3)
30. 5. Динамические модели Динамическое модели — это модели позволяющие решать задачи оптимизации управления динамическими системами, и
32. Основные этапы составления динамической модели
33. Основные этапы составления динамической модели
34. Этапы решения задач динамического программирования
35. Пример задачи динамического программирования
36. Пример задачи динамического программирования
37. Пример задачи динамического программирования
38. Сетевая модель - пример динамической модели в теории управления
39. Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных работ (операций), заданного в форме сети, изображение
40. Пример решения задачи. Для заданного сетевого графика рассчитать все параметры событий и работ, определить критический путь
41. Параметры событий сетевого графика Критический путь образуют следующие события: 0 → 3 → 5 → 6
42. Параметры работ сетевого графика
45. Графики 1. Диаграммы круговые 2. Гистограммы 3. Линейные 4. Лепестковые
46. Схемы блок-схемы
47. Схемы схемы-расположений
48. Схемы схемы-производства
49. Схемы схемы-производства
50. Графы
51. Графы
53. Скачать презентацию

Слайд 2

2. Классические задачи линейного программирования
Целевая функция и ограничения линейны

Слайд 3

В зависимости от вида целевой функции f и ограничений можно выделить

несколько типов задач линейного программирования:
1. общая линейная задача,
2. специальные задачи линейного программирования
2.1. транспортная задача,
2.2. задача о назначениях.

Слайд 4

Задача оптимального использования ресурсов
В распоряжении предприятия имеется определённое количество ресурсов

нескольких видов.
Предприятие может выпускать однотипные изделия нескольких видов.
Задана информация о количестве единиц каждого ресурса, необходимых для производства одного изделия каждого вида, и доходах, получаемых предприятием от единицы каждого вида товаров.
Требуется найти такой план выпуска продукции, при котором общая выручка от реализации будет максимальной.

Слайд 5

Слайд 6

Слайд 7

Задача о составлении рациона (технологическая задача)
Необходимо составить такой дневной рацион,

имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела.
Пусть
x j — число единиц корма j-го вода;
b i — необходимый минимум содержания в рационе питательного
вещества S i,
а ij — число единиц питательного вещества S i, в единице корма j-го вида,
с i — стоимость единицы корма j-го вида

Слайд 8

Тогда модель задачи будет иметь вид:
f(x) = c1 x1 + c2x2

+ … + cn xn → min

a11 x1 + a12 x2 + … + a1n xn ≥ b1

a11 x1 + am2 x2 + … + amn xn ≥ bт

…................................................

xi ≥ 0, i = 1 ÷ n

Слайд 9

Методы решения задач линейного программирования:
1. Графичский метод
2. Симплекс метод
3. С помощью

Excel
4. С помощью Mathcard

Слайд 10

2. Специальные задачи линейного программирования
2.1. Траспортная задача

Слайд 11

:

Слайд 12

Алгоритм решения транспортной задачи состоит из 4 этапов:
Этап 1. Представление данных

в форме стандартной таблицы и поиск любого допустимого распределения ресурсов.
Допустимым называется такое распределение ресурсов, которое позволяет удовлетворить весь спрос в пунктах назначения и вывезти весь запас продуктов из пунктов производства
Этап 2. Проверка полученного распределения ресурсов на оптимальность.

Слайд 13

Этап 3. Если полученное распределение ресурсов не является оптимальным, то ресурсы

перераспределяются, снижая стоимость траспортировки
Этап 4. Повторная проверка оптимальности полученного распределения ресурсов

Слайд 14

Методы поиска допустимого распределения:
1. Метод минимальной стоимости
2. Метод северо-западного угла
3. Метод

Фогеля

Слайд 15

Метод Фогеля.
Основан на «штрафной стоимости». Штрафная стоимость для каждой строки и

столбца — разность между наиболее дешевым маршрутом и следующим за ним с точки зрения критерия минимизации стоимости перевозок.
Суть метода состоит в минимизации штрафов.
Алгоритм метода Фогеля:
1. Вычислить значения штрафной стоимости для каждой строки и столба
2. Выбрать строку или столбец с наибольшим значением штрафной стоимости, и в клетку с наименьшим значением стоимости перевозки для данной строки и столбца помещается наибольшее количество продукта.
3. Провести корректировку итоговых значений по строкам и столбцам таблицы
4. В строках или столбцах, где предложение или спрос равны нулю ставится прочерк
5. Произвести возврат к шагу 1 и пересчитать штрафные стоимости без учета клеток, где указаны перевозки, или клеток, где стоит прочерк

Слайд 16

2.2. Задача о назначениях
Особенность задачи о назначениях:
1. Число пунктов производства

равно числу пунктов назначения. Транспортная таблица имеет форму квадрата
2. В каждом пункте назначения объем потребности равен 1. Величина предложения каждого пункта производства равна 1

Слайд 17

Алгоритм решения задачи о назначении (Венгерский метод)
Этап 1:
1.1. Формализация проблемы в

виде транспортной таблицы по аналогии с решением транспортной задачи
1.2. В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки
1.3. Повторить эту процедуру для столбцов

Слайд 18

Этап 2
2.1. Найти строку, содержащую только 1 нулевое значение стоимости, и

в клетку, соответствующую данному значению, поместить 1 элемент. Если такие строки отсутствуют, допустимо начать с любого нулевого значения стоимости
2.2. Зачеркнуть оставшиеся нулевые значения данного столбца
2.3. Повторять п.2.1 и 2.2 до тех пор, пока продолжение описанной процедуры окажется невозможным

Слайд 19

Этап 3
3.1. Провести минимальное число прямых через строки и столбцы матрицы

(не по диагоналям) таким образом, чтобы они проходили через все нули, содержащиеся в таблице
3.2. Найти наименьший среди элементов, через которые не проходит ни одна из проведенных прямых.
3.3. Вычесть его из всех элементов, через которые не проходят прямые
3.4. Прибавить найденный элемент ко всем элементам таблицы, которые лежат на пересечении проведенных ранее прямых
3.5. Все элементы матрицы, через которые проходит только одна прямая, оставить без изменения

Слайд 20

Пример решения задачи о назначениях
Некоторая компания имеет 4 сбытовые базы и

4 заказа, которые необходимо доставить потребителям. Каждое складское помещение может разместить 1 заказ. Расстояние между складами и потребителями указаны в таблице. Как следует распределить заказы по сбытовым базам, чтобы общая дальность транспортировки была минимальной

Слайд 21

3. Нелинейные модели
Нелинейное программирование (НП) представляет собой раздел в теории

математического программирования, предметом которого является изучение экстремальных задач с нелинейными целевыми функциями и ограничениями.
В инженерной практике под нелинейным программированием обычно понимают методы формализации и решения задач параметрической оптимизации нелинейных целевых (критериальных) функций в условиях нелинейных функциональных ограничений.

Слайд 22

Слайд 23

Алгоритм решения задачи НП Графическим методом
Шаг 1. На плоскости х1Ох2 строят

область допустимых решений, определенную ограничениями. Если область пуста, т. е. ограничения несовместны, то задача не имеет решения. В противном случае переходят к шагу 2.
Шаг 2. Строят линии уровня функции f(x1, x2) = C, где С - некоторая константа. Переход к шагу 3.
Шаг 3. Определяют направление возрастания (при максимизации), убывания (при минимизации) функции f .
Шаг 4. Находят точку области допустимых решений, через которую проходит линии уровня f(x1, x2) = C, с наибольшим (при максимизации), наименьшим (при минимизации) значением С или устанавливают неограниченность функции на области допустимых решений.
Шаг 5. Определяют значения x1, x2 для точки, найденной на шаге 4, и величину функции f в этой точке.

Слайд 24

Пример решения задачи НП графическим методом
Решить задачу нелинейного программирования

Слайд 25

Алгоритм метода множителей Лангранжа
Шаг 1.

Слайд 26

Пример решения задачи методом Лангранжа

Слайд 27

Пример решения задачи методом Лангранжа

Слайд 28

Пример решения задачи методом Лангранжа

Слайд 29

Методы поиска экстремального значения ЦФ
Группа 1.Градиентные методы
1) метод

градиента
2) метод наискорейшего пуска
3) Метод сопряженных градиентов
4) метод проектирования градиента
Группа 2. Методы прямого поиска
1) метод Гаусса-Зайделя;
2) метод вращения координат
3) метод конфигураций
4) метод случайного поиска

Слайд 30

5. Динамические модели
Динамическое модели — это модели позволяющие решать задачи

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

Слайд 31

Слайд 32

Основные этапы составления динамической модели

Слайд 33

Основные этапы составления динамической модели

Слайд 34

Этапы решения задач динамического программирования

Слайд 35

Пример задачи динамического программирования

Слайд 36

Пример задачи динамического программирования

Слайд 37

Пример задачи динамического программирования

Слайд 38

Сетевая модель - пример динамической модели в теории управления

Слайд 39

Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных работ (операций),

заданного в форме сети, изображение которой называется сетевым графиком
Основное назначение Сетевого планирования и управления (СПУ):
- формирование календарного плана реализации комплекса работ;
- принятие эффективных решений в процессе выполнения этого плана

Слайд 40

Пример решения задачи. Для заданного сетевого графика рассчитать все параметры событий

и работ, определить критический путь и его длину

Слайд 41

Параметры событий сетевого графика
Критический путь образуют следующие события:
0 → 3 →

5 → 6 → 9 → 10 → 11.
Его продолжительность составляет 61 день

Слайд 42

Параметры работ сетевого графика

Слайд 43

Слайд 44

Слайд 45

Графики
1. Диаграммы круговые 2. Гистограммы 3. Линейные
4. Лепестковые

Слайд 46

Схемы
блок-схемы

Слайд 47

Схемы
схемы-расположений

Слайд 48

Схемы
схемы-производства

Слайд 49

Схемы
схемы-производства

Слайд 50

Графы

Слайд 51

Детерминированные модели

Содержание

2. Классические задачи линейного программированияЦелевая функция и ограничения линейны

В зависимости от вида целевой функции f и ограничений можно выделить

Задача оптимального использования ресурсов В распоряжении предприятия имеется определённое количество ресурсов

Задача о составлении рациона (технологическая задача)Необходимо составить такой дневной рацион,

Тогда модель задачи будет иметь вид:f(x) = c1 x1 + c2x2

Методы решения задач линейного программирования:1. Графичский метод2. Симплекс метод3. С помощью

2. Специальные задачи линейного программирования2.1. Траспортная задача

:

Алгоритм решения транспортной задачи состоит из 4 этапов:Этап 1. Представление данных

Этап 3. Если полученное распределение ресурсов не является оптимальным, то ресурсы

Методы поиска допустимого распределения:1. Метод минимальной стоимости2. Метод северо-западного угла3. Метод

Метод Фогеля.Основан на «штрафной стоимости». Штрафная стоимость для каждой строки и

2.2. Задача о назначениях Особенность задачи о назначениях:1. Число пунктов производства

Алгоритм решения задачи о назначении (Венгерский метод)Этап 1:1.1. Формализация проблемы в

Этап 22.1. Найти строку, содержащую только 1 нулевое значение стоимости, и

Этап 33.1. Провести минимальное число прямых через строки и столбцы матрицы

Пример решения задачи о назначенияхНекоторая компания имеет 4 сбытовые базы и

3. Нелинейные модели Нелинейное программирование (НП) представляет собой раздел в теории

Алгоритм решения задачи НП Графическим методомШаг 1. На плоскости х1Ох2 строят

Пример решения задачи НП графическим методомРешить задачу нелинейного программирования

Алгоритм метода множителей ЛангранжаШаг 1.

Пример решения задачи методом Лангранжа

Пример решения задачи методом Лангранжа

Пример решения задачи методом Лангранжа

Методы поиска экстремального значения ЦФ Группа 1.Градиентные методы 1) метод

5. Динамические моделиДинамическое модели — это модели позволяющие решать задачи

Основные этапы составления динамической модели

Основные этапы составления динамической модели

Этапы решения задач динамического программирования

Пример задачи динамического программирования

Пример задачи динамического программирования

Пример задачи динамического программирования

Сетевая модель - пример динамической модели в теории управления

Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных работ (операций),

Пример решения задачи. Для заданного сетевого графика рассчитать все параметры событий

Параметры событий сетевого графикаКритический путь образуют следующие события:0 → 3 →

Параметры работ сетевого графика

Графики1. Диаграммы круговые 2. Гистограммы 3. Линейные4. Лепестковые

Схемы блок-схемы

Схемы схемы-расположений

Схемы схемы-производства

Схемысхемы-производства

Графы

Графы

Похожие презентации

2. Классические задачи линейного программирования
Целевая функция и ограничения линейны

Задача оптимального использования ресурсов
В распоряжении предприятия имеется определённое количество ресурсов

Задача о составлении рациона (технологическая задача)
Необходимо составить такой дневной рацион,

Тогда модель задачи будет иметь вид:
f(x) = c1 x1 + c2x2

Методы решения задач линейного программирования:
1. Графичский метод
2. Симплекс метод
3. С помощью

2. Специальные задачи линейного программирования
2.1. Траспортная задача

Алгоритм решения транспортной задачи состоит из 4 этапов:
Этап 1. Представление данных

Методы поиска допустимого распределения:
1. Метод минимальной стоимости
2. Метод северо-западного угла
3. Метод

Метод Фогеля.
Основан на «штрафной стоимости». Штрафная стоимость для каждой строки и

2.2. Задача о назначениях
Особенность задачи о назначениях:
1. Число пунктов производства

Алгоритм решения задачи о назначении (Венгерский метод)
Этап 1:
1.1. Формализация проблемы в

Этап 2
2.1. Найти строку, содержащую только 1 нулевое значение стоимости, и

Этап 3
3.1. Провести минимальное число прямых через строки и столбцы матрицы

Пример решения задачи о назначениях
Некоторая компания имеет 4 сбытовые базы и

3. Нелинейные модели
Нелинейное программирование (НП) представляет собой раздел в теории

Алгоритм решения задачи НП Графическим методом
Шаг 1. На плоскости х1Ох2 строят

Пример решения задачи НП графическим методом
Решить задачу нелинейного программирования

Алгоритм метода множителей Лангранжа
Шаг 1.

Методы поиска экстремального значения ЦФ
Группа 1.Градиентные методы
1) метод

5. Динамические модели
Динамическое модели — это модели позволяющие решать задачи

Параметры событий сетевого графика
Критический путь образуют следующие события:
0 → 3 →

Графики
1. Диаграммы круговые 2. Гистограммы 3. Линейные
4. Лепестковые

Схемы
блок-схемы

Схемы
схемы-расположений

Схемы
схемы-производства

Схемы
схемы-производства