Примеры решения транспортной задачи

План будет называться оптимальным , если он, среди всех допустимых планов, приводит к максимальной суммарной стоимости перевозок. Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще. Найдем вначале допустимое опорное решение транспортной задачи. Это решение можно найти, используя метод "северо-западного угла" или метод "минимального элемента".

Находим следующую наименьшую по стоимости ячейку — их несколько, например, A1B1. Присваиваем ей значение 3, а сумму по столбцу заменяем на Выбираем ячейку A3B3, присваиваем ей значение 5. Сумму по третьей строке заменяем на Выбираем ячейку A3B1, присваиваем ей Сумму по второй строке заменяем на 8.

Методы решения транспортных задач Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.

Если план не оптимален, то необходимо перейти к следующему плану таблице так, чтобы транспортные расходы не увеличивались.

Цикл перерасчёта таблицы — это последовательность ячеек, удовлетворяющая условиям:. Никакие три соседние ячейки не могут быть в одной строке или в одном столбце. Далее составляют новую таблицу по следующему правилу:.

Построение второй транспортной таблицы Находим в таблице наименьшую стоимость перевозки — это 0 в клетке A1B2. Теперь вычеркиваем второй столбец, уменьшив сумму в первой строке на Ячейке A2B4 присваиваем 8 и вычеркиваем четвертый столбец.

Выделим из них пять для магазина В3. На складе А2 осталось 3 кровати. Выделим их на магазин В3, но потребности магазина ещё не удовлетворены, поэтому выделим ему со склада А3 ещё пять кроватей. Осталось 15 кроватей, столько, сколько требуется в магазин В5.

Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя северо-западная клетка оставшейся части таблицы, причем максимально возможным числом: Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, удовлетворяют ли найденные компоненты плана Х ij горизонтальным и вертикальным уравнениям. Магазин В1 подал заявку на 20 кроватей, но со склада А1 мы можем перевести 15 кроватей, ещё 5 кроватей мы перевезём со склада А2.

Построение математической модели Пусть Х ij — количество кроватей, отправляемых со склада i в магазин j. Таким образом, имеем следующую математическую модель: Постановка транспортной задачи Однородный груз, имеющийся в m пунктах отправления производства А1, А2, Математическая модель транспортной задачи Будем называть любой план перевозок допустимым , если он удовлетворяет системам ограничений и требованиям неотрицательности.

Мы рассмотрели общие подходы к решению задач линейного программирования. Однако существуют частные типы задач линейного программирования, которые в силу своей структуры допускают решения более простыми методами. Мы остановимся только на одной из них — так называемой транспортной задаче. Фирма должна отправить некоторое количество кроватей с трёх складов в пять магазинов.

Затем решение задачи разбивается на два этапа: Нахождение оптимального решения путем последовательных операций. Метод северо-западного угла диагональный Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя северо-западная клетка оставшейся части таблицы, причем максимально возможным числом: Построение второй транспортной таблицы Магазин В1 подал заявку на 20 кроватей, но со склада А1 мы можем перевести 15 кроватей, ещё 5 кроватей мы перевезём со склада А2.

Её результат можно обобщить на транспортную задачу общего вида. Однородный груз, имеющийся в m пунктах отправления производства А1, А2, Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится, и запросы всех пунктов потребления удовлетворяются закрытая модель , т. Будем называть любой план перевозок допустимым , если он удовлетворяет системам ограничений и требованиям неотрицательности.

Построенный план не является оптимальным, следовательно, производим пересчет. Полученный план является оптимальным. FAQ Обратная связь Вопросы и предложения. Diryabuh Опубликованный материал нарушает ваши авторские права?

Спрос для магазина В1 удовлетворён. В него необходимо доставить 12 кроватей - доставим их со склада А2. На складе А2 осталось 8 кроватей.

Для этого воспользуемся методом потенциалов. Цикл перерасчёта таблицы — это последовательность ячеек, удовлетворяющая условиям: Одна ячейка пустая, все остальные занятые.

Построенный план является допустимым, так как все заявки удовлетворены, все запасы израсходованы. Проверим, является ли полученный план опорным: Сущность метода в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них.

Любые две соседние ячейки находятся в одной строке или в одном столбце. Далее составляют новую таблицу по следующему правилу: В плюсовых клетках добавляем Х. Из минусовых клеток вычитаем Х. Все остальные клетки вне цикла остаются без изменения. Проверим полученный план на оптимальность. Проверим построенный план на оптимальность. Соседние файлы в предмете Организация и планирование производства

На складах имеется соответственно 15, 25 и 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати со склада в магазин приведены в таблице. Пусть Х ij — количество кроватей, отправляемых со склада i в магазин j. Рассмотренная задача является задачей линейного программирования, но специального вида.

Методы решения транспортных задач. Метод потенциалов решения транспортных задач. Вырожденность в транспортной задаче. Структурная схема терминов 3. Построение математической модели транспортной задачи Мы рассмотрели общие подходы к решению задач линейного программирования. Пример 1 Фирма должна отправить некоторое количество кроватей с трёх складов в пять магазинов.

В остальном действуют аналогично предыдущему способу. Находим в таблице наименьшую стоимость перевозки — это 0 в клетке A1B2. Записываем в этой клетке значение 12 наименьшее из сумм по строке и столбцу.

Организация и планирование производства. Транспортная задача линейного программирования 3. Введение Цели изучения темы изучить понятие транспортной задачи; развить навыки решения транспортных задач при помощи метода потенциалов. Требования к знаниям и умениям Студент должен знать: План изложения материала Построение математической модели транспортной задачи.

Найдём оптимальный план для рассмотренной выше задачи. Все остальные элементы равны 0. Составим систему уравнений для нахождения потенциалов решения, найдем сумму соответствующих потенциалов для каждой свободной ячейки и пересчитаем тарифы стоимости для каждой свободной ячейки. Так как у нас получились отрицательные значения, то полученный план не является оптимальным. Выберем ячейку для пересчета A2B2.