Тема 4. Задача о загрузке.
-
Общие сведения.
-
Рекуррентные соотношения для процедур прямой и обратной прогонки.
-
Решение задачи о загрузке
4.1 Общие сведения.
Задача о загрузке – это задача о рациональной загрузке судна (самолета, автомашины и т.п.), которое имеет ограничения по объему или грузоподъемности. Каждый помещенный на судно груз приносит определенную прибыль. Задача состоит в определении загрузки судна такими грузами, которые приносят наибольшую суммарную прибыль.Рекуррентное уравнение процедуры обратной прогонки выводится для общей задачи загрузки судна грузоподъемностью W предметов (грузов) n наименований. Пусть mi-количество предметов і-го наименования, подлежащих загрузке, ri-прибыль, которую приносит один загруженный предмет і-го наименования, wi-вес одного предмета і-го наименования. Общая задача имеет вид следующей целочисленной задачи линейного программирования.
Максимизировать z=r1m1+r2m2+…+rnmn.
при условии, что
w1m1+w2m2+…+wnmn W,
m1,m2,…,mn 0 и целые.
Три элемента модели динамического программирования определяются следующим образом:
Этап і ставится в соответствии предмету і-го наименования, і=1,2,…n.
Варианты решения на этапе і описываются количеством mi предметов і-го наименования, подлежащих загрузке. Соответствующая прибыль равна rimi. Значение mi заключено в пределах от 0 до [W/wi], где [W/wi] – целая часть числа W/wi.
Состояние xi на этапе і выражает суммарный вес предметов, решения о погрузке которых приняты на этапах і,і+1,...n. Это определение отражает тот факт, что ограничения по весу является единственным, которое связывает n этапов вместе.
Пусть fi(xi)-максимальная суммарная прибыль от этапов і,і+1,...,n при заданном состоянии xi. Проще всего рекуррентное уравнение определяется с помощью следующей двухшаговой процедуры.
Шаг 1. Выразим fi(xi) как функцию fi+1(xi+1) в виде
где fn+1(xn+1)=0.
Шаг 2. Выразим xi+1 как функцию xi для гарантии того, что левая часть последнего уравнения является функцией лишь xi. По определению xi-xi+1 представляет собой вес, загруженный на этапе і, т.е. xi-xi+1=wimi или xi+1=xi-wimi. Следовательно, рекуррентное уравнение приобретает следующий вид:
- Тема 1. Классификация моделей.
- Тема 1. Классификация моделей.
- Основные признаки классификации моделей.
- Область использования.
- Учет в модели временного фактора.
- Способ представления модели.
- Тема 2. Классификация языков компьютерного моделирования.
- Тема 3. Этапы и цели компьютерного математического моделирования.
- Раздел 1. Задачи линейного программирования.
- Тема 1. Математическое программирование. Общий вид задач линейного программирования.
- Формулировка задачи.
- Геометрическая интерпретация задачи линейного программирования.
- Найти минимальное значение линейной функции
- Тема 2. Графический метод решения задач линейного программирования.
- Примеры задач, решаемых графическим методом.
- Обобщение графического метода решения задач линейного программирования.
- Тема 3. Симплекс - метод.
- Каноническая задача лп на максимум.
- Вспомогательная задача лп.
- Алгоритм метода искусственного базиса
- Вспомогательная задача лп.
- Алгоритм метода искусственного базиса.
- Тема 4. Транспортная задача.
- 4.2 Составление опорного плана.
- 4.3 Метод потенциалов.
- Раздел 2. Теория графов.
- Тема 1. Основные понятия теории графов.
- Элементы множества V называются вершинами графа g (или узлами), элементы множества u-его ребрами. Вершины и ребра графа называют также его элементами и вместо VV и u u пишут Vg и ug.
- 1.2 Операции над графами.
- 1.3.Связность графов.
- 1.4 Эйлеровы графы.
- 1.5 Гамильтоновы графы.
- Тема 2. Поиск пути в графе.
- 2.2 Путь минимальной суммарной длины во взвешенном графе с неотрицательными весами (алгоритм Дейкстры).
- 2.3 .Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин (алгоритм Флойда).
- 2.4 Путь с минимальным количеством промежуточных вершин (волновой алгоритм).
- 2.5 Нахождение k путей минимальной суммарной длины во взвешенном графе с неотрицательными весами (алгоритм Йена).
- Тема 3. Задачи о минимальном остове.
- 3.1 Деревья.
- 3.1 Построение минимального остовного дерева (алгоритм Краскала).
- 3.1 Деревья.
- 3.1 .Построение минимального остовного дерева (алгоритм Краскала).
- Раздел 3. Динамическое программирование.
- Тема 1. Метод динамического программирования.
- 1.2 Идеи метода динамического программирования
- 1.3 Выбор состава оборудования для технологической линии.
- Исходные данные для примера
- Тема 2. Задача инвестирования.
- Тема 3. Замена оборудования.
- Тема 4. Задача о загрузке.
- 4.2 Рекуррентные соотношения для процедур прямой и обратной прогонки.
- 4.3 Решение задачи о загрузке.
- Раздел 4. Системы массового обслуживания (смо). (8 часов).
- Тема 1. Основные понятия теории массового обслуживания.
- Тема 2. Простейшие смо и нахождение их параметров.
- Перечень характеристик систем массового обслуживания можно представить следующим образом:
- 2. Одноканальная смо с неограниченной очередью
- 3. Одноканальная смо с неограниченной очередью, простейшим потоком заявок и произвольным распределением времени обслуживания
- 4. Одноканальная смо с произвольным потоком заявок и произвольным распределением времени обслуживания
- Раздел 5. Имитационное моделирование.
- Тема 1. Простейшие задачи, решаемые методом имитационного моделирования.
- Тема 2. Основные понятия теории Марковских процессов.
- Тема 3. Метод Монте – Карло.
- Раздел 6. Прогнозирование.
- Тема 1. Основная идея прогнозирования. Методы прогнозирования
- Тема 2.Теории экспертных оценок.
- Раздел 7. Теория игр.
- Тема 1. Основные понятия теории игр.
- 1. 1 Понятие об играх и стратегиях
- Тема 2. Простейшие методы решения задач теории игр.
- Раздел 8. Элементы теории принятия решений. (2 часа).
- Основные понятия.
- Принятие решений в условиях полной неопределенности
- Принятие решений при проведении эксперимента.
- 2. Принятие решений в условиях полной неопределенности
- 2.1 Максиминный критерий Вальда.
- Критерий равновозможных состояний.
- 3. Принятие решений при проведении эксперимента.
- 3.1. Принятие решений в условиях неопределенности.
- 3.2. Использование смешанной стратегии
- 3.3. Принятие решений в условиях риска