Моделирование и оптимизация автомобильных дорог
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
Моделирование и оптимизация автомобильных дорог
Исходные данные:
Вариант 8
1. учебная сеть дорог;
. координаты предприятий поставщиков и потребителей;
. запасы продукции у предприятий поставщиков;
. потребность в продукции у предприятий и потребителей;
. ресурс рабочего времени оборудования;
. необходимые поставок продукции;
. удельные затраты времени на производство продукции;
. объем инвестиций предприятиям;
. прибыли предприятий.
Содержание курсового проекта:
. оптимизировать дорожную сеть;
. составить оптимальную схему перевозок;
.оптимизировать распределение продукции, используя алгоритм "транспортная задача";
. оптимизировать распределение продукции, используя Ехсеl;
. произвести сравнительный анализ решения по алгоритму "транспортная задача" и в Ехсеl;
. оптимизировать инвестирование предприятий, использую динамическое программирование и пакет прикладных программ;
. оптимизировать производственную программу предприятия и объединения, используя симплекс метод и программы.
Курсовой проект представляется:
. Пояснительная записка с необходимыми расчетами и схемами;
. Обоснование принимаемых проектных решений.
ВВЕДЕНИЕ
Задачами линейного программирования (ЛП) называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств, и для которых методы математического анализа оказывается непригодными.
Задача ЛП в стандартной форме имеет следующий вид:
W = с1*х1 + с2*х2 + … + сn*хn > min (max)
где х1, х2 и хп - переменные величины;
с1, с2 и сп - коэффициенты.
Условия функционирования объекта (ограничения) в задачах линейного программирования должны относиться к одному из следующих типов:
d1*х1 + d2*х2 + … + dn*хn = d0
е1*х1 + е2*х2 + … + еn*хn ? еo
f1* х1 + f2* х2 + … + fn* хn ? f0
где dп, еп, - коэффициенты;
do, еo, fo - постоянные величины.
В предлагаемых методических указаниях решение задач начинается с составления математической модели процесса, описанного в задаче, и анализа модели с целью выбора наиболее эффективного способа оптимизации. Для решения оптимальных задач использован пакет программ статического программирования "Statgraphic".
Процесс динамического программирования проводится от конца к началу. Первым планируется последний этап. При этом предполагаются различные варианты завершения предыдущего этапа, и для всех этих вариантов находят такое решение, при котором эффект на последнем этапе будет наибольшим. Такое решение будет условно оптимальным. Аналогично находятся услoвно оптимальное решение на последующих этапах.
Таким образом, задача поиска условного максимума функции многих переменных сводится к нескольким задачам поиска максимума функции двух переменных. Далее процесс происходит в обратном порядке (от начала к концу). В результате чего, находятся оптимальные уравнения на каждом шаге и, таким образом, оптимизируется весь процесс.
1. ОПТИМИЗАЦИЯ ДОРОЖНОЙ СЕТИ
1.1 Исходные данные
Необходимо найти кратчайшее расстояние между двумя пунктами А и K, для перевозки грузов с минимальными затратами. Между этими пунктами находится 10 пунктов: 3 внутри, 5 внизу, 2 наверху.
1.2 Нахождение кратчайшего пути с использованием динамического программирования
Для решения рода многошаговых задач разработан соответствующий математический аппарат, который получил название динамическое программирование.
Метод динамического программирования был предложен и развит Р. Беллманом и его учениками в начале 50-х годов и состоит в нахождении оптимума целевой функции при ограничении общего вида на варьируемые параметры.
Характерным для динамического программирования является то, что переменные рассматриваются не вместе, а последовательно - одна за другой. При этом вычислительная схема строится таким образом, чтобы вместо одной задачи с n переменными решалась серия задач с небольшим числом, а чаще всего с одной переменной. Сам же вычислительный процесс производится на основе метода последовательных приближений в два этапа:
от последнего шага к первому;
от первого шага к последнему или же, наоборот, в зависимости от исходных данных.
На первом этапе ищется так называемое условное оптимальное решение. Оно выбирается так, чтобы все предыдущие шаги обеспечили максимальную эффективность последующего. Основу такого подхода составляет принцип оптимальности Беллмана, который формулируется следующим образом: нельзя получить оптимальное значение целевой функции i-шагового процесса, если для любого ui, выбранного на шаге I, значение целевой функции для оставшихся i-1 шагов не является оптимальным.
Такой процесс продолжается до тех пор, пока решение не потеряет свой условный характер, т.е. до первого шага или последнего. Для последнего шага решение однозначно оптимально. Поэтому второй этап начинают именно с этого шага и последовательно переходят от условных к оптимальным решениям, тем самым обеспечивая оптимальность операции в целом.
Процесс поиска начинается с последовательно пройденных этапов.
этап - Попадание в точку K одним способом - J, L, I.
этап - 3-мя способами - G, E, C.
этап - 4-мя способами - B, H.
этап - 10-тью способами - F, D.
этап - 15-тью способами - А.
Далее ищем оптимальные варианты.
Для данно?/p>