![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
В приведенном способе построения плана не участвовали затраты на перевозку. Следует ожидать, что учет затрат позволит получить начальный план, более близкий к оптимальному. Этим и отличается расматриваемое правило.
Первой заполняется клетка с минимальными затратами. Пусть min Cij = Ckp. Тогда Xkp =min(ak, bp). Если при этом закрывается строка k,то в столбце p ищем клетку с минимальными затратами и определяем значение соответствующей переменной согласно (5.13). При закрытии столбца p действуем аналогично в строке k. В общем случае клетка, лежащая в закрытом столбце и/или закрытой строке является закрытой, иначе – открытой. На каждом шаге движение идет либо по столбцу, либо по строке и при этом отыскивается среди открытых клетка с минимальным значением Cij.
Пример 5.2. Построим начальный план по правилу минимального элемента для задачи из примера 1. Результат представлен в табл. 5.3.
Таблица 5.3
Поставщик | Потребитель | Запасы груза | |||
B1 | B2 | B3 | B4 | ||
A1 |
5 ![]() |
60 ![]() |
35 ![]() | ||
A2 |
![]() ![]() |
75 ![]() | |||
A3 | |||||
Потребность в грузе |
При таком начальном плане L= 665, что меньше чем в примере 1. Однако нельзя утверждать, что для любых данных этот способ дает лучший план. Правильнеее говорить, что правило минимального элемента эффективнее в среднем (на множестве задач). В то же время алгоритм реализации этого правила сложнее, чем правила северо-западного угла.
Применяется также вариант, в котором на каждом шаге ищется клетка с минимальными затратами среди всех открытых клеток. Такой способ еще сложнее, но в среднем дает планы, более близкие к оптимальным.
Переход от одного плана перевозок к другому
Как и в симплекс-методе, новый план можно получить из исходного заменой одной базисной переменной. Клетки с базисными переменными будем называть базисными или занятыми, остальные – небазисными или свободными. Для перехода к новому плану используется замкнутая цепь, которая строится в матрице перевозок по следующим правилам.
Построение начинается со свободной клетки, которую соединяют с базисной в строке (столбце). Последнюю соединяют с базисной в столбце (строке). Далее, чередуя движение по строкам и столбцам, продолжаем соединение занятых клеток так, чтобы вернуться в начальную. При этом не требуется, чтобы цепь включала все базисные клетки. Угловые клетки цепи назовем вершинами цепи. Тогда правило построения замкнутой цепи можно сформулировать проще: начальная вершина должна быть в свободной клетке, остальные – в занятых.
![]() |
Кружком выделена начальная (небазисная) клетка цикла. Нумеровать вершины можно в любом направлении. И начинать можно с любой вершины. На рисунке нумерация проведена с клетки, смежной начальной. В этом случае начальная клетка всегда будет четной.
Теперь становится очевидным, что в каждой строке и каждом столбце, по которым проходит цикл пересчета, будет две и только две вершины: одна четная и одна нечетная. Если бы оказалось вершин больше двух, то из базисных клеток образовался бы цикл, что невозможно. В этом легко убедиться на примере: допустим, в правом цикле на рис. 5.2 отрезки 1-8 и 5-4 лежат в одной строке, тогда вершины 1, 4, 3 и 2 образуют цикл.
В результате цикл пересчета, построенный в допустимой матрице перевозок, обладает замечательным свойством: если перемещать по нему некоторое количество груза q >0, прибавляя его к Xij в четных вершинах и вычитая из Xij в нечетных, то условия задачи (5.3) и (5.4) не нарушатся. Чтобы новое решение было допустимым, то есть выполнялось и условие неотрицательности переменных, необходимо ограничить значение q:
q £ q0 =min Xij, ijÎ нечет. (5.14)
Здесь нечет – множество индексов переменных в нечетных вершинах цикла.
Для получения базисного решения (нового опорного плана) достаточно взять q = q0. При этом переменная свободной клетки, на которой строился цикл, становится базисной со значением q0, а переменная, доставляющая минимум в (5.14), обнуляется и переходит в небазисные.
Таким образом, переход от одного плана к другому в методе потенциалов заключается в построении цикла пересчета, определении q0 с последующим прибавлением к значениям переменных в четных вершинах и вычитанием в нечетных.Очевидно, что это значительно проще, чем в аналогичной процедуре симплекс-метода.
Дата публикования: 2015-01-23; Прочитано: 267 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!