Информатика

Решение транспортных задач в Excel (стр. 3 из 4)

Таблица 7 – Структура парка автомобилей автотранспортной компании

КОЛИЧЕСТВО АВТОМОБИЛЕЙ
МАРКИ А	МАРКИ В	МАРКИ С	МАРКИ D	МАРКИ Е
0	4	3	2	1

Таблица 8 – Заказ на перевозку груза

ХАРАКТЕРИСТИКИ	КЛИЕНТЫ
ХАРАКТЕРИСТИКИ	1	2	3	4	5	6	7	8	9
*Q_j, Т*	100	35	45	95	15	125	35	5	50
*L_j, КМ*	50	60	70	18	20	10	12	25	28

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

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

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

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

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

Стоимость выполнения всего комплекса работ равна

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

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

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

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

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

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

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

У автотранспортной компании имеется n автомобилей разных марок. Автомобили разных марок имеют разную грузоподъёмность q_i (т) и разные удельные эксплуатационные затраты c_i ($/км). Компания получила заказы от m клиентов на перевозку грузов. Причём в каждом заказе указан объём перевозимого груза Q_j (т) и расстояние перевозки L_j (км). Требуется, используя табличный процессор Excel, оптимальным образом назначить автомобили на рейсы для выполнения заказов клиентов, полагая тарифы на перевозки одинаковыми.

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

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

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

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

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

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

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

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

, для всех i=1,2,…k; j=1,2,…k.

Количество рейсов - величина целочисленная, принимающая значение большее или равное 1. Для её вычисления следует воспользоваться функцией округления частного от деления в большую сторону. Например, если исходные данные находятся в ячейках B29:C29 и D26:D27, то количество рейсов определяется функцией (второй параметр функции округления равен 0)

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

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

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

,

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

=ОКРУГЛВВЕРХ($B6/D$3;0)*$C6*D$4

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

Целевая функция имеет вид

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

;

;

целое для всех i,j =1,2,… k.

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

Автотранспортная компания располагает 10 автомобилями разных марок: 0 автомобилей марки A; 4 автомобиля марки B; 3 автомобиля марки C; 2 автомобиль марки D; 1 автомобилей марки E.

читать дальше

3