о плану методом "північно-західного" кута і методом мінімальних елементів;
) вибирається перший незаповнений елемент опорного плану;
) від обраного елемента будується найкоротший прямокутний замкнутий контур, решта вершини проходить через заповнені елементи опорного плану. Поворот здійснюється тільки на 90 0 і тільки в заповнених елементах;
) кожній вершині контуру присвоюється коефіцієнт рівний відповідному значення елементу з С = {c ij };
) кожному коефіцієнту у вершині контуру суворо по черзі присвоюється знак "+" або "-" починаючи з порожньої клітки;
) виконується алгебраїчне підсумовування коефіцієнтів по всьому контуру;
) пункт 4-8 виконується для кожного порожнього елемента опорного плану;
) перевіряються результати підсумовування по всіх контурах на оптимальність;
) якщо план перевезень не оптимальний то виконується перерозподіл ресурсів і повертаємося до пункту 4.
Якщо при вирішенні транспортної задачі цільова функція прагне до min, то алгебраїчні суми по всіх контурах повинні бути позитивними або рівними нулю.
Якщо цільова функція прагне до max, то алгебраїчні суми по всіх контурах повинні бути негативними або рівними нулю.
Якщо план перевезень не оптимальний, то перерозподіл виконується таким чином:
а) вибирається контур, для якого порушено умова оптимальності, якщо цільова функція прагне до min, то вибирається негативний контур. Якщо таких контурів декілька, то обирається той, який більше за модулем;
б) у вершинах обраного контуру розставляються фактичні перевезення з тими знаками, які були вказані при обчисленні коефіцієнтів. Розглядається вершини тільки з негативними значеннями. Вибирається вершина з мінімальним по модулю негативним значенням, і воно віднімається з усіх вершин контуру. Отриманий опорний план застосовується без урахування знаків;
в) перевіряється збалансованість перевезень по стовпцях і рядках;
г) заново розраховується алгебраїчні суми (за вартістю) для всіх контурів;
д) перевіряється умова оптимальності.
2.3 Опис програми
...
