Определение параметров обслуживающих систем как одноканальных замкнутых смо с простейшими потоками.

Постановка задачи. Допустим, что обслуживающая производственная система может быть представлена как одноканальная замкнутая СМО. Например, “Ремонтная бригада - оборудование”. Канал обслуживания - ремонтная бригада, а требования - оборудование, требующее время от времени! соответствующего ремонта. При этом, как время выхода из строя оборудования, так и продолжительность ремонта оборудования имеют вероятностный! характер. Поступающее в ремонт оборудование, находится в системе до тех пор, пока не будут отремонтированы - система с неограниченным временем ожидания ремонтируемого оборудования. Допустим, что потоки событий,] происходящие в системе, в процессе ее работы являются простейшими (ординарными, стационарными и без последействия).

Известны:

число оборудований, обслуживаемых ремонтной бригадой - т;

интенсивность поступления оборудования в ремонт - λ;

интенсивность ремонта оборудования - µ.

Требуется определить параметры функционирования обслуживающей

системы “Ремонтная бригада - оборудование” в установившемся режиме. когда вероятности состояния системы не зависят от времени:

вероятность отсутствия в системе ремонтируемого оборудования - канал обслуживания - ремонтная бригада простаивает - Р_а;

вероятности наличия в системе п требований (ремонтируемых оборудований) - Р_п;

коэффициент использования канала обслуживания (ремонтной бригады);

среднюю длину очереди, т. е. среднее число требований находящихся в очереди, ожидающих обслуживания - N₀ч,

среднее число требований находящихся в системе, т. е. в очереди и в ка* нале обслуживания - N_Cmct-

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

Представим функционирование производственного процесса “Ремонт­ная бригада - оборудование” как системы массового обслуживания, в виде размеченного графа всех возможных состояний системы. Для чего необхо­димо выполнить ряд действий:

• составить полный перечень всех возможных состояний производствен­ной системы по числу требований (оборудований), требующих ремонта! (обслуживания). Так, если ни одно оборудование не поступила в систему] в ремонт, то канал обслуживания (ремонтная бригада) будет простаивать] и такое состояние характеризуется параметром Р₀ - вероятностью отсут­ствия требований в системе. При наличии в системе только одного обо­рудования это состояние характеризуется параметром Р₁ - вероятностью! наличия одного требования в системе и т. д. Таким образом, каждый] прямоугольник графа, количественно оцениваемый вероятностью со­стояний Р₁ определяет одно из всех возможных состояний;

определить все возможные переходы (связи) системы из одного состоя­ния в другие. Переходы (связи) изображаются соответствующими стрел­ками. Стрелки указывают, в какое состояние система может перейти и с какой интенсивностью. Первый прямоугольник с вероятностью Р₀ опреде­ляет состояние производственной системы, при котором канал обслужи­вания простаивает, из-за отсутствия требований. Из этого состояния сис­тема может перейти только в состояние Pi. Тогда в системе появится одно оборудование, нуждающееся в обслуживании, так как входной поток их ординарный. С интенсивностью µ система может перейти также из со­стояния Р; в состояние Р₀. Это тогда, когда в системе находилось одно оборудование, но оно было обслужено раньше, чем появилось новое и т.д.; построить размеченный граф состояний, который изображает все воз­можные состояния системы, все возможные переходы и соответствую­щие интенсивности.

Для одноканального замкнутого производственного процесса “Ремонтная бригада - оборудование” размеченный граф состояний будет выглядеть так, как показан на рис. 5.4.

рис. 5.4. Размеченный граф состояний одноканальной замкнутой производственной

системы

 

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

Исследование системы. Для определения искомых параметров функ­ционирования, рассматриваемой производственной системы, проведем ре­шение системы алгебраических уравнений аналитическим, а затем числен­ным методом с помощью системы Mathcad [7].

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

При решении задачи аналитическим методом используем метод по­следовательных подстановок. Обозначим величину λ/т через ψ и назовем его коэффициентом загрузки.

 

 

В качестве примера рассмотрим производственный процесс "Ремонт­ная бригада - оборудование". Известны исходные данные системы:

число обслуживаемого оборудования m = 5;

интенсивность ремонта оборудования µ = 29 ремонтов в год;

интенсивность отказа каждого оборудования λ = 6 отказов в год. Требуется определить:

вероятность простоя ремонтной бригады Р₀

вероятности нахождения в ремонте 1-го, 2-х, 3-х, 4-х и 5 оборудова­ний P₁P₂P₃P₄P₅.

• коэффициент использования ремонтной бригады - К;

среднее число оборудований, находящихся в системе – Nсист,

среднее число оборудований, находящихся в очереди - Noч-

Перед определением требуемых параметров функционирования задан­ной одноканальной замкнутой производственной системы определим ко­эффициент загрузки µ который будет равен ψ= λ/µ= 0,207.

Вероятность простоя ремонтной бригады составит:

 

Вероятности отказа 1-го, 2-х, 3-х, 4-х и 5 оборудований соответственно составят:

P₁ = Р₀ *т *ψ = 0,271-• 5 • 0,207 = 0,281,

P₂ = P₁*(m-1)* ψ =0,281-4-0,207 =0,233,

P₃ = P₂*(m-2)* ψ = 0,233 • 3 • 0,207 = 0,144,

P₄ = P₃*(m-3)* ψ = 0,144 • 2 • 0,207 = 0,058,

P₅ = P₄*(m-4)* ψ = 0,058-1-0,207 = 0,012.

Коэффициент использования ремонтной бригады составит.

K = 1-Р₀ =1-0,271 = 0,729.

Среднее число оборудований, находящихся в ремонте, определится по формуле:

 

N_cucm=m-(1-P₀)/ψ =1.477

 

Среднее число оборудований, находящихся в очереди, определится по формуле:

N_m=N_cucm-(1-P₀)=m-(1-P₀)*(1/ψ+1)= 0,749.

 

 

14. Оптимизация структуры обслуживающих систем как СМО с простейшими потоками

Постановка задачи. Известны основные технико-экономические по­казатели функционирования обслуживающей системы как одноканальной замкнутой СМО с простейшими потоками.:

С_Кп, Скр - средние затраты, связанные с простоем и работой канала обслуживания (наладчик, ремонтная бригада,...) в единицу времени, руб.;

Стп, Стр - средние затраты, связанные с простоем и работой требова­ния (станок, прибор, оборудование) в единицу времени, руб.;

Я - интенсивность поступления одного требования на обслуживание; fi - интенсивность обслуживания каналом.

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

Выявление основных особенностей взаимосвязей и количествен­ных закономерностей. Используя логико-аналитический анализ, критерий оптимизации (себестоимость обслуживания требований) может быть запи­сан в таком виде:

Где: P₀ - вероятность простоя канала обслуживания;

т - число обслуживаемых требований в системе

Nсист - число требований, находящихся в системе.

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

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

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

И так, мы имеем простейший поток, который обладает одновременно свойствами стационарности, ординарности и отсутствием последействия. Тогда вероятность простоя канала обслуживания определяется так.

Число требований, находящихся в системе обслуживания равны.

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

 

 

В результате такого преобразования в критерии оптимизации выделе­ны три части, из которых второй и третий члены не зависят от числа об­служиваемых машин m, а первый член зависит. Обозначим второй и третий члены через y₁ и несколько преобразуем первый член, тогда получим:

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

Для поиска оптимума воспользуемся следующим неравенством:

Если число обслуживаемых требований в системе мало, то будут зна­чительные простои канала обслуживания, если же наоборот, то будет велик простой требований. И в том, и в другом случае производственная система будет неэффективна.

Подставим в исходное неравенство математические выражения крите­рия оптимизации с соответствующим числом обслуживаемых требований: (т-1), т и (т+1), При этом часть критерия оптимизации –y1, которая не зависят от числа обслуживаемых машин т, может быть опущена:

Разделим все части неравенства на выражение, стоящего в числителе сред­него члена , а затем в левой и правой частях неравенства на .

После некоторых преобразований получим следующее неравенство:

 

Для того, чтобы определить оптимальное число требований в произ­водственной системе т_ОПТ, необходимо протабулировать полученное нера­венство для различных значений т. Те из значений, которые будут удовле­творять неравенству, и будут искомыми оптимальными значениями.

Для облегчения поиска оптимальной структуры одноканальной замк­нутой производственной системы, для различных коэффициентов С и ко­эффициентов загрузки ψ проведены расчеты и результаты расчетов представлены в табл. 5.1.

Оптимальное планирование производства при различных видах спроса.

15. Оптимальное планирование производства (ремонта, обслуживания, ….) при регулярном спросе.

Задача А: Для изготовления (ремонта, обслуживания) n видов изделий И₁, И₂, …., И_n необходимы ресурсы m видов: трудовые, материальные, финансовые и др. Известно необходимое количество отдельного i-го ресурса для изготовления(ремонта, обслуживания) каждого j-го изделия. Назовем эту величину нормой расхода c_ij. Известно имеющееся количество каждого вида ресурса, которым предприятие располагает в данный момент, - a_i (i=1, 2, m). Известна прибыль П_j, получаемая предприятием от изготовления (ремонта, обслуживания, …) каждого j-го изделия. Требуется определить: какие изделия и в каком количестве должно изготавливать (ремонтировать, обслуживать, …) предприятие x_j (j=1, 2, …., n), чтобы обеспечить получение максимальной прибыли.

Таблица 1.1.

Используемые Ресурсы	Изготавливаемые изделия	Наличие ресурсов
И1	И2	И3	И4	И5
Трудовые Материальные Финансовые Иные
Прибыль

Постановка задачи В: В распоряжении завода ж / б изделий (ЖБИ) имеется mвидов сырья (песок, щебень, цемент, вода) в объеме a_i(i=,2,…,m). Требуется произвести продукцию nвидов – x_j (j=1,2,…,n). Дана технологическая норма c_ij потребления отдельного i – го вида сырья для изготовления единицы продукции каждого j-го вида. Известна прибыль П_j, получаемая от выпуска единицы продукции j-го вида. Требуется определить, какую продукцию и в каком количестве должен производить завод ЖБИ, чтобы получить максимальную прибыль. Исходные данные представлены в табл. 1.2.

Таблица 1.2.

Используемые Ресурсы	Изготавливаемые изделия	Наличие ресурсов
И1	И2	И3	И4	И5
Песок Щебень Цемент Вода
Прибыль

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

Выявление основных особенностей, взаимосвязей и количественных закономерностей. Количество изделий j-го наименования, которое может производить предприятие, обозначим через x_j. Зная количество каждого вида i-го ресурса, необходимого для изготовления отдельного j-го типа изделия – норму расхода c_ij и количество каждого i-го ресурса a_i (табл 1.2.), можно записать следующую систему неравенств:

Полученную систему неравенств можно записать в виде совокупности равенств, если в каждое из неравенств ввести фиктивные изделия (дополнительные переменные) x₆, x₇, x₈,x₉ при изготовлении которых используют каждый оставшийся вид ресурса.

В этом случае система принимает вид:

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

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

Граничные условия можно записать следующим образом:

x_j 0, (j=1,…,n).

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

Алгоритм решения. Метод решения – симплекс-метод. Для его использования необходимо предварительно определить начальный базис, т.е решение, которое удовлетворит системе равенств.

Систему уравнений необходимо записать в виде:

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

Для определения значений базисных переменных x₆, x₇, x₈, x₉ необходимо приравнять к нулю небазисные x₁, x₂, x₃, x₄, x₅ и подставить их в систему уравнений. Полученное таким образом решение наз. базисным и будет выглядеть таким образом:

(x₁, x₂, x₃, x₄, x₅ , x₆, x₇, x₈, x₉)

(0, 0, 0, 0, 0, 21, 15, 16, 15)

Алгоритм симплекс-метода:

1. Заполнение исходной симплекс-таблицы.

2. Проверка базисного решения на оптимальность. Просматриваются знаки коэффициентов при небазисных переменных в целевой функции (критерий оптимизации)- последняя строка табл. 1.3.

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

Базисные переменные xi	Свободные члены bi	Коэффициенты при небазисных и базисных переменных
x1	x2*	x3	x4	x5	x6	x7	x8	x9
x6* x7 x8 x9			7*
Цел. ф-ция

3. Проверка задачи на наличие решения. Если при какой-либо небазисной переменной, имеющей положительный коэф. В целевой ф-ции, окажется, что столбец коэффициентов при этой же переменной в системе уравнений состоит из одних положительных чисел, то максимальное значение целевой функции стремится к бесконечности, т.е. задача решений не имеет.

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

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

21/7=3, 15/5=3, 16/8=2, 15/5=3.

Минимальное отношение из полученных указывает строку, базисную переменную, которая должна быть выведена из базиса. При наличии нескольких одинаковых отношений берется любое. Выводим из базиса переменную x₅.

6. Представление новой базисной переменной через небазисные. Строится новая симплекс-таблица (табл.1.4.). Отмечается звездочкой строка и столбец в предыдущей таблице 1.3. соответственно для выводимой из базиса и для вводимой в него переменной.

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

Базисные переменные xi	Свободные члены bi	Коэффициенты при небазисных и базисных переменных
x1	x2	x3	x4	x5	x6	x7	x8	x9
x2* x7 x8 x9
Цел. ф-ция

7. Представление остальных базисных переменных и целевой функции через набор небазисных переменных. Этот этап состоит из нескольких шагов:

1) Определение преобразуемой строки в предыдущей таблице табл. 1.3.

2) Определение множителя для преобразуемой строки. Он равен коэффициенту, стоящему на пересечении преобразуемой строки в предыдущей таблице и столбца коэффициентов при новой базисной переменной, но с обратным знакомю

3) Умножение каждого коэффициента в новой таблице при новой базисной переменной на множитель преобразуемой строки.

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

5) Занесение результатов сложения в соответствующие клетки новой таблицы.

6) Аналогичные расчеты проводятся для всех остальных строк включая и строку целевой функции.

Далее выполняем новую итерацию. Цикл расчета начинается с этапа 2.

2. Проверка базисного решения на оптимальность. Анализируя знаки коэффициентов при небазисных переменных в целевой функции (критерий оптимизации) - последняя строка табл. 1.4 видим, что не все коэффициен­ты при небазисных переменных не положительны, следовательно данный базис не является оптимальным, но лучше, чем предыдущий.

3. Проверка задачи на наличие решения. В нашей задаче имеется.

4. Выбор из небазисных переменных той, которая способна при введе­ны ее в базис увеличить значение целевой функции. В качестве вводимой в базис небазисной переменной берем х₃ (или х_;), как имеющую наибольший положительный коэффициент. Отмечаем звездочкой столбец х6 табл. 1.4.

5. Определение базисной переменной, которая должна быть выведена базиса. В качестве выводимой из базиса переменной берем х₆ табл. 1.4,как для нее частное от деления свободного члена на соответствующий коэффициент минимально. Отмечаем звездочкой строку х₆ табл. 1.4.

 

6. Представление новой базисной переменной через небазисные. Строит- новая симплекс-таблица (табл. 1.5).

Отмечаем звездочкой коэффициент, находящийся на пересечении строки и столбца, отмеченных звездочками табл. 1.4

В нашей задаче на второй итерации разрешающий элемент равен ^/5 и находится во второй строке (табл. 1.4). Все коэффициенты строки, отмеченной звездочкой (табл. 1.4), делятся на разрешающий элемент, а результаты расчета заносятся в новую симплекс-таблицу (табл. 1.5) во вторую строку.

Таблица 1.5

Базисные переменные xi	Свободные члены bi	Коэфф. при небазисных и базисных переменных
x1	x2	x3	x4	x5	x6	x7
х2 х3 х7		1/9 11/9 -5/9			1/9 4/9 -10/9	1/3 -3/9 -2/9	-2/9 5/9 -8/9
Целевая функция	-150	-20/0			-490/9	-20/3	-0/9

 

7. Представление остальных базисных переменных и целевой функции через новый набор небазисных переменных. Этап включает ряд шагов:

1) определение преобразуемой строки в предыдущей таблице (табл. 1.4),

допустим, что это будет строка один;

2) определение множителя для преобразуемой строки. В нашем примере на второй

итерации для преобразуемой первой строки этот множитель будет равен -2/5;

3) умножение каждого коэффициента в новой таблице табл. 1.5 при но- эй базисной переменной х₃ на множитель преобразуемой строки» В нашем примере на второй итерации умножаем коэффициенты при новой базисной переменной (х3) - второй строки табл. 1.5 на множитель -2/5. Получим следующие коэффициенты (0 • (-2/5) = 0, 11/9 • (-2/5) = -22/45, 0 • 2/5)

= 0,1 • (-2/5) =-2/5, 4/9 • (-2/5) = -8/45, -3/9 • (-2/5) = 6/45, 5/9 • (-2/5) = -10/45, 0 • (-2/5) = 0;

4) сложение результатов умножения на предыдущем шаге с соответст­вующим b коэффициентами преобразуемой строки (табл. 1.4). В нашем примере необходимо сложить коэффициенты (0, -22/45, 0, -2/5, -8/45, 6/45, -10/45, 0) с соответствующими коэффициентами преобразуемой первой строки табл. 1.4 (3, 3/5, 1, 2/5, 7/5, 1/5, 0, 0). Получим (0 + 3 =3, -22/45 + + 3/5 = 1/9, 0 +1 = 1, -2/5 + 2/5 = 0, -8/45 + 7/5 = 11/9, 6/45 + 1/5 = 1/3, -10/45 + 0 = -2/9, 0 + 0 = 0);

5) занесение результатов сложения в соответствующие клетки новой таблицы. В нашем примере в первой строке табл. 1.5 появятся коэффици­енты (3, 1/9, 1, 0, 1/9, 1/3, -2/9, 0);

6) аналогичные расчеты проводятся для всех остальных строк, включая и строку целевой функции

Последняя строка таблицы не содержит положительных коэффициен­тов при небазисных переменных. Анализируя полученное решение, видим, что оно оптимально и выглядит так:

(x1 x2, x3, x4, x5, x6, x7);

(0, 3, 0, 0, 0, 0,12).

Из полученного решения видно, что предприятию наиболее выгодно изготовление только изделия И₂, производство которых обеспечит ему мак­симальную прибыль в размере Ymax = 150. При этом материальные и тру­довые ресурсы будут задействованы полностью, а финансовые - недоис­пользованы на 12 единиц.

Рассмотрим теперь решение этой же задачи в системе Mathcad.

Определение оптимального плана производства изделий в системе Mathcad включает несколько этапов.

Нулевой этап - ввод поясняющего текста и исходных данных:

> введите название этапа;

> выведите поясняющий текст и исходные данные рис. 1.1.

В нашей задаче исходные данные представлены в виде таблицы и по­ясняющего текста рис. 1.1.

Алгоритм решения задачи включает несколько этапов.

Первый этап - представление критерия оптимизации:

> введите имя критерия оптимизации, с аргументами в скобках через запятые Y(X1,X2,X3,X4,X5,X6,X7), а затем знак присваивания, на­жав комбинацию клавиш Shift+: (двоеточие);

У введите в появившуюся метку выражение критерия оптимизации

40-Х1+ 50-Х2 + 30X3 + 20-Х4 + 0-Х5 + 0X6 + 0-Х7

Второй этап - определение начальных приближений:

> введите название этапа, а затем начальные приближения для иско­мых переменных: XI:= 0 Х2:=0 Х3:=0 Х4:=0;

ведите начальные приближения для фиктивных переменных: Х5:=15 Х6:= 9 Х7:=30.

 

 

17. Оптимизация загрузки оборудования (рабочих) в единичном производстве

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

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

Задача оптимизации в общем случае включает три составляющие: целевую функцию (критерий оптимизации); ограничения; граничные условия.

Граничные условия показывают предельно допустимый значения искомых переменных.

Ограничения показывают существующие связи между искомыми переменными. По своему происхождению связи могут быть детерминированными и статистическими.

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

Значения искомых переменных, удовлетворяющих граничным услови­ям и ограничениям, называют допустимым решением задачи.

Структура математической модели представлена на рис. 2.1.

Рис. 2.1. Структура математической модели

 

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

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

Постановка задачи А. На предприятии имеется п - типов универсаль­ного оборудования и требуется изготовить п - видов изделий. Известно время изготовления каждого изделия на каждом виде оборудования. Требу­ется определить какое изделие, на каком оборудовании необходимо изго­тавливать, чтобы суммарное время на изготовление всех изделий было ми­нимальным {табл. 2.2).

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

Постановка задачи С. В конструкторском бюро требуется разрабо­тать проект машины, состоящей из и-узлов. К разработке узлов можно при­влечь п конструкторов. Известно время, затрачиваемое каждым конструк­тором для разработки каждого узла. Требуется определить какие конструк­тора, какие узлы должны проектировать, чтобы суммарное время на проек­тирование машины было минимально.

Таблица 2.2. Используемое оборудование Оi (i = 1,2,…,n) Изготавливаемые изделия Иj (j =1,2,..., n)   И1 И2 И3 И4 И5 Затраты Уijпри изготовлении изделия Иj на оборудовании Оi О1           О2           O3           O4           O5

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

Введем переменные Ху, которые равны:

1, если на i - ом оборудовании изготавливается j - ое изделие;

О, если на i - ом оборудовании не изготавливается j - ое изделие. Сформулируем ограничения в задаче:

1) каждое оборудование может изготавливать только одно изделие. Это ограничение можно записать в таком виде

 

.

 

2) каждое изделие может изготавливаться только на одном оборудования. Это ограничение можно записать так

Построение математической модели. В качестве критерия оптимизации и примем суммарные затраты на изготовление всех изделий - Y. Обозначаем через Y_ij затраты при изготовлении j - го изделия на i - м оборудовании. Когда критерий оптимизации Y запишется в таком виде

 

Совокупность ограничений и целевой функции образует математическую модель. Это типичная экстремальная комбинаторная задача.

Эта задача представляет собой выбор оборудования для изготовления изделий в единичном производстве. Число возможных расстановок - N с ростом количества используемого оборудования -пи числа изготавливаемых изделий - п резко возрастает и равно N = п!.

Даже для нашей простой задачи N = 5! = 120, а для п = 1 число перестановок составляет уже - 5040.

В литературе эта задача имеет свое название - задача о назначении, данная задач относится к классу задач линейного программирования, так как ограничения и целевая функция имеют линейный вид, т.е. искомые величины находятся в первой степени.

Алгоритм решения. Для решения задач данного типа разработанного методов. Рассмотрим один из наиболее распространенных - венгерский метод. Для поиска оптимального решения потребуется не более чем (п - 2) последовательно проводимых итераций.

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

1. Получение нулей в каждой строке и каждом столбце. Находится наименьший элемент в каждой строке исходной таблицы (см. табл. 2.2) и учитывается из всех ее элементов. Получаем новую таблицу (табл. 2.3).

Аналогично действия выполняем для каждого столбца в новой таблице табл. 2.3). Получаем табл. 2.4.

2. Проверка решения на оптимальность. Ищется строка, содержащая меньшее число нулей. В нашей задаче это строка 3. Отмечается звездочкой один

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

Таблица 2.3

Используемое оборудование Оi (i = 1,2,…,n)	Изготавливаемые изделия Иj (j =1,2,..., n)
И1	И2	И3	И4	И5
Затраты Уijпри изготовлении изделия Иj на оборудовании Оi
О1
О2
O3
O4
O5

 

Таблица 2.4

Используемое оборудование Оi (i = 1,2,…,n)	Изготавливаемые изделия Иj (j =1,2,..., n)
И1	И2	И3	И4	И5
Затраты Уijпри изготовлении изделия Иj на оборудовании Оi
О1
О2
O3
O4
O5

 

Таблица 2.5

Используемое оборудование Оi (i = 1,2,…,n)	Изготавливаемые изделия Иj (j =1,2,..., n)
И1	И2	И3	И4	И5
Затраты Уijпри изготовлении изделия Иj на оборудовании Оi
О1
О2
O3			0*
O4			Ø
O5			Ø

 

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