Как решать транспортные задачи линейного программирования

Раздел линейного программирования Транспортные задачи включает пять онлайн-калькуляторов:

Классическая транспортная задача (задача Хитчкока-Купманса). Вариант транспортной задачи с ограничениями на пропускную способность. Применение транспортной задачи. Постановка условий
Универсальная транспортная задача.
Решение ТЗ методом дифференциальных рент.
Задача коммивояжера.
Задача о назначениях.
Сетевое планирование.

В условиях к транспортным задачам задается матрица стоимости c_ij, запасы на складе (что нужно распределить) и магазины (куда необходимо распределить). Для получения решения необходимо задать размерность матрицы затрат. Если задан первоначальный опорный план, то отметьте пункт Предложить свой начальный план.
После этого необходимо будет заполнить матрицу тарифов, запасы поставщиков и потребности магазинов.
Нахождение первого опорного плана включает в себя методы:

Минимального элемента;
Северо-западного угла;
Аппроксимация Фогеля;
Двойного предпочтения.

Далее выбирается метод улучшения опорного плана: Метод потенциалов или Распределительный метод.
Для большинства транспортных задач требуется найти минимальные затраты на перевозки, поэтому в качестве целевой функции выбираем Минимальные затраты.
Если потребуется найти максимальное значение целевой функции (получение максимальной прибыли, получение максимального урожая и т.п.), то выбираем Максимальная прибыль.

После решения создается сетевая модель транспортной задачи в виде графа для наглядного отображения оптимального плана перевозок.

Рекомендуется сразу проверять решение в Excel (см. ссылку для скачивания шаблона после решения).

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

Пример. Задание. Решить транспортную задачу в эксель.
Помимо этого решить в ручную эту же транспортную задачу методом-северо западного угла, методом Фогеля, методом минимального тарифа. Используя результат полученный методом северо-западного угла улучить план методом потенциалов.
Помимо этого решить задачу на запрет поставки из А_i в B_i (в Excel):

Запретим поставку груза от 1-го поставщика к 3-му потребителю. Для этого увеличим соответствующую стоимость перевозки до большого числа. Зафиксировать насколько изменится целевая функция.
2-й поставщик может поставить 3-му потребителю только половину товара. Зафиксировать изменение целевой функции;
3-й поставщик может поставить 3-му потребителю не менее половины товара. зафиксировать изменение целевой функции.

Перейти к онлайн решению своей задачи

Применение транспортной задачи. Постановка условий

Задача. Для полива различных участков сада, на которых растут сливы, яблони, груши, служат три колодца. Колодцы могут дать соответственно 180, 90, и 40 ведер воды. Участки сада требуют для полива соответственно 100, 120 и 90 ведер воды. Расстояние (в метрах) от колодцев до участков сада указаны в следующей таблице:

Колодцы	Участки
Колодцы	сливы	яблони	груши
1	10	5	12
2	23	28	33
3	43	40	39

Как лучше организовать полив.
Решаем задачу как транспортную с помощью калькулятора.
Математическая модель транспортной задачи:
F = ∑∑c_ijx_ij, (1)
при условиях:
∑x_ij = a_i, i = 1,2,…, m, (2)
∑x_ij = b_j, j = 1,2,…, n, (3)
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 180 + 90 + 40 = 310
∑b = 100 + 120 + 90 = 310
Условие баланса соблюдается. Возможности колодца равны потребностям полива. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.

	1	2	3	Колодец
1	10	5	12	180
2	23	28	33	90
3	43	40	39	40
Участки	100	120	90

Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, возможности которого полностью израсходованы, либо столбец, соответствующий потребителю,Участки которого полностью удовлетворены, либо и строку и столбец, если израсходованы Колодец поставщика и удовлетворены Участки потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все возможности не будут распределены, а потребности удовлетворены.
Искомый элемент равен 5
Для этого элемента элемента запасы колодца равны 180,Участки 120. Поскольку минимальным является 120, то вычитаем его.
x₁₂ = min(180,120) = 120.

10	5	12	180 - 120 = 60
23	x	33	90
43	x	39	40
100	120 - 120 = 0	90	0

Искомый элемент равен 10
Для этого элемента запасы колодца равны 60,Участки 100. Поскольку минимальным является 60, то вычитаем его.
x₁₁ = min(60,100) = 60.

10	5	x	60 - 60 = 0
23	x	33	90
43	x	39	40
100 - 60 = 40	0	90	0

Искомый элемент равен 23
Для этого элемента запасы колодца равны 90, потребности для участков - 40. Поскольку минимальным является 40, то вычитаем его.
x₂₁ = min(90,40) = 40.

10	5	x	0
23	x	33	90 - 40 = 50
x	x	39	40
40 - 40 = 0	0	90	0

Искомый элемент равен 33
Для этого элемента запасы колодца равны 50,Участки 90. Поскольку минимальным является 50, то вычитаем его.
x₂₃ = min(50,90) = 50.

10	5	x	0
23	x	33	50 - 50 = 0
x	x	39	40
0	0	90 - 50 = 40	0

Искомый элемент равен 39
Для этого элемента запасы колодца равны 40,Участки 40. Поскольку минимальным является 40, то вычитаем его.
x₃₃ = min(40,40) = 40.

10	5	x	0
23	x	33	0
x	x	39	40 - 40 = 0
0	0	40 - 40 = 0	0

	1	2	3	Колодец
1	10[60]	5[120]	12	180
2	23[40]	28	33[50]	90
3	43	40	39[40]	40
Участки	100	120	90

В результате получен первый опорный план, который является допустимым, так как все ведра распределены, потребность участков удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 5. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 10*60 + 5*120 + 23*40 + 33*50 + 39*40 = 5330
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 10; 0 + v₁ = 10; v₁ = 10
u₂ + v₁ = 23; 10 + u₂ = 23; u₂ = 13
u₂ + v₃ = 33; 13 + v₃ = 33; v₃ = 20
u₃ + v₃ = 39; 20 + u₃ = 39; u₃ = 19
u₁ + v₂ = 5; 0 + v₂ = 5; v₂ = 5

	v₁=10	v₂=5	v₃=20
u₁=0	10[60]	5[120]	12
u₂=13	23[40]	28	33[50]
u₃=19	43	40	39[40]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(1;3): 0 + 20 > 12; ∆₁₃ = 0 + 20 - 12 = 8
Выбираем максимальную оценку свободной клетки (1;3): 12
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	Колодец
1	10[60][-]	5[120]	12[+]	180
2	23[40][+]	28	33[50][-]	90
3	43	40	39[40]	40
Участки	100	120	90

Цикл приведен в таблице (1,3; 1,1; 2,1; 2,3; ).
Из ведер х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 50. Прибавляем 50 к ведрам, стоящих в плюсовых клетках и вычитаем 50 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	Колодец
1	10[10]	5[120]	12[50]	180
2	23[90]	28	33	90
3	43	40	39[40]	40
Участки	100	120	90

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 10; 0 + v₁ = 10; v₁ = 10
u₂ + v₁ = 23; 10 + u₂ = 23; u₂ = 13
u₁ + v₂ = 5; 0 + v₂ = 5; v₂ = 5
u₁ + v₃ = 12; 0 + v₃ = 12; v₃ = 12
u₃ + v₃ = 39; 12 + u₃ = 39; u₃ = 27

	v₁=10	v₂=5	v₃=12
u₁=0	10[10]	5[120]	12[50]
u₂=13	23[90]	28	33
u₃=27	43	40	39[40]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j <= c_ij.
Минимальные затраты составят:
F(x) = 10*10 + 5*120 + 12*50 + 23*90 + 39*40 = 4930
Анализ оптимального плана.
Из 1-го колодца необходимо ведра направить на 1-й участок (10 шт.), на 2-й участок (120 шт.), на 3-й участок (50 шт.). Из 2-го колодца необходимо все ведра направить на 1-й участок. Из 3-го колодца необходимо все ведра направить на 3-й участок.
Скачать решение

Перейти к онлайн решению своей задачи

Как решать транспортные задачи линейного программирования

Применение транспортной задачи. Постановка условий

Правила ввода данных

Поиск

Процесс

Сообщение