Методы решения задачи о Назначениях: - метод решения Мака - Венгерский метод

СОДЕРЖАНИЕ

Введение

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

Основные задачи выполнения курсовой работы:

1. Усвоение основных теоретических понятий теории оптимального управления, относящихся к разделу решения задач о назначениях:

- классификация методов решения задач линейного программирования (распределительный метод, симплекс – метод, венгерский метод, метод решения Мака), их общие и отличительные свойства;

- постановка задачи о назначениях и ее математическая модель;

- алгоритм метода решения Мака и его модификации для любого критерия оптимальности;

- алгоритм Венгерского метода и его особенности.

2. Выработка навыков выполнения основных этапов математического программирования на основе методики решения задач о назначении:

- составление математической модели по условию задачи;

- приведение задачи «открытого типа» к расширенной закрытой задаче;

- осуществление перехода (при необходимости) от задачи на «минимум» к задаче на «максимум» в процессе решения задачи методом Мака и Венгерским методом;

- нахождение оптимального плана распределения работ посредством Венгерского метода и метода решения Мака;

- проведение сравнительного анализа указанных методов и выявление достоинств и трудных моментов в процессе их использования при решении задач «вручную» и при реализации на ЭВМ;

Задача о назначениях относится к транспортным задачам линейного программирования, то есть, к ее решению можно применить

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

Рассматриваемые в курсовой работе специальные методы решения такого рода задач более просты в смысле применения для их решения как «вручную», так и для практической реализации на ЭВМ.

1 Основная часть

1.1Теоретические сведения

1.1.1 Алгоритм метода решения Мака

До настоящего времени было предложено два метода решения задачи о назначениях:

«Венгерский метод» и «метод решения Мака». Венгерский метод основан на комбинаторных свойствах матриц. Метод Мака имеет в основе интуитивное обоснование. Это – логический процесс.

Формулировка задачи (проблема выбора). Пусть необходимо выполнить n (i = 1, n) работ. Для этого используются n ( j = 1, n) исполнителей, каждый из которых в состоянии выполнять любую работу. Известны затраты C = ||c’ij ||  на выполнение j - м исполнителем i - й работы. Требуется назначить каждого исполнителя на одну работу так, чтобы минимизировать суммарные затраты.