Метод минимальной стоимости
Суть метода в следующем. Сначала из всей таблицы выбираем клетку с самым маленьким тарифом. В эту клетку помещаем максимально возможную перевозку, а затем вычеркиваем клетки, ставшие ненужными. Затем в оставшейся части таблицы процесс повторяем, пока вся таблица не будет заполнена. В данном случае сама дешёвая клетка (А 1, В 1 ). С неё и начинаем распределение грузов: х 11 = min { 200; 70 } = 70. Вычеркиваем оставшиеся клетки первого столбца и повторяем процесс в оставшейся части таблицы. Запишем последовательность заполнения клеток: х 14 = min { 200 - 70; 110 } = 110; х 32 = min { 100; 80 } = 80; х 13 = min { 200 – 70 – 110; 150 } = 20; х 23 = min { 200; 150 - 20 } = 130; х 25 = min { 200 - 130; 90 } = 70; х 35 = 20. Получаем следующий опорный план:
Здесь получены семь ненулевых перевозок, поэтому план невырожденный. Подсчитаем его стоимость: F (X 2 ) = 4 × 70 + 6 × 20 + 5 × 110 + 9 × 130 + 10 × 70 + 5 × 80 + 20 × 20 = 3620. Как видим, этот опорный план дешевле первого.
|
ПН
ПО
