Задача выбора (назначения) с матрицей А особого вида

, пусть элементы матрицы удовлетворяют следующим условиям:

1) В любой строке приращение между элементами матрицы

2) Строки расположены так, что

В этом случае оптимальное решение имеет следующий вид:

Пример

 

. Совершенно ясно, что .

Точные методы решения задач выбора

I. Метод линейного программирования

II. Вычислительная процедура динамического программирования

III. Венгерский метод

IV. Метод кратчайшего увеличивающегося пути (КУП)

V. Задача выбора с матрицей особого вида\

VI. Метод Мака

Метод линейного программирования

Предварительно проводится переиндексация переменных и коэффициентов матрицы:

           

Ограничения по строкам и столбцам:

dim A =100, .

Вычислительная процедура динамического программирования

Введем функцию Беллмана  - функция оптимального распределения К –работ между К -исполнителями, когда они имеют номера .

Функциональное уравнение Беллмана имеет вид:

Метод кратчайшего увеличивающегося пути (КУП)

Предположим, что существует оптимальное решение для матрицы , и его можно расположить по главной диагонали.

Перейдем к . Нужно добавить элемент для того, чтобы получить оптимальное решение.

Проанализируем пары:  и .

Рассмотрим разность: -  - условие включения элемента в решение.

Если min соответствует , следовательно, в решение включаем элементы  и .

Если min обеспечивается для , следовательно, в решение добавляем элемент .

Если решение для матрицы  будет оптимальным, то полученное решение будет оптимальным для матрицы .

В методе КУП последовательно наращивается порядок матрицы от 2 до n, в решение вводятся элементы по приведенным выше правилам.

Пример задачи выбора.

Пусть  дает решение .

Дополним до матрицы .

i =1 (25+1)-(5+5)=16

i =2 (20+2)-(8+5)=9

i =3 (15+3)-(9+5)=4

i =4 (10+4)-(8+5)=4

i =5 5-5=0

min=0  в решение попадает

Порядок: от 2 до n.

.

Приближенные методы решения задач выбора

1) Метод поэтапного выбора

2) Метод Фогеля

3) Метод КУП

4) Задача выбора и «жадный» алгоритм

5) Метод приращений

6) Метод min (max) элемента при минимизации (максимизации) (частный случай «жадного» алгоритма)

и т.д.

Метод поэтапного выбора

Подсчитывается сумма элементов в каждой строке, строки расположены в порядке убывания этих сумм.

К -тый шаг: в К-той строке отыскивается минимальный элемент и вносится в решение. Соответствующий этому элементу столбец исключаем из матрицы, .

Пример

    

Эта матрица особого вида, следовательно, уже знаем решение.

 - существует сигнал.

Метод Фогеля

1-ая итерация

1-ый шаг: в каждой строке определяется минимальный элемент и ближайший к нему элемент и составляются n -разностей.

2-ой шаг: в каждом столбце определяется минимальный и ближайший к нему элемент и составляются n -разностей.

3-ий шаг: Из 2 n элементов  и  выбирается максимальный. Пусть соответствующий элемент (  или ) есть .

2-ая итерация

Элемент  вносится в искомое решение.

3-я итерация

Строка k и столбец l удаляются из матрицы.

К -ая итерация

Аналогично, но матрица имеет порядок n - k.

 

Замечания:

1. Если среди элементов  и  одинаковые максимумы, то анализируются соответствующие им минимальные элементы строки (столбца), из них выбирается минимум.

2. Если и они одинаковые (  и ), то выбирается 1-ый элемент в порядке просмотра.

Пример (рассматривается специальная матрица, имеющая точное решение)

1-ая итерация:

 два одинаковых максимальных элемента и одинаковые соответствующие им минимальные элементы (6). Поэтому выбирается 1-ый элемент в порядке просмотра  - в решение ().

2-ая итерация:

- вносим в решение ()

3-я итерация:

 - в решение ()

4-ая итерация: