Слайд 1Транспортная задача
Дисциплина «Методы оптимальных решений»
Слайд 2Транспортная задача
Имеется n пунктов отправления (ПО), в которых сосредоточены
запасы каких-то однородных грузов в количестве ai единиц (i=1,2,…,n).
Имеется m
пунктов назначения (ПН), подавших заявки соответственно на bj единиц груза (j=1,2,…,m).
Сумма всех заявок равна сумме всех запасов:
(1)
Известна стоимость перевозок cij из i-го ПО в j-ый ПН за единицу груза.
Считается, что стоимость перевозки нескольких единиц груза пропорциональна их числу.
Требуется составить такой план перевозок (откуда, куда и сколько), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальной.
Слайд 3Транспортная задача
Построим модель задачи:
Введем переменные xij - количество груза, перевозимого
из i-го ПО в j-ый ПН. Всего план будет состоять
из nxm элементов.
Суммарное количество груза, перевозимого из i-го ПО во все ПН равно:
(2)
Суммарное количество груза, доставляемого в j-ый ПН из всех ПО равно:
(3)
Суммарная стоимость всех перевозок равна:
(4)
причем (5)
Слайд 4Виды транспортных задач
1) замкнутые (сбалансированные) – выполняется условие (1);
2) открытые
(несбалансированные) – вместо условия (1) может быть:
а)
т.е. спрос превышает предложение (дефицит
товара), тогда задача приводится к замкнутому ввиду с помощью введения фиктивного ПО с номером n+1, для которого запасы
равны дефициту товара
а стоимость перевозок cn+1j равна штрафу за единицу недопоставленного в j-ый ПН товара:
где уj объемы недопоставленного товара.
Слайд 5Виды транспортных задач
б)
, т.е. предложение превышает спрос
(избыток товара), тогда задача приводится к замкнутому ввиду с помощью введения фиктивного ПН с номером m+1, для
которого запросы равны избытку товара
а стоимость перевозок cim+1 равна штрафу за единицу нереализованного в i-ом ПО товара:
где yi объемы нереализованного товара.
Слайд 6Транспортная таблица
Построим для замкнутой транспортной задачи транспортную таблицу:
Опорное решение (опорный
план) транспортной задачи можно находить разными способами:
1. Методом северо-западного угла.
2. Методом минимальной стоимости.
3. Методом Фогеля.
Слайд 7Метод северо-западного угла
Заполнение таблицы всегда начинается с верхней левой ячейки.
Например,
задача имеет транспортную таблицу
Заполнение таблицы начинаем с пустой верхней левой
ячейки, соответствующей тарифу на перевозки с11=10. Так как первому ПН требуется 200 единиц груза, а первый ПО имеет ровно 200 единиц, то все эти 200 единиц отправляем в первый ПН, при этом в первом ПО ничего не останется и не может быть отправлено в другие пункты назначения; с остальных ПО в первый ПН тоже грузы отправляться не будут.
Слайд 8Метод северо-западного угла
Далее заполнение таблицы начинаем с ячейки, соответствующей с22=5.
Второму ПН требуется 180 единиц, которыми располагает второй ПО. Поэтому
со второго ПО во второй ПН отправляем 180 единиц, тогда во втором ПО остается 250-180=70 единиц. Из других ПО во второй ПН перевозить грузы не будут.
Далее заполнение таблицы начинаем с ячейки, соответствующей с23=9. Все оставшиеся 70 единиц груза на втором ПО могут полностью быть отправлены в третий ПН, которому требуется 100 единиц. Отправим эти 70 единиц, после этого во втором ПО ничего не останется, но третьему ПН еще не хватает 30 единиц.
Далее заполнение таблицы начинаем с ячейки, соответствующей с33=3. Из третьего ПО в третий ПН отправляем недостающие 30 единиц, все остальные 150-30=120 единиц отправляем в четвертый ПН.
Получили опорное решение, которое
можно записать в виде матрицы
Суммарные затраты на перевозки будут равны:
Слайд 9Метод минимальной стоимости
Заполнение таблицы всегда начинается с ячейки, имеющей наименьшую
стоимость.
Например, применим этот метод для приведенной выше транспортной таблицы
Заполнение начинаем
с ячейки, соответствующей с14=1.
Далее заполняем ячейку, соответствующую с12=2, затем с21=3.
Далее с33=3, с22=5 и с32=7.
Слайд 10Метод минимальной стоимости
Получили опорное решение, которое можно записать в виде
матрицы
Суммарные затраты на перевозки будут равны:
3. Метод Фогеля. Заполнение таблицы
всегда начинается с ячейки, которая находится следующим образом: в каждой строке и каждом столбце определяют разность между наименьшей стоимостью и ближайшим к нему значением; в строке или столбце, которым соответствует наибольшая разность, выбирают клетку с наименьшей стоимостью.
Для нашего примера этот метод даст опорное решение совпадающее с решением, полученным методом наименьшей стоимости.
Слайд 11Метод потенциалов
Если при решении транспортной задачи число заполненных клеток транспортной
таблицы равно m+n-1, где m – число пунктов отправления (ПО),
n – число пунктов назначения (ПН), то план перевозок называется невырожденным.
Если это число меньше m+n-1, то план перевозок называется вырожденным.
Алгоритм метода потенциалов:
Найти опорный план решения задачи.
Проверить полученный план на не вырожденность, если план оказался вырожденным, то недостающее количество клеток формально заполняется нулями так, чтобы не образовался замкнутый цикл из заполненных клеток.
Проверить опорный план на оптимальность.
«Улучшение плана» - если полученный план был неоптимальным.
Слайд 12Метод потенциалов: критерий оптимальности
а) Запишем матрицу стоимости С и подчеркнем
в ней те стоимости, которые соответствуют занятым клеткам в опорном
решении,
б) Составим систему уравнений для подчеркнутых элементов матрицы С: ui+vj=cij, где i – номер строки; j – номер столбца; cij - это стоимость перевозок, выделенных в матрице С; ui, vj – потенциалы; эта система имеет m+n-1 уравнение и m+n – неизвестных потенциалов. Пусть, например, u1=0, тогда все остальные потенциалы находятся из этой системы;
в) Построим оценочную матрицу Δ, элементы которой равны: Δij=ui+vj-cij, где cij - все элементы матрицы C.
г) Если все Δij≤0, то этот план оптимальный, иначе план не оптимальный.
Слайд 13Метод потенциалов: улучшение плана
а) построим матрицу Х, соответствующую нашему опорному
решению и отметим в ней элемент соответствующий максимальному положительному числу
Δij;
б) построим по этому элементу цикл, так чтобы одна вершина цикла находилась в свободной клетке, а все остальные в занятых клетках, например:
расставим чередующиеся знаки, выберем число λ=min{b,c} среди чисел, помеченных минусом;
в) число λ прибавим к элементам цикла матрицы X, отмеченным плюсом, и вычтем из элементов, помеченных минусом, остальные элементы матрицы не изменяются.
В результате получим новое опорное решение X1.
Проверим его на оптимальность.
Слайд 14Метод потенциалов: пример 1
Проверим на оптимальность опорное решение транспортной задачи
которое
можно записать в виде матрицы
Суммарные затраты на перевозки будут равны:
z=1780.
Выпишем платежную матрицу
Слайд 15Метод потенциалов: пример 1
Запишем систему уравнений для определения потенциалов и
решим ее:
Построим оценочную матрицу
Слайд 16Метод потенциалов: пример 1
Матрица Δ содержит положительный элемент Δ34=2, следовательно,
решение Х не является оптимальным и может быть улучшено.
Выделим в
матрице Х элемент, соответствующий элементу Δ34=2,
И построим по нему цикл пересчета
Найдем λ=min{50;120}=50.
Построим новое опорное решение
Слайд 17Метод потенциалов: пример 1
Проверим его на оптимальность, используя метод потенциалов.
Решим систему уравнений
Построим оценочную матрицу
Эта матрица не содержит положительных
элементов
и содержит ровно 6 отрицательных,
поэтому решение Х1 является оптимальным и
единственным. Суммарные затраты на перевозки составляют
z=
Слайд 18Метод потенциалов: пример 2
Закончим решение транспортной задачи
Запишем решение Х и
матрицу стоимости С:
Слайд 19Метод потенциалов: пример 2
Решим систему
Построим оценочную матрицу
Она содержит положительные элементы,
поэтому решение Х не оптимально.
Слайд 20Метод потенциалов: пример 2
Отметим в матрице Х элемент соответствующий наибольшему
положительному элементу Δ33=4 и построим цикл
Найдем λ=min{20,30,20}=20 и получим новое
решение
Это решение является вырожденным.
Проверим его оптимальность.
Слайд 21Метод потенциалов: пример 2
Решим систему
Из данной системы не можем определить
u3 b v3, поэтому дополним систему еще одним уравнением, соответствующим
нулевому элементу матрицы Х1 с номером (4,3):
Слайд 22Метод потенциалов: пример 2
Построим оценочную матрицу
Она содержит положительный элемент Δ44=1.
Отметим в матрице Х1 элемент, соответствующий ему и построим цикл
пересчета.
Найдем λ=min{20,10}=10 и получим новое решение
Слайд 23Метод потенциалов: пример 2
Это решение является вырожденным. Проверим его оптимальность.
Решим систему
Из данной системы не можем определить u3 b v3,
поэтому дополним систему еще одним уравнением, соответствующим нулевому элементу матрицы Х1 с номером (4,3):
Слайд 24Метод потенциалов: пример 2
Оценочная матрица примет вид
Так как в этой
матрице нет положительных элементов, то решение Х2 оптимально и ему
соответствует значение
Z=
Слайд 25Тестовые вопросы
Среди следующих транспортных задач закрытыми являются
1)
2)
3)
Слайд 26Тестовые вопросы
2. Транспортная задача будет закрытой, если …
1) a=45, b=40
2)
a=45, b=35
3) a=45, b=25
4) a=45, b=30
3. Транспортная задача будет
закрытой, если …
1) a=50, b=40
2) a=50, b=50
3) a=50, b=20
4) a=50, b=30
Слайд 27Тестовые вопросы
4. Суммарные затраты на перевозку для опорного плана, содержащегося
в транспортной таблице равны _______
5. Суммарные затраты на перевозку для
опорного плана, содержащегося в транспортной таблице равны _____
Слайд 28Тестовые вопросы
6. Найти опорный план транспортной задачи, составленный методом северо-западного
угла.
Слайд 29Тестовые вопросы
7. Найти опорный план транспортной задачи, составленный методом наименьшей
стоимости
Слайд 30Домашнее задание
Решить транспортные задачи:
1.
2.
