Читайте также:
|
1. Среди задач линейной оптимизации могут быть выделены два класса задач со специальной структурой: транспортная задача и задача о назначениях. Эти задачи используются для моделировали оптимизации экономических проблем, связанных с формированием оптимального плана перевозок, оптимального распределения индивидуальных контрактов на транспортировки, составления оптимального штатного расписания, определения оптимальной специализации предприятий, рабочих участков и станков, оптимального назначения кандидатов на работы, оптимального использования торговых агентов. Критерием эффективности в данных задачах является линейная функция, ограничения также линейны, поэтому для их решения могут применяться методы линейной оптимизации, например симплекс-метод. Однако специальная структура таких задач позволяет разработать более удобные методы их решения. Некоторые из таких методов приведены этой книге. Даны общая формулировка задач, основные термины и определения, этапы построения математических моделей, этапы получения оптимальных решений. Также приведены числовые примеры экономических задач, которые могут быть решены этими методами.
2. задача о назначениях – это распределительная задача, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.д.), а каждый ресурс может быть использован на одной и только одной работе. То есть ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задача о назначениях является частным случаем транспортной задачи. Задача о назначениях имеет место при назначении людей на должности или работы, автомашин на маршруты, водителей на машины, при распределении групп по аудиториям, научных тем по научно-исследовательским лабораториям и т.п.
Алгоритм венгерского метода.(это по ходу задача о назначениях.только другим методом)
В исходной матрице стоимостей определим в каждой строке минимальную стоимость и отнимем ее от других элементов строки.В матрице, полученной на первом этапе, найдем в каждом столбце минимальную стоимость и отнимем ее от других элементов столбца.Если после выполнения первого и второго пункта не получено допустимое решение (в том смысле, что каждому работнику назначена в точности одна работа) выполняем следующие действия:В последней матрице проведите минимальное число горизонтальных и вертикальных прямых по строкам и столбцам, чтобы вычеркнуть в матрице все нулевые элементы.
Найдите наименьший невычеркнутый элемент и вычтите его из остальных невычеркнутых элементов и прибавьте к элементам, стоящим на пересечении проведенных на предыдущем этапе прямых.
Если новое распределение нулевых элементов не позволяет построить допустимое решение повторите пункт 3. В противном случае перейдите к пункту 4.
Оптимальным назначениям будут соответствовать нулевые элементы, полученные на предыдущем этапе.
Дата добавления: 2015-09-10; просмотров: 75 | Поможем написать вашу работу | Нарушение авторских прав |