 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Правило 4. Потенциальной называется незагруженная клетка, у которой сумма вспомогательных коэффициентов строки и столбца больше проставленного в ней расстояния
|
|
Рассматриваем последовательно незагруженные клетки. Такой первой клеткой является А1Б1, расстояние которой равно 12. Эта клетка имеет вспомогательные коэффициенты строки и столбца 8 и 12. Сумма вспомогательных коэффициентов 8+12=20 будет больше расстояния, проставленного в этой клетке. Разница между суммой вспомогательных коэффициентов и расстоянием в клетке будет 20-12=8. Эта величина называется потенциалом и проставляется в клетке в кружочке.
Проверяем последовательно остальные незагруженные клетки и устанавливаем, что в матрице все незагруженные клетки потенциальные. Матрица №5 с проставленными потенциалами показана на рисунке 5.
| Потреб. | Коэф | Поставщик | Потреб. в грузе, т | |||||
| А1 | А2 | А3 | ||||||
| Б1 | ||||||||
| Б2 | ||||||||
| Б3 | -1 | |||||||
| Б4 | ||||||||
| Наличие груза, т |
Рисунок 5 – Матрица №5 с обозначенными величинами потенциалов
Наличие потенциальных клеток в матрице свидетельствует о том, что составленный вариант закрепления получателей за поставщиками не является оптимальным и может быть улучшен. Улучшение варианта закрепления получателей за поставщиками производится при помощи контура.
Правило 5. Контур представляет собой замкнутую ломаную линию, состоящую из попеременных отрезков вертикальных и горизонтальных прямых, вершины которых находятся в загруженных клетках; началом контура является клетка с наибольшим по величине потенциалом; отрезки контура должны проходить через возможно большее число загруженных клеток, но не менее двух, считая и потенциальную; линии контура должны замкнуться в потенциальной клетке, из которой контур взял свое начало; вершины перегиба линий контура должны лежать только в загруженных клетках и угол перегиба должен быть прямым, т.е. составлять 90°. Вершины перегибов линий контура обозначаются попеременно знаками плюс и минус, причем первый минус ставится в потенциальной точке. В каждой матрице из данной потенциальной клетки можно провести только один контур.
На матрице №6 показаны линии контура для данного случая.
| Потреб. | Коэф | Поставщик | Потреб. в грузе, т | |||||
| А1 | А2 | А3 | ||||||
| Б1 | ||||||||
| Б2 | ||||||||
| Б3 | -1 | |||||||
| Б4 | ||||||||
| Наличие груза, т |
Рисунок 6 – Матрица №6 с нанесенным контуром
Следующим этапом решения задачи является отыскание минимального числового значения нагрузки в клетках, где вершины контура имеют знак плюс. Нагрузку в 160 единиц переносим из клетки со знаком плюс в клетку со знаком минус и добавляем к тому числу, которое там уже находилось. Затем из следующей клетки со знаком плюс отнимаем это число и переносим далее по линии контура в клетку со знаком минус и так далее до потенциальной клетки.
Перенесем цифру 160 из клетки А1Б4 (+) в клетку А1Б1 (-) и добавляем ее к той величине, которая в ней имелась. Тогда цифра загрузки в клетке А1Б4 будет равна 0, а в клетке А1Б1 – 160 единиц. Из клетки А3Б1 (+) отнимаем цифру 160 и переносим ее клетку А3Б4 (-), тогда в ней окажется загрузка, равная 160,а в А3Б1 останется 220 единиц.Новый план закрепления получателей за поставщиками показан в матрице №7 (рисунок 7).
| Потреб. | Коэф | Поставщик | Потреб. в грузе, т | |||||
| А1 | А2 | А3 | ||||||
| Б1 | ||||||||
| Б2 | ||||||||
| Б3 | -1 | |||||||
| Б4 | ||||||||
| Наличие груза, т |
Рисунок 7 – Матрица №7. Улучшенный план закрепления потребителей за поставщиками
В результате проведенных действий произошло следующее
1) при переносе 160 единиц из клетки А1Б4 в клеткуА1Б1 расстояние перевозки уменьшилось на 2 км (14-12=2);
2) при переносе 160 единиц из клетки А3Б1 в клетку А3Б4 расстояние перевозки увеличилось на 6 км (11-5=6).
В связи с тем, что уменьшение расстояния численно равно потенциалу, контур следует начинать из клетки с наибольшим значением потенциала.
Продолжаем исследование матрицы №7. Проверяем ее на число загруженных клеток. Оно равно 5, поэтому загружаем клетку А2Б2 нулевой нагрузкой.
Пользуясь предыдущими правилами, отыскиваем вспомогательные коэффициенты строки и столбца и подставляем их в матрицу. Такими коэффициентами будут: А1-6, А2-7, А3-5, Б1-6, Б2-5, Б3-5, Б4-0.
Проверяем матрицу на потенциальность (матрица №8, рисунок 8).
| Потреб. | Коэф | Поставщик | Потреб. в грузе, т | |||||
| А1 | А2 | А3 | ||||||
| Б1 | ||||||||
| Б2 | ||||||||
| Б3 | ||||||||
| Б4 | ||||||||
| Наличие груза, т |
Рисунок 8 – Матрица №8 с нанесенным контуром
Перенесем цифру 160 из клетки А1Б1 (+) в клетку А2Б1 (-) и добавляем ее к той величине, которая в ней имелась. Тогда цифра загрузки в клетке А1Б1 будет равна 0, а в клетке А2Б1 – 160 единиц. Из клетки А2Б2 (+) отнимаем цифру 160 и переносим ее клетку А1Б2 (-), тогда в ней окажется загрузка, равная 160.
Новый план закрепления получателей за поставщиками показан в матрице №9 (рисунок 9).
| Потреб. | Коэф | Поставщик | Потреб. в грузе, т | |||||
| А1 | А2 | А3 | ||||||
| Б1 | ||||||||
| Б2 | ||||||||
| Б3 | ||||||||
| Б4 | ||||||||
| Наличие груза, т |
Рисунок 9 – Матрица №9. Улучшенный план закрепления потребителей за поставщиками.
В результате проведенных действий произошло следующее
1) при переносе 160 единиц из клетки А1Б1 в клеткуА2Б1 расстояние перевозки увеличилось на 1 км (13-12=1);
2) при переносе 160 единиц из клетки А2Б2 в клетку А1Б2 расстояние перевозки увеличилось на 9 км.
Продолжаем исследование матрицы №9. Проверяем ее на число загруженных клеток. Оно равно 6, т.е. соответствует правилу.
Пользуясь предыдущими правилами, отыскиваем вспомогательные коэффициенты строки и столбца и подставляем их в матрицу. Такими коэффициентами будут: А1-5, А2-8, А3-6, Б1-5, Б2-4, Б3-6, Б4-(-1).
Проверяем матрицу на потенциальность (матрица №10, рисунок 10).
| Потреб. | Коэф | Поставщик | Потреб. в грузе, т | |||||
| А1 | А2 | А3 | ||||||
| Б1 | ||||||||
| Б2 | ||||||||
| Б3 | ||||||||
| Б4 | -1 | |||||||
| Наличие груза, т |
Рисунок 10 – Матрица №10 с нанесенным контуром
Перенесем цифру 150 из клетки А2Б2 (+) в клетку А2Б3 (-) и добавляем ее к той величине, которая в ней имелась. Тогда цифра загрузки в клетке А2Б2 будет равна 0, а в клетке А2Б3 – 150 единиц. Из клетки А1Б3 (+) отнимаем цифру 150 и переносим ее клетку А1Б2 (-), тогда в ней окажется загрузка, равная 310.
Новый план закрепления получателей за поставщиками показан в матрице №11 (рисунок 11).
| Потреб. | Коэф | Поставщик | Потреб. в грузе, т | |||||
| А1 | А2 | А3 | ||||||
| Б1 | ||||||||
| Б2 | ||||||||
| Б3 | ||||||||
| Б4 | -1 | |||||||
| Наличие груза, т |
Рисунок 11 – Матрица №11. Улучшенный план закрепления потребителей за поставщиками
В результате проведенных действий произошло следующее
1) при переносе 150 единиц из клетки А2Б2 в клеткуА2Б3 расстояние перевозки увеличилось на 1 км (13-12=1);
2) при переносе 150 единиц из клетки А1Б3 в клетку А1Б2 расстояние перевозки уменьшилось на 2 км (11-9=2).
Продолжаем исследование матрицы №11. Проверяем ее на число загруженных клеток. Оно равно 5, поэтому загружаем клетку А1Б3 нулевой нагрузкой.
Пользуясь предыдущими правилами, отыскиваем вспомогательные коэффициенты строки и столбца и подставляем их в матрицу. Такими коэффициентами будут: А1-5, А2-7, А3-5, Б1-6, Б2-4, Б3-6, Б4-0.
Проверяем матрицу на потенциальность (матрица №12, рисунок 12).
| Потреб. | Коэф | Поставщик | Потреб. в грузе, т | |||||
| А1 | А2 | А3 | ||||||
| Б1 | ||||||||
| Б2 | ||||||||
| Б3 | ||||||||
| Б4 | ||||||||
| Наличие груза, т |
Рисунок 12 – Матрица №12.Оптимальный план закрепления
получателей за поставщиками.
В матрице №12 нет потенциальных клеток, что свидетельствует о получении оптимального плана закрепления получателей за поставщиками:
1) поставщик А1 будет поставлять груз получателю Б2 в количестве 310 единиц на расстояние 9 км (шифр А1Б2);
2) поставщик А2 будет поставлять груз получателю Б1 в количестве 160 единиц на расстояние 12 км (шифр А2Б1), а также получателю Б3 в количестве 150 единиц на расстояние 13 км (шифр А2Б3);
3) поставщик А3 будет поставлять груз получателю Б1 в количестве 220 единиц на расстояние 11 км (шифр А3Б1), а также получателю Б4 в количестве 160 единиц на расстояние 5 км (шифр А3Б4).
Рассмотрим итоги решения задачи на закрепление получателей за поставщиками.
Среднее расстояние перевозки груза определяется из выражения
, (6)
Где: Q - единицы груза транспортируемые от поставщика к
потребителю;
l - расстояние на которое транспортируется груз.
Тогда при первичном плане закрепления получателей за поставщиками среднее расстояние перевозки
при вторичном
при третьем
при оптимальном плане
Уменьшение среднего расстояния перевозки в процентах определится по формуле
, (7)
Где: l - среднее расстояние перевозки при первичном плане;
l - среднее расстояние перевозки при последующих улучшенных
планах.
Тогда уменьшение среднего расстояния перевозки при вторичном плане составит
при третьем
а при оптимальном плане по отношению к первичному
Таким образом, каждый последующий вариант закрепления получателей за поставщиками дает все меньшие значения уменьшения среднего расстояния перевозки и поэтому при решении сложных и громоздких задач можно не добиваться оптимального варианта, а ограничиться двумя-тремя вариантами улучшения плана.
Дата публикования: 2015-02-20; Прочитано: 1077 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
