Условие потенциальности показывает, что
разность потенциалов потребителя и поставщика = стоимости перевозки между ними,
если перевозка осуществляется, и не больше стоимости перевозки при её
отсутствии.
Алгоритм решения транспортной задачи методом
потенциалов состоит из двух этапов: предварительного и общего. Первый включает:
1. построение опорного решения 2. присвоение и расчёт системы потенциалов 3.
проверка первоначального плана на оптимальность. Если опорное решение не
является оптимальным, то переходят ко второму (общему) этапу, который включает:
1. улучшение плана перевозок 2. исправление системы потенциалов 3. проверка
улучшенного плана на оптимальность. Общий шаг циклически выполняется до
получения оптимального плана перевозок.
Алгоритм решения транспортной задачи на сети.
В ряде случаев транспортную задачу целесообразно решать в сетевой постановке,
отличающейся наглядностью. Транспортная сеть это совокупность вершин или узлов
(пункты отправления и приёма грузов, промежуточные пункты) и соединяющих их
транспортных коммуникаций или звеньев. На каждом звене проставляются удельная
стоимость перевозки груза по данному транспортному участку Сij , а при
ограниченности пропускной способности звена также и её максимальное значение
dij. Около каждой вершины в скобках со знаком + или – проставляются объемы
отправления и приёма грузов. Соответственно.
Нахождение оптимального при сетевой постановке
транспортной задачи плана осуществляется методом потенциалов: 1)Строится
опорное решение 2) Для построения системы потенциалов любой вершине
присваивается какой-л потенциал. 3)Проверка плана на оптимальность
осуществляется для всех звеньев без грузопотока. 4) При улучшении плана по
звену, на котором нарушено первое условие оптимальности (разность потенциалов
потребителя и поставки = стоимости перевозки между ними), должна пройти
перевозка; если нарушено 3е условие опт-ти (разность потенциалов потребителя и
поставка должна быть больше стоимости перевозок по звену если по нему
осуществляется перевозка, объёмом равной его пропускной способности), то на
этом звене перевозка должна уменьшаться.
Постановка и решение ТЗ по критерию времени.
Иногда (перевозка возгорающихся полезных
ископаемых, оперативное управление работой транспорта и др.) перевозку грузов
от поставщиков i=1,n до потребителей j=1,m необходимо спланировать и
организовать за минимальное время.
Решение ТЗ задачи по критерию времени
осуществляется в следующем порядке. 1) Методом с-з угла или наименьшего
элемента троится опорное решение ТЗ. 2)Из всех клеток, занятых перевозками, выбирается
наибольшее время. 3) Клетки исходной матрицы, в которых время перевозки
превышает максимальное для допустимого плана, зачёркиваются. 4)Улучшается
допустимый план 5) Улучшение допустимого плана осуществляется до тех пор, пока
полученный план не станет оптимальным
БИЛЕТ 11 ВОПРОС 1 Методика построения
календарного плана и диаграмм потребления рес.
Календ. план строится в соответствии со
спец.формой, совмещающей в себе график и диаграмму потребления ресурсов.
|