Ирина Эланс

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

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

Курсовая работа по дисциплине

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

МЕТОДЫ ПРИНЯТИЯ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ

Вариант № 5

Хабаровск

2012

ВВЕДЕНИЕ

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

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

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

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

ПОСТАНОВКА ЗАДАЧИ

Дано 3 поставщика:

, , Предложение поставщика составляет 70 единиц, i=1; поставщика составляет 65 единиц, i=2; поставщика составляет 90 единиц, i=3.

Дано 5 потребителей:

, , , , .Спрос потребителя составляет 50 единиц, j=1; потребителя составляет 65 единиц, j=2;потребителя составляет 65 единиц, j=3; потребителя составляет 15 единиц, j=4; потребителя составляет 30 единиц, j=5.

Дана стоимость перевозки:

единицы товара от 1 поставщика к 1 потребителю =20;

единицы товара от 1 поставщика к 2 потребителю =21;

единицы товара от 1 поставщика к 3 потребителю =22;

единицы товара от 1 поставщика к 4 потребителю =23;

единицы товара от 1 поставщика к 5 потребителю =24;

единицы товара от 2 поставщика к 1 потребителю =22;

единицы товара от 2 поставщика к 2 потребителю =28;

единицы товара от 2 поставщика к 3 потребителю =31;

единицы товара от 2 поставщика к 4 потребителю =40;

единицы товара от 2 поставщика к 5 потребителю =15;

единицы товара от 3 поставщика к 1 потребителю =23;

единицы товара от 3 поставщика к 2 потребителю =27;

единицы товара от 3 поставщика к 3 потребителю =34;

единицы товара от 3 поставщика к 4 потребителю =43;

единицы товара от 3 поставщика к 5 потребителю =18.

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

Общая стоимость перевозок равна:

S==

Матрица транспортных расходов имеет вид:

СОДЕРЖАНИЕ

МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА

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

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

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

∑ a = 70 + 65 + 90 = 225

∑ b = 50 + 65 + 65 + 15 + 30 = 225

Ищем первый опорный план:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21*55 + 23*15 + 31*65 + 23*50 + 27*10 + 18*30 = 5475

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21*55 + 23*15 + 31*65 + 23*50 + 27*10 + 18*30 = 5475

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21*25 + 22*30 + 23*15 + 31*35 + 15*30 + 23*50 + 27*40 = 5295

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	50	65	65	15	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

22*55 + 23*15 + 22*25 + 31*10 + 15*30 + 23*25 + 27*65 = 5195

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

	50	65	65	15	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

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

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

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

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

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

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

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

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

	50	65	65	15	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 [+]

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

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

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

22*55 + 23*15 + 22*25 + 31*10 + 15*30 + 23*25 + 27*65 = 5195

МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА

МЕТОД ПОТЕНЦИАЛОВ

Математическая модель транспортной задачи:

F = ∑∑c_ijx_ij, (1)

при условиях:

∑x_ij = a_i, i = 1,2,…, m, (2)

∑x_ij = b_j, j = 1,2,…, n, (3)

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

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

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

∑a = 70 + 65 + 90 = 225

∑b = 50 + 65 + 65 + 15 + 30 = 225

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

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

Методы принятия управленческих решений. 35 📙 Курсовая → 🆔 128812