![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Приведение открытой транспортной задачи к закрытой
В открытой или несбалансированной задаче имеет место неравенство Прежде чем решать такую задачу, необходимо привести ее к сбалансированному виду. В зависимости от ситуации сбалансировать задачу можно формальным способом без обращения к ЛПР или с привлечением дополнительной информации от ЛПР. Пусть в исходной задаче предложение превышает спрос: В каждое неравенство (22) введем дополнительную переменную xi, n+1. В сумме эти переменные должны равняться величине дебаланса: Добавляя это равенство к условиям (23), получаем закрытую задачу: Спрос превышает предложение: Такое преобразование соответствует введению фиктивного поставщика (дополнительной строки) с возможностью am+ 1 и нулевыми затратами Cm+ 1, j. Дополнительная переменная xm+ 1, j имеет смысл количества груза, недопоставленного j- му ПН. Алгоритм решения сбалансированной Тd-задачи: 1. Построение начального плана перевозок. План может получиться как допустимый, так и искусственный (недопустимый). 2. Выделение базисных клеток. Если их меньше m+n- 1, то добавляются клетки на границе. 3. Нахождение потенциалов из системы (18). 4. Вычисление оценок по формуле (19) 5. Начало цикла. Определение множества G по матрицам плана и оценок. 6. Проверка признака оптимальности: если G =Æ (эквивалент (25)), переход на шаг 10. 7. Определение вводимой переменной (клетки kr) по (5.26) и построение цикла пересчета. 8. Построение нового плана: вычисление q0 в зависимости от принадлежности kr по (27) или (28) и соответствующее перемещение по циклу. 9. Получение матрицы оценок нового плана с помощью преобразования матрицы оценок старого плана (как в Т-задаче). Переход на шаг 5. 10. Конец. Полученный план является оптимальным, если не содержит запрещенных перевозок (с затратами М).
|