Оптимизация математической модели

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 4Следующая ⇒

Для оптимизации полученной модели сведем исходные данные в таблицу 6 и введем следующие обозначения:

В1, В2, В3 – данные поставщика с запасами груза b₁, b₂, b₃;

D1, D2, D3 – данные потребителя с объемами заявок d₁, d₂, d₃.

Таблица 6

В верхнем правом углу клеток занесены стоимости перевозок i -го поставщика к j -му потребителю.

Сравнивая запасы груза с суммарным объемом заявок потребителей , убеждаемся, что это открытая транспортная задача (запасы груза у поставщика не равны потребностям в грузе потребителя). С избытком объема заявок

В этом случае заявки выполняются не полностью, поэтому равенство (3.7) заменяется неравенством:

Открытая транспортная задача сводится к закрытой введением (m+1)-го фиксированного поставщика с запасом груза равным:

Тогда имеем: b₄= 165-164=1 единица.

Себестоимость перевозок от фиктивного поставщика к любому потребителю принимаем равной нулю, после этого получаем таблицу 7, в которой методом наименьшего элемента находим опорное решение задачи.

Таблица 7

Опорное решение проверяется на выраженность по формуле:

N=m+n-1

Где: N- количество клеток таблицы, занятых объемами грузов;

m- количество поставщиков;

n- количество потребителей.

N=4+3-1=6. Так как количество клеток в таблице 7 именно 6, то найденное опорное решение можно принять к рассмотрению.

Значение целевой функции будет иметь вид:

W = 42*(4+11) + 8*(8+11) +71*(4+11) +30(4+11) +13*(7+3)+1(0+0) = 2427

Оптимальное решение задачи находится методом потенциалов: каждому поставщику Bi ставятся в соответствие некоторая переменная Ui, называемая потенциалом данного поставщика. Каждому потребителю Dj ставятся в соответствие переменная Vj – потенциал этого потребителя.

Для отыскания значений этих переменных, т.е. потенциалов поставщиков и потребителей, составляется и решается система уравнений, каждой занятой объемами перевозок клетке соответствует уравнение вида:

Ui + Vj = Cij, (3.11)

где Cij – себестоимость перевозок единицы груза.

Для рассматриваемой задачи система уравнений будет иметь вид:

U1+ V1 = 4;

U1+ V3= 8;

U2+ V2 = 4;

U2+ V3 = 4;

U3+ V3 = 7;

U4+ V3 = 0;

Принимаем чаще всего встречающееся значение потенциала, равное V3 =0, получим:

U1 = 8; U2 = 4; U3 = 7; V1 = -4; V2 = 0; V3 = 0; U₄=0.

Таблицу 8 с учетом найденных потенциалов запишем в следующем виде:

Таблица 8

Для каждой свободной клетки вычислим сумму потенциалов поставщика и потребителя. Обозначим ее Z_RS для R-го поставщика и S-го потребителя:

Z_RS = UR + VS.

Определим для свободных от грузоперевозок клеток разность (δ_RS) себестоимости и величины ZRS:

δ_RS = Cij – ZRS.

Отсюда: δ12 = 10-8 = 2;

δ21 = 5-0 = 5;

δ31 = 5-3 = 2;

δ32 = 10-7 = 3;

δ41 = 0-(-4) = 4;

δ42 = 0-0 = 0.

Для всех свободных членов получены положительные разности. Следовательно, данное решение является оптимальным, и целевая функция имеет вид:

W = 42*(4+11) + 8*(8+11) +71*(4+11) +30(4+11) +13*(7+3)+1(0+0) = 2427

Анализ полученных результатов позволяет сделать вывод, что для минимизации затрат на производство и доставку продукции целесообразно разместить производство продукции следующим образом: в пункте В1 объемом 50 единиц для удовлетворения нужд потребителей – D1 (42 ед.), D3(8 ед); в пункте В2 объемом 101 единиц – D2 (71 ед.), D3 (30 ед.); в пункте В3 объемом 13 единиц – D3 (13 ед.),в пункте D4 объемом 1 единица – D3(1ед). При этом, учитывая, что суммарный объем выпускаемой продукции на предприятиях В1, В2, В3 равно суммарному объему потребности в продукции потребителей D1, D2, D3.

“Ручной” способ решения подобных задач является трудоемкой операцией, поэтому целесообразно использование компьютерных программ; применение программы “Statgraphics” для этих целей рассмотрим в следующем разделе.

Познавательные статьи:



Техника нижней прямой подачи мяча

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

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов