Экономико-математическое моделирование в химии и экологии. Бутырская Е.В - 18 стр.

                                       18
выбираем клетку (2,3) и делаем в нее максимальную                 поставку 100 и
вычеркиваем вторую строку из рассмотрения, так как второй постащик весь
товар отдал, затем выбираем клетку (3,3) и делаем в нее поставку 30 ( так как
третьему потребителю нужно только 130 ед. груза, а 100 он уже получил), и
вычеркиваем третий столбец из рассмотрения, так как третий потребитель
получил весь товар. Далее опять выбираем клетку с к=1 – (3,1) и делаем в нее
поставку 160 ед., так как 30 ед третий постащик уже отдал, при этом из
рассмотрения вычеркивается третья строка. Затем 90 ед. ставим в клетку (1,4) и
вычеркиваем 4 столбец из рассмотрения. У нас остались две клетки, в которые
можно сделать поставки – (1,2) и (1,1). Делаем в них поставки 157 и 53. Если
распределение составлено правильно, то число заполненных клеток должно
равняться числу строк + число столбцов - единица.
Для проверки оптимальности распределения используется метод потенциалов,
который заключается в следующем. Пусть U i – потенциал i-й строки а Vj –
потенциал j-го столбца. Зададим потенциал первой строки U 1 – произвольно,
например, U1=0. Далее потенциалы Ui и Vj подбираем так, чтобы для
заполненных клеток Ui +Vj =Сij. Ui пишем справа от таблицы, а Vj – под
таблицей. Например, для клетки ( 1 , 1 ) имеем: U1 +V1 =5 , следовательно,
V1 =5 , так как U1=0. Находим все потенциалы и строим матрицу оценок клеток
                                              � 0 0 −3 0 �
                                               �              �
                                (        )
                       Dij =C ij − U i +V j =� 0 5 0 4 �
                                                 � 0 3 0 7�
                                                  �             �
Так как в матрице имеются отрицательные элементы, полученное
распределение не оптимально. Необходимо сделать поставку в клетку с
отрицательной оценкой, в данном случае (1,3). Делаем перестановку по циклу,
указанному пунктиром, включающему клетку (1,3). Цикл перестановки в
транспортной задаче представляет собой замкнутый многоугольник, одна
вершина которого находится в клетке, в которую, исходя из анализа матрицы
оценок клеток, необходимо сделать поставку. В данной задаче это клетка (1,3).
Этой вершине цикла присваивается знак +. Остальные вершины цикла
находятся в заполненных клетках, в каждой заполненной клетке, ломаная,
составляющая цикл, делает поворот на 90 градусов. В данном примере цикл
проходит через клетки (1,3), (3,3), (3,1) и (1, 1) . Далее делаем следующие шаги:
1. После выбора цикла перестановки в углах цикла расставляем знаки
следующим образом. От положительной вершины (1,3) переходим к соседней
вершине, чередуя знаки, присваиваемые вершинам цикла ( см. табл.1).
2. Среди отрицательных вершин цикла находим клетку с минимальной
поставкой клетки, (это клетка (3,3) с поставкой клетки 30).
3.На следующем шаге в положительные вершины цикла добавляем поставку 30,
а из клеток с отрицательными вершинами вычитаем поставку 30.
В результате получим распределение