Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Время простоя определяется графически





 

В некоторых частных случаях алгоритм Джонсона применяется и для решения задач, требующих трехэтапного обслуживания. Это можно сделать, когда соблюдается одна из следующих систем неравенств:

 

1) максимальное время обработки изделия на первой машине больше или равно максимальному времени обработки изделия на второй машине:

;

 

2) минимальное время обработки изделия на третьей машине больше или равно максимальному времени обработки на второй машине:

.

 

После этого составляется новая таблица для суммы вместо или вместо и к ней применяется алгоритм Джонсона.

Класс задач, к которым применяется алгоритм Джонсона, ограничен. Решение же методом прямого перебора всех возможных вариантах уже при десяти изделиях требует более трех миллионов переборов. В некоторых задачах упорядочения для решения можно использовать методы линейного и динамического программирования.

 

4. Задача о назначении.

 

Задача о назначении в общем виде формулируется так.

 

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

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

Это типичная экстремальная задача комбинаторного вида, ее решение путем прямого перебора практически невозможно при сколько-нибудь больших , так как число перестановок !

 

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

Пусть для монтажа четырех объектов требуется четыре крана . Из отчетных данных известно, какое время необходимо каждому крану для монтажа объекта .

Нужно так распределить краны по объектам чтобы суммарное время на монтаж этих объектов было минимально. В нашем случае - затраты времени – го крана при монтаже объектов .

Таблица 1

Аi В1 В2 В3 В4
А1            
А2            
А3            
А4            
Вi            

 

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

 

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

Введем переменные

 

 

Так как каждый кран можно распределить (назначить) только на один объект и на каждом объекте может работать только один кран, то введенные переменные должны подчиняться двум условиям:

 

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

Критерий оптимизации – суммарное время монтажа четырех объектов - математически можно заменить:

 

 

Нужно найти , удовлетворяющие двум вышеприведенным условиям.

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

Для решения задачи о назначении имеется насколько методов. Самый распространенный - венгерский метод.

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

Решение считается оптимальным, если все измененные искусственные затраты и можно отыскать такой набор ,что

 

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

 

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

 

 

Таблица 2

Вj Аi В1 В2 В3 В4
А1          
А2          
А3          
А4          
         
         

 

Таблица 3

Вj Аi В1 В2 В3 В4
А1 -0-º -2- -2- -2-  
А2 - - -0- -2- -0-  
А3     0 ˝    
А4        
         

 

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

3) Поиск минимального набора строк и столбцов, содержащих нули. Для этого необходимо отметить точкой:

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

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

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

 

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

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

Таблица 4

 

Вj Аi В1 В2 В3 В4
А1 0 ◦        
А2 0 ◦    
А3   0 ◦    
А4     0 ◦  
         

 

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

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

 

 

Лекция 11

 







ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.