Методы линейного программирования для решения транспортной задачи

6. Методы построения начального опорного решения

6.1 Построение первоначального плана по способу северо-западного угла

В этом случае не обращают внимания на показатели затрат. Начав заполнение с клетки (1.1) - "северо-западного угла" таблицы, ступенями спускаются вниз до клетки (k, l), вычеркивая либо одну строку, либо один сто

лбец. На последнем шаге вычеркиваются последняя (k-я) строка и последний (l-й) столбец. При практическом заполнении таблицы, вычеркивание строк и столбцов производится лишь мысленно.

Когда осуществляется первоначальное распределение поставок, то не ставится цель получить оптимальное распределение. Достижению этой цели служат последующие этапы решения задачи. Они заключаются в переходах к новым распределениям поставок, пока не будет найдено оптимальное распределение поставок. [4]

6.2 Построение первоначального плана по способу минимального элемента

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

Способ минимального элемента учитывает тарифы и потому позволяет найти план, более близкий к оптимальному.

Этот способ заключается в следующем.

1. Располагаем все клетки таблицы в очередь по мере возрастания тарифов, начиная с минимального.

линейное программирование транспортная задача

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

Полученный план будет ациклическим и будет состоять не более чем из k+l-1 компонент. Этот план и принимаем за исходный. Он будет лучше плана, построенного по способу северо-западного угла, и для нахождения оптимума потребуется меньше вычислений. [5]

7. Переход от одного опорного решения к другому

Числа и называют потенциалами. В распределительную таблицу добавляют строку и столбец . Потенциалы и находят из равенства , справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, а остальные потенциалы определяются однозначно. Если известен потенциал , то , если известен потенциал , то .

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

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

Для свободной клетки с строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность и т.д. до тех пор, пока не получим оптимальное решение. [7]

8. Распределительный метод

Распределительный метод решения транспортной задачи отличается от метода потенциалов некоторым изменением вычислительного процесса и иным (по форме) критерием оптимальности.

Алгоритм распределительного метода заключается в следующем.

1. Отыскиваем первоначальный ациклический план, содержащий (k+l-1) компонент (при недостатке компонент дописываем нули).

2. Включаем в набор свободную клетку, строим для нее цикл, означиваем его, приписывая свободной клетке знак плюс, и вычисляем по этим знакам алгебраическую сумму тарифов, стоящих во всех вершинах цикла. Полученное число с его знаком записываем внутри свободной клетки.

3. Проделываем указанную в п.2 операцию для каждой свободной клетки, строя всякий раз свой цикл пересчета. В результате в каждой свободной клетке появится число (положительное, отрицательное или нуль).

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

5. В отрицательной полуцепи того цикла, который соответствует выбранной клетке, отыскиваем наименьшую перевозку и делаем сдвиг по циклу на это число. Находим новый допустимый план.

6. Испытываем этот план на оптимальность, т.е. для каждой свободной клетки строим цикл пересчета и вычисляем алгебраическую сумму тарифов. При неоптимальности плана снова включаем свободную клетку в план и делаем сдвиг по соответствующему циклу. Так продолжаем до тех пор, пока план не будет оптимальным.

Для ручного счета более удобен метод потенциалов. Однако на распределительном методе основаны некоторые другие способы решения задач, что и вызывает необходимость его изучения. [5]

9. Метод потенциалов

Решение транспортной задачи любым способом производится на макете. Макет для применения метода потенциалов имеет следующий вид.

 Скачать реферат