Транспортная задача линейного программирования

Автор работы: Пользователь скрыл имя, 13 Марта 2012 в 17:09, курсовая работа

Краткое описание

Встречаются такие варианты транспортной задачи, где условие ai=bj нарушено. В этих случаях говорят о транспортной задаче с неправильным балансом.
Требуется составить такой план перевозок, чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальной.
Рассмотрим транспортную задачу как задачу линейного программирования и составим математическую модель, т. е. запишем целевую функцию и ограничения к ней.

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

1. Введение……………………………………………………………………….3
2. Составление допустимых планов………………………………………….…5
2.1. Метод северо-западного угла………………………………………...5
2.2. Метод минимальной стоимости по строке……………………....….6
2.3. Метод минимальной стоимости по столбцу…………………….…..7
2.4. Метод минимальной стоимости………….…………….………...…..8
2.5. Метод двойственного предпочтения………….……….………...…..9
3. Метод циклических перестановок…………………………...………………10
4. Метод потенциалов………………………………………………………….14
5. Вывод………………………..……………

Скачать целиком (42.52 Кб) Сколько стоит заказать работу?
Содержимое работы - 1 файл

Копия КуРсОвАя .doc

— 342.00 Кб (Скачать файл)

 

 

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

Проверяем план на опорность: (количество заявок + количество запасов – 1) m + n - 1 = 6 + 5 - 1 = 10. Количество базисных клеток 10. Следовательно план является опороным.

Считаем общую стоимость всех перевозок:

L=20*1+4*2+6*8+23*4+26*4+4*14+20*6+9*12+11*9+21*3 =718 условных единиц.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

             

 

2.4.Метод минимальной стоимости

 

В1

В2

В3

В4

В5

В6

Ai

A1

16

8

10

              1

2

3

24

 

 

 

 20

4 

 

A2

            14     

11

5

8

4

8

29

 

 

 

 

23 

6 

A3

14

4

8

10

13

14

30

 

 26

 

 

 

4 

A4

6

            6       

15

5

12

12

29

 20

 

 

 

 

9

A5

16

14

3

4

9

9

32

 

 

 21

 

 

11

Ai

20

26

21

20

27

30

   144

 

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

Проверяем план на опорность: (количество заявок + количество запасов – 1) m + n - 1 = 6 + 5 - 1 = 10. Количество базисных клеток 10. Следовательно план является опороным.

Считаем общую стоимость всех перевозок:

L=20*1+4*2+6*8+23*4+26*4+4*14+20*6+9*12+11*9+21*3 =718 условных единиц.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

В1

В2

В3

В4

В5

В6

Ai

A1

16

8

10

              1

2

3

24

 

 

 

 20

4 

 

A2

            14     

11

5

8

4

8

29

 

 

6

 

23 

 

A3

14

4

8

10

13

14

30

 

 26

4 

 

 

 

A4

6

            6       

15

5

12

12

29

 20

 

 

 

 

9

A5

16

14

3

4

9

9

32

 

 

 11

 

 

21

Ai

20

26

21

20

27

30

   144

 

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

Проверяем план на опорность: (количество заявок + количество запасов – 1) m + n - 1 = 6 + 5 - 1 = 10. Количество базисных клеток 10. Следовательно план является опороным.

Считаем общую стоимость всех перевозок:

L=20*1+4*2+6*5+23*4+26*4+4*8+20*6+9*12+11*3+21*9 =736 условных единиц.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Метод циклических перестановок

 

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

Если цена цикла  больше нуля, то цикл нам не подходит, если меньше, то мы делаем перестановки.

Цикл 1

 

 

В1

В2

В3

В4

В5

В6

Ai

A1

16

8

10

              1

2

3

24

20

-4

 

+ *

 

 

A2

            14     

11

5

8

4

8

29

 

+22

-7

 

 

 

A3

14

4

8

10

13

14

30

 

 

 +14

-16

 

 

A4

6

            6       

15

5

12

12

29

 

 

 

 4

25

 

A5

16

14

3

4

9

9

32

 

 

 

 

 2

30

Ai

20

26

21

20

27

30

   144

 

L0=21*11+16*10+8*11+18*4+13*5+21*12+19*12+16*6+21*10+21*8+24*0=1509 условных единиц

Цена цикла = 1-10+8-5+11-8 = -3 < 0 – делаем перестановки.

q = 4

 

 

 

 

 

 

 

 

 

Цикл 2

 

В1

В2

В3

В4

В5

В6

Ai

A1

16

8

10

              1

2

3

24

20

 

 

-4

+ *

 

A2

            14     

11

5

8

4

8

29

 

26

3

 

 

 

A3

14

4

8

10

13

14

30

 

 

 18

12

 

 

A4

6

            6       

15

5

12

12

29

 

 

 

 +4

-25

 

A5

16

14

3

4

9

9

32

 

 

 

 

 2

30

Ai

20

26

21

20

27

30

   144

 

Считаем общую стоимость всех перевозок:

L1= L0 + цена цикла * q =1509 + (-3*4)= 1497 условных единиц

Цена цикла = Цена цикла = 2-12+5-1 = -6 < 0 – делаем перестановки.

q = 4

Цикл 3

 

В1

В2

В3

В4

В5

В6

Ai

A1

16

8

10

              1

2

3

24

20

 

 

 

4

 

A2

            14     

11

5

8

4

8

29

 

-26

+3

 

 

 

A3

14

4

8

10

13

14

30

 

+* 

 -18

12

 

 

A4

6

            6       

15

5

12

12

29

 

 

 

 8

21

 

A5

16

14

3

4

9

9

32

 

 

 

 

 2

30

Ai

20

26

21

20

27

30

   144

Информация о работе Транспортная задача линейного программирования