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

                                                  24

 - поиск максимального звена неоптимальности;
 - составление контура перераспределения ресурсов;
- определение минимального элемента в контуре перераспределения;
- перераспределение ресурсов по контуру и возврат к первому этапу.
    Описанная процедура повторяется несколько раз (итераций), пока не будет найдено
оптимальное решение. Вычислительный алгоритм для каждой итерации не меняется.
     Построение начального плана
    Опорный план – план перевозок, у которого число ненулевых перевозок N равно сум-
ме числа производителей и потребителей без единицы(N=m+n-1).
    Для транспортной задачи существует несколько методов отыскания начального плана
(опорного решения):
    • метод северо-западного угла;
    • метод минимальной стоимости по строке;
    • метод двойного предпочтения и т. д.

   Начальный план можно составить одним из перечисленных выше методов.
   Воспользуемся способом минимальной стоимости по строке, т.к. он дает начальный
план наиболее приближенный к оптимальному. Суть метода заключается в том, что начи-
ная с 1-й строки в каждой строке из всей строки выбирают клетку с наименьшей стоимо-
стью и в нее помещают меньшее из чисел ai и bj. Затем из рассмотрения исключают либо
строку, соответствующую поставщику, запасы которого полностью израсходованы, либо
столбец, соответствующий потребителю, потребности которого полностью удовлетворе-
ны, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены
потребности потребителя. Если у поставщика еще остались запасы, то из оставшейся час-
ти строки снова выбирают клетку с наименьшей стоимостью и в нее помещают меньшее
из чисел ai и bj. Далее переходят на следующую строку. Процесс распределения запасов
продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
   Итак, математическая модель процесса построения начального плана методом мини-
мальной стоимости по строке примет следующий вид:

   Для i=1..m выполнить:
        tai=ai.
   Для j=1..n выполнить:
        tbj=bj.
   jmin=1, j=1,cmin=c1,1;
   Для i=1..m выполнить:
       Пока tai>0:
                     j, сmin= сi,j, j=j+1, если cmin>сi,j и tbj <>0
           jmin =
                     jmin, j=j+1, если cmin<сi,j и tbj <>0;


                      tai, tai=0, tbjmin=tbjmin- tai, если tbjmin> tai и tai<>0
          pi,jmin=
                      tbjmin, tbjmin=0, tai=tai- tbjmin, если tbjmin< tai и tbjmin<>0.

   где jmin – j-координата элемента множества С с минимальной стоимостью транс-
портировки, jmin=1..n;
   tai – объем запасов у i-го поставщика. TA –рабочее множество запасов поставщиков;
   tbj – объем потребностей у j-го потребителя. TB – рабочее множество потребностей
потребителей;
   cmin – минимальная стоимость транспортировки;