Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Метод потенциалов для Td-задачи




Транспортная задача с ограниченными пропускными способностями отличается от T-задачи наличием ограничений сверху на перевозки: 0 £ xij £dij. Если задача не сбалансирована, то добавляют столбец или строку с нулевыми затратами, но с ∞ пропускной способностью. Начальное решение строят по правилу минимального элемента. Принцип определения значений переменных: на каждом шаге присваивается максимальное допустимое значение согласно формуле Xij=min(ост от ai, ост до bj, dij).

Если минимум достигается на dij, то не закрывается ни строка, ни столбец, и следует продолжать движение по строке или столбцу (если двигались по столбцу). Может оказаться, что в строке (столбце) больше нет открытых клеток, а она не закрыта - начальный план недопустимый. Если часть строк (столбцов) не закрыта, то обязательно не закроются и некот. столбцы (строки). Так как задача сбалансированная, то суммарная величина незакрытия строк = =g. Чтобы в этом случае завершить построение начального плана, добавляют фиктивного потребителя (столбец) и фиктивного поставщика (строку) с одинаковой потребностью и возможностью g. Так как их клетки соответствуют искусственным переменным, которые в разрешимой задаче должны стать равными нулю, затраты в них полагают бесконечно большими (М), а в клетке на пересечении фиктивного столбца с фиктивной строкой – равными нулю. Пропускные способности в фиктивных клетках не лимитируются. В процессе работы алгоритма план станет допустимым, когда все искусственные переменные обнулятся, то есть в юго-восточной клетке перевозка станет равна g. После построения начального плана определяются базисные клетки. Если их окажется меньше m+n-1(вырожденный план), то в число базисных включают переменные (клетки), равные нулю или dij. На базисных клетках не д строиться замкнутый цикл, иначе клетки добавлены неверно.

bj ai g=3
8 3 5 1 5 10 5 7 М
5 2 9 4 6 4 7 М
12 6 11 2 11 10 3 9 М
20 4 15 10 5 10 7 9 7 М 3
g=3 М М 1 М 2

Пример: Исходные данные задачи приведены в табл. В клетках слева даны пропускные способности, справа – затраты на перевозки. Задача сбаланс-я. Начальный план строим по правилу минимального элемента, порядок построения показан стрелками. Строка 4 и столбцы 2 и 3 не закрылись: g =3.

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

Так как общее число пунктов равно 9, то базисных переменных должно быть 8. Из сравнения значений xij и dij находим только 7 базисных переменных (базисные клетки закрашены), то есть план вырожденный. В качестве недостающей базисной клетки возьмем клетку 4,2, в которой значение переменной находится на верхней границе. Ни из каких базисных клеток нельзя построить замкнутый цикл.

Изменения на основном этапе алгоритма: Признак оптимальности в Td-задаче расширяется. При введении в решение небазисной переменной xij=0, то есть ее увеличении, критерий уменьшается при Dij>0 и увеличивается при Dij<0. Если же вводить переменную xij=dij, а это означает ее уменьшение, то критерий уменьшится при Dij<0 и возрастет при Dij>0. Этот характер изменения критерия показан на рис. Поэтому решение не может быть улучшено, если выполняются условия, составляющие признак оптимальности задачи с ограниченными пропускными способностями:

Если условия не выполняются хотя бы для одной небазисной клетки, решение может быть улучшено. Введем два множества: множество индексов переменных на нижней границе ; множество индексов переменных на верхней границе . Объединенное множество G= È является множеством индексов перспективных переменных (клеток): введение любой из них приведет к улучшению критерия. Выбор переменной, вводимой в базис, осуществляется на множестве G: При определении q0 необходимо учитывать обе границы: при вычитании нельзя вычесть больше, чем имеется, а при добавлении недопустимо превысить пропускную способность:

1. Если , цикл строится на клетке, в которой перевозка равна 0. Новый план получается прибавлением q0 в четных вершинах цикла и вычитанием в нечетных.

2. Если , цикл строится на клетке, в которой перевозка равна dij. В этом случае вводимая переменная должна уменьшаться. Перемещение по циклу состоит в вычитании q0 в четных вершинах и прибавлении в нечетных.

В обоих вариантах значение критерия улучшается на величину q0|Dkr|.

Алгоритм решения сбалансированной Тd-задачи включает следующие шаги:

1. Построение начального плана перевозок. План может получиться как допустимый, так и искусственный (недопустимый).

2. Выделение базисных клеток. Если их < m+n-1, + клетки на границе.

3. Нахождение потенциалов.

4. Вычисление оценок

5. Начало цикла. Определение множества G по матрицам плана и оценок.

6. Проверка признака оптимальности: если G=Æ, переход на шаг 10.

7. Определение вводимой переменной (клетки kr) и построение цикла пересчета.

8. Построение нового плана: вычисление q0 в зависимости от принадлежности kr и соответствующее перемещение по циклу.

9. Получение матрицы оценок нового плана с помощью преобразования матрицы оценок старого плана (как в Т-задаче). Переход на шаг 5.

10. Конец. Полученный план является оптимальным, если не содержит запрещенных перевозок (с затратами М).

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


Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой





Дата добавления: 2015-04-19; просмотров: 665. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.017 сек.) русская версия | украинская версия
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7