Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии 


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




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

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

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

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

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

.

Затраты на перевозку из Ai в пункт Bj, равны сij.

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

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

,

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

, i=1, ..., m;

, j = 1, ..., n;

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

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

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

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

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



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

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

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

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

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

 





Рекомендуемые страницы:


Читайте также:



Последнее изменение этой страницы: 2016-05-30; Просмотров: 152; Нарушение авторского права страницы


lektsia.com 2007 - 2021 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.014 с.) Главная | Обратная связь