Пример решения транспортной задачи - Экономико-математические методы

На четырех строительных площадках В1, В2, В3, В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит налажено на трех заводах А1, А2, А3 в размере соответственно 100,70 и 50 м3. Известны стоимости перевозки (табл.2) 1м3 сборных плит из каждого пункта производства в каждый пункт потребления (ден. ед./ м3).

Требуется так закрепить строительные площадки за заводами, чтобы при полном обеспечении сборными плитами перекрытий затраты на перевозку были минимальными.

РЕШЕНИЕ.

Исходное опорное решение получим по методу "северо-западного угла" (табл.3) и по методу min элемента (табл.4).

Здесь, т.е имеем закрытую модель ТЗ (табл.2 ).

Табл.2

Bj

Ai

20

120

20

60

100

6

4

2

4

70

1

2

7

2

50

2

4

1

4

Табл.3

Bj Ai

20

120

20

60

100
    6 20
    4 80

2

4

70

1
    2 40
    7 20
    2 10

50

2

4

1
    4 50

Транспортные расходы f=

Табл.4

Bj Ai

20

120

20

60

100

6
    4 100

2

4

70
    1 20

2

7
    2 50

50

2
    4 20
    1 20
    4 10

F=

Транспортные расходы для опорного плана, построенного по методу min элемента, меньше. Поэтому за исходное решение возьмем то, которое получено по методу min элемента (табл.4).

Количество заполненных клеток в табл.4 равно 6: m+n-1=3+4-1=6.

Следовательно, полученный план невырожденный.

Для определения потенциалов (см. формула 3.8) составляем уравнения:

U1+v2=4, u2+v1=1, u2+v4=2, u3 +v2=4, u3+v3=1, u3+v4=4. Положим u1=0, тогда v2=4, u3=0, v3=1, v4=4, u2=-2, v1=3.

Потенциалы проставлены в табл.5 (последняя строка и последний столбец). Их можно вычислять и непосредственно в таблице не выписывая систему уравнений. Т. к. если известны потенциал и тариф (стоимость перевозки) занятой клетки, то из соотношения ui+vj=cij легко определить неизвестный потенциал (из суммы вычесть известное слагаемое, получим неизвестное слагаемое. Роль суммы в данном равенстве играет тариф cij)

Определим по формуле (3.9) оценки свободных клеток:

S11=6-(0+3)=3>0, s13=2-(0+1)=1>0, s14=4-(0+4)=0

S22=2-(-2+4)=0, s23=7-(-2+1)=8>0, s31=2-(0+3)= -1<0

Табл.5 табл.6

Bj

Ai

20

120

20

60

Ui

Bj

Ai

20

120

20

60

Ui

100

6
    4 100

2

4

0

100

6
    4 100

2

4

0

70
    - 1 20

2

7

+ 2

50

-2

70
    - 1 10

+ 2

7
    2 60

-1

50

2

+
    4 20
    1 20
    -- 4 10

0

50

+ 2

10
    - 4 20
    1 20

4

0

Vi

3

4

1

4

Vj

2

4

1

3

План неоптимальный, т. к. s31<0. Строим для клетки (3;1) цикл непосредственно в табл.5. В цикл войдут клетки (3;1), (3;4), (2;4), (2;1). Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком, В результате смещения по циклу получим новый план (табл.6). Транспортные расходы ( а были равны 660).

Будет ли полученный план оптимальным? План невырожденный.

Определим для него новые потенциалы:

U1+v2=4, u2+v1=1, u2+v4= 2, u3+v1=2, u3+v2=4, u3+v3=1. Положим u1=0, тогда v2=4, u3=0, v1=2, v3=1, u2= -1, v4=3. Проставим значения найденных потенциалов в табл.6.

Определим оценки свободных клеток:

S11=6-(0+2)=4>0, s13=2-(0+1)=1>0, s14=4-(0+3)=1>0

S22=2-(-1+4)=-1<0, s23=7-(-1+1)=7>0, s44=4-(0+3)=1>0.

План (табл.6) неоптимальный, т. к. s22<0. Строим для клетки (2;2) цикл непосредственно в табл.6. В цикл войдут клетки (2;2), (2;1), (3;1), (3;2). Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком, В результате смещения по циклу получим новый план (табл.7). План невырожденный. Транспортные расходы

F = (а были равны 650).

Табл.7

Bj

Ai

20

120

20

60

Ui

100

6
    4 100

2

4

0

70

1
    2 10

7
    2 60

-2

50
    2 20
    4 10

2444 1 1111 20

4

0

Vj

2

4

1

4

Будет ли полученный план оптимальным?

Определим для него новые потенциалы:

U1+v2=4, u2+v2=2, u2+v4=2, u3+v1=2, u3+v2=4, u3+v3=1. Положим u1=0, тогда v2=4, u2=-2, v4=4, u3=0, v1= 2, v3=1. Проставим значения найденных потенциалов в табл.7.

Определим оценки свободных клеток:

S11=6-(0+2)=4>0, s13=2-(0+1)=1>0, s14=4-(0+4)=0

S21=1-(-2+2)=1>0, s23=7-(-2+1)=8>0, s34=4-(0+4)=0

Оценки свободных клеток неотрицательны, следовательно, полученный план является оптимальным:

X12=100, x22=10, x24=60, x31=20, x32=10, x33=20

Минимальные транспортные расходы для этого плана f=640.

Все оценки свободных клеток равны нулю. Это свидетельствует о неединственности оптимального плана.

ОТВЕТ.

Согласно оптимальному плану, с первого завода A1 нужно поставить 100м3 перекрытый на вторую строительную площадку B2, с завода А2 - 10м3 на строительную площадку В2 и 60м3 на строительную площадку В4, с завода А3 - на 20 м3 на строительную площадку В1, 10 м3 на строительную площадку В2 и 20 м3 на строительную площадку В3.

Похожие статьи




Пример решения транспортной задачи - Экономико-математические методы

Предыдущая | Следующая