Моделирование процессов перевозок и назначения

Простейшие модели

 

Одним из распространённых процессов, при математическом моделировании которых с успехом используется транспортная задача и её модификации, является процесс перевозки и распределения продукции, сырья, трудовых и материальных ресурсов. Другими словами, речь идёт о моделировании процессов перевозки продукции с m пунктов производства в n пунктов потребления так, чтобы при этом был выполнен баланс производства и потребления и затрачены минимальные средства на транспортировку.

Математически этот процесс может быть описан следующим образом:

 

(1)

(2)

 

(3)

 

(4)

 

Здесь a_i – объём запасов i -го продукта на складах (или в пунктах производства), a_i >0;

b_j – объём потребления j -го объекта, b_j >0;

x_ij – количество продукции, перевозимое с i -го склада j -му потребителю;

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

Отметим, что задача (1) – (4) является сбалансированной, если:

Если последнее условие не выполняется, причём объём потребления превосходит объём запасов, то ограничение (2) записывается в виде:

Если же предложение превосходит потребление, то ограничение (1) записывается в виде:

Нередко появляются дополнительные требования на пропускную возможность коммуникации, в этом случае появляется дополнительное ограничение:

, (5)

где d_ij – пропускная способность пути от i -го поставщика к j -му потребителю.

Простой модификацией данной модели является модель процесса назначения. Речь идёт о назначении m различных специалистов на n мест работы при условии, что каждую работу должен выполнять лишь один специалист, и каждый специалист должен выполнять лишь одну работу. Приоритетная возможность i -го специалиста на получение j -й работы оценивается коэффициентами c_ij матрицы С. При моделировании таких процессов x_ij вводится как булевская переменная

 

Ограничения в этом случае записываются в виде:

или

,

в случае если m > n, т.е. специалистов больше, чем мест работы.

Функция цели имеет вид:

 

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

Где c_j – затраты производства единицы продукции у j -го производителя;

x_j – объём производства j -го производителя;

– верхняя и нижняя границы для выпуска продукции;

c_ij – затраты на транспортировку ед. продукции от j -го производителя к i -му потребителю;

x_ij – количество продукции, перевозимой от j -го производителя к i -му потребителю;

a_i – потребности i -го заказчика.

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

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

Введём обозначения:

q – номер варианта развития сети, Q – число всех вариантов развития сети;

g – вид груза, G – число всех видов груза;

i, j – пункты, между которыми осуществляется перевозка;

s – вид лимитированного ресурса; S – число всех видов лимитированных ресурсов;

R_sij – количество выделенных ресурсов s -го вида для развития транспортного участка между пунктами i и j;

– потребность в s -м виде ресурсов для перевозки g -го вида грузов по участку i, j согласно q -му варианту развития сети;

– текущие затраты на перевозку g -го вида груза из пункта i в пункт j согласно q -му варианту развития сети;

K_ij – выделенные капитальные вложения для развития участка сети от пункта i к пункту j;

– капитальные вложения, выделенные согласно q -му варианту развития сети для перевозки g -го груза от пункта i к пункту j;

E – нормативный коэффициент эффективности капитальных вложений в транспорт;

a_ij – пропускная способность участка I, j;

– план перевозок g -го вида продукции, перевозимого от пункта I к пункту j согласно q -му варианту;

– искомая величина, равная 1, если на участке от пункта I к пункту j выбирается q -й вариант развития сети по перевозкам g -го вида груза, и равная 0 в противном случае.

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

­– минимизация приведённых затрат;

– выбирается лишь один вариант развития;

– ограничение на объёмы выделенных ресурсов;

– ограничение на объёмы капитальных вложений;

– ограничение на план перевозок

 

 

Данная задача решается методами целочисленного програм-мирования.