Задачи ЛП и методы их решения

можно трактовать, как цену единицы продукции у поставщика, а v j = ui' + cij (см. (Y2))

как цену единицы продукции у потребителя, которая возросла на цену перевозки. Условие (Y1)

vj ≤ ui' + cij

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

Так как заполненных клеток в таблице (m+n-1) штук, а неизвестных и (m+n) штук, то для их определения имеется система из (m+n-1) уравнений относительно (m+n) неизвестных. Чтобы найти решение (хотя бы какое-нибудь) такой системы, достаточно положить одно из неизвестных (произвольное) равным некоторому произвольно выбранному числу. Тогда остальные определяются единственным образом. Можно решать эту систему непосредственно (продолжаем работать с нашим “старым” примером и найдем потенциалы для начального плана, построенного способом МС).

Заполненные клетки Уравнения

53

1.Ни одна перевозка на цикле не может стать отрицательной (а такими могут стать перевозки только в клетках, отмеченных знаком (-)).

2.Число заполненных клеток должно оставаться равным m+n-1 . (С учетом того, что клетка, где нарушалась оптимальность, станет заполненной, это условие означает, что одна из ранее заполненных клеток цикла должна стать незаполненной, т.е. не иметь положительной перевозки. Опять же кандидатами в такие клетки могут быть только отрицательные клетки цикла).

Вышеприведенные условия позволяют записать правило выбора θ .

θ = min {xij , где (i , j) - клетки цикла, отмеченные знаком (-)}

Одна из клеток (i*, j*), где достигается этот минимум и станет незаполненной. Для нашего примера имеем

θ= min {x32 ,x13 , где (3 ,2),(1 , 3) - отрицательные клетки цикла}= min{50 , 10}=10

а). Если в качестве θ взять величину, большую 10, то перевозка в клетке (1,3) станет отрицательной (10- θ) и нарушится условие 1.

б). Если же взять меньше 10, то нарушится условие 2, так как число заполненных клеток в таблице увеличится и станет равным m+n=6 (так как 10- θ >0 в этом случае!)

И, наконец, переход к новому плану перевозок завершается изменением перевозок по циклу. (В положительных клетках цикла перевозка увеличивается на θ , в отрицательных на столько же уменьшается, в остальных клетках таблицы не изменяются).

Для нашего примера:

x33 = 0 + 10 =10

x32 = 50 −10 = 40

x12 = 50 + 10 = 60

x13 = 10 − 10 = 0- клетка становится незаполненной,

x11 = 60

55

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

Закончим рассмотрение нашего примера. Имея новый план, переходим к шагу 1 (проверка на оптимальность)

Условия оптимальности выполнены для всех клеток, а значит, последний план перевозок является оптимальным планом (т.е. имеет наименьшие транспортные расходы). Можно проиллюстрировать последний план картинкой (вспоминая, что третий поставщикфиктивный).

Читателю предлагается самостоятельно рассмотреть этот же пример, взяв в качестве начального базисного решения план перевозок, найденный по способу северо-западного угла (СЗУ).

56

4.3. Пример решения классической транспортной задачи

Замечание. Это пример решения транспортной задачи одним студентом – заочником. На мой взгляд, решение излишне подробное. Достаточно было изображать по одной таблице с потенциалами на каждом шаге. А.А.Холопов

Исходные данные (запасы, потребности и цены)

Потребность 170 140 200 195

Транспортная задача является открытой, так как запас груза больше потребностей на 145 единиц. Приведем задачу к закрытому типу - введем фиктивного потребителя B5.

Находим начальный базисный план (он содержит 3+5 –1=7 заполненных клеток). План найден методом минимальной стоимости.

Решаем задачу методом потенциалов.

1-й этап.

Полагая потенциал U1 = 0, определяем остальные потенциалы из соотношения

57

U j + Vi = Ci, j (i = 1..m, j = 1..n),

просматривая все занятые клетки. Потенциалы:

U1 = 0,

V2 = C1,2 − U1 = 14,

V3 = C1,3 − U1 = 16,

V5 = C1,5 − U1 = 0,

U2 = C3,2 − V3 = 10,

U3 = C3,3 − V3 = 15,

V1 = C2,1 − U 2 = 9,

V4 = C3,4 − U3 = 24.

Определяем значения оценок, для всех свободных клеток:

Выделенные оценки не являются оптимальными, а именно:

Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус".

58

Новый план грузоперевозок

Стоимость перевозок при этом = 16295.

Значение стоимости перевозок изменилось на 1575 единиц, по сравнению с предыдущей стоимостью.

2 этап.

Полагая потенциал U1 = 0, определяем остальные потенциалы из соотношения

U j + Vi = Ci, j (i = 1..m, j = 1..n),

просматривая все занятые клетки.