Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Воронежская государственная лесотехническая академия

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

4640

.pdf

Скачиваний:

Добавлен:

08.01.2021

Размер:

1.27 Mб

Скачать

☆

<<< < Предыдущая 1 2 34 / 54 5 > Следующая >>>

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 4. ЗАДАЧА О НАЗНАЧЕНИЯХ

Цель работы: изучить модель задачи о назначениях, освоить надстройку Поиск решения в Excel, научиться формализации реальных задач организации перевозок в виде модели этого вида.

4.1. Математическая постановка задачи о назначениях

Предположим, что имеется n различных работ, каждую из которых может выполнить любой из n привлеченных исполнителей. Стоимость выполнения i-ой работы j-ым исполнителем известна и равна сij (в условных денежных единицах). Необходимо распределить исполнителей по работам (назначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затраты, связанные с выполнением всего комплекса работ.

В исследовании операций задача, сформулированная выше, известна как задача о назначениях. Введем переменную хij, принимающую значение 1 в случае, когда i-ю работу выполняет j-ый исполнитель, и значение 0 во всех остальных случаях, i, j = 1,..., n. Тогда ограничение /1, 2/

n
xij 1, i 1, , n ,	(4.1)

j 1

гарантирует выполнение каждой работы лишь одним исполнителем, а ограничение /1, 2/

n
xij 1, j 1, , n ,	(4.2)

i 1

гарантирует, что каждый из исполнителей будет выполнять лишь одну работу. Стоимость выполнения всего комплекса работ равна /1, 2/

n n
cijxij .	(4.3)

i 1 j 1

Таким образом, задачу о назначениях можно записать следующим образом

/1, 2/:

n n
cijxij min
i 1 j 1
n
xij			1, i 1, , n		(4.4)
j 1				.	(4.4)
n
n
xij			1, j 1, , n
i 1
i 1		0, 1 , i 1, , n, j 1,
x
x	ij			, n
	ij

Задача о назначениях является частным случаем классической транспортной задачи, в которой надо положить n = m; Si = 1, i = 1, ..., n; Dj = l, j = 1, ..., n. При этом условие хij {0, 1}; i, j = 1, ..., n означает выполнение требования целочисленности переменных хij. Это связано с тем, что мощности всех источников и стоков равны 1, откуда следует, что в допустимом целочисленном решении значениями переменных могут быть только 0 и 1.

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

В задаче о назначениях переменная хij может принимать значение 0 или 1. При этом в любом допустимом решении лишь n переменных могут принимать значение 1. Таким образом, любое допустимое базисное решение задачи о назначениях будет вырожденным.

На практике встречаются задачи о назначениях, в постановках которых параметр сij для i, j = 1, ..., n понимается как эффективность выполнения i-ый работы j-ым исполнителем. В этих случаях нужно так распределить работы между исполнителями, чтобы суммарная эффективность их выполнения была бы максимальной, т. е. /1, 2/

n n
cijxij max ,	(4.5)

i 1 j 1

где максимум находится при указанных выше ограничениях.

4.2. Решение задачи о назначениях в Excel

Рассмотрим методику решения в Excel задачи о назначениях на основании следующего примера.

Задача 4.1. У автотранспортной компании имеется n автомобилей разных марок. Автомобили разных марок имеют разную грузоподъемность qi (т) и разные удельные эксплуатационные затраты сi, (тыс. руб./км). Компания получила заказы от m клиентов на перевозку грузов. Причем в каждом заказе указан объем перевозимого груза Qj (т) и расстояние перевозки Lj (км). Требуется, используя табличный процессор Excel, оптимальным образом назначить автомобили на рейсы для выполнения заказов клиентов, полагая тарифы на перевозки одинаковыми.

Покажем, что представленная задача удовлетворяет рассмотренным выше требованиям:

1.Поскольку тарифы одинаковые, то в качестве целевой функции следует выбрать эксплуатационные затраты. Эти затраты необходимо минимизировать путем оптимального распределения автомобилей по клиентам.

2.Поскольку в общем случае m ≠ n, то задачу необходимо сбалансировать путем введения фиктивных заказов или фиктивных автомобилей. Получим:

при n > m заказов меньше, чем автомобилей (избыток провозных возможностей). В этом случае дополнительно вводятся n-m фиктивных клиентов с нулевыми объемами заказов (Qi = 0 и Li = 0). Поскольку для фиктивных клиентов заказы нулевые, то для их выполнения будут назначаться самые неэффективные по затратам автомобили. Практически выполнение заказа фиктивного клиента означает резервирование автомобиля (автомобиль остается в парке).

при n < m заказов больше, чем автомобилей (недостаток провозных возможностей). В этом случае дополнительно вводятся m-n фиктивных автомобилей с бесконечно большими удельными затратами (сj → ∞). Практически это означает отказ от самых невыгодных по затратам заказов.

3. Окончательно получим сбалансированную задачу, описываемую квадратной матрицей эксплуатационных затрат размерностью k × k, где k = max {m, n}.

Алгоритм решения данной задачи в Excel сводится к следующему.

Количество рейсов i-го автомобиля у j-го клиента вычисляется по фор-

муле /1, 2/

z		Q j	, для всех i 1, 2, , k; i 1, 2, , k.	(4.6)
	ij
		qi

Количество рейсов – величина целочисленная, принимающая значение, большее или равное 1. Для ее вычисления следует воспользоваться функцией округления частного от деления в большую сторону. Например, если исходные данные находятся в ячейках В7:С7 и D4:D5, то количество рейсов определяется функцией (второй параметр функции округления равен 0) /1, 2/

= ОКРУГЛВВЕРХ($В7/D$5;0)

(4.7)

Пробег i-го автомобиля y j-гo клиента вычисляется по формуле /1, 2/

Rij zij L j .

(4.8)

Эксплуатационные затраты вычисляются по формуле /1, 2/

Sij Rij ci zij L j ci ,

(4.9)

где сi – удельные эксплуатационные затраты, связанные с назначением i-го автомобиля для обслуживания j-го клиента, то есть для приведенного выше примера в ячейку D7 необходимо занести формулу /1, 2/

= ОКРУГЛВВЕРХ($В7/D$5;0)*$С7*D$4

(4.10)

Дополнительная целочисленная переменная логического типа принимает значения /1, 2/

	при назначении;
1	при назначении;
xij	иначе.	.	(4.11)
0	иначе.

Целевая функция имеет вид /1, 2/

k k
F Sij xij min ,	(4.12)

i 1 j 1

при ограничениях /1, 2/

k	k
xij 1;	xij 1; где xij 0	целое для всех i, j 1, 2, , k. (4.13)
i 1	j 1

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

Автотранспортная компания располагает 10 автомобилями разных марок: 3 автомобиля марки А; 3 автомобиля марки В, 2 автомобиля марки С; 1 автомобиль марки D; 1 автомобиль марки Е.

Характеристики автомобилей представлены в таблице 4.1.

													Таблица 4.1
		Характеристики автомобилей

	Характеристика							Марка автомобиля

					А			В			С		D			Е
					А			В			С		D			Е

	Грузоподъемность qi, т			20			16				8		5		2,5
	Удельные затраты сi, тыс.руб./км			0,8			0,55				0,35		0,25		0,13
	Компанией получены заказы от 9 клиентов. Характеристики заказов
представлены в таблице 4.2.
													Таблица 4.2
			Характеристики заказов

	Характеристика								Клиент

			1		2	3		4		5		б	7	8		9
			1		2	3		4		5		б	7	8		9

	Объем груза Qj, т		250		200	350		69		50		12	30	20		60
	Расстояние Lj, км		60		40	80		140		50		120	60	100		90

На рисунке 4.1 представлена таблица с исходными данными. Поскольку заказов меньше, чем имеющихся у компании автомобилей, необходимо ввести фиктивного клиента с нулевым объемом перевозок. В той же таблице

произвести необходимые промежуточные расчеты затрат по приведенным выше формулам.

Рис. 4.1 – Матрица затрат

На рисунках 4.2 и 4.3 представлены Матрица Xij содержащая переменные логического типа хij и Матрица произведения Sij*Xij, в которой отразится результат оптимального закрепления автомобилей за клиентами и, соответствующие этому закреплению, минимальные затраты.

Рис. 4.2 – Матрица переменных

Рис. 4.3 – Матрица произведений

Используя меню Сервис Поиск решения, открываем диалоговое окно Поиск решения (рисунок 4.4), в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек со значениями логической переменной xij (Матрица Xij) и ограничения и запускаем процедуру вычисления, щелкнув по кнопке Выполнить.

Результат поиска будет находиться в изменяемых ячейках Матрицы Xij (i – автомобиль; j – клиент) и в целевой ячейке (эксплуатационные затраты) (рис. 4.4). Как видно, оптимальный план назначения автомобилей на рейсы следующий: первый автомобиль направляется на обслуживание восьмого клиента, второй – девятого, третий – четвертого, четвертый – первого, пятый – третьего, шестой – второго, седьмой – седьмого, восьмой – пятого, десятый – шестого. Девятый автомобиль, назначенный фиктивному десятому клиенту, будет простаивать в парке. Эксплуатационные затраты при этом минимальны и составят 2698,5 тыс. руб.

Рис. 4.4 – Решение задачи о назначениях

4.3. Содержание отчета по практической работе № 4

В отчете представить математическую модель, таблицы Excel с решением задачи и сделать вывод о назначении автомобилей по маршрутам.

Задание 4.1. Решить задачу о назначениях в Excel и сделать вывод о назначении марки автомобиля по каждому маршруту.

					Таблица 4.3
	Транспортные средства

			Марка автомобиля
Характеристики		КАМАЗ-5320		ГАЗ-3307	ЗИЛ 5301АО
автотранспортных средств		КАМАЗ-5320		ГАЗ-3307	«Бычок»
автотранспортных средств		(тентованный)		(тентованный)	«Бычок»
		(тентованный)		(тентованный)	(тентованный)
					(тентованный)
Количество, шт.		3		4	5
Грузоподъемность, т		8		4,5	3
Тариф, руб./км		27		18	17

Таблица 4.4

Характеристики маршрутов

Вариант	Номер маршрута	1	2	3	4	5	6	7	8	9


1	2	3	4	5	6	7	8	9	10	11

1	Qi, т	3	11	12	12	19	2	3	22	12
	Li, км	37	12	24	20	2	9	38	5	29

2	Qi, т	47	31	74	13	57	7	89	60	23
	Li, км	18	6	24	13	27	20	3	15	19

3	Qi, т	11	25	12	20	30	11	4	29	18
	Li, км	33	16	29	3	16	27	32	13	20

4	Qi, т	53	38	95	60	23	56	46	49	92
	Li, км	13	15	23	10	16	20	20	13	22

5	Qi, т	4	2	10	22	6	14	1	12	23
	Li, км	38	21	24	2	45	4	9	35	12

6	Qi, т	54	91	69	76	3	23	59	14	14
	Li, км	4	13	3	13	25	5	16	3	25

7	Qi, т	13	11	9	27	6	2	22	16	27
	Li, км	40	12	2	7	42	9	50	18	1

8	Qi, т	32	7	95	89	36	77	62	70	13
	Li, км	12	11	6	19	9	27	15	25	8

9	Qi, т	19	24	13	21	15	14	27	21	3
	Li, км	15	20	22	50	20	6	39	42	13

10	Qi, т	80	12	94	30	40	78	35	25	71
	Li, км	22	15	10	6	4	8	4	14	16

Продолжение таблицы 4.4

1	2	3	4	5	6	7	8	9	10	11

11	Qi, т	19	18	12	1	11	4	13	22	14
	Li, км	16	50	11	49	45	30	26	41	25

12	Qi, т	8	50	100	82	88	26	62	77	83
	Li, км	14	3	23	1	25	12	2	7	27

13	Qi, т	5	16	21	9	12	17	4	10	13
	Li, км	4	3	26	50	49	18	1	14	19

14	Qi, т	58	45	62	89	74	21	41	3	43
	Li, км	14	12	21	24	5	21	15	30	17

15	Qi, т	25	30	26	17	21	14	3	18	25
	Li, км	27	16	24	37	27	9	36	17	4

16	Qi, т	96	68	27	44	97	4	48	63	34
	Li, км	3	20	27	8	9	19	8	2	5

17	Qi, т	11	13	3	18	12	7	26	23	7
	Li, км	39	45	24	45	49	8	42	5	15

18	Qi, т	67	79	60	58	62	78	11	55	81
	Li, км	28	9	5	2	17	6	25	16	8

19	Qi, т	19	14	20	28	13	5	16	3	22
	Li, км	46	38	29	12	25	43	49	42	2

20	Qi, т	5	16	22	76	48	57	85	81	41
	Li, км	9	17	5	15	29	21	19	13	3

21	Qi, т	6	22	2	30	20	11	27	30	13
	Li, км	3	18	35	27	38	41	42	9	5

22	Qi, т	41	13	87	50	12	58	94	39	36
	Li, км	21	8	26	5	13	28	10	9	11

23	Qi, т	3	17	6	24	26	23	11	15	22
	Li, км	23	25	18	9	34	37	48	41	48

24	Qi, т	27	97	2	20	67	17	43	1	75
	Li, км	24	20	23	13	7	14	9	17	1

25	Qi, т	15	14	11	13	9	6	28	8	30
	Li, км	20	5	32	7	6	37	5	31	30

26	Qi, т	34	76	51	39	54	75	12	34	54
	Li, км	12	3	25	15	26	26	19	17	4

27	Qi, т	8	25	4	17	26	15	10	1	28
	Li, км	28	5	47	14	16	41	47	9	4

28	Qi, т	40	42	51	93	17	62	89	23	88
	Li, км	23	7	18	7	10	6	22	14	18

29	Qi, т	6	7	8	3	18	22	8	17	17
	Li, км	25	13	45	43	46	8	10	24	33

30	Qi, т	76	37	2	85	97	87	32	93	62
	Li, км	3	13	1	6	14	20	18	11	27

31	Qi, т	12	13	22	3	3	23	16	20	19
	Li, км	4	10	19	48	14	20	30	50	36

32	Qi, т	42	65	95	2	26	20	89	5	44
	Li, км	4	29	8	10	9	18	15	12	23

33	Qi, т	9	10	5	30	3	15	12	14	11
	Li, км	24	36	40	46	44	41	11	17	18

34	Qi, т	61	11	67	90	94	18	79	83	38
	Li, км	4	24	23	4	10	1	18	2	7

35	Qi, т	2	22	15	8	30	2	13	5	19
	Li, км	27	43	12	32	47	34	26	24	20

<<< < Предыдущая 1 2 34 / 54 5 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
08.01.20211.26 Mб104636.pdf
#
08.01.20211.27 Mб84637.pdf
#
08.01.20211.27 Mб34638.pdf
#
08.01.20211.27 Mб244639.pdf
#
08.01.2021200.83 Кб2464.pdf
#
08.01.20211.27 Mб54640.pdf
#
08.01.20211.27 Mб1204641.pdf
#
08.01.20211.28 Mб94642.pdf
#
08.01.20211.28 Mб44643.pdf
#
08.01.20211.28 Mб14644.pdf
#
08.01.20211.29 Mб34646.pdf