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

Решение транспортной задачи.

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

Условие задачи.

Известно количество однородного груза Q в тонах у поставщиков, условно обозначенных, А 1, А 2, А 3, А 4. Этот груз необходимо доставить потребителям, условно обозначенным Б 1, Б 2, Б 3, Б 4, Б 5, Б 6, Б 7. Известны расстояния между всеми поставщиками и потребителями С 11, С 12 и т. д. Необходимо закрепить потребителей за поставщиками таким образом, чтобы транспортная работа была минимальной.

Необходимо решить матрицу 4 X 7 (4 потребителя и 7 поставщиков или наоборот), объем перевозок:

Q = Nгр. + 10 X n. сп (т).

Q=215+10*10=315(т).

С 11 = n сп.

С 23 =n сп. + 2.

С 34 =n сп. + 1.

С 47 =n сп. + 5.

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

А 1Б 1=10 А 2Б 1=9 А 3Б 1=20 А 4Б 1=16.

А 1Б 2=12 А 2Б 2=7 А 3Б 2=14 А 4Б 2=18.

А 1Б 3=25 А 2Б 3=12 А 3Б 3=7 А 4Б 3=25.

А 1Б 4=11 А 2Б 4=14 А 3Б 4=11 А 4Б 4=11.

А 1Б 5=17 А 2Б 5=10 А 3Б 5=7 А 4Б 5=17.

А 1Б 6=14 А 2Б 6=25 А 3Б 6=18 А 4Б 6=8.

А 1Б 7=21 А 2Б 7=21 А 3Б 7=9 А 4Б 7=15.

Транспортная схема в масштабе 1см=2км Делаем первоначальное закрепление потребителей за поставщиками методом двойного предпочтения. Вначале выбираем и отмечаем наименьшее расстояние в каждой строке, затем то же самое делаем по столбцам. Клетки, имеющие две отметки, загружают в первую очередь, затем загружают клетки, отмеченные один раз, нераспределённый груз записывают в неотмеченные клетки расположенные на пересечении неудовлетворённой строки и столбца.

После того как указанным способом весь груз будет распределён, считаем транспортную работу.

Таблица 1.

P=?qi*ci.

P1=50*10+35*7+25*12+35*7+30*11+35*7+45*8+55*21+5*15=3455 (т*км).

Для уменьшения трудоёмкости дальнейшего решения целесообразно рассмотреть возможность перемещения загрузки в клетки с меньшим расстоянием. Это достигается в том случае если можно компенсировать такую передвижку из одной клетки данной строки в другую, соответствующей передвижкой груза по другой строке. Рассмотрим возможность перемещения груза из клетки, А 2Б 3 в клетку, А 3Б 3. Такое перемещение можно компенсировать передвижкой загрузки из клетки, А 3Б 5 в клетку, А 2Б 5.

Выигрыш 12−7=5.

Проигрыш 7−10=-3.

Итог 5−3=2 км Новое распределение записываем в таблицу 2.

Таблица 2.

Рассмотрим возможность улучшения первоначального распределения по столбцам. Есть возможность переместить груз из клетки, А 2Б 7 в клетку, А 2Б 3, такое перемещение можно компенсировать передвижкой загрузки из клетки, А 3Б 3 в клетку, А 3Б 7.

Выигрыш 21−12=9.

Проигрыш 7−9=-2.

Итог 9−2=7.

Новое распределение записываем в таблицу 3.

Таблица 3.

Рассчитаем транспортную работу:

P2=50*10+35*7+55*12+5*7+30*11+25*10+10*7+45*8+55*9+5*15=3020 т*км.

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

v-u=c.

v=u+c.

u=v-c.

Для начала расчёта потенциалов используем следующее правило: среди загруженных клеток выберем клетку с наибольшим расстоянием. В нашем случае это клетка, А 4Б 7. Потенциал столбца в котором находится эта клетка приравняем к нулю.

u4=0.

v7=0+15=15.

v6=0+8=8.

u3=15−9=6.

v3=6+7=13.

u2=13−12=1.

v5=1+10=11.

v2=1+7=8.

Потенциалы u1, v1, v4 остались ненайденными, это произошло потому, что матрица недозагружена. Число загруженных клеток матрицы:

s=n+m-1,.

n — число основных столбцов.

m — число основных строк.