Альтернативные эвристические методы решения задач
Распределительного типа
Если не представляется возможным получить решение плановой или экономической задачи на основе непосредственно многокритериального подхода, предлагается использовать ряд достаточно эффективных эвристических (т.е. полученных в результате обобщения накопленного практического опыта) методов. Среди них наиболее перспективными и обеспечивающими получение в большинстве случаев вполне приемлемых с практической точки зрения (приближенно оптимальных) планов являются:
- метод «наибольшего подобия»;
- метод, базирующийся на использование в расчетах формулы линейного коэффициента корреляции;
- метод, получивший условное название косинуса многомерного пространства.
Общим для этих методов является то, что с помощью оригинальной системы расчетов в каждом из них, ищется степень сходства между структурой трудоемкостей участвующих в расчетах изделий (заготовок, деталей, сборочных единиц) и структурой подлежащих использованию в данном плановом периоде фондов времени основных групп рабочих мест (ОГРМ) или иных видов ресурсов. Приведем краткую характеристику перечисленным выше эвристическим методам и сопроводим их практическими иллюстрациями, отражающими существо необходимых расчетов.
Метод «наибольшего подобия». Сущность его состоит в том, что в план формируемого на данной стадии расчетов периода (например, месяца) в первую очередь включается такое изделие, структура трудоемкости которого имеет наибольшее сходство со структурой остающихся к использованию фондов времени основных групп рабочих мест.
Для четкого понимания существа данного метода приведем краткую постановку, экономико-математическую модель задачи распределения квартального плана и последовательность укрупненного вычислительного процесса.
Постановка задачи. Пусть необходимо распределить заданную на квартал номенклатуру (программу) изделий по месяцам с учетом обеспечения требования необходимой равномерности и полноты (сбалансированности) использования имеющихся фондов времени по основным группам рабочих мест. Под сбалансированностью загрузки основных групп рабочих мест подразумевается обеспечение такой их занятости работой, кото рая находится в пределах от 90 до 120% от величины первоначального подлежащего использованию фонда времени 
.
Экономико-математическая модель задачи распределения
квартального плана по месяцам
(
(1)
N 
(
i) (2)
f(X) = 
( jk) (3)
где
i - код изделия (i = 1,..., n);
j - код основной группы рабочих мест (j = 1,..., m);
N - программа выпуска i-го изделия на квартал, шт.;
k - номер месяца квартала (k = 1,...,3);
х 
- количество изделий (партия изделий) i-го наименования,
включенных в план k-го месяца данного квартала, шт.; 
t 
- трудоемкость i-го изделия на j-ой ОГРМ, ч;
- подлежащий использованию фонд времени по j-ой ОГРМ в
k - ом месяце квартала, ч; 
В выражении экономико-математической модели (1) сформулировано требование, предусматривающее обеспечение необходимой сбалансированности загрузки каждой ОГРМ в любом месяце квартала.
Уравнение (2) предусматривает безусловный выпуск всех участвующих в расчетах изделий на протяжении трех месяцев квартала.
Целевая функция (формализованная форма изображения критерия оптимальности) задачи (3) заключается в обеспечении необходимого уровня сбалансированности посредством минимизации относительного отклонения от равномерности загрузки каждой ОГРМ в любом месяце квартала.
Укрупненный алгоритм решения задачи распределения квартального плана по месяцам согласно методу «наибольшего подобия» включает следующие основные процедуры.
1. Формируется номер месяца, по которому предстоит формирование плана:
k:= 0; k:= k + 1, k = 1,…,3.
2. Определяются соотношения столбцов матрицы исходного числового материала. Для этого значения трудоемкости изделий по j - ой ОГРМ, включая подлежащие использованию фонды времени данного 
го месяца, делим на соответствующие значения трудоемкостей первого столбца (j = 1).
3. Вычисляется отклонение структуры трудоемкости каждого изделия от структуры остающихся к загрузке фондов времени в k - ом месяце (
). Это осуществляется путем вычитания из данных, полученных в 
ом столбце, соответствующих значений соотношения фондов времени различных ОГРМ.
4. Полученные отклонения () по ой ОГРМ суммируются по абсолютной величине для 
-го изделия:
где 
- суммарное отклонение i- го изделия от соотношения остающихся к использованию фондов времени в 
ом месяце.
5. Выбирается изделие, у которого суммарное отклонение является наименьшим (min ). Это изделие имеет наибольший приоритет. Поэтому оно включается в план формируемого месяца.
6. Определяется коэффициент загрузки по каждой ОГРМ как отношение суммарной трудоемкости включенных в план формируемого k - го месяца изделий на данной стадии расчетов к первоначальной величине используемого фонда времени по данному месяцу (К 
).
Если 0,9 
К 
1,2, то рассматриваемое изделие включается в план формируемого месяца. Из дальнейших расчетов оно исключается. При этом корректируются остающиеся к использованию фонды времени по каждой ОГРМ на величину трудоемкости изделия:
, 
где
х 
- количество изделий i-го наименования, включенных в план
формируемого го месяца.
В противном случае, если изделие не обеспечивает соблюдение условия допустимой величины равномерности и полноты загрузки ОГРМ 
, то оно помещается на временное хранение в нерабочее множество.
Если окажется невозможно включить в план формируемого месяца ни одного из оставшихся изделий претендентов, то следует переход к п. 1. Иначе говоря, приступают к формированию плана следующего по порядку месяца. Далее процесс вычислений повторяется в том же порядке до тех пор, пока не наступит очередь формирования плана третьего месяца.
7. План третьего месяца определяется как разность между всей квартальной номенклатурой изделий и составом изделий, включенных в планы первого и второго месяцев.
Проиллюстрируем порядок расчетов по приведенному алгоритму на условном числовом примере. Пусть известны исходные данные, приведенные в табл. 1.1.
Таблица 1.1
Матрица числового материала по задаче распределение квартального
плана по месяцам
| Код Изделия (i) | Программа выпуска изделий на квартал, шт.
(N 
| Затраты необходимого времени на изготовление i-го изделия на j-ой ОГРМ, ч ( )
| ||
| j=1 | j=2 | j=3 | ||
| k=1 | |||
| k=2 | ||||
| k=3 |
Для выполнения лабораторной работы исходные данные, приведенные в
таблице 1 необходимо поместить в Excel на лист 1. Расчеты по методу «наибольшего подобия» проводить на этом же листе.
Практический пример расчетов.
1. Формируется номер месяца, по которому предстоит формирование плана выпуска изделий: k:= 0 + 1 = 1.
2. Определяются соотношения столбцов матрицы исходного числового материала. Результаты расчетов приведены в табл. 1.2.
Таблица 1.2
Соотношения столбцов матрицы числового материала
| Код Изделия | Соотношения столбцов | ||
| 21:21=1 | 42:21=2,0 | 65:21=3,1 | |
| 73:73=1 | 52:73=0,71 | 208:73=2,85 | |
| 30:30=1 | 64:30=2,13 | 93:30=3,1 | |
| 147:147=1 | 115:147=0,78 | 365:147=2,48 | |
| 68:68=1 | 41:68=0,6 | 160:68=2,35 | |
| 121:121=1 | 93:121=0,77 | 309:121=2,55 | |
| 49:49=1 | 101:49=2,06 | 152:49=3,1 |
3. Вычисляется отклонение структуры трудоемкости изделия от структуры остающихся к загрузке фондов времени по ОГРМ в k-ом месяце (). Результаты расчетов приведены ниже в табл. 1.3.
Таблица 1.3
Отклонение структуры трудоемкости изделия от структуры остающихся к загрузке фондов времени
| Код изделия | Результаты расчетов()
| ()
| ||
| 1-1= 0 |  2-2,06  = 0,06
| 3,1-3,1 = 0 | 0,06 | |
| 1-1= 0 | 0,71-2,06 = 1,35
| 2,85-3,1 = 0,25
| 1,6 | |
| 1-1= 0 | 2,13-2,06 = 0,07 | 3,1-3,1 = 0 | 0,07 | |
| 1-1= 0 | 0,78-2,06 = 1,28
| 2,48-3,1 = 0,62
| 1,9 | |
| 1-1= 0 | 0,6-2,06 = 1,46
| 2,35-3,1 = 0,75
| 2,21 | |
| 1-1= 0 | 0,77-2,06 = 1,29
| 2,55-3,1 = 0,55
| 1,84 |
Из приведенных выше расчетов видно, что по первому изделию имеет место наибольшее сходство структуры трудоемкости со структурой подлежащих использования фондов времени ОГРМ. Следовательно, оно и должно быть включено в план формируемого первого месяца. В дальнейших расчетах первое изделие не участвует.
4. Корректирование остающихся к использованию фондов времени по ОГРМ в результате включения первого изделия в план первого месяца в табл. 1.4.:
Таблица 1.4
Оставшиеся к использованию фондов времени по ОГРМ
| Код основных групп рабочих мест | ||
| Остающиеся к использованию фонды времени | ||
| 49 - 21 = 28 | 101 - 42 = 59 | 152 - 65 = 87 |
5. Матрица исходного числового материала принимает новый вид табл. 1.5.:
Таблица 1.5
Измененная матрица числового материала по задаче распределение квартального
плана по месяцам
| Код Изделия (i) | Программа выпуска изделий на квартал, шт.
(N )
| Затраты необходимого времени на изготовление i-го изделия на j-ой ОГРМ, ч ()
| ||
| j=1 | j=2 | j=3 | ||
|  =1
|
6. Вновь определяются соотношения столбцов матрицы исходного числового материала. Результаты расчетов приведены в табл. 1.6.
Таблица 1.6
Соотношения столбцов матрицы числового материала
| Код Изделия | Соотношения столбцов | ||
| 73:73 = 1 | 52:73 = 0,71 | 208:73 = 2,85 | |
| 30:30 = 1 | 64:30 = 2,13 | 93:30 = 3,1 | |
| 147:147 = 1 | 115:147 = 0,78 | 365:147 = 2,48 | |
| 68:68 = 1 | 41:68 = 0,6 | 160:68 = 2,35 | |
| 121:121 = 1 | 93:121 = 0,77 | 309:121 = 2,55 | |
|
| 28:28 = 1 | 59:28 = 2,11 | 87:28 = 3,11 |
7. Повторяется вычисление абсолютных отклонений структуры трудоемкости изделия от структуры остающихся к загрузке фондов времени ОГРМ в к-ом месяце (). Результаты расчетов представлены в табл. 1.7.
Таблица 1.7
Результаты расчетов абсолютных отклонений структуры
трудоемкости изделий от структуры фондов времени
| Код Изделия | Результаты расчетов()
| ()
| ||
| 1-1= 0 | 0,71-2,11 = 1,4
| 2,85-3,11 = 0,26
| 1,66 | |
| 1-1= 0 | 2,13-2,11 = 0,02 | 3,1-3,11 = 0,01 | 0,03 | |
| 1-1= 0 | 0,78-2,11 = 1,33
| 2,48-3,11 = 0,63
| 1,96 | |
| 1-1= 0 | 0,6-2,11 = 1,51
| 2,35-3,11 = 0,76
| 2,27 | |
| 1-1= 0 | 0,77-2,11 = 1,34
| 2,55-3,11 = 0,56
| 1,9 |
8. Из приведенных в табл. 19 расчетов видно, что по третьему изделию имеет место наибольшее сходство структуры трудоемкости со структурой подлежащих использования ОГРМ. Следовательно, оно и должно быть включено в план формируемого первого месяца. В дальнейших расчетах третье изделие не участвует.
9. Корректирование остающихся к использованию фондов времени по ОГРМ в результате включения третьего изделия в план первого месяца в табл. 1.8:
Таблица 1.8
Оставшиеся к использованию фондов времени по ОГРМ
| Код основных групп рабочих мест | ||
| Остающиеся к использованию фонды времени ОГРМ | ||
| 28 - 30 = -2 | 59 - 64 = -5 | 87 - 93 = -6 |
Как видим, фонды времени по всем ОГРМ исчерпаны.
10. Рассчитаем коэффициенты загрузки по каждой ОГРМ в табл. 1.9:
Таблица 1.9
Коэффициенты загрузки по каждой ОГРМ:
| Код основных групп рабочих мест | ||
| Коэффициенты загрузки по ОГРМ | ||
| (21+30): 49 = 1,04 | (42+64): 101 = 1,055 | (65+93): 152 = 1,04 |
Полученные коэффициенты загрузки ОГРМ по плану первого месяца находятся в пределах допустимых значений (не меньше 90% и не больше 120%). Переходим к формированию плана второго месяца квартала.
11. Самостоятельно сформировать план второго и третьего месяца. Результаты расчетов поместить в таблицы.
Результаты окончательных расчетов по методу «наибольшего подобия» поместить в табл. 1.1.1
Таблица 1.1.1
План распределения изделий квартальной программы по месяцам, полученный при использовании «метода наибольшего подобия»
| Первый месяц | Второй месяц | Третий месяц | ||||||
| Включенные в план коды изделий | ||||||||
| 1 и 3 | ||||||||
| Коэффициенты загрузки ОГРМ | ||||||||
j=1 
| j=2 | j=3 |  j=1
| j=2 | j=3 | j=1 | j=2 | j=3 |
| 1,04 | 1,05 | 1,04 |
Метод, базирующийся на использовании формулы линейного
Коэффициента корреляции
Для определения степени сходства между структурой трудоемкости участвующих в расчетах изделий и структурой подлежащих использованию фондов времени ОГРМ предлагается линейный коэффициент корреляции (r(tij; Fjk)):
r(
При этом последовательность вычислительного процесса остается примерно такой же, что и при использовании метода «наибольшего подобия».
Выполнение расчетов по данному методу записать на лист 2 Microsoft Excel.
Система расчетом в этом случае включает следующие основные этапы.
1. Формируется номер месяца, по которому необходимо сформировать план выпуска изделий. Начинают построение плана с первого месяца.
2. Рассчитываются по изделиям линейные коэффициенты корреляции, которые отражают степень сходства между структурой их трудоемкости и подлежащими использованию фондами времени по ОГРМ. Применительно к первому изделию коэффициент корреляции после подстановки в него соответствующих цифровых данных будет иметь такой вид:
= 0,9996
Результаты расчетов численных значений линейных коэффициентов корреляции по всем изделиям сведены в табл. 2.1.
Таблица 2.1
Численные значения линейных коэффициентов корреляции
| Код изделия | Коэффициент корреляции |
| 0,9996 | |
На основании полученных данных табл.1 определить изделие которое имеет наибольшее сходство между структурой трудоемкости и подлежащими загрузке ОГРМ в первом месяце квартала (изделие у которого коэффициент корреляции МАКСИМАЛЕН).Оно и подлежит первоочередному включению в план формируемого месяца.
3. Корректирование остающихся к использованию фондов времени по ОГРМ в результате включения этого изделия в план первого месяца (табл. 2.2).
Таблица 2.2
Результаты корректировки фондов времени по ОГРМ
| Код основных групп рабочих мест | ||
| Остающиеся к использованию фонды времени, ч | ||
| 49 - = | 101 - = | 152 - = |
Из дальнейших расчетов первое изделие выбывает.
4. Для изменившихся условий повторяется процедура, связанная с определением численных значений линейных коэффициентов корреляции. Результаты этих вычислений приведены в табл. 2.3.
Таблица 2.3
Численные значения линейных коэффициентов корреляции
| Код изделия | Коэффициент корреляции |
По результатам проведенных вычислений включаем в план первого месяца изделие с МАКСИМАЛЬНЫМ коэффициентом корреляции.
5. Корректирование остающихся к использованию фондов времени по ОГРМ в результате включения i-го изделия в план 1-го месяца (табл. 2.4).
Таблица 2.4
Результаты корректировки фондов времени по ОГРМ
| Код основных групп рабочих мест | ||
| Остающиеся к использованию фонды времени | ||
6. Рассчитаем коэффициенты загрузки по каждой ОГРМ для сформированного плана первого месяца (табл. 2.5).
Таблица 2.5
Результаты расчетов коэффициентов загрузки ОГРМ
| Код основных групп рабочих мест | ||
| Коэффициенты загрузки по ОГРМ | ||
| (+): 49 = | (+): 101 = | (+): 152 = |
Проверяем находятся ли полученные коэффициенты загрузки ОГРМ по плану первого месяца находятся в пределах допустимых значений. Если да, то переходим к формированию плана второго месяца квартала.
7. Формируем план второго и третьего месяца.
Сводим результаты расчетов по методу, основу которого составляет формула линейного коэффициента корреляции, в табл.2.1.1.
Таблица 2.1.1
План распределения изделий квартальной программы по месяцам, полученный на основе применения линейного коэффициента корреляции
| Первый месяц | Второй месяц | Третий месяц | ||||||
| Включенные в план коды изделий | ||||||||
| Коэффициенты загрузки ОГРМ | ||||||||
| j=1
| j=2 | j=3 | j=1
| j=2 | j=3 | j=1 | j=2 | j=3 |
Метод, называемый косинусом многомерного пространства. Ниже описан метод, который хотя и не приводит к оптимальному плану, но все же позволяет получать вполне практически приемлемые для руководящих менеджеров решения. Этот метод условно был назван методом косинуса многомерного пространства.
Формула для m групп рабочих мест (для m -мерного пространства) имеет вид:
cos 
.
Все расчеты по данному методу необходимо поместить в Excel на лист 3.
Для иллюстрации решения задачи распределения квартального плана по месяцам воспользуемся теми же исходными данными, которые были приведены на листе 1 Microsoft Excel в табл. 1. 1.
Последовательность расчетов остается прежней.
1. Формируется номер месяца, по которому необходимо сформировать план выпуска изделий. Начинают построение плана с первого месяца.
2. Рассчитываются числовые значения Cos2j по всем изделиям. Для иллюстрации приведем расчет по первому изделию:
Cos2j = 
Численные значения Cos2j по всем конкурирующим изделиям сведены в табл. 3.1.
Таблица 3.1
Численные значения Cos2j по изделиям, претендующим к включению в план первого месяца
| Код изделия | Cos2j |
| 0,9998 | |
Включаем в первую очередь в план 1-го месяца изделие с наибольшим значением Cos2j.
3. Корректирование остающихся к использованию фондов времени по ОГРМ в результате включения i-го изделия в план первого месяца (см. табл. 15). Из дальнейших расчетов i-е изделие выбывает.
4. Для изменившихся условий повторяется процедура, связанная с определением численных значений Cos2j. Результаты этих вычислений приведены в табл. 3.2.
Таблица 3.2
Численные значения Cos2j по оставшимся нераспределенным
изделиям
| Код изделия | Cos2j |
Включаем в план 1-го месяца изделие с наибольшим значением Cos2j.
5. Корректирование остающихся к использованию фондов времени по ОГРМ (табл. 3.3).
Таблица 3.3
Результаты корректировки фондов времени по ОГРМ
| Код основных групп рабочих мест | ||
| Остающиеся к использованию фонды времени | ||
6. Рассчитаем коэффициенты загрузки по каждой ОГРМ.
Если полученные коэффициенты загрузки ОГРМ по плану первого месяца находятся в пределах допустимых значений, то переходим к формированию плана второго месяца квартала.
7. Формируем план 2 и 3 месяца.
В сводном виде результаты решения задачи распределения выпуска изделий по месяцам квартала приводятся в табл. 3.1.1.
Таблица 3.1.1
Результаты распределения квартального плана по месяцам по методу, основывающемуся на применении Cos2j
| Номер месяца | Коды включенных изделий | Коэффициенты загрузки ОГРМ | ||
| j=1 | j=2 | j=3 | ||
Для определения наиболее предпочтительного из трех рассмотренных выше методов приведем для сравнения значения целевых функций, соответствующих полученным результатам решения задачи распределения квартального плана по месяцам на одном и том же числовом материале (табл. 4.1).
Таблица 4.1
Значения целевых функций, соответствующих вариантам решения
задачи с помощью трех различных методов
| Но-мер ме-сяца | Альтернативные методы | |||||||||
| «наибольшего подо- бия» | с использованием коэффициента корреляции | с использованием косинуса многомер- ного пространства | ||||||||
| числовые значения целевой функции, представляющих собой относительные отклонения от равномерности загрузки ОГРМ | ||||||||||
| j=1 | j=2 | j=3 | j=1 | j=2 | j=3 | j=1 | j=2 | j=3 | ||
| k=1 | ||||||||||
| k=2 | ||||||||||
| k=3 | ||||||||||
Из приведенной в табл.4.1 расчетной информации можно сделать следующие выводы.
1. Варианты решения задачи распределения квартального плана по месяцам, полученные с помощью методов «наибольшего подобия» и линейного коэффициента корреляции, удовлетворяют всем требованиям экономико-математической модели. Следовательно, они могут быть признаны оптимальными. Решение, полученное на основании применения метода, условно названного косинусом многомерного пространства, не удовлетворяет требованию равномерности загрузки ОГРМ. Поэтому его нельзя признать приемлемым.
Параметрическая оценка качества полученных вариантов планов предлагается осуществлять с помощью следующих показателей.
1. Суммарное абсолютное отклонение от равномерности загрузки ОГРМ по плановому периоду
D = 
,
где
K 
- коэффициент загрузки j-ой ОГРМ в k-м месяце квартала
(k=1,…,3);
К 
- так называемый эталонный коэффициент загрузки ОГРМ по
j-ой ОГРМ в k-ом месяце, равный 1.
2. Среднеквадратическое отклонение от равномерности загрузки ОГРМ.
s = 
.
3. Вариационный размах:
R 
(
Результаты расчетов перечисленных выше показателей по трем вариантам распределения квартального план по месяцам с помощью трех альтернативных методов cпоместить в табл. 4.2.
Таблица 4.2
Численные оценки значений показателей, используемых для оценки
уровня качества полученных трех различных вариантов планов
распределения квартального плана по месяцам
| Показатель | Вариант распределения квартального плана по месяцам, полученный с помощью | ||
| метода «наибольшего подобия» | линейного коэффициента корреляции | Косинуса многомерного пространства | |
| Суммарное абсолютное отклонение от равномерности загрузки | |||
| Среднеквадратическое отклонение | |||
| Вариационный размах |
На основании табл. 4.2 определяем наилучший вариант плана (тот у которого полученные показатели МИНИМАЛЬНЫ).
По результатам выполнения лабораторной работы сформировать отчет, показывающий последовательность проведенных вычислений по каждому методу.