Магистерская диссертация на тему: Постановка линейной целочисленной задачи. Теоретические основы методов отсечения

Введение

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

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

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

Оглавление

- Введение

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

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

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

- Второй алгоритм Гомори

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

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

- Некоторые выводы Заключение

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

- Приложение

Заключение

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

Наиболее перспективными для дальнейших исследований по методу отсечения представляются следующие направления:

1) Исследование строения множеств Вц и V(Вц).

2) Исследование свойств правильных отсечений.

3) Указание новых способов построения правильных отсечений.

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

5) Выделение отдельных классов эффективно решаемых задач.

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

1. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование, М.: Наука, - 1969.

2. Лященко И.Н. Линейное и нелинейное программирование, М.: Наука, - 1985.

3. Санович К.М. Исследование операций, М.: Наука, - 1989.