Транспортная задача

Содержание

Слайд 2

Обозначим xij груз, перевозимый от i-го поставщика к j-му потребителю, сij –

Обозначим xij груз, перевозимый от i-го поставщика к j-му потребителю, сij –
стоимость перевозки единицы груза.
Условия задачи запишем в матрицу планирования.

Слайд 3

Составим модель задачи

Составим модель задачи

Слайд 4

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

Теорема
Любая транспортная задача, у

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

Слайд 5

Построение первоначального опорного плана

Система ограничений ТЗ содержит m x n неизвестных и

Построение первоначального опорного плана Система ограничений ТЗ содержит m x n неизвестных и m+n уравнений.
m+n уравнений.

Слайд 6

Если сложить почленно уравнения подсистемы (1) и отдельно подсистемы (2) то получим

Если сложить почленно уравнения подсистемы (1) и отдельно подсистемы (2) то получим
два одинаковых уравнения.
Следовательно подсистема линейно зависима.
Если одно из уравнений отбросить, то система ограничений должна содержать m+n-1 линейно независимых уравнений.
Следовательно невырожденный опорный план ТЗ содержит m+n-1 положительных компонент (xij), а остальные равны нулю.

Слайд 7

Если условия задачи представлены в матрице планирования, то клетки, в которых находятся

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

Занятые клетки соответствуют базисным переменным и для невырожденного опорного плана их количество должно быть равно m+n-1.

Слайд 8

Опорность плана при записи в виде таблицы означает его ацикличность , т.е.

Опорность плана при записи в виде таблицы означает его ацикличность , т.е.
в таблице нельзя построить замкнутый цикл, все вершины которого лежат в занятых клетках.
(Циклом называется набор клеток, в котором только две соседние клетки расположены в одном столбце или одной строке, причем последняя клетка находится в той же строке или столбце, что и первая).

Слайд 9

Всякий план ТЗ содержащий более m+n-1 занятых клеток не является опорным, т.к.

Всякий план ТЗ содержащий более m+n-1 занятых клеток не является опорным, т.к.
ему соответствует линейно зависимая система векторов.
При таком плане в таблице всегда можно построить замкнутый цикл.
Если к занятым клеткам, определяющим опорный план (ацикличный) добавить одну незанятую клетку, то появится единственный цикл.

Слайд 10

Построение циклов начинают с какой-либо занятой клетки и переходят по столбцу (или

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

Слайд 11

Существует несколько методов построения первоначального опорного плана.

Существует несколько методов построения первоначального опорного плана.

Слайд 12

Метод северо-западного угла

Пусть условия ТЗ заданы таблицей.

Метод северо-западного угла Пусть условия ТЗ заданы таблицей.

Слайд 13

Начинаем с первого потребителя В1 и первого поставщика А1.
Сравниваем a1=100 и b1=200,

Начинаем с первого потребителя В1 и первого поставщика А1. Сравниваем a1=100 и
a1Запасы первого поставщика израсходованы, поэтому в клетках первой строки ставим черту.

Слайд 14

Потребности В1 неудовлетворенны на 200-100=100 ед.
Сравниваем этот остаток с запасами А2:

Потребности В1 неудовлетворенны на 200-100=100 ед. Сравниваем этот остаток с запасами А2: 100
100<250, 100 ед. записываем в А2В1 и удовлетворяем потребности В1, в оставшихся клетках первого столбца ставим черту.

Слайд 15

У А2 осталось 150 ед. груза. Отдаем их В2. Потребности В2 =200,

У А2 осталось 150 ед. груза. Отдаем их В2. Потребности В2 =200,
Записываем 150 в клетку А2В2 и т.к. запасы А2 израсходованы прочеркиваем клетки второй строки.

Слайд 16

Потребности В2 не удовлетворены на 50 ед. Берем их у А3 и

Потребности В2 не удовлетворены на 50 ед. Берем их у А3 и
переходим к В3 и т.д.
Процесс продолжается пока не закончатся запасы и потребности.

Слайд 17

Начиная движение от занятой клетки А1В1 вернуться в нее, двигаясь только по

Начиная движение от занятой клетки А1В1 вернуться в нее, двигаясь только по
занятым клеткам невозможно. Следовательно план опорный.
План является невырожденным, т.к. содержит m+n-1=4+5-1=8 занятых клеток.
Мы не учитывали стоимость перевозок, поэтому план наверное не оптимальный.
Найдем общую стоимость перевозок:
Z=100·10+100·2+150·7+50·5+100·3+50·2+
+50·16+235·13=6950 ед. стоимости.
Если при составлении опорного плана учитывать стоимость, то план будет ближе к оптимальному.

Слайд 18

Метод минимальной стоимости.

Суть метода в том, что из всей таблицы стоимостей выбирают

Метод минимальной стоимости. Суть метода в том, что из всей таблицы стоимостей
наименьшую и в эту клетку (ij) помещают меньшее из чисел ai или bj.
Вычеркивают столбец или строку (запасы израсходованы или запрос удовлетворен)
Из оставшейся таблицы снова выбирают клетку с наименьшей стоимостью и т.д.
Процесс продолжается пока все запасы не будут распределены, а потребности удовлетворены.

Слайд 19

Пусть условия ТЗ заданы таблицей

Пусть условия ТЗ заданы таблицей

Слайд 20

Выбираем наименьшую стоимость, она помещена в клетке А1В4, т.к. а1=b4=100, то 100

Выбираем наименьшую стоимость, она помещена в клетке А1В4, т.к. а1=b4=100, то 100
помещаем в А1В4 и вычеркиваем первую строку и четвертый столбец.

Слайд 21

Наименьшей является стоимость в А2В1 и А3В5.
В А2В1 200<250, →200 записываем и

Наименьшей является стоимость в А2В1 и А3В5. В А2В1 200 В А3В5 200
исключаем столбец В1.
В А3В5 200<250 записываем 200 и исключаем строку А3.

Слайд 22

В таблице снова выбираем наименьшую стоимость и продолжим пока все запасы не

В таблице снова выбираем наименьшую стоимость и продолжим пока все запасы не
будут распределены

X=(x14=100, x21=200, x22=50,x35=200,x42=150,x43=100, x45=50).
План вырожденный опорный, т.к. 7 занятых клеток и нет циклов.
Z=100·1+200·2+50·7+200·2+150·8+100·12+50·13=4300 ед.

Слайд 23

Метод двойного предпочтения.

Если таблица большая, то перебор элементов сложен и используют этот

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

Слайд 24

Пусть условия ТЗ заданы таблицей

Пусть условия ТЗ заданы таблицей

Слайд 25

Отметим клетки c минимальной стоимостью по строкам

Отметим клетки c минимальной стоимостью по строкам

Слайд 26

Отметим клетки c минимальной стоимостью по столбцам

Отметим клетки c минимальной стоимостью по столбцам

Слайд 27

Сначала заполним клетки А2В1, А1В4 А3В5 а затем А4В2

Сначала заполним клетки А2В1, А1В4 А3В5 а затем А4В2

Слайд 28

Далее заполним клетки по минимальной стоимости А2В3, А4В3 , А4В5

Получился вырожденный опорный

Далее заполним клетки по минимальной стоимости А2В3, А4В3 , А4В5 Получился вырожденный опорный план. Z=100·1+200·2+50·10+200·2+200·8+50·12+50·13=4250ед.
план.
Z=100·1+200·2+50·10+200·2+200·8+50·12+50·13=4250ед.

Слайд 29

С помощью рассмотренных методов можно получить вырожденный или невырожденный опорный план.
Оптимальный план

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

Слайд 30

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

Теорема
Если план X* транспортной задачи является оптимальным, то ему соответствует система

Метод потенциалов Теорема Если план X* транспортной задачи является оптимальным, то ему
из m+n чисел U*I V*j, удовлетворяющих условиям
U*i+V*j=Cij
U*i+V*j≤Cij
Числа U*I и V*j называются потенциалами соответственно поставщиков и потребителей.

Слайд 31

Доказательство
Транспортную задачу

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

Доказательство Транспортную задачу можно рассматривать как двойственную некоторой исходной задаче линейного программирования

Слайд 32

Пусть каждому ограничению вида

в исходной задаче соответствует переменная Ui (i=1,2,..m),

Пусть каждому ограничению вида в исходной задаче соответствует переменная Ui (i=1,2,..m), а
а каждому ограничению вида

переменная Vj j=(1,2,…n) .
Тогда двойственная задача запишется так:

Слайд 33

План X* является оптимальным планом двойственной задачи, поэтому план
Y*=(U*I, V*j)

План X* является оптимальным планом двойственной задачи, поэтому план Y*=(U*I, V*j) является
является оптимальным планом исходной задачи и согласно теоремы двойственности

Слайд 34

На основании свойств двойственных задач получаем:
ограничения исходной задачи, соответствующие положительным переменным

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

Слайд 35

Из теоремы следует, что для того, чтобы опорный план был оптимальным, необходимо

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

Для каждой незанятой клетки сумма потенциалов должна быть меньше или равна стоимости единицы перевозки, стоящей в этой клетке

Слайд 36

Если хотя бы одна незанятая клетка не удовлетворяет этому условию, то план

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

Слайд 37

Построение системы потенциалов.
Используем условие

Систему потенциалов можно построить только для невырожденного плана. Он

Построение системы потенциалов. Используем условие Систему потенциалов можно построить только для невырожденного
должен содержать m+n-1 занятых клеток и для него можно составить систему из m+n-1 линейно независимых уравнений с n+m-1 неизвестными.
Если уравнений меньше чем неизвестных, система неопределенная, то одному неизвестному (Ui) придают нулевое значение и все потенциалы определяются однозначно.

Слайд 38

Пусть известен потенциал Ui тогда

Если известен потенциал Vj тогда

Пусть известен потенциал Ui тогда Если известен потенциал Vj тогда

Слайд 39

В таблице выбираем строку с наибольшим количеством занятых клеток (А4) и полагаем

В таблице выбираем строку с наибольшим количеством занятых клеток (А4) и полагаем
U4=0.
В А4 три занятых клетки А4В2 А4В3 А4В5, которые связывают потенциал U4 c потенциалами V2 , V3, ,V5

Слайд 40

Определим эти потенциалы
V2= C42-U4=8-0=8
V3= C43-U4=12-0=12
V5= C45-U4=13-0=13
C помощью U4

Определим эти потенциалы V2= C42-U4=8-0=8 V3= C43-U4=12-0=12 V5= C45-U4=13-0=13 C помощью U4
нельзя определить больше никакой потенциал, подчеркиваем U4

Слайд 41

Поочередно просматриваем столбцы В2 В3 В5 , для которых потенциалы определены.
В столбце

Поочередно просматриваем столбцы В2 В3 В5 , для которых потенциалы определены. В
В2 две занятые клетки А2В2 и А4В2 , которые связывают V2 c U2 и U4(уже определен).
U2= C22-V2=7-8=-1Подчеркиваем V2
В столбце В3 нет занятых клеток, связывающих V3 с неизвестными потенциалами строк, подчеркиваем V3

Слайд 42

Переходим к В5. В нем одна занятая клетка А3В5 , которая связывает

Переходим к В5. В нем одна занятая клетка А3В5 , которая связывает
V5 c неизвестным U3=C32-V5=2-13=-11 Подчеркиваем V5
Потенциал U2 занятой клетки А2В1 связан с неизвестным потенциалом V1=2-(-1)=3. Подчеркиваем U2 и U3
Подчеркиваем V 1 т.к. в В1 нет занятых клеток, связывающих его с неизвестным потенциалом строки

Слайд 43

Построение системы потенциалов прервалось. Потенциалы U1 и V4 остались неопределенными, поскольку план

Построение системы потенциалов прервалось. Потенциалы U1 и V4 остались неопределенными, поскольку план
вырожденный.
Добавляем фиктивно занятую клетку с нулевой перевозкой в столбце В4 или строке А1. Целесообразно найти клетку с наименьшей стоимостью, это клетка А3В4.
Тогда, V4=C34-U3=2-(-11)=13 U1=C14-V4=1-13=-12

Слайд 44

Система потенциалов построена, уберем знаки подчеркивания и проверим правильность системы. Для этого

Система потенциалов построена, уберем знаки подчеркивания и проверим правильность системы. Для этого
проверяем для всех занятых клеток выполнение равенства

Слайд 45

Проверка выполнения условия оптимальности для незанятых клеток

План будет оптимальным, если для всех

Проверка выполнения условия оптимальности для незанятых клеток План будет оптимальным, если для
незанятых клеток выполняется условие

Если план не оптимальный, то для каждой клетки, в которой не выполняется условие находим величину разности и записываем в левый нижний угол клетки

Слайд 46

Для строки А1: -9<10, -4<7. 0<4, -8<4.
Для строки А2 : для А2В3

Для строки А1: -9 Для строки А2 : для А2В3 11> 10
11> 10 или 11-10=1, 1 записываем в клетку. Для А2В4: 12>6, 12-6=6 записываем в клетку. Для А2В5 12>11, 12-11=1 записываем в клетку.
Для строки А3: -8<8, -3<5, 1<3
Для строки А4: 3<11, 13<16

Слайд 47

Выбор клетки, в которую следует послать перевозку

Загрузке подлежит клетка соответствующая max[(Ui+Vj)-Cij]
Таким образом,

Выбор клетки, в которую следует послать перевозку Загрузке подлежит клетка соответствующая max[(Ui+Vj)-Cij]
выбираем max(1;6;1)=6 клетку А2В4
Отмечаем знаком + клетку, которую надо загрузить, она считается занятой.

Слайд 48

Построение цикла и определение величины перераспределения груза

В таблице m+n-1 занятых клеток, поэтому

Построение цикла и определение величины перераспределения груза В таблице m+n-1 занятых клеток,
имеется единственный цикл, все вершины которого в занятых клетках.
Начинаем движение от клетки с + поочередно проставляем – и +.

Слайд 49

Находим Q0=min xij, где xij – перевозки, стоящие в вершинах цикла со

Находим Q0=min xij, где xij – перевозки, стоящие в вершинах цикла со
знаком “-”. Q0=min(50;50;0)=0.
Следовательно, нулевую перевозку перемещаем в клетку А2В4, остальные числа при вычитании и прибавления нуля не изменяются.

Слайд 50

Новый опорный план проверяется на оптимальность

Строится новая система потенциалов
Клетка А2В4 стала

Новый опорный план проверяется на оптимальность Строится новая система потенциалов Клетка А2В4
занятой и для нее должно выполняться равенство U2+V4=C24=-1+13=12≠6. Следовательно, надо U2 либо V4 уменьшить на 6.
Удобнее изменить V4, т.к. он связан только с U1 . V4=13-6=7 U1=C14-V4=1-7=-6.

Слайд 51

Проверяется выполнение условий оптимальности для каждой незанятой клетки.
Значение V4 уменьшилось

Проверяется выполнение условий оптимальности для каждой незанятой клетки. Значение V4 уменьшилось на
на 6 и в В4 не могут появиться свободные клетки не удовлетворяющие условию оптимальности. Такие клетки могут быть только в строке (столбце) потенциал которой увеличился.
U1 увеличился на 6. Строка А1: -3<10; 2<7; 6>4; 7>4. А1В3 и А1В5 не удовлетворяют условию для их находим Ui+Vj-Cij и записываем в левый нижний угол клеток.

Слайд 52

Находим max(2;3;1;1)=3. А1В5 подлежит загрузке, отмечаем ее + и определяем цикл перераспределения.

Находим max(2;3;1;1)=3. А1В5 подлежит загрузке, отмечаем ее + и определяем цикл перераспределения.
Q0=min(50;50;100)=50.
По циклу 50 переносим в А1В5

Слайд 53

План улучшился на 150 единиц стоимости (произведение груза перемещенного в свободную клетку

План улучшился на 150 единиц стоимости (произведение груза перемещенного в свободную клетку
на величину (Ui+Vj)-Cij .
(Ui+Vj)-Cij>0 в свободных клетках показывает, на сколько уменьшится стоимость плана, если единицу груза перераспределить в эту клетку.

Слайд 54

В полученном опорном плане изменяем систему потенциалов.

Условию оптимальности не удовлетворяют 2

В полученном опорном плане изменяем систему потенциалов. Условию оптимальности не удовлетворяют 2
клетки А1В3 и А2В3, груз перемещаем в А1В3.

Слайд 55

Строим цикл перераспределения.

Q0=min (50;0;100)=0. Нулевую перевозку перемещаем в А1В3 и получаем новый

Строим цикл перераспределения. Q0=min (50;0;100)=0. Нулевую перевозку перемещаем в А1В3 и получаем новый опорный план.
опорный план.

Слайд 56

Вносим изменения в систему потенциалов

Вносим изменения в систему потенциалов

Слайд 57

План оптимальный, его стоимость равна 4150 единиц.

План оптимальный, его стоимость равна 4150 единиц.

Слайд 58

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

Возможны два случая открытой модели:
Суммарные запасы превышают суммарные потребности

Суммарные

Открытая(несбалансированная) модель транспортной задачи Возможны два случая открытой модели: Суммарные запасы превышают
потребности превышают суммарные запасы

Слайд 61

Открытая модель решается приведением к закрытой модели.
В случае 1 вводится фиктивный потребитель

Открытая модель решается приведением к закрытой модели. В случае 1 вводится фиктивный
Bn+1, потребности которого bn+1=∑ai-∑bj
В случае 2 вводится фиктивный поставщик Аm+1, потребности которого am+1=∑bj- ∑ai
Стоимость перевозки единицы груза до фиктивного потребителя или фиктивного поставщика полагают равной нулю.
Получается закрытая задача. При ее решении фиктивному потребителю (поставщику) направляют груз от наименее выгодных поставщиков (потребителей).

Слайд 62

Пример

Пример

Слайд 64

При составлении первого опорного плана методом минимальной стоимости или двойного предпочтения необходимо

При составлении первого опорного плана методом минимальной стоимости или двойного предпочтения необходимо
наименьшую стоимость выбирать только среди реальных поставщиков и потребителей, а запасы фиктивного поставщика (или потребителя) распределять в последнюю очередь.
Это правило используют и при введении фиктивных клеток.

Слайд 65

Ответ

Ответ
Имя файла: Транспортная-задача.pptx
Количество просмотров: 39
Количество скачиваний: 0