Claw.ru | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения | Категория реферата: Рефераты по математике | Теги реферата: контрольная работа по математике класс, хозяйство реферат | Добавил(а) на сайт: Костюк. Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

Формируем задачу ЛП путем добавления к исходной ограничений

Ее целевая функция . Находим решение x' этой задачи. Возможны случаи:

1) , процесс завершается;

2) , тогда, если

a) x'p < 1; если p=1, процесс завершается, в противном случае идем на шаг 2;

b) x'p = 1; идем на шаг 1.

Шаг 2. Находим максимальный номер , такой, что . Формируем задачу ЛП, добавляя к исходной следующие ограничения:

ее целевая функция . Находим решение x' этой задачи. Возможны варианты:

1) , процесс завершается;

2) , тогда возможны случаи:

a) ; если , процесс завершается, иначе и переходим на шаг 1.

В результате работы алгоритма перебора L-классов мы получаем лексикографически монотонную последовательность представителей L-классов множества M/L.

3. Декомпозиционный алгоритм

После фиксирования всех переменных zi мы получаем из (1)-(4) транспортную задачу T(z) и соответствующую ей двойственную задачу D(z) с переменными , которая имеет вид