Методы принятия упр. ...

5.2 Нахождение первоначального базисного распределения поставок

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

Существует несколько способов нахождения первого опорного плана:

1)диагональный (способ верхнего левого угла, иногда его называют способом северо-западного угла);

2)способ наилучшего элемента в таблице.

Рассмотрим эти два способа, как наиболее широко применяемые и простые на конкретном примере.

Задача:

В хозяйстве на стойловый период заготовлено 2000 т сена, которое сосредоточено на трех различных участках: на первом участке 200 т, на втором участке – 800 т, на третьем – 1000т. Это сено необходимо доставить на четыре животноводческие фермы, потребности которых следующие: первой ферме требуется 300 т сена, второй – 850 т, третей – 550 т, четвертой – 300т. Расстояние от каждого участка до фермы (в километрах) известно и дано в матрице расстояний:

		2	8	6	4
S	=	1	5	2	3
		7	4	10	6

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

Построение опорного плана диагональным способом (метод северо-западного угла)

При построении опорного плана диагональным методом заполнять таблицу поставок начинают с верхнего левого угла, двигаясь как бы по диагонали. Первой ферме необходимо 300 тонн сена, а возможности первого участка - 200, осуществляем поставку в 200, на 1-м участке сена больше нет, но первая ферма еще не полностью получила сено, поэтому доставляем ей со второго участка недостающие 100 тонн, на втором участке осталось 700, а на ферму №2 надо 850 - поставляем все со второго участка и то, что недостает с участка № 3. Так, последовательно и передвигаясь заполняем таблицу с учетом возможностей и потребностей.

Фермы Участки	В1	В2	В3	В4	Наличие сена на участках
А1	2 200	8	6	4	200
А2	1 100	5 700	2	3	800
А3	7	4 150	10 550	6 300	1000
Потребность ферм в сене	300	850	550	300	2000

Построение опорного плана способом наилучшего элемента в матрице (наименьшего тарифа)

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

Заполним таблицу этим методом. Самая дешевая поставка с тарифом 1 - это поставка от второго участка  - ферме №1. Ферме необходимо 300 тонн, можем осуществить сразу всю поставку, так как возможность участка - 800.

Фермы Участки	В1	В2	В3	В4	Наличие сена на участках
А1	2	8	6	4	200
А2	1 300	5	2	3	800
А3	7	4	10	6	1000
Потребность ферм в сене	300	850	550	300	2000

Следующий шаг - столбец 1 (желтым цветом выделен) не рассматриваем, так как первая ферма полностью удовлетворена и ей больше не надо сена. Из оставшихся ячеек самый дешевый тариф 2: поставка с участка №2 на ферму №3. Ферме необходимо 550 тонн, но столько на втором участке нет - только 500 (т.к. 300 было ранее отправлено на ферму №1), поэтому осуществляем поставку в размере 500 тонн.

Фермы Участки	В1	В2	В3	В4	Наличие сена на участках
А1	2	8	6	4	200
А2	1 300	5	2 500	3	800
А3	7	4	10	6	1000
Потребность ферм в сене	300	850	550	300	2000

Из оставшихся 6-ти ячеек наименьший тариф 4 у двух поставок. Они не "мешают" друг другу, а если поставки пересекались бы, то надо было бы осуществить максимальную поставку вначале.

Фермы Участки	В1	В2	В3	В4	Наличие сена на участках
А1	2	8	6	4  200	200
А2	1 300	5	2 500	3	800
А3	7	4  850	10	6	1000
Потребность ферм в сене	300	850	550	300	2000

Выбор на этом этапе построения опорного плана уже отсутствует - просто осуществляем недостающие поставки.

Фермы Участки	В1	В2	В3	В4	Наличие сена на участках
А1	2	8	6	4 200	200
А2	1      300	5	2      500	3	800
А3	7	4      850	10 50	6      100	1000
Потребность ферм в сене	300	850	550	300	2000

Опорный план построенный любым из методов необходимо проверить на вырожденность, число занятых клеток должно равняться N = m+n-1, где m – число поставщиков, n – число потребителей. Для нашей задачи   N = 3+4-1 = 6. Если число занятых клеток будет меньше, то решить задачу предлагаем алгоритмом нельзя.

Рассмотрим дальнейший алгоритм решения транспортной задачи. За основу возьмем опорный план, построенный диагональным методом.

Исследуем опорный план на оптимальность:

Необходимо рассчитать  потенциалы р_i и k_j по формуле:

С_ij = р_i + k_j

Где С_ij – тариф занятой клетки.

Для этого первый потенциал принимаем равной нулю р₁=0.

Далее по формуле рассчитываем остальные значения по занятым клеткам.

Определяем k₁:     2=p₁+k₁ отсюда  определим   k₁=2-0=2;

Определяем p₂:    1=p₂+k₁ отсюда  определим   p₂=1-2=-1;

Определяем k₂:     5=p₂+k₂ отсюда  определим   k₂=5-(-1)=6;

Определяем p₃:     4=p₃+k₂ отсюда  определим   p₃=4-6=-2;

Определяем k₃:     10=p₃+k₃ отсюда  определим   k₃=10-(-2)=12;

Определяем k₄:     6=p₃+k₄ отсюда  определим   k₄=6-(-2)=8;

Фермы Участки		В1	В2	В3	В4	Наличие сена на участках
		k1 =2	k2 =6	k3 =12	k4 =8
А1	р1= 0	2 200	8	6	4	200
А2	р2=-1	1 100	5 700	2	3	800
А3	р3=-2	7	4 150	10 550	6 300	1000
Потребность ферм в сене		300	850	550	300	2000

Рассчитаем значения L_ij для свободных клеток по формуле:

L_ij = С_ij – (р_i + k_j)

Где С_ij – тариф свободной клетки клетки.

L₁₂=8-(6+0)=2

L₁₃=6-(12+0)=-6

L₁₄=4-(8+0)=-4

L₂₃=2-(12-1)=-9

L₂₄=3-(8-1)=-4

L₃₁=7-(2-2)=7

План считается оптимальным, если все значения

L_ij >=0

Рассчитав все значения свободных клеток, видим, что план не оптимален.

Значение целевой функции для первой таблицы

С=200*2+100*1+700*5+150*4+550*10+300*6=400+100+3500+600+5500+1800=11 400

План поставок следует улучшать.