Анализ метода, основанного на алгоритме максимального потока или минимальной стоимости. Использование системы последовательных операций выбора кратчайшего маршрута. Изучение целочисленной задачи линейного программирования с применением алгоритма Гамори.
Аннотация к работе
В 1955 г. на Втором симпозиуме по линейному программированию была рассмотрена задача о бомбардировщике, известная как задача о ранце. Цель данной работы: В данной работе я рассмотрю Целочисленное линейное программирование(ЦЛП) ориентированное на решение задач линейного программирования, также рассмотрю задачу о назначениях. , Условия неотрицательности и целочисленности (булевости): , Легко видеть, что задача о назначении - частный случай транспортной задачи при Однако с учетом специфики задачи для ее решения разработаны специальные, более эффективные алгоритмы. Прежде всего необходимо отметить, что если задача о назначениях ставится при условии получения максимального эффекта, то ее сводят к задаче на минимум. , В самом деле, , Функция Z" достигает минимума при условии, что Z достигает максимума, Если в задаче о назначениях число исполнителей равно числу работ, то говорят о закрытой модели, в противном случае - об открытой модели задачи о назначениях.