Оптимизация плана перевозок материально-технического имущества



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

Ключевые слова: оптимизация, войсковая перевозка, экономико- математическая задача.

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

Перед проведением учений в трех войсковых частях (в/ч № 1, в/ч № 2, в/ч № 3) необходимо провести техническое обслуживание № 2 (ТО-№ 2) соответственно 12, 16, 18 изделий.

Техническое обслуживание могут выполнять четыре ремонтных подразделения (РП1, РП2, РПЗ, РП4), каждое из которых имеет на этот период фонд времени на техническое обслуживание 10, 12, 11, 13 (АО) соответственно.

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

Таблица 1

Исходные данные

Пункты от­правления	Пункты назначения				Запасы
	РП1	РП2	РП3	РП4
В/ч № 1	4	3	5	2	12
В/ч № 2	5	2	4	3	16
В/ч № 3	1	4	6	7	18
Заявки	10	12	И	13	46

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

Для построения экономико-математической модели обозначим Х_ij — количество артиллерийских орудий, отправляемых на техническое обслуживание i-й войсковой части в j-e ремонтное подразделение; С_ij — стоимость перевозки артиллерийских орудий из i-й войсковой части в j-e ремонтное подразделение; j=1n — ремонтное подразделение; i=1_m — войсковые части.

Неотрицательные переменные ху должны удовлетворять следующим условиям:

‒ суммарное количество артиллерийских орудий, направляемых из каждой войсковой части во все ремонтные подразделения, должно быть равно количеству артиллерийских орудий в войсковой части. Это дает три условия равенств:

х₁₁+х₁₂+х₁₃+х₁₄=12;

х₂₁+х₂₂+х₂₃+х₂₄=16;

х₃₁+х₃₂⁺ х₃₃+х₃₄=18.

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

х₁₁+х₂₁+1+х₃₁=10;

х12+х22+х₃2=12;

х₁з+х₂₃+х₃₃=11;

х14+х24+х34=13.

Суммарная стоимость всех перевозок, то есть сумма величин хij, умноженных на соответствующие стоимости С_ij,- должна быть минимальной:

L=ΣΣС_ijx_ij → min,

где знак двойной суммы означает, что суммирование производится по всем комбинациям индексов i и j, то есть по всем параметрам «войсковая часть — ремонтное подразделение»;

L=(х1₁+2х₁₂+4х13+3х₁₄+2х21+х2₂+5х₂₃+6х₂₄+3х31+4х₃₂+2х₃₂+ х₃₄) → min

Далее составляем опорный план применим так называемый «метод северо-западного угла» (табл. 2). Начнем заполнение транспортной таблицы с левого верхнего «северо-западного угла». Пункт РП₁ подал заявку на 10 артиллерийских орудий. Удовлетворим эту заявку за счет запасов войсковой части (1–12 артиллерийских орудий) и запишем в клетку 1.1.

После этого заявка РП₁ удовлетворена, а в пункте отправления в/ч № 1 осталось еще 12–10=2 артиллерийских орудия; отдадим их пункту РП₂, запишем2 в клетку 1.2. Но заявка этого пункта еще не удовлетворена; выделим 10 артиллерийских орудий из пункта в/ч № 2 и впишем в клетку 2.2. Заявка пункта РП2 удовлетворена полностью. В в/ч № 2 осталось 6 артиллерийских орудий, требующих технического обслуживания. Удовлетворим за счет них заявку РП3 (запишем в клетку 2.3). В составе заявки РП3 остались неудовлетворенными 5 артиллерийских орудий. Возьмем эти 5 единиц из запаса пункта в/ч № 3 и запишем в клетку 3.3. Заявка пункта РП3 теперь удовлетворена. В пункте в/ч № 3 осталось еще 13 артиллерийских орудий. Удовлетворим за счет этих 13 единиц заявку РП4.

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

Проверим, является ли этот план допустимым: да, потому, что в нем сумма перевозок по строкам равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу — заявке соответствующего пункта назначения, значит, все заявки удовлетворены, все запасы израсходованы (сумма запасов равна сумме заявок и числу 46, стоящему в правом нижнем углу табл. 2).

Таблица 2

Распределение запасов

Пункты отправления	Пункты назначения				Запасы
	РП1	РП2	РП3	РП4
В/ч № 1	4 10	3 2	5	2	12
В/ч № 2	5	2 10	4 6	3	16
В/ч № 3	1	4	6 5	7 13	18
Потребность в изделиях	10	12	11	13	46

Здесь и в дальнейшем мы проставляем в таблице только отличные от нуля перевозки, а клетки, соответствующие нулевым перевозкам, оставляем свободными. Проверим, является ли план перевозок, данный в табл. 3, опорным (не слишком ли там много отличных от нуля «базисных» перевозок?). Число «базисных» клеток равно m+n-l=3+4-l=6 нулевых перевозок. План является опорным. Возникает вопрос: является ли этот план оптимальным по стоимости? Нет! Ведь при его составлении мы не учитывали стоимость перевозок С_ij. Стоимость этого плана, рассчитанного по формуле, равна

С=40+6+20+24+20+91=201 усл. ед.

Далее методом последовательного улучшения находим оптимальный план. Улучшить план можно, если произвести в нем «циклическую перестановку» перевозок между клетками таблицы. Для этого выбираем произвольную свободную клетку, например 1.3 (см. табл. 3). Оказывается, что в опорном, плане однозначным образом можно выбрать замкнутую цепочку, называемую циклом, состоящую только из вертикальных и горизонтальных звеньев, одной из вершин которой является выбранная свободная клетка, а остальными вершинами — занятые клетки (см. табл. 2).

После образования цикла свободной клетке и связанным с ней занятым клеткам присваивается поочередно знак «минус» или «плюс» начиная со свободной клетки. В нашем примере расстановка знаков показана в табл. 2.

Далее просматриваем те занятые клетки, которым присвоен знак «минус», и выбиваем ту из них, в которой содержится наименьшая постановка. Это количество артиллерийских орудий подлежит перемещению из каждой клетки со знаком «минус» в каждую клетку (в том числе и свободную) со знаком «плюс». Совершив — эту процедуру, мы будем иметь новый план (табл. 3). Законченный цикл вычислений, приводящих к получению нового плана, называется вычислением отдельной операции.

Стоимость нового плана равна

С=40+4+24+16+4–42+77=203 уел. ед.

Таблица 3

План распределения запасов

Пункты отправления	Пункты назначения				Запасы
	РП1	РП2	РП3	РП4
В/ч № 1	4- 10	3	5-	2+ 2	12
В/ч № 2	5	2 12	4 4	3	16
В/ч № 3	1+	4	6+ 7	7- 11	18
Потребности	10	12	11	13	46

Назовем ценой цикла изменение стоимости перевозок при перемещении одной единицы груза по обозначенному циклу.

Цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, причем стоимости, стоящие в положительных вершинах цикла, берутся со знаком «плюс», а в отрицательных — со знаком «минус».

Например, для цикла (см. табл. 3) цена равна

γ=2–7+6–5=-4

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

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

Для дальнейшего улучшения плана возьмем свободную клетку 3.1. Цикл, соответствующий этой клетке, показан в табл. 3, цена цикла равна

γ=1–4+2–7= -8.

По этому циклу перемещаем 10 единиц из каждой клетки со знаком «минус» в клетки со знаком «плюс».

Новый план приведен в табл. 4.

Таблица 4

План распределения запасов

Пункты отправления	Пункты назначения				Запасы
	РП1	РП2	РП3	РП4
В/ч № 1	4	3	5	2 12	12
В/ч № 2	5	2 12	4- 4	3+	16
В/ч № 3	1 10	3	6+ 7	7- 1	18
Потребности	10	12	11	13	46

Стоимость нового плана равна С=24+24+16+10+42+7=123 уел. ед.

Для дальнейшего улучшения плана возьмем свободную клетку 2.4. Цикл, соответствующий этой клетке, показан в табл.4. Цена этого цикла равна

γ=3–7+6–4= -2.

По этому циклу перемещаем единицы из каждой клетки со знаком «минус» в клетку со знаком «плюс». Новый план приведен в табл. 5.

Таблица 5

Новый план распределения запасов

Пункты отправления	Пункты назначения				Запасы
	РП1	РП2	РП3	РП4
В/ч № 1	4	3	5	2 12	12
В/ч № 2	5	2 12	4 4	3	16
В/ч № 3	1 10	3	6 7	7 1	18
Потребности	10	12	11	13	46

Стоимость нового плана равна

С=24+24+3+10+48=109 уел. ед.

Попробуем дальше улучшить этот план. Для этого составим для всех свободных клеток циклы и подсчитаем их цены.

Для клеток

γ=4–2+3–4+6–1=+6

γ=3–2+3–2=+2

γ=5–2+3–4=+2

γ=5–4+6–1=+6

γ=4–6+4–2=0

γ=7–3+4–6=+2

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

Литература:

1. Перегудов А. Б. Математические модели в организации транспортных процессов: учеб. пособие / А. Б. Перегудов, С. П. Павлов. Саратов: Сарат. гос. техн. ун-т, 2013. 84 с.
2. Экономика промышленности и машиностроительного производства: учебное пособие / В. В. Теплухин, А. В. Мешков, А. Н. Рыбаков и др. — Пенз. ПАИИ, 2007/ — 235 c.