Переход от одного опорного решения к другому

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

Для свободной клетки с Dij>0 строится цикл (цепь-многоугольник) …… все вершины которого кроме одной находятся в занятых клетках, углы прямые, число вершин чётное. Около свободной клетки цикла становится знак “+”, поочерёдно “- ”, “+”, “-”, “+”…

У вершин со знаком “-“ выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком “+” и отнимают у вершин со знаком “-“.

В результате перераспределения получим новое опорное решение, его проверяем на оптимальность и т. д. …

По табл.2 построим цикл для клетки с “+” оценкой

Новое опорное решение:

Проверим решение:

				ui
vj		-2

ui + vj = cij

Пусть u1=0

v1= c11 – u1 = 2 – 0 = 2

v3= c13 – u1 = 2 – 0 = 2

u2= c23 – v3 = 5 – 2 = 3

v2= c22 – u2 = 1 – 3 = -2

u3= c31 – v1 = 3 – 2 = 1

D12=u1 + v2 – c12= 0 – 2 – 5 = -7 <0

D21=u2 + v1 – c21= 3 + 2 – 4 = 1 >0

D32=u3 + v2 – c32= 1 – 2 – 6 = -7 <0

D33=u3 + v3 – c33= 1 + 2 – 8 = -5 <0

D21=1 >0 => решение не оптимально

				ui
vj		-2

ui + vj = cij

Пусть u1=0

v3= c13 – u1 = 2 – 0 = 2

u2= c23 – v3 = 5 – 2 = 3

v1= c31 – u3 =3 – 2 = 1

v2= c22 – u2 = 1 – 3 = -2

u3= c31 – v1 = 3 – 1 = 2

D11=u1 + v1 – c11= 0 + 1 – 2 = -1 <0

D12=u1 + v2 – c12= 0 – 2 – 5 = -7 >0

D32=u3 + v2 – c32= 2 – 2 – 6 = -6 <0

D33=u3 + v3 – c33= 2 + 2 – 8 = -4 <0

решение оптимально

Ответ:

Задача:

Фирма осуществляет поставку бутылок на 4 завода, занимающихся производством напитков.

У фирмы 3 склада: на 1-м 6000, на 2-м 3000, на 3-м 4000 бутылок

Необходимо поставить на 1-й завод 4000, на 2-й 5000, на 3-й 1000, на 4-й 3000

Стоимость перевозки одной бутылки задана матрицей

Как следует организовать поставку, чтобы стоимость была минимальной?

Дата добавления: 2014-01-04