Методы решения транспортной задачи.

Транспортная задача может быть решена симплекс методом. Однако специфическая форма системы ограничений позволяет упростить симплекс метод.

МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА. Заполнение клеток происходит последовательно по следующему алгоритму: сначала вывозится груз из пункта А1 и завозится в пункт В1, и этой перевозке х11 присваивается максимально возможное значение. Если заявка пункта В1 выполнена, а в пункте А1 еще остается груз, то он вывозится в пункт В2 и т.д. Если в пункте А1 недостаточно было груза для В1, то недостающий груз берется из А2 и т.д.

После того как спрос потребителя А1 удовлетворен, он выпадает из рассмотрения и т.д.

Стоимость перевозки: W=5*15+5*7+25*7+5*4+25*6+10*7+5*4+10*6=605

Существенным недостатком метода северо-западного угла является то, что он построен без учета стоимости перевозок.

МЕТОД МИНИМАЛЬНОГО ЭЛЕМЕНТА. Заполнение клеток транспортной таблицы начинается с той клетки, в которой значение минимально. В нее записывается максимально возможное значение перевозки хij, которое может быть равно либо запасу аi, либо заявке вj. Если заявка вj выполнена полностью, то j-й столбец больше не рассматривается. Если не вывезенный груз еще остался, то он вывозится в пункт с наименьшим тарифом.