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

UptoLike

ВУЗ: 

ИжГТУ им. Калашникова | Ижевск

Составители: 

Рубрика: 

26
Для j =1..n выполнить:
1, если загр(p
i,j
)=ист. и zb
j
=0 и za
i
=1
zb
j
=
zb
j
, если загр(p
i,j
)=лож или zb
j
<>0 или za
i
<>1;
c
i,j
– alfa
i
, если загр(p
i,j
)=ист. и zb
j
=0 и za
i
=1
betta
j
=
betta
j
, если загр(p
i,j
)=лож или zb
j
<>0 или za
i
<>1;
k+1, если загр(p
i,j
)=ист. и zb
j
=0 и za
i
=1
k =
k, если загр(p
i,j
)=лож или zb
j
<>0 или za
i
<>1.
Для i =1..m выполнить:
Для j =1..n выполнить:
1, если загр(p
i,j
)=ист. и za
j
=0 и zb
i
=1
za
j
=
za
j
, если загр(p
i,j
)=лож или za
j
<>0 и zb
i
<>1;
c
j,i
– betta
i
, если загр(p
i,j
)=ист. и za
j
=0 и zb
i
=1
alfa
j
=
alfa
j
, если загр(p
i,j
)=лож или za
j
<>0 и zb
i
<>1;
k+1, если загр(p
i,j
)=ист. и Za
j
=0 и Zb
i
=1
k =
k, если загр(p
i,j
)=лож или Za
j
<>0 и Zb
i
<>1.
Пока k<>m+n.
где alffa
i
– потенциал i-й строки, alffa
i
∈
ALFA. ALFA – множество строчных потен-
циалов;
betta
j
– потенциал j-й строки, betta
j
∈
BETA. BETA – множество столбцовых потен-
циалов;
za
i
– флаг, сигнализирующий о том, что у данной строки уже был рассчитан потен-
циал. za
i
∈
ZA – множество флагов для строк;
zb
j
– флаг, сигнализирующий о том, что у данного столбца уже был рассчитан по-
тенциал. za
i
∈ZA – множество флагов для столбцов.
Проверка плана на оптимальность
Проверяем план на оптимальность по незагруженным клеткам, используя следующее
неравенство:
Если для незагруженных клеток условие выполняется, то план - оптимальный.
Математическая модель процесса проверки плана на оптимальность имеет вид:
КОН = ист.
Для i =1..m выполнить:
Для j =1..n выполнить:
ист., если alffa
i
+ betta
j
<= с
i,j
и загр(p
i,j
)=лож и КОН<>лож
КОН =
лож, если alffa
i
+ betta
j
> с
i,j
и загр(p
i,j
)=лож.
Если КОН = ист., то x
i,j
= p
i,j
прекратить вычисления. 
                                                 26

          Для j =1..n выполнить:
                     1, если загр(pi,j)=ист. и zbj=0 и zai =1
             zbj =
                     zbj, если загр(pi,j)=лож или zbj<>0 или zai<>1;

                              ci,j – alfai, если загр(pi,j)=ист. и zbj=0 и zai =1
             bettaj =
                              bettaj, если загр(pi,j)=лож или zbj<>0 или zai<>1;

                       k+1, если загр(pi,j)=ист. и zbj=0 и zai =1
             k=
                       k, если загр(pi,j)=лож или zbj<>0 или zai<>1.

      Для i =1..m выполнить:
         Для j =1..n выполнить:
                      1, если загр(pi,j)=ист. и zaj=0 и zbi=1
             zaj =
                      zaj, если загр(pi,j)=лож или zaj<>0 и zbi<>1;

                              cj,i – bettai, если загр(pi,j)=ист. и zaj=0 и zbi=1
             alfaj =
                              alfaj, если загр(pi,j)=лож или zaj<>0 и zbi<>1;

                       k+1, если загр(pi,j)=ист. и Zaj=0 и Zbi=1
             k=
                       k, если загр(pi,j)=лож или Zaj<>0 и Zbi<>1.

   Пока k<>m+n.
   где alffai – потенциал i-й строки, alffai ∈ ALFA. ALFA – множество строчных потен-
циалов;
   bettaj – потенциал j-й строки, bettaj ∈ BETA. BETA – множество столбцовых потен-
циалов;
   zai – флаг, сигнализирующий о том, что у данной строки уже был рассчитан потен-
циал. zai ∈ ZA – множество флагов для строк;
   zbj – флаг, сигнализирующий о том, что у данного столбца уже был рассчитан по-
тенциал. zai ∈ ZA – множество флагов для столбцов.
   Проверка плана на оптимальность
   Проверяем план на оптимальность по незагруженным клеткам, используя следующее
неравенство:




   Если для незагруженных клеток условие выполняется, то план - оптимальный.
   Математическая модель процесса проверки плана на оптимальность имеет вид:
   КОН = ист.
   Для i =1..m выполнить:
      Для j =1..n выполнить:
                     ист., если alffai + bettaj <= сi,j и загр(pi,j)=лож и КОН<>лож
          КОН =
                    лож, если alffai + bettaj > сi,j и загр(pi,j)=лож.

   Если КОН = ист., то xi,j = pi,j прекратить вычисления.

Страницы