Комплексный метод. Методы решения задач транспортного типа

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

33 страницы (Word-файл)

Фрагмент текста работы

Если – недопустимая точка, уменьшать в два раза расстояния до центра

тяжести, пока   не станет допустимой точкой.

       Проверка окончания поиска :

вычисления оканчиваются, иначе переход к п. II. 1).

Для невыпуклых областей метод расходится.

Задание № 1

Методы решения задач транспортного типа.

4 вариант.

1)  Математическая постановка транспортной задачи.

Имеется четыре поставщика продукции (А1, А2, А3, А4),  в руках которых сосредоточены 24, 14, 19 и 17 единиц соответственно. Необходимо доставить продукцию пятерым потребителям (В1, В2, В3, В4, В5) в количестве 22, 9, 12, 13, 18 единиц. Известна стоимость перевозки единицы груза от i-го поставщика к j-му потребителю.

Стоимость перевозок

Запасы

22

24

25

23

29

24

А1

1

21

10

7

19

14

А2

2

26

18

30

27

19

А3

22

10

29

26

23

17

А4

22

9

12

13

18

В1

В2

В3

В4

В5

 

Потребности

 

Аi=74

Вj=74

Аi=Вj

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

2)  Поиск опорного решения транспортной задачи с помощью следующих методов:

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

Исходная задача:

22

24

25

23

29

24

1

21

10

7

19

14

2

26

18

30

27

19

22

10

29

26

23

17

22

9

12

13

18

74

После преобразований:

22 22

2 24

0

0

0

24

0

7 21

7 10

0

0

14

0

0

5 18

13 30

1 27

19

0

0

0

0

17 23

17

22

9

12

13

18

74

          Стоимость перевозки:   Z=1647

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

В исходной задаче в каждом столбце нахожу минимальный элемент и отмечаю его «*».

22

24

25

23

29

24

1 *

21

10 *

7 *

19 *

14

2

26

18

30

27

19

22

10 *

29

26

23

17

22

9

12

13

18

74

Далее заполняю таблицу, начиная с элементов, помеченных «*». Получаю:

0

0

1 25

13 23

10 29

24

14 1

0

0

0

0

14

8 2

0

11 18

0

0

19

0

9 10

0

0

8 23

17

22

9

12

13

18

74

Стоимость перевозки  Z=1116

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

 Теперь ищу минимумы строк и так же отмечаю их «*»

22 *

24

25

23

29

24

1 **

21

10 *

7 *

19 *

14

2 *

26

18

30

27

19

22

10 **

29

26

23

17

22

9

12

13

18

74


Далее заполняю таблицу, начиная с элементов, помеченных «**», затем «*». В результате получаю:

8 22

0

0

13 23

3 29

24

14 1

0

0

0

0

14

0

0

12 18

0

7 27

19

0

9 10

0

0

8 23

17

22

9

12

13

18

74

Стоимость перевозки Z=1255

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

 


 

2

4

-7

30

27

20

22 22

2 24

0 25

0 23

0 29

24

17

0 1

2 21

12 10

0 7

0 19

14

0

0 2

0 26

0 18

13 30

1 27

19

-4

0 22

0 10

0 29

0 26

17 23

17

22

9

12

13

18

74

 

22

24

13

23

47

0

5 22

2 24

0 25

13 23

0 29

24

-3

0 1

2 21

12 10

0 7

0 19

14

-20

18 2

0 26

5 18

0 30

1 27

19

-24

0 22

0 10

0 29

0 26

17 23

17

22

9

12

13

18

74

 

22

24

26

23

47

0

5 22

4 24

0 25

11 23

0 29

24

-16

0 1

0 21

12 10

2 7

0 19

14

-20

18 2

0 26

0 18

13 30

1 27

19

-24

0 22

0 10

0 29

0 26

17 23

17

22

9

12

13

18

74

 

1

9

10

7

26

15

0 22

4 24

5 25

11 23

0 29

24

0

5 1

0 21

7 10

2 7

0 19

14

1

18 2

0 26

0 18

13 30

1 27

19

-3

0 22

0 10

0 29

0 26

17 23

17

22

9

12

13

18

74

 

1

9

10

7

19

15

0 22

4 24

5 25

11 23

0 29

24

0

4 1

0 21

7 10

2 7

1 19

14

1

19 2

0 26

0 18

13 30

0 27

19

4

0 22

0 10

0 29

0 26

17 23

17

22

9

12

13

18

74

 

1

6

10

7

19

15

0 22

0 24

5 25

11 23

4 29

24

0

4 1

0 21

7 10

2 7

1 19

14

1

19 2

0 26

0 18

13 30

0 27

19

4

0 22

4 10

0 29

0 26

13 23

17

22

9

12

13

18

74

 

1

1

10

7

14

15

0 22

0 24

5 25

10 23

5 29

24

0

4 1

0 21

7 10

3 7

0 19

14

1

19 2

0 26

0 18

13 30

0 27

19

9

0 22

4 10

0 29

0 26

13 23

17

22

9

12

13

18

74

Z=972

4)  Венгерский метод

Находим min по столбцам и вычитаем из всех элементов этого столбца

Матрица C

22

24

25

23

29

24

1

21

10

7

19

14

2

26

18

30

27

19

22

10

29

26

23

17

22

9

12

13

18

74

То же самое, но по строкам

Матрица C'

21

14

15

16

10

24

0

11

0

0

0

14

1

16

8

23

8

19

21

0

19

19

4

17

22

9

12

13

18

74

Матрица C0

11

4

5

6

0

24

0

11

0

0

0

14

0

15

7

22

7

19

21

0

19

19

4

17

22

9

12

13

18

74

Матрица X0

0

0

0

0

16

24

8

3

0

7

2

2

14

0

19

0

0

0

0

19

0

0

9

0

0

0

17

8

22

9

12

13

18

74

0

0

5

11

0

невязки

 


     0=2*74-2*58=32>0 =>переходим к первой итерации

Итерация №1

Матрица C0

 +

 +

 +

11

4

5

6

0

24

8

0*

11

0'

0

0

14

0

  +

0'

15

7

22

7

19

0

21

0

19

19

4

17

8

22

9

12

13

18

74

0

0

5

11

0

невязки

Матрица C0

 +

 +

11

4

5

6

0

24

8

0*

11

0'

0

0

14

0

  +

0'

15

7

22

7

19

0

 +

21

0

19

19

4

17

8

22

9

12

13

18

74

0

0

5

11

0

невязки

Существенных нулей нет.

Ищем невыделенный нуль и с самого начала I этапа

                     Матрица C0

 +

 +

11

4

5

6

0

24

8

0*

11

0'

0

0

14

0

  +

0'

15

7

22

7

19

0

 +

21

0

19

19

4

17

8

22

9

12

13

18

74

0

0

5

11

0

невязки

Т.к. не осталось больше невыд. Нулей, то переходим к III этапу

III этап

 

 +

 +

 

11

4

5

6

0

24

8

 

0*

11

0'

0

0

14

0

  +

 

0'

15

7

22

7

19

0

 +

Матрица C0

21

0

19

19

4

17

8

 

22

9

12

13

18

74

 

0

0

5

11

0

невязки

 

Мин. Элемент среди невыд-х cтрок и столбцов: h=5 

Матрица C'0

 +

 +

6

4

0

1

0

24

8

0*

16

0'

0

5

14

0

  +

0'

20

7

22

12

19

0

 +

16

0

14

14

4

17

8

22

9

12

13

18

74

0

0

5

11

0

невязки

Получили матрицу C1

Переходим к I этапу

I этап

                 Матрица C1

 +

 +

6

4

0'

1

0

24

8

0

16

0

0

5

14

0

0

20

7

22

12

19

0

16

0

14

14

4

17

8

22

9

12

13

18

74

0

0

5

11

0

невязки

Невязка по строке б1=8>0 => переходим ко II этапу

II этап

Цепочка состоит из одного элемента C113=0.   

Находим Q=min(8;5)=5

Матрица X1

0

0

5

0

16

24

3

3

0

7

2

2

14

0

19

0

0

0

0

19

0

0

9

0

0

0

17

8

22

9

12

13

18

74

0

0

0

11

0

невязки

    1=32-2*Q=32-2*5=22>0     Переходим ко второй итерации

Переходим ко второй итерации

Итерация №2

I этап

Матрица C1

    +

 +

     +

 +

6

4

0'

1

0

24

3

0*

16

0

0'

5

14

0

     +

0'

20

7

22

12

19

0

     +

16

0

14

14

4

17

8

22

9

12

13

18

74

0

0

0

11

0

невязки

Т.к не осталось невыд-х нулей, то переходим к III этапу

III этап

Минимальный элемент среди невыд-х строк и столбцов h=1

Матрица C'1

       +

       +

      +

5

4

0

0

0

24

3

0

17

1

0

6

14

0

     +

0

21

8

22

13

19

0

     +

15

0

14

13

4

17

8

22

9

12

13

18

74

0

0

0

11

0

невязки

Получили матрицу C2.

Переходим к I этапу

I этап

Матрица C2

      +

    +

       +

5

4

0

0'

0

24

3

0

17

1

0

6

14

0

   +

0

21

8

22

13

19

0

   +

15

0

14

13

4

17

8

22

9

12

13

18

74

0

0

0

11

0

невязки

Среди невыд-х столбцов находим элемент C14=0, который расположен

в строке с ненулевой невязкой. =>Переходим ко II этапу

II этап

Цепочка состоит из одного элемента C214=0

Находим Q=min(3;11)=3

Матрица X2

0

0

5

3

16

24

0

3

0

7

2

2

14

0

19

0

0

0

0

19

0

0

9

0

0

0

17

8

22

9

12

13

18

74

0

0

0

8

0

невязки

    2==22-2*Q=32-2*3=16>0               Переходим к след. Итерации

Итерация №3

I этап

Матрица C2

      +

      +

    +

       +

5

4

0

0

0

24

3

   +

0

17

1

0

6

14

0

   +

0

21

8

22

13

19

0

   +

15

0

14

13

4

17

8

22

9

12

13

18

74

0

0

0

8

0

невязки

Т.к. не осталось невыд-х нулей, то переходим к III этапу

III этап

Мин-й элемент среди невыд-х строк и столбцов h=13

Матрица C'2

18

17

13

0

13

24

13

30

14

0

19

14

13

34

21

22

26

19

15

0

14

0

4

17

22

9

12

13

18

74

Получили матрицу C3.

Переходим к I этапу

I этап

Матрица C3

      +

      +

    +

       +

18

17

13

0

13

24

3

   +

13

30

14

0

19

14

0

   +

13

34

21

22

26

19

0

   +

15

0

14

0'

4

17

8

22

9

12

13

18

74

0

0

0

8

0

невязки

Среди невыд-х элементов находим элемент C44=0, который расположен в строке с ненулевой невязкой.

Следовательно переходим ко II этапу.

II этап

Цепочка состоит из одного элемента C344=0

Находим Q=min(8;8)=8

Матрица X3

0 22

0 24

5 25

3 23

16 29

24

0

3 1

0 21

7 10

2 7

2 19

14

0

19 2

0 26

0 18

0 30

0 27

19

0

0 22

9 10

0 29

8 26

0 23

17

0

22

9

12

13

18

74

0

0

0

0

0

невязки

   3=3=16-2*Q=16-2*8=0

Следовательно X3 - оптимальный план.

Стоимость перевозки Z=1119

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

Задание  № 2.

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

22 вариант.

1)  Математическая постановка задачи линейного программирования.

Дана линейная функция

                                     6х1 + 7х2 ® max

и система линейных ограничений:

 


                                       6х1 + 11х2 £ 66

                                       12х1 + 7х2 £ 84

                                       х1³ 0, х2 ³0

Необходимо найти такие неотрицательные значения х1 и х2, которые удовлетворяют системе ограничений и доставляют линейной функции минимальное значение.

2)  Графическая интерпретация задачи линейного программирования.

1) 6x1+11x2 =66

x1

0

11

x2

6

0

2)12x1+7x2 =84

x1

0

7

x2

12

0

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

Точка А – точка максимального значения функции.

Координаты точки А находятся при решении системы линейных уравнений.

 6x1+11x2 =66

 12x1+7x2 =84

x1=15,4/3=5,13

x2=16/5=3,2

Fmax=6*5,13+7*3,2=798/15=53,2

3)  Двойственная задача линейного программирования и ее графическая интерпретация.

66y1+84y2->min

6y1+12y2>=6

11y1+7y2>=7

1)6y1+12y2=6

y1

0

1

y2

1/2

0

2)11y1+7y2=7

y1

0

11/7

y2

1

0

В результате получила область допустимых планов.

Координаты точки А находятся при решении следующей системы линейных уравнений.

6y1+12y2=6

11y1+7y2=7

y1=7/15=2,8

y2=4/15=0,27

Fmin=66*2,8+84*0,27=798/15=266/5 =53,2

4)  Симплекс-метод

а) прямая задача

6x1+7x2  ->max

 


6x1+11x2 <=66

12x1+7x2 <=84

x1>=0, x2>=0

Приводим задачу к канонической форме, а целевую функцию к min:

6x1+11x2 +x3=66

12x1+7x2 +x4=84

x1>=0, x2>=0

V= -f =  -6x1 -7x->min

Исходный опорный план:

X0=(66, 84, 0, 0)

Строим исходную симплекс-таблицу

i

Базис

C

A0

C1=-6

C2=-7

C3=0

C4=0

базиса

A1

A2

A3

A4

1

A3

0

66

6

11

1

0

2

A4

0

84

12

7

0

1

m+1

Uj-Cj

0

6

7

0

0

Исходный опорный план не оптимален, т.к. в (m+1) строке 2 положительных элемента

O01=min(66/6;84/12)=7

O01*(U1-C1)=7*6=42

O02=min(66/11;84/7)=6

O02*(U2-C2)=6*7=42

maxO0j(Uj-Cj)=max(42;42)=42

За разрешающий элемент возьмем элемент 12 на пересечении 2-ой строки и 1-го столбца(A1)

II симплекс-таблица

i

Базис

C

A0

C1=-6

C2=-7

C3=0

C4=0

базиса

A1

A2

A3

A4

1

A3

0

24

0

15/2

1

-1/2

2

A1

-6

7

1

7/12

0

1/12

m+1

Uj-Cj

-42

0

7/2

0

-1/2

Второй опорный план:

X1=(7, 0, 24, 0)

Он не оптимален,

т.к. в (m+1) строке 1 положительный элемент

За разрешающий элемент возьмем элемент 15/2 на пересечении 1-ой строки и 2-го столбца(A2)

III симплекс-таблица

i

Базис

C

A0

C1=-6

C2=-7

C3=0

C4=0

базиса

A1

A2

A3

A4

1

A2

-7

16/5

0

1

2/15

-1/15

2

A1

-6

77/15

1

0

-7/90

11/90

m+1

Uj-Cj

-266/5

0

0

-7/15

-4/15

Третий опорный план:

X2=(77/15, 16/5, 0, 0)

Он оптимален, т.к. в (m+1) строке нет положительных элементов

fmax= -V = 266/5=53,2

Значения целевой функции, найденной графическим и симплекс методами совпадают.

Следовательно решение верно.

б) двойственная задача

66y1+84y2->min

 


6y1+12y2>=6

11y1+7y2>=7

Приводим задачу к канонической форме, а целевую функцию к min:

6y1+12y2+y3=6

11y1+7y2+y4=7

V= -f =  -66y1 -84y->max

Исходный опорный план:

Y0=(6, 7, 0, 0)

Строим исходную симплекс-таблицу

i

Базис

C

A0

C1=-66

C2=-84

C3=0

C4=0

базиса

A1

A2

A3

A4

1

A3

0

6

6

12

1

0

2

A4

0

7

11

7

0

1

m+1

Uj-Cj

0

66

84

0

0

Исходный опорный план не оптимален, т.к. в (m+1) строке 2 положительных элемента

O01=min(6/6;7/11)=7/11

O01*(U1-C1)=7/11*66=42

O02=min(6/12;7/7)=6/12=1/2

O02*(U2-C2)=1/2*84=42

maxO0j(Uj-Cj)=max(42;42)=42

За разрешающий элемент возьмем элемент 12 на пересечении 1-ой строки и 2-го столбца(A2)

II симплекс-таблица

i

Базис

C

A0

C1=-66

C2=-84

C3=0

C4=0

базиса

A1

A2

A3

A4

1

A2

-84

1/2

1/2

1

1/12

0

2

A4

0

7/2

15/2

0

-7/12

1

m+1

Uj-Cj

-42

24

0

-7

0

Второй опорный план:

Y1=(0, 1/2, 0, 7/2)

Он не оптимален,

т.к. в (m+1) строке 1 положительный элемент

За разрешающий элемент возьмем элемент 15/2 на пересечении 2-ой строки и 1-го столбца(A1)

III симплекс-таблица

i

Базис

C

A0

C1=-66

C2=-84

C3=0

C4=0

базиса

A1

A2

A3

A4

1

A2

-84

4/15

0

1

11/90

-1/15

2

A1

-66

7/15

1

0

-7/90

2/15

m+1

Uj-Cj

-266/5

0

0

-77/15

-16/15

Третий опорный план:

Y2=(7/15, 4/15, 0, 0)

Он оптимален, т.к. в (m+1) строке нет положительных элементов

fmin= -V = 266/5=53,2

Значения целевой функции, найденной графическим, прямым и двойственным симплекс методами совпадают.

Следовательно решение верно.

5)  Сравнивание полученных решений с графическим (п.2, п.3)

Результаты, полученные  при решении прямой и двойственной задачи

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

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