ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Galina O Ivanova                     2:5036/32.29   12 Jul 2001  10:04:32
 To : All
 Subject : Re: Matrix
 -------------------------------------------------------------------------------- 
 

 >  Имеется матрица n*n, все числа - байты, 15<n<150.
 >  Hеобходимо найти максимальную сумму по перестановке ( т.е. в каждой
 > строке и в каждом столбце надо чтобы выбран был ровно один элемент).
 
 Это есть задача о назначении. Очень частный случай ЗЛП, частн.сл. транспортной
 задачи. Соответственно, решается методами ТЗ (потенциалов, венгерским, 
 дифференциальных рент) и собственными методами, из которых могу назвать метод
 Мака (файл был набит по конспекту лекций):
 
 //---- начало mak.txt
  (Экономико-математические м-ды, Погодаев А.К., вес.сем 99г.)
  4. Задачи транспортного типа.
  4.2. Задача о назначении.
 
  Частнам случаем ТЗ является з-ча оптимального выбора, к-рую можно
 сформулировать след. образом: задано n работ, каждую из к-рых может
 выполнить любой из n исполнителей. Требуется распределить исполнителей по
 работам с целью минимизации общих затрат.
   Hайти min f(x) =  sum    sum   c_{ij} x_{ij},   x_{ij} e {0,1}
                    j=1..n i=1..n
      sum x_{ij} = 1, j = 1..n       sum x_{ij} = 1, i = 1..n
       i=1..n                        j=1..n
   Одним из м-дов реш-я з-чи о назначении является м-д Мака. Идея м-да
 заключается в логической процедуре распределения мин. эл-тов по столбцам
 м-цы затрат.
   Шаг 0. Подчеркнем в каждой строке м-цы С мин. эл-ты. Если в каждом
 столбце имеется по 1-му мин.эл-ту, то план оптимален, иначе на шаг 1.
   Шаг 1. Представим м-цу C в виде 2-х матриц [ A | A' ], где A = \emptyset,
 A' = C.
   Шаг 2. Выбрать из A' столбец, содержащий более одного подчеркнутого
 эл-та и перевести его в м-цу A.
   Шаг 3. Пусть мин. подчеркнутый эл-т в i-й строке равен a_i (в м-це A), а 
 мин. неподчеркнутый в A' -- {a'}_i. найдем min (a'_i - a_i) = a'_r - a_r,
                                             i
 \forall i=1..n a'_i > a_i
   Шаг 4. Увеличиваем все значения м-цы A на a'_r - a_r. 
   Шаг 5. Отметим a_r точками.
   Шаг 6. Пусть k - столбец, содержащий a'_r. Если в k содержатся другие
 подчеркнутые элементы, перевести k из A' в A и перейти к шагу 3. Иначе - к 
 шагу 7 и далее.
   Шаг 7. Подчеркнуть a'_r полностью (это новый подчеркнутый элемент).
   Шаг 8. Hайти исходный подчеркнутый элемент в той же строке, что a'_r,
 убрать подчеркивание. Пусть он находился в столбце l.
   Шаг 9. Если l не содержит других подчеркнутых элементов, то он должен
   содержать эл-т, отмеченный точками. Обозначить этот эл-т как a'_r и
   перейти на шаг 7. Если l содержит другие подчеркнутые эл-ты, и остался
   столбец в С без подчеркнутых элементов, то перейти к шагу 1, убрав
   подчеркивание с точками. Если в С в каждом столбце имеется
   подчеркивание, то решение найдено.
 //----- конец mak.txt
 Максимизацию можно заменить на минимизацию, вычтя все элементы матрицы 
 из некоторого достаточно большого положительного числа.
 
 С уважением,
 Галина О. Иванова
 --- tin/1.4.1-19991201 ("Polish") (UNIX) (Linux/2.2.14-15mdk (i586))
  * Origin: -= HomeNet =- (2:5036/32.29@fidonet)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Matrix   Kluchnikov Eugene   11 Jul 2001 22:34:44   Re: Matrix   Andrew Ezhguroff   12 Jul 2001 03:07:04   Re: Matrix   Andrzej Novosiolov   12 Jul 2001 13:39:39   Matrix   Kluchnikov   12 Jul 2001 13:29:16   Re: Matrix   Galina O Ivanova   12 Jul 2001 10:04:32   Matrix   Kluchnikov Eugene   12 Jul 2001 22:07:23   Re: Matrix   Andrzej Novosiolov   12 Jul 2001 15:23:14   Matrix   Dan Raskovalov   15 Jul 2001 23:36:44   Re: Matrix   Ihor Bobak   16 Jul 2001 14:51:37