Постановка задачи и выбор критерия оптимизации.

Пусть в эксплуатации находится машина, имеющая n наименований сменного оборудования. Известны объекты работы О_i, (i = 1, 2,…,n), которые должны выполнить с использованием этой машины.

Потери от смены рабочего оборудования при переходе с одного объекта на другой известны и задаются матрицей затрат (табл. 1).

Выполнение работ производится так, что отсутствует повторная установка сменного оборудования, пока не будут выполнены все работы.

Выполнение таких работ назовем полным циклом. Требуется определить такой порядок смены рабочего оборудования или такой порядок выполнения работ, чтобы суммарные потери от смены рабочего оборудования при строительстве объектов были минимальны.

Выявление основных особенностей, взаимосвязей и количественных закономерностей.

Время на смену оборудования при переходе от i – го объекта к j – му равно t_ij = ∞ (i = 1, 2,…,n).

Построение математической модели.

Суммарные затраты, связанные с выполнением n видов работ, например, для порядка выполнения работ

О₁ → О₂ →О₄ → О₃ →О₅ →О₁

запишутся в таком виде:

y = t₁₂ + t₂₄ + t₄₃ + t₃₅ + t₅₁, (i ≠ j)

Таблица 1 – Время смены оборудования t_ij – исходные данные

Объекты работы О_i	О₁	О₂	О₃	О₄	О₅	d_i
О₁	∞
О₂		∞
О₃			∞
О₄				∞
О₅					∞

Таблица 2 – Время смены оборудования t_ij – 1– й шаг

Объекты работы О_i	О₁	О₂	О₃	О₄	О₅
О₁	∞
О₂		∞
О₃			∞
О₄				∞
О₅					∞
d_i

Таблица 3 – Время смены оборудования t_ij – результаты расчета

Объекты работы О_i	О₁	О₂	О₃	О₄	О₅
О₁	∞	0*
О₂		∞		0*
О₃			∞		0*
О₄	0*			∞
О₅			0*		∞

Таблица 4 – Время смены оборудования – исходные данные при Т (5,3) = ∞

Объекты работы О_i	О₁	О₂	О₃	О₄	О₅
О₁	∞
О₂		∞
О₃			∞
О₄				∞
О₅			∞		∞

Таблица 5 – Время смены оборудования – результаты расчета при Т (5,3) = ∞

Объекты работы О_i	О₁	О₂	О₃	О₄	О₅
О₁	∞	0*
О₂	0*	∞
О₃			∞		0*
О₄			0*	∞
О₅			∞	0*	∞

Таблица 6 – Время смены оборудования – исходные данные при Т (3,5) = ∞

Объекты работы О_i	О₁	О₂	О₃	О₄	О₅
О₁	∞
О₂		∞
О₃			∞		∞
О₄				∞
О₅					∞

Таблица 7 – Время смены оборудования – результаты расчета при Т (3,5) = ∞

Объекты работы О_i	О₁	О₂	О₃	О₄	О₅
О₁	∞	0*
О₂		∞			0*
О₃			∞	0*	∞
О₄	0*			∞
О₅			0*		∞

Исследование математической модели.

Рассмотрим один из алгоритмов решения данной задачи, основанный на использовании метода ветвей и границ и венгерского метода. Алгоритм включает следующие основные этапы:

I. Определение верхней границы искомого оптимального решения целевой функции.

Для этого берется максимальный элемент таблицы (1) и умножается на число объектов. В задаче такой элемент равен 9.

y_max = 9 ∙ 5 = 45

II. Определение нижней границы искомого оптимального решения.

Для этого необходимо решить задачу о назначении для исходной матрицы затрат.

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

Решить ее можно венгерским методом.

Идея этого метода была высказана венгерским математиком Эгервари (отсюда и название метода). Американский ученый Кун в 1953 г. развил эту идею и предложил метод, названный им венгерским, для решения задачи выбора (частный случай транспортной задачи).

Основной принцип венгерского метода – оптимальность решения задачи о назначении не нарушается при уменьшении (увеличении) элементов строки (столбца) на одну и ту же величину d_i (d_j).

Алгоритм венгерского метода включает следующие этапы:

1) получение нулей в каждой строке.

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

2) поиск оптимального решения.

Необходимо рассмотреть сначала одну из строк табл. 3, имеющую меньше нулей. Отметим звездочкой один из нулей этой строки и зачеркнем все остальные в этой строке и столбце, в котором находится этот нуль. Аналогичные операции последовательно проводят для всех строк.

Если назначения, которые получены при всех нулях, отмеченных звездочкой, являются полными (т. е. число нулей отмеченных звездочкой, равно n), то решение является оптимальным, в противном случае следует переходить к следующему этапу;

3) поиск минимального набора строк и столбцов, содержащих нули.

Для этого необходимо отметить звездочкой:

– все строки, в которых не имеется ни одного отмеченного звездочкой нуля (см. строка 4 табл. 3 пример);

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

– все строки, содержащие отмеченные звездочкой нули, хотя бы в одном из отмеченных звездочкой столбцов (см. строка 3 табл. 3 пример).

Пример использования венгерского метода (Кудрявцев стр. 110)

Таблица 1 – матрица затрат – исходные данные.

Машины А₁	Затраты времени на монтаж С_ij по объектам В_j	d_i
В₁	В₂	В₃	В₄
А₁
А₂
А₃
А₄

Примечание. а_i – число i – х машин,

d_i – минимальный элемент строки,

В_j – число машин на j – м объекте

Таблица 2 – матрица затрат – 1 – я итерация.

Машины А₁	Искусственные затраты времени С_ij по объектам В_j
В₁	В₂	В₃	В₄
А₁
А₂
А₃
А₄
d_j

Таблица 3 – матрица затрат – 2 – я итерация

Машины А_i	Искусственные затраты времени С_ij по объектам В_j
В₁	В₂	В₃*	В₄
А₁	0*
А₂		0*
А₃			0*
А₄

Таблица 4 – матрица затрат – 3 – я итерация

Машины А_i	Искусственные затраты времени С_ij по объектам В_j
В₁	В₂	В₃*	В₄
А₁	0*
А₂		0*
А₃			0*
А₄				0*

После этого необходимо зачеркнуть каждую непомеченную строку и каждый помеченный столбец (цель – провести минимальное число горизонтальных и вертикальных прямых, пересекающих, по крайней мере, один раз все нули);

4) перестановка некоторых нулей.

Возьмем наименьше число из тех клеток, через которые не проведены прямые (в табл. 3 это число 2 пример).

Вычтем его из каждого числа не вычеркнутых столбцов и прибавим к каждому числу вычеркнутых строк. Получим табл. 4 (пример).

Эта операция не изменяет оптимального решения, после чего весь цикл расчета начинают с этапа 2) и продолжают до получения оптимального решения. В нашем случае число нулей, отмеченных звездочкой, оказалось равным 4, значит назначение является полным, а решение оптимальным.

В результате решения венгерским методом получаем промежуточную и окончательную таблицу расчетов (табл. 2 и 3).

Анализ результатов расчета (табл. 2 и 3) показывает, что объекты распределены так, что имеется 2 неполных цикла выполнения n объектов:

1) О₁→ О₂ → О₄ → О₁;

2) О₃→ О₅ → О₃

Суммарные потери от переналадок при таком распределении составят (табл.1)

y = 3 + 5 + 3 + 3 + 6 = 20 (мин.,ч)

Если получены два и более неполных цикла выполнения работ, необходимо перейти к этапу III, в противном случае полученное решение является оптимальным.

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

y ≥ 20

III. Выбор из неполных циклов такого, которому отвечает минимальное число переналадок (переходов) в цикле.

В решаемой задаче это второй неполный цикл

О₃→ О₅ → О₃,

которому соответствуют 2 перехода.

IV. Решение столько задач о назначении для неполного цикла с минимальным числом переходов, сколько имеется переходов в этом цикле.

В решаемой задаче 2 перехода, т. е. необходимо решить две задачи о назначении.

При этом, в одном из этих переходов принимаем время смены оборудования равным ∞, получим:

1)-я задача: принимая Т (5,3) = ∞ (время смены 5 оборудования на 3), имеем исходную матрицу затрат (табл. 4);

Решая задачу о назначении венгерским методом, получим окончательное решение (табл. 5). В результате имеем два неполных цикла выполнения объектов:

О₁→ О₂ → О₁;

О₃→ О₅ → О₄ → О₃

С суммарными потерями от смены рабочего оборудования

Т = 3 + 4 + 3 +7 + 6 = 23

y^I_опт ≥ 23 – для 1-й ветви

2)-я задача: принимая Т (3,5) = ∞ (время смены 3-го оборудования на 5), имеем другую исходную матрицу затрат (табл. 6).

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

О₁→ О₂ → О₅ → О₃ → О₄ → О₁

с суммарными потерями от смены рабочего оборудования

Т = 3 + 6 + 6 + 4 + 3 = 22

Для второй ветви суммарные потери от смены оборудования

y^II_опт ≥ 22

Каждое из полученных решений, т. е. полученные суммарные потери являются нижней границей для соответствующих ветвей решения.

Для первой ветви решения нижняя граница критерия оптимизации (целевой функции) – суммарных потерь от смены рабочего оборудования составит

y^I_min (5,3) = 23

Для второй же ветви она составит 22.

V. Определение верхней границы искомого оптимального решения.

Если имеется один и более полных производственных циклов, (допустимых решений) и минимальные потери из них меньше, чем верхняя граница критерия оптимизации (в данной задаче y_max = 45), то верхняя граница приравнивается к минимальным потерям.

В задаче y_max = 22.

В противном случае верхняя граница остается неизменной:

y_min ≤ y_опт ≤ y_max

20 ≤ y_опт ≤ 22

VI. Проверка полученного решения на оптимальность.

Возможны 2 исхода. Если новая верхняя граница меньше, чем все другие нижние границы для всех других ветвей решения, то имеем оптимальное решение задачи. В данной задаче верхняя граница равна y_max = 22, имеем 2 – е ветви решения и для второй ветви решения нижняя граница y_min = 23, следовательно, полученное решение оптимально.

Если решение не оптимально, то переходят к следующему этапу.

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

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

Решение задачи определения оптимального порядка выполнения работ (строительство объектов) можно представить в виде графа (дерева) рис. 1.

Для оптимального использования сменного рабочего оборудования необходим такой порядок выполнения работ

О₁→ О₂ → О₅ → О₃ → О₄ → О₁

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

Литература

1. Васильев А.Л. Модульный принцип формирования техники.– М.: Из – во стандартов, 1989.

2. Бесов В.И., Бресская А.Л., Граженская О.В., Сентюрина Н.М., Внедрение функционально-стоимостного анализа в отрасли.– Строительные и дорожные машины, 1988, № 9, с. 12…13.

3. Бусленко Н.П. Моделирование сложных систем.– М.: Наука, 1978.

О₁

О₄

О₃

О₅

О₂

О₁