Пример. найти наименьшую стоимость перевозок.

Пример. найти наименьшую стоимость перевозок.

Решение:

1. Модель задачи закрытая, так как , .

2. Методом наименьшей стоимости распределим груз в (4+4-1=7) 7 базисных клеток. Подсчитаем стоимость перевозок по первому опорному плану

;

3. Находим потенциалы по базисным клеткам по формуле a _p + b _q = c_pq

Положим, что a₁ = 3, тогда b₁ = 9; b₄ = 0; a₂ = 3; a₃ = -2; a₄ = -3; b₂ = 7;

b₃ = 8.

Запишем эти потенциалы в таблицу и вычислим оценки свободных клеток:

g _ij = c_ij - (a _i + b _j).

4. Получили 4 отрицательные оценки: g₁₂ = -2; g₁₃ = -5; g₂₁ = -3; g₂₂ = -6; g₂₃ = -6. Клетке с наименьшей удельной стоимостью x₂₂ присваиваем знак «+» и строим для неё цикл пересчета. Сдвиг . Находим новые значения переменных в вершинах цикла:

.

Строим таблицу с новым базисом:

В этой таблице находим новые значения потенциалов.

Зададим один потенциал, пусть и по таблице, двигаясь по базисным клеткам, вычислим остальные потенциалы.

Вычисляем оценки свободных клеток. Выбираем с оценкой ставим знак «+» и строим цикл:

.

Делаем перерасчет:

свободная клетка.

.

Строим таблицу с новым базисом. В ней снова находим новые значения потенциалов и оценок свободных клеток. Одна оценка отрицательная, g₂₁ = -3, строим для клетки x₂₁ цикл пересчета:

.

Строим таблицу с новым базисом.

Все оценки свободных клеток положительны, следовательно, последняя таблица содержит оптимальное решение:

Дата добавления: 2015-11-04