Описание алгоритма решения транспортной задачи по планированию перевозки зерна. Ход решения задачи вручную, в программе TORA методом наименьшего элемента, с помощью MS Excel. Разработка программы для решения задачи в общем виде средствами Delphi.
Аннотация к работе
Выбрать и обосновать наиболее эффективный метод решения задачи. Разработать алгоритм и программу для решения задачи в общем виде.Транспортная задача является сбалансированной, если суммарные запасы поставщиков равны суммарным запросам потребителей, т.е. Если суммарные запасы поставщиков превосходят суммарные запросы потребителей, т.е. то необходимо ввести фиктивного (n 1)-го потребителя с запросами равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза; Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы. Данный метод состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости , и исключается из рассмотрения только одна строка(поставщик) или один столбец (потребитель). При этом если поставщик не исключен, но его запасы равны нулю, то на том шаге, когда от него требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения.1 Проверим на сбалансированность. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов: Элеватор Хлебозавод Запасы зерна Так как ? Ai > ? Bi, то вводим «Фиктивный» пункт потребления - хлебозавод №4 с потребностью в зерне : B4 = ?Ai - ?Bi = 5400 - 4600 = 800 т. и с нулевыми расстояниями до элеваторов. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.Когда данные будут введены, нажимаем кнопку «SOLVE Menu» и выбираем метод Solve Problem => Iterations => Least-Cost starting solution (Метод наименьшего элемента) с помощью которого необходимо решить задачу. Программа Поиск решений (в оригинале Excel Solver) - дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных задач оптимизации. Чтобы активизировать ее необходимо перейти на вкладку «Пуск », нажать кнопку «Параметры Ecxel» => «Надстройки» и установить флажок рядом с пунктом «Поиск решения». В ячейки «E7-G8» вводим расстояния до хлебозаводов, в ячейки «E12-G12» вводим потребности хлебозаводов, в «I7;I8» вводим запасы в элеваторах и в ячейку «F26» вписывается значение затрат на 1 единицу. В ячейки «H7» и «H8» вставляем нули, так как данная задача несбалансированна и запасы превышают потребности и вводится фиктивный потребитель, ячейка «H12» считается автоматически, как только будут заполнены ячейки с потребностями и запасами «=(I7 I8)-(E12 F12 G12)» (см. рисунок 6).В курсовой работе были произведены расчеты различными способами решения транспортной задачи. Данные, выводимые программой, соответствуют тем, что получены при расчетах вручную - методом наименьшего элемента и методом потенциалов, соответствуют решению в программе TORA и в программе.
План
Содержание
1. Постановка задачи
2. Описание алгоритма решения задачи
3. Решение задачи вручную
4. Решение в программе TORA
5. Решение в программе MS Excel
6. Разработка программы для решения задачи в общем виде (Delphi)
Выводы
Список используемой литературы
1. Постановка задачи
Вывод
В курсовой работе были произведены расчеты различными способами решения транспортной задачи.
Была составлена программа, которая разработана в программе Delphi .
В программе удобный и понятный пользовательский интерфейс. Для ввода данных используется клавиатура. Данные, выводимые программой, соответствуют тем, что получены при расчетах вручную - методом наименьшего элемента и методом потенциалов, соответствуют решению в программе TORA и в программе. MICROSOFTEXCEL 2007 реализованную через «Поиск решения»
Для всех способов минимальные денежные затраты равны 3700000 д.е.
Таким образом, поставленная задача была выполнена.
Список литературы
1. Данилин Г.А. Математическое программирование с EXCEL: Учебное пособие для студентов всех специальностей МГУЛА / Г.А. Данилин, В.М. Курзина, П.А. Курзин и др. - М.: МГУЛ. 2005.
2. Корняков В.Н. Программирование документов и приложений MS Office в Delphi. - СПБ.: БХВ-Петербург, 2005. - 496 с : ил.
3. Таха, Х.А. Введение в исследование операций, 7-е издание.: Пер. с англ. - М.: Издательский дом "Вильяме", 2005. - 912 с: ил.