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

Алгоритм решения

Читайте также:
  1. B. Принятия оптимального управленческого решения по наиболее важным вопросам деятельности на рынке.
  2. CRC-алгоритмы обнаружения ошибок
  3. I.5.5. Просмотр и анализ результатов решения задачи.
  4. VII. Алгоритмы продаж
  5. Алгоритм 4. Транспонування бази даних
  6. Алгоритм 5. Пошук автофильтром
  7. Алгоритм Apriori

Отличие в рассматриваемом методе заключается только в том, что вместо «оценок клеток» (как известно, рекомендуется выполнять построение циклов со свободными клетками, имеющими отрицательные оценки) будут фигурировать нарушения потенциалов в некоторых свободных клетках.

Нарушения потенциала со знаком плюс в некоторой свободной клетке будет свидетельствовать о том, что с ней можно организовать цикл однократного замещения, ведущий к уменьшению значения целевой функции.

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

Потенциалы клеток, занятых базисными переменными, в точности равны сумме потенциалов i-ой строки и j-го столбца, поскольку это является исходным условием для понятия потенциалов:

Пijбаз = ui + vj (4.1)

 

Нарушение потенциала для свободной клетки констатируется в том случае, если: Пijсв. > с ijсв (4.2)

с ijсв – значение единичной стоимости, записанное в клетке

Численное значение нарушения потенциалов ΔПij равно:

ΔПij = Пijсв. - с ijсв = - о ijсв (4.3)

Опорное решение в данном алгоритме рекомендуется определять методом минимального элемента (см. лекцию 3).

Рассмотрим теперь порядок определения потенциалов и нарушения потенциалов ΔZij по свободным клеткам (рис. 4.5.).

 

Рис. 4.5. Схема определения потенциалов клеток

 

В приводимой таблице клетки, занятые базисными переменными заштрихованы. В кружочках рядом с потенциалами показана очерёдность их нахождения, начиная с первого, который обязательно назначается равным нулю (с какой строчки начинать, в принципе) не имеет значения. Но удобней с первой строчки.

Ввиду того, что для данного расчёта нам не нужны «значения корреспонденций» в занятых клетках мы просто заштриховали названные клетки, чтобы обозначить их расположение в таблице. Продолжаем горизонтальную стрелку по первой строке (это горизонтальная составляющая потенциала) до затенённой клетки и останавливаемся в клетке (1-2). Далее поворачиваем её ход по вертикали вниз, за границы таблицы.

Там мы должны записать вертикальную составляющую потенциала с таким значением, чтобы сумма горизонтальной и вертикальной составляющей в точности совпадали со значением единичной стоимости, записанной в уголке затенённой клетки.

В нашем случае это будет число «3». Здесь же в кружочке запишем номер нашего действия – это цифра 2. Названная только что стрелка «пронзает» также клетку (1.5.). В третьей процедуре (порядковый номер 3), мы записываем цифру «9».Действие под номером 4 (в кружочке) выводит своей горизонтальной стрелкой на клетку (2-5). Здесь инициатива идёт уже от клетки (2-4) и для обеспечения нулевого баланса единичной стоимости мы записываем горизонтальную составляющую потенциала в размере «- 5». Метод потенциалов, при наличии навыков, позволяет намного быстрее прийти к опорному решению, в том числе за счёт отпадания надобности в проведении циклических преобразований. Мы сразу, в процессе заполнения таблицы потенциалами обнаруживаем свободные клетки, которые обеспечивают полезное циклическое преобразование от новой свободной клетки.

Следует иметь в виду, что после проведения очередной итерации, описанная схема расчёта повторяется заново с каждым, очередным, опорным решением.

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

 

Zмин = 860

 

Рис. 4.6. Оптимальное решение транспортной задачи

 

Контрольные вопросы

 

1. Какой метод используется для однократного замещения корреспонденций в матрице?

2. Дайте определение понятию «цикл»

3. Каким образом определяются значения величины λ?

4. В чем заключается сущность метода «северо-западного угла»?

5. В чем заключается сущность метода «потенциалов»?

6. Назовите основные отличия метода «северо-западного угла» от метода «потенциалов».

7. Каким образом определить, что решение транспортной задачи является оптимальным?

 


Лекция 5

теория графов. сетевое планирование

 

План

 

5.1. Основы теории графов

5.2. Особенности и постановка задач сетевого планирования

 


Дата добавления: 2015-10-29; просмотров: 158 | Нарушение авторских прав


Читайте в этой же книге: Разработка операционных моделей | Формулировка задачи | Алгоритм графоаналитического метода построения сетевых моделей | Методика оптимизации сетевых моделей | Непрерывная случайная величина | Постановка задач | Входящий поток | Постановка задачи | Разработка модели | Графоаналитическая модель имитации обслуживания. |
<== предыдущая страница | следующая страница ==>
Описание алгоритма однократного замещения| Основы теории графов

mybiblioteka.su - 2015-2024 год. (0.008 сек.)