Презентация «Транспортная задача. Метод потенциалов»
Смотреть слайды в полном размере 
Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 41 слайд и доступен в формате ppt. Размер файла: 362.50 KB
Pic.1
5. 6. 2. Метод потенциалов Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от …
Pic.2
Алгоритм метода потенциалов состоит Алгоритм метода потенциалов состоит в следующем. После построения опорного плана все переменные транспортной задачи разбиваются на две группы: - базисные …
Pic.3
Функция стоимости перевозок Функция стоимости перевозок выражается через свободные переменные следующим образом здесь номер итерации Для нахождения коэффициентов каждому пункту оправления ставится …
Pic.4
Каждому пункту ставится величина Каждому пункту ставится величина - потенциал пункта Для каждой заполненной клетки составляется уравнение где - стоимость перевозки единицы груза из пункта в пункт Так …
Pic.5
Одному из этих неизвестных можно Одному из этих неизвестных можно дать произвольное значение, и тогда неизвестных определяются однозначно. Далее для каждой свободной клетки находим относительные …
Pic.6
Если среди величин есть Если среди величин есть отрицательные, то значение целевой функции (5. 8) может быть уменьшено путем перехода к новому базису. Для этого рассматривают свободные клетки, для …
Pic.7
Заполняя выбранную клетку Заполняя выбранную клетку необходимо перераспределить объемы поставок, записанных в ряде других занятых клеток и связанных с заполненной так называемым циклом.
Pic.8
Циклом в таблице транспортной Циклом в таблице транспортной задачи, называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой …
Pic.9
Будем отмечать знаком « + » те Будем отмечать знаком « + » те вершины цикла, в которых перевозки необходимо увеличить, а знаком « - », те вершины, в которых перевозки необходимо уменьшить. Цикл с …
Pic.10
Перенести какое-то количество Перенести какое-то количество единиц груза по означенному циклу, это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а …
Pic.11
Пример 5. 8. Составить план перевозок Пример 5. 8. Составить план перевозок грузов с наименьшей стоимостью от трех поставщиков соответственно в количествах 100, 400 и 600 ед. к четырем потребителям …
Pic.12
Pic.13
1. Определение исходного плана перевозов. 1. Определение исходного плана перевозов. Для составления исходного плана перевозок используем метод северо- западного угла. Общее число базисных клеток равно
Pic.14
Pic.15
2. Исследование базисного решения на оптимальность. 2. Исследование базисного решения на оптимальность. 2. 1. Вычислим потенциалы и Исходя из базисных переменных. Для их нахождения используем условие
Pic.16
Полагая, например, , найдем Полагая, например, , найдем 2. 2. Для каждой свободной клетки вычислим относительные оценки:
Pic.17
Pic.18
Pic.19
3. Определение нового базисного решения. 3. Определение нового базисного решения. Минимальной разностью является для клетки (1,4). Отрицательная оценка показывает, что при включении в данную …
Pic.20
Одна из вершин цикла находится в Одна из вершин цикла находится в незанятой клетке (1,4), которую отмечаем знаком «+». Все остальные вершины цикла находятся в базисных клетках, с чередующимися …
Pic.21
Значение записываем в незанятую Значение записываем в незанятую клетку. Далее двигаясь по означенному циклу, вычитаем из объемов перевозок, расположенных в клетках, которые обозначены знаком «-», и …
Pic.22
Pic.23
4. Исследование базисного решения на оптимальность. 4. Исследование базисного решения на оптимальность. 4. 1. Вычислим потенциалы и исходя из базисных переменных
Pic.24
Полагая, например, , найдем 4. 2. Для каждой свободной клетки вычислим относительные оценки:
Pic.25
Pic.26
Условие оптимальности плана Условие оптимальности плана перевозок не выполняется, так как одна из оценок отрицательна, поэтому построим замкнутый цикл пересчета и определим величины перераспределения …
Pic.27
5. Определение нового базисного решения. 5. Определение нового базисного решения. Построим цикл пересчета для свободной клетки (2,4), для которой не выполняется неравенство, и перераспределим …
Pic.28
Замечание. Так как одновременно в Замечание. Так как одновременно в двух вершинах цикла (2,2) и (3,4) поставки становятся равными нулю, то лишь одну из них можно объявить свободной, например, (2,2), …
Pic.29
Pic.30
6. Исследование базисного решения на оптимальность. 6. Исследование базисного решения на оптимальность. 6. 1. Вычислим потенциалы и исходя из базисных переменных
Pic.31
Полагая, например, , найдем Полагая, например, , найдем 6. 1. Для каждой свободной клетки вычислим относительные оценки:
Pic.32
Pic.33
Так как для всех свободных клеток Так как для всех свободных клеток таблицы неравенство выполняется, то полученное решение будет оптимальным. При таком плане перевозок затраты на перевозку будут …
Pic.34
5. 6. 3. Задачи с нарушенным балансом 5. 6. 3. Задачи с нарушенным балансом а) Транспортная задача с избытком запасов. Транспортную задачу такого типа можно свести к закрытой модели, если ввести …
Pic.35
Стоимость перевозок между фиктивным Стоимость перевозок между фиктивным пунктом назначения и пунктами отправления принимаются равными нулю. Пример 5. 9. Решить транспортную задачу, заданную матрицей …
Pic.36
Pic.37
Pic.38
б)Транспортная задача с недостатком запасов. б)Транспортная задача с недостатком запасов. Транспортную задачу такого типа можно свести к закрытой модели, если ввести фиктивный пункт отправления …
Pic.39
Стоимость перевозок между фиктивным Стоимость перевозок между фиктивным пунктом отправления и пунктами назначения принимаются равными нулю. Пример 5. 10. Решить транспортную задачу, заданную матрицей …
Pic.40
Pic.41
Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!
