Методы линейного программирования для решения транспортной задачи

при этом контролируются и потенциалы. [5]

12. Транспортная задача с ограничениями на пропускную способность

Транспортная задача с ограниченными пропускными спосо6ностями коммуникаций решается с дополнительным ограничением: , где dij - пропускная способность звена (i, j) в единицу времени. Ма

тематическая модель задачи такова:

,

при ограничениях

Эта задача разрешима при выполнении условий

.

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

[8]

13. Транспортная задача по критерию времени

Кроме транспортной задачи по критерию стоимости существует задача транспортного типа по критерию времени. Постановка такой задачи состоит в следующем.

Дана матрица времени (tij) kl, где tij - время на перевозку груза из i-того пункта отправления в j-тый пункт назначения. Матрица перевозок грузов (xij) kl, где xij - количество перевозимого груза из i-того пункта отправления в j-тый пункт назначения. Известно также наличие груза Mi и спрос на него Nj, . Требуется определить такой план перевозок, при котором весь груз будет доставлен потребителям в кратчайший срок.

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

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

Исходный опорный план можно получить по правилам "северо-западного угла", "минимального элемента", приближенным методом. Далее просматриваем все занятые клетки и в них выбираем максимальное время t, за которое осуществляется опорный план перевозок, т.е. Т=max (tij), где клетки (i; k) занятые. Каждому плану перевозок будет соответствовать вполне определенное значение Т, зависящее от плана, т.е. T=f (x). Следовательно, нужно найти такой план доставки груза потребителям, для которого Т будет минимальным.

Определив максимальное значение Т для исходного плана, просматриваем ту клетку, для которой t=Т=max (tij). Например, такой клеткой является (p, q). Для этой клетки строится цикл, который включает в себя занятые и свободные клетки. Таких циклов может быть несколько. Однако при построении его следует учесть условия. Занятая клетка (p, q), для которой tiq = Т будет нечетной, следующая клетка по часовой или против часовой стрелки - четная, следующая - нечетная и т.д. Цикл состоит из двух полуциклов - четного и нечетного. Для нечетных клеток цикла обязательно должна быть загрузка больше нуля, а для четных - время меньше Т. Свободные клетки, для которых время tij> Т, прочеркиваются и в расчет не принимаются.

Построив цикл для разгрузочной клетки (p, q), для которой t (p, q) = Т, определяем наименьшую загрузку в нечетных клетках цикла. Полученное количество груза вычитается из грузов нечетных клеток и добавляется к числам четных клеток цикла. При этом может оказаться, что после смещения по циклу клетка (p, q) не разгрузится, тогда снова строится цикл и производится разгрузка клетки до тех пор, пока количество груза не станет равным нулю. После разгрузки клетки, имеющей максимальный промежуток времени, получаем новый план перевозок, для которого отыскивается разгрузочная клетка и снова производится процедура построения цикла и смещения груза по циклу. Процесс продолжается до тех пор, покуда можно будет строить разгрузочные циклы. В случае невозможности построить такой цикл в полученных занятых клетках плана выбираем максимальное время, которое и будет искомым по реализации оптимального плана. [9]

14. Применение транспортной задачи для решения экономических задач

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

Кроме того, следует учитывать, что экономико-математическая модель транспортной задачи позволяет описывать множество ситуаций, весьма далеких от проблемы перевозок, в частности, находить оптимальное размещение заказов на производство изделий с разной себестоимостью. [2]

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

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

2. Оптимальные назначения или проблема выбора. Имеется k механизмов, которые могут выполнять l различных работ с производительностью aij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности.

3. Задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции.

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

5. Решение задач с помощью метода запрещения перевозок. Используется в том случае, если груз от некоторого поставщика по каким-то причинам не может быть направлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости. [7]

Заключение

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

 Скачать реферат