Оптимизация закрепления потребителей. за подразделениями предприятия

Лабораторная работа № 1

Оптимизация закрепления потребителей
за подразделениями предприятия

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

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

Сущность метода.

Пусть имеется m, i - ых производителей продукции объемом аi и n,
j - тых потребителей этой продукции объемом bj. Необходимо прикрепить
j - тых потребителей к i - ым производителям, так чтобы транспортные издержки внешнего и внутреннего транспорта были минимальны. i = 1, m;
j = 1, n.

Данное условие в математической интеграции можно записать:

Найти целевую (критериальную функцию):

(1)

при ограничениях

(2)

(2)

где Ц/ij - удельные транспортные издержки на единицу xi - той продукции для j - того потребителя за 1 км;

Sij - расстояние от производителя i до потребителя j;

xij доставляемый объем продукции от производителя i до потребителя j;

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

(3)

то вводят j + 1 (дополнительного) потребителя с потребностью

(4)

и наоборот, если

(5)

то вводят i + 1 (дополнительного) производителя с возможностью выпуска

(6)

При соблюдении условия задача называется закрытой, при условиях (3), (5) – открытой.

Итак, чтобы решить задачу она должна быть закрытой.

С целью обеспечения достоверности (верификации) решениz расстояния от дополнительных потребителя и поставщика целесообразно принимать в полтора - два раза больше наибольшей из величин (), при этом дополнительные расстояния до всех поставщиков от потребителей принимаются равными. Т. е. Ц/ij *Si,j+1 = const.

Основы решения транспортной задачи методом потенциалов.

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

Определение потенциальной функции F выполняется по этапам.

1.  Для решения составляется по определенным правилам опорный план, который последовательно улучшается до тех пор, пока не будет достигнута критериальная функция F®min.

Правила составления опорного плана представлено матрицей

V U		V1	V2	…	Vn
	Изготовители продукции (i)	Потребители (j) и расстояние между изготовителями (Sij)	Возможности (ai)
j = 1	j = 1	…	j = 1
U1	i = 1	Ц/11 S1.1 x1.1	Ц/12 S1.2 x1.2	…	Ц/1n S1.n x1.n	a1=
…	…	…	…	…	…	…
Um	i = m	Ц/m1 Sm.1 xm.1	Ц/m2 Sm.2 xm.2	…	Ц/mn Sm. n xm. n	am=
	Потребности (bj)	b1=	b2=	…	bn=

Куда в ij - e клетки вписываются в верхний левый угол по строкам величины (Цij Sij) или Sij если Цij =const, в нижний правый угол вписываются величины xij – распределения (xij £ bj)i используя метод Северо-западного угла (или минимального) элемента.

С целью оперативности решения рекомендуется для составления опорного плана использовать метод минимального элемента, сущность которого заключается в первоочередном удовлетворении потребителей, имеющих кратчайшие (минимальные) расстояния (или Ц/ij *Si,j) до производителей.

2.  Для опорного плана отыскивается целевая функция по формуле:

(или , при Цij =const)

3.  Значение целевой функции F исследуется (проверяется) на оптимальность. Для этой цели:

4.  Составляются уравнения потенциалов для базовых – заполненных товаром клеток (где xij ¹ 0). Это делается для того чтобы найти невязки по свободным (где xij = 0) клеткам. Начинают с Si,j (или Ц/ij *Si,j) =min
Ui + Vj = Sij (для всех клеток, где xij ¹ 0). Количество таких уравнений будет равно количеству заполненных клеток.

5.  Находятся все потенциалы для базовых клеток. С этой целью для разрешения неопределенности потенциала Ui (где i =min) - придаем значение ноль; т. е. Ui =min = 0.

6. Составляются уравнения невязок Dij для небазовых клеток
(где xij = 0) клеток.

где

таких уравнений должно быть равно количеству свободных
(где xij = 0) клеток

7. Анализируются невязки. При оптимальном плане все невязки должны быть отрицательны, т. е. Dij <0. В противном случае выполняется оптимизация методом перераспределения поставок xij. Для этого:

8. Выбирается из положительных невязок наибольшая Dij ®max.

9. Образуется контур клетки, которому принадлежит данная невязка. Этот контур состоит из нескольких смежных клеток и может иметь различную конфигурацию, но углы поворотов, должны находиться в клетках где xij ¹ 0. В вершины контураторого (кроме величины xij=0, где Dij ®max), Выписываются значения распределений xij ¹ 0 из опорного плана.

10. Вершине клетки (c xij = 0) придается знак «+» и далее чередуются знаки вершин: «-», «+» и т. д. по часовой стрелке.

11. Производится перераспределение поставок (величины xij ¹ 0). Для этого производится алгебраическое вычитание наименьшего по абсолютной величине (модулю)отрицательного значения: -(/xij/ = min) из вершин контура.

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

13. Повторяем этапы 1 - 4 до тех пор пока не получим оптимальный план, т. е. когда для всех свободных клеток Dij <0.

С целью лучшего усвоения планирования объектов (закрепления потребителей) по подразделениям предприятия решим пример.

Пример:

Геодезическое предприятие в планируемом периоде 200_г. будет выполнять работы на четырех геодезических объектах, имеющих объемы работ в условно-натуральных показателях (УПН) b1 = 50, b2 = 90, b3 = 100, b4 = 60.

Требуется распределить объекты по экспедициям, имеющим предметную специализацию и соответствующие производственные мощности в условно-натуральных показателях:

M1 = 85, M2 = 94, M3 =190

Планируемые коэффициенты используемой производственной мощности по экспедициям соответственно равны:

k1 = 0.9, k2 = 0.87, k3 = 0.91.

Стоимость удельных транспортных издержек постоянна и составляет Ц/ = 0,05 тыс. руб. за единицу УПН продукции на 1 км2. Расстояние от объектов до экспедиции соответственно равны см. табл.1.

Примечание: за условно-натуральный показатель (УНП) принята топографическая съемка масштаба 1:10000 с сечением рельефа 2м. Третьей категории сложности.

Таблица 1

Подразделения (i)	Объекты (потребители) (j)	Miki (ai)
1	2	3	4
Экспедиция 1	50	120	270	90	76
Экспедиция 2	30	180	250	110	82
Экспедиция 3	210	170	140	150	173
(bj)	50	90	100	60	åa=331

åbj=500

Решение произвести под условием:

при

xij ³0

Ц/ij = Ц/ = const

Решение:

1. Так как суммарная возможность экспедиций превышает на 31 единицу УПН потребность (), то задача открыта. Для закрытия задачи вводим дополнительного (искусственного) потребителя D с расстоянием 800 км. от каждой экспедиции и потребностью 31 УПН
см. табл. 2.

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

Опорный план.

Таблица 2

Экспедиция (i)	V U	1 V1	2 V2	3 V3	4 V4	D V5	ai
1	U1	80	120 16	270	90 60	800	76
2	U2	30 50	180 32	250	110	800	82
3	U3	210	170 42	140 100	150	800 31	173
	(bj)	50	90	100	60	31	331

2.  Отыскиваем целевую функцию без дополнительной неизвестной

F=0.05*[(30*50)+(120*16+180*32+170*42)+(140*100)+(90*60)]=
0.05*[1500+1920+5760+7140+14000+5400] =1786 тыс. руб.

3.  Исследуем F на оптимальность, для этого:

4.  Составляем уравнение потенциалов для базовых клеток

U1+V2=120 U2+V1=30 U3+V2=170 U3+V5=800

U1+V4=90 U2+V2=180 U3+V3=140

5.  Находим потенциалы для базовых клеток:

Примем U1=0, тогда:

U1=0 V1=-30

U2=180-120=60 V2=120

U3=170-120=50 V3=90

V4=90

V5=-10

6.  Составляем уравнение невязок для небазовых клеток

7.  Так как имеются положительные невязки (+40, +10), то целевая функция не отрицательна

8.  Выбираем наибольшую положительную невязку (+40);

9.  Образуем контур клетки, которому принадлежит данная невязка:

 

и выписываем распределение xij в вершины этого контура

10.  Расставляем знаки «+», «-» и т. д., начиная с наибольшего распределения;

11.  Производим перераспределение

 

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

	1	2	3	4		D
U/V	V1	V2	V3	V4	V5	(ai)
U1	80	120 48	270	90 28	800	76
U2	30 50	180	250	110 32	800	82
U3	210	170 42	140 100	150	800 31	173
(bj)	50	90	100	60	31

13.  Исследуем полученный план на оптимальность. С этой целью повторяем этапы 4, 5, 6, 7;

4  составляем уравнение потенциалов для базовых клеток

U1+V2=90 U2+V1=30 U3+V2=42 U3+V5=80

U1+V4=28 U2+V2=32 U3+V3=100

5  Находим потенциалы для базовых клеток

U1=0 V1=-26

U2=4 V2=120

U3=38 V3=62

V4=28

V5=762

6  Составляем уравнение невязок для небазовых клеток

7  Так как все невязки свободных клеток отрицательны, то план следует считаеть оптимальным;

14.  Отыскиваем целевую функцию без дополнительного потребителя (объекта), используя матрицу оптимального плана:

F=0.05*[(30*50)+(120*48+170*42)+(140*100)+(90*28+110*32)]=
0.05*[1500+5760+7140+14000+2520+3520] =1722 тыс. руб.

15.  Таким образом, в оптимальном варианте целесообразно распределение закрепление объектов за экспедициями по следующим объемам

Экспедиции (исполнители)	Объекты (потребители) км2	Контроль
1	2	3	4
1	-	48	-	28	76
2	50	-	-	32	82
3	-	42	100	-	(173) 142
Контроль	50	90	100	60	(331) 300

Примечание: В экспедиции №3 имеются резервы производственных ресурсов достаточных для выполнения 31 км.2 условно-натуральной продукции. Данные резервы могут быть использованы для выполнения договорных работ или утилизированы.

ЗАДАЧА 1

Хабаровское аэрогеодезическое предприятие выиграло тендеры по пяти госбюджетным объектам на 200…г. Для составления текущего (годового) плана предприятия требуется распределить объекты по трем комплексным экспедициям предприятия.

Исходные данные приведены в таблице 1.

Распределение объектов произвести под условием минимизации издержек на внешний и внутренний транспорт.

Таблица 1

Исходные данные к задаче № 1.

Экспедиции	Наименование объектов и расстояние до экспедиций и стоимость транспортных издержек на единицу км2/км (j)
(i) / M, k	Mi	k i	1. Угольный	2. Иманский	3. Боровой	4. Холмский	5. Лазаревский
Ц/ij	Sij	Ц/ij	Sij	Ц/ij	Sij	Ц/ij	Sij	Ц/ij	Sij
1	1200	0,85	0,03	260	0,05	220	0,04	550	0,06	909	0,04	800
2	1500	0,90	0,05	280	0,03	320	0,02	400	0,07	840	0,05	620
3	900	0,78	0,02	800	0,02	900	0,05	220	0,06	400	0,05	110
Потребность (bj)	600	450	800	400	500

Примечания:

1. Потребность объектов (bj) и мощность экспедиций (Mi) приведены в условно-натуральных показателях (УНП) измеряемых в км2;

2. Расстояния Sij даны в км.;

3.  Стоимость транспортировки единицы УНП на один км. Ц/ij даны в тыс. руб.;

4.  При расчете возможности (Mi k i) экспедиций округлять до целых;

5.  Исходные данные преобразовать к своему варианту путем прибавления к каждому значению Sij числа N - число из двух последних цифр варианта Nворп (т. е. Sij +N).

Литература:

, Кимельман программирование в планировании геодезических и топографических работ. Издательство «Недра», 1972 – 232 стр.