Нахождение оптимального плана транспортной задачи распределительным методом
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Министерство образования и науки Российской Федерации
Уральский государственный колледж им. И.И. Ползунова
КП.230105.08. ПЗ
НАХОЖДЕНИЕ ОПТИМАЛЬНОГО ПЛАНА ТРАНСПОРТНОЙ ЗАДАЧИ РАСПРЕДЕЛИТЕЛЬНЫМ МЕТОДОМ
Пояснительная записка
Руководитель /Е.В. Щанова/
Разработал /Е.А. Ищенко/
Екатеринбург 2011
Содержание
Введение
1. Постановка задачи
2. Этапы решения задачи
2.1 Математическая модель
2.2 Разработка алгоритма
2.3 Описание программы
2.4 Тестирование программы
2.5 Анализ полученных результатов
Заключение
Список использованных источников
Приложение А
Введение
Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача - задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования - области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.
Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и вычислительных в планировании перевозок дает большой экономический эффект. Транспортные задачи могут быть решены специальными методами. Одним из таких методов является распределительный метод.
Цель курсового проекта: решение транспортной задачи распределительным методом.
Задачи курсового проекта:
построение математической модели;
разработка алгоритма задачи;
создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi7;
решить задачу созданной программой;
проанализировать результат.
Практическим результатом курсового проекта является разработка программы для решения транспортной задачи распределительным методом.
1. Постановка задачи
От каждого i-го производителя произведенный им ресурс Ai может перемещаться к j-му потребителю ресурса в объеме, не превышающие Bi. Таким образом, xij будет означать перемещение некоторого числа единиц ресурса от i-го производителя к j-му потребителю.
Сформулируем условие задачи для частного случая, которое в дальнейшем будем использовать для тестирования задачи.
Составить оптимальный план перевозок ресурсов от производителя к потребителю с минимальными затратами. Исходные данные указаны в таблице 1.
Таблица 1 - Исходные данные
Матрица стоимостиА1А2А3А4ПроизводителиВ1658714В2364212В391368Потребители1014642. Этапы решения задачи
2.1 Математическая модель
При решении транспортной задачи необходимо:
а)обеспечить всех потребителей ресурсами;
б)распределить все произведенные ресурсы;
в)переместить ресурсы от производителей к потребителям с наименьшими затратами.
Транспортная задача разрешима, когда количество произведенного ресурса равна количеству потребленного ресурса. Такая задача называется сбалансированной или закрытой. В другом случаи получится дефицит или избыток ресурса. Тогда задача называется несбалансированной или открытой.
Транспортная задача всегда разрешима и имеет:
а)единственное решение;
б)несколько допустимых решений, одно из которых оптимально;
в)несколько допустимых решений и все оптимальны.
Через Сij обозначим стоимость перемещения единицы ресурса, от i-го производителя к j-му потребителю. Тогда матрица X={xij} называется матрицей перевозок или планом перевозок, а матрица C={cij} - матрица стоимости.
Строим математическую модель
транспортная задача распределительный метод
, (1)
где F (x) - целевая функция;
cij - коэффициенты матрицы стоимости;
xij - коэффициенты матрицы перевозок.
(x) i j0, i=, j=
2.2 Разработка алгоритма
1)Задать количество производителей и потребителей;
2)Произвести ввод данных, данные берутся из таблицы 1;
)следующим шагом строится опорный план для задачи. В программе рассмотрено построение опорного плана методом "северо-западного" угла и методом минимальных элементов;
)выбирается первый незаполненный элемент опорного плана;
)от выбранного элемента строится кратчайший прямоугольный замкнутый контур, остальные вершины проходит через заполненные элементы опорного плана. Поворот осуществляется только на 900 и только в заполненных элементах;
)каждой вершине контура присваивается коэффициент равный соответствующему значение элементу из С={cij};
)каждому коэффициенту в вершине контура строго поочередно присваивается знак "+" или "-" начиная с пустой клетки;
)выполняется алгебраическое суммирование коэффициентов по всему контуру;
)пункт 4-8 выполняется для каждого пустого элемента опорного плана;
)проверяются результаты суммирования по всем контурам на оптимальность;
)если план перевозок не оптимальный то выполняется перераспределение ресурсов и возв?/p>