Задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления

Страницы работы

Содержание работы

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

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

Метод северо-западного угла

На каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз или полностью удовлетворяется потребность.

14

25

18

19

23

23

23

0

0

0

0

2

17

16

24

2

25

10

11

4

0

0

29

3

7

15

22

25

0

0

7

11

7

5

20

17

23

10

27

0

0

0

0

27

33

11

11

11

34

100=100

W=23*14+10*2+11*17+4*16+7*7+11*15+7*22+27*10=1231

Метод минимального элемента

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

14

25

18

19

23

23

23

0

0

0

0

2

17

16

24

2

25

10

0

0

0

15

29

3

7

15

22

25

0

11

11

3

0

5

20

17

23

10

27

0

0

0

8

19

33

11

11

11

34

100=100

W=23*14+10*2+15*2+11*3+11*7+3*15+8*23+19*10=901

Метод двойного предпочтения

            Алгоритм аналогичен предыдущему методу, только минимальный элемент находим в каждой строке и в каждом столбце, заполнение ячеек начинается с ячеек, в которых элемент является минимальным как в строке, так и в столбце.

14

25

18

19

23*

23

8

0

0

8

7

2*

17

16*

24

2*

25

25

0

0

0

0

29

3*

7

15

22

25

0

11

11

3

0

5

20

17*

23

10*

27

0

0

0

0

27

33

11

11

11

34

100=100

W=8*14+25*2+11*3+11*7+8*19+3*15+7*23+27*10=900

Метод потенциалов

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче.

            Заполним таблицу методом северо-западного угла. Потенциал строки или столбца с наибольшим количеством элементов примем равным нулю. Подсчитаем потенциалы по заполненным ячейкам, используя формулу cij=ui+vj, где cij – стоимость перевозки единицы груза, ui – потенциал строки, vj – потенциал столбца. Уменьшаем стоимость транспортировки, перемещая груз в ячейки с наименьшими стоимостями.  Повторяем цикл до тех пор, пока во всех пустых клетках не будет выполняться условие cijui+vj .

v1=-7

v2=8

v3=7

v4=11

v5=7

u1=21

14

25

18

19

23

23

23

u2=9

2

17

16

24

2

25

10

11

4

u3=0

29

3

7

15

22

25

7

11

7

u4=3

5

20

17

23

10

27

27

33

11

11

11

34

100=100

v1=2

v2=17

v3=16

v4=29

v5=2

u1=12

14

25

18

19

23

23

23

u2=0

2

17

16

24

2

25

10

4

4

7

u3=-14

29

3

7

15

22

25

7

7

11

u4=8

5

20

17

23

10

27

27

33

11

11

11

34

100=100

Похожие материалы

Информация о работе