Применение методов математической экономики к решению практических задач
Курсовой проект - Экономика
Другие курсовые по предмету Экономика
?ы вычислений с точностью до 0,1 представим в форме межотраслевого баланса. Величина чистой продукции определяется как разница между валовой продукцией отрасли и суммой межотраслевых потоков в каждом столбце.
Потребляющие отрасли Производящие отраслиПромышленностьСельское хозяйствоПрочие отраслиКонечная продукцияВаловая продукция123130,29,093,92467,2213,434,360,581836,4310,071,821,55619,4Чистая продукция13,521,113,4--Валовая продукция67,236,419,4-123
3. Построение кольцевых маршрутов
Коммерческая деятельность обычно связана с командировками, поездками по городам для заключения сделок. Расстояния между любой парой множества из п городов известны и составляют . Если прямого маршрута между городами i и j не существует, то допускают, что . Коммерсант, выезжая из какого-либо города, должен посетить все города, побывав в каждом из них один и только один раз, и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы наименьшей. Таким образом, нам приходиться обращаться к данному методу.
3.1 Содержательная постановка задачи
branchandbound)- с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений.
Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).
,..">Процедура ветвления состоит в разбиении области допустимых решений на подобласти меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево , называемое деревом поиска или деревом ветвей и границ. Узлами этого дерева являются построенные подобласти.
3.2 Математическая постановка задачи
Экономико-математическая постановка этой задачи может быть представлена, как задача целочисленного линейного программирования.
Переменные определим следующим образом: , если коммивояжер переезжает из города i в городу j в противном случае .
Задача заключается в определении матрицы целых неотрицательных значений переменных , минимизирующих целевую функцию вида:
) для въезда в город только один раз
) для выезда из города только один раз
3.3 Описание метода решения
В постановке задача коммивояжера представляет собой задачу целочисленного линейного программирования. Действительно, условия исключают в оптимальном решении значения как не имеющие смысла, а ограничения требуют:
) чтобы маршрут включал только один въезд в каждый город;
) чтобы маршрут включал лишь один выезд из каждого города, а целевая функция включала длину маршрута коммивояжера;
) чтобы маршрут образовывал контур, проходящий через все города.
Таким образом, формируется экономный вариант маршрута в виде кольца.
3.4 Пример решения задачи
Решение этой задачи строится, например, методом ветвей и границ целочисленного программирования: Процедура нахождения оценок заключается в поиске верхних и нижних границ для оптимального значения на подобласти допустимых решений.
В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева).