Транспортная задача

Содержание

Введение 3

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

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

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

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

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

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

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

Заключение 19

Список использованных источников 20

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

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

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

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

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

 

 

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. Решение задачи на  ЭВМ с помощью программы

Решение задачи происходило с применением  онлайн программы из сети Интернет www.reshmat.ru [7].

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

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

Запасы  поставщиков: 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