Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Суммарные запасы (мощности) поставщиков и потребителей равны между собой (задача закрыта, или задача с правильным балансом).
Цикл клетки (i,j) – последовательность клеток таблицы ТЗ, определяемая ломаной линией, состоящей из вертикальных и горизонтальных звеньев. Начало и конец ломаной – в клетке (i,j), остальные вершины – в заполненных клетках таблицы.
Допустимое решение ТЗ является базисным тогда и только тогда, когда из заполненных им клеток таблицы нельзя образовать ни одного цикла.
Алгоритм решения ТЗ,
1) находим начальное базисное допустимое (опорное) решение, состоящее из (n+m+1) заполненных клеток таблицы поставок методом северо-западного угла или методом минимальной стоимости. Убеждаемся в его «опорности» методом вычёркивания рядов с одной заполненной клеткой из матрицы поставок.
2) проверяем оптимальность найденного решения (используя различные критерии оптимальности)
3) если найденное решение не оптимально, изменяем его, используя «сдвиг по циклу»: увеличиваем объём перевозок во всех нечётных клетках цикла и уменьшаем во всех чётных на величину ( равен наименьшему из объёмов перевозок в чётных клетках цикла). Переходим к пункту 2).
Построение начального решения:
В клетку (i,j) таблицы поставок вносим максимально возможный объём перевозки, равный оставшимся запасам i-го поставщика или неудовлетворённым потребностям j -го потребителя. Затем вычёркиваем из таблицы поставщика или потребителя, потребности которого полностью удовлетворены. (одна заполненная клетка таблицы – один вычеркнутый ряд матрицы).
Метод северо-западного угла: последовательнозаполняем правую верхнюю клетку таблицы поставок.
Метод минимальной стоимости – в первую очередь заполняем клетки с наименьшей стоимостью первозки.
Критерий оптимальности найденного решения распределительного метода.
Вычисляем оценку цикла для каждой свободной клетки таблицы поставок (складываем стоимости перевозок в нечётных клетках цикла и вычитаем стоимости в чётных клетках).
Если оценки циклов всех свободных клеток неотрицательны, найденное решение оптимально.
Дата публикования: 2015-03-26; Прочитано: 778 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!