Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Приведение открытой транспортной задачи к закрытой
|
|
В открытой или несбалансированной задаче имеет место неравенство 
.
Прежде чем решать такую задачу, необходимо привести ее к сбалансированному виду. В зависимости от ситуации сбалансировать задачу можно формальным способом без обращения к ЛПР или с привлечением дополнительной информации от ЛПР.
Пусть в исходной задаче предложение превышает спрос: 
Тогда условия задачи имеют вид 
(22) 
(23)
В каждое неравенство (22) введем дополнительную переменную xi, n+1. В сумме эти переменные должны равняться величине дебаланса: 
Добавляя это равенство к условиям (23), получаем закрытую задачу: 
Потребность bn+1 называют фиктивной. Таким образом, чтобы сбалансировать задачу, достаточно ввести фиктивного потребителя с потребностью, равной дебалансу. Практически это означает, что к исходной таблице добавляется один столбец с потребностью bn+1 и затратами Ci, n+1 =0. Ненулевые дополнительные переменные в оптимальном решении будут показывать количество груза, остающееся в соответствующих ПО.
Спрос превышает предложение: 
. При этом исходные условия записываются в виде: 
Введем в каждое неравенство дополнительную переменную xm+ 1, j. Очевидно, что сумма этих переменных равна величине дебаланса: 
С учетом этого равенства сбалансированная модель принимает вид: 
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
Такое преобразование соответствует введению фиктивного поставщика (дополнительной строки) с возможностью 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. Конец. Полученный план является оптимальным, если не содержит запрещенных перевозок (с затратами М).
|
|