ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ РФ
    
    КАФЕДРА МТЕМАТИКИ
    
    
    
    
    
    КУРСОВАЯ РАБОТА
    тема:
    
    
    
    
    
    ПРИМЕНЕНИЕ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ ЗАДАЧ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ
    
    
    
    
    
    
    
    Студент группы МЭК 1-1 Клеймёнов И.Д.
    Научный руководитель Солодовников А.С.
    
    
    
    
    
    
    
    
    МОСКВА, 2001г. План 1.Постановка задачи целочисленного программирования 3 2. Понятие о методе ветвей и границ 4 3.Применение метода ветвей и границ для задач календарного планирования 13 Летература 20
    
     1.Постановка задачи целочисленного программирования
    По смыслу значительной части экономических задач, относятся к задачам линейного программирования, компоненты решения должны выражаться в целых числах, т.е. быть целочисленными. К ним относятся, например, задачи, в которых переменные означают количество единиц неделимой продукции, число станков при загрузке оборудования, число судов при распределениях по линиям, число турбин в энергосистеме, число вычислительных машин в управляющем комплексе и многие другие. Задача линейного целочисленного программирования формируется следующим образом: найти такое решение (план) X = (x1,x2,...,xn), при котором линейная функция
     (1)
    принимает максимальное или минимальное значение при ограничениях
    =bi , i=1, 2..., m. (2)
    хj ? 0, j=1, 2,..., п. (3)
    xj - целые числа (4)
    
     2. Понятие о методе ветвей и границ Метод ветвей и границ - один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов. Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи. Алгоритм решения: Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план X0. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и Fmax = F(Xo). Если же среди компонент плана X0 имеются дробные числа, то X0 не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи. Покажем, как это можно сделать, предварительно отметив, что F(X0) ? F(X) для всякого последующего плана X. Предполагая, что найденный оптимальный план X0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла в плане X0 дробное значение. ............