Распределительный метод решения транспортной задачи

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

Вернемся к нашему примеру и возьмем базисный план, построенный методом северо-западного угла (табл. 2.3.3). Соответствующие данному плану суммарные транспортные затраты (значение целевой функции) F =750. Чтобы определить, является ли полученный план оптимальным, необходимо «оценить» различные варианты, связанные с неиспользованием клеток, в которых нет поставок (выделенных чисел). Таких клеток в нашем примере четыре. Посмотрим, что произойдет с таблицей, если дать единичную поставку в одну из пустых клеток, например в (2,1).

Чтобы не нарушался баланс по строкам и столбцам необходимо уменьшить на единицу поставку в клетки (2,2) и (1,1). Уменьшив поставку в (1,1) мы должны увеличить на единицу поставку в клетку (1,2). Заметим, что последнее изменение восстановило баланс по столбцу 2, нарушенный уменьшением поставки в клетку (2,2). Мы получили новый допустимый план поставок (см. табл. 2.3.5).

	2	1	5
	3	4
	4	15	6

Таблица 2.3.5

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

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

При этом знаком “+” помечены те клетки, поставка в которых увеличится (положительные вершины). Знаком “–“ отмечены клетки, в которых поставка уменьшится (отрицательные вершины).

(1,1) 2 – (1,2) 1 +

Дата добавления: 2015-04-24