Решить транспортную задачу онлайн методом потенциалов: Транспортная задача онлайн

Как решить транспортную задачу. Руководство

Примеры решенийМетод Гомори Симплекс-метод Метод Фогеля Транспортная задачаЗадача о назначениях Распределительный методМетод потенциаловЗадача коммивояжера Открытые и закрытые задачи

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

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

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

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

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

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

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

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

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

методом потенциалов.
Помимо этого решить задачу на запрет поставки из А_i в B_i (в Excel):

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

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

Задать свои вопросы или оставить замечания можно внизу страницы в разделе Disqus.
Можно также оставить заявку на помощь в решении своих задач у наших проверенных партнеров (здесь или здесь).

Транспортная задача Метод потенциалов Пример решения

Skip to content

27.11.2019 Artman Математическое программирование

Метод потенциалов (оптимизация транспортных задач)

Метод потенциалов для решения транспортной задачи с наименьшей стоимостью

c_ij-(u_i+v_j)=0 при любых x_ij>0

c_ij-(u_i+v_j)>0 при любых x_ij=0

В случае

c_ij-(u_i+v_j)<0 при любых x_ij=0 произвести перестановку

Целевая функция прямой задачи имеет вид:

при этом

---

Пример решения транспортной задачи методом потенциалов
Пусть имеется опорный план, где
A — пункты отправления;
B — пункты назначения.

Ai/Bj		B1	B2	B3
		110	330	160
A1	200	3	5	2
A2	280	8	8	12
A3	120	4	6	10

Находим ячейку с самой низкой стоимостью (в соответствии с методом минимальной стоимости), в данном случае 2 и отправляем весь товар на этот склад.

Ai/Bj		B1	B2	B3
		110	330	0
A1	40	3	5	2160
A2	280	8	8	12
A3	120	4	6	10

Затем опять находим ячейку с самой минимальной стоимостью и далее проделываем аналогичные шаги.

Ai/Bj		B1	B2	B3
		70	330	0
A1	0	340	5	2 160
A2	280	8	8	12
A3	120	4	6	10

Ai/Bj		B1	B2	B3
		0	330	0
A1	0	340	5	2160
A2	280	8	8	12
A3	50	470	6	10

Ai/Bj		B1	B2	B3
		0	0	0
A1	0	340	5	2160
A2	0	8	8280	12
A3	0	470	650	10

∑a=200+280+120=600
∑b=110+330+160=600
Так как a=b ресурсы совпадают с потребностями ⇒ транспортная задача закрытая.
Здесь, число известных — m+n, число уравнений — m+n-1
m+n-1=3+3-1=5 – совпадает ⇒ опорный план невырожденный.

F(x)=3*40+2*140+8*280+4*70+6*50=3220

F(x)=3220

Проверка оптимальности плана

Найдём потенциалы α и β для определения оптимальности плана.

α_i+β_j

=c_ij

Подсчитаем оценки свободных клеток по формулам

∆_ij=с_ij-(α_i+β_j)

∆₁₂=5-(0+3)=2

∆₂₁=8-(3+3)=2

∆₂₃=12-(3+2)=8

∆₃₃=10-(1+2)=7

Так как все искомые оценки стоимости перевозки ресурсов больше нуля, то отсюда следует, что полученный опорный план оптимален.

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

Для этого, из полученных отрицательных значений опорного плана выбирается то значение, которое по модулю самое наибольшее или наименьшее без модуля и ставим в соответствующей ячейки знак «+».

Затем выставляем чередующиеся знаки «–» и «+» в соответствии со следующими правилами:

— оставшиеся знаки ставим только в тех ячейках таблицы, в которых находятся значения;

— в случае, если в столбце имеется знак «–»(«+»), то в этом же столбце должен быть противоположный знак, аналогично и со строками, в случае, если в строке имеется знак «–»(«+»), то в этой же строке должен быть противоположный знак;

— цикл должен быть замкнутым.

Переходим к тем ячейкам таблицы опорного плана,  в которых содержатся знак «–» и среди них находим минимальное значение. Затем к значениям в ячейках со знаком «+» прибавляем, а в ячейках со знаком «–» вычитаем, ранее найденное минимальное значение со знаком «–», при этом ячейка с минимальным значением окажется пустой. Общее количество значений ячеек в таблице при выполнении перерасчёта должно оставаться таким же и соответствовать первоначальному условию задачи.

5192

Транспортная задача 2 (двухэтапный транспорт) | решатель

Свернуть расходы по доставке товаров с заводов на склады и покупателям, и
склады клиентам, не превышая при этом поставок, имеющихся на каждом заводе или
» colspan=»6″> вместимость каждого склада и удовлетворение спроса каждого клиента.
Стоимость доставки ($ за продукт)
	Направления
	Склад 1	Склад 2	Склад 3	Склад 4
Завод 1	5″> 0,50 $	0,50 $	1,00 $	0,20 $
Завод 2	1,50 $	0,30 $	0,50 $	0,20 $
	Клиент 1	Клиент 2	Клиент 3	Клиент 4	Клиент 5
Завод 1	75″> 1,75 $	2,50 $	1,50 $	2,00 $	1,50 $
Завод 2	2,00 $	2,50 $	2,50 $	1,50 $	1,00 $
	Клиент 1	Клиент 2	Клиент 3	Клиент 4	Клиент 5
Склад 1	5″> 1,50 $	1,50 $	0,50 $	1,50 $	3,00 $
Склад 2	1,00 $	0,50 $	0,50 $	1,00 $	0,50 $
Склад 3	1,00 $	1,50 долл. США	2,00 $	2,00 $	0,50 $
Склад 4	5″> 2,50 $	1,50 $	0,20 $	1,50 $	0,50 $
Количество продукция отгружена
	Склад 1	Склад 2	Склад 3	Склад 4	Всего
Завод 1	0	999995932736″> 20 000	0	15 000	35 000
Завод 2	45 000	0	11 000	0	56 000
Всего	45 000	20 000	99993067349″> 11 000	15 000
Емкость	45 000	20 000	30 000	15 000
	Клиент 1	Клиент 2	Клиент 3	Клиент 4	Клиент 5	Всего
Завод 1	999999992724″> 10 000	0	0	15 000	0	25 000	Фабрика
Фабрика 2	0	0	0	0	0	0	Емкость
			Всего продукция, отгружаемая с завода 1			000065601082″> 60 000	60 000
			Всего продукция, отгружаемая с завода 2			56 000	60 000
	Клиент 1	Клиент 2	Клиент 3	Клиент 4	Клиент 5	Всего
Склад 1	0	23 000	0	999929997335″> 17 000	5000	45 000
Склад 2	20 000	0	0	0	0	20 000
Склад 3	0	0	0	0	11 000	99993067349″> 11 000
Склад 4	0	0	15 000	0	0	15 000
Итого	30 000	23 000	15 000	32 000	16 000
Требования	30 000	23 000	15 000	32 000	16 000
Общая стоимость доставка		000166385″> 237 000 долларов США
Проблема
It wants to minimize the cost of shipping its » colspan=»8″> А компания имеет 2 завода, 4 склада и 5 клиентов. Он хочет свести к минимуму стоимость доставки его
товар с фабрик на склады, с фабрик к клиентам, а склады до
клиентов. Количество продукции, поступившей на склад с завода должно быть таким же как у
Количество товаров, отправляемых со склада покупателям. Как компания должна распространять продукцию?
Решение
1) Переменные — это количество продукции, которую необходимо отправить с фабрики на склады, заводы до
These are defined in worksheet Transport2 as » colspan=»7″> клиентов, и склады для клиентов. Они определены в рабочем листе Транспорт2 как
Фабрика_на_склад, Фабрика_к_заказчику, Склад_заказчик.
2) Логический все ограничения определяются с помощью параметра «Предполагать неотрицательное значение»:
	Фабрика_на_склад >= 0
	Завод_к_заказчику >= 0
	Склад_клиент >= 0
Другой ограничения
	Total_from_factory <= Factory_capacity
	Total_to_customer >= Спрос
	Total_to_warehouse <= Warehouse_capacity
	Всего_на_склад = Всего_со_склада
3) цель состоит в том, чтобы минимизировать стоимость, заданную Total_cost.
Примечания
Пожалуйста обратите внимание, что последнее ограничение должно быть ‘=’ , потому что в противном случае продукты начнет накапливаться на
No related posts. Добавить комментарий Отменить ответ Ваш адрес email не будет опубликован. Обязательные поля помечены * Комментарий * Имя * Email * Сайт