Автор работы: Пользователь скрыл имя, 04 Марта 2014 в 09:15, курсовая работа
В данной курсовой работе будут рассмотрены: понятие транспортной задачи, её особенности, решение транспортных задач методами северо – западного угла, минимальной стоимости, Фогеля, а так же методом потенциалов.
Целью транспортной задачи является обеспечение получения (доставки) продукции (товара) потребителю в нужное время и место при минимально возможных совокупных затратах трудовых, материальных, финансовых ресурсов.
Объектом изучения являются материальные и соответствующие им финансовые, информационные потоки, сопровождающие производственно-коммерческую деятельность.
Особенности транспортной задачи:
1.Система ограничений это система линейных уравнений.
2.Коэффициенты при переменных в системе уравнений равны 1 или 0.
Введение……………………………………………………………………3-4.
1.Транспортные задачи закрытого типа………………………………….4-13.
1.1.Метод СЗУ………………………………………………………........4-6.
1.2.Метод минимальной стоимости……………………………….........7-9.
1.3.Метод Фогеля……………………………………………………......10-13.
2.Метод потенциалов……………………………………………………..14-29
2.1.СЗУ……………………………………………………………….......14-21
2.2.Метод минимальной стоимости……………………………………21-26.
2.3.Метод Фогеля………………………………………………………..26-29.
Заключение……………………………………………………………………30.
Список используемой литературы…………………………………………..31.
Мы полностью удовлетворили потребность потребителя, исключаем его из рассмотрения.
Таблица 14.
2. Далее заполняем транспортную таблицу 15 и 16 по алгоритму СЗУ, учитывая фиктивного потребителя.
Таблица 15
Таблица 16
Таблица 17
Итак, мы полностью израсходовали запасы поставщиков и удовлетворили запросы потребителей.
3. Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться , где - количество строк в таблице, - количество столбцов в таблице. Количество базисных ячеек равно 7, а требуется, чтобы было 8.
Таблица 18
Количество задействованных маршрутов равно 8, что и требовалось.
Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.
4. Рассчитаем сумму.
Но наша задача стоит в использовании метода потенциалов, итак найдем для данной транспортной таблицы потенциалы.
5. Как уже говорилось, первое значение мы берем произвольно.
Допустим .
Таблица 19
Таблица 20
6. Далее работаем с пустыми ячейками.
По данной формуле, находим оценки свободных ячеек :
7. Вносим их в транспортную таблицу 21.
Таблица 21
Среди оценок свободных ячеек есть отрицательные, следовательно, решение не является оптимальным.
8. Сделаем перепланировку .
Таблица 22
9. Записываем таблицу с новыми маршрутами.
Таблица 23
10. Найдем снова потенциалы и поработаем с пустыми клетками.
Таблица 24
Среди оценок свободных ячеек есть отрицательные, следовательно, решение не является оптимальным.
11. Строим новый маршрут в таблице 25.
Таблица 25
12. Далее производим аналогичные действия и повторяем шаги до получения оптимального плана.
В итоге мы получим транспортную таблицу вида.
Таблица 26
Sсзу = 850 ден. ед.
2.2.Метод минимальной стоимости
Найдем начальное решение методом минимального элемента. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется не оптимальным, используя метод потенциалов, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение.
Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей. Проверим это условие.
1. В нашем случае, поставщик может дать потребителю товара больше, чем ему требуется, значит, для решения задачи вводим фиктивного потребителя.
Условия задачи остаются прежними. Составим таблицу, которая будет иметь вид:
Таблица 27
2. Таблицу заполняем согласно алгоритму метода минимальной стоимости для задачи закрытого типа, учитывая фиктивного потребителя.
Таблица28
Мы нашли начальное решение, т.е. израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.
3. Для решения задачи методом потенциалов нужно подсчитать потенциалы для каждого поставщика и потребителя.
Примем и посчитаем все потенциалы. Далее дадим оценки свободных ячеек.
Получим таблицу 29 вида:
Таблица 29
После занесения значений в таблицу видим, что есть отрицательные значения в ячейках. Делаем перепланировку.
Таблица 30
4. Делаем перерасчет в ячейках данного маршрута и получаем таблицу вида:
Таблица 31
5. Пересчитаем снова потенциалы и произведем оценку свободных ячеек, чтобы проверить план на оптимальность.
Таблица 32
6. Так как в ячейках есть отрицательные значения, делаем перепланировку.
Таблица 33
Получаем таблицу 34 вида:
Таблица 34
7. Далее снова пересчитываем потенциалы, чтобы проверить оптимальность данного плана.
Получаем таблицу 35 вида:
Таблица 35
Все оценки свободных ячеек неотрицательные, следовательно, найдено оптимальное решение.
Можем найти транспортные расходы:
Smin = 2 40 + 1 90 + 1 95 + 4 5 + 3 25 + 4 95 + 0 35 + 1 110 = 850
Общие затраты на доставку всей продукции, для оптимального решения, составляют 850 ден. ед.
2.3.Метод Фогеля
Найдем начальное решение методом Фогеля. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется не оптимальным, используя метод потенциалов, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение.
Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей. Проверим это условие. В нашем случае, потребность всех потребителей - 495 единиц продукции равна запасам всех поставщиков.
1. Согласно условию задачи составим таблицу 36.
Таблица 36
2. Решаем задачу методом Фогеля и получим транспортную таблицу 37.
Таблица 37
3. Для решения задачи найдем потенциалы и оценки свободных ячеек.
Таблица 38
Так как у нас имеются отрицательные значения в ячейках, то следует сделать перепланировку.
Таблица 39
Далее получим таблицу 40 вида:
Таблица 40
4. Далее вновь проверим новый план на оптимальность.
Таблица 41
Sф = 850
Общие затраты на доставку всей продукции, для начального решения, составляют 850 ден. ед.
Заключение
Необходимость решения задач линейного программирования на современных предприятиях очевидна. Построение и решение транспортных задач позволяет, в свою очередь, решать различные технико-экономические и экономические производственные задачи, будь то проблема оптимальной загрузки станка и раскройки стального листа или анализ межотраслевого баланса и оценки темпов роста экономики страны в целом.
В данной курсовой работе были систематизированы теоретические положения по теме применения методов линейного программирования при решении задач, рассмотрена сущность задач линейного программирования, выявлены основные методы решения задач линейного программирования.
Список используемой литературы
1. Лекционный материал доцента кафедры «Прикладная математика» Иванова Андрея Николаевича.
2. Литвак Б. Г. Разработка управленческого решения: Учебник. - 3-е изд., испр. - М.: Дело 2002.
3. Орлов А. И. Теория принятия решений: Учеб. пособие.- М.: Издательство «Март», 2004.