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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Транспортная задача. Метод потенциалов, слайд №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. Метод потенциалов Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого опорного решения, получить оптимальное решение за конечное число итераций.
Описание слайда:
5.6.2. Метод потенциалов Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого опорного решения, получить оптимальное решение за конечное число итераций.

Слайд 2


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

Слайд 3


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

Слайд 4


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

Слайд 5


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

Слайд 6


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

Слайд 7


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

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


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

Слайд 12


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

Слайд 13


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

Слайд 14


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

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Слайд 19


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

Слайд 20


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

Слайд 21


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

Слайд 22


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

Слайд 23


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

Слайд 24


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

Слайд 25


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

Слайд 26


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

Слайд 27


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

Слайд 28


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

Слайд 29


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

Слайд 30


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

Слайд 31


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

Слайд 32


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

Слайд 33


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

Слайд 34


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

Слайд 35


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

Слайд 36


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

Слайд 37


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

Слайд 38


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

Слайд 39


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

Слайд 40


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

Слайд 41


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию