Принятие управленческих решений с использованием метода "дерево решений"

Размещено на http://www.allbest.ru/

[Введите текст]

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Филиал федерального государственного бюджетного образовательного учреждения высшего профессионального образования

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «МЭИ» в г. Смоленске

Кафедра менеджмента и информационных технологий в управлении

Специальность 080801 «Прикладная информатика (в экономике)»

Расчетное задание

по дисциплине «Теория систем и системный анализ»

Смоленск 2011 г.



Содержание

Введение

Задание по теме «Принятие управленческих решений с использованием метода «дерево решений»

Задание по теме «Принятие управленческих решений с использованием метода «платежной матрицы»

Задание по теме «Линейное программирование» (задача планирования производства

Задание по теме «Транспортная задача»



Введение

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

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

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

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

- Построить дерево решение для принятия управленческих решений;

- Научиться принимать управленческие решения с помощью метода «платежной матрицы»;

- Составить план производства продукции, при котором прибыль от ее реализации будет максимальной, с помощью линейного программирования;

- Разработать оптимальное распределение поставок, при котором суммарные затраты на перевозку были бы минимальными.



Задание по теме «Принятие управленческих решений с использованием метода «дерево решений»

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

А. Построить завод стоимостью 620 000 руб. При этом варианте возможны: большой спрос с вероятностью 0,3 и низкий спрос с вероятностью 0,7. Если спрос будет большим, то ожидается годовой доход в размере 270 000 руб. в течение следующих 7 лет; если спрос низкий, то ежегодные убытки из-за больших капиталовложений составят 50 000 руб.

Б. Построить маленький завод стоимостью 370 000 руб. Здесь также возможны большой спрос с вероятностью 0,83 и низкий спрос с вероятностью 0,17. В случае большого спроса ежегодный доход в течение 7 лет составит 170 000 руб., при низком спросе 30 000 руб.

В. Сразу завод не строить, а отложить решение этого вопроса на один год для сбора дополнительной информации, которая может быть позитивной или негативной с вероятностями 0,26 и 0,74 соответственно. Через год если информация окажется позитивной, можно построить большой или маленький завод по указанным выше ценам. Руководство компании может решить вообще никакого завода не строить, если информация окажется негативной. Вне зависимости от типа завода вероятности большого и низкого спроса меняются на 0,09 и 0,91 соответственно, если будет получена позитивная информация. Доходы на следующие 6 года остаются такими же, какими они были в вариантах А и Б. Все расходы выражены в текущей стоимости и не должны дисконтироваться. Стоимость сбора дополнительной информации составляет 2000.

А) Нарисуйте «дерево», охватывающее все возможности, открывающиеся перед ООО «Пирожковая».

Б) Определите наиболее эффективную последовательность действий руководства предприятия, основываясь на ожидаемых доходах каждого варианта.

Решение:

Рисунок 1 - «Дерево решений»

Оценка узлов:

EMV(А) = 270000*7*0,3 - 50000*7*0,7 - 620000 = -298000

EMV(B) = 170000*7*0,83 + 30000*7*0,17 - 370000 = 653400

EMV(D) = 270000*6*0,09 - 50000*6*0,91 - 620000 = -747200

EMV(E) = 170000*6*0,09 + 30000*6*0,91 - 370000 = -114400

EMV(2)=max{EMV(D), EMV(E)} = max{-747200, -114400} = -114400 = EMV(E)

EMV(C) =-114400*0,26 + 0*0,74 - 2000 = -31744

EMV(1)=max{EMV(A), EMV(B), EMV(C), } = max{-298000, 653400, -31744} = 653400 = EMV(B)



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

Задание по теме «Принятие управленческих решений с использованием метода «платежной матрицы»

ООО «Сладость» производит фруктовое желе. Стоимость изготовления - 40 руб. Цена желе - 50 руб.

Спрос на фруктовое желе представлен в таблице 1.

Таблица 1 - Спрос на желе

Спрос	45	50	55	60	65	70	75	80	85	90	95	100
Вероятность	4%	5%	7%	10%	14%	14%	14%	11%	10%	5%	3%	3%

В случае если не хватает порций фруктового желе, то продавщица ООО «Сладость» вынуждена для поддержания репутации компании покупать в соседнем ларьке желе по цене 75 руб.

В случае, если часть желе остается нераспроданным, его утилизируют.

Сколько порций желе необходимо производить ежедневно по рабочим дням ООО «Сладость»?

Решение

В таблице 2 приведены возможные доходы за день.

Таблица 2 - Возможные доходы за день

Возможные исходы: спрос в день	Возможные решения: число закупленных для реализации единиц
	45	50	55	60	65	70	75	80	85	90	95	100
45	450	250	50	-150	-350	-550	-750	-950	-1150	-1350	-1550	-1750
50	325	500	300	100	-100	-300	-500	-700	-900	-1100	-1300	-1500
55	200	375	550	350	150	-50	-250	-450	-650	-850	-1050	-1250
60	75	250	425	600	400	200	0	-200	-400	-600	-800	-1000
65	-50	125	300	475	650	450	250	50	-150	-350	-550	-750
70	-175	0	175	350	525	700	500	300	100	-100	-300	-500
75	-300	-125	50	225	400	575	750	550	350	150	-50	-250
80	-425	-250	-75	100	275	450	625	800	600	400	200	0
85	-550	-375	-200	-25	150	325	500	675	850	650	450	250
90	-675	-500	-325	-150	25	200	375	550	725	900	700	500
95	-800	-625	-450	-275	-100	75	250	425	600	775	950	750
100	-925	-750	-575	-400	-225	-50	125	300	475	650	825	1000
максимакс	450	500	550	600	650	700	750	800	850	900	950	1000
максимин	-925	-750	-575	-400	-350	-550	-750	-950	-1150	-1350	-1550	-1750

Пользуясь правилом максимакса, каждый раз надо изготавливать 100 ед. Это - подход очень азартного человека.

Пользуясь правилом максимина, каждый раз надо изготавливать 45 ед. Это - подход очень осторожного человека.

В таблице 3 представлены возможные потери за период.

Таблица 3 - Возможные потери за период

Возможные исходы: спрос в день	Возможные решения: число закупленных для реализации единиц
	45	50	55	60	65	70	75	80	85	90	95	100
45	0	250	500	750	1000	1250	1500	1750	2000	2250	2500	2750
50	175	0	250	500	750	1000	1250	1500	1750	2000	2250	2500
55	350	175	0	250	500	750	1000	1250	1500	1750	2000	2250
60	525	350	175	0	250	500	750	1000	1250	1500	1750	2000
65	700	525	350	175	0	250	500	750	1000	1250	1500	1750
70	875	700	525	350	175	0	250	500	750	1000	1250	1500
75	1050	875	700	525	350	175	0	250	500	750	1000	1250
80	1225	1050	875	700	525	350	175	0	250	500	750	1000
85	1400	1225	1050	875	700	525	350	175	0	250	500	750
90	1575	1400	1225	1050	875	700	525	350	175	0	250	500
95	1750	1575	1400	1225	1050	875	700	525	350	175	0	250
100	1925	1750	1575	1400	1225	1050	875	700	525	350	175	0
минимакс	1925	1750	1575	1400	1225	1250	1500	1750	2000	2250	2500	2750



Руководствуясь правилом минимакса каждый раз надо производить 65 ед.

Если руководствоваться правилом максимальной вероятности на основе таблицы 4, то нужно производить 70 ед. желе в день, так как вероятность самая большая и равна 14%.

Расчёт математического ожидания дохода представлен в таблице 4.

Таблица 4 - Математическое ожидание дохода

Возможное решение 1	Возможный доход Х	Вероятность Р	Х*Р
	450	0,04	18
	325	0,05	16,25
	200	0,07	14
	75	0,10	7,5
	-50	0,14	-7
	-175	0,14	-24,5
	-300	0,14	-42
	-425	0,11	-46,75
	-550	0,10	-55
	-675	0,05	-33,75
	-800	0,03	-24
	-925	0,03	-27,75
	Сумма	1	-205
Возможное решение 2	250	0,04	10
	500	0,05	25
	375	0,07	26,25
	250	0,10	25
	125	0,14	17,5
	0	0,14	0
	-125	0,14	-17,5
	-250	0,11	-27,5
	-375	0,10	-37,5
	-500	0,05	-25
	-625	0,03	-18,75
	-750	0,03	-22,5
	Сумма	1	-45
Возможное решение 3	50	0,04	2
	300	0,05	15
	550	0,07	38,5
	425	0,10	42,5
	300	0,14	42
	175	0,14	24,5
	50	0,14	7
	-75	0,11	-8,25
	-200	0,10	-20
	-325	0,05	-16,25
	-450	0,03	-13,5
	-575	0,03	-17,25
	Сумма	1	96,25
Возможное решение 4	-150	0,04	-6
	100	0,05	5
	350	0,07	24,5
	600	0,10	60
	475	0,14	66,5
	350	0,14	49
	225	0,14	31,5
	100	0,11	11
	-25	0,10	-2,5
	-150	0,05	-7,5
	-275	0,03	-8,25
	-400	0,03	-12
	Сумма	1	211,25
Возможное решение 5	-350	0,04	-14
	-100	0,05	-5
	150	0,07	10,5
	400	0,10	40
	650	0,14	91
	525	0,14	73,5
	400	0,14	56
	275	0,11	30,25
	150	0,10	15
	25	0,05	1,25
	-100	0,03	-3
	-225	0,03	-6,75
	Сумма	1	288,75
Возможное решение 6	-550	0,04	-22
	-300	0,05	-15
	-50	0,07	-3,5
	200	0,10	20
	450	0,14	63
	700	0,14	98
	575	0,14	80,5
	450	0,11	49,5
	325	0,10	32,5
	200	0,05	10
	75	0,03	2,25
	-50	0,03	-1,5
	Сумма	1	313,75
Возможное решение 7	-750	0,04	-30
	-500	0,05	-25
	-250	0,07	-17,5
	0	0,10	0
	250	0,14	35
	500	0,14	70
	750	0,14	105
	625	0,11	68,75
	500	0,10	50
	375	0,05	18,75
	250	0,03	7,5
	125	0,03	3,75
	Сумма	1	286,25
Возможное решение 8	-950	0,04	-38
	-700	0,05	-35
	-450	0,07	-31,5
	-200	0,10	-20
	50	0,14	7
	300	0,14	42
	550	0,14	77
	800	0,11	88
	675	0,10	67,5
	550	0,05	27,5
	425	0,03	12,75
	300	0,03	9
	Сумма	1	206,25
Возможное решение 9	-1150	0,04	-46
	-900	0,05	-45
	-650	0,07	-45,5
	-400	0,10	-40
	-150	0,14	-21
	100	0,14	14
	350	0,14	49
	600	0,11	66
	850	0,10	85
	725	0,05	36,25
	600	0,03	18
	475	0,03	14,25
	Сумма	1	85
Возможное решение 10	-1350	0,04	-54
	-1100	0,05	-55
	-850	0,07	-59,5
	-600	0,10	-60
	-350	0,14	-49
	-100	0,14	-14
	150	0,14	21
	400	0,11	44
	650	0,10	65
	900	0,05	45
	775	0,03	23,25
	650	0,03	19,5
	Сумма	1	-73,75
Возможное решение 11	-1550	0,04	-62
	-1300	0,05	-65
	-1050	0,07	-73,5
	-800	0,10	-80
	-550	0,14	-77
	-300	0,14	-42
	-50	0,14	-7
	200	0,11	22
	450	0,10	45
	700	0,05	35
	950	0,03	28,5
	825	0,03	24,75
	Сумма	1	-251,25
Возможное решение 12	-1750	0,04	-70
	-1500	0,05	-75
	-1250	0,07	-87,5
	-1000	0,10	-100
	-750	0,14	-105
	-500	0,14	-70
	-250	0,14	-35
	0	0,11	0
	250	0,10	25
	500	0,05	25
	750	0,03	22,5
	1000	0,03	30
	Сумма	1	-440

Выбираем максимум среди итоговых чисел (-205; -45; 96,25; 211,25; 288,75; 313,75; 286,25; 206,25; 85; -73,75; -251,25; -440) = 313,75. Поэтому надо производить 70 ед. желе ежедневно, если учитывать данные спроса.

Менеджер в кафе в начале дня принимает решение о закупке молока для производства коктейлей по цене 14 рублей за 1 литр цельного молока.

Известно, что спрос в пятницу может быть: 12; 14; 18; 22; 26; 30; 34 литров молока.

При реализации в составе безалкогольных коктейлей каждый литр молока реализуется по цене 20. Из наблюдений известно, что вероятность может быть 0,1; 0,15; 0,05; 0,15; 0,25; 0,1; 0,2 соответственно.

Если продукт не продали, то его используют для производства мусса, которые реализуются в кафе, принося доход 8 рублей с каждого использованного литра молока. Сколько литров цельного молока должен закупать менеджер? Дополнительное задание: Как изменится решение, если при отсутствии молока менеджер вынужден будет использовать сливки по цене 23 рубля за литр?

В таблице 5 приведены возможные доходы за день.

Таблица 5 - Возможные доходы за день

Возможные исходы: спрос в день	Возможные решения: число литров молока закупленных для реализации
	12	14	18	22	26	30	34
12	72	60	26	12	-12	-36	-60
14	72	84	60	36	12	-12	-36
18	72	84	108	84	60	36	12
22	72	84	108	132	108	84	60
26	72	84	108	132	156	132	108
30	72	84	108	132	156	180	156
34	72	84	108	132	156	180	204
Максимакс	72	84	108	132	156	180	204
Максимин	72	60	26	12	-12	-36	-60

Пользуясь правилом максимакса, каждый раз надо закупать 34 литра. Это - подход очень азартного человека.

Пользуясь правилом максимина, каждый раз надо изготавливать 12 ед. Это - подход очень осторожного человека.

В таблице 6 представлены возможные потери за период.

Таблица 6 - Возможные потери за период

Возможные исходы: спрос в день	Возможные решения: число литров молока закупленных для реализации
	12	14	18	22	26	30	34
12	0	12	36	60	84	108	132
14	12	0	24	48	72	96	120
18	36	24	0	24	48	72	96
22	60	48	24	0	24	48	72
26	84	72	48	24	0	24	48
30	108	96	72	48	24	0	24
34	132	120	96	72	48	24	0
Минимакс	132	120	96	72	84	108	132

Руководствуясь правилом минимакса каждый раз надо закупать 22 литра.

Если руководствоваться правилом максимальной вероятности на основе исходных данных, то нужно закупать 26 литров молока в день, так как вероятность самая большая равна 25%.

Расчёт математического ожидания дохода представлен в таблице 7.



Таблица 7 - Математическое ожидание дохода

Возможное решение 1	Возможный доход Х	Вероятность Р	Х*Р
	72	0,1	7,2
	72	0,15	10,8
	72	0,05	3,6
	72	0,15	10,8
	72	0,25	18
	72	0,1	7,2
	72	0,2	14,4
	Сумма	1	72
Возможное решение 2	60	0,1	6
	84	0,15	12,6
	84	0,05	4,2
	84	0,15	12,6
	84	0,25	21
	84	0,1	8,4
	84	0,2	16,8
	Сумма	1	81,6
Возможное решение 3	26	0,1	2,6
	60	0,15	9
	108	0,05	5,4
	108	0,15	16,2
	108	0,25	27
	108	0,1	10,8
	108	0,2	21,6
	Сумма	1	92,6
	36	0,15	5,4
	84	0,05	4,2
	132	0,15	19,8
	132	0,25	33
	132	0,1	13,2
	132	0,2	26,4
	Сумма	1	103,2
Возможное решение 5	-12	0,1	-1,2
	12	0,15	1,8
	60	0,05	3
	108	0,15	16,2
	156	0,25	39
	156	0,1	15,6
	156	0,2	31,2
	Сумма	1	105,6
Возможное решение 6	-36	0,1	-3,6
	-12	0,15	-1,8
	36	0,05	1,8
	84	0,15	12,6
	132	0,25	33
	180	0,1	18
	180	0,2	36
	Сумма	1	96
Возможное решение 7	-60	0,1	-6
	-36	0,15	-5,4
	12	0,05	0,6
	60	0,15	9
	108	0,25	27
	156	0,1	15,6
	204	0,2	40,8
	Сумма	1	81,6

Выбираем максимум среди итоговых чисел (72; 81,6; 92,6; 103,2; 105,6; 96; 81,6) = 105,6. Поэтому надо закупать по 26 литров молока ежедневно, если учитывать данные спроса.

Дополнительное задание: Как изменится решение, если при отсутствии молока менеджер вынужден будет использовать сливки по цене 23 рубля за литр?

Решение:

В таблице 8 приведены возможные доходы за день.

Таблица 8 - Возможные доходы за день

Возможные исходы: спрос в день	Возможные решения: число литров молока закупленных для реализации
	12	14	18	22	26	30	34
12	72	60	26	12	-12	-36	-60
14	66	84	60	36	12	-12	-36
18	54	72	108	84	60	36	12
22	42	60	96	132	108	84	60
26	30	48	84	120	156	132	108
30	18	36	72	108	144	180	156
34	6	24	60	96	132	168	204
Максимакс	72	84	108	132	156	180	204
Максимин	6	24	26	12	-12	-36	-60

Пользуясь правилом максимакса, каждый раз надо закупать 34 литра. Это - подход очень азартного человека.

Пользуясь правилом максимина, каждый раз надо изготавливать 18 ед. Это - подход очень осторожного человека.

В таблице 9 представлены возможные потери за период.

Таблица 9 - Возможные потери за период

Возможные исходы: спрос в день	Возможные решения: число литров молока закупленных для реализации
	12	14	18	22	26	30	34
12	0	12	36	60	84	108	132
14	12	0	24	48	72	96	120
18	36	24	0	24	48	72	96
22	60	48	24	0	24	48	72
26	84	72	48	24	0	24	48
30	108	96	72	48	24	0	24
34	132	120	96	72	48	24	0
Минимакс	132	120	96	72	84	108	132

Расчёт математического ожидания дохода представлен в таблице 10.

Таблица 10 - Математическое ожидание дохода

Возможное решение 1	Возможный доход Х	Вероятность Р	Х*Р
	72	0,1	7,2
	66	0,15	9,9
	54	0,05	2,7
	42	0,15	6,3
	30	0,25	7,5
	18	0,1	1,8
	6	0,2	1,2
	Сумма	1	36,6
Возможное решение 2	60	0,1	6
	84	0,15	12,6
	72	0,05	3,6
	60	0,15	9
	48	0,25	12
	36	0,1	3,6
	24	0,2	4,8
	Сумма	1	51,6
Возможное решение 3	26	0,1	2,6
	60	0,15	9
	108	0,05	5,4
	96	0,15	14,4
	84	0,25	21
	72	0,1	7,2
	60	0,2	12
	Сумма	1	71,6
	36	0,15	5,4
	84	0,05	4,2
	132	0,15	19,8
	120	0,25	30
	108	0,1	10,8
	96	0,2	19,2
	Сумма	1	90,6
Возможное решение 5	-12	0,1	-1,2
	12	0,15	1,8
	60	0,05	3
	108	0,15	16,2
	156	0,25	39
	144	0,1	14,4
	132	0,2	26,4
	Сумма	1	99,6
Возможное решение 6	-36	0,1	-3,6
	-12	0,15	-1,8
	36	0,05	1,8
	84	0,15	12,6
	132	0,25	33
	180	0,1	18
	168	0,2	33,6
	Сумма	1	93,6
Возможное решение 7	-60	0,1	-6
	-36	0,15	-5,4
	12	0,05	0,6
	60	0,15	9
	108	0,25	27
	156	0,1	15,6
	204	0,2	40,8
	Сумма	1	81,6

Выбираем максимум среди итоговых чисел (36,6; 51,6; 71,6; 90,6; 99,6; 93,6; 81,6) = 99,6. Поэтому надо закупать по 26 литров молока ежедневно, если учитывать данные спроса. Значит решение менеджера не изменится.

Задание по теме «Линейное программирование» (задача планирования производства)

Для изготовления двух видов продукции Р1 и Р2 используют три вида ресурсов S1, S2, S3. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице 11.

Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Таблица 11 - Исходные данные

Виды сырья	Нормы расхода сырья на 1 изделие (кг)	Общее количество сырья (кг)
	А	В
I	12	8	1585
II	3	5	1029
III	8	9	815
Прибыль от одного изделия, руб.	12	10

Решение:

Составим экономико-математическую модель задачи.

Обозначим: x1 - число единиц изделий вида А, планируемых к производству; x2 - число единиц изделий В, планируемых к производству.

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

Целевая функция:

Построим многоугольник допустимых решений (рисунок 2).

Рисунок 2 - Многоугольник решений

Строим вектор n(12,10). При перемещение по направлению вектора n перпендикулярной ему линии уровня F=0 находим последнюю точку касания линии уровня с областью допустимых решений. Из графика видно, что такой точкой является точка пересечения прямых и , ее координаты:



Решаем систему, получаем координаты точки , в которой и будет оптимальное решение, т.е.:

, при этом .

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

Проверка

Все условия выполняются, значит Хопт рассчитано верно.

Задание по теме «Транспортная задача»

Елена Александровна решила заняться собственным бизнесом и разместить в Италии заказ на сумочки. Изделие состоим из 5 элементов. В Италии нашлось 8 мастерских, готовых выполнить ее заказ. Но у каждой мастерской свои расценки на одну операцию. Помогите Елене Александровне минимизировать издержки по пошиву сумочек.

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



Таблица 12 - Исходные данные (вариант №3)

	Мастерские	Запас
	1	2	3	4	5	6	7	8
Элементы сумочек	1	14	19	5	1	4	3	6	7	150
	2	4	2	7	14	6	4	9	5	130
	3	10	7	8	10	6	5	4	1	190
	4	8	8	7	10	10	4	5	1	210
	5	7	2	10	2	4	9	9	4	190
Спрос	130	120	80	80	90	110	140	120

Решение:

управленческий решение линейный программирование

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



Таблица 13 - Платежная матрица

L = 130*14+20*19+100*2+30*7 +50*8+80*10+60*6+30*10+ 110*4+70*5+70*9+120*4 = 6370 (ден. ед.) - общая сумма транспортных расходов.

Ui = Vj - Сij V3 = 17 + 7 = 24 V7 = 12+5=17

Vj = Ui + Сij U3 = 24-8=16 U5 = 17-9=8

U1 = 0 V4 = 16+10=26 V8 = 8+4=12

V1 = 0+14=14 V5 = 16+6=22

V2 = 0+19=19 U4 = 22 - 10=12

U2 = 19-2=17 V6 = 12+4=16

Выполняем проверку: Ui + Сij ? Vj

U1 + C13 = 0 + 5 = 5 <24 U3 + C36 = 16 + 5 = 21 >16

U1 + C14 = 0 + 1 = 1 <26 U3 + C37 = 16 + 4 = 20 >17



U1 + C15 = 0 + 4 = 4 <22 U3 + C38 = 16 + 1 = 17 >12

U1 + C16 = 0 + 3 = 3 <16 U4 + C41 = 12 + 8 = 20 >14

U1 + C17 = 0 + 6 = 6 <17 U4 + C42 = 12 + 8 = 20 >19

U1 + C18 = 0 + 7 = 7 <12 U4 + C43 = 12 + 7 = 19 <24

U2 + C21 = 17 + 4 = 21 >14 U4 + C44 = 12 + 10 = 22 <26

U2 + C24 = 17 + 14 = 31 >26 U4 + C48 = 12 + 1 = 13 >12

U2 + C25 = 17 + 6 = 23 >22 U5 + C51 = 8 + 7 = 15 >14

U2 + C26 = 17 + 4 = 21 >16 U5 + C52 = 8 + 2 = 10 <19

U2 + C27 = 17 + 9 = 26 >17 U5 + C53 = 8 + 10 = 18 <24

U2 + C28 = 17 + 5 = 22 >12 U5 + C54 = 8 + 2 = 10 <26

U3 + C31 = 16 + 10 = 26 >14 U5 + C55 = 8 + 4 = 12 <22

U3 + C32 = 16 + 7 = 23 >19 U5 + C56 = 8 + 9 = 17 >16

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

Последовательное улучшение плана представлено в таблицах 14.

Таблица 14 - Платежная матрица



L = 130*14+20*1+120*2 +10*7+70*8+60*10+ 60*6+30*10+110*4 +70*5+70*9+120*4 = 5870 (ден. ед.)

Ui = Vj - Сij V3 = -9 + 8 = -1 V7 = -13+5= -8

Vj = Ui + Сij U2 = -1-7= -8 U5 = -8-9= -17

U1 = 0 V2 = -8+2=-6 V8 = -17+4= -13

V1 = 0+14=14 V5 = -9+6=-3

V4 = 0+1=1 U4 = -3 - 10= -13

U3 = 1-10= -9 V6 = -13+4=-9

Выполняем проверку: Ui + Сij ? Vj

U1 + C12 = 0 + 19 = 19 > -6 U3 + C36 = -9 + 5 = -4 >-9

U1 + C13 = 0 + 5 = 5 > -1 U3 + C37 = -9 + 4 = -5 >-8

U1 + C15 = 0 + 4 = 4 > -3 U3 + C38 = -9 + 1 = -8 >-13

U1 + C16 = 0 + 3 = 3 > -9 U4 + C41 = -13 + 8 = -5 <14

U1 + C17 = 0 + 6 = 6 > -8 U4 + C42 = -13 + 8 = -5 >-6

U1 + C18 = 0 + 7 = 7 > -13 U4 + C43 = -13 + 7 = -6 <-1

U2 + C21 = -8 + 4 = -4 < 14 U4 + C44 = -13 + 10 = -3 <1

U2 + C24 = -8 + 14 = 6 >1 U4 + C48 = -13 + 1 = -12 >-13

U2 + C25 = -8 + 6 = -2 > -3 U5 + C51 = -17 + 7 = -10 <14

U2 + C26 = -8 + 4 = -4 > -9 U5 + C52 = -17 + 2 = -15 <-6

U2 + C27 = -8 + 9 = 1 > -8 U5 + C53 = -17 + 10 = -7 <-1

U2 + C28 = -8 + 5 = -3 > -13 U5 + C54 = -17 + 2 = -15 <1

U3 + C31 = -9 + 10 = 1 <14 U5 + C55 = -17 + 4 = -13 <-3

U3 + C32 = -9 + 7 = -2 > -6 U5 + C56 = -17 + 9 = -8 >-9

Условие оптимизации не выполняется. Для улучшения плана необходимо переместить перевозку в клетку (5;1).



Таблица 15 - Платежная матрица

L = 100*14+50*1+120*2+ 10*7+70*8+30*10+ 90*6+110*4+100*5+ 30*7+40*9 +120*4 = 5150 (ден. ед.)

Ui = Vj - Сij V7 = 7 + 9 = 16 U2 = -1 - 7= -17

Vj = Ui + Сij V8 = 7+4= 11 V2 = -17+2= -6

U1 = 0 U4 = 16 - 5= 11 V5 = -9+6= -3

V1 = 0+14=14 V6 = 11+4=15

V4 = 0+1=1 U3 = 1 - 10= -9

U5 = 14-7= 7 V3 = -9+8= -1

Выполняем проверку: Ui + Сij ? Vj

U1 + C12 = 0 + 19 = 19 > -6 U3 + C36 = -9 + 5 = -4 <15

U1 + C13 = 0 + 5 = 5 > -1 U3 + C37 = -9 + 4 = -5 <16

U1 + C15 = 0 + 4 = 4 > -3 U3 + C38 = -9 + 1 = -8 <11

U1 + C16 = 0 + 3 = 3 < 15 U4 + C41 = 11+ 8 = 19 >14

U1 + C17 = 0 + 6 = 6 < 16 U4 + C42 = 11+ 8 = 19 >-6

U1 + C18 = 0 + 7 = 7 < 11 U4 + C43 = 11+ 7 = 18 >-1

U2 + C21 = -8 + 4 = -4 < 14 U4 + C44 = 11+ 10 = 21 >1



U2 + C24 = -8 + 14 = 6 >1 U4 + C45 = 11+ 10 = 21 >-3

U2 + C25 = -8 + 6 = -2 > -3 U4 + C48 = 11 + 1 = 12 >11

U2 + C26 = -8 + 4 = -4 < 15 U5 + C52 = 7 + 2 = 9 >-6

U2 + C27 = -8 + 9 = 1 < 15 U5 + C53 = 7+ 10 = 17 >-1

U2 + C28 = -8 + 5 = -3 > 11 U5 + C54 = 7+ 2 = 9 >1

U3 + C31 = -9 + 10 = 1 <14 U5 + C55 = 7+ 4 = 11 >-3

U3 + C32 = -9 + 7 = -2 > -6 U5 + C56 = 7+ 9 = 16 >15

Условие оптимизации не выполняется. Для улучшения плана необходимо переместить перевозку в клетку (3;7).

Таблица 16 - Платежная матрица

L = 70*14+80*1+120*2+10*7+ 70*8+90*6+30*4+110*4+ 100*5+ 60*7+ 10*9 + 120*4 = 4520 (ден. ед.)

Ui = Vj - Сij V7 = 7 + 9 = 16 V5 = 12+6= 18

Vj = Ui + Сij V8 = 7+4= 11 U2 = 20 - 7= 13

U1 = 0 U4 = 16 - 5= 11 V2 = 13+2= 15

V1 = 0+14=14 V6 = 11+4=15

V4 = 0+1=1 U3 = 16 - 4= 12

U5 = 14-7= 7 V3 = 12+8= 20



Выполняем проверку: Ui + Сij ? Vj

U1 + C12 = 0 + 19 = 19 > 15 U3 + C34 = 12 + 10 = 22 >1

U1 + C13 = 0 + 5 = 5 < 20 U3 + C36 = 12 + 5 = 17 >15

U1 + C15 = 0 + 4 = 4 < 18 U3 + C38 = 12 + 1 = 13 >11

U1 + C16 = 0 + 3 = 3 < 15 U4 + C41 = 11+ 8 = 19 >14

U1 + C17 = 0 + 6 = 6 < 16 U4 + C42 = 11+ 8 = 19 >15

U1 + C18 = 0 + 7 = 7 < 11 U4 + C43 = 11+ 7 = 18 <20

U2 + C21 = 13 + 4 = 17 > 14 U4 + C44 = 11+ 10 = 21 >1

U2 + C24 = 13 + 14 = 27 >1 U4 + C45 = 11+ 10 = 21 >18

U2 + C25 = 13 + 6 = 19 > 18 U4 + C48 = 11 + 1 = 12 >11

U2 + C26 = 13 + 4 = 17 > 15 U5 + C52 = 7 + 2 = 9 <15

U2 + C27 = 13 + 9 = 22 > 16 U5 + C53 = 7+ 10 = 17 <20

U2 + C28 = 13 + 5 = 18 > 11 U5 + C54 = 7+ 2 = 9 >1

U3 + C31 = 12 + 10 = 22 >14 U5 + C55 = 7+ 4 = 11 <18

U3 + C32 = 12 + 7 = 19 > 15 U5 + C56 = 7+ 9 = 16 >15

Условие оптимизации не выполняется. Для улучшения плана необходимо переместить перевозку в клетку (1;3).

Таблица 17 - Платежная матрица



L = 60*14+10*5+ 80*1+120*2+ 10*7+60*8+ 90*6+40*4+ 110*4+100*5 +70*7+120*4 = 4370 (ден. ед.)

Ui = Vj - Сij U5 = 14-7= 7 V7 = -3 + 4 = 1

Vj = Ui + Сij V8 = 7+4= 11 U4 = 1 - 5= -4

U1 = 0 U2 = 5 - 7= -2 V6 = -4+4=0

V1 = 0+14=14 U3 = 5 - 8= -3

V3 = 0+5= 5 V2 = -2+2= 0

V4 = 0+1=1 V5 = -3+6= 3

Выполняем проверку: Ui + Сij ? Vj

U1 + C12 = 0 + 19 = 19 > 0 U3 + C36 = -3 + 5 = 2 >0

U1 + C15 = 0 + 4 = 4 > 3 U3 + C38 = -3 + 1 = -2 <11

U1 + C16 = 0 + 3 = 3 > 0 U4 + C41 = -4+ 8 = 4 <14

U1 + C17 = 0 + 6 = 6 > 1 U4 + C42 = -4+ 8 = 4 >0

U1 + C18 = 0 + 7 = 7 < 11 U4 + C43 = -4+ 7 = 3 <5

U2 + C21 = -2 + 4 = 2 < 14 U4 + C44 = -4+ 10 = 6 >1

U2 + C24 = -2 + 14 = 12 >1 U4 + C45 = -4+ 10 = 6 >3

U2 + C25 = -2 + 6 = 4 > 3 U4 + C48 = -4 + 1 = -3 <11

U2 + C26 = -2 + 4 = 2 > 0 U5 + C52 = 7 + 2 = 9 >0

U2 + C27 = -2 + 9 = 7 > 1 U5 + C53 = 7+ 10 = 17 >5

U2 + C28 = -2 + 5 = 3 < 11 U5 + C54 = 7+ 2 = 9 >1

U3 + C31 = -3 + 10 = 7 <14 U5 + C55 = 7+ 4 = 11 >3

U3 + C32 = -3 + 7 = 4 > 0 U5 + C56 = 7+ 9 = 16 >0

U3 + C34 = -3 + 10 = 7 >1 U5 + C57 = 7+ 9 = 16 >1

Условие оптимизации не выполняется. Для улучшения плана необходимо переместить перевозку в клетку (4;8).



Таблица 18 - Платежная матрица

L = 70*5+80*1+ 120*2+10*7+90*6 +100*4+110*4+40*5+60*1 +130*7+ 60*4 = 3530 (ден. ед.)

Выполняем проверку: Ui + Сij ? Vj

U1 + C11 = 0 + 14 = 14 > 0 U3 + C34 = -3 + 10 = 7 >1

U1 + C12 = 0 + 19 = 19 > 0 U3 + C36 = -3 + 5 = 2 >0

U1 + C15 = 0 + 4 = 4 > 3 U3 + C38 = -3 + 1 = -2 >-3

U1 + C16 = 0 + 3 = 3 > 0 U4 + C41 = -4+ 8 = 4 >0

U1 + C17 = 0 + 6 = 6 > 1 U4 + C42 = -4+ 8 = 4 >0

U1 + C18 = 0 + 7 = 7 > -3 U4 + C43 = -4+ 7 = 3 <5

U2 + C21 = -2 + 4 = 2 > 0 U4 + C44 = -4+ 10 = 6 >1

U2 + C24 = -2 + 14 = 12 >1 U4 + C45 = -4+ 10 = 6 >3

U2 + C25 = -2 + 6 = 4 > 3 U5 + C52 = -7 + 2 = -5 <0

U2 + C26 = -2 + 4 = 2 > 0 U5 + C53 = -7+ 10 = 3 <5

U2 + C27 = -2 + 9 = 7 > 1 U5 + C54 = -7+ 2 = -5 <1

U2 + C28 = -2 + 5 = 3 > -3 U5 + C55 = -7+ 4 = -3 <3

U3 + C31 = -3 + 10 = 7 >0 U5 + C56 = -7+ 9 = 2 >0

U3 + C32 = -3 + 7 = 4 > 0 U5 + C57 = -7+ 9 = 2 >1



Условие оптимизации не выполняется. Для улучшения плана необходимо переместить перевозку в клетку (5;5).

Таблица 19 - Платежная матрица

L = 70*5+80*1+120*2 +10*7+0*8+50*6 +140*4+110*4+ 100*1+130*7 +40*4+20*4 = 3290 (ден. ед.)

Выполняем проверку: Ui + Сij ? Vj

U1 + C11 = 0 + 14 = 14 > 6 U3 + C34 = -3 + 10 = 7 >1

U1 + C12 = 0 + 19 = 19 > 0 U3 + C36 = -3 + 5 = 2 <6

U1 + C15 = 0 + 4 = 4 > 3 U3 + C38 = -3 + 1 = -2 <3

U1 + C16 = 0 + 3 = 3 < 6 U4 + C41 = 2+ 8 = 10 >6

U1 + C17 = 0 + 6 = 6 > 1 U4 + C42 = 2+ 8 = 10 >0

U1 + C18 = 0 + 7 = 7 > 3 U4 + C43 = 2+ 7 = 9 >5

U2 + C21 = -2 + 4 = 2 < 6 U4 + C44 = 2+ 10 = 12 >1

U2 + C24 = -2 + 14 = 12 >1 U4 + C45 = 2+ 10 = 12 >3

U2 + C25 = -2 + 6 = 4 > 3 U4 + C47 = 2+ 5 = 7 >1

U2 + C26 = -2 + 4 = 2 < 6 U5 + C52 = -1 + 2 = 1 >0



U2 + C27 = -2 + 9 = 7 > 1 U5 + C53 = -1+ 10 = 9 >5

U2 + C28 = -2 + 5 = 3 = 3 U5 + C54 = -1+ 2 = 1 =1

U3 + C31 = -3 + 10 = 7 >6 U5 + C56 = -1+ 9 = 8 >6

U3 + C32 = -3 + 7 = 4 > 0 U5 + C57 = -1+ 9 = 8 >1

Условие оптимизации не выполняется. Для улучшения плана необходимо переместить перевозку в клетку (3;8).

Таблица 20 - Платежная матрица

L = 70*5+80*1+120*2+10*7 +0*8+30*6+140*4 +20*1+110*4+ 100*1+130*7+60*4 = 3190 (ден. ед.)

Выполняем проверку: Ui + Сij ? Vj

U1 + C11 = 0 + 14 = 14 > 6 U3 + C34 = -3 + 10 = 7 >1

U1 + C12 = 0 + 19 = 19 > 0 U3 + C36 = -3 + 5 = 2 >1

U1 + C15 = 0 + 4 = 4 > 3 U4 + C41 = -3 + 8 = 5 <6

U1 + C16 = 0 + 3 = 3 > 1 U4 + C42 = -3 + 8 = 5 >0

U1 + C17 = 0 + 6 = 6 > 1 U4 + C43 = -3 + 7 = 4 <5

U1 + C18 = 0 + 7 = 7 > -2 U4 + C44 = -3 + 10 = 7 >1



U2 + C21 = -2 + 4 = 2 < 6 U4 + C45 = -3 + 10 = 7 >3

U2 + C24 = -2 + 14 = 12 >1 U4 + C47 = -3 + 5 = 2 >1

U2 + C25 = -2 + 6 = 4 > 3 U5 + C52 = -1 + 2 = 1 >0

U2 + C26 = -2 + 4 = 2 >1 U5 + C53 = -1+ 10 = 9 >5

U2 + C27 = -2 + 9 = 7 > 1 U5 + C54 = -1+ 2 = 1 =1

U2 + C28 = -2 + 5 = 3 > -2 U5 + C56 = -1+ 9 = 8 >1

U3 + C31 = -3 + 10 = 7 >6 U5 + C57 = -1+ 9 = 8 >1

U3 + C32 = -3 + 7 = 4 > 0 U5 + C58 = -1+ 4 = 3 >-2

Условие оптимизации не выполняется. Для улучшения плана необходимо переместить перевозку в клетку (2;1).

Таблица 21 - Платежная матрица

L = 70*5+80*1 +10*4+120*2 +10*8+20*6+ 140*4+20*1+110*4+ 100*1+120*7+70*4 = 3150 (ден. ед.)

Выполняем проверку: Ui + Сij ? Vj

U1 + C11 = 0 + 14 = 14 > 6 U3 + C34 = -3 + 10 = 7 >1



U1 + C12 = 0 + 19 = 19 > 4 U3 + C36 = -3 + 5 = 2 >1

U1 + C15 = 0 + 4 = 4 > 3 U4 + C41 = -3 + 8 = 5 <6

U1 + C16 = 0 + 3 = 3 > 1 U4 + C42 = -3 + 8 = 5 >4

U1 + C17 = 0 + 6 = 6 > 1 U4 + C43 = -3 + 7 = 4 <5

U1 + C18 = 0 + 7 = 7 > -2 U4 + C44 = -3 + 10 = 7 >1

U2 + C23 = 2 + 7 = 9 > 6 U4 + C45 = -3 + 10 = 7 >3

U2 + C24 = 2 + 14 = 16 >1 U4 + C47 = -3 + 5 = 2 >1

U2 + C25 = 2 + 6 = 8 > 3 U5 + C52 = -1 + 2 = 1 <4

U2 + C26 = 2 + 4 = 6 >1 U5 + C53 = -1+ 10 = 9 >5

U2 + C27 = 2 + 9 = 11 > 1 U5 + C54 = -1+ 2 = 1 =1

U2 + C28 = 2 + 5 = 7 > -2 U5 + C56 = -1+ 9 = 8 >1

U3 + C31 = -3 + 10 = 7 >6 U5 + C57 = -1+ 9 = 8 >1

U3 + C32 = -3 + 7 = 4 = 4 U5 + C58 = -1+ 4 = 3 >-2

Условие оптимизации не выполняется. Для улучшения плана необходимо переместить перевозку в клетку (5;2).

Таблица 22 - Платежная матрица

L = 70*5+80*1+130*4+0*2+10*2+10*8+20*6+140*4+20*1+110*4+100*1 +120*2+70*4 = 2790 (ден. ед.)



Выполняем проверку: Ui + Сij ? Vj

U1 + C11 = 0 + 14 = 14 > 6 U3 + C34 = -3 + 10 = 7 >1

U1 + C12 = 0 + 19 = 19 > 4 U3 + C36 = -3 + 5 = 2 >1

U1 + C15 = 0 + 4 = 4 > 3 U4 + C41 = -3 + 8 = 5 >3

U1 + C16 = 0 + 3 = 3 > 1 U4 + C42 = -3 + 8 = 5 >1

U1 + C17 = 0 + 6 = 6 > 1 U4 + C43 = -3 + 7 = 4 <5

U1 + C18 = 0 + 7 = 7 > -2 U4 + C44 = -3 + 10 = 7 >1

U2 + C23 = -1 + 7 = 6 > 5 U4 + C45 = -3 + 10 = 7 >3

U2 + C24 = -1 + 14 = 13 >1 U4 + C47 = -3 + 5 = 2 >1

U2 + C25 = -1 + 6 = 5 > 3 U5 + C51 = -1 + 7 = 6 >3

U2 + C26 = -1 + 4 = 3 >1 U5 + C53 = -1+ 10 = 9 >5

U2 + C27 = -1 + 9 = 8 > 1 U5 + C54 = -1+ 2 = 1 =1

U2 + C28 = -1 + 5 = 4> -2 U5 + C56 = -1+ 9 = 8 >1

U3 + C31 = -3 + 10 = 7 >3 U5 + C57 = -1+ 9 = 8 >1

U3 + C32 = -3 + 7 = 4 > 1 U5 + C58 = -1+ 4 = 3 >-2

Условие оптимизации не выполняется. Для улучшения плана необходимо переместить перевозку в клетку (4;3).

Таблица 23 - Платежная матрица

	Мастерские	Запас
	1	2	3	4	5	6	7	8
	V1 =4	V2 =2	V3 =5	V4 = 1	V5 =4	V6 = 2	V7 = 2	V8 = -1
Элементы сумочек	1	U1 = 0	14	19	5 70	1 80	4	3	6	7	150
	2	U2 = 0	4 130	2 0	7	14	6	4	9	5	130
	3	U3 = -2	10	7	8	10	6 20	5	4 140	1 30	190
	4	U4 = -2	8	8	7 10	10	10	4 110	5	1 90	210
	5	U5 = 0	7	2 120	10	2	4 70	9	9	4	190
Спрос	130	120	80	80	90	110	140	120

L = 70*5+80*1+130*4+0*2+20*6+140*4+30*1+10*7+110*4+90*1+120*2 +70*4 = 2780 (ден. ед.)

Выполняем проверку: Ui + Сij ? Vj

U1 + C11 = 0 + 14 = 14 > 4 U3 + C33 = -2 + 8 = 6 >5

U1 + C12 = 0 + 19 = 19 > 2 U3 + C34 = -2 + 10 = 8 >1

U1 + C15 = 0 + 4 = 4 = 4 U3 + C36 = -2 + 5 = 3 >2

U1 + C16 = 0 + 3 = 3 > 2 U4 + C41 = -2 + 8 = 6 >4

U1 + C17 = 0 + 6 = 6 > 2 U4 + C42 = -2 + 8 = 6 >2

U1 + C18 = 0 + 7 = 7 > -1 U4 + C44 = -2 + 10 = 8 >1

U2 + C23 = 0 + 7 = 7 > 5 U4 + C45 = -2 + 10 = 8 >4

U2 + C24 = 0 + 14 = 14 >1 U4 + C47 = -2 + 5 = 3 >2

U2 + C25 = 0 + 6 = 6 > 4 U5 + C51 = 0 + 7 = 7 >4

U2 + C26 = 0 + 4 = 4 >2 U5 + C53 = 0+ 10 = 10 >5

U2 + C27 = 0 + 9 = 9 > 2 U5 + C54 = 0+ 2 = 2 >1

U2 + C28 = 0 + 5 = 5> -1 U5 + C56 = 0+ 9 = 9 >2

U3 + C31 = -2 + 10 = 8 >4 U5 + C57 = 0+ 9 = 9 >2

U3 + C32 = -2 + 7 = 5 > 2 U5 + C58 = 0+ 4 = 4 >-1

В таблице 23 условие оптимизации выполняется для всех свободных клеток. Следовательно, данное решение является оптимальным. Ответ: L = 2780.

Размещено на Allbest.ru