Автор: Пользователь скрыл имя, 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
5. У нас есть отрицательные разности, значит опорный план не оптимальный, а значит, необходима перепланировка.
6. Выбираем клетку с наименьшей разностью. Это клетка . Из неё строим контур, вершины которого будут лежать в заполненных клетках.
7. Вершина в пустой клетке имеет знак «+», знаки остальных вершин чередуются.
8. Среди отрицательных вершин выбираем наименьшую поставку. Это поставка, равная .
9. Эту поставку мы прибавляем к поставке в клетке с положительными вершинами и отнимаем от поставок в клетках с отрицательными вершинами.
10. В клетке оставляем нулевую поставку, чтоб опорный план был вырожденный.
Полученный опорный план:
Посчитаем стоимость данного опорного плана по формуле:
Перепланировка представлена в таблице 9.
Таблица 9
1. Проверяем план на вырожденность по формуле:
где – количество строк, - количество столбцов.
число заполненных клеток – . План – вырожденный.
2. Приписываем каждому поставщику и каждому потребителю потенциалы. Берем один любой потенциал, равный любому произвольному числу. В нашем случае возьмем .
3. Используя заполненные клетки транспортной таблицы, мы определяем значения остальных потенциалов из условия, что
где – потенциалы поставщиков, – потенциалы.
, , , , |
, , . |
4.Далее для пустых клеток определяем разности:
Все разности неотрицательные, значит опорный план оптимальный, перепланировка не требуется.
Полученный опорный план:
Посчитаем стоимость данного опорного плана по формуле:
1.5. Построение опорного плана методом Фогеля
Преобразуем данные задачи 1 в таблицу 10.
Таблица 10
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. В последнюю клетку мы доставляем оставшуюся мощность поставщика , полностью удовлетворяя спрос потребителя , равную .
Полученный опорный план:
Посчитаем стоимость данного опорного плана по формуле:
1.6. Метод потенциала на основе опорного плана, полученного методом Фогеля
Снова преобразуем данные в таблицу. Теперь она будет иметь немного иной вид. Появятся наименование и значение потенциалов. Так выглядит таблица 11.
Таблица 11
1.Проверяем план на вырожденность по формуле:
где – количество строк, - количество столбцов.
число заполненных клеток – . План – невырожденный. В клетку делаем нулевую поставку. Тогда план получится вырожденным.
2. Приписываем каждому поставщику и каждому потребителю потенциалы. Берем один любой потенциал, равный любому произвольному числу. В нашем случае возьмем .
3. Используя заполненные клетки транспортной таблицы, мы определяем значения остальных потенциалов из условия, что
где – потенциалы поставщиков, – потенциалы.
, , , , |
, , . |
4.Далее для пустых клеток определяем разности:
Все разности неотрицательные, значит опорный план оптимальный, перепланировка не требуется.
Полученный опорный план:
Посчитаем стоимость данного опорного плана по формуле:
Вывод: самый выгодный опорный план получен методом Фогеля.
Решение задачи №2
2.1. Построение опорного
плана методом северо-
Определим тип задачи:
Мощность всех поставщиков равна . Спрос всех потребителей . Транспортная модель – открытого типа. Введем фиктивного потребителя со спросом в единиц товара (его транспортные издержки равны 0).
Преобразуем данные задачи №2 в таблицу 12.
Таблица 12
1. В исходной таблице ищем северо-западный (верхний левый) угол. Это клетка (с транспортной издержкой ).
2. Производим в неё поставку, которая смогла бы максимально удовлетворить спрос потребителя , учитывая мощность поставщика . Это количество товара .
3. Так как спрос потребителя удовлетворен, зачеркиваем столбец .
4. Снова находим северо-западный угол. Это клетка (с транспортной издержкой ).
5. Производим в неё поставку, которая смогла бы максимально удовлетворить спрос потребителя , учитывая мощность поставщика . Это количество товара, оставшееся у поставщика после первой поставки, .
6. Так как мощность поставщика иссякла, зачеркиваем строку .
7. Снова находим северо-западный угол. Это клетка (с транспортной издержкой ).
8. Производим в неё поставку, которая смогла бы максимально удовлетворить спрос потребителя , учитывая мощность поставщика . Это количество товара .
9. Так как спрос потребителя удовлетворен, зачеркиваем столбец .
10. Снова находим северо-западный угол. Это клетка (с транспортной издержкой ).
11. Производим в неё поставку, которая смогла бы максимально удовлетворить спрос потребителя , учитывая мощность поставщика . Это количество товара .
12. Так как спрос потребителя удовлетворен, зачеркиваем столбец .
13. Снова находим северо-западный угол. Это клетка (с транспортной издержкой ).
14. Производим в неё поставку, которая смогла бы максимально удовлетворить спрос потребителя , учитывая мощность поставщика . Это количество товара
15. Так как мощность поставщика иссякла, закрываем строку .
16. Снова находим самый северо-западный угол. Это клетка .
17.Производим в неё поставку, которая смогла бы максимально удовлетворить спрос потребителя , учитывая мощность поставщика . Это количество товара .
18. Далее производим поставку в клетку , которая смогла бы максимально удовлетворить спрос потребителя , учитывая мощность поставщика . Это количество товара .
Полученный опорный план:
Посчитаем стоимость данного опорного плана по формуле:
2.2. Метод потенциала
на основе опорного плана,
Снова преобразуем данные в таблицу 13.
Таблица 13
1. Проверяем план на вырожденность по формуле:
где – количество строк, - количество столбцов.
число заполненных клеток – . План – вырожденный.
2. Приписываем каждому поставщику и каждому потребителю потенциалы. Берем один любой потенциал, равный любому произвольному числу. В нашем случае возьмем .
3. Используя заполненные клетки транспортной таблицы, мы определяем значения остальных потенциалов из условия, что
где – потенциалы поставщиков, – потенциалы.
, , , , |
, , , . |