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

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

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

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

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

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

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

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

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

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

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

                (1)

при условиях

при .       (2) 
 

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

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

• графический метод
• симплекс-метод

 

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

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

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

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

 

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

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

Имеется ряд  пунктов производства A₁, A₂, ..., A_m с объемами производства в единицу времени (месяц, квартал), равными соответственно a₁, a₂, ..., a_m,, и пункты потребления B₁, B₂, ..., B_n, потребляющие за тот же промежуток времени, соответственно b₁, b₂, ..., b_n продукции.

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

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

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

и каждый поставщик  отгружает весь произведенный им продукт

 

Самый простой метод  решения - итерационное улучшение плана перевозок. Использование таблицы.

Последовательность  действий:

1. Нахождение  опорного плана

2. Оптимизация с  помощью метода потенциалов

 

Транспортная  задача

Из трех холодильников  Ai , i =1,3, вмещающих мороженную рыбу в количествах ai, необходимо последнюю доставить в пять магазинов B j , j =1-5 в количествах b т. Стоимости перевозки 1т рыбы из холодильника i A в магазин j B заданы в виде матрицы

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

1 a =320, 2 b =140,       20 23 20 15 24

2 a =280, 3 b =110, С = 29 15 16 19 29

3 a =250, 4 b =230,         6 11 10   9   8

1 b =150, 5 b =220 

Составим опорный  план по правилу минимального элемента.

 

Введем некоторые  обозначения: Ai* - излишек нераспределенного груза от

поставщика Ai, Bj* - недостача в поставке груза потребителю Bj.

Находим незанятую  клетку с минимальным тарифом: (3,1). Помещаем туда меньшее из чисел A3*=250 и B1*=150.

Находим незанятую  клетку с минимальным тарифом: (3,5). Помещаем туда меньшее из чисел A3*=100 и B5*=220.

Находим незанятую  клетку с минимальным тарифом: (1,4). Помещаем туда меньшее из чисел A1*=320 и B4*=230.

Находим незанятую  клетку с минимальным тарифом: (2,2). Помещаем туда меньшее из чисел A2*=280 и B2*=140.

Находим незанятую  клетку с минимальным тарифом: (2,3). Помещаем туда меньшее из чисел A2*=140 и B3*=110. Находим незанятую клетку с минимальным тарифом: (1,5).

Помещаем туда меньшее из чисел A1*=90 и B5*=120.

Находим незанятую  клетку с минимальным тарифом: (2,5). Помещаем туда меньшее из чисел A2*=30 и B5*=30.

Пришли к таблице:

Транспортные расходы  составят z = 12040.

Решим задачу методом  потенциалов.

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j,

просматривая все  занятые клетки. Получим:

U1=0

V4=C1,4-U1= 15

V5=C1,5-U1= 24

U2=C2,5-V5=5

U3=C3,5-V5=-16

V2=C2,2-U2= 10

V3=C2,3-U2= 11

V1=C3,1-U3= 22 

Для свободных клеток определим значения оценок (разностей  между прямыми и косвенными тарифами).

S1,1 = С1,1 - (U1 + V1) = -2.

S1,2 = С1,2 - (U1 + V2) = 13.

S1,3 = С1,3 - (U1 + V3) = 9.

S2,1 = С2,1 - (U2 + V1) = 2.

S2,4 = С2,4 - (U2 + V4) = -1.

S3,2 = С3,2 - (U3 + V2) = 17.

S3,3 = С3,3 - (U3 + V3) = 15.

S3,4 = С3,4 - (U3 + V4) = 10.

Имеем две клетки с отрицательными оценками – (1,1) и (2, 4). Выбираем клетку с наименьшей оценкой (1, 1) и строим для нее цикл.

 

Перемещаем по циклу  груз величиной в 90 единиц, прибавляя  эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".

В результате перемещения  по циклу получим новый план:

 

Целевая функция (транспортные расходы) z = 11860. Значение целевой функции изменилось на 180 единиц по сравнению с предыдущим этапом.

Проверим полученный план на оптимальность. Подсчитаем потенциалы.

U1=0

V1=C1,1-U1= 20

V4=C1,4-U1= 15

U3=C3,1-V1=-14

V5=C3,5-U3= 22

U2=C2,5-V5=7

V2=C2,2-U2= 8

V3=C2,3-U2= 9

Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:

S1,2 = С1,2 - (U1 + V2) = 15.

S1,3 = С1,3 - (U1 + V3) = 11.

S1,5 = С1,5 - (U1 + V5) = 2.

S2,1 = С2,1 - (U2 + V1) = 2.

S2,4 = С2,4 - (U2 + V4) = -3.

S3,2 = С3,2 - (U3 + V2) = 17.

S3,3 = С3,3 - (U3 + V3) = 15.

S3,4 = С3,4 - (U3 + V4) = 8.

Имеем клетку (2, 4) с  отрицательной оценкой, план не оптимален. Строим для этой клетки цикл.