- •1. Основные определения теории принятия решений
- •2. Постановка задач принятия оптимальных решений
- •3. Виды классификаций задач принятия решений
- •4. Аксиомы теории принятия решений
- •5. Многокритериальные задачи принятия решений
- •6. Аксиомы рационального поведения при принятии решений
- •7. Нерациональное поведение при принятии решений
- •8. Принятие решений в условиях определенности
- •9. Принятие решений в условиях риска
- •10. Принятие решений в условиях неопределенности.
- •11. Классические критерии принятия решения (минимаксный критерий, критерий Байеса-Лапласа, критерий Сэвиджа).
- •12. Производные критерии (критерий Гурвица, Ходжа-Лемана).
- •15. Задача о назначениях.
- •16. Транспортная задача.
- •18. Задача о ранце
- •19. Задача коммивояжера.
- •20. Задача управлення запасами
- •22. Метод анализа иерархий.
- •24. Дерево принятия решений.
- •29.Системы поддержки принятия решений
16. Транспортная задача.
Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.[1][2] Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной или входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной.
Постановка задачи
Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).
Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).
18. Задача о ранце
Задача о ранце (рюкзаке) — одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Подобные задачи часто возникают в экономике, прикладной математике, криптографии. В общем виде, задачу можно сформулировать так: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
Содержание [убрать]
1 Разновидности
2 Решение
3 Задача о ранце с возможностью бесконечного выбора предметов
3.1 Формулировка
3.2 Решение
3.3 Реализация
4 Задача о ранце с возможностью единичного выбора предмета
4.1 Решение
4.2 Реализация
5 См. также
6 Ссылки
7 Литература
[править]Разновидности
Каждый предмет из множества можно выбирать произвольное количество раз.
Каждый предмет можно использовать только один раз.
[править]Решение
Задача о ранце в случае, когда вес каждого предмета представляет собой целое число, может быть решена с помощью динамического программирования. Но важно отметить, что задача о ранце является NP-задачей (псевдо-полиномиальна).
19. Задача коммивояжера.
Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр — разъездной сбытовой посредник) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.
Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.
Общая постановка задачи, впрочем как и большинство её частных случаев, относится к классу NP-полных задач.