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

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

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

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

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

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

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

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

Итак, 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 способ. Симплекс метод

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

например:

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

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

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

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

c_ij –(α_i + β_j) ³ 0

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

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

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.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: