Транспортная задача с ограничениями возможных транспортных средств (стр. 2 из 3)

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

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

(1.7)

i=1,2,…,m, (1.8)

j=1,2,…,n, (1.9)

(1.10)

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

Если обозначиться транспортные возможности между пунктами I и j через dij, то количество груза

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

(1.11)

Тогда ограничения 1.10, 1.11 объединяются, и модель задачи усложняется двусторонними ограничениями на переменные

(1.12)

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

i=1,2,…,m, (1.13)

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

i=1,2,…,n, (1.14)

Существуют различные подходы к решению этой задачи. Рассмотрим наиболее простой из них.

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

Мощность условного поставщика А’_{i -} принимается равный установленной возможности средств, соединяющих пункт и с потребителями j

A’_i=d_{ij (}1.15)

а мощность условного поставщика А’_j - равной разности между заданными в условии задачи мощностью поставщика в пункте I и возможностью средств между I-м и j-м пунктами, т.е.

a’’_i=a_i-d_ij. (1.16)

При этом затраты на поставку грузов из пунктов I’ в пункт j-c_ij принимаются равными действительным расходам c_ij приведенным в условии задачи. В оптимальном решение переменные х_ij могут иметь любое неотрицательное значение от нуля до a’_i, т.е.

(1.17)

В отличие от них переменные х_ij в оптимальном решении непременно должны быть равны нулю, поскольку мощность А’_j характеризует количество в пункте и сверх установленной средств, соединяющих пункты i и j, следовательно это часть груза должна быть направлена не j-му а любому другому потребителю. Для того, чтобы в оптимальном решении обеспечить значение переменных х_ij равно нулю, затраты на поставку груза из пункта i’’ в пункт j принимаются равными М, т. е c_ij=М.

При минимизации целевой функции (1.7) и коэффициентах c_ij=М, в оптимальном решении получим

Отсюда следует, что

X_ij = X_i’j+ X_i’j = X_{ij (}1.18)

Тогда, исходя из условий (1.15), (1.17), получим

Таким образом, объем поставки груза из пункта i в пункт j не превысит установленной способности транспортных средств, обеспечивающих эти пункты.

Если для какой то пары пунктов производства i потребления s транспортные возможности не ограничены, объем поставки груза от поставщика Аi к потребителю B_s определится как сумма значений пары соответствующих переменных:

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

1.6 Решение транспортной задачи с ограниченными возможностями транспортных средств венгерским методом

Предварительный этап. По исходной матрице С выполняется построение матрицы С', а затем матрицы Co, по известным правилам.

Выполняется построение начального плана Xo. Построение плана выполняется, сверху-вниз по столбцам матрицы Co начиная с левого, для O матрицы Co, при этом учитывается пропускная возможность коммуникаций.

Разметка. На этапе разметки отмечают символом "+" столбцы с нулевыми невязками и существенные нули матрицы С. Точкой отмечают существенные неполные нули, а двумя точками - полные. Несущественные нули остаются без разметки. С точки зрения коммуникации они являются неполными.

Поисковый этап. Целью поиска является отыскать неполный нуль (без разницы существенный или несущественный), расположенный в строке с полной невязкой. Алгоритм поиска по колонкам известен.

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

Выбирается корректирующий элемент h. Корректирующий элемент получаем как минимальный положительный элемент среди невыделенной части матрицы, либо как минимальный модуль двух выделенных отрицательных элементов, если поисковый этап окончился неудачей в невыделенной части матрицы элементы неположительны, а все дважды выделенные элементы неотрицательны, то задача неразрешима при данных ограничениях на пропускную способность. Прибавляется h к выделенным элементам и вычитается из невыделенных. Если дважды выделенный элемент становится равным нулю, то его выделяют "*"Знак выделения над столбцом снимается.

Расчёт целевой функции.

2. Практическая часть

2.1 Описание алгоритма реализации модели

Определившись с методами, которые мы будем использовать в решении задачи, приступим к непосредственному получению результата. Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ “Метод ограничений”/ Условия транспортной задачи заданы транспортной таблицей (2.1).

Таблица 2.1 - Условие транспортной задачи

ai/ bj		B1	B2	B3	B4
		25	25	15	25
A1	40	10	15	5	5
A2	30	10	12	6	6
A3	30	5	5	3	2

В данном случае Σa_i=100 = Σb_j=100 имеем дело с закрытой моделью транспортной задачи.

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

Рисунок 2.1 - блок-схема подпрограммы проверки на условие баланса.

Происходит начальное вычисление опорного плана.

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

На этапе разметки отмечают символом "+" столбцы с нулевыми невязками и существенные нули матрицы С. Точкой отмечают существенные неполные нули, а двумя точками - полные. Несущественные нули остаются без разметки. С точки зрения коммуникации они являются неполными.

Целью поиска является отыскать неполный нуль (без разницы существенный или несущественный), расположенный в строке с полной невязкой. Алгоритм поиска по колонкам известен.

Элемент который стоит на пересечении выделенной строки и выделенного столбца называется дважды выделенным.

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

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

Прибавляется h к выделенным элементам и вычитается из невыделенных. Если дважды выделенный элемент становится равным нулю, то его выделяют "*"Знак выделения над столбцом снимается.

Рисунок 2.2 - Общий алгоритм вычисления опорного плана

Вычисление невязки.

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