Автор работы: Пользователь скрыл имя, 20 Марта 2013 в 15:01, курсовая работа
Цель работы: построить модель наиболее экономичного распределенияресурсов и доказать, что данное решение является наиболее экономичным.
Основные аспекты исследования транспортной модели состоят в следующем: доказательство того, что сформулированная задача имеет решение; обоснование положения о том, что это решение является оптимальным; изучение влияния на полученное решение любых изменений условий задачи.
Министерство транспорта Российской Федерации
Федеральное агентство железнодорожного транспорта
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Дальневосточный государственн
Кафедра «Прикладная математика»
Курсовая работа по дисциплине
«Методы принятия управленческих решений»
МЕТОДЫ ПРИНЯТИЯ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ
Вариант №3
Выполнил(а):студент(ка) группы Ц18 (1 курс, 2 семестр),
направления 080200 «Менеджмент»,
специальности 080200.62 «Логистика»,
Визгин Павел Владимирович
Проверил:(преподаватель, ст.преподаватель, доцент, профессор)
кафедры «Прикладная математика»
РЕЙТИНГОВЫЙ БАЛЛ за курсовую работу: _______
ОТМЕТКА за курсовую работу:_______
Хабаровск
2012
Введение
Цель работы: построить модель наиболее экономичного распределенияресурсов и доказать, что данное решение является наиболее экономичным.
Основные аспекты исследования транспортной модели состоят в следующем: доказательство того, что сформулированная задача имеет решение; обоснование положения о том, что это решение является оптимальным; изучение влияния на полученное решение любых изменений условий задачи.
Транспортная задача — задача о поиске оптимального распределения поставок однородного товара от поставщиков к потребителям при известных затратах на перевозку (тарифах) между пунктами отправления и назначения. Является задачей линейного программирования специального вида. Транспортная задача может быть записана в виде прямоугольной таблицы.
Пример подобной таблицы приведен ниже:
№ поставщика |
Мощность поставщика |
Потребители и их спрос | ||||
1 |
2 |
3 |
4 |
5 | ||
20 |
30 |
20 |
10 |
10 | ||
1 |
30 |
2 |
3 |
2 |
4 |
1 |
2 |
40 |
3 |
2 |
5 |
1 |
2 |
3 |
20 |
4 |
3 |
2 |
6 |
3 |
Цена перевозки (например, в рублях
за 1 килограмм груза) Cij записывае
Допустимое (но не всегда оптимальное с точки зрения стоимости доставки) начальное решение транспортной задачи можно построить, последовательно перебирая строки таблицы (то есть поставщиков) сверху вниз. В пределах каждой строки, нужно перебрать слева направо не охваченных или не полностью охваченных поставками потребителей, записывая в соответствующие ячейки объем поставляемого груза от поставщика в данной строке, и так до исчерпания возможностей поставщика. Таким образом, весь груз от поставщиков будет распределен по потребителям.
Другой метод получения
Для поиска начального решения транспортной задачи можно применить также метод Фогеля, который обычно дает еще более приближенное к оптимальному решение.
Метод потенциалов позволяет за несколько шагов (итераций) найти полностью оптимальное решение транспортной задачи. Перед решением задачи этим методом нужно найти допустимое начальное решение одним из методов, описанных выше.
Так же, если сумма запасов равна сумме потребностей, то транспортная задача называется закрытой. Если равенство не соблюдается, то задача называется открытой. Для решения транспортной задачи необходимо, чтобы она была приведена к закрытому виду. Если это равенство не соблюдено, необходимо ввести фиктивного поставщика или фиктивного потребителя на недостающий или избыточный объем товара, которому нужно приписать нулевую цену доставки. Этот объем будет соответствовать недопоставке или, напротив, избытку товара на складе.
Постановка задачи
Дано n поставщиков А1, А2 …. Аn, предложение каждого i-го поставщика составляетaiединиц i =1, n.
Дано mпотребителей B1 , B2, ... Bn,спрос каждого j- потребителя составляет bjединиц , j = 1,m.
Дана стоимость перевозкиCijединицы товара от i-го поставщикаj -му
потребителю.
Требуется составить план перевозок от i-го поставщика к j- му потребителю с минимальной стоимостью и рассчитать стоимость плана перевозок.
Запасы:
A1 = 95,
A2 = 45,
A3 = 65,
A4 = 35,
Потребности:
B1 = 75,
B2 = 85,
B3 = 65,
B4 = 15,
Матрица стоимости перевозок:
9 |
10 |
3 |
4 |
7 |
8 |
5 |
6 |
15 |
4 |
8 |
11 |
7 |
4 |
6 |
8 |
В предыдущих исходных данных заменить
А4 = 60
Решение:
1) Метод северо-западного угла
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов. Проверим необходимое и достаточное условие разрешимости задачи.
Проверим необходимое
и достаточное условие
∑a = 95 + 45 + 65 + 35 = 240
∑b = 75 + 85 + 65 + 15 = 240
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Поиск первого опорного плана.
1. Используя метод
северо-западного угла, построим
первый опорный план
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число
занятых клеток таблицы, их 7, а
должно быть m + n - 1 = 7. Следовательно,
опорный план является
Значение целевой функции для этого опорного плана равно:
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi>cij
Выбираем максимальную оценку свободной клетки (1;4): 4
Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалыui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi>cij
Выбираем максимальную оценку свободной клетки (1;3): 3
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалыui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi>cij
Выбираем максимальную оценку свободной клетки (2;1): 7
Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 25. Прибавляем 25 к объемам грузов, стоящих в плюсовых клетках и вычитаем 25 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалыui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi>cij
Выбираем максимальную оценку свободной клетки (4;2): 4
Для этого в перспективную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалыui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi>cij
Выбираем максимальную оценку свободной клетки (4;1): 7
Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 3) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалыui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi<= cij.
Минимальные затраты составят:
S = 9*15 + 3*65 + 4*15 + 7*45 + 4*65 + 7*15 + 4*20 = 1150
Поиск второго опорного плана.
1. Используя метод наименьшей
стоимости, построим первый
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
В результате получен первый опорный
план, который является допустимым,
так как все грузы из баз
вывезены, потребность магазинов
удовлетворена, а план соответствует
системе ограничений
2. Подсчитаем число занятых
Значение целевой функции для этого опорного плана равно:
Этап II. Улучшение опорного плана.
Проверим оптимальность