Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Правило северо-западного угла
|
|
Построение плана начинается с северо-западной клетки таблицы, то есть первым определяется значение переменной X11.
| b1 | b2 | … | bn | |
| C11 X11 | C12 X12 | … | C1n X1n |
| C21 X21 | C22 X22 | … | C2n X2n |
| … | … | … | … | … |
| Cm1 Xm1 | Cm2 Xm2 | … | Cmn Xmn |
Так как оно должно быть максимально допустимым, то 
Если X11=а1, то закрывается первая строка и X12=X13=…=X1n= 0, а следующей базисной переменной будет X21. Из указанного выше принципа следует X21 =min(a2, b1 - a1). Если же окажется, что X11=b1, то закроется первый столбец и следующей базисной переменной станет X12= min(a1-b1, b2). Общее правило определения значения очередной базисной переменной: Xij =min(остаток от ai, остаток до bj). (13)
Таким образом, число базисных переменных равно m+ n -1. Построение начального плана завершено.
Переход от одного плана перевозок к другому
Клетки с базисными переменными будут базисными или занятыми, остальные – небазисными или свободными. Для перехода к новому плану используется замкнутая цепь, которая строится в матрице перевозок по следующим правилам.
 |
Построение начинается со свободной клетки, которую соединяют с базисной в строке (столбце). Последнюю соединяют с базисной в столбце (строке). Далее, чередуя движение по строкам и столбцам, продолжаем соединение занятых клеток так, чтобы вернуться в начальную. При этом не требуется, чтобы цепь включала все базисные клетки. Угловые клетки цепи - вершины цепи. Правило построения замкнутой цепи можно сформулировать проще: начальная вершина должна быть в свободной клетке, остальные – в занятых. Такая цепь называется циклом пересчета. Он является геометрическим представлением разложения небазисного вектора условий при переменной в свободной клетке по векторам текущего базиса. Если базисная клетка не попала в цикл пересчета, то соответствующий базисный вектор имеет в этом разложении нулевой коэффициент. Так как любой небазисный вектор выражается через базис единственным образом, то для любой небазисной (свободной) клетки можно построить один и только один цикл пересчета. Кружком выделена начальная (небазисная) клетка цикла. Нумеровать вершины можно в любом направлении. И начинать можно с любой вершины. На рисунке нумерация проведена с клетки, смежной начальной. В этом случае начальная клетка всегда будет четной.
В результате цикл пересчета, построенный в допустимой матрице перевозок, обладает замечательным свойством: если перемещать по нему некоторое количество груза q > 0, прибавляя его к Xij в четных вершинах и вычитая из Xij в нечетных, то условия задачи 
и 
не нарушатся. Чтобы новое решение было допустимым, то есть выполнялось и условие неотрицательности переменных, необходимо ограничить значение q: q £ q0 =min Xij, ijÎ нечет. (14) Здесь нечет – множество индексов переменных в нечетных вершинах цикла.
Для получения базисного решения (нового опорного плана) достаточно взять q = q0. При этом переменная свободной клетки, на которой строился цикл, становится базисной со значением q0, а переменная, доставляющая минимум в (14), обнуляется и переходит в небазисные. Переход от одного плана к другому в методе потенциалов заключается в построении цикла пересчета, определении q0 с последующим прибавлением к значениям переменных в четных вершинах и вычитанием в нечетных.