Оптимизация в планировании перевозок (стр. 2 из 2)

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

Таблица 1 Исходная информация

Вид ресурса (автомобили)	Объем груза, перевезенного за смену одним автомобилем, т				Запас ресурсов (кол. автомобилей)
	Груз 1-го вида		Груз 2-го вида
	Маршрут 1	Маршрут 2	Маршрут 3	Маршрут 4
q=3	14	7	15	9	10
q=5	15	5	17	9	15
Плановый объем перевозок, т	150	100	200	250	__

Исходя из данных, составим систему неравенств, которая в математическом виде воспроизводит решаемую задачу:

х11+х21+х31+х41 ≤ 10

х12+х22+х23+х42 ≤ 15

14х11+15х12 ≤ 150

7х21+5х22 ≤ 100(1)

15х31+17х32 ≤ 200

9х41+9х42 ≤ 250

Так как целью решения является обеспечение максимального объема перевозок имеющимся парком подвижного состава, то условия оптимизации решения задачи записываются в виде:

Qmax=14х11+15х12+7х21+5х22+15х31+17х32+9х41+9х42. (2)

В уравнениях (1) и (2) xij – количество автомобилей i-го типа, работающих на j-м маршруте при перевозках соответствующего вида груза, но так как на каждом маршруте перевозятся по два вида груза, то это равносильно рассмотрению четырех маршрутов. Поэтому принята сквозная нумерация по j.

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

При решении задач симплекс-методом все неравенства (1) необходимо обратить в равенства. Для этого введем свободные переменные х1, х2, …,х6 ≥ 0.

Тогда

х11+х21+х31+х41+х1=10

х12+х22+х23+х42 +х2=15

14х11+15х12+х3=150

7х21+5х22+х4= 100(3)

15х31+17х32 +х5=200

9х41+9х42+х6=250

Qmax=14х11+15х12+7х21+5х22+15х31+17х32+9х41+0х1+0х2+0х3+0х4+0х5+0х6 ® max. (4)

Свободные переменные х1 и х2 выражают количество неиспользованных автомобилей из числа имеющихся, а х3, …, х6 – объем неперевезённого груза. В целевую функцию они входят с коэффициентами, равными нулю.

Все данные полученных уравнений заносятся в специальную симплекс-таблицу (таблица 2).

Каждая строка в симплекс-таблице отражает по порядку все ранее написанные уравнения, а по столбцам таблицы располагаются коэффициенты, с которыми переменные (х11, х12, …, х6) входят в соответствующее уравнение. Если какая-либо переменная не входит в рассматриваемое уравнение, то в таблице для нее проставляется нуль. В индексной строке записываются коэффициенты при соответствующей переменной в выражении целевой функции с обратным знаком.

Алгоритм вычислений симплекс-методом состоит в следующем.

Шаг 1. Выбираем в индексной строке наибольшее отрицательное число. Ему соответствует ключевой столбец. В таблице 2 это столбец х32 с числом 17.

Шаг 2. Определяем ключевую строку. Для этого разделим числа столбца свободных членов на соответствующие им положительные числа ключевого столбца: 10/0 = ∞; 15/1 = 15; 150/0= ∞; 200/17 = 11,76; 250/0 = ∞. Из всех полученных частных выбираем наименьшее (200/17 = 11,76). Оно определяет ключевую строку.

На пересечении ключевой строки и ключевого столбца находится ключевое число (17).

Шаг 3. Переходим к построению следующей симплекс-таблицы, в которой в первую очередь заполняется главная строка. Главная строка располагается там, где в предыдущей симплекс-таблице находилась ключевая строка, а числа главной строки определяются путем деления чисел ключевой строки на ключевое число. Вместо прежнего переменного в столбце переменных записывается переменное соответствующего ключевого столбца. Поэтому для главной строки таблицы 3 в столбце переменных указано 11,76.

В том столбце, который в предыдущей таблице был ключевым, все клетки заполняются нулями, за исключением клетки, где находилось ключевое число. Там всегда будем иметь 1 по расчету чисел главной строки. Те столбцы, у которых в клетках ключевой строки (см. табл. 2) записаны нули, переписываются без изменений. Аналогично правило и для строк. Если в ключевом столбце строке соответствует нуль, то она переписывается в следующую таблицу без изменений.

Для остальных клеток (в столбце свободных членов клетка строки х2, х3, х2, х5, х2 и в индексной строке клетка столбца х32) определяются производные числа (Пр) по правилу:

Пр = Вч – КсКст/Кч,

где Вч – выбранное число;

Кс – соответствующее число в ключевой строке;

Кст – соответствующее число в ключевом столбце;

Кч – ключевое число.

Теперь известны все числа, и построение симплекс-таблицы (см. табл. 2) закончено. Так как в индексной строке еще сохранились отрицательные числа, то решение продолжается, повторяются все операции, описанные выше. Вычисления проводятся до той поры, пока в индексной строке одной из таблиц не окажутся числа больше или равные нулю. Опуская промежуточные решения, покажем сразу матрицу оптимального распределения (таблица 4).

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

Исходная симплекс-таблица Таблица 2

Столбец переменных	Столбец свободных членов	Строка переменных
		Х11	Х12	Х21	Х22	Х31	Х32	Х41	Х42	Х1	Х2	Х3	Х4	Х5	Х6
Х1	10	1	0	1	0	1	0	1	0	1	0	0	0	0	0
Х2	15	0	1	0	1	0	1	0	1	0	1	0	0	0	0
Х3	150	14	15	0	0	0	0	0	0	0	0	1	0	0	0
Х4	100	0	0	7	5	0	0	0	0	0	0	0	1	0	0
Х5	200	0	0	0	0	15	17	0	0	0	0	0	0	1	0
Х6	250	0	0	0	0	0	0	9	9	0	0	0	0	0	1
Индексная строка	___	-14	-15	-7	-5	-15	-17	-9	-9	0	0	0	0	0	0

Промежуточная симплекс-таблица Таблица 3

Столбец переменных	Столбец свободных членов	Строка переменных
		Х11	Х12	Х21	Х22	Х31	Х32	Х41	Х42	Х1	Х2	Х3	Х4	Х5	Х6
Х1	10	1	0	1	0	1	0	1	0	1	0	0	0	0	0
Х2	3,24	0	1	0	1	-0,88	0	0	1	0	1	0	0	-0,06	0
Х3	150	14	15	0	0	0	0	0	0	0	0	1	0	0	0
Х4	100	0	0	7	5	0	0	0	0	0	0	0	1	0	0
Х32	11,76	0	0	0	0	0,88	1	0	0	0	0	0	0	0,06	0
Х6	250	0	0	0	0	0	0	9	9	0	0	0	0	0	1
Индексная строка	__	-14	-15	-7	-5	0	0	-9	-9	0	0	0	0	0	0

Оптимальная симплекс-таблица Таблица 4

Столбец переменных	Столбец свободных членов	Строка переменных
		Х11	Х12	Х21	Х22	Х31	Х32	Х41	Х42	Х1	Х2	Х3	Х4	Х5	Х6
Х41	2,76	0	0	1	1,07	0,06	0	1	1,07	1	1,07	-0,07	0	-0,064	0
Х12	3,24	0	1	0	1	-0,82	0	0	1	0	1	0	0	-0,06	0
Х11	7,25	1	0	0	-1,07	0,94	0	0	-1,07	0	-1,07	0,07	0	0,064	0
Х4	100	0	0	7	5	0	0	0	0	0	0	0	1	0	0
Х32	11,76	0	0	0	0	0,88	1	0	0	0	0	0	0	0,06	0
Х6	225,16	0	0	-9	-9,63	-0,54	0	9	-0,63	-9	-9,63	-0,63	0	0,576	1
Индексная строка	__	0	0	2	34,63	0,54	0	0	0,63	9	9,63	0,37	0	0,424	0

Литература

1. В.И. Николин, Е.Е. Витвицкий, С.М. Мочалин, Н.И. Ланьков «Основы теории автотранспортных систем ( грузовые автомобильные перевозки )»

2. В.И. Николин «Автотранспортный процесс и оптимизация его элементов»