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

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

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

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

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

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

Наилучшее распределение ресурсов — такое распределение ресурсов, которое обеспечивает лучшее, более действенное их внедрение в согласовании с данным аспектом оптимальности.

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

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

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

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

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

(1)

при критериях

при . (2)

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

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

· графический способ

· симплекс-способ

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

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

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

Более пользующаяся популярностью задачка действенного распределения ресурсов — транспортная задачка.

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

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

Имеется ряд пт производства
1
,
2
, …, Am

с размерами производства в единицу времени (месяц, квартал), равными соответственно
1
,
2
, …, am

,, и пункты употребления
1
,
2
, …, Bn

, потребляющие за этот же просвет времени, соответственно
1
,
2
, …, bn

продукции.

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

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

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

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

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

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

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

2. оптимизация при помощи способа потенциалов

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

Из 3-х холодильников
=1,3, вмещающих мороженную рыбу в количествах

, нужно последнюю доставить в 5 магазинов
=1-5 в количествах
т. Цены перевозки 1т рыбы из холодильника
в магазин
заданы в виде матрицы

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

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

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

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

1
=150, 5
=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
.

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

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) с отрицательной оценкой, план не оптимален. Строим для данной клеточки цикл.

]]>