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