Курсовая работа: Применение метода ветвей и границ для задач календарного планирования

Содержание

Введение

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

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

§1. Описание метода ветвей и границ

§2. Алгоритм действия метода ветвей и границ

§3. Общий алгоритм решения задач с помощью метода границ и ветвей, его суть

§4. Пример использования метода ветвей и границ

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

§1. Алгоритм решения задачи трех станков методом ветвей и границ

§1.1 Реккурентное вычисление A(s_k ), В(s_k ), C(s_k ) и условие доминирования

§1.2 Способ конструирования вариантов последовательностей s и вычисления оценок D(s) для каждого из них.

§2. Пример использования метода ветвей и границ в задаче трех станков

Список литературы

Приложения

Приложение 1

Приложение 2

Приложение 3

Введение

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

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

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

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

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

Задача линейного целочисленного программирования формируется следующим образом: найти такое решение (план) X = (x₁ ,x₂ ,...,x_n ), при котором линейная функция

(1)

принимает максимальное или минимальное значение при ограничениях:

= b_i ,. (2)

х_j ³ 0, . (3)

--> ЧИТАТЬ ПОЛНОСТЬЮ <--