Методы построения опорного решения транспортной задачи ЛП

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

Решение задач ТЗЛП включает 2 основных этапа построение опорного решения (начального плана перевозок) и построение оптимального решения.

Построение опорного решения. Оно может быть получено методами северо-западного угла, наименьших стоимостей и двойного предпочтения. Наиболее простым и легко формализуемым является метод северо-западного угла, однако он даёт обычно решение, далёкое от оптимального. При построении опорного решения методами наименьших стоимостей и двойного предпочтения анализируется матрица затрат и начальный план обычно близок к оптимальному. Метод с-з угла используется, как правило, при расчётах на ПК. При его применении данные о стоимостях не нужны.