Моделирование и оптимизация. Кучина Т.Л. - 27 стр.

                                              27

   где КОН – признак конца процесса вычисления, если КОН = ист., то это значит, что
получен оптимальный план.

   Поиск максимального звена неоптимальности
    Максимальное звено неоптимальности находится как max(αi + βj - сi,j) среди незагру-
женных клеток.
    Эту клетку необходимо загрузить за счет перераспределения ресурсов из других за-
груженных клеток. Клетку в таблице помечаем знаком "+", так как здесь в начальном пла-
не находится вершина максимальной неоптимальности.
    Математическая модель данного процесса примет следующий вид:
    iмзн = 1;
    jмзн = 1;
    МЗН =с 11 .
    Для i =1..m выполнить:
       Для j =1..n выполнить:
                      i, МЗН = alffai + bettaj – сi,j, если alffai + bettaj – сi,j >= МЗН
           iмзн =
                     iмзн, если alffai + bettaj – сi,j < МЗН;

                    j, МЗН = alffai + bettaj – сi,j, если alffai + bettaj – сi,j >= МЗН
          jмзн =
                    iмзн, если alffai + bettaj – сi,j < МЗН.

    где jмзн, iмзн – j и i координаты максимального звена неоптимальности;
    МЗН – значение максимального звена неоптимальности.
   Составление контура перераспределения ресурсов
    Контур перераспределения ресурсов составляют по следующим правилам:
    • этот контур представляет замкнутый многоугольник с вершинами в загруженных
клетках, за исключением клетки с вершиной максимальной неоптимальности "+", и звень-
ями, лежащими вдоль строк и столбцов матрицы;
    • ломаная линия должна быть связанной в том смысле, что из любой ее вершины
можно попасть в любую другую вершину по звеньям ломаной цепи (по строке или по
столбцу);
    • в каждой вершине контура встречаются только два звена, одно из них располагает-
ся по строке, другое - по столбцу;
    • число вершин контура четное, все они в процессе перераспределения делятся на за-
гружаемые и разгружаемые;
    • в каждой строке (столбце) имеются две вершины: одна - загружаемая, другая - раз-
гружаемая.
    Математическая модель данного процесса примет следующий вид:
    Для i =1..m выполнить:
       Для j =1..n выполнить:
           tpi,j = pi,j
    Пока КНЦ = лож выполнять:
       КНЦ = ист.;
        Для i=1..m выполнить:
           Для j=1..n выполнить:
                        0, КНЦ = лож, если загр(tpi,j) и ВССЕ(i,j) = лож
             tpi,j =
                        tpi,j, если загр(tpi,j) и ВССЕ(i,j) = лож.
    k=1, ui1 = iмнз, uj1 = jмнз;