являетя сбалансированной (закрытой) Шаг 2 Отыскание начального решения

являетя сбалансированной (закрытой).
Шаг:2
Отыскание начального решения. Метод минимального элемента

b1= 25

b2= 45

b3= 45

b4= 35

a1= 55

  15 5 35
a2= 55

25 30    
a3= 40

    40  
Шаг:3Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1 . В нашем случае N=6, n+m=4+3=7 , что удовлетворяет условию невырожденности плана.
Шаг:4Вычислим общие затраты на перевозку всей продукции.

b1= 25

b2= 45

b3= 45

b4= 35

a1= 55

 

 

15

8

5

5

35

3

a2= 55

25

2

30

4

 

 

 

 

a3= 40

 

 

 

 

40

1

 

 

Перемножим числа стоящие в одной клетке (для всех клеток) затем полученные произведения сложим. Получим значение суммарных затрат, для данного начального решения.
Pнач= 460
Шаг:5Проведем поэтапное улучшение начального решения, используя метод потенциалов.Итерация: 1
Составим вспомогательную рабочую матрицу затрат. Она строится из исходной матрицы издержек (см. Таблицу 3) путем переноса только тех ячеек Pij которые соответствуют заполненным клеткам транспортной таблицы. Остальные ячейки остаются пустыми.Кроме того, введем вспомогательный столбец в который внесем значения неизвестных U1 … U3 (3,это m — число складов) и вспомогательную строку в которую внесем значения неизвестных V1 … V4 (4,это n — число потребителей). На рисунке они представлены желтым цветом. Эти n+m неизвестных должны для всех (i,j), соответствующих загруженым клеткам, удовлетворять линейной системе уравненийUi+Vj=Pij

Читайте также:  Смоделируйте в Excel работу одноканальной СМО с очередью Пусть длительность интервалов времени между поступлениями заявок

b1

b2

b3

b4

a1

  8 5 3 u1= 3

a2

2 4     u2= -1

a3

    1   u3= -1

v1= 3

v2= 5

v3= 2

v4= 0

Порядок вычисления потенциалов был следующий:   1) Пусть V4 = 0 ;   2) U1 = P1,4 — V4 ;   3) V2 = P1,2 — U1 ;   4) V3 = P1,3 — U1 ;   5) U2 = P2,2 — V2 ;   6) U3 = P3,3 — V3 ;   7) V1 = P2,1 — U2 ;
Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = Pij – Ui — Vj (зеленый цвет).

b1

b2

b3

b4

a1

1 8 5 3 u1= 3

a2

2 4 4 10 u2= -1

a3

4 -1 1 3 u3= -1

v1= 3

v2= 5

v3= 2

v4= 0

Из всех отрицательных оценок имеет смысл выбрать наибольшую по модулю (красный цвет), так как ее воздействие на общие затраты является максимальным.

b1= 25

b2= 45

b3= 45

b4= 35

a1= 55

 

 

15

5

+

35

 

a2= 55

25

 

30

 

 

 

 

 

a3= 40

 

 

 

+

40

 

 

Затем мы определим минимум M из всех элементов, помеченных знаком — , и выбираем одну ячейку где этот минимум достигается. В нашем случае таковой является а1,b2 и обозначает загруженую клетку, которая должна стать свободной.
Число M при этом составляет: 15
Переход к новой транспортной таблице разбивается на следующие шаги.а) В ячейку а3,b2 новой таблицы записывается число M.б) Ячейка а1,b2 остается пустой.в) В остальных ячейках, помеченных знаками — или +, число M соответственно вычитается из стоящего в ячейке числа или складывается с ним. Результат вносится в соответствующую ячейку новой таблицы.г) Непомеченные числа переносятся в новую таблицу без изменений. Остальные ячейки новой таблицы остаются пустыми.

Читайте также:  №8 9В большой партии 70% изделий высшего качества и 0 2% бракованных

b1= 25

b2= 45

b3= 45

b4= 35

a1= 55

    20 35
a2= 55

25 30    
a3= 40

  15 25  
Итерация: 2Рабочая матрица затрат с пересчитанными потенциалами и оценкам.

b1

b2

b3

b4

a1

2 1 5 3 u1= 3

a2

2 4 3 9 u2= 0

a3

5 3 1 3 u3= -1

v1= 2

v2= 4

v3= 2

v4= 0

В приведенной выше таблице нет отрицательных оценок (план улучшить нельзя), следовательно достигнуто оптимальное решение.

b1= 25

b2= 45

b3= 45

b4= 35

a1= 55

 

 

 

 

20

5

35

3

a2= 55

25

2

30

4

 

 

 

 

a3= 40

 

 

15

3

25

1

 

 

Решение:

Общие затраты на перевозку всей продукции, для оптимального плана составляют:
Pопт= 445

002035253000015250

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...