Методы принятия управленческих решений

Автор: Пользователь скрыл имя, 11 Марта 2013 в 11:59, курсовая работа

Краткое описание

Одна из наиболее распространенных задач математического программирования — транспортная задача. Транспортная задача (задача Монжа —Канторовича) —математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Скачать в ZIP (166.02 Кб) Сколько стоит заказать работу?

Файлы: 1 файл

Курсовая работа МПУР.docx

— 171.84 Кб (Скачать)

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

Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v₁=20	v₂=21	v₃=24	v₄=33	v₅=33
u₁=0	20[50]	21[20]	22	23	24
u₂=7	22	28[45]	31[20]	40	15
u₃=10	23	27	34[45]	43[15]	18

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем максимальную оценку свободной клетки : 15

Для этого в перспективную клетку поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	50	65	65	55	30
70	20[50]	21[20]	22	23	24
65	22	28[45]	31[20] [-]	40	15 [+]
90	23	27	34[45] [+]	43[45] [-]	18

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	50	65	65	55	30
70	20[50]	21[20]	22	23	24
65	22	28[45]	31	40	15[20]
90	23	27	34[65]	43[25]	18

	v₁=20	v₂=21	v₃=-1	v₄=8	v₅=8
u₁=0	20[50]	21[20]	22	23	24
u₂=7	22	28[45]	31	40	15[20]
u₃=35	23	27	34[65]	43[25]	18

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Аналогично выполняя все действия, находим оптимальный опорный план:

	50	65	65	55	30
70	20	21	22[55]	23[15]	24
65	22	28[25]	31[10]	40	15[30]
90	23[50]	27[40]	34	43	18

	v₁=15	v₂=19	v₃=22	v₄=23	v₅=6
u₁=0	20	21	22[55]	23[15]	24
u₂=9	22	28[25]	31[10]	40	15[30]
u₃=8	23[50]	27[40]	34	43	18

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем максимальную оценку свободной клетки (2;1): 22

Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	50	65	65	55	30
70	20	21	22[55]	23[15]	24
65	22 [+]	28[25] [-]	31[10]	40	15[30]
90	23[50] [-]	27[40] [+]	34	43	18

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 25. Прибавляем 25 к объемам грузов, стоящих в плюсовых клетках и вычитаем 25 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план

	50	65	65	55	30
70	20	21	22[55]	23[15]	24
65	22[25]	28	31[10]	40	15[30]
90	23[25]	27[65]	34	43	18

	v₁=13	v₂=17	v₃=22	v₄=23	v₅=6
u₁=0	20	21	22[55]	23[15]	24
u₂=9	22[25]	28	31[10]	40	15[30]
u₃=10	23[25]	27[65]	34	43	18

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:

F(x) = 22*55 + 23*15 + 22*25 + 31*10 + 15*30 + 23*25 + 27*65 = 5195

МЕТОД МИНИМАЛЬНОЙ СТОИМОСТИ

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

Проверим необходимое и достаточное условие разрешимости задачи.

∑ a = 70 + 65 + 90 = 225

∑ b = 50 + 65 + 65 + 55 + 30 = 265

Занесем исходные данные в распределительную таблицу.

	50	65	65	55	30
70	20	21	22	23	24
65	22	28	31	40	15
90	23	27	34	43	18

Построим первый опорный план транспортной задачи.

	50	65	65	55	30
70	20[50]	21[20]	22	23	24
65	22	28	31[35]	40	15[30]
90	23	27[45]	34[30]	43[15]	18

Определяем оценку для каждой свободной клетки.

В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	50	65	65	55	30
70	20[50]	21[20] [-]	22 [+]	23	24
65	22	28	31[35]	40	15[30]
90	23	27[45] [+]	34[30] [-]	43[15]	18

Оценка свободной клетки равна Δ₁₃ = -6

Аналогично выполняем оценку для каждой свободной клетки:

Оценка свободной клетки равна Δ₁₄ = -14

Оценка свободной клетки равна Δ₁₅ = 12

Оценка свободной клетки равна Δ₂₁ = -1

Оценка свободной клетки равна Δ₂₂ = 4

Оценка свободной клетки равна Δ₂₄ = 0

Оценка свободной клетки равна Δ₃₁ = -3

Оценка свободной клетки равна Δ₃₅ = 0

Оценка свободной клетки равна Δ₄₁ = 17

Оценка свободной клетки равна Δ₄₂ = 16

Оценка свободной клетки равна Δ₄₃ = 9

Оценка свободной клетки равна Δ₄₅ = 25

Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (1,4;) равные: (-14).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	50	65	65	55	30
70	20[50]	21[5]	22	23[15]	24
65	22	28	31[35]	40	15[30]
90	23	27[60]	34[30]	43	18

Информация о работе Методы принятия управленческих решений