Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур

взял свое начало; вершины перегиба линий контура должны лежать только в загруженных клетках и угол перегиба должен быть прямым, т.е. составлять 90°. Вершины перегибов линий контура обозначаются попеременно знаками плюс и минус, причем первый минус ставится в потенциальной клетке.

В каждой матрице из данной потенциальной клетки можно провести только один контур.

Потребитель Вспомога- тельные Поставщик  
Строка   Столбец А1 А2 А3 Потребность в грузе, т
Б1        
Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru 434 +   Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru _ (22)      
Б2 -11   Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru _  
    + 434    
Б3 -4 _      
Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru 0   (9)   + 210  
Б4 -13        
         
Наличие груза, т

Рисунок 6.-Матрица №6 с нанесённым контуром.

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

А3Б3. Минимальную загрузку в 210 единиц переносим из клетки со знаком плюс в клетку со знаком минус и добавляем к тому числу, которое там уже

имелось. Затем из следующей клетки со знаком плюс отнимаем это число и переносим далее по линии контура в клетку со знаком минус и так далее до потенциальной клетки.

Перенесем число 210 из клетки А3Б3 (+) в клетку А3Б2 (-) и добавим ее к той величине, которая в ней имелась. Тогда цифра загрузки в клетке А3Б3 будет равна нулю, а в клетке А3Б3 - 210 единицам. Из клетки А2Б2 (+) отнимаем число 210 и переносим ее в клетку А2Б1 (-), тогда в ней окажется загрузка, равная 210, а в А2Б2 останется 224. Из клетки А1Б1 (+) переносим число 210 в клетку А1Б3 (-).

Новый план закрепления получателей за поставщиками показан на матрице №7 (рисунок 7).

Потребитель Вспомога- тельные Поставщик  
Строка Столбец А1 А2 А3 Потребность в грузе, т
     
Б1          
       
Б2          
       
Б3          
         
Б4          
         
Наличие груза, т


Рисунок 7.-Матрица №7-улучшенный план закрепления получателей за поставщиками.

В результате проведенных действий произошло следующее; при переносе 210 единиц из клетки А3Б3 в клетку А3Б2 расстояние перевозки уменьшилось на 7 км (12-5=7); при переносе числа 210 из клетки А2Б2 в клетку А2Б1 расстояние перевозки уменьшилось на 11 км (17-6 = 11). Из клетки А1Б1 в А1Б3 уменьшилось на 4км (12-8=4).Таким образом, общее уменьшение расстояния перевозки 210 единиц груза составило 7+11+4=22

км, т.е. оно численно равно величине потенциала потенциальной клетки, из которой контур взял свое начало.

В связи с тем, что уменьшение расстояния перевозок численно равно потенциалу, контур следует начинать из клетки с наибольшим значением потенциала.

Продолжаем исследование матрицы №7. Проверяем ее на число загруженных клеток. Оно равно 6, т.е. соответствует правилу, при котором число загруженных клеток должно быть равно 4+3-1=6.

Пользуясь предыдущими правилами, отыскиваем вспомогательные коэффициенты строки и столбца и подставляем их в матрицу. Такими коэффициентами будут :для Б1- 0; Б2-11; БЗ- (-4); Б4-9; А1-12; А2-6; А3-(-6).

Проверяем матрицу на потенциальность и устанавливаем, что в ней имеется две потенциальные клетки: А1Б2; А1Б4; (матрица №8, рисунок 8). Строим контур, который выйдет из клетки А1Б2, т.к. это клетка с наибольшим потенциалом, пойдет в клетки А2Б2, А2Б1, А1Б1 и замкнется в клетке А2Б2. На вершинах контура проставляем знаки минус и плюс, причем первый минус ставится в потенциальной.

Потребитель Вспомога- Тельные Поставщик  
Строка Столбец А1 А2 А3 Потребность в грузе, т
-6
Б1   _    
Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru 224+        
Б2 -11        
(10) _   + 224    
Б3 -4        
         
Б4        
(9)        
Наличие груза, т

Рисунок 8.-Матрица №8- с нанесенным контуром

В результате проведенных действий произошло следующее; при переносе 224 единиц из клетки А2Б2 в клетку А2Б1 расстояние перевозки уменьшилось на 11 км (17-6=11); при переносе числа 224 из клетки А1Б1 в клетку А1Б2 расстояние перевозки увеличилось на 1 км (12-13=-1). Таким образом, общее уменьшение расстояния перевозки 224 единиц груза составило 11-1=10 км, т.е. оно численно равно величине потенциала потенциальной клетки, из которой контур взял свое начало.

В связи с тем, что уменьшение расстояния перевозок численно равно потенциалу, контур следует начинать из клетки с наибольшим значением потенциала.

Продолжаем исследование матрицы №8. Проверяем ее на число загруженных клеток. Оно равно 5, т.е. не соответствует правилу, при котором число загруженных клеток должно быть равно 4+3-1=6. Вводим нулевую загрузку в А1Б4.

Пользуясь предыдущими правилами, отыскиваем вспомогательные коэффициенты строки и столбца и подставляем их в матрицу. Такими коэффициентами будут для Б1- 0; Б2-10; БЗ-5; Б4-9; А1-3; А2-6; А3-(-5).

Новый план закрепления получателей за поставщиками показан на матрице №9 (рисунок 9).

Потребитель Вспомога- тельные Поставщик  
Строка Столбец А1 А2 А3 Потребность в грузе, т
-5
Б1        
         
Б2        
       
Б3        
         
Б4        
       
Наличие груза, т

Рисунок 9.-Матрица №9-оптимальный план закрепления получателей за поставщиками.

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

1. Поставщик А1 будет поставлять продукцию потребителю Б3 в количестве 210 единиц на расстояние 8 км и потребителю Б2 в количестве 224 единицы на расстояние13 км;

2. Поставщик А2 будет поставлять продукцию потребителю Б1 в количестве 434 единицы на расстояние 6 км и потребителю Б4 в количестве 196 единицы на расстояние15 км;

3. Поставщик А3 будет поставлять продукцию потребителю Б2 в количестве 210 единиц на расстояние 5 км

Расшифрованный оптимальный план перевозок передают в диспетчерскую для определения дневных заданий шоферам и выписки путевых листов.

Рассмотрим итоги решения задачи на закрепление получателей за поставщиками.

Среднее расстояние перевозки груза определяется:

Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru , (9)

где Q – количество перевозимого груза, указанного в клетке рассматриваемой матрицы, т;

Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru - расстояние между поставщиком и получателем, соответствующие грузу Q, км.

Уменьшение среднего расстояния перевозки в процентах определяется:

Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru , (10)

где Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru и Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru - среднее расстояние перевозки, соответственно, при первичном и улучшенном плане закрепления получателем за поставщиками, км

При первичном плане закрепления получателей за поставщиками среднее расстояние перевозки

Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru ;

при вторичном плане

Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru

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

Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru

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

В практике решения задач матрицу наносят на плотный лист бумаги, цифры в нее проставляют карандашом, при переносе цифр ненужные стирают, а вместо них записывают новые. Таким образом, вся задача решается на одной матрице в описанной ранее последовательности.

При оптимальном плане закрепления среднее расстояние перевозки составит:

Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru

уменьшение среднего расстояния перевозки при оптимальном плане закрепления составило

Загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в отрицательной клетке, из которой контур - student2.ru

Наши рекомендации