Автор: Пользователь скрыл имя, 27 Октября 2013 в 12:25, курсовая работа
Целью данной работы является рассмотрение транспортной задачи и метода потенциалов как метода ее решения.
Новизна и практическая значимость работы обусловлена тем фактом, что транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.
Введение..................................................................................................................3
Постановка задачи..................................................................................................4
Часть 1. Решение задачи №1.................................................................................6
1.1. Построение опорного плана методом северо-западного угла.............6
1.2. Метод потенциала на основе опорного плана, построенного методом северо-западного угла..........................................................7
1.3. Построение опорного плана методом минимальной стоимости.......15
1.4. Метод потенциала на основе опорного плана, построенного методом минимальной стоимости....................................................17
1.5. Построение опорного плана методом Фогеля....................................23
1.6. Метод потенциала на основе опорного плана, построенного методом Фогеля..................................................................................25
Часть 2. Решение задачи №2...............................................................................27
2.1. Построение опорного плана методом северо-западного угла...........27
2.2. Метод потенциала на основе опорного плана, построенного методом северо-западного угла........................................................29
2.3. Построение опорного плана методом минимальной стоимости.......37
2.4. Метод потенциала на основе опорного плана, построенного методом минимальной стоимости....................................................39
2.5. Построение опорного плана методом Фогеля....................................45
2.6. Метод потенциала на основе опорного плана, построенного методом Фогеля..................................................................................47
Заключение............................................................................................................50
Список использованной литературы..................................................................51
2. Приписываем каждому поставщику и каждому потребителю потенциалы. Берем один любой потенциал, равный любому произвольному числу. В нашем случае возьмем .
3. Используя заполненные клетки транспортной таблицы, мы определяем значения остальных потенциалов из условия, что
где – потенциалы поставщиков, – потенциалы.
, , , , |
, , , . |
4. Далее для пустых клеток определяем разности:
5. У нас есть отрицательные разности, значит опорный план не оптимальный, а значит, необходима перепланировка.
6. Выбираем клетку с наименьшей разностью. Это клетка . Из неё строим контур, вершины которого будут лежать в заполненных клетках.
7. Вершина в пустой клетке имеет знак «+», знаки остальных вершин чередуются.
8. Среди отрицательных вершин выбираем наименьшую поставку. Это поставка, равная .
9. Эту поставку мы прибавляем к поставке в клетке с положительными вершинами и отнимаем от поставок в клетках с отрицательными вершинами.
Полученный опорный план:
Посчитаем стоимость данного опорного плана по формуле:
Перепланировка представлена в таблице 20.
Таблица 20
1. Проверяем лан на вырожденность по формуле
где – количество строк, - количество столбцов.
число заполненных клеток – . План – невырожденный, поэтому в клетку делаем нулевую поставку.
2. Приписываем каждому поставщику и каждому потребителю потенциалы. Берем один любой потенциал, равный любому произвольному числу. В нашем случае возьмем .
3. Используя заполненные клетки транспортной таблицы, мы определяем значения остальных потенциалов из условия, что
где – потенциалы поставщиков, – потенциалы.
, , , , |
, , , . |
4. Далее для пустых клеток определяем разности:
5. У нас есть отрицательные разности, значит опорный план не оптимальный, а значит, необходима перепланировка.
6. Выбираем клетку с наименьшей разностью. Это клетка . Из неё строим контур, вершины которого будут лежать в заполненных клетках.
7. Вершина в пустой клетке имеет знак «+», знаки остальных вершин чередуются.
8. Среди отрицательных вершин выбираем наименьшую поставку. Это поставка, равная .
9. Эту поставку мы прибавляем к поставке в клетке с положительными вершинами и отнимаем от поставок в клетках с отрицательными вершинами.
10. В клетке оставляем нулевую поставку, чтоб опорный план был вырожденный.
Полученный опорный план:
Посчитаем стоимость данного опорного плана по формуле:
Перепланировка представлена в таблице 21.
Таблица 21
1. Проверяем план на вырожденность по формуле:
где – количество строк, - количество столбцов.
число заполненных клеток – . План – вырожденный.
2. Приписываем каждому поставщику и каждому потребителю потенциалы. Берем один любой потенциал, равный любому произвольному числу. В нашем случае возьмем .
3. Используя заполненные клетки транспортной таблицы, мы определяем значения остальных потенциалов из условия, что
где – потенциалы поставщиков, – потенциалы.
, , , , |
, , , . |
4.Далее для пустых клеток определяем разности:
Все разности неотрицательные, значит опорный план оптимальный, перепланировка не требуется.
Полученный опорный план:
Посчитаем стоимость данного опорного плана по формуле:
2.5 Построение опорного плана методом Фогеля
Представим данные задачи №2 в таблицу 22.
Таблица 22
1. Находим в каждой строке самую минимальную транспортную издержку. Затем ближайшую к ней минимальную транспортную издержку.
2. Находим разность этих издержек и записываем в конце строки вне таблицы.
3. Повторяем пункты только уже для столбцов.
4. Выбираем самую большую разность. В нашем случае это разность столбце .
5. Находим минимальную транспортную издержку в этом столбце. Это клетка с транспортной издержкой .
6. Производим в неё поставку, которая смогла бы максимально удовлетворить спрос потребителя , учитывая мощность поставщика . Это количество товара .
7. Так как спрос потребителя удовлетворен, закрываем столбец .
8. Повторяем пункты .
9. Снова выбираем самую большую разность. В этот раз это разность строчке . (Когда у нас более одной наибольшей разности мы можем выбрать любую одну, на своё усмотрение).
10. Находим минимальную транспортную издержку в этом столбце. Это клетка , с транспортной издержкой .
11. Производим в неё поставку, которая смогла бы максимально удовлетворить спрос потребителя , учитывая мощность поставщика . Это количество товара .
12. Так как спрос потребителя удовлетворен, закрываем столбец .
13. Так как мощность поставщика иссякла, закрываем строку .
14. Повторяем пункты .
15. Снова выбираем самую большую разность. В этот раз это разность столбца .
16. Находим минимальную транспортную издержку в этом столбце. Это клетка , с транспортной издержкой .
17. Производим в неё поставку, которая смогла бы максимально удовлетворить спрос потребителя , учитывая мощность поставщика . Это количество товара .
18. Так как спрос потребителя удовлетворен, закрываем столбец .
19. Повторяем пункты .
20. Снова выбираем самую большую разность. В этот раз это разность столбца .
21. Находим минимальную транспортную издержку в этом столбце. Это клетка , с транспортной издержкой .
22. Производим в неё поставку, которая смогла бы максимально удовлетворить спрос потребителя , учитывая мощность поставщика . Это количество товара .
23. Так как спрос потребителя удовлетворен, закрываем столбец .
24. У нас осталось всего две клетки. Выбираем минимальную транспортную издержку, это клетка с транспортной издержкой .
25. Производим в неё поставку, которая смогла бы максимально удовлетворить спрос потребителя , учитывая мощность поставщика . Это количество товара .
26. В последнюю клетку мы доставляем оставшуюся мощность поставщика , полностью удовлетворяя спрос потребителя , равную .
Полученный опорный план:
Посчитаем стоимость данного опорного плана по формуле:
2.6. Метод потенциала на основе опорного плана, полученного методом Фогеля
Преобразуем данные в таблице 23.
Таблица 23
1. Проверяем план на вырожденность по формуле:
где – количество строк, - количество столбцов.
число заполненных клеток – . План – невырожденный, поэтому в клетку делаем нулевую поставку.
2. Приписываем каждому поставщику и каждому потребителю потенциалы. Берем один любой потенциал, равный любому произвольному числу. В нашем случае возьмем .
3. Используя заполненные клетки транспортной таблицы, мы определяем значения остальных потенциалов из условия, что
где – потенциалы поставщиков, – потенциалы.
, , , , |
, , , . |
4.Далее для пустых клеток определяем разности:
Все разности неотрицательные, значит опорный план оптимальный, перепланировка не требуется.
Полученный опорный план:
Посчитаем стоимость данного опорного плана по формуле:
Вывод: самый выгодный план получен
методом Фогеля.
Заключение
В работе изложены основные подходы и методы решения транспортной задачи, являющейся одной из наиболее распространенных задач линейного программирования. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие: