Алгоритм решения транспортной задачи с нарушенным балансом, страница 2

В этом случае удовлетворяется полностью заявка потребителя j,  а остаток произведённого ресурса будет распределён после. Так как потребность потребителя j удовлетворена полностью, то исключается из рассмотрения столбец матрицы стоимости, принадлежащий  j-му потребителю;

2) производитель i  имеет ресурса меньше, чем надо потребителю j.

В этом случае весь имеющийся ресурс производителя i назначается потребителю j. Недостающая часть ресурса потребителю j будет названа потом. Так как весь ресурс производителя i исчерпан полностью, то из рассмотрения удаляется строка матрицы стоимости, принадлежащая производителю i;

3) производитель i имеет ресурса столько, сколько надо потребителю j.

В этом случае, аналогично рассмотренным выше случаям, из рассмотрения удаляются и строка, и столбец матрицы стоимости.

Затем из матрицы стоимостей выбирается следующая минимальная стоимость перевозки ресурса от производителя к потребителю, удовлетворяются потребности следующего потребителя ресурса (полностью или частично) и удаляется из рассмотрения очередная строка или столбец матрицы стоимостей. Процесс повторяется до тех пор, пока не будет распределён полостью весь произведённый ресурс между всеми потребителями. Так как ресурса произведено ровна столько, сколько нужно потребителям, то задач распределения будет обязательно выполнена.

1.2.6. Метод добротностей

При использовании метода добротностей исходную матрицу стоимостей перевозок переводят в разреженное состояние. Разреженное состояние характеризуется наличием нулевых значений в строках и столбцах исходной матрицы. Перевод матрицы стоимостей в разреженное состояние производится по следующему алгоритму:

1) в каждой строке матрицы стоимостей определяют минимальный элемент и вычитают его значение из каждого элемента строки;

2) в каждом столбце, полученном па первом шаге разреженной матрицы, определяют минимальный элемент и вычитают его значение из каждого элемента столбца;

3) определяют добротности.

Добротность  определяется   по   каждой  строке  и  по каждому столбцу разреженной матрицы.

Добротности рассчитываются по следующему правилу:

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

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

4)      назначают ресурс потребителю.

Определяется строка или столбец, у которого добротность имеет максимальное значение, и в этой строке или столбце определяется элемент сij, с минимальным значением. Потребителю j (под выбранным минимальным элементом) назначается ресурс от производителя k (справа от минимального элемента). Возможны три варианта:

а) спрос потребителя удовлетворен полностью, а ресурс у производителя остался. В этом случае из рассмотрения удаляется столбец из исходной матрицы, а в матрицу решения (плана перевозок) записывается поставка ресурса;

б)      спрос потребителя удовлетворен частично, а ресурс производителя использован полностью. В этом случае из рассмотрения удаляется строка k из исходной матрицы, а в матрицу решения (плана перевозок) записывается поставка ресурса;

в)      спрос потребителя удовлетворен полностью и полностью исчерпан ресурс производителя. В этом случае из рассмотрения удаляется строка k и столбец i из исходной матрицы, а в матрицу решения (плана перевозок) записывается поставка ресурса;