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

Метод разработан в 1940 г. академиком Л. В. Конторовичем. В 1951 г. американским ученым Дж. Б. Данцигом предложен распределительный метод (МОДИ), аналогичный методу потенциалов. В обоих методах при проверке допустимого плана на оптимальность определяются потенциалы (числа), с помощью которых вычисляются характеристики клеток без кружков (в них нет поставок).

Обозначив потенциалы строк через U_i, потенциалы столбцов через V_j, показатели C_ij в клетках с поставками и кружками через , характеристики клеток без кружков (без поставок) через E_ij. получим следующие соотношения::

метод потенциалов метод МОДИ

u_i = v_j – ; (8.10) u_i = – v_j;

v_j = + u_i; (8.11) v_j = – u_i;

= v_j – u_i; (8.12) = v_j + u_i;

E_ij = c_ij – (v_j – u_i); (8.13) E_ij = c_ij – (v_j + u_i).

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

Рассмотрим пример решения транспортной задачи, предложенный В. С. Михеевой (1981). Базисный допустимый план составлен способом наименьшего элемента в столбце, его первоначальный функционал 555 (табл. 8.4).

Вначале рассчитаем потенциалы строк и столбцов по методу потенциалов с использованием формул. Произвольно выбранную величину потенциала выбирает в том столбце или строке, где наибольшее количество клеток с кружками. В нашем примере – это третья строка. В качестве потенциала для нее возьмем число 0. По формуле (8.11) определяем потенциалы (v_j) первого (v_j = + u_i = 0 + 2 = 2), третьего (0 + 6 = 6), четвертого (0 + 4 = 4), пятого (0 + 2 = 2) столбцов. Зная потенциалы по четырем столбцам, можно вычислить потенциалы строк (u_i) по формуле (8.10): первой (u_i = v_j – = 2 – 1 = 1), четвертой (6 – 2 = 4). По полученным потенциалам новых строк вычисляем потенциалы новых столбов, а по ним – новых строк (см. табл. 8.4).

Определив потенциалы строк и столбцов, вычисляют характеристики клеток (E_ij) без кружков (в них нет поставок) по формуле (8.13). Приведем расчет характеристики клетки 1.2: E_ij = c_ij – (v_j – u_i) = 2 – (7 – 1) = – 4. Аналогично рассчитываем E_ij (показаны курсивом) для других клеток без кружков.

отрицательные величины получены в клетках матрицы 1.2, 1.3, 3.2 (их величины соответственно: – 4, –2, –2), поэтому составленный первичный базовый план не оптимален. Проводят следующее перераспределение поставок по правилам цепи.

Выбираем клетку с наибольшей отрицательной абсолютной величиной характеристики (E₁₂) равную – 4. К клетке 1.2 строится цепь по перемещению наименьшей поставки 5 из клетки 3.3, так как функционал стремится к минимуму. Путь перемещения следующий: 3.3 (–5)4.3 (+5)4.2 (–5)1.2 (+5)1.1 (–5)3.1 (+5)3.3. К имеющейся поставке в клетке прибавляется или отнимается 5 с целью сохранения баланса между поставщиками и потребителями.

Получаем новую матрицу с измененными поставками (8.5). В ней повторяем алгоритм расчетов, как в табл. 8.4: рассчитываем потенциалы строк и столбцов, характеристику клеток без поставок, производим перераспределение поставок с использованием другой минимальной поставки 25 в клетке 3.4. Другая минимальная поставка 25 в клетке 3.1 перемещаться не может по цепи, так как в свободной клетке 4.4 с максимальной отрицательной абсолютной характеристикой (–3) ее следует вычитать из несуществующей поставки. Поставка 25 в клетке 3.4 перемещается по цепи: 3.4 (–25)3.1 (+25)1.1 (–25)1.2 (+25)4.2 (–25)4.4 (+25)3.4 (цепь замыкается). Расчет потенциалов и характеристики в новой матрице показал, что распределение не оптимально. Получена отрицательная характеристика –1 в клетке 4.5. Следует произвести очередное перераспределение следующей минимальной поставки равной 0 в клетке 1.1. Здесь получена нулевая поставка, так как из прежней поставки в клетке 25 следовало вычесть перераспределяемую 25. В таких ситуациях допускается наличие нулевой поставки, чтобы не нарушались правила перемещения поставки по цепи. Результаты распределения представлены в матрице 3 (табл. 8.6). В ней снизилось отрицательное значение E_ij до –1. План приблизился к оптимальному и требуется его усовершенствовать. Проводим очередное перераспределение поставок. Минимальную нулевую поставку из клетки 1.1 перемещаем в клетку 4.5, где отрицательная характеристика клетки. Прибавление и вычитание нуля по цепи не изменяет величины поставок в клетках и не нарушает правил построения цепи. В новой матрице 4 (табл. 8.7) после перерасчетов v_j, u_i, E_ij получены все положительные характеристики цепи при стремлении функционала к минимуму, поэтому план распределения поставок оптимальный, величина Z = 460. По сравнению с базовым планом функционал снизился на 95 единиц.

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

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

НСР = t_табл ∙ m_d , (1.24)

где m_d – ошибка разницы средних; t_табл – табличное значение критерия Стьюдента при уровне вероятности 0,95 или 0,99 и степени свободы, определяемой экспериментом.

Если разность между сравниваемыми средними в условиях эксперимента больше или равна величине НСР при Р 0,95 или 0,99, то различие сущеcтвенно. Используя предыдущий пример по глубине расчленения рельефа, проверим достоверность разницы между средними арифметическими с использованием критерия НСР для случаев независимого и сопряженного наблюдений по формуле (1.24):

НСР_0,95 = 2,31 ∙ 1,40 = 3,23 м; НСР_0,99 = 3,36 ∙ 1,40 = 4,70 м (для независимых наблюдений);

НСР_0,95 = 3,18 ∙ 0,40 = 1,27 м; НСР_0,99 = 5,84 ∙ 0,40 = 2,33 м (для сопряженных наблюдений.

Разница между средними арифметическими глубины расчленения рельефа при независимых и сопряженных наблюдениях одна и та же (1,4 м). Сравнивая ее с величиной НСР, приходим к тем же выводам. что и при использовании критерия Стъюдента.

33 Критерий Фишера. В выборочных совокупностях дисперсии могут существенно отличаться друг от друга. В таких случаях установление различий между выборочными совокупностями проводится по критерию Фишера (F – положительное асимметричное распределение). Расчет производится по формуле:

F = σ²_{большая}/ σ²_{меньшая} (1.25)

Если величина расчетного критерия Фишера (F_ф) не превышает величины приведенного в таблице (F_т) (прил. 5), то различие между сравниваемыми дисперсиями считается недостоверным. При F_ф > F_т эти дисперсии достоверно различны, как и сравниваемые по ним генеральные совокупности. Степень свободы рассчитывается для сравниваемых выборок отдельно по формуле ν = N – 1.