Читать курсовая по финансовому менеджменту, финансовой математике: "Применение метода ветвей и границ для задач календарного планирования" Страница 1

(Назад) (Cкачать работу)

ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ РФ

Кафедра «Математика и финансовые приложения» Курсовая работа по дисциплине

«Метод ветвей и границ в исследовании операций»

Применение метода ветвей и границ для задач календарного планирования Москва 2011

§1.1 Реккурентное вычисление A(k), В(k), C(k) и условие доминирования 13 §1.2 Способ конструирования вариантов последовательностей  и вычисления оценок () для каждого из них 14

В своей курсовой работе мне хотелось бы рассмотреть применения метода ветвей и границ для задач календарного планирования. В контексте данной задачи будет дано общее описание метода ветвей и границ, его места в общей задаче целочисленного программирования.

Будут рассмотрены примеры, как простого применения метода, так и для задач календарного планирования (будет рассмотрена задача о трех станках).

Данная тема является чрезвычайно актуальной, ведь метод ветвей и границ в связи с простотой сущности алгоритма используется при работе на некоторых ЭВМ, а решения задач календарного планирования всегда востребованы как в экономической отрасли, так и других, смежных с ней.

Описание задачи целочисленного программирования

По смыслу значительной части экономических задач, относятся к задачам линейного программирования, компоненты решения должны выражаться в целых числах, т.е. быть целочисленными. К ним относятся, например, задачи, в которых переменные означают количество единиц неделимой продукции, число станков при загрузке оборудования, число судов при распределениях по линиям, число турбин в энергосистеме, число вычислительных машин в управляющем комплексе и многие другие.

Задача линейного целочисленного программирования формируется следующим образом: найти такое решение (план) X = (x1,x2,...,xn), при котором линейная функция(1) принимает максимальное или минимальное значение при ограничениях: = bi,.(2)

хj  0,.(3)

xj  ,.(4).

Метод ветвей и границ

Метод ветвей и границ — один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.

Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи.

Первоначально находим, к примеру, симплекс-методом оптимальный план задачи без учета целочисленности переменных. Пусть им является план X0. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и Fmax = F(X0).

Если же среди компонент плана X0 имеются дробные числа, то X0 не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи. Покажем, как это можно сделать, предварительно отметив, что F(X0)  F(X) для всякого последующего плана X в связи с увеличением количества ограничений.

Предполагая, что найденный оптимальный

Похожие работы