Решение задач симплекс методом (стр. 3 из 4)

Способ северо-западного угла состоит в том, что распределение объемов вывоза производится, начиная с верхнего левого угла таблицы и кончая нижним углом ее. Результаты распределения показаны в таблице.

Поставщики и объемы вывоза, т		Потребители и объемы завоза						Потенциалы строк
		М1	М2	М3	М4	М5	М6
		92	84	80	112	96	36
П1	144	24	30	42	15	39	21	0
		92	52
П2	148	9	24	30	33	27	29	-6
		32	80	36
П3	76	24	22	20	45	21	23	6
		76	0
П4	132	11	36	27	40	30	8	15
		96	36
Потенциалы столбцов		24	30	36	39	15	-7

Проверка плана на оптимальность. Когда исходный план получен и рассчитана соответствующая ему суммарная тонно-километровая работа, определяют, является ли этот план оптимальным. Для проверки плана на оптимальность применяется метод потенциалов.

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

Для решения задач методом потенциалов исходный план должен иметь количество заполненных клеток m + n – 1 (m - число строк, n - число столбцов). Если план не отвечает этим требованиям, то не для всех строк и столбцов можно рассчитать потенциалы, а без них нельзя проверить план на оптимальность.

Потенциалы строк и столбцов определяются по заполненным клеткам, находящимся на их пересечении.

Элемент заполненной клетки должен равняться сумме потенциалов строки и столбца, на пересечении которых находится эта заполненная клетка.

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

Обозначив потенциалы строк u_i, потенциалы столбцов Vj, элементы заполнения клеток

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

Из основного требования

= u_i+ Vj вытекает:

u_i =

- Vj; Vj = - u_i

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

Потенциалы показаны в таблице.

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

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

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

Иными словами, если характеристика, значение которой равно разности

- (u_i+ Vj), положительная, то свободная метка не заполняется при решении задачи на минимум функции.

Свободные клетки, имеющие нулевое значение характеристики, показывают на то, что их заполнение приведет к перераспределению поставок, но объем работ (значение функционала) останется неизменным.

Суммы потенциалов, значения элементов и характеристики для незаполненных клеток приведены в таблице.

Шифры клеток	П1-М3	П1-М4	П1-М5	П1-M6	П2-М1	П2-М5	П2-М6	П3-М1	П3-М2	П3-М3	П3-М6	П4-М1	П4-М2	П4-М3	П4-М4
Суммы потенциалов	36	39	15	-7	18	9	-13	30	36	42	-1	39	45	51	54
Значение элементов	42	15	39	21	9	27	29	24	22	20	23	11	36	27	40
Характеристики	6	-24	24	28	-9	18	42	-6	-14	-22	24	-28	-9	-24	-14

В первоначальном плане шесть клеток имеют положительные характеристики, в девяти клетках характеристики отрицательные.

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

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

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

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

+П4М1 -П1М1 +П1М2 -П2М2 +П2М4 -П3М4 +П3М5 -П4М5

Поставщики и объемы вывоза, т		Потребители и объемы завоза						Потенциалы строк
		М1	М2	М3	М4	М5	М6
		92	84	80	112	96	36
П1	144	24	30	42	15	39	21	0
		60	84
П2	148	9	24	30	33	27	29	-6
		80	68
П3	76	24	22	20	45	21	23	6
		44	32
П4	132	11	36	27	40	30	8	15
		32	64	36
Потенциалы столбцов		24	30	36	39	15	-7

Шифры клеток	П1-М3	П1-М4	П1-М5	П1-М6	П2-М1	П2-М2	П2-М5	П2-М6	П3-М1	П3-М2	П3-М3	П3-М6	П4-М2	П4-М3	П4-М4
Суммы потенциалов	36	39	15	-7	18	24	9	-13	30	36	42	-1	45	51	54
Значение элементов	42	15	39	21	9	24	27	29	24	22	20	23	36	27	40
Характеристики	6	-24	24	28	-9	0	18	42	-6	-14	-22	24	-9	-24	-14

+П2М5 -П4М5 +П4М1 -П1М1 +П1М4 -П2М4

Поставщики и объемы вывоза, т		Потребители и объемы завоза						Потенциалы строк
		М1	М2	М3	М4	М5	М6
		92	84	80	112	96	36
П1	144	24	30	42	15	39	21	0
		16	84	44
П2	148	9	24	30	33	27	29	18
		80	68
П3	76	24	22	20	45	21	23	-22
		76
П4	132	11	36	27	40	30	8	-13
		76	20	36
Потенциалы столбцов		24	30	12	15	43	21

Шифры клеток	П1-М3	П1-М5	П1-М6	П2-М1	П2-М2	П2-М5	П2-М6	П3-М1	П3-М2	П3-М3	П3-М4	П3-М6	П4-М2	П4-М3	П4-М4
Суммы потенциалов	12	43	21	42	48	61	39	2	8	-10	-7	-1	17	-1	2
Значение элементов	42	39	21	9	24	27	29	24	22	20	45	23	36	27	40
Характеристики	30	-4	0	-33	-24	-34	-10	22	14	30	52	24	19	28	38

+П2М5 -П4М5 +П4М1 -П1М1 +П1М4 -П2М4