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