Транспортная задача. Метод потенциалов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Транспортная задача. Метод потенциалов, слайд №1

Транспортная задача. Метод потенциалов, слайд №2

Транспортная задача. Метод потенциалов, слайд №3

Транспортная задача. Метод потенциалов, слайд №4

Транспортная задача. Метод потенциалов, слайд №5

Транспортная задача. Метод потенциалов, слайд №6

Транспортная задача. Метод потенциалов, слайд №7

Транспортная задача. Метод потенциалов, слайд №8

Транспортная задача. Метод потенциалов, слайд №9

Транспортная задача. Метод потенциалов, слайд №10

Транспортная задача. Метод потенциалов, слайд №11

Транспортная задача. Метод потенциалов, слайд №12

Транспортная задача. Метод потенциалов, слайд №13

Транспортная задача. Метод потенциалов, слайд №14

Транспортная задача. Метод потенциалов, слайд №15

Транспортная задача. Метод потенциалов, слайд №16

Транспортная задача. Метод потенциалов, слайд №17

Транспортная задача. Метод потенциалов, слайд №18

Транспортная задача. Метод потенциалов, слайд №19

Транспортная задача. Метод потенциалов, слайд №20

Транспортная задача. Метод потенциалов, слайд №21

Транспортная задача. Метод потенциалов, слайд №22

Транспортная задача. Метод потенциалов, слайд №23

Транспортная задача. Метод потенциалов, слайд №24

Транспортная задача. Метод потенциалов, слайд №25

Транспортная задача. Метод потенциалов, слайд №26

Транспортная задача. Метод потенциалов, слайд №27

Транспортная задача. Метод потенциалов, слайд №28

Транспортная задача. Метод потенциалов, слайд №29

Транспортная задача. Метод потенциалов, слайд №30

Транспортная задача. Метод потенциалов, слайд №31

Транспортная задача. Метод потенциалов, слайд №32

Транспортная задача. Метод потенциалов, слайд №33

Транспортная задача. Метод потенциалов, слайд №34

Транспортная задача. Метод потенциалов, слайд №35

Транспортная задача. Метод потенциалов, слайд №36

Транспортная задача. Метод потенциалов, слайд №37

Транспортная задача. Метод потенциалов, слайд №38

Транспортная задача. Метод потенциалов, слайд №39

Транспортная задача. Метод потенциалов, слайд №40

Транспортная задача. Метод потенциалов, слайд №41

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Транспортная задача. Метод потенциалов. Доклад-сообщение содержит 41 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

5.6.2. Метод потенциалов Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого опорного решения, получить оптимальное решение за конечное число итераций.

Слайд 2

Описание слайда:

Алгоритм метода потенциалов состоит Алгоритм метода потенциалов состоит в следующем. После построения опорного плана все переменные транспортной задачи разбиваются на две группы: - базисные переменные (заполненные клетки); - свободные переменные (незаполненные клетки).

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

Заполняя выбранную клетку Заполняя выбранную клетку необходимо перераспределить объемы поставок, записанных в ряде других занятых клеток и связанных с заполненной так называемым циклом.

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

Будем отмечать знаком « + » те Будем отмечать знаком « + » те вершины цикла, в которых перевозки необходимо увеличить, а знаком « - », те вершины, в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами называется означенным.

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Пример 5.8. Составить план перевозок Пример 5.8. Составить план перевозок грузов с наименьшей стоимостью от трех поставщиков соответственно в количествах 100, 400 и 600 ед. к четырем потребителям соответственно в количествах 300, 500, 100 и 200 ед. Стоимости перевозок единицы груза приведены в таблице.

Слайд 12

Описание слайда:

Слайд 13

Описание слайда:

1. Определение исходного плана перевозов. 1. Определение исходного плана перевозов. Для составления исходного плана перевозок используем метод северо- западного угла. Общее число базисных клеток равно

Слайд 14

Описание слайда:

Слайд 15

Описание слайда:

2. Исследование базисного решения на оптимальность. 2. Исследование базисного решения на оптимальность. 2.1. Вычислим потенциалы и Исходя из базисных переменных. Для их нахождения используем условие

Слайд 16

Описание слайда:

Полагая, например, , найдем Полагая, например, , найдем 2.2. Для каждой свободной клетки вычислим относительные оценки:

Слайд 17

Описание слайда:

Слайд 18

Описание слайда:

Слайд 19

Описание слайда:

3. Определение нового базисного решения. 3. Определение нового базисного решения. Минимальной разностью является для клетки (1,4). Отрицательная оценка показывает, что при включении в данную свободную клетку каждой единицы груза общая стоимость уменьшается на 4 единицы. Для определения количества груза подлежащего распределению, построим замкнутый цикл (указан пунктиром в табл.).

Слайд 20

Описание слайда:

Одна из вершин цикла находится в Одна из вершин цикла находится в незанятой клетке (1,4), которую отмечаем знаком «+». Все остальные вершины цикла находятся в базисных клетках, с чередующимися знаками «-» и «+». Найдем значение равное наименьшему из чисел, стоящих в отрицательных вершинах цикла.

Слайд 21

Описание слайда:

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

Слайд 22

Описание слайда:

Слайд 23

Описание слайда:

4. Исследование базисного решения на оптимальность. 4. Исследование базисного решения на оптимальность. 4.1. Вычислим потенциалы и исходя из базисных переменных

Слайд 24

Описание слайда:

Полагая, например, , найдем 4.2. Для каждой свободной клетки вычислим относительные оценки:

Слайд 25

Описание слайда:

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

5. Определение нового базисного решения. 5. Определение нового базисного решения. Построим цикл пересчета для свободной клетки (2,4), для которой не выполняется неравенство, и перераспределим поставки согласно этому означенному циклу. В клетку (2,4) поместим груз.

Слайд 28

Описание слайда:

Замечание. Так как одновременно в Замечание. Так как одновременно в двух вершинах цикла (2,2) и (3,4) поставки становятся равными нулю, то лишь одну из них можно объявить свободной, например, (2,2), а другая (3,4) остается базисной с нулевой поставкой. Этим сохраняется количество базисных клеток После преобразований получаем новый план перевозок.

Слайд 29

Описание слайда:

Слайд 30

Описание слайда:

6. Исследование базисного решения на оптимальность. 6. Исследование базисного решения на оптимальность. 6.1. Вычислим потенциалы и исходя из базисных переменных

Слайд 31

Описание слайда:

Полагая, например, , найдем Полагая, например, , найдем 6.1. Для каждой свободной клетки вычислим относительные оценки:

Слайд 32

Описание слайда:

Слайд 33

Описание слайда:

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

Слайд 34

Описание слайда:

5.6.3. Задачи с нарушенным балансом 5.6.3. Задачи с нарушенным балансом а) Транспортная задача с избытком запасов. Транспортную задачу такого типа можно свести к закрытой модели, если ввести фиктивный пункт назначения которому требуется единиц груза.

Слайд 35

Описание слайда:

Стоимость перевозок между фиктивным Стоимость перевозок между фиктивным пунктом назначения и пунктами отправления принимаются равными нулю. Пример 5.9. Решить транспортную задачу, заданную матрицей перевозок

Слайд 36

Описание слайда:

Слайд 37

Описание слайда:

Слайд 38

Описание слайда:

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

Слайд 39

Описание слайда:

Стоимость перевозок между фиктивным Стоимость перевозок между фиктивным пунктом отправления и пунктами назначения принимаются равными нулю. Пример 5.10. Решить транспортную задачу, заданную матрицей перевозок