Эффективное распределение ресурсов, транспортная задача

Доклад на тему

«Эффективное распределение ресурсов. Транспортная задача.»

В настоящее время большое прикладное значение имеет задача распределения ресурсов по работам. Значение этой проблемы определяется, во-первых, ограниченностью ресурсов и, во-вторых, тем, что эффективность
ресурсов в разных направлениях может быть различна. Это означает, что общая эффективность зависит не только от количества ресурсов, но и от распределения ресурсов.

К таким задачам можно отнести, например, задачу распределения продукции от нескольких производителей нескольким потребителям с минимальными затратами на перевозку.

Оптимальное распределение ресурсов - такое распределение ресурсов, которое обеспечивает наилучшее, наиболее эффективное их использование в соответствии с заданным критерием оптимальности.

Критерий оптимальности - признак, по которому вариант функционирования системы признается наилучшим из возможных.

Проблема оптимального распределения ресурсов решается с помощью методов линейного.

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения задач об экстремумах линейных функций, задаваемых системами линейных уравнений и неравенств.

Математическая формулировка задачи линейного программирования ставится следующим образом:

нужно определить максимум линейной целевой функции (линейной формы)

(1)

при условиях

при . (2)

Примером задачи линейного программирования можно назвать задачу об оптимальном рационе, когда необходимо минимизировать стоимость продуктов (f(x)), но при этом получить минимум необходимых веществ (белков, жиров. углеводов).

Основными алгоритмами решения общей задачи линейного программирования являются:

· графический метод

· симплекс-метод

Графический метод является наиболее простым в случае наличия в системе 2-х переменных, которые мы оптимизируем. Тогда мы получаем решение на плоскости. При наличии 3-х переменных мы получаем задачу в пространстве Для его осуществления необходимо построить полуплоскости для каждого ограничения (2). После чего выделить область их пересечения (это будет область допустимых значений, если пересечений нет – то значит нет решения), а затем построить градиент целевой функции.

Далее строим перпендикуляр к градиенту (лучше всего в точке (0,0)) и перемещаем его в сторону границ выделенной области.

Ближайшая точка пересечения перпендикуляра с областью допустимых значений – это точка минимума целевой функции, самая дальняя точка – точка максимума целевой функции.

Наиболее популярная задача эффективного распределения ресурсов - транспортная задача.

Транспортная задача — задача об оптимальном плане перевозок продукта из пунктов отправления в пункты потребления.

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

Имеется ряд пунктов производства A
1
, A
2
, ..., Am
с объемами производства в единицу времени (месяц, квартал), равными соответственно a
1
, a
2
, ..., am
,, и пункты потребления B
1
, B
2
, ..., Bn
, потребляющие за тот же промежуток времени, соответственно b
1
, b
2
, ..., bn
продукции.

Кроме того, известны затраты
по перевозке единицы продукта от каждого поставщика к каждому получателю — эти величины обозначим cij
.
В качестве неизвестных величин выступают объемы продукта, перевозимого из каждого пункта производства в каждый пункт потребления, соответственно обозначаемые xij
.

Тогда наиболее рациональным прикреплением поставщиков к потребителям будет то, при котором суммарные затраты на транспортировку будут наименьшими:

При этом каждый потребитель получает нужное количество продукта