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

Выполнила: студентка 5 курса, факультета Математики, Информатики, Физики Группы И - 51 Ченцова Е.А. Научный руководитель: Астахова Н.А. к. п. н. , доцент

Формулировка транспортной задачи Транспортная задача в общем виде состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А1 А2,,..., Аm в n пунктов назначения B1 ,B2 ,…, Bn В качестве критерия оптимальности можно взять минимальную стоимость перевозок всего груза, либо минимальное время его доставки.

Неизвестными транспортной задачи являются объёмы перевозок от каждого i-го поставщика каждому j–му потребителю. В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, фабрики, склады, магазины и т.д. Под стоимостью перевозок понимают тарифы, расстояния, время, расход топлива и т.п.

Рассмотрим задачу с первым критерием (минимальная стоимость перевозок всего груза), обозначив: Cij - тарифы перевозок единицы груза из i-гo пункта отправления в j-й пункт назначения ai - запасы груза в пункте Аi bj - потребности в грузе пункта Bj xij - количество единиц груза, перевозимого из i-гo пункта в j-й пункт. Рассмотрим задачу с первым критерием (минимальная стоимость перевозок всего груза), обозначив: Cij - тарифы перевозок единицы груза из i-гo пункта отправления в j-й пункт назначения ai - запасы груза в пункте Аi bj - потребности в грузе пункта Bj xij - количество единиц груза, перевозимого из i-гo пункта в j-й пункт.

Исходные данные транспортной задачи записываются в виде таблицы

Целевая функция имеет вид:

Система ограничений состоит из двух групп уравнений Первая группа из m уравнений описывает тот факт, что запасы всех поставщиков вывозятся полностью: i = 1, 2, …, m.

Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей: Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:

Формулировка транспортной задачи такова: Найти переменные задачи

Пример: Данные задачи представлены в следующей таблице. Составить математическую модель задачи. Пример: Данные задачи представлены в следующей таблице. Составить математическую модель задачи.

Решение: Пусть xij - объемы перевозок груза от i-го поставщика – j-му потребителю. В таблице представлены затраты на перевозку единицы груза от поставщика – потребителю. Решение: Пусть xij - объемы перевозок груза от i-го поставщика – j-му потребителю. В таблице представлены затраты на перевозку единицы груза от поставщика – потребителю. Целевая функция имеет вид :

при ограничениях 1)

Опорный и оптимальный план транспортной задачи Всякое неотрицательное решение систем ограничений определяемое матрицей X = (xij ), называют опорным планом ТЗ, а план при котором функция Z принимает минимальное значение - называется оптимальным планом ТЗ.

Необходимое и достаточное условие разрешимости транспортной задачи Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения совпадают, т.е.

Искусственные потребители и поставщики Если спрос меньше предложения, то необходимо вводить искусственного потребителя Bn+1 Если спрос больше предложения, то необходимо вводить искусственного поставщика Am+1

Используемая литература: Борзунова Т.Л., Барыкин М.П. , Данилов Е.А. Соловьева О.Ю. - Математическое моделирование: учебное пособие/ВолгГТУ, - Волгоград, 2008. Конюховский П.В. Математические методы исследования операций в экономике – СПб: Питер, 2000.