Презентация на тему: Презентация транспортной задачи исправл

Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
Презентация транспортной задачи исправл
1/21
Средняя оценка: 4.9/5 (всего оценок: 89)
Код скопирован в буфер обмена
Скачать (1017 Кб)
1

Первый слайд презентации

Изображение слайда
2

Слайд 2

Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков  А  = ( a 1, а 2,..., а m ), вектора запросов потребителей  В=  ( b 1,   b 2,...,   b n ) и матрицы стоимостей  C={ с ij }

Изображение слайда
3

Слайд 3

Переменными (неизвестными) транспортной задачи являются  x ij  , ( i=1,2,...,   m ), ( j= 1,2,...,   n ) — объемы перевозок от каждого  i  -го поставщика каждому  j -му потребителю. Эти переменные можно записать в виде матрицы перевозок:

Изображение слайда
4

Слайд 4

Математическая модель транспортной задачи → min Все запасы груза должны быть вывезены Потребности в грузе должны быть удовлетворены Условие неотрицательности

Изображение слайда
5

Слайд 5

В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей Такая задача называется задачей с правильным балансом, а ее модель — закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель — открытой.

Изображение слайда
6

Слайд 6

Модель транспортной задачи может быть открытой в двух случаях: 1) Запасы грузов пунктов отправления превышают потребности пунктов назначения Для перехода к закрытой модели вводится ( n +1) фиктивный пункт назначения с потреблением : Стоимость перевозок равна 0. 2) Запасы грузов пунктов отправления меньше потребности пунктов назначения Для перехода к закрытой модели вводится ( m +1) фиктивный пункт отправления с запасом груза : Стоимость перевозок равна 0.

Изображение слайда
7

Слайд 7

Изображение слайда
8

Слайд 8

Изображение слайда
9

Слайд 9

Метод северо-западного угла В данном методе запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика. Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель. Осуществляется это таким образом: 1) если  a i <  b   j  то  х   ij  = а i, и исключается поставщик с номером  i, x i k  = 0,  k = 1, 2,...,  n, k ≠ j,   b j ’=b j -  a i 2) если  a i >  b   j  то  х   ij  =  b j, и исключается потребитель с номером  j,  x k j = 0,  k = 1,2,...,  m, k ≠ i, a i ‘= a i  - b j, 3) если  a   i  =  b j  то  х ij = a i =   b j,  исключается либо поставщик  i,  x i k = 0,  k = 1,2,...,  n,  k ≠ j,,  b j ’=0 , либо  j -й потребитель,  x k j = 0,  k = 1,2,...,  m,  k ≠ i, a i ‘= 0.

Изображение слайда
10

Слайд 10

Метод минимальной стоимости Он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи  C={ c ij }, i=1,2,...,  m, j=1,2,...,  n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости  min { с ij } }, и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую  min {с   ij }, заполняют по тем же правилам, что и в методе северо-западного угла.

Изображение слайда
11

Слайд 11

Изображение слайда
12

Слайд 12

Метод потенциалов Теорема. Для того, чтобы некоторый допустимый план перевозок был оптимальным, необходимо и достаточно, чтобы ему соответствовала система из ( m + n ) чисел u 1, u 2, …, u m и v 1, v 2, …, v n, удовлетворяющие условиям: v j + u i = c ij – для занятых клеток; v j + u i ≤ c ij – для свободных клеток.

Изображение слайда
13

Слайд 13

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

Изображение слайда
14

Слайд 14

Если второе условие теоремы нарушается, то подсчитываем разности ( v j + u i - c ij ). Выбирают клетку с наибольшим нарушением условия потенциальности.

Изображение слайда
15

Слайд 15

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

Изображение слайда
16

Слайд 16

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

Изображение слайда
17

Слайд 17

Картофелехранилища Торговая сеть I II III IV 1 3 5 7 11 2 1 4 6 3 3 5 8 12 7 Пример решения транспортной задачи В агрохолдинге имеется три картофелехранилища, в которых хранится картофель в следующих количествах: в первом хранилище а 1 =100 т, во втором – а 2 =130 т и в третьем – а 3 = 170 т. Картофель распределяется между четырьмя торговыми сетями. Первой сети требуется b 1 = 150 т картофеля, второй - b 2=120 т, b 3=80 т и четвертой – b 4=50 т. Стоимость перевозки 1 т картофеля от каждого картофелехранилища к складу каждой торговой сети задано таблицей ( в у.е.). Табличная форма всех условий исходной транспортной задачи Составить такой план перевозки картофеля, чтобы общая стоимость всей транспортировки была бы минимальной.

Изображение слайда
18

Слайд 18

Решение Найдем общее наличие картофеля – Найдем общие потребности в картофеле – Модель транспортной задачи является закрытой.

Изображение слайда
19

Слайд 19

Построим опорный план решения транспортной задачи Метод северо-западного угла Табличная форма реализации метода северо-западного угла Картофелехранилища Торговая сеть Наличие картофеля I II III IV 1 3 100 5 - 7 - 11 - 100 2 1 50 4 80 6 - 3 - 130 3 5 - 8 40 12 80 7 50 170 Потребности в картофеле 150 120 80 50 400 Рассчитаем затраты на реализацию данного плана:

Изображение слайда
20

Слайд 20

Метод минимального элемента Табличная форма реализации метода минимального элемента Картофелехранилища Торговая сеть Наличие картофеля I II III IV 1 3 20 5 80 7 - 11 - 100 2 1 130 4 - 6 - 3 - 130 3 5 - 8 40 12 80 7 50 170 Потребности в картофеле 150 120 80 50 400 Рассчитаем затраты на реализацию данного плана:

Изображение слайда
21

Последний слайд презентации: Презентация транспортной задачи исправл

Найдем оптимальный план перевозок методом потенциалов Картофелехранилища Торговая сеть Наличие картофеля v 1 v 2 v 3 v 4 u 1 3 20 5 80 7 - 11 - 100 u 2 1 130 4 - 6 - 3 - 130 u 3 5 - 8 40 12 80 7 50 170 Потребности в картофеле 150 120 80 50 400 Табличная форма реализации теоремы о потенциалах

Изображение слайда