Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


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


Начало. Разбить множество всех столбцов на два подмножества А и А’, где А — выбранное множество столбцов, А — невыбранное множество столбцов (при этом в начале каждой итерации выбранных столбцов нет, т.е. подмножество А пустое, а под-множество А содержит все столбцы).


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


Шаг 2. В каждой строке рассчитать разность Ri:


R = minlcl]ai,    (28)


где min cij — минимальный элемент i-й строки среди элементов множества А (минимальный элемент среди невыбранных элементов строки); ai — подчеркнутый элемент i-й строки. При этом в строках, где среди выбранных элементов (элементов множества А) нет подчеркнутых, такой разности не будет.


Среди найденных разностей определить минимальную: min Ri.


Шаг 3. Прибавить min Ri ко всем элементам множества А.


Шаг 4. Условно подчеркнуть (например, тремя точками) в j-м столбце min Cj’ множества А, из которого вычитали а, чтобы получить min R


Если в j-м столбце нет подчеркнутых элементов, то сделать это условное подчеркивание явным, прежнее подчеркивание в этой строке удалить. В итоге получим новый подчеркнутый элемент. Далее вернуться к Началу и начать новую итерацию.

Скачать в pdf «Экстремальные модели менеджмента и экономики»