- •Тема 1. ФУНКЦИИ РЕШЕНИЯ В МЕТОДОЛОГИИ И ОРГАНИЗАЦИИ ПРОЦЕССА УПРАВЛЕНИЯ
- •1.1. Характеристика процессов управления
- •1.2. Общая характеристика проблем, задач и решений
- •1.3. Понятие и содержание управленческих решений
- •1.4. Типология управленческих решений
- •Тема 2. МОДЕЛИ, МЕТОДОЛОГИЯ И ОРГАНИЗАЦИЯ ПРОЦЕССА РАЗРАБОТКИ УПРАВЛЕНЧЕСКОГО РЕШЕНИЯ
- •2.1. Условия и факторы качества управленческого решения
- •2.2. Целевая ориентация управленческих решений
- •2.3. Критериальный язык описания выбора
- •2.3.1. Сведение многокритериальной задачи к однокритериальной
- •2.3.2. Условная оптимизация
- •2.3.3. Поиск альтернативы с заданными свойствами
- •2.3.4. Нахождение паретовского множества
- •2.4. Описание выбора на языке бинарных отношений
- •2.5. Язык функций выбора
- •Тема 3. ПРОЦЕСС ПРИНЯТИЯ РЕШЕНИЙ
- •3.1. Стандартный процесс принятия решения
- •Этап 0. Уяснение возникшей ситуации и выявление проблемы
- •Этап 1. Формулировка проблемы, постановка целей
- •Этап 2. Определение критериев
- •Этап 3. Выработка альтернатив
- •Этап 4. Сравнение альтернатив
- •Этап 5. Выбор лучшего решения
- •3.2. Условия неопределенности и риска
- •Тема 4. РАЗРАБОТКА АЛЬТЕРНАТИВ ДЕЙСТВИЙ
- •4.1. Составление списков альтернатив
- •4.2. Дерево решений (вариантов)
- •4.3. Морфологическая комбинационная таблица
- •4.4. Причинно-следственная диаграмма (диаграмма Исикавы)
- •4.5. Математическое описание множества вариантов
- •4.6. Коллективный поиск вариантов
- •Тема 5. АНАЛИЗ АЛЬТЕРНАТИВ ДЕЙСТВИЙ
- •5.1. Случайный выбор
- •5.2. Интуитивные решения
- •5.3. Решения, основанные на суждениях
- •5.4. Решения на основе максим (основных правил, принципов)
- •5.5. Решения на основе функций приоритетов
- •5.6. Графические методы анализа вариантов
- •5.7. Дерево решений (вариантов)
- •5.8. Таблицы оценок
- •5.9. Определение весовых коэффициентов
- •5.10. Поэтапное сравнение
- •5.10.1. Парное сравнение
- •5.10.2. Поэтапное сравнение
- •5.11. Бинарные решающие матрицы
- •Тема 6. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ
- •6.1. Модели теории очередей (массового обслуживания)
- •6.2. Модели управления запасами
- •6.3. Задача упорядочения и согласования. Детерминированная задача упорядочения
- •6.4. Задача о назначении
- •6.5. Модели линейного программирования. Общая линейная распределительная задача
- •6.4.1. Метод последовательных уступок
- •6.4.2. Компромиссная целевая функция
- •6.4.3. Метод многоцелевого программирования
- •Тема 7. КОЛЛЕКТИВНОЕ ПРИНЯТИЕ РЕШЕНИЙ
- •7.1. Принятие решений голосованием
- •7.2. Принятие коллективных решений в малых группах
- •7.3. Конференции по принятию решений
- •7.4. Экспертные системы принятия решений
- •Тема 8. ЭФФЕКТИВНОСТЬ РЕШЕНИЙ
- •8.1. Задача оценки эффективности решения
- •8.2. Математические методы оценки последствий решения
- •8.4. Экспертные методы оценки последствий решения
- •Тема 9. РЕАЛИЗАЦИЯ РЕШЕНИЙ И КОНТРОЛЬ
- •9.1. Контроль реализации управленческих решений
- •9.2. Управленческие решения и ответственность
- •Тема 10. ВЛИЯНИЕ ВНЕШНЕЙ СРЕДЫ И ЧЕЛОВЕЧЕСКОГО ФАКТОРА НА ПРОЦЕСС ПРИНЯТИЯ РЕШЕНИЯ
- •10.1. Анализ внешней среды и ее влияния на реализацию альтернатив
- •10.2. Влияние человеческого фактора на реализацию альтернатив
- •СЛОВАРЬ ТЕРМИНОВ
- •МАТЕРИАЛЫ ДЛЯ ТЕСТОВОЙ СИСТЕМЫ
- •СОДЕРЖАНИЕ
Это выражение называется формулой Вильсона, из которой можно устанавливать оптимальный размер поставок. С помощью этой функции можно установить и оптимальные моменты времени пополнения запасов.
6.3. Задача упорядочения и согласования. Детерминированная задача упорядочения
Постановка задачи и выбор критерия оптимизации. Пусть имеется несколько изделий,
каждое из которых должно быть обработано на двух машинах. Допустим, что известны время обработки и последовательность обработки каждого изделия на каждой машине (табл. 6.1).
Т а б л и ц а 6.1
Числовые данные задачи
Номер издания |
j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
|
|
|
|
|
|
Время обработки на первой машине |
t1j |
6 |
4 |
6 |
5 |
7 |
4 |
|
|
|
|
|
|
|
|
Время обработки на второй машине |
t2j |
5 |
2 |
3 |
6 |
6 |
7 |
|
|
|
|
|
|
|
|
Требуется выбрать такой порядок обработки изделий, при котором суммарное время обработки изделий будет минимальным (или суммарное время ожидания обработки изделий на машине).
Основные особенности, взаимосвязи и количественные закономерности. Основные ограничения задачи:
1)время перехода изделия от одной машины к другой незначительно и им можно пренебречь;
2)каждое изделие обрабатывается в определенном технологическом порядке;
3)каждое обслуживание должно быть завершено прежде, чем начнется следующее. Обозначения:
t1j – время обработки j-го изделия на первой машине; t2j – время обработки j-го изделия на второй машине.
Изобразим процесс обработки изделий на двух машинах графически (рис. 6.4):
Время |
|
t11 = 6 |
t12 = 4 |
t13 = 6 |
|
t14 = 5 |
t15 = 7 |
|
t16 = 4 |
|
|
|
|||||||
обработки на |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
машине 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Время |
|
t21 = 5 |
t22 = 2 |
|
|
t23 = 3 |
t24 = 6 |
|
t25 = 6 |
t26 = 7 |
|
||||||||
обработки на |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
машине 2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Время простоя |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
машины 2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
tn1 |
|
|
|
|
tn2 |
tn3 |
|
tn4 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
T |
|
|
|
|
|
|
|
|
Рис. 6.4. Процесс обработки изделий на двух машинах:
Т – полное время, которое пройдет от начала обработки первого изделия на первой машине до конца обработки последнего изделия на второй машине
Построение математической модели. Пусть tnj – время простоя второй машины между
концом выполнения работы по обработке (j −1)-го изделия на второй машине и началом обработки j -го изделия на той же самой машине.
Тогда суммарное время обработки изделий составит:
m |
m |
T = ∑ t2 j +∑ tnj = 29 +12 = 41 , |
|
j=1 |
j=1 |
54
m |
∑tnj |
6 |
|
а так как сумма ∑ t2 j известна, то надо минимизировать |
(в нашем случае ∑ tnj |
=12 ). |
|
j =1 |
|
j =1 |
|
Исследование математической модели. Известен весьма простой алгоритм для нахождения |
|||
оптимальной последовательности порядка обслуживания |
m |
требований на двух |
пунктах |
обслуживания (алгоритм Джонсона). При этом каждое из требований должно пройти сначала обслуживание на первом пункте, затем на втором.
Продолжительности обслуживания требований различны. Если использовать метод прямого перебора, то при наличии m требований (изделий) и двух пунктов обслуживания (машин) и при условии, что все виды требований обрабатываются в одинаковом порядке, существует m! возможных вариантов (последовательностей). (Для нашего примера имеется 720 вариантов.)
Алгоритм включает следующие основные этапы:
1. Поиск наименьшего элемента. Ищем в Т-2 наименьший элемент (равен 2, относится ко второй машине) и отмечаем точкой (табл. 6.2).
Т а б л и ц а 6.2
Первый шаг метода
Номер издания |
j |
1 |
2 |
3 |
4 |
5 |
6 |
Время обработки на первой машине |
t1j |
6 |
4 |
6 |
5 |
7 |
4 |
Время обработки на второй машине |
t2j |
5 |
2 ● |
3 ● |
6 |
6 |
7 |
Номер цикла |
– |
4 |
1 |
2 |
4 |
5 |
3 |
2. Перестановки изделий. Определяется место нахождения элемента. Если этот элемент относится к первой машине, то столбец с точкой поставить на первое место, если ко второй, то поставить на последнее место календарного плана.
При наличии равных минимальных элементов в обеих строках изделие с минимальным временем обработки на первой машине ставится на первое место; а на второй машине – на последнее. Если же одинаковые минимальные элементы оказываются в первой (второй) строке, то на первое (последнее) место ставится изделие, которому соответствует меньший элемент второй (первой) строки.
Т а б л и ц а 6.3
Второй шаг метода
Номер издания |
j |
6 |
4 |
5 |
1 |
3 |
2 |
|
|
|
|
|
|
|
|
Время обработки на первой машине |
t1j |
4 |
5 |
7 |
6 |
6 |
4 |
Время обработки на второй машине |
t2j |
7 |
6 |
6 |
5 |
3 |
2 |
3. Вычеркивание из таблицы столбца, отмеченного точкой и возвращение к п.1 и так далее, пока не будет исчерпан список всех изделий. Получим оптимальную последовательность обработки на двух машинах (Т-3).
Процесс оптимальной обработки:
t16 = 4 t14 = 5 |
t15 = 7 |
t11 = 6 |
t13 = 6 |
t12 = 4 |
|
|
|
|
|
||||||||
Время обработки на |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
машине 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
t26=7 |
t24=6 |
t25=6 |
t21=5 |
t23=3 |
|
t22=2 |
|||||||||
Время обработки на |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
машине 2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Время простоя |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
машины 2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
tn1 |
|
|
|
|
|
|
|
|
|
|
|
tn2 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Tmin = 29 + 4 + 1 = 34
Рис. 6.5. Процесс оптимальной обработки
55
Время простоя определяется графически. В некоторых частных случаях алгоритм Джонсона применяется и для решения задач, требующих трехэтапного обслуживания. Это можно сделать, когда соблюдается одна из следующих систем неравенств:
1) максимальное время обработки изделия на первой машине больше или равно максимальному времени обработки изделия на второй машине:
min { t1 j } ≥ |
max { t2 j }; |
(6.12) |
j=1,...,m |
j=1,...,m |
|
2) минимальное время обработки изделия на третьей машине больше или равно |
||
максимальному времени обработки на второй машине: |
|
|
min { t3 j } ≥ |
max { t2 j }. |
(6.13) |
j=1,...,m |
j=1,...,m |
|
После этого составляется новая таблица для суммы (t1 j +t2 j )вместо t1 j |
или (t2 j +t3 j ) вместо |
|
t2 j и к ней применяется алгоритм Джонсона. |
|
|
Класс задач, к которым применяется алгоритм Джонсона, ограничен. Решение же методом прямого перебора всех возможных вариантов уже при 10 изделиях требует более 3 млн переборов. В некоторых задачах упорядочения для решения можно использовать методы линейного и динамического программирования.
6.4. Задача о назначении
Задача о назначении в общем виде формулируется так.
Пусть имеется n работ и n кандидатов для выполнения этих работ, назначение кандидата i на работу j связано с затратами Cij .
Требуется найти назначения кандидатов на все работы, дающие минимальные суммарные затраты: при этом каждого кандидата можно назначить только на одну работу, и каждая работа может быть занята только одним кандидатом.
Это типичная экстремальная задача комбинаторного вида, ее решение путем прямого перебора практически невозможно при сколько-нибудь больших n , так как число перестановок
N = n !
Постановка задачи и выбор критерия. Пусть для монтажа четырех объектов (n = 4)
требуется четыре крана (n = 4). Из отчетных данных известно, какое время необходимо каждому крану Ai для монтажа объекта B j .
Нужно так распределить краны по объектам чтобы суммарное время на монтаж этих объектов было минимально. В нашем случае Cij – затраты времени Ai -го крана при монтаже объектов B j .
|
|
|
|
|
|
|
|
Т а б л и ц а 6.4 |
|
|
|
|
Числовые данные |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
Аi |
В1 |
В2 |
|
В3 |
|
В4 |
αi |
di |
|
|
|
|
|
|
|
|
|
|
|
А1 |
3 |
7 |
|
5 |
|
8 |
1 |
3 |
|
А2 |
2 |
4 |
|
4 |
|
5 |
1 |
2 |
|
А3 |
4 |
7 |
|
2 |
|
8 |
1 |
2 |
|
А4 |
9 |
7 |
|
3 |
|
8 |
1 |
3 |
|
Вi |
1 |
1 |
|
1 |
|
1 |
– |
– |
|
Примечание: di – минимальный элемент строки.
56
Основные особенности, взаимосвязи и количественные закономерности. Введем |
||
переменные xij |
(i, j =1,...,n) |
|
|
x(ij) |
1, если Ai−й кран распределяется на объект B j |
|
0, в противном случае. |
|
|
= |
|
|
|
|
Так как каждый кран можно распределить (назначить) только на один объект и на каждом объекте может работать только один кран, то введенные переменные xij должны подчиняться двум
условиям:
n=4 |
|
|
(6.14) |
|
∑ xij |
= xi1 + xi2 + xi3 + xi4 =1, |
i = 4, ..., 4; |
||
j=1 |
|
|
|
|
n=4 |
|
|
(6.15) |
|
∑ xij |
= x1 j + x2 j + x3 j + x4 j =1, |
j =1, ..., 4. |
||
|
i=1
Построение математической модели. Критерий оптимизации – суммарное время монтажа четырех объектовΥ математически можно записать:
4 |
4 |
|
Υ = C11 X11 +... +Cij +... +C44 X 44 = ∑∑Cij X ij . |
(6.16) |
|
i=1 |
j=1 |
|
Нужно найти xij , удовлетворяющие двум вышеприведенным условиям.
Исследование математической модели. Для решения задачи о назначении имеется насколько методов. Самый распространенный – венгерский метод.
Основной его принцип – оптимальность решения задачи о назначении – не нарушается при уменьшении (увеличении) элементов строки (столбца) на одну и ту же величину di (d j ).
Решение считается оптимальным, |
если все измененные искусственные затраты |
|
Cij ≥ 0, (i, j =1, ..., n) |
и можно отыскать такой набор xij , что |
|
|
4 |
4 |
|
Υ = ∑∑Cij′ X ij = 0 . |
|
|
i=1 |
j=1 |
Алгоритм метода включает следующие основные этапы:
1. Получение нулей в каждой строке, для чего найти наименьший элемент в каждой строке di (табл. 6.4) и вычесть его из всех элементов, получаем новую матрицу (табл. 6.5), аналогично делается для каждого столбца (табл. 6.6).
|
|
|
Первый шаг метода |
|
Т а б л и ц а 6.5 |
||
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
Аi |
Вj |
В1 |
В2 |
В3 |
В4 |
α i |
|
|
|
||||||
|
|
|
|
|
|
|
|
А1 |
|
0 |
4 |
2 |
5 |
1 |
|
А2 |
|
0 |
2 |
2 |
3 |
1 |
|
А3 |
|
2 |
5 |
0 |
6 |
1 |
|
А4 |
|
6 |
4 |
0 |
5 |
1 |
|
вi |
|
1 |
1 |
1 |
1 |
– |
|
α i |
|
0 |
2 |
0 |
3 |
– |
|
|
|
|
|
|
|
Т а б л и ц а 6.6 |
|
|
|
|
Второй шаг метода |
|
|
|
|
|
|
|
|
|
|
|
|
Аi |
Вj |
В1 |
В2 |
В3 |
В4 |
αi |
|
|
|
||||||
|
|
|
|
|
|
|
|
А1 |
|
-0-• |
-2- |
-2- |
-2- |
1 |
|
А2 |
|
- - |
-0- |
-2- |
-0- |
1 |
|
А3 |
|
2 |
3 |
0 • |
3 |
1 |
|
А4 |
|
6 |
2 |
|
2 |
1 |
|
вi |
|
1 |
1 |
1 |
1 |
– |
|
57