Задать начальные значения элементам

7 8 9 10 11 12 13

массивов х_ij; с_ij; а_i,b_j_, u_i, v_j, а также

счетчикам и рабочим массивам

вычислить базисное допустимое

решение по правилу “самая

дешевая продукция реализу-

ется первой”

вычислить коэффициенты

и для базисного

допустимого решения

найти для небазисных перейти к базисному

переменных допустимому решению

все ли нет

Да

Оптимальное решение получено

Рис1.

Процедура перехода к новому базисному допустимому решению (начиная со строки 2000 до строки 3250) заслуживает внимательного изучения. Поясним ее подробнее. Сначала находим “цепь” w клеток, которая не является “тупиковым путем” (строки 2050 – 2730).

Найти наименьший элемент C(I,J)

текущего массива C(RI,CJ)

нет

DA(RI)0<DB(CJ)?

да

Проверить, что удалено не более М-1 Положим X(RI,CJ)=DB(CJ) и

строк. Положить X(RI,CJ)=DA(RI) и пометить этот элемент как

пометить этот элемент как базисный. базисный. Заменить DA(RI)

Заменить DB(CJ) на DB(CJ)-DA(RI). на DA(RI)-DB(CJ). Удалить

Удалить строку RI и подсчитать столбец и посчитать количество

количество удалений удалений

нет

Увеличить TR(RI) и TC(CJ) на 1

Количество базисных

переменных меньше

чем М+N-1?

Введите следующую программу

для определения u и v

Рис2.

На шаге 1 мы находимся в клетке (K,L), T - счетчик шагов, IP – индикатор “тупикового пути”, (RT(T), CT(T)) (RI,CJ) – клетка, в которую мы попадаем на шаге Т. Массив D состоит из 1, соответствующих w; положим ММ=1, если клетка используется, IU=1 и IV=1, если строки и столбцы входят в цикл.

В команде 2100 на шаге Т ищется строка RT(T) для столбца, содержащего базисную переменную в неиспользованном столбце (строка 2140) в неотмеченной клетке (строка 2150). Если это единственная переменная в своем столбце, то производится присваивание IP=1 (строка 2170). Разумеется, это не делается в начальном столбце L. После того как подходящая переменная найдена в столбце CJ, поиск прекращается; при этом FC=1.

Затем T увеличивается для следующего шага, в переменную RT(T) заносится номер текущей строки, а в переменную СT(T) – номер только что найденного столбца CJ; соответствующему D присваивается значение –1, и найденная клетка помечается присвоением ММ значения 1 (строка 2320). Если мы снова оказались в столбце L, откуда начали, то цикл завершен (строка 2400). В противном случае ищем столбец СT(T)[ СJ] для строки, содержащей базисную переменную в неотмеченных строке и клетке; таким образом снова помечаются “тупиковые пути”. Как только искомый столбец найден, поиск прекращается присвоением FR=1. Затем T увеличивается для следующего шага, переменной RT(T) присваивается номер только что найденной строки RI, а CT(T) - -номер только что обрабатывавшегося столбца; для этой клетки осуществляются присвоения: D=+1, MM=1,после чего программа возвращается к поиску строки в строке 2100 программы.

Заметим, что если в процессе поиска строки не удается найти столбец (СJ=0 в строке 2190), не являющийся “тупиковым путем”, то происходит возвращение (строка 2210) к строке предыдущего поиска столбца. Если в поисках столбца удается найти только строки (RI=0 в строке 2590), соответствующие тупиковым путям, то осуществляется возвращение (строка 2610) к строке предыдущего поиска строки. Однако в силу того, что ММ сохраняет свое значение, ошибка не повторяется в дальнейшем (ММ=1 в строках 2150 и 2550). Поскольку базис задан треугольной системой уравнений, процесс в конце концов закончится и управление будет передано из строки 2400 в строку 3000.

В строках 3000 – 3040 программы содержится наименьшая базисная переменная из клеток, в которых D=-1. Здесь определяются значение w и положение переменной (KK,LL), которая будет удалена из базиса. В строках 3100 – 3120 клетки включаются в цепь. В конечном счете переменная (K,L) определяются как базисная, переменная (KK,LL) – как небазисная и определяется количество базисных переменных во всех строках и столбцах. Затем программа возвращается к вычислению симплекс-множителей u и v.

При работе программы печать (u и v) в строках 1340 – 1342 и наибольшего по модулю значения с_ij в строке 1581, а также печать в строках 2071, 2321 и 2721 могут быть подавлены. Последние три строки отражают цепи и обратный поиск. Печать в строке 3221, определяющая w и переменную для удаления из базиса, тоже могут быть подавлена.

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