Министерство высшего и профессионального образования РФ

Тульский государственный университет

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по дисциплине

«ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ И ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ»

на тему:

«Методы отсечения»

Тула 2003 г.

Содержание

 

Введение

1. Постановка линейной целочисленной задачи

2. Теоретические основы методов отсечения

3. Первый алгоритм Гомори

4. Второй алгоритм Гомори

5. Алгоритм Дальтона и Ллевелина

6. Алгоритм Данцига

7. Некоторые выводы

Заключение

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

Приложение

Введение

Среди практически важных задач отыскания условного экстремума линейной функции важное место занимают задачи с требованием целочисленности всех (части) переменных. Они получили название задач целочисленного (частично целочисленного) программирования.

Исторически первой задачей целочисленного типа является опубликованная венгерским математиком Е. Эгервари в 1932 г. задача о назначении персонала.

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

1. Постановка линейной целочисленной задачи

Среди совокупности п неделимых предметов, каждый i-и (i=1,2,…, п) из которых обладает по i-й характеристике показателем  и полезностью  найти такой набор, который позволяет максимизировать эффективность использования ресурсов величины .

Математическая модель этой задачи может быть представлена следующим образом:

в области, определенной условиями

                                      (1)

 

                                                   (2)

- целые, .                      (3)

найти решение при котором максимизируется (минимизируется) значение целевой функции

                                                      (4)

Если , то (1–4) является моделью задачи целочисленного программирования, если - моделью задачи частично целочисленного программирования.

Частным случаем задачи целочисленного программирования является задача с булевыми переменными. Ее математическая модель в общем виде записывается следующим образом:

в области, определенной условиями

                            (5)

                                       (6)

найти решение , при котором максимизируется (минимизируется) значение функции

                                             (7)

К классу задач целочисленного программирования примыкают задачи, в которых условие целочисленности всех или части переменных заменено требованием дискретности. А именно, для каждой j-и переменной  заранее определен набор значений (не обязательно целых), которые она может принимать:  где .

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

в области, определенной условиями

                              (8)

  (9)

найти решение , при котором максимизируется (минимизируется) линейная функция

                                             (10)

Условие (9) определило название этого класса; задач. ............