Теорема. Литература, которая использована лектором для подготовки лекции

М Е Т О Д П О Т Е Н Ц И А Л О В

Литература, которая использована лектором для подготовки лекции.

- основна література:

1.Чеботарьова В.Д., Майданник В.Г. Пропедевтична педіатрія. - К., 1999. - 578 с.

2. Мазурин А.В., Воронцов И.В. Пропедевтика детских болезней.- СПб.: Фолиант, 1999. - 928 с.

- додаткова література:

3.Игнатов С.И. Руководство по клиническому исследованию ребенка (с элементами семиотики и диагностики).- М.: Медицина, 1978.-328 с.

4. Майданник В.Г., Чеботарьова В.Д., Дадакіна М.А. та ін. Клінічне обстеження органів та систем у дітей.-К., 1993.- Ч. 1.-148 с.

5. Майданік В.Г. Лекції з пропедевтичної педіатрії, Київ, І995 с.

Лекцию составила доцент Никитина Н.А.

Этот метод позволяет вычислять цены циклов γ_ij без построения самих циклов.

Если план транспортной задачи является оптимальным, то ему соответствует система из m+n чисел α_i и β_j, удовлетворяющих условиям:

α_i + β_j = c_ij для x_ij > 0,

α_i + β_j ≤ c_ij для x_ij = 0; i = 1, m, j = 1, n.

Числа α_i и β_j называются потенциалами соответственно поставщиков и потребителей.

На основании теоремы для того чтобы опорный план был оптимальным, необходимо выполнение следующих условий:

а) для каждой базисной клетки сумма потенциалов должна быть равна стоимости перевозки единицы груза, стоящей в этой клетке:

α_i + β_j = c_ij; (1)

б) для каждой свободной клетки сумма потенциалов должна быть меньше или равна стоимости перевозки единицы груза, стоящей в этой клетке:

α_i + β_j ≤ c_ij. (2)

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

Алгоритм метода потенциалов.

1. Построение системы потенциалов.

Для построения системы потенциалов используют условие α_i + β_j = c_ij, где c_ij - стоимость перевозки единицы груза.

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

Пусть известен потенциал α_i, тогда из равенства (1) следует, что β_j = c_ij - α_i.

Если известен потенциал β_j, то из того же равенства имеем: α_i = c_ij - β_j.

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

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

3. Выбор клетки, в которую необходимо послать перевозку.

Загрузке подлежит та свободная клетка, которой соответствует наибольшая по модулю отрицательная цена цикла γ_ij.

При вычислении цены цикла пользуются тем свойством, что для любой свободной клетки γ_ij = c_ij - (α_i + β_j).

4. Построение цикла и определение количества единиц груза, которое можно перенести по циклу.

Находят min{ x_ij }, где x_ij – перевозки, стоящие в вершинах цикла, отмеченных знаком ‘ - ‘.

Величина min{ x_ij } определяет, сколько единиц груза можно перенести по циклу. Это значение записывают в свободную клетку, отмеченную знаком ‘ + ‘, двигаясь по циклу, вычитают это значение из объёмов перевозок, расположенных в клетках, которые отмечены знаком ‘ - ‘, и прибавляют к объёмам перевозок, находящихся в клетках, отмеченных знаком ‘ + ‘.

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

Для нового опорного плана нужно построить свою систему потенциалов и проверить выполнение условия оптимальности для каждой свободной клетки. Если полученный план окажется неоптимальным, то следует выполнить действия, приведённые в пп.3 и 4.

Процесс повторяют до тех пор, пока все свободные клетки не будут удовлетворять условию (2).