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

 

 

 

 

 

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

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

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

Вариант № 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.

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

	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]