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


Вы можете изучить и скачать доклад-презентацию на тему Транспортная задача. Двухиндексные задачи линейного программирования. Презентация на заданную тему содержит 33 слайдов. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций в закладки!
Презентации» Математика» Транспортная задача. Двухиндексные задачи линейного программирования
Двухиндексные задачи линейного программированияВ пунктах производства A1, A2, ..., Am имеется однородный груз вВ зависимости от соотношения между суммарными запасами груза и суммарными потребностямиПри ограничениях
 Оптимальным решением задачи является матрицаТранспортная задача как задача линейного программирования может быть решена симплексным методом,На складах A1, А2, А3 имеются запасы продукции в количествах 90,Проверим, является ли задача закрытой:
 Проверим, является ли задача закрытой:Рассмотрим один из методов — метод минимального тарифа:
 Рассмотрим один изПри распределении грузов может оказаться, что количество занятых клеток меньше, чемНайдем исходное опорное решение методом наименьшего тарифа:
 Найдем исходное опорное решениеНайденное исходное опорное решение проверяется на оптимальность методом потенциалов.
 Найденное исходноеОбозначим Δij = ui + vj - cij. 
 Обозначим ΔijПроверим найденное опорное решение на оптимальность, добавив в таблицу столбец uiВычисляем оценки свободных клеток:
 Вычисляем оценки свободных клеток:
 Получили оценку Δ13Переход к другому опорному решению осуществляется перераспределением грузов, перемещая их изСтроим цикл для клетки (1,3), имеющей положительную оценку. У вершин циклаУ вершин со знаком (—) выбираем минимальный груз, он равен 60.Построим цикл для клетки с положительной оценкой Δ21 = 1:
 ПостроимВсе оценки свободных клеток отрицательные, следовательно, найденное решение оптимальное. 
 ВсеПри открытой транспортной задаче сумма запасов не совпадает с суммой потребностей
При введении фиктивного участника открытая транспортная задача становится закрытой и решаетсяПризнак наличия альтернативного оптимума в ТЗ: равенство нулю хотя бы однойНа трех складах имеется мука в количестве 60, 130 и 90Решение (кратко). 
 Решение (кратко).Решение (кратко). 
 Решение (кратко).Так как Δ33 = 0, то задача имеет альтернативный оптимум иТеперь Δ14 = 0, получили еще одно решение:
 Теперь Δ14 =Найдем элементы матрицы общего решения:
 Найдем элементы матрицы общего решения:
 Итак,



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


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

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

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

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

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

Слайд 7
Описание слайда:
На складах 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 т продукции заданы матрицей (ден. ед.)

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

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

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

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

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

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

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

Слайд 15
Описание слайда:
Проверим найденное опорное решение на оптимальность, добавив в таблицу столбец 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. Найденные значения потенциалов заносим в таблицу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Похожие презентации