🗊Презентация Транспортная задача

ТРАНСПОРТНАЯ ЗАДАЧА Семинар 1:

Постановка задачи Имеется m поставщиков A1 , A2, …, Am и n потребителей B1 , B2, …, Bn некоторого груза. Для каждого поставщика и потребителя заданы запасы ai ≥ 0, i = 1, 2, …, m и объем потребления bj ≥ 0, j = 1, 2, …, n. Известна стоимость перевозки единицы груза сij ≥ 0 от i-го поставщика к j-му потребителю. Требуется найти объемы всех перевозок xij от i-го поставщика к j-му потребителю, при которых общая стоимость минимальна.

Математическая постановка задачи

Математическая постановка транспортной задачи определяется задачей линейного программирования: Математическая постановка транспортной задачи определяется задачей линейного программирования: при условиях

Задача 1 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок.

Решение транспортной задачи методом потенциалов Теорема Если опорный план X = (xij) транспортной задачи является оптимальным, то существуют потенциалы поставщиков ui, i = 1,…, m и потребителей vj, j = 1,…, n, удовлетворяющие условиям: ui + vj = сij при xij > 0 (для занятых клеток), Δij = ui + vj - сij ≤ 0 при xij = 0 (для свободных клеток).

Метод потенциалов

Открытая модель транспортной задачи Модель транспортной задачи называется открытой, если (суммарные запасы не равны суммарным потребностям).

Задача 2 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок.

Задача 3 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок.

В некоторых транспортных задачах наложены дополнительные ограничения на перевозку грузов. В некоторых транспортных задачах наложены дополнительные ограничения на перевозку грузов. 1. Если в закрытой задаче перевозки от поставщика Ai к потребителю Bj не могут быть осуществлены (стоит блокировка), для определения оптимального решения задач предполагают, что тариф перевозки единицы груза равен сколь угодно большому числу М.

2. Если дополнительным условием в задаче является обеспечение перевозки от поставщика Ai к потребителю Bj в точности aij единиц груза, в клетку AiBj записывают указанное число aij, а эту клетку считают свободной со сколь угодно большим тарифом М. 2. Если дополнительным условием в задаче является обеспечение перевозки от поставщика Ai к потребителю Bj в точности aij единиц груза, в клетку AiBj записывают указанное число aij, а эту клетку считают свободной со сколь угодно большим тарифом М. 3. Если от поставщика Ai к потребителю Bj должно быть перевезено не менее aij единиц груза, то запасы пункта Ai и потребности Bj полагают меньше фактических на aij единиц. После нахождения оптимального плана перевозку в клетке AiBj увеличивают на aij единиц.

4. Если от поставщика Ai к потребителю Bj требуется перевезти не более aij единиц груза, то вводят дополнительного потребителя Bn+1 = Bij, которому записывают те же тарифы, что и для Bj, за исключением тарифа в i–й строке, который считают равным сколь угодно большому числу М. 4. Если от поставщика Ai к потребителю Bj требуется перевезти не более aij единиц груза, то вводят дополнительного потребителя Bn+1 = Bij, которому записывают те же тарифы, что и для Bj, за исключением тарифа в i–й строке, который считают равным сколь угодно большому числу М. Потребности пункта Bj считают равными aij, а потребности Bij полагают равными bj - aij.

Спасибо за внимание!