Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения.
Аннотация к работе
Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP . Когда суммарный объем предложений (грузов, имеющихся в пунктах отправления) не равен общему объему спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой). Под названием транспортная задача ,определяется широкий круг задач с единой математической моделью, эти задачи относятся к задачам линейного программирования и могут быть решены оптимальным методом.Имеется 5 пунктов отправления , в которых сосредоточен однотипный груз в количестве . Каждый пункт подает заявку на груз в количестве . Стоимости из іго пункта отправления в jй пункт назначения представлены в виде матрицы в таблице 2.1.Данный метод находит лучшее начальное решение транспортной задачи по сравнению с методом северо-западного угла, т.к выбирает переменные, которым соответствуют наименьшие стоимости. Переменной в этой клетке присваивается максимально допустимое значение, допускаемое ограничениями на заявки и запасы, т.е. Если одновременно удовлетворяет заявка и исчерпывается запас, то обычно вычеркивается j-тый столбец. Каждый пункт подает заявку на груз в количестве . Обозначим через количество единицы груза, отправляемого из i-го пункта отправления в j-ый пункт назначения.Даны сходные данные: Таблица 5.1 - Опорный план Для каждой свободной клетки построим цикл и определим его стоимость Построим цикл для {1;5} Построим цикл для {1;5} Построим цикл для {1;5}Для начала работы с программой необходимо запустить файл transport.exe. Программу можно использовать в полноэкранном режиме, для этого необходимо зайти в меню «Просмотр» и выбрать пункт «Полный экран» или нажать комбинацию клавиш Ctrl F, режим окна можно вернуть с помощью клавиши Esc.(Рисунок 6.1) В главном меню программы необходимо выбрать пункт «Составить план». Программа выведет на экран рабочую таблицу и заполнит стоимость перевозок по умолчанию, если вы хотите изменить стоимость, необходимо нажать на предыдущее значение стоимости. С его помощью можно вернуться в меню, просмотреть подсказку о цветовой схеме таблицы и продолжить работу программы нажав кнопку «Далее».С помощью данной программы вы сможете без труда производить вычисления по транспортной задаче.Рисунок 6.2 - Улучшение плана Рисунок 6.3 - Улучшение плана Рисунок 6.
План
Содержание
1 Введение
2 Постановка задачи
3 Численный метод
4 Схемы алгоритма программы
4.1 Схема алгоритма основной программы
4.2 Схема алгоритма метода NEWPLAN
4.3 Схема алгоритма метода SUMTRANSPORT
4.4 Схема алгоритма метода CICLEPR
4.5 Схемы алгоритма метода SEARCHCYCLE
4.6 Схемы алгоритма метода FIRSTPLAN
5 Ручной просчет
6 Инструкция по эксплуатации программы
7 Заключение
Литература
Приложение А. Листинг программы
Приложение Б. Результаты выполнения программы
Введение
Темой курсовой работы является создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей.
Транспортная задача (задача Монжа - Канторовича) - математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP . Когда суммарный объем предложений (грузов, имеющихся в пунктах отправления) не равен общему объему спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).
Транспортная задача (классическая) - задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределенном количестве) со статичными данными и линеарном подходе (это основные условия задачи).
Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). Под названием транспортная задача ,определяется широкий круг задач с единой математической моделью, эти задачи относятся к задачам линейного программирования и могут быть решены оптимальным методом. Однако, специальный метод решения транспортной задачи позволяет существенно упростить ее решение, поскольку транспортная задача разрабатывалась для минимизации стоимости перевозок.
Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем . Поэтому иногда эта проблема называется транспортной задачей Монжа - Канторовича.
Вывод
С помощью данной программы вы сможете без труда производить вычисления по транспортной задаче. Интерфейс программы удобен и приятен.
Список литературы
1 К.Л. Самаров Транспортная задача. Учебное пособие для студента.
2 Колин Мук ACTIONSCRIPT 3.0 для Flash. Подробное руководство.