Общие сведения по траспотным задачам

Стр 1 из 2Следующая ⇒

Математическое программирование – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Методы математического программирования широко используются для оптимизации при решении так называемых распределительных задач, к которым относятся и транспортные задачи (ТЗ). Распределительные задачи возникают в случае, когда имеющихся в наличии ресурсов не хватает для выполнения каждой из намеченных работ эффективным образом и необходимо наилучшим образом распределить ресурсы по работам в соответствии с выбранным критерием оптимальности.

Развитие сложных систем зависит от множества факторов (параметров), следовательно, оптимальное значение зависит от множества параметров. Выражением такой зависимости является целевая функция (ЦФ).

Критерием оптимальности могут быть различные параметры. Например, при решении транспортных задач, критерием оптимальности могут служить минимум затрат (времени, пробега), максимальная выручка или объем транспортных работ и т.п.

Классические транспортные задачи обычно решаются на основе линейного программирования (ЛП), которая является наиболее простым и лучше всего изученным разделом математического программирования. Линейное программирование - это раздел математического программирования, посвященный нахождению экстремума линейных функций нескольких переменных при дополнительных линейных ограничениях, которые налагаются на переменные. Методы, с помощью которых решаются задачи, подразделяются на универсальные (например, симплексный метод) и специальные. С помощью универсальных методов решаются любые задачи линейного программирования.

Классическая ТЗ - это задача о наиболее рациональном плане перевозок однородного продукта из пунктов производства в пункты потребления. Пусть имеется m пунктов производства некоего однородного продукта A₁, …, Ai, …, Am и n пунктов его потребления B₁, …, Bj, …, Bn. В пункте Ai (i = 1, …, m) производится ai единиц, а в пункте Bj (j = 1, …, n) потребляется bj единиц продукта. Предполагается, что

Затраты на перевозку из A_i в пункт B_j, равны с_ij.

Суть ТЗ состоит в составлении оптимального плана перевозок, минимизирующего суммарные транспортные издержки, при реализации которого запросы всех пунктов потребления Bj были бы удовлетворены за счёт производства продукта в пунктах Ai.

Пусть x_ij — количество продукта, перевозимого из пункта Ai в пункт Bj. Тогда ТЗ формулируется так: определить значения переменных x_ij, минимизирующих целевую функцию - суммарные транспортные издержки:

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

, i=1, ..., m;

, j = 1, ..., n;

, i=1, ..., m; j = 1, ..., n.

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

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

Если целевая функция нелинейная, то она имеет экстремумы, которые находятся специальными математическими методами.

В настоящее время разработано множество различных алгоритмов решения ТЗ: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, способ двойного предпочтения, различные сетевые методы. Они относительно просты, по ним составлены десятки программ для ЭВМ. Во многих снабженческих, транспортных и других организациях во всем мире с их помощью рассчитываются маршруты доставки материалов на строительные площадки, планы длительного прикрепления поставщиков металлопроката к потребителям, планы перевозок топлива. Такие задачи часто усложняются разного рода дополнительными условиями, например, в них включается расчет не только себестоимости перевозок, но и себестоимости производства продукции (производственно-транспортная задача), оптимизируется совместно доставка взаимозаменяемых видов продукции (скажем, различных кровельных материалов), оптимизируется доставка грузов с промежуточными базами (складами). Кроме того, следует учитывать, что экономико-математическая модель ТЗ позволяет описывать множество ситуаций, весьма далеких от проблемы перевозок, в частности, находить оптимальное размещение заказов на производство изделий с разной себестоимостью.

Решение задач оптимизации может быть автоматизировано с помощью надстройки «Поиск решения» в электронных таблицах MS Excel.Задачи, которые лучше всего решаются данным средством, имеют три свойства:

- имеется единственная оптимизируемая цель;

- имеются ограничения, выражающиеся, как правило, в виде неравенств;

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

Формулировка таких задач представляет собой систему уравнений с несколькими неизвестными и набор ограничений на решения, поэтому решение задачи необходимо начинать с построения соответствующей модели (экранной формы).

12 Следующая ⇒