Решение транспортной задачи онлайн калькулятор

Теорема 2 условие оптимальности плана транспортной задачи. Для того чтобы план транспортной задачи был оптимальным, необходимо и достаточно выполнить следующие условия: Построение системы потенциалов и проверка плана на оптимальность. Условий у нас 9, а заполненных клеток — 7. Следовательно, план является вырожденным. Двойственность в линейном программировании.

Но цель решающего задачу - найти из них оптимальное. Если план является вырожденным, то его дополняют условно заполненной клеткой, вписывая в нее груз в объеме нуль единиц.

Поэтому разработаны специальные методы решения транспортной задачи. Если суммарное количество грузов, имеющихся у поставщиков, совпадает с суммарным количеством грузов, необходимых потребителям, то такая транспортная задача называется закрытой. Если эти объемы не совпадают - транспортная задача называется открытой.

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

В клетку А 1 В 1 проставляем данные все, что есть у А 1. Другим потребителям от него ничего не достанется, в остальных клетках первой строки ставим прочерки. Так как В 1 запрашивает единиц, добавляем ему ед. Остаток мы полностью отгружаем второму потребителю. И так далее по всей таблице. После полной загрузки таблицы проверьте суммы грузов по строкам и столбцам. Если суммы совпадут со значениями грузов у поставщиков и потребителей, то таблица составлена верно. Он состоит в последовательном полном удовлетворении потребителей при наименьшей стоимости перевозок.

Пусть это будет клетка с наименьшей стоимостью перевозок - 2. Теперь проверим план на оптимальность. Для этого в каждой пустой клетке проверим выполнение условия. Отмечаем в клетке A 2 B 4 нарушение условия оптимальности. Это значит, что план не является оптимальным. Нужно перераспределить поставки, чтобы стоимость перевозок оказалась меньше, чем в данном плане.

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

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

Проверим суммы грузов поставщиков и потребителей: Следовательно, транспортная задача закрытая. Определим стоимость перевозок по нашему плану: Для той же задачи имеем: По сравнению с методом северо-западного угла получили меньшую стоимость перевозок. Для той же задачи получим таблицу: Определим стоимость перевозок по этому плану: Условия оптимальности плана транспортной задачи Теорема 1. Ранг матрицы транспортной задачи на единицу меньше числа уравнений.

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

Поэтому одному из потенциалов придают любое числовое значение. Рекомендуется присваивать значение нуль тому потенциалу, для которого в соответствующей строке или в столбце имеется наибольшее количество занятых клеток. Рассмотрим опорный план для транспортной задачи п. Пусть потенциал U 2 будет равен 0. От потенциала V 3 перейдем к потенциалу U 4 , исходя из уравнения. На этом процесс остановился в силу вырожденности задачи. Чтобы найти остальные потенциалы, необходимо заполнить нулем клетку, первой строки или четвертого столбца.

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

Не нашли то, что искали? Google вам в помощь! Методы решения транспортных задач также реализуются с помощью таблиц. Для построения первоначального опорного плана существуют различные методы. Матрица стоимостей имеет вид Составить первоначальный опорный план транспортной задачи методом северо-западного угла.