Первоначальный план, выбранный по методу минимальной стоимости.
В нем число занятых клеток равно 7, а .
Следовательно, план вырожденный.
Для дальнейшего решения нужно сделать одну клетку фиктивно (условно) занятой.
Выбираем клетку и в нее записываем ноль.
(Целесообразно выбрать клетку с min стоимостью)
Таблица будет иметь другой вид:
Матрица перевозок | Потребители | Запасы | |||||||||||
Поставщики | |||||||||||||
- | - | - | - | ||||||||||
- 7 50 | - | - | - | ||||||||||
- | - | - | - 2 - | 200 + | |||||||||
- | 150 + | - | 50 - | ||||||||||
Потребности |
ед.
Расчет системы потенциалов
Чтобы начать расчет нужно один из потенциалов принять за 0. Затем по теореме потенциалов для занятых клеток рассчитать остальные потенциалы.
Выбираем строку с наибольшим количеством занятых клеток. Это строка А 4.
Пусть тогда
клетка А 4 В 2: следовательно
клетка А 4 В 3: следовательно
клетка А 4 В 5: следовательно
клетка А 3 В 5:
клетка А 3 В 4:
клетка А 1 В 4:
клетка А 2 В 2:
клетка А 2 В 1:
далее проверяем план на оптимальность по свободным клеткам (Теорема для свободных клеток)
клетка А 1 В 1: ДА
клетка А 1 В 2: ДА
клетка А 1 В 3: ДА
клетка А 1 В 5: ДА
клетка А 2 В 3: тогда рассчитываем разность потенциалов:
клетка А 2 В 4:
клетка А 2 В 5:
клетка А 3 В 1: ДА
клетка А 3 В 2: ДА
клетка А 3 В 3: ДА
клетка А 4 В 1: ДА
клетка А 4 В 4: ДА
Из трех цифр и выбираем самое большое .
С нее будем начинать цикл. Цикл строим по занятым клеткам. Затем выбираем количество груза, которое нужно перераспределить . Там где знак «+» прибавляем 0, там где «-» отнимаем.
Строим новую таблицу. И снова рассчитываем систему потенциалов.
Матрица перевозок | Потребители | Запасы | |||||||||
Поставщики | |||||||||||
- | - | - | - 1 | - | |||||||
- 7 50 | - | + 6 - | - | ||||||||
- | - | - | - | ||||||||
- | 150 + | - | 50 - | ||||||||
Потребности |
Клетка А 2 В 4 была свободной, а стала занятой, следовательно, должно измениться либо либо .
Изменим так как его изменение приведет к меньшим пересчетам.
Пусть осталось равным -1 клетка А 2 В 4: , клетка А 1 В 4:
Проверим по занятым клеткам правильность расчетов системы потенциалов.
Клетка А 2 В 1: .
Все верно.
Проверяем план на оптимальность по свободным клеткам:
клетка А 1 В 1: ДА
клетка А 1 В 3:
клетка А 1 В 5:
клетка А 2 В 3:
самая большая величина. С этой клетки начинаем цикл .
Матрица перевозок | Потребители | Запасы | |||||||
Поставщики | |||||||||
- | - | - | - 1 | ||||||
- 7 0 |
| + 6 | - | ||||||
- | - | - | - | ||||||
- | 200 + | 100 - | - | - | |||||
Потребности |
Клетка А 1 В5 была свободной, а стала занятой, следовательно, должно измениться либо либо .
Изменим / так как его изменение приведет к изменению только .
Пусть осталось равным -6 клетка А1В5: , клетка А3В5:
Проверим по занятым клеткам правильность расчетов системы потенциалов.
Все верно.
Проверяем план на оптимальность по свободным клеткам:
Условие нарушено в трех клетках.
клетка А 1 В 3:
клетка А 2 В 3:
клетка А3В 3:
самая большая величина. С этой клетки начинаем цикл .
Матрица перевозок | Потребители | Запасы | |||||
Поставщики | |||||||
- | - | ||||||
- | - | - | |||||
- | - | - | - | ||||
- | 100 - | - | - | ||||
Потребности |
Клетка А 1 В3 была свободной, а стала занятой, следовательно, должно измениться либо либо .
Изменим , так как его изменение приведет к меньшим изменениям.
Пусть осталось равным -6 клетка А1В3: ,
клетка А4В3: ,
клетка А4В2: .
Проверим по занятым клеткам правильность расчетов системы потенциалов.
Все верно.
Проверяем план на оптимальность по свободным клеткам:
Условие выполняется во всех клетках. План оптимальный.
Рассчитаем значение целевой функции, то есть стоимость перевозки для оптимального плана.
Z=0*4+50*1+50*4+200*2+50*6+200*2+200*8+100*12+4150