При выполнении дооптимизации единственным подтверждением правильности результатов может служить уменьшение целевой функции

.

5. Алгоритм решения задачи

1. Проверка правильности ввода данных.

2. Проверка условия баланса.

3. Построение начального опорного плана Х⁽⁰⁾ методом минимального элемента.

4. Проверка плана на вырожденность, если нужно добавляем фиктивные перевозки.

5. Расчет начальных потенциалов и заполнение матрицы С⁽¹⁾ .

6. Поиск минимального элемента в матрице С⁽¹⁾ .

7. Если этот элемент меньше нуля, то заменяем нулевой элемент, соответствующий минимальному в С⁽¹⁾ , в плане Х⁽⁰⁾ на фиктивную перевозку, иначе на пункт 12.

8. Производим процедуру вычеркивания.

9. Оставшиеся не вычеркнутыми элементы разделяем на четные и нечетные, учитывая, что добавленный элемент принадлежит к четным.

10. Находим минимальный нечетный элемент и прибавляем его ко всем четным и отнимаем от нечетных элементов. Причем, если минимальных элементов окажется 2 или более, то один из них обнуляем, а остальные делаем фиктивными. В итоге получаем план Х⁽¹⁾ .

11. Производим процедуру вычеркивания. Получаем матрицу С⁽²⁾ .

12. Проверяем матрицу С⁽²⁾ на наличие отрицательных элементов. Если такие элементы присутствуют, то повторяем пункты с 5 по11.

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

14. Дооптимизация по времени.

14.1. Ищем отличный от нуля элемент в матрице X^{( k )} , которому соответствует наибольший элемент матрицы Т=t_max .

14.2. Ищем в матице С^{( k )} нули соответствующие таким нулям в матрице X^{( k )} , что соответствующие им элементы матрицы Т меньше t_max .

14.3. Если в предыдущем пункте нашелся хоть один ноль, то производим процедуры пунктов 7-10.

14.4. Переходим к пункту 14.1.

15. Вывод результатов.

6. Листинг программы, реализующий алгоритм задачи

const

color=TColor(Clred);

var i,j,v,w:integer;

err,kon:boolean;

str:String;

begin

kon:=true;

Label3.Caption:='';