Транспортная задача. Метод северо-западного угла. Транспортная задача. Метод северозападного угла
 Скачать 227.61 Kb.
|
|
Этап II. Нахождение оптимального решения. Найдем оптимальный план транспортной задачи методом потенциалов. Опорный план имеет следующий вид:
При этом плане стоимость перевозок вычисляется так: S=2·14+6·39+8·27+4·8+3·25+0·48=585 Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 6 уравнений с 7 неизвестными: β1−α1=2 β1−α2=6 β2−α2=8 β2−α3=4 β3−α3=3 β3−α4=0 Полагая α1=0, находим β1=2 α2=-4 β2=4 α3=0 β3=3 α4=3 . Для каждой свободной клетки вычисляем число αij=βj−αi−cij: α12=1, α13=-1, α23=2, α31=-3, α41=-1, α42=1. Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы Модель транспортной задачи (Таблица 9). Таблица 9 – Модель транспортной задачи
Среди чисел αij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 2 находится в пересечении строки A2 и столбца B3. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак "+" а остальные клетки цикла поочередно знаки "−" и "+" Модель транспортной задачи (Таблица 10). Таблица 10 – Модель транспортной задачи
Наименьшее из чисел в минусовых клетках равно 25. Клетка, в которой находится это число становится свободной. В новой таблице другие числа получаются так. Числам, находящимся в плюсовых клетках добавляется 25, а из чисел, находящихся в минусовых клетках вычитается это число (Таблица 11). Таблица 11 – Модель транспортной задачи
Опорный план имеет следующий вид:
При этом плане стоимость перевозок вычисляется так: S=2·14+6·39+8·2+5·25+4·33+ 0·48= 535 Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 6 уравнений с 7 неизвестными: β1−α1=2 β1−α2=6 β2−α2=8 β3−α2=5 β2−α3=4 β3−α4=0 Полагая α1=0, находим β1=2 α2=-4 β2=4 β3=1 α3=0 α4=1 . Для каждой свободной клетки вычисляем число αij=βj−αi−cij: α12=1, α13=-3, α31=-3, α33=-2, α41=1, α42=3. Полученные числа заключаем в рамки и записываем их в соответствующие клетки таблицы (Таблица 12). Таблица 12 – Модель транспортной задачи
Среди чисел αij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 3 находится в пересечении строки A4 и столбца B2. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак "+" а остальные клетки цикла поочередно знаки "−" и "+" (Таблица 13). Таблица 13 – Модель транспортной задачи
Наименьшее из чисел в минусовых клетках равно 2. Клетка, в которой находится это число становится свободной. В новой таблице другие числа получаются так. Числам, находящимся в плюсовых клетках добавляется 2, а из чисел, находящихся в минусовых клентках вычитается это число (Таблица 14). Таблица 14 – Модель транспортной задачи
Опорный план имеет следующий вид:
При этом плане стоимость перевозок вычисляется так: S=2·14+6·39+5·27+4·33+0·2+ 0·46= 529 Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 6 уравнений с 7 неизвестными: β1−α1=2 β1−α2=6 β3−α2=5 β2−α3=4 β2−α4=0 β3−α4=0 Полагая α1=0, находим β1=2 α2=-4 β3=1 α4=1 β2=1 α3=-3 . Для каждой свободной клетки вычисляем число αij=βj−αi−cij: α12=-2, α13=-3, α22=-3, α31=0, α33=1, α41=1. Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы (Таблица 15). Таблица 15 – Модель транспортной задачи
Среди чисел αij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 1 находится в пересечении строки A3 и столбца B3. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак "+" а остальные клетки цикла поочередно знаки "−" и "+" (Таблица 16). Таблица 16 – Модель транспортной задачи
Наименьшее из чисел в минусовых клетках равно 33. Клетка, в которой находится это число становится свободной. В новой таблице другие числа получаются так. Числам, находящимся в плюсовых клетках добавляется 33, а из чисел, находящихся в минусовых клентках вычитается это число (Таблица 17). Таблица 17 – Модель транспортной задачи
Опорный план имеет следующий вид:
При этом плане стоимость перевозок вычисляется так: S=2·14+6·39+5·27+3·33+0·35 +0·13 =496 Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 6 уравнений с 7 неизвестными: β1−α1=2 β1−α2=6 β3−α2=5 β3−α3=3 β2−α4=0 β3−α4=0 Полагая α1=0, находим β1=2 α2=-4 β3=1 α3=-2 α4=1 β2=1 . Для каждой свободной клетки вычисляем число αij=βj−αi−cij: α12=-2, α13=-3, α22=-3, α31=-1, α32=-1, α41=1. Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы (Таблица 18). Таблица 18 – Модель транспортной задачи
Среди чисел αij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 1 находится в пересечении строки A4 и столбца B1. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак "+" а остальные клетки цикла поочередно знаки "−" и "+" (Таблица 19). Таблица 19– Модель транспортной задачи
Наименьшее из чисел в минусовых клетках равно 13. Клетка, в которой находится это число становится свободной. В новой таблице другие числа получаются так. Числам, находящимся в плюсовых клетках добавляется 13, а из чисел, находящихся в минусовых клентках вычитается это число (Таблица 20). Таблица 20– Модель транспортной задачи
Опорный план имеет следующий вид:
При этом плане стоимость перевозок вычисляется так: S=2·14+6·26 +5·40+3·33+ 0·13+ 0·35= 483 Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 6 уравнений с 7 неизвестными: β1−α1=2 β1−α2=6 β3−α2=5 β3−α3=3 β1−α4=0 β2−α4=0 Полагая α1=0, находим β1=2 α2=-4 α4=2 β3=1 β2=2 α3=-2 . Для каждой свободной клетки вычисляем число αij=βj−αi−cij: α12=-1, α13=-3, α22=-2, α31=-1, α32=0, α43=-1. Полученные числа заключаем в рамки и записываем их в соответствующие клетки таблицы (Таблица 21). Таблица 21– Модель транспортной задачи
Среди чисел αij нет положительных. Следовательно данный опорный план является оптимальным. Удаляем добавленный пункт отправления: Оптимальный план имеет следующий вид:
При этом плане стоимость перевозок вычисляется так: S=2·14+6·26+5·40+3·33=483 При этом плане остается неудовлетворенным потребности (13) пункта B1, потребности (35) пункта B2. Распределение ресурсов: Из склада A1 отправить груз (14) в пункт B1 Из склада A2 отправить груз (26) в пункт B1 Из склада A2 отправить груз (40) в пункт B3 Из склада A3 отправить груз (33) в пункт B3 Вывод: Задачу решили, нашли оптимальный план перевозок, в процессе решении задачи рассмотрели метод северо-западного угла и метод потенциалов. 3.3 Программная реализация Программу писали на языке C# используя Windows Forms. Вводим количество потребителей и поставщиков, заполняем матрицу стоимости во вкладке условие задачи (Рисунок 2).  Рисунок 2 – Условие задачи Во вкладке решение, видим две таблицы, первая опорный план, который был найден методом северо-западного угла, вторая таблица оптимальное решение, которая было получено методом потенциалов и цена перевозок (Рисунок 3).  Рисунок 3 – Решение задачи ЗаключениеВ ходе курсовой работы мы рассмотрели “транспортные задачи” и составили их общую характеристику. Затем построили математическую модель и подробно разобрали решение задачи на конкретном примере, используя метод северо-западного угла. Методом потенциалов, сделали программную реализацию на языке “python”. Исходя из полученных нами расчётов, мы получили нужное количество товара, направляемого от поставщика к потребителю, а также варианты маршрутов, удовлетворяющих один из главных вопросов «транспортной задачи» - оптимальность результата. В результате проделанной работы, мы познакомились с этапами решения транспортных задач и применениями данного типа задач в жизни, спроецировав их на актуальных примерах. Научились определять и грамотно решать данные задачи. По итогам проделанной работы программа успешно решает заданную транспортную задачу и выдаёт верные результаты в соответствии с нашими предварительными расчётами. Все задачи и цели курсовой работы выполнены. Таким образом, можно сделать вывод, что транспортная задача — это математическая задача линейного программирования специального вида, которую можно рассматривать как задачу об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. С ростом потребительской способности населения вопрос оптимизации путей доставки товара потребителю будет подниматься все чаще, следовательно повысится и потребность в его решении возрастет. Соответственно актуальность транспортной задачи не пропадет еще долгие годы. Список литературы1. Струченков В. И. Методы оптимизации / В. И. Струченков. – Москва : ГЭОТАР-Медиа, 2019. – 315 с. 2. Болдырев Ю. Я. Вариационное исчисление и методы оптимизации / Ю. Я. Болдырев. – Москва : МАИ, 2020. – 240 с. 3. А. В. Аттетков. Введение в методы оптимизации / А. В. Аттетков– Москва : Юрайт, 2018. – 441 с. 4. Вячеслав Ф. В. Численные методы оптимизации / Ф. В. Вячеслав – Москва : Юрайт, 2019. – 368 с. 5. Кохендерфер М. В. Алгоритмы оптимизации / М. В. Кохендерфер. – Москва : Вильямс, 2019. – 528 с. 6. Золоторев А. А. Методы оптимизации распределительных процессов / А. А. Золоторев. – Москва : Инфра-Инженерия, 2018. – 160 с. 7. Бертсекас Р. Н. Условная оптимизация и методы множителей Лагранжа / Р. Н. Бертсекас – Москва : Инфра-Инженерия, 2020. – 400 с. 8. Беленький А. С. Исследование операций в транспортных системах / А. С. Беленький – Москва : Мир, 2020. – 582 с. 9. Ганшин Г.С. Методы оптимизации и решения уравнений / Г.С. Ганшин – Москва : Наука, 2019. – 129 с. 10. Токарев В. В. Методы оптимизации. Задачник / В. В. Токарев – Москва : Наука, 2019. – 292 с. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||