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

Для решения транспортной задачи можно использовать метод потенциалов. Пусть задан опорный план задачи, тогда каждому пункту отправления А_i приписывается некоторое число U_i, а каждому пункту назначения В_j – число V_j. Эти числа называют потенциалами, они подбираются так, чтобы для каждой базисной клетки (i, j) выполнялось равенство

U_i + V_j = C_ij.

Таким образом, получаем m + n – 1 простых уравнений с m + n неизвестными U_i и V_j. В таком случае, когда система состоит из числа уравнений, меньшего, чем число неизвестных, появляется свободная неизвестная величина, которой мы можем придать любое значение. Все остальные неизвестные можно найти из системы уравнений.

После того, как будут найдены все потенциалы U_i и V_j, для каждой свободной клетки (i, j) определяют числа D_ij = C_ij– – (U_i + V_j). Далее поступаем так же, как и в распределительном методе: находим наибольшее по модулю отрицательное число (т.е. самое малое из отрицательных) и делаем сдвиг по соответствующему циклу пересчета. Таким образом, в методе потенциалов для нахождения чисел D_ij не нужно искать циклы пересчета для всех свободных клеток. Надо найти только один цикл пересчета, соответствующий наименьшему отрицательному .

Пример решения задачи методом потенциалов:

	V1 = 5	V2 = 4	V3 = 2	V4 = 1		Для занятых клеток U1 + V1 = 5, U1 + V2 = 4, U2 + V2 = 1, U3 + V2 = 3, U3 + V3 = 1, U4 + V3 = 2, U4 + V4 = 1.
U1 = 0	20 5	10 4	2	5
U2 = -3	6	70 1	1	3
U3 = -1	2 Q	10 3	401	8
U4 = 0	6	3	30 2	70 1

Положим U₁ = 0, тогда учитывая занятые клетки

V₁ = 5, V₂ = 4, U₂ = –3, U₃ = –1, V₃ = 2, U₄ = 0, V₄ = 1.

Подсчитаем D_ij для свободных клеток:

D₁₃ = 2 – (0 + 2) = 0, D₁₄ = 5 – (0 + 1) = 4,

D₂₁ = 6 – (–3 + 5) = 4, D₂₃ = 1 – (–3 + 2) = 2,

D₂₄ = 3 – (–3 + 1) = 5,

D₃₁ = 2 – (–1 + 5) = –2, D₃₄ = 8 – (–1 + 1) = 8,

D₄₁ = 6 – (0 + 5) = 1, D₄₂ = 3 – (0 + 4) = –1.

Поскольку среди значений D_ij есть отрицательные, то план перевозок не оптимален и необходимо, сделав сдвиг по циклу пересчета для клетки (3,1), перейти к новому плану.

	V1 = 5	V2 = 4	V3 = 4	V4 = 3		Для занятых клеток U1 + V1 = 5, U1 + V2 = 4, U2 + V2 = 1, U3 + V1 = 2, U3 + V3 = 1, U4 + V3 = 2, U4 + V4 = 1.
U1 = 0	10 5	20 4	Q2	5
U2 = -3	6	70 1	1	3
U3 = -3	10 2	3	401	8
U4 = -2	6	3	30 2	70 1

Положим U₁ = 0, тогда

V₁ = 5, V₂ = 4, U₂ = –3, U₃ = –3, V₃ = 4, U₄ = –2, V₄ = 3.

Подсчитаем D_ij для свободных клеток:

D₁₃ = 2 – (0 + 4) = –2, D₁₄ = 5 – (0 + 3) = 2,

D₂₁ = 6 – (– 3 + 5) = 4, D₂₃ = 1 – (–3 + 4) = 0,

D₂₄ = 3 – (–3 + 3) = 3,

D₃₂ = 3 – (–3 + 4) = 2, D₃₄ = 8 – (–3 + 3) = 8,

D₄₁ = 6 – (–2 + 5) = 3, D₄₂ = 3 – (–2 + 4) = 1.

Поскольку среди значений D_ij есть отрицательное, то план перевозок не оптимален и необходимо, сделав сдвиг по циклу пересчета для клетки (1,3), перейти к новому плану.

	V1 = 3	V2 = 4	V3 = 2	V4 = 1		Для занятых клеток U1 + V2 = 4, U1 + V3 = 2, U2 + V2 = 1, U3 + V1 = 2, U3 + V3 = 1, U4 + V3 = 2, U4 + V4 = 1.
U1 = 0	5	20 4	10 2	5
U2 = -3	6	70 1	1	3
U3 = -1	20 2	3	301	8
U4 = 0	6	Q 3	30 2	70 1

Положим U₁ = 0, тогда учитывая занятые клетки

V₂ = 4, V₃ = 2, U₂ = –3, U₃ = –1, V₁ = 3, U₄ = 0, V₄ = 1.

Подсчитаем D_ij для свободных клеток:

D₁₁ = 5 – (0 + 3) = 2, D₁₄ = 5 – (0 + 1) = 4,

D₂₁ = 6 – (– 3 + 3) = 6, D₂₃ = 1 – (–3 + 2) = 2,

D₂₄ = 3 – (–3 + 1) = 5,

D₃₂ = 3 – (–1 + 4) = 0, D₃₄ = 8 – (–1 + 1) = 8,

D₄₁ = 6 – (0 + 3) = 3, D₄₂ = 3 – (0 + 4) = –1.

Поскольку среди значений D_ij есть отрицательное, то план перевозок не оптимален и необходимо, сделав сдвиг по циклу пересчета для клетки (4,2), перейти к новому плану.

	V1 = 3	V2 = 4	V3 = 2	V4 = 1		Для занятых клеток U1 + V3 = 2, U2 + V2 = 1, U3 + V1 = 2, U3 + V3 = 1, U4 + V2 = 2, U4 + V3 = 2, U4 + V4 = 1.
U1 = 0	5	4	30 2	5
U2 = -3	6	70 1	1	3
U3 = -1	20 2	3	301	8
U4 = 0	6	20 3	10 2	70 1

Положим U₁ = 0, тогда учитывая занятые клетки

V₃ = 2, U₃ = –1, U₄ = 0, V₁ = 3, V₂ = 4, U₂ = –3, V₄ = 1.

Подсчитаем D_ij для свободных клеток:

D₁₁ = 5 – (0 + 3) = 2, D₁₂ = 4 – (0 + 4) = 0,

D₁₄ = 5 – (0 + 1) = 4,

D₂₁ = 6 – (– 3 + 3) = 6, D₂₃ = 1 – (–3 + 2) = 2,

D₂₄ = 3 – (–3 + 1) = 5,

D₃₂ = 3 – (–1 + 4) = 0, D₃₄ = 8 – (–1 + 1) = 8,

D₄₁ = 6 – (0 + 3) = 3.

Поскольку среди значений D_ij нет отрицательных, то найден оптимальный план перевозок.

f(х) = 30 × 2 + 70 × 1 + 20 × 2 + 30 × 1 + 20 × 3 + 10 × 2 + 70 × 1 = 350.

Решение транспортной задачи методом потенциалов, реализованным в ППП PRIMA показано на рис. 24 и 25.

Рис. 24. Заполнение диалоговой формы Транспортная задача

Рис. 25. Решение транспортной задачи в ППП PRIMA

Рис. 25. Продолжение

Этапы метода потенциалов:

1. Найти первоначальный опорный план. Число заполненных клеток равно m + n – 1.

2. Найти потенциалы U_i и V_j. Составить для базисных клеток m + n – 1 уравнений с m + n неизвестными.

3. Для каждой свободной клетки найти значения D_ij = C_ij –– (U_i + V_j). Если среди значений D_ij нет отрицательных, то полученный план транспортной задачи оптимальный. Если же такие имеются, то перейти к новому опорному плану.

4. Среди отрицательных D_ij выбрать наибольшее по модулю отрицательное число D_ij. Построить для этой свободной клетки цикл пересчета и произвести сдвиг по циклу пересчета.

5. Полученный опорный план проверить на оптимальность. Если он не оптимален, то перейти к п. 2.

Тема 3.СЕТЕВЫЕ МОДЕЛИ И МЕТОДЫ

ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ

В результате изучения данной темы студенты должны:

знать:

- область применения моделей сетевого планирования и управления в экономике;

- основные понятия сетевого планирования и управления;

- методы расчёта параметров моделей сетевого планирования и управления;

уметь:

- формулировать постановку различных задач линейного программирования;

- находить решение задач линейного программирования с помощью графического и симплексного методов;

- давать экономическую интерпретацию полученных результатов решения задач линейного программирования;

- применять методы сетевого планирования и управления для решения практических задач;

владеть:

- математическим аппаратом линейного программирования;

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

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

Объектом управления в системе сетевого планирования и управления (СПУ) является коллектив исполнителей, располагающий определенными материальными и денежными ресурсами и выполняющий комплекс работ, направленный на достижение конечного результата в установленные сроки.

Система СПУ позволяет:

1. Составлять календарный план реализации комплекса работ.

2. Выявлять и мобилизовать резервы времени, трудовые, материальные и денежные ресурсы.

3. Повышать эффективность управления, прогнозируя и предупреждая возможные срывы в ходе выполнения работ.

Система СПУ включает следующие основные этапы:

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

2. Построение сетевого графика на основе выявленной очередности выполнения работ.

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

4. Расчет параметров сетевого графика.

5. Анализ и оптимизация сетевого графика (для ускорения выполнения работ производится необходимое перераспределение ресурсов).

6. Использование сетевого графика как основного инструмента управления ходом работ.