Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Методика перехода к лучшему опорному решению
Наличие положительной оценки свободной клетки (D ij ≥ 0) при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально, и для уменьшения значения целевой функции надо перейти к другому опорному решению. При этом надо перераспределять грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых – свободной. Для свободной клетки, имеющей максимальную положительную величину оценки, , строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках, углы прямые, число вершин четное. Форма цикла может быть разной, например: Но для клетки с положительной оценкой он является единственным. Около свободной клетки цикла ставится знак (+), затем, используя правило чередования знаков, поочередно проставляют знаки (–) и (+). У вершин со знаком (–) выбирают минимальный груз q = min[ xi j(-)], его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (–). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т.д. до тех пор, пока не получим оптимальное решение. Замечание. В некоторых случаях поставка, перераспределяемая по циклу, может оказаться равной нулю. Это возможно тогда, когда клетка со знаком «–» содержала нулевую поставку . В этом случае по циклу передается нулевая поставка. В результате свободная клетка, для которой был построен цикл, становится заполненной (нулевой поставкой), а клетка с нулевой поставкой – свободной. Если при перераспределении поставки по циклу поставка обращается в нуль сразу в нескольких заполненных клетках, то свободной следует считать только одну (любую) из них. Остальные клетки, поставка в которых стала равной нулю, следует считать заполненными нулевой поставкой . Переход к следующему опорному решению. Выбираем клетку, от которой начнем построение цикла перераспределения поставок, по правилу , или , т.е. максимальную величину оценки имеет свободная клетка (1, 2). Для этой клетки можно построить следующий цикл: 0*-14-1- -15-5-0* (все вершины цикла, кроме первой, находятся в занятых клетках, углы прямые, число вершин четное). У вершин цикла с соответствующими значениями поставок по правилу чередования знаков ставим знаки (+) и (–).У вершин со знаком (–) выбираем минимальный груз q = min[14, , 5] = . Поскольку перемещаемый по циклу груз имеет нулевое значение, то произойдет только перемещение нулевой поставки в клетку(1, 2), а клетка (4, 3), где ранее была нулевая поставка, станет свободной.
Фактически решение задачи (план перевозок) не изменилось, однако необходимо пересчитать потенциалы и найти новые оценки свободных клеток, учитывая, что клетка (1, 2) теперь занята, а клетка (4, 3) свободна: . Проверка решения Х1 на оптимальность выполняется аналогично предыдущему шагу. Расчет потенциалов для занятых клеток: u1 = 0; клетка (1, 1): v1 = c11 – u1 = 6 – 0 = 6; клетка (4, 1): u4 = c41 – v1 = 5 – 6 = -1; клетка (1, 2): v2 = c12 – u1 = 10 – 0 = 10; клетка (2, 2): u2 = c22 – v2 = 7 – 10 = -3; клетка (3, 2): u3 = c32 – v2 = 14 – 10 = 4; клетка (3, 3): v3 = c33 – u3 = 5 – 4 = 1; клетка (4, 4): v4 = c44 – u4 = 4 – (-1) = 5. Расчет оценок свободных клеток: D 13 = u1 + v3 - c13 = 0 + 1 – 7 = –6 < 0, D 14 = u1 + v4 - c14 = 0 + 5 – 5 = 0, D 21 = u2 + v1 - c21 = – 3 + 6 – 10 = –7 < 0, D 23 = u2 + v3 - c23 = – 3 + 1 – 6 = –8 < 0, D 24 = u2 + v4 - c24 = – 3 + 5 – 9 = –7 < 0, D 31 = u3 + v1 - c31 = 4 + 6 – 13 = –3 < 0, D 34 = u3 + v4 - c34 = 4 + 5 – 7 = 2 > 0, D 42 = u4 + v2 - c42 = – 1 + 10 – 10 = –1 < 0, D4 3 = u4 + v3 - c43 = – 1 + 1 – 6 = –6 < 0.
Результаты расчета представлены в распределительной таблице:
Клетка (3, 4) имеет положительную оценку D 34 = 2 > 0, следовательно, решение Х1 не оптимальное, а для клетки строим новый цикл: 0*-5- -14-1-20-0* (все вершины цикла, кроме первой, находятся в занятых клетках, углы прямые, число вершин четное). У вершин цикла с соответствующими значениями поставок по правилу чередования знаков ставим знаки (+) и (–), начиная со свободной клетки. У вершин со знаком (–) выбираем минимальный груз q = min[14, 20, 5] = 5.
Его прибавляем к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл: Получили новое решение задачи (план перевозок): Справа и внизу матрицы проведена проверка: исходные данные запасов и потребностей в результате перераспределения поставок не изменились.
Значение целевой функции: . Значение целевой функции уменьшилось на 10 ед.. Проверка решения Х2 на оптимальность. Расчет потенциалов для занятых клеток: u1 = 0; клетка (1, 1): v1 = c11 – u1 = 6 – 0 = 6; клетка (4, 1): u4 = c41 – v1 = 5 – 6 = -1; клетка (1, 2): v2 = c12 – u1 = 10 – 0 = 10; клетка (2, 2): u2 = c22 – v2 = 7 – 10 = -3; клетка (4, 4): v4 = c44 – u4 = 4 – (-1) = 5; клетка (3, 4): u3 = c34 – v4 = 7 – 5 = 2; клетка (3, 3): v3 = c33 – u3 = 5 – 2 = 3; Расчет оценок свободных клеток: D 13 = u1 + v3 - c13 = 0 + 3 – 7 = –4 < 0, D 14 = u1 + v4 - c14 = 0 + 5 – 5 = 0, D 21 = u2 + v1 - c21 = – 3 + 6 – 10 = –7 < 0, D 23 = u2 + v3 - c23 = – 3 + 3 – 6 = –6 < 0, D 24 = u2 + v4 - c24 = – 3 + 5 – 9 = –7 < 0, D 31 = u3 + v1 - c31 = 2 + 6 – 13 = –5 < 0, D 32 = u3 + v2 - c32 = 2 + 10 – 14 = –2 < 0, D 42 = u4 + v2 - c42 = – 1 + 10 – 10 = –1 < 0, D4 3 = u4 + v3 - c43 = – 1 + 3 – 6 = –4 < 0. Результаты расчета представлены в распределительной таблице:
Все оценки свободных клеток положительные, следовательно, решение Х2 оптимально. Оценка клетки (1, 4) D 14 = 0 означает, что задача имеет альтернативные решения.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-02-10; просмотров: 97; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.190.217.134 (0.01 с.) |