Решение транспортных задач венгерским методом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Министерство образования и науки Украины
Севастопольский национальный технический университет
Кафедра
Информационных систем
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту
на тему: Решение транспортных задач венгерским методом
по курсу Методы исследования операций
Выпонил: ст. гр. И-23 д
Костенко К.
Приняла: ст.пр. Заикина Е.Н.
Севастополь
2011
АННОТАЦИЯ
транспортная задача решение венгерский метод
В данной пояснительной записке приводится постановка задачи, её экономическая интерпретация и математическая модель. Рассматривается общая методика постановки, построения алгоритмов и решения транспортных задач. Особое внимание уделяется решению транспортных задач венгерским методом. Здесь также представлен текст программы, реализующей решение транспортных задач венгерским методом, описание работы программы, результаты проведения вычислительного эксперимента и сравнительная характеристика полученных результатов. В заключительной части пояснительной записки проводится анализ математической модели на чувствительность к изменению экономических аспектов.
СОДЕРЖАНИЕ
Введение
Краткий обзор решения транспортных задач
.1 Постановка Т-задачи
.2 Метод потенциалов
.2.1 Метод северо-западного угла
.2.2 Метод минимальной стоимости
.2.3 Метод штрафов
2 Содержательная постановка задачи
2.1 Экономическая интерпретация поставленной задачи
Разработка и описание алгоритма решения задачи
.1 Предварительный этап
.2 Поисковый этап
.3 Этап построения цепочки и коррекции плана
.4 Этап эквивалентных преобразований
Построение математической модели задачи
Получение оптимального решения
.1 Решение варианта № 24 вручную
.2 Решение задачи на ЭВМ
Анализ модели на чувствительность
Заключение
Библиографический список
Приложение А. Описание интерфейса программы
Приложение Б. Текст программы
ВВЕДЕНИЕ
Целью настоящей курсовой работы является закрепление знаний, получаемых в процессе изучения диiиплины Методы исследования операций, приобретение необходимых практических навыков комплексного применения теоретико-методологических принципов исследования операций и математического программирования к постановке, решению и анализу задач организационного управления.
Задача данной курсовой работы состоит в следующем:
- изучить требуемый раздел диiиплины;
- построить математическую модель оптимизационной задачи, соответственно содержательной постановке;
- подобрать и разработать алгоритм решения поставленной задачи;
- написать программу, соответствующую разработанному алгоритму, отладить ее, используя в качестве тестовых данных рассчитанный вручную вариант;
- провести анализ модели на чувствительность компонентов оптимального решения к изменению элементов ограничений.
- Тема курсовой работы - решение транспортных задач венгерским методом - является актуальной на сегодняшний день. Венгерский метод наиболее эффективен при решении транспортных задач iелочисленными объемами производства и потребления. В этом случае число итераций не превышает величины ?0/2 (?0 - суммарная невязка подготовительного этапа). Достоинством венгерского метода является возможность оценивать близость результата каждой из итераций к оптимальному плану перевозок. Это позволяет контролировать процесс вычислений и прекратить его при достижении определенных точностных показателей. Данное свойство существенно для задач большой размерности. Так как венгерский метод решения Т-задачи является сравнительно простым, то его можно широко применять на предприятиях, где требуется вести подсчет минимальных затрат на перевозку груза, например, со скалада на предприятие.
- 1 КРАТКИЙ ОБЗОР РЕШЕНИЯ ТРАНСТПОРТНЫХ ЗАДАЧ
- Транспортная задача (Т-задача) является одной из самых распространенных специальных задач линейного программирования. Первый точный метод решения Т-задачи разработан советскими учеными Л. В. Канторовичем и М. К. Гавуриным.
- 1.1 Постановка Т-задачи
- Пусть в пунктах А1, А2, тАж, Аm производят некоторый однородный продукт, причем объем производства в пункте Аi составляет ai единиц (i = 1, ..., m). Допустим, что данный продукт потребляют в пунктах B1, B2, тАж, Bn, а объем потребления в пункте Вj составляет bj единиц (j = 1, тАж, n).
- Предположим, что из каждого пункта производства возможна транспортировка продукта в любой пунт потребления. Транспортные издержки по перевозке из пункта Аi в пункт Вj единицы продукции равны cij (i = 1, ..., m, j = 1, тАж, n).
- Задача состоит в определении такого плана перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны.
- Существуют следующие методы решения транспортных задач: метод потенциалов и венгерский метод.
- 1.2 Метод потенциалов
- Метод потенциалов позволяет, исходя из некоторого опорного плана перевозок, построить за конечное число итераций решение Т-задачи.
- Общая схема метода такова. В данном начальном опорном плане каждому пункту ставят в соответствие некоторое число, называемое его предварительным потенциалом.