Планирование перевозок кирпича

Введение

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

Цель транспортной задачи - разработка наиболее рациональных путей и способов транспортировки товаров, устранение чрезмерно дальних, встречных и повторных перевозок.

В наиболее общем виде транспортная задача может быть поставлена так - требуется найти наиболее экономичный план перевозок от поставщиков к потребителям.

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

Задачами курсовой работы являются:

·        изучить литературу по теме транспортной задачи и линейного программирования;

·        сформулировать постановку транспортной задачи;

·        обоснование выбора метода потенциалов для проверки оптимального плана грузоперевозок;

·        описание метода решения задачи;

·        построить транспортную модель задачи и обосновать оптимальный вариант;

·        проанализировать полученный результат.

1. Обзор литературы по теме исследования

Информационной базой для написания работы послужили учебные пособия отечественных авторов: Бурда Г.П. Методы оптимальных решений и теория игр: пособие для вузов, Вентцель Е.С. Исследование операций: задачи, принципы, методология, Горлач Б.А. Исследование операций и другие.

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

Перед началом решения транспортной задачи строится транспортная таблица [1, 2, 3, 4]:

Потреб. Поставщ.	1	…	j	…	n	Запас
1	c11 x11	…	c1j x1j	…	c1n x1n	a1
…	…	…	…	…	…	…
i	ci1 xi1	…	cij xij	…	cin xin	ai
…	…	…	…	…	…	…
m	cm1 xm1	…	cmj xmj	…	cmn xmn	am
Спрос	b1	…	bj	…	bn

где

m - количество пунктов отправления (поставщиков);

i - номер поставщика;

n - количество пунктов назначения (потребителей);

j - номер потребителя;

ai - объем однородного груза i-го поставщика (запасы);

bi - объем однородного груза, требуемого j-ому потребителю (спрос);

cij - стоимость доставки единицы груза i-го поставщика j-ому потребителю;

xij - количество груза, доставляемое от i-го поставщика к j-му потребителю;

С - общие затраты на перевозки.

Равенство запаса и спроса есть необходимое и достаточное условие совместимости и, следовательно, разрешимости транспортной задачи.

Метод минимального тарифа учитывает величины затрат на грузоперевозки, позволяет найти опорный план транспортной задачи, при котором общая стоимость перевозок груза меньше, чем стоимость перевозок при плане северо-западного угла [1, 2, 3, 4, 5, 6].

Выбирается клетка, имеющая минимальную стоимость перевозок (минимальный тариф). Если таких клеток более одной, то выбирается первая по порядку.

В клетку с наименьшим тарифом помещается наименьшее из чисел ai или bj.

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

В завершении проверяется число загруженных клеток (m + n - 1).

Если число загруженных клеток будет меньше, то следует загрузить нулем клетку с наименьшим тарифом, но такую, чтобы она не образовывала замкнутого цикла.

Метод потенциалов - процесс последовательного улучшения исходного плана грузоперевозок до оптимального.

После того как найден исходный опорный план перевозок, каждому поставщику ai ставится в соответствие потенциал ui, а каждому потребителю bj ставится в соответствие потенциал vj.

Числа ui и vj выбираются так, чтобы в любой загруженной клетке сумма потенциалов равнялась стоимости перевозки в этой клетке:

vj + ui = cij

Для оценки плана необходимо просмотреть свободные клетки, для которых определяются косвенные тарифы c’ij = ui + vj

Для каждой свободной клетки вычисляется оценка - разность между тарифом клетки и ее косвенным тарифом:

Dij = cij - c’ij

План оптимален тогда, когда по каждой свободной клетке эта оценка неотрицательна.

Если есть хоть одна отрицательная оценка, то план надо улучшить, то есть построить новый план.

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

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

Для каждой свободной клетки существует только один цикл.

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

В результате такого перемещения груза по циклу получим новый план перевозок.

2. Постановка и формализация задачи

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

Кирпичный завод	Цена перевозки 1 тыс. шт. кирпича к объекту						Производство кирпича (тыс. шт.)
	1	2	3	4	5	6
I	8	7	5	10	12	8	240
II	13	8	10	7	6	13	360
III	12	4	11	9	10	11	180
IV	14	6	12	13	7	14	120
V	9	12	14	15	8	13	150
Потребность в кирпиче (тыс. шт.)	230	220	130	170	190	110

Для решения поставленной задачи применяется метод построения транспортной таблицы способом минимального тарифа. На оптимальность план проверяется методом потенциалов.

3. Построение математической модели задачи

 

3.1 Целевая функция и критерий оптимизации

Целевой функцией в транспортной задаче является стоимость грузоперевозок.

С = 8x₁₁+7x₁₂+5x₁₃+10x₁₄+12x₁₅+8x₁₆+13x₂₁+8x₂₂+10x₂₃+7x₂₄+6x₂₅+13x₂₆+

+12x₃₁+4x₃₂+11x₃₃+9x₄₄+10x₃₅+11x₃₆+14x₄₁+6x₄₂+12x₄₃+13x₄₄+7x₄₅+14x₄₆

+9x₅₁+12x₅₂+14x₅₃+15x₅₄+8x₅₅+13x₅₆ → min

3.2 Система ограничений

Ограничения по поставкам

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅+x₁₆ = 240

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅+x₂₆ = 360

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅+x₃₆ = 180

x₄₁+x₄₂+x₄₃+x₄₄+x₄₅+x₄₆ = 120

x₅₁+x₅₂+x₅₃+x₅₄+x₅₅+x₅₆ = 150

Ограничения по потребителям

x₁₁+ x₂₁+ x₃₁+ x₄₁+ x₅₁ = 230

x₁₂+ x₂₂+ x₃₂+ x₄₂+ x₅₂ = 220

x₁₃+ x₂₃+ x₃₃+ x₄₃+ x₅₃ =130

x₁₄+ x₂₄+ x₃₄+ x₄₄+ x₅₄ = 170

x₁₅+ x₂₅+ x₃₅+ x₄₅+ x₅₅ = 190

x₁₆+ x₂₆+ x₃₆+ x₄₆+ x₅₆ = 110

4. Решение задачи на ЭВМ с помощью программы

Вводим исходные данные в программу.

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

Запасы поставщиков: 240 + 360 + 180 + 120 + 150 =1050 единиц продукции.

Потребность потребителей: 230 + 220 + 130 + 170 + 190 + 110 =1050 единиц продукции.

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

Строится первая транспортная таблица.

Поставщик	Потребитель						Запас
	B 1	B 2	B 3	B 4	B 5	B 6
A 1	8	7	5	10	12	8	240
A 2	13	8	10	7	6	13	360
A 3	12	4	11	9	10	11	180
A 4	14	6	12	13	7	14	120
A 5	9	12	14	15	8	13	150
Потребность	230	220	130	170	190	110

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

Поставщик	Потребитель						Запас
	B 1	B 2	B 3	B 4	B 5	B 6
A 1	110   8	7	130   5	10	12	8	240 0
A 2	13	8	10	170   7	190   6	13	360 0
A 3	12	180   4	11	9	10	11	180 0
A 4	14	40   6	12	13	7	80   14	120 0
A 5	120   9	12	14	15	8	30   13	150 0
Потребность	230 0	220 0	130 0	170 0	190 0	110 0

Стоимость доставки продукции, для начального решения

С = 110 * 8 + 130 * 5 + 170 * 7 + 190 * 6 + 180 * 4 + 40 * 6 + 80 * 14 + 120 * 9 + 30 * 13 = 7410 ден. ед.

Далее задача проверяется на вырожденность

m+n-1

Требуется, чтобы количество загруженных ячеек равнялось 10.

В данной задаче, количество загруженных ячеек равняется 9.

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

·        Желательно, чтобы стоимость доставки продукции по маршруту была как можно меньше.

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

Это ячейка А₄В₅

Поставщик	Потребитель						Запас
	B 1	B 2	B 3	B 4	B 5	B 6
A 1	110   8	7	130   5	10	12	8	240
A 2	13	8	10	170   7	190   6	13	360
A 3	12	180   4	11	9	10	11	180
A 4	14	40   6	12	13	0   7	80   14	120
A 5	120   9	12	14	15	30   13	150
Потребность	230	220	130	170	190	110

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

Поставщик	Потребитель						Запас
	B 1	B 2	B 3	B 4	B 5	B 6
A 1	110 - 30   8	7	130   5	10	12	+ 30  -4 8	240
A 2	13	8	10	170   7	190   6	13	360
A 3	12	180   4	11	9	10	11	180
A 4	14	40   6	12	13	0   7	80   14	120
A 5	120 + 30   9	12	14	15	8	30 - 30   13	150
Потребность	230	220	130	170	190	110

Получаем новый план грузоперевозок.

Поставщик	Потребитель						Запас
	B 1	B 2	B 3	B 4	B 5	B 6
A 1	80   8	7	130   5	10	12	30   8	240
A 2	13	8	10	170   7	190   6	13	360
A 3	12	180   4	11	9	10	11	180
A 4	14	40   6	12	13	0   7	80   14	120
A 5	150   9	12	14	15	8	13	150
Потребность	230	220	130	170	190	110

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

Поставщик	Потребитель						Запас
	B 1	B 2	B 3	B 4	B 5	B 6
A 1	80   8	7	130   5	10	12	30   8	240
A 2	13	8	10	170   7	190   6	13	360
A 3	12	180 - 80   4	11	9	10	+ 80  -1 11	180
A 4	14	40 + 80   6	12	13	0   7	80 - 80   14	120
A 5	150   9	12	14	15	8	13	150
Потребность	230	220	130	170	190	110

Получаем новый план грузоперевозок.

Поставщик	Потребитель						Запас
	B 1	B 2	B 3	B 4	B 5	B 6
A 1	80   8	7	130   5	10	12	30   8	240
A 2	13	8	10	170   7	190   6	13	360
A 3	12	100   4	11	9	10	80   11	180
A 4	14	120   6	12	13	0   7	14	120
A 5	150   9	12	14	15	8	13	150
Потребность	230	220	130	170	190	110

Оценки всех незадействованных маршрутов неотрицательные. Следовательно, найденное решение оптимально. С = 80*8+130*5+30*8+170*7+190*6+100*4+80*11+120*6+0*7+150*9 = 7210.

перевозка поставка компьютер маршрут

5. Анализ результатов решения задачи

Решенная транспортная задача имеет закрытый тип, следовательно, в данной задаче не остается излишек на складе поставщика кирпича и спрос покупателя полностью удовлетворен.

При первом построении плана грузоперевозок методом минимального тарифа стоимость перевозки составила 7410 ден. ед. Далее был применен метод потенциалов для проверки плана на оптимальность.

Метод потенциалов показал, что план перевозок можно улучшить, что показывает его стоимость 7210 ден. ед. Разница стоимости грузоперевозок показывает, что метод потенциалов позволяет оптимизировать первоначальный план грузоперевозок на 200 ден. ед.

Заключение

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

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

Список источников

1.     Бурда А.Г. Математическое моделирование в управлении плодоводческими предприятиями / А.Г. Бурда, С.Н. Косников. - Краснодар: КГАУ, 2012. - 101 с.

2.   Бурда Г.П. Методы оптимальных решений и теория игр: пособие для вузов / Г.П. Бурда, А.Г. Бурда. - Краснодар: КубГАУ, 2011. - 491 с.

3.     Вентцель Е.С. Исследование операций: задачи, принципы, методология: учебное пособие / Е.С. Вентцель. - 5-е изд., стер. - М.: КноРус, 2010. - 191 с.

4.       Горлач Б.А. Исследование операций / Б.А. Горлач. - Санкт-Петербург: Лань, 2013. - 442 с.

5.     Зайцев М.Г., Варюхин С.Е. Методы оптимизации управления и принятия решений: примеры, задачи, кейсы: учебное пособие. - 2-е изд., испр. - М.: Изд-во «Дело» АНХ, 2008. - 664 с.

.       Исследование операций в экономике: учебное пособие / Н.Ш. Кремер [и др.]; под ред. Н.Ш. Кремера. - 2-е изд., перераб. и доп. - М.: Юрайт, 2010. - 430 с.