Контакты

город Санкт-Петербург
E-Mail:______ @znanieonline.ru
телефон: +7 (000) 000 00 00

 

 

Внимание!

Все зависит от Вас

Автоматизированные системы управления. Матрицы

Применение экономико-математических методов.

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

Алгоритм решения матрицы:               

1. Первоначальное закрепление потребителей за поставщиками.

Трудоемкость решения транспортных задач методом потенциалов значительно сокращается, если первоначальное распределение будет ближе к оптимальному. Поэтому предложен ряд способов наилучшего построения первоначального распределения. Одним из них является способ двойного предпочтения.
Вначале выбирают и отмечают наименьшие расстояния в каждой строке. Затем то же самое делают по столбцам.
Клетку, имеющую две отметки, загружают, т.е. делают туда запись количества груза в первую очередь.
Затем загружают клетки, отмеченные один раз. Нераспределенный груз записывают в неотмеченные клетки, расположенные на пересечении строк и столбцов, в которых еще не хватает загрузки.
Количество груза, помещаемого в каждую клетку, определяется наличием груза груза у соответствующего поставщика или потребностью в грузе соответствующего потребителя.
              
Правило 1. Количество загруженных клеток в матрице равно:
m + n - 1
где: m - количество поставщиков;
n - количество потребителей,
 
Правило 2.  Количество груза, которое записывается в клетки каждой строки, в сумме должно быть равно потребности в грузе каждого потребителя, а количество груза, которое записывается в клетки каждого столбца, в сумме должно быть равно наличию груза у каждого поставщика.

2. Проверка оптимальности полученного распределения.

Для проверки оптимальности полученного первоначального распределения находят специальные вспомогательные показатели для столбцов U и строк V, называемые потенциалами (коэффициентами). Для каждой загруженной клетки сумма соответствующих этой клетке потенциалов (коэффициентов) должна быть равна расстоянию, указанному в этой клетке, то есть:
V + U = C
где  V - потенциал (коэффициент) для строк,
U - потенциал (коэффициент) для столбцов,
С - расстояние между соответствующими грузоотправителями и грузополучателями.
 
В соответствии с этим все потенциалы (коэффициенты) определяются по следующему правилу:
Для одной из строк (грузополучателей) принимают потенциал (коэффициент) равным 0. Остальные потенциалы (коэффициенты) определяются по загруженным клеткам исходя из следующих формул:
для строк V = C - U
для столбцов U = C - V
т.е каждый раз уже найденный потенциал (коэффициент) отнимается от расстояния.

Правило 3. Если число загруженных клеток меньше m + n - 1, то необходимо искусственно загрузить недостающее количество клеток матрицы, для чего в них записывают 0.
В последующих расчетах с этой клеткой оперируют, как с загруженной.
Нуль следует ставить в ту клетку, которая лежит на пересечении строки или столбца, не имеющих потенциала (коэффициента), со строкой или столбцом, для которых потенциалы (коэффициенты) уже определены.
 
Необходимо заметить, что в некоторых случаях после получения первоначального распределения потенциалы (коэффициенты) той или иной строки или столбца могут определяться неоднозначно. Неоднозначное определение потенциала (коэффициента) возникает в тех случаях, когда в матрице число загруженных клеток больше, чем m + n - 1, или при неправильном расположении загруженных клеток в матрице.
 

 

После определения всех потенциалов (коэффициентов) рассматриваются все незагруженные клетки и среди них отыскиваются такие, для которых сумма соответствующих им потенциалов (коэффициентов) будет больше расстояния, указанного в этой клетке (то есть потенциальные клетки).
 
Правило 4. Потенциальной является клетка, для которой сумма соответствующих ей потенциалов (коэффициентов) будет больше расстояния, указанного в этой клетке, т.е. V+U>C
Для каждой такой клетки определяется число d=V+U-C
Наличие таких клеток показывает, что данное распределение не является оптимальным и его можно улучшить, т.е. можно найти более лучший план перевозок.

3. Улучшение полученного распределения

Чтобы улучшить полученный план перевозок, находят клетку с максимальным числом d и для этой клетки строят так называемый контур.

 
Здесь контур строится для клетки А1Б1.

Контур строят следующим образом. От выбранной клетки проводят прямую линию по строке или столбцу до загруженной клетки, которой в свою очередь должна соответствовать еще одна загруженная клетка под прямым углом. И так до тех пор, пока линия не замкнется в исходной клетке. Движение при определении контура совершается строго под прямым углом, причем в каждой строке или столбце, которые находятся в замкнутой линии, в состав контура входят всегда по две клетки.
Вид контура может быть весьма разнообразным:
Следует иметь в виду, что число вершин контура всегда будет четным, при этом те клетки, где горизонтальные и вертикальные линии только пересекаются, нельзя рассматривать как его вершины. Вершиной контура является лишь та загруженная клетка, где эти линии образуют один прямой угол.
Затем всем вершинам контура попеременно присваиваются знаки " - " и " + ", начиная с выбранной для начала построения контура клетки, которой присваивается знак " - ".
 

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

Их отсутствие показывает, что улучшить распределение нельзя, оно является оптимальным, т.е. получено окончательное распределение.