Метод сечения Гомори

Допустим мы решали задачу и получили последнюю таблицу без учета целочисленности

Б	X опт	x 1	x 2	....	xm	ω1	ω2	....	ω n
x 1	β1			:		α11	α21	....	α1 n
x 2	β1			:		α21	α22	....	α2 n
....	....	....	....	....	....	....	....	....	....
xn	β n			:		α m 1	α m 2	....	α mn
z	β0			:		c 1	c 2	....	cn

Если β _i – целые, то задача решена; иначе выбирают β _i с наибольшей дробной частью и выписывают уравнение из таблицы.

По условию целочисленности x_i, ω _i – целые.

Чтобы уравнять обе части мы добавляем искусственную переменную

К полученной таблице добавляется строка, соответствующая отсечению Гомори, в столбце X _опт стоит – f_i (т.е. отрицательное число). А так как в столбце X _опт стоит отрицательное число – поэтому применяем двойственный симплекс-метод.

пример. max z = 7 x ₁ + 9 x ₂.

Б	С	X опт					r
x 1	x 2	s 1	s 2
s 1			– 1
s 2
z			– 7	– 9
x 2			– 1/3		1/3
s 2			22/3		– 1/3
z			– 10
x 2		7/2			7/22	1/22
x 1		9/2			– 1/22	3/22
z					28/11	15/11

Б	С	X опт	x 1	x 2	s 1	s 2	R 1
x 2		7/2			7/22	1/22
x 1		9/2			– 1/22	3/22
z					28/11	15/11
R 1		– 1/2			– 7/22	– 1/22

Б	С	X опт	x 1	x 2	s 1	s 2	R 1	R 2
x 2
x 1		32/7				1/7	– 1/7
s 1		11/7				1/7	– 22/7
z
R 2		– 4/7				– 1/7	– 67
x 2
x 1							– 1
s 1							– 4
s 2								– 7
z

Итак, x ₁ = 4; x ₂ = 3; max z = 55; s ₁ = 1; s ₂ = 4; R ₁ = 0; R ₂ = 0.

Транспортная задача на минимум

пример. На трех базах Б ₁; Б ₂; Б ₃ находится однородный груз. Этот груз необходимо доставить в пять пунктов П ₁, П ₂,..., П ₅. Запасы груза на трех базах a_i и потребности пунктов b_j указаны в таблице. Стоимость перевозки одной тонны груза с базы Б_i в пункт П_j (Б_i → П_j) равная c_ij рублей. Спланировать их перевозки так, чтобы их стоимость была наименьшей.

	П 1	П 2	П 3	П 4	П 5	ai
Б 1
Б 2
Б 3
bj

1 способ. Симплекс метод

x_ij – перевозка Б_i → П_j

2 способ. Метод потенциалов

1 этап. Составить начальный план.

Показатели плана записываются только в клетки с оценками, x_ij ³ 0.

Для построения начального решения используются следующие методы.

1 метод – Метод северо-западного угла

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

	П 1	П 2	П 3	П 4	П 5	ai
Б 1
Б 2
Б 3
bj

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

2 метод – минимальный элемент по строке

	П 1	П 2	П 3	П 4	П 5	ai
Б 1
Б 2
Б 3
bj

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

3 метод – минимальный элемент по столбцу. Аналогично вышеизложенному.

4 метод – метод минимального элемента.

	П 1	П 2	П 3	П 4	П 5	ai
Б 1
Б 2
Б 3
bj

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

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

Рассмотрим план северо-западного угла.

Заполненных клеток 7.

m + n – 1 = 5 + 3 – 1 = 7 Þ план невырожденный.

В этом случае система потенциалов строится таким образом.

α _i – потенциалы строк.

β _j – потенциалы столбцов.

Положим α₁ = 0, остальные потенциалы считают из условия: для заполненных клеток c _ij = α _i + β _j.

П 1

П 2

П 3

П 4

П 5

α i

Б 1

Б 2

Б 3

β j

Отступление. Для вырожденного плана.

например:

	П 1	П 2	П 3	П 4	α i	Заполненных клеток 6. m + n – 1 = 4 + 4 – 1 = 7 1. Потенциал строки с наиболь­шим количеством заполненных клеток положим равным нулю. 2. Далее по общему правилу пока это возможно вычисляем потенциалы. Остались две незаполненные клетки. Далее невозможно.
Б 1
Б 2
Б 3
Б 4
β j

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

Условие оптимальности плана

c _ij ³ α _i + β _j – признак оптимальности плана.

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

c _ij –(α _i + β _j) ³ 0

	П 1	П 2	П 3	П 4	П 5	α i
Б 1
Б 2					–		+
Б 3					+		–
β j

Б1П3	7 – (0 + 6) ³ 0	хорошая клетка
Б1П4	7 – (4 + 0) ³ 0	хор.
Б1П5	3 – (0 + 3) = 0	хор.
Б2П1	6 – (5 + 1) = 0	хор.
Б2П5	5 – (3 + 1) ³ 0	хор.
Б3П1	8 – (5 + 2) ³ 0	хор.
Б3П2	6 – (2 + 6) = – 2	плохая
Б3П3	5 – (6 + 2) = – 3	плохая

Значит план неоптимален, его надо улучшать.

3 этап. Построение цикла перевозки. Здесь мы выбираем самую плохую клетку Б₃П₃, в нее помещаем вершину.

Цикл – это прямоугольник, начальная вершина которого находится в самой плохой клетке, а остальные вершины только в заполненных клетках. Начальная вершина отмечается знаком «плюс» (+), далее в порядке чередования ставятся знаки «–», «+».

Выберем объем дополнительной перевозки – это будет минимальная перевозка, отмеченная знаком «–».

θ = min (285; 660) = 285.

Прибавим её в клетках со знаком «+» и отнимем в клетках со знаком «–». Таким образом мы пересчитаем план и все начнется сначала.

	П 1	П 2	П 3	П 4	П 5	α i
Б 1			–						+
Б 2			+		–
Б 3					+				–		– 1
β j

θ = min (525; 375; 810) = 285.

	П 1	П 2	П 3	П 4	П 5	α i
Б 1			–						+
Б 2
Б 3			+						–
β j

θ = min (150; 435) = 150.

	П 1	П 2	П 3	П 4	П 5	α i
Б 1	–								+
Б 2	+		–
Б 3			+						–
β j

θ = min (705; 285; 420) = 285.

	П 1	П 2	П 3	П 4	П 5	α i
Б 1
Б 2
Б 3
β j

с = 420 · 5 + 285 · 6 + 135 · 7 + 435 · 6 +660 · 5 + 555 · 5 + 810 · 3 = 15870.