Линейное математическое программирование, страница 31

            Число уравнений для определения потенциалов поставщика и потребителя равно числу базисных клеток, т.е. , а число неизвестных в уравнениях равно , т.е. на единицу больше цикла уравнений. Поэтому при определении указанных потенциалов полагается .

            Определяем потенциалы поставщиков u_i и потребителей v_j по формуле (7.3)

             при                     

                    

                   

                   

                   

                   

            Заносим найденные потенциалы в таблицу 7.8. По формуле (7.4) определяем потенциалы свободных клеток.

           

           

           

           

           

           

            План перевозки, представленный в таблице 7.8, не оптимальный, т.к. потенциалы двух клеток (1,1) и (1,3) отрицательны.

            План перевозки следует улучшить за счет перераспределения груза. Перераспределение груза осуществляется по так называемому циклу пересчета.

            Цикл пересчета составляется для той свободной клетки, потенциал которой является наименьшим. В рассматриваемом случае наименьший потенциал, равный «-1», имеют клетки (1,1) и (1,3). Составим цикл пересчета для любой из них, например, для клетки (1,1).

            Цикл пересчета – это замкнутая ломаная линия, соединяющая между собой несколько клеток, отвечающая следующим условиям:

1. среди клеток цикла одна является свободная, для которой строится цикл, остальные базисные;
2. в каждой клетке ломаная делает поворот на 90^о;
3. свободной клетке присваивается знак «+», знаки остальных клеток чередуются. Цикл, клетки которого имеют знаки, называется означенным.

            Составим цикл пересчета для клетки (1,1)

 

            Определяем величину перемещения поставки по циклу из условия минимума среди поставок в клетках цикла со знаком «-» min (20;60;10) = 10. Увеличиваем на 10 единиц поставки в клетки со знаком «+» и уменьшаем в клетках со знаком «-». Получаем таблицу 7.9.

Таблица 7.9