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

Способы построения опорных планов (северо-западного угла, наилучшего тарифа, двойного предпочтения) при решении транспортной задачи.

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

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

Эта постановка задачи обусловливается тем, что эксплуатационные и экономические показатели зависят от состава транспорта.

2.Вторая постановка задачи обусловливается тем, что эффективность использования различного транспорта на одной и той же работе не всегда одинакова. Задачу можно сформулировать так:

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

3. Третью постановку можно определить как задачу прикрепления потребителей к поставщикам.

Это классическая транспортная задача. С неё начиналось математическое программирование. Мы её рассмотрим детально.

В качестве критерия оптимизации чаще других используются следующие:

1.Минимум денежно – материальных затрат на перевозки.

2.Минимум затрат времени на перевозки.

3. Минимум объёма транспортных работ.

4.Минимум приведённых затрат.

Первый критерий – минимум материально - денежных затрат. Этот критерий учитывает эффективность перевозок, используется чаще других. Рассчитывается путём умножения себестоимости перевозок на объемы. Иногда вместо себестоимости, применяют тарифные стоимости, тарифы. Если перевозки выполняются привлечённым транспортом, расчёт ведётся по тарифной сетке на договорной основе. Технически расчёт сводится к умножению тарифа на объём перевозок. Наличие в сельском хозяйстве скоропортящихся грузов иногда требует кратчайших перевозок по времени. Это можно достигнуть минимизировав затраты времени на перевозки.

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

Рассмотрим задачу прикрепления потребителей к поставщикам.

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

Формализуем задачу

m – количество пунктов отправления

Назовем их поставщики

i – номер поставщика.

n – количество пунктов назначения

Назовем их потребители

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

а_i – объем однородного груза i-го поставщика. Назовем его коротко – запас

в_j – объем однородного груза, требуемого j-ому потребителю. Назовем его коротко – спрос

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

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

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

Используя эти формализованные характеристики, составим матрицу перевозок. По строкам размещаются поставщики, по столбцам – потребители. На пересечении строк и столбцов проставляется стоимость доставки единицы груза от i-го поставщика к j-ому потребителю. Здесь же представляется количество доставленного груза.

Таблица 1 ­– Схема матрицы перевозок

Используя данную схему, нетрудно записать математическую модель транспортной задачи в структурной, компактной форме.

Базовая модель транспортной задачи

Из условий видно, что стоимость перевозок можно выразить так:

С=с₁₁х₁₁+…+с_ijx_ij+…c_mnx_mnmin

или более компактно

С (1)

Это целевая функция, она позволяет определить численное значение критерия оптимальности на всех этапах расчетов и в оптимальном плане. Требуется найти минимальное значение целевой функции при условиях:

1. Условие вывоза всего груза от каждого поставщика:

х₁₁+…+х_ij+…x_1n=a₁

x_i1+…+x_ij+…+x_in=a_i

x_m1+…x_mj+…+x_mn=a_m

Или более компактно:

где i = …m; (2)

2. Условие удовлетворения спроса каждого потребителя:

х₁₁+…+х_i1+…x_m1=в₁

x_1j+…+x_ij+…+x_mj=в_j

x_1n+…x_in+…+x_mn=в_n

или более компактно

, где j=1…n (3)

3. Условие равенства запаса и спроса:

а₁+…а_i+…a_m=в₁+…+в_j+…в_n

или более компактно:

(4)

4. Условие неотрицательности переменных:

х_ij0 (5)

Условие (3) является необходимым условием совместности ограничений задачи. В линейном программировании доказывается что:

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

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

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

Возможны два случая:

1. - запас превышает спрос (6)

Модель будет иметь вид:

С=

При условиях:

1. где i = 1…m; (8)

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

2. гдеj=1…n. (9)

Потребности (спрос) каждого потребителя необходимо удовлетворить полностью.

3. - Запас превышает спрос (10)

4. х_ij0 – Условие неотрицательности переменных (11)

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

Его спрос определяют как разность запаса и спроса всех поставщиков и потребителей, то есть

(12)

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

Второй случай.

Спрос превышает запас.

(13)

Модель имеет вид:

С= (14)

При условиях:

1. где i = 1…m; (15)

2. где j = 1…n; (16)

Спрос не всех потребителей будет удовлетворен.

3. - спрос превышает запас, (17)

4. х_ij0 (18)

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

Его запас определяется как разность спроса и запаса всех потребителей и поставщиков.

(19)

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

Пусть l_j – величина ущерба из–за недопоставки единицы груза;

Z_j- неудовлетворенный спрос j^го потребителя.

Тогда целевая функция задачи будет иметь вид:

С (20)

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

Такую задачу называют транспортной с блокировкой перевозок.

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

Пусть: Р_ij – предельное число единиц груза, которое можно перевозить от i – го поставщика к j- тому потребителю, за отведенное условиями задачи время.

Например: поставляются ранние ягоды с Кубани в промышленные северные центры самолетом.

Тогда, вместо условия неотрицательности переменных, вводится следующее ограничение:

0  х_ij  р_ij (21)

Эти условия называют ограничениями по пропускной способности, а задачу – транспортная с ограниченными пропускными способностями.

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

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

Чаще других используют следующие способы:

1. Способ северо-западного угла. Его еще называют диагональным.

Таблица 3 – Матрица перевозок

Не учитывая тарифов с_ij с верхнего левого угла, удовлетворяем потребности, начиная с меньшего числа. Вычитая с большего меньшее, строим план.

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

Число занятых клеток равно m+n– 1=4+5-1=8

Значит план невырожденный.

Этот способ прост, но план строится без учета оценок с_ij и он может оказаться далеким от оптимального.

Так если определить значение целевой функции С=6950 пусть это будут рубли. Если при определении опорного плана учитывать стоимость перевозок (с_ij) то, очевидно, можно построить опорный план ближе к оптимальному.

Способ северо-западного угла удобен при вычислениях на ЭВМ.

2. Способ минимальной стоимости

Его еще называют способом наилучшего тарифа, наилучшей оценки.

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

Таблица 4 – Матрица перевозок

Выбираем наименьший тариф.

Это 1 в клетке А₁- 4. Ее, возможно, загрузить только числом 100. Запас и спрос равны. Первую строку и четвертый столбец исключаем из рассмотрения. В оставшейся таблице наименьший тариф А₂ – 1 равен 2 и А₃ - 5. Заполняем любую из них например А₂ – 1 поставка 200 и исключим столбец 1.

В А₃5 записываем меньшее из 250 и 200 это 200 и исключаем строку А₃. И так далее получим план.

х₁₄ =100; х₂₁=200; х₂₂ =50; х₃₅=200

х₄₂=150; х₄₃=100; х₄₅=50.

Остальные значения переменных равны нулю.

План не содержит циклов и состоит из семи положительных перевозок, следовательно, является вырожденным.

m+n-1=8, а у нас 7.

Определим значение целевой функции

С=4300 руб.

3.Способ двойного предпочтения

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

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

Применим этот способ в той же задаче. Сначала заполняем клетки А₂ 1; А₁4; А₃5 затем клетку А₄2.

В оставшейся части таблицы последовательно заполняем клетки по минимальной стоимости А₂₃, А₄₃, А₄₅.

План, полученный в таблице 4, - вырожденный опорный план.

С = 4250 руб.

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

Таблица 5 – Матрица перевозок

4. Иногда удобно построить свой опорный план методом аппроксимации. Мы рассмотрели способы построения опорного плана.

БИЛЕТ №29

Дата добавления: 2015-12-08