Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача — задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования — области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.
Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и вычислительных в планировании перевозок дает большой экономический эффект. Транспортные задачи могут быть решены симплексным методом, однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его получить оптимальное решение.
В зависимости от способа представления условий транспортной задачи она может быть представлена в сетевой (схематичной) или матричной (табличной) форме. Транспортная задача может также решаться с ограничениями и без ограничений.
Математическое моделирование — процесс построения и изучения математических моделей. Все естественные и общественные науки, использующие математический аппарат, по сути занимаются математическим моделированием: заменяют реальный объект его математической моделью и затем изучают последнюю.
1 Постановка транспортной задачи общего вида
Классическая постановка транспортной задачи общего вида такова.
Имеется m пунктов отправления («поставщиков») и n пунктов потребления («потребителей») некоторого одинакового товара. Для каждого пункта определены:
ai -объемы производства iго поставщика, i =1, …, m;
вj -спрос j-гопотребителя, j=1,…, n;
сij — стоимость перевозки одной единицы продукции из пункта Ai- i-го поставщика, в пункт Вj — j-го потребителя.
Для наглядности данные удобно представлять в виде таблицы 1.1, которую называют таблицей стоимостей перевозок.
Таблица 1.1
Потребители Поставщики В1 В2 … В n запасы А1 С11 C 12 C 1n, а 1
А2 С21 C 22 C 2n а2
…
Am Cm 1 Cm 2 Cmn, а m
Потребности в1 в2 в n
Требуется найти план перевозок, при котором бы полностью удовлетворялся спрос всех потребителей, при этом хватало бы запасов поставщиков и суммарные транспортные расходы были бы минимальными.
Под планом перевозок понимают объем перевозок, т. е. количество товара, которое необходимо перевезти от i-го поставщика к j-му потребителю. Для построения математической модели задачи необходимо ввести m • n штук переменных хij, i= 1,…, n, j= 1, …, m, каждая переменная хij обозначает объем перевозок из пункта Ai в пункт Вj. Набор переменных X = {xij} и будет планом, который необходимо найти, исходя из постановки задачи.
