ТРАНСПОРТНАЯ ЗАДАЧА

Постановка задачи: имеется n вакантных должностей и m претендентов на эти места. Эффективность i-го претендента на j-ой должности равна V(i,j). Требуется назначить претендентов таким образом, чтобы их совместная эффективность была максимальной.

Или же: вред от i-го претендента на j-ой должности равен V(i,j). Требуется назначить претендентов таким образом, чтобы совокупный вред оказался минимальным.

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

Рассмотрим решение задачи, если требуется минимизировать вред. В противном случае (в случае задачи максимизации эффективности) выберем число M, большее любого элемента матрицы V, и составим новую матрицу V', элементы которой соответственно будут равны: V'(i,j)=M-V(i,j).

Если матрица V не квадратная, дополняем ее нужным числом нулевых рядов. (Под рядом будем понимать строку или столбец).

1. Приводим матрицу следующим образом: уменьшаем элементы каждой строки на число, равное минимальному элементу данной строки. То же самое делаем и для столбцов. В получившейся матрице каждая строка и каждый столбец должны содержать хотя бы по одному нулю. 2. Ищем решение с нулевым значением. Для этого берем 1-ю строку; отметим один из нулей, остальные нули зачеркиваем и зачеркиваем нули в том столбце, где отметили ноль. То же делаем со всеми последующими строками.

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

Если максимальное паросочетание дает насыщенную матрицу назначений, то решение найдено: номер строки каждого из отмеченных нулей соответствуют номеру претендента, а номер строки - номеру должности, на которое следует его назначить.

В противном случае переходим к пункту 4.

4. Нахождение минимальной опоры - минимального множества рядов, содержащего все ее нули.

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

Строки берем помеченные, а столбцы - непомеченные, и выбранное отмечаем пунктиром. "Пунктирные" ряды и составляют минимальную опору.

5. Перестановка нулей.

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

6. Переходим к пункту 2.

ОРИСФЕРЫ

В наше время любой грамотный человек знает, что есть такая странная неевклидова геометрия - геометрия Лобачевского. Она была создана нашим соотечественником - Никола ем Ивановичем Лобачевским. Её открытие и революционная идея о том, что возможны разные и равноправные геометрии, произвели переворот не только в математике, но и в представлениях людей об окружающем мире (см. статью "Геометрия Лобачевского"). И тем не менее в повседневной жизни и даже на уроках геометрии в школе нам не приходится с ней сталкиваться, поэтому не все представляют себе, что же на самом деле придумал Лобачевский. А между тем одну из неевклидовых геометрий ко времени открытия Лобачевского давно знали и хорошо изучили. Речь идёт о сферической геометрии, в которой рассматриваются фигуры на сфере и соотношения между ними.

Согласно античной модели мироздания, звёзды и планеты располагаются на нескольких сферах с общим центром, в котором находится Земля. При этом звёзды неподвижны, как бы "прибиты" к своей сфере и вращаются вместе с ней вокруг Земли, а планеты на собственных сферах выписывают замысловатые фигуры - ведь само слово "планета" в переводе с греческого означает "блуждающая". С помощью такой геоцентрической модели древние научились достаточно точно описывать и предсказывать движения планет. Это было необходимо, например, в мореплавании да и во всех областях "земной" деятельности человека, где надо учитывать, что под ногами у нас шар, а не плоский блин на трёх китах. При изучении закономерностей вращения небесных светил возникли разнообразные математические задачи, связанные со свойствами сферы и фигур, которые об разуют на ней большие окружности.

Поскольку сфера находится в обычном трёхмерном евклидовом пространстве, теоремы сферической геометрии можно пони мать как обыкновенные стереометрические. Поэтому в сферической геометрии не видели "другую планиметрию", и она не привела к ниспровержению устоявшихся взглядов подобно геометрии Лобачевского. Между тем, если при смотреться к сфере внимательнее - а для этого подойдёт обыкновенный глобус, - легко обнаружить немало удивительного.

Возьмите нить и натяните её между двумя пунктами на глобусе. Она пройдёт по кратчайшей линии на сфере, соединяющей эти пункты и укажет, в частности, наилучший маршрут дл самолёта. Если вы проложите такой маршрут из Москвы в Нью-Йорк, находящийся пример но на одной широте с Баку, то обнаружите, что путь лайнера проходит севернее, чем, возможно, вы ожидали, - через Скандинавию и близко от Гренландии. Что же это за линия? Ответ станет ясен, если взять точки на экваторе. Тогда и вся нить пройдёт по экватору. Экватор является одной из больших окружностей сферы, т. е. окружностей наибольшего радиуса. Они образуются при пересечении сферы её диаметральными, проходящими через центр, плоскостями. Из других линий на глобусе кроме экватора большие окружности образуют так же меридианы (рис. 1).

Рис. 1

Именно большим окружностям и отводится роль прямых в сферической геометрии. Как правило, через две точки на сфере, как и на плоскости, можно провести только одну сферическую прямую. Исключение составляют диаметрально противоположные точки: например, через полюсы на глобусе проходит бесконечно много меридианов. Но в отличие от обычной геометрии любые две сферические прямые пересекаются в двух диаметрально противоположных точках -

Примечаний нет.