Презентация Транспортная задача. Двухиндексные задачи линейного программирования онлайн

Содержание слайда: Двухиндексные задачи линейного программирования

Содержание слайда: В пунктах производства A1, A2, ..., Am имеется однородный груз в количестве соответственно a1, a2,…, am. В пунктах производства A1, A2, ..., Am имеется однородный груз в количестве соответственно a1, a2,…, am. Этот груз необходимо доставить в пункты назначения B1, В2, …., Вn в количестве соответственно b1, b2,..., bn. Стоимость перевозки единицы груза (тариф) из пункта Ai в пункт Bj равна cij. Требуется составить план перевозок, позволяющий вывезти все грузы и имеющий минимальную стоимость.

Содержание слайда:

Содержание слайда: В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми. В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми.   Если   задача называется закрытой. Если то открытой.

Содержание слайда: При ограничениях Оптимальным решением задачи является матрица

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

Содержание слайда: На складах A1, А2, А3 имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители В1, В2, B3 должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (ден. ед.) На складах A1, А2, А3 имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители В1, В2, B3 должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (ден. ед.)

Содержание слайда: Проверим, является ли задача закрытой: Проверим, является ли задача закрытой:

Содержание слайда:

Содержание слайда: Рассмотрим один из методов — метод минимального тарифа: Рассмотрим один из методов — метод минимального тарифа: Грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок cij. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс распределения продолжают до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены.

Содержание слайда: При распределении грузов может оказаться, что количество занятых клеток меньше, чем m+n-1. В этом случае задача имеет вырожденное решение. При распределении грузов может оказаться, что количество занятых клеток меньше, чем m+n-1. В этом случае задача имеет вырожденное решение. В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми. Нулевые поставки помещают в незанятые клетки с учетом наименьшего тарифа таким образом, чтобы в каждых строке и столбце было не менее чем по одной занятой клетке.

Содержание слайда: Найдем исходное опорное решение методом наименьшего тарифа: Найдем исходное опорное решение методом наименьшего тарифа: Число занятых клеток в таблице равно m+n-1= 3+3–1=5, т.е. условие невырожденности выполнено.

Содержание слайда: Найденное исходное опорное решение проверяется на оптимальность методом потенциалов. Найденное исходное опорное решение проверяется на оптимальность методом потенциалов. В распределительную таблицу добавляют строку vj и столбец ui. Числа ui и vj называют потенциалами. Потенциалы ui и vj находят для занятых клеток из равенства ui + vj = cij. Одному из потенциалов дается произвольное значение, например u1 = 0, тогда остальные потенциалы определяются однозначно. Так, если известен потенциал ui, то vj=сij—ui; если известен потенциал vj, то ui=cij–vj.

Содержание слайда: Обозначим Δij = ui + vj - cij. Обозначим Δij = ui + vj - cij. Эту оценку называют оценкой свободных клеток. Если все Δij ≤ 0, то опорное решение является оптимальным. Если хотя бы одна из оценок Δij > 0, то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому.

Содержание слайда: Проверим найденное опорное решение на оптимальность, добавив в таблицу столбец ui и строку vj. Проверим найденное опорное решение на оптимальность, добавив в таблицу столбец ui и строку vj. Полагая u1=0, запишем это в последнем столбце таблицы. Рассмотрим занятую клетку (1,1), для нее выполняется условие u1+ v1 = 2, откуда v1 = 2. Далее рассматриваем последовательность из занятых клеток таблицы, для которых один из потенциалов известен: Для клетки (3,1): u3 + v1 = 3, v1 = 2, откуда u3 = 1. Для клетки (3,3): u3 + v3 = 8, u3 = 1, v3 = 7. Для клетки (2,3): u2 + v3 = 5, v3 = 7, u2 = -2. Для клетки (2,2): u2 + v2 = 1, u2 = -2, v2 = 3. Найденные значения потенциалов заносим в таблицу.

Содержание слайда:

Содержание слайда: Вычисляем оценки свободных клеток: Вычисляем оценки свободных клеток: Получили оценку Δ13 = 5 > 0, следовательно, исходное опорное решение не является оптимальным и его можно улучшить.

Содержание слайда: Переход к другому опорному решению осуществляется перераспределением грузов, перемещая их из занятых клеток в свободные: Переход к другому опорному решению осуществляется перераспределением грузов, перемещая их из занятых клеток в свободные: Для свободной клетки с Δij > 0 строится замкнутый цикл (цепь, многоугольник), все остальные вершины которого находятся в занятых клетках; углы прямые. Около свободной клетки цикла ставится знак (+), затем чередуют знаки (—) и (+). У вершин со знаком (—) выбирают минимальный груз. Его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (—). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т.д. до тех пор, пока не получим оптимальное решение.

Содержание слайда: Строим цикл для клетки (1,3), имеющей положительную оценку. У вершин цикла ставим знаки (+) и (—) Строим цикл для клетки (1,3), имеющей положительную оценку. У вершин цикла ставим знаки (+) и (—)

Содержание слайда: У вершин со знаком (—) выбираем минимальный груз, он равен 60. У вершин со знаком (—) выбираем минимальный груз, он равен 60. Его прибавляем к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл и новое опорное решение, которое заносим в новую распределительную таблицу для проверки на оптимальность:

Содержание слайда:

Содержание слайда: Построим цикл для клетки с положительной оценкой Δ21 = 1: Построим цикл для клетки с положительной оценкой Δ21 = 1: Получим новое решение, которое занесем в таблицу Проверим его на оптимальность.

Содержание слайда:

Содержание слайда: Все оценки свободных клеток отрицательные, следовательно, найденное решение оптимальное. Все оценки свободных клеток отрицательные, следовательно, найденное решение оптимальное. Стоимость транспортных расходов равна

Содержание слайда: При открытой транспортной задаче сумма запасов не совпадает с суммой потребностей При открытой транспортной задаче сумма запасов не совпадает с суммой потребностей При этом: а) если то объем запасов превышает объем потребления. Для решения задачи вводят фиктивного потребителя, потребности которого равны разности запасов и потребностей. б) если то объем потребления превышает объем запасов, часть потребностей останется неудовлетворенной. Для решения задачи вводим фиктивного поставщика.

Содержание слайда: При введении фиктивного участника открытая транспортная задача становится закрытой и решается по алгоритму решения закрытых ТЗ. При введении фиктивного участника открытая транспортная задача становится закрытой и решается по алгоритму решения закрытых ТЗ. Фиктивному участнику назначаются тарифы больше или равны наибольшему из всех транспортных тарифов (иногда их считают равными нулю). В целевой функции фиктивный поставщик или потребитель не учитывается.

Содержание слайда: Признак наличия альтернативного оптимума в ТЗ: равенство нулю хотя бы одной из оценок свободных переменных в оптимальном решении (Xопт1). Признак наличия альтернативного оптимума в ТЗ: равенство нулю хотя бы одной из оценок свободных переменных в оптимальном решении (Xопт1). Сделав перераспределение грузов относительно клетки, имеющей Δij = 0, получим новое оптимальное решение (Хопт2), при этом значение целевой функции (транспортных расходов) не изменится. Если одна оценка свободных переменных равна нулю, то оптимальное решение находится в виде где 0 ≤ t ≤ 1

Содержание слайда: На трех складах имеется мука в количестве 60, 130 и 90 т, которая должна быть в течение месяца доставлена четырем хлебозаводам в количестве: 30, 80, 60, 110 т соответственно. На трех складах имеется мука в количестве 60, 130 и 90 т, которая должна быть в течение месяца доставлена четырем хлебозаводам в количестве: 30, 80, 60, 110 т соответственно. Составить оптимальный план перевозок, имеющий минимальные транспортные расходы, если стоимость доставки 1 т муки на хлебозаводы задана матрицей

Содержание слайда: Решение (кратко). Решение (кратко).

Содержание слайда: Решение (кратко). Решение (кратко).

Содержание слайда: Так как Δ33 = 0, то задача имеет альтернативный оптимум и одно из решений равно Так как Δ33 = 0, то задача имеет альтернативный оптимум и одно из решений равно Произведем перераспределение грузов относительно клетки (3,3):

Содержание слайда: Теперь Δ14 = 0, получили еще одно решение: Теперь Δ14 = 0, получили еще одно решение: Данная задача имеет два оптимальных решения Хопт1 и Xопт2, общее решение находится по формуле где 0 ≤ t ≤ 1.

Содержание слайда: Найдем элементы матрицы общего решения: Найдем элементы матрицы общего решения: Итак, Стоимость транспортных расходов составит L(Хопт) = 1550 усл. ед.