Экспериментальное сравнение трудоемкости двух алгоритмов решения задачи построения наибольшего паросочетания минимального веса в двудольном графе

Содержание

Введение..3

1. Цель работы.5

2. Основные определения и обозначения.6

3. Постановка задачи о назначении…8

4. Алгоритм решения задачи построения наибольшего паросочетания минимального веса…9

5. Постановка транспортной задачи13

6. Решение транспортной задачи.14

7. Сведение задачи о назначении к транспортной задаче.17

8. Реализация программы.18

9. Текст программы..23

10. Эксперименты.50

Заключение..187

Список литературы.188

Выдержка из текста

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

Для этого необходимо было:

1.Разобраться в предложенных алгоритмах решения задачи;

2.Создать программу для решения задачи и проведения экспериментов;

3.Провести сравнение и проанализировать полученные результаты.

Список использованной литературы

1.Бахтин А.Е., Колоколов А.А., Коробкова З.В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука, 1978. 160с.

2.Диниц Е.А. О решении двух задач о назначении: — в книге: Исследования по дискретной оптимизации.-М.: Наука, 1976, с.333-348

3.Заботин И.Я., Фазылов В.Р., Шульгина О.Н. Алгоритмы решения оптимизационных задач на графах: Учебное пособие. Казань: Казанский государственный университет им. В.И.Ульянова-Ленина, 2006. 68с.

4.Заботин И.Я. Лекции по линейному программированию: Учебное пособие. Казань: Издательство Казанского университета, 1985. 98с.

5.Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. 323с.

С этим материалом также изучают

Теория решения изобретательских задач. Алгоритм решения изобретательских задач 2

... решения изобретательских задач. Алгоритм решения изобретательских задач ... систем. Поскольку программу реализует ... большой размер инфы. Список использованных источников1. Альтшуллер Г.С. Найти идею: Введение в ТРИЗ – теорию решения изобретательных задач ...

Теория решения изобретательских задач. Алгоритм решения изобретательских задач.

Содержание Содержание Лист для замечаний 2 Введение 4 Теория решения изобретательских задач. Алгоритм решения изобретательских задач 6 Заключение 8 Список использованных источников 9 Приложение Анализ использования ...

Постройте наибольшее паросочетание для двудольного графа G. Первая доля состоит из вершин (a, b, с, d, е, f, g), вторая доля — из вершин (…). Ребра задан

... Ребра заданы следующим списком: (...).Выдержка из текстаПостройте наибольшее паросочетание для двудольного графа G. Первая доля состоит из вершин (a, b, ... СодержаниеПостройте наибольшее паросочетание для двудольного графа G. Первая доля состоит из ...

Программное обеспечение решения транспортной задачи

... по выбранной тематике диплома и анализ специфики алгоритмов и методов построения прикладного программного обеспечения для решения транспортной задачи, разработка программы и оформление пояснительной записки согласно установленным ...

Полный алгоритм решения задач линейного программирования

... большого числа экономических задач (планирование производства, расходование ресурсов, раскрой материалов, транспортные перевозки и т.д.). Рассмотрим на примерах процесс построения ... И.В. Алгоритмы решения экстремальных задач. М.: Наука. ...

Курсовая работа по уравнениям Фредгольма пошаговый алгоритм решения методом квадратур в MATLAB

Подробное руководство по численному решению интегральных уравнений Фредгольма второго рода методом квадратур. Рассматривается теория, пошаговый алгоритм, его реализация в MATLAB, а также анализ и визуализация результатов для успешного выполнения курсовой работы.

Решения транспортных задач на примере решения задачи

... связанных с решением транспортных задач.Курсовая работа состоит из двух частей: теоретической и практической. В первой главе работы будут рассмотрены теоретические основы решения транспортной задачи: - постановка задачи, - построение математической ...

Спосбы нахождения опорного плана решения транспортной задачи

... большой экономический эффект. Транспортные задачи могут быть решены симплексным методом, однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения ... Для построения математической модели задачи необходимо ...

Похожие записи