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

ТРАНСПОРТНАЯ ЗАДАЧА Семинар 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 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 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.

Задача 4 Найти решение транспортной задачи, если из А3 в В1 и из А2 в В3 перевозки не могут быть осуществлены, из А1 в В2 должно быть завезено не менее 30 ед. груза, а из А2 в В4 ровно 70 ед. груза.

Задача 4 Найти решение транспортной задачи, если из А3 в В1 и из А2 в В3 перевозки не могут быть осуществлены, из А1 в В2 должно быть завезено не менее 30 ед. груза, а из А2 в В4 ровно 70 ед. груза.

Задача 4 Найти решение транспортной задачи, если из А3 в В1 и из А2 в В3 перевозки не могут быть осуществлены, из А1 в В2 должно быть завезено не менее 30 ед. груза, а из А2 в В4 ровно 70 ед. груза.

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

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

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

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

Задача 5 Найти решение транспортной задачи, если из А1 в В4 должно быть перевезено не менее 50 ед. груза, из А3 в В3 должно быть перевезено не менее 30 ед. груза, а из А2 в В2 ровно 40 ед. груза.

Задача 5 Найти решение транспортной задачи, если из А1 в В4 должно быть перевезено не менее 50 ед. груза, из А3 в В3 должно быть перевезено не менее 30 ед. груза, а из А2 в В2 ровно 40 ед. груза.

Задача 5 Найти решение транспортной задачи, если из А1 в В4 должно быть перевезено не менее 50 ед. груза, из А3 в В3 должно быть перевезено не менее 30 ед. груза, а из А2 в В2 ровно 40 ед. груза.

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

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

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

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