ТРАНСПОРТНАЯ ЗАДАЧА ЗАКРЫТОГО ТИПА

МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ

ПРОЦЕССОВ ДЕРЕВООБРАБОТКИ

Методические указания по лабораторному практикуму для студентов

направления 250400 Технология и оборудования лесозаготовительных и деревоперерабатывающих производств»

Часть 2

ЕКАТЕРИНБУРГ

Печатается по рекомендации методической комиссии факультета механической технологии древесины

Протокол № от

Рецензент………..

Редактор……..

Компьютерная верстка………

Редакционно-издательский отдел УГЛТУ

Отдел оперативной полиграфии УГЛТУ

Лабораторный практикум №5

ТРАНСПОРТНАЯ ЗАДАЧА ЗАКРЫТОГО ТИПА

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

Общие сведения

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

Алгоритм решения задачи

Постановка задачи

Изделия, сконцентрированные на n мебельных предприятиях (A₁, А₂,…, А_n), необходимо доставить m в торговых центров (В₁, В₂,…, В_m). Запасы грузов в пунктах отправления составляют соответственно a₁, a₂,…, a_n единиц. Потребности пунктов назначения составляют соответственно b₁, b₂,…, b_m единиц. При этом суммарный запас груза у поставщиков равен сумме потребностей потребителей (т.е. данная задача является закрытой):

(5.1)

Затраты на перевозку единицы груза от i -го поставщика к j -му потребителю известны и равны C_ij ден. ед. Требуется определить оптимальный план перевозок груза, т.е. найти количество груза x_ij, которое необходимо перевезти от каждого поставщика каждому потребителю таким образом, чтобы все запасы были вывезены из пунктов отправления, были удовлетворены потребности в грузе всех пунктов назначения при этом суммарные затраты на все перевозки были минимальны.

Алгоритм решения

Алгоритм решения состоит из следующих действий:

1) записать целевую функцию. Целевая функция транспортной задичи представляет собой сумму затрат на перевозку грузов от каждого поставщика к каждому потребителю. Каждое слагаемое в данной сумме равно произведению количества груза, перевозимого от i -го поставщика к j -му потребителю (x_ij), на стоимость перевозки единицы груза по данному маршруту (C_ij). Количество слагаемых в целевой функции, таким образом, равно сумме количества поставщиков и количества потребителей:

(5.2)

2) записать ограничения. Ограничения транспортной задачи могут быть разделены на две группы. К первой относятся ограничения, которые отражают Условие вывоза всего запаса груза из пунктов отправления. Другими словами, сумма количества груз, которое каждый поставщик отправляет всем потребителям, равна запасу груза на складе данного поставщика:

(5.3)

Количество ограничений первой группы равно количеству поставщиков.

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

(5.4)

Количество ограничений второй группы равно количеству потребителей;

3) записать условие задачи в виде транспортной таблицы (табл.5.1);

4) составить опорный план перевозок, который удовлетворяет всем ограничениям. Опорный план может быть получен двумя способами. Более простой, но и вместе с тем менее эффективный их них носит название метода северо-западного угла. Согласно ему заполнение транспортной таблицы начинается с верхней левой клетки, т.е. сначала определяют количество груза, которое перевозят от первого поставщика к первому потребителю. Как правило, опорное решение, полученное методом северо-западного угла, значительно отличается от оптимального потому, что при его отыскании не учитывается стоимость перевозок. Второй метод принято называть методом наименьшего элемента. По нему заполнение таблицы начинается с клетки, которой соответствует минимальная стоимость перевозки груза;

Таблица 5.1 – Транспортна таблица

5) проверить правильность полученного опорного плана. Сумма количества перевозимого груза в каждом столбце должна равняться потребности потребителя в грузе, соответствующего данному столбцу. Сумма количества перевозимого груза в каждой строке должна равняться запасу груза у поставщика, соответствующего данной строке. Число заполненных клеток таблицы N должно быть равно m+n- 1. Превышение числа N говорит о неправильно заполненной таблице. Если количество заполненных клеток меньше N (такой план называется «вырожденным»), следует набрать недостающее число, заполняя пустые клетки таблицы нулями (создать нулевые перевозки);

6) рассчитать значение целевой функции при опорном плане. Целевая функция рассчитывается по формуле (5.2);

7) определить, является ли найденный опорный план перевозок оптимальным, используя метод потенциалов. Последовательность действий при использовании данного метода следующая:

- каждому поставщику A_i ставится в соответствие потенциал u_i. Каждому потребителю В_j ставится в соответствие потенциал v_j. Для отыскания значения потенциалов решается система уравнений, которая записывается, исходя из данных заполненных клеток. Количество уравнений равно количеству заполненных клеток (т.е. числу N). Каждое уравнение имеет вид:

(5.5)

где u_i. и v_j. – потенциалы поставщика и потребителя соответственно;

C_ij – стоимость перевозки единицы груза;

- для каждой свободной клетки рассчитывают значение δ_ij по формуле:

(5.6)

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

- в таблице отыскивают свободную клетку с максимальным по модулю значением δ_ij. Начиная с этой клетки, строят так называемый «цикл».

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

В построенном цикле последовательно, по часовой стрелке или против нее, помечают вершины чередующимися знаками «+» и «-». Начинают при этом со свободной клетки, которой приписывают знак «+»;

- осуществляют перераспределение груза по циклу. Для этого среди клеток, помеченных знаком «+», отыскивают ту, в которой записано минимальное количество груза. Это значение прибавляют к значениям количества груза в клетках, соответствующих вершинам цикла, которые помечены знаком «+», и отнимаю от количества груза в клетках, помеченных знаком «-»;

Для нового плана, полученного в результате перераспределения груза, вновь рассчитывают значение потенциалов поставщиков и потребителей в заполненных, а затем – значения δ_ij в свободных клетках. Если новый план не является оптимальным (остались отрицательные значения δ_ij в свободных клетках), процедуру переноса груза по циклу повторяют.

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

Пример решения задачи

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

Таблица 5.2 – Исходные данные задачи

Сумма запаса груза у поставщиков:

Сумма потребностей в грузе у потребителей:

Поскольку , транспортная задача является закрытой.

Целевая функция задачи:

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

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

Составим опорный план методом наименьшего элемента. Среди клеток таблицы необходимо найти клетку, которой соответствует наименьшая стоимость перевозки единицы груза. В нашем примере есть две клетки с минимальной стоимостью перевозки, равной 3 ден. ед. (C₂₃ =3 и C₂₄). Начнем с любой из них, например, с клетки 23. Из таблицы видно, что 2-й поставщик имеет на складе 450 единиц груза, однако 3-й потребитель прислал заявку только на 250 единиц. Поэтому в клетку 23 заносим значение x₂₃ =250. На этом потребность 3-го поставщика в грузе полностью удовлетворена, и больше в его столбец ничего заносить не будем. Далее вновь выбираем из оставшихся незаполненных клеток клетку с минимальной стоимостью перевозки. Это клетка 24. У 2-го поставщика на складе осталось 450-25=200 единиц груза, 4-ый потребитель хочет получить 160 единиц. Таким образом, x₂₄ =160. Действуя по данному алгоритму, продолжаем заполнять клетки транспортной таблицы до тех пор, пока все потребности поставщиков не будут удовлетворены, а весь груз со складов не будет вывезен. Составленный методом наименьших элементов план перевозок показан в табл. 5.3.

Проверим, выполняется ли условие по количеству заполненных клеток:

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

Вычисляем значение целевой функции в опорном плане:

ден. ед.

Поставщикам присваиваем потенциалы u₁ u₂ и u₃, потребителям - потенциалы v₁ v₂ v₃ v₄ и v₅. По заполненным клеткам составляем систему уравнений:

Таблица 5.3 – Опорный план. Первая транспортная задача

Принимаем, что u₁ =0. Решая систему уравнений, получаем значения остальных потенциалов, которые заносим в соответствующие графы таблицы (табл. 5.3).

Для незаполненных клеток рассчитываем значение δ_ij по формуле (5.6). Результат расчета записываем в нижнем левом углу соответствующих клеток. Так, например, для клетки 13:

Из табл. 5.3 видно, что в клетке 14 получено отрицательное значение δ_ij =-1. Таким образом, может быть сделан вывод о том, что представленный в табл. 5.3 план перевозок не является оптимальным и перераспределение груза по циклу позволит снизить суммарные затраты на перевозки.

Для перераспределения груза найдем цикл (табл. 5.4). Первая вершина цикла находится в клетке с отрицательным значением δ_ij (клетка 14). Остальные лежат в заполненных клетках 11, 21, 24. Последовательно помечаем вершины цикла чередующимся знаками «+» и «-». При этом начинаем с клетки 14, в которой ставим знак «+». Среди клеток, помечаем знаком «-» (клетки 11 и 24), находим ту, в которой количество груза меньше. Это клетка 11, в ней x₁₁ =10, что меньше, чем x₂₄ =160. Таким образом, по циклу переносим 10 единиц груза. Это число мы прибавляем в клетках со знаком «+» и отнимаем в клетках со знаком «-».

Таблица 5.4 – Вторая транспортная таблица

Постав-щик	Запас груза поставщика	Потребитель	Потенциал поставщика
В1	В2	В3	В4	В5
A1	a1 =420	7 - 10			+		u1 =0
A2	a2 =450	+			-		u2 =-2
А3	a3 =90						u3 =-2
Потребность потребителя в грузе	b1 =50	b2 =400	b3 =250	b4 =160	b5 =100
Потенциал потребителя	v1 =7	v2 =6	v3 =5	v4 =5	v5 =4

Таблица 5.5 – Третья транспортная таблица

Полученные новые значения x_ij заносим в табл. 5.5, причем клетки, в которых не лежали вершины цикла, остаются без изменений. Заново рассчитываются значения потенциалов u_i, v_j и разностей δ_ij. Из таблицы видно, что все значения δ_ij ≥0. Следовательно, план является оптимальным. Значение целевой функции оптимального плана является минимальным возможным значением расходов на перевозки:

ден.ед.

4. Индивидуальные задания

Определить оптимальный план перевозок. Исходные данные для решения задач принять в соответствии с табл. 5.6.

Таблица 5.6 –Исходные данные для решения транспортной задачи

Лабораторный практикум №6

Пример решения задачи

Изделия, сконцентрированные на трех мебельных предприятиях, необходимо доставить в пять торговых центров. Запасы груза в пунктах отправления составляют соответственно 10, 20 и 30 ед. Потребности пунктов назначения составляют соответственно 20, 30, 40, 10 и 20 ед. Затраты на перевозку единицы груза от единицы груза от i -го поставщика к j -му потребителю известны и равны: С₁₁ =2; С₁₂ =4; С₁₃ =6; С₁₄ =8; С₁₅ =1; С₂₁ =5; С₂₂ =9; С₂₃ =2; С₂₄ =10; С₂₅ =7; С₃₁ =8; С₃₂ =9; С₃₃ =6; С₃₄ =7; С₃₅ =5 ден.ед. Требуется определить оптимальный план перевозок груза

Суммарный запас груза у поставщиков составляет:

ед. груза.

Суммарная потребность в грузе у потребителей составляет:

ед. груза.

Таким образом, можно сделать вывод, что мы имеем дело с транспортной задачей открытого типа, в которой потребности потребителей превышают запас груза у поставщиков. Для приведения задачи к закрытому виду вводим фиктивного 4-го поставщика А₄. Объем запаса груза на его складе принимаем равным разности между суммарным объемом заявок потребителей и суммарным запасом грузов поставщиков:

ед. груза.

Стоимости перевозок от фиктивного поставщика А₄ ко всем потребителям равны нулю.

При составлении опорного плана по методу наименьших элементов заполнение транспортной таблицы начинается с клетки, имеющей наименьшую стоимость перевозки. В данном случае это клетки фиктивного поставщика (C_4j=0). Заполнение можно начинать с любой из них. В опорном плане задачи, представленном в табл. 6.1, последовательность заполнения клеток была следующей: 41-42-43-15-23-35-33-34. Количество заполненных клеток соответствует требуемом, т.е. сумме количества поставщиков (включая фиктивного) и потребителей минус 1, т.е.:

Таблица 6.1 – Первая транспортная таблица открытой задачи после

приведения к закрытому виду

Постав-щик	Запас груза поставщика	Потребитель	Потенциал поставщика
В1	В2	В3	В4	В5
A1	a1 =10						u1 =2
A2	a2 =20						u2 =2
А3	a3 =30			+	-		u3 =6
А4	A4 =60			-	-1 +		u4 =0
Потребность потребителя в грузе	b1 =20	b2 =30	b3 =40	b4 =10	b5 =20
Потенциал потребителя	v1 =0	v2 =0	v3 =0	v4 =1	v5 =-1

Значение целевой функции:

ден.ед.

Расчет значений δ_ij в свободных клетках табл. 6.1 показал, что данный опорный план не является оптимальным, так как имеется отрицательное значение δ₄₄ =-1. Переход от опорного плана к оптимальному может быть осуществлен после постарения цикла с вершиной в клетке 44.

По алгоритму решения задачи среди клеток, помеченных знаком «-», мы должны отыскать ту, в которой указано меньшее количество груза. Однако в данном примере ив клетке 34, ив клетке 43 количество груза одинаковы (x₃₄=x₄₃ =10 ед.). По циклу переносим 10 единиц груза. В клетках 33 и 44 это число прибавляем, а в клетках 34 и 43 вычитаем. Однако после перераспределения груза количество заполненных клеток в таблице должно остаться неизменным N =8. Поэтому хотя в клетках 34 и 43 груза после вычитания не остается, одну из них будем продолжать считать заполненной и поставим в нее x =0. Пусть это будет клетка 43, так как по стоимости перевозки она выгоднее, чем клетка 34 (С₄₃ < С₃₄). Новый план перевозок представлен в табл. 6.2.

Таблица 6.2 – Вторая транспортная таблица

Значение целевой функции в новом плане уменьшилось по сравнению с предыдущим:

ден.ед.

Расчет знчений δ_ij в свободных клетках табл. 6.2 показывает, что данный план является оптимальным, так как все δ_ij неотрицательны.

Анализ решения открытой транспортной задачи позволяет определить, кто из потребителей не получит (полностью или же частично) заказанный груз. В нашем примере это потребители В₁, В₂ и В₄. В соответствии с оптимальным планом этих потребителей должен обеспечить грузом 4-ый (фиктивный) поставщик, которого по условию задачи не существует.

Задания для индивидуального решения

Для получения индивидуального задания транспортной задачи открытого типа перепишите задание, соответствующее Вашему варианту, из табл. 5.6 за исключением значения запаса груза у первого поставщика а₁. Значение а₁ примите по табл. 6.3.

Таблица 6.3 – Значение запаса груза у первого поставщика

Лабораторный практикум №7

ЗАДАЧА СЕТЕВОГО ПЛАНИРОВАНИЯ

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

Общие св

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

---

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: