Постановка транспортной задачи

Автор работы: Пользователь скрыл имя, 03 Апреля 2013 в 12:10, реферат

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

Транспортная задача ставится следующим образом: имеется m пунктов отправления, в которых сосредоточены запасы каких-то однородных грузов. Имеется n пунктов назначения подавшие заявки соответственно на груза. Известны стоимости р i j перевозки единицы груза от каждого пункта отправления до каждого пункта назначения. Все числа р i j, образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

Содержание

1. Линейная транспортная задача - 3 стр.
2. Составление опорного плана - 6 стр.
3. Метод потенциалов - 7 стр.
3. Список использованной литературы - 15 стр.

Прикрепленные файлы: 1 файл

транспортная задача метод потенциалов.doc

— 192.00 Кб (Скачать документ)

 

v5 = 0 ® u3 = 8, так как u3 + u5 = p35 = 8, ® v4 = -7, так как u3 + v4  = p34 = 1,  ® v3 = -5, так как u3 + v3  = 3, ® u2 = 12  ® v2 = -8, ® v1 = -6  ® u1 = 11.

Симплекс – множители  нужны для того, чтобы найти свободную ячейку (i, j), которая при замене базиса переходит в базисную (это соответствует отысканию разрешающего столбца в симплекс – методе).

Для определения симплекс – множителей мы вносим на свободные  места в таблице значения

ij = pij – ui – vj

(коэффициенты целевой  функции, пересчитанные для свободных  переменных). Если все  ij 0, то базисное решение оптимально. В противном случае мы выбираем произвольное p¢ab < 0, чаще всего наименьшее. Индексом ab помечено свободное переменное хab , которое должно войти в базис. Соответствующую ячейку транспортной таблицы мы отметим знаком +.

Пример 3.

5

6

3

5

9

6

4

7

3

5

2

5

3

1

8




pij

5

       

11

 

6

4

7

   

12

®  

   

3

1

8

8

 

-6

-8

-5

-7

0

   



   

 

5

3

-3

1

-2

®

6

4

7

-2

-7

 

0

5

3

1

8




 

 

Минимальный элемент  –7 ®   (a, b) = (2,5).

Кроме ячейки (a, b) транспортной таблицы, мы пометим значками – и + другие занятые числами ячейки таким образом, чтобы в каждой строке и в каждом столбце транспортной таблицы число знаков + было равно числу знаков -. Это всегда можно сделать единственным образом, причем в каждой строке и в каждом столбце будет содержаться максимум по одному знаку = и по одному  знаку -.

Пример 4.

 

15

         

5

5

5

 

+

®

   

5

10

5

 

 

 

15

       

®

5

5

5-

 

+

     

5+

10

5-


 

Знак + поставлен в ячейке (2,5). Соответственно в последнем  столбце должен быть поставлен знак -,  это можно сделать только в ячейке (3,5). Следовательно, знак + должен быть поставлен в последней строке. В ячейке с числом 10 этого сделать  нельзя, так как тогда в соответствующем столбце не было бы знака -, и д.т.

 

Затем мы определяем минимум  М  из всех элементов, помеченных знаком -, и выбираем ячейку (g, d), где этот минимум достигается.

В нашем примере с М = 5 можно  выбрать (g, d) = (2, 3); при этом (g, d) определяет базисное переменное, которое должно стать свободным, т.е. базисное переменное, соответствующее индексу разрешающей строки симплекс – метода.

 

 

 

20

5

10

10

5

15

15

       

15

5

5

5-

 

+

20

   

5+

10

5-


 

¯

 

15

       

5-

5

   

5+

+

 

10

10

0-


 

¯

 

15-

 

+

   

5

5

   

5

0+

 

10-

10

 

 

¯

 

5

 

10

   

5-

5

 

+

5

10+

   

10-

 

 

¯

5

 

10

   
 

5

 

5

5

15

   

5

 

 

Копт = 150

 

Переход к новой транспортной таблице (замена базиса) происходит следующим  образом:

а). В ячейку (a, b) новой таблицы записывается число М.

б). Ячейка (g, d) остается пустой.

в). В других ячейках  помеченных знаками – или +, число  М вычитается из стоящего в ячейке числа (-) или складывается с ним (+). Результат вносится в соответствующую  ячейку новой таблицы.

г). Непомеченные числа  переносятся в новую таблицу без изменений. Остальные ячейки новой таблицы остаются пустыми.

Пример 5.

15

         

5

5

5-

 

+

®

   

5+

10

5-

 

 

 

15

       

®

5

5

   

5

     

10

10

0


 

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

Пример 6. Ниже воспроизведен  ход решения примера 1.

5

3

-3

1

-2

11

6

4

7

-2

-7

12

0

5

3

1

8

8

-6

-8

-5

-7

0

 

 

5

3

4

8

5

4

6

4

7

5

5

5

-7

-2

3

1

8

8

-1

-1

2

0

0

 

 

5

3

-3

1

5

4

6

4

0

-2

5

5

2

5

3

1

7

1

1

-1

2

0

0

 

 

5

3

3

1

5

4

6

4

3

-2

5

5

2

5

3

1

7

1

1

-1

-1

0

0

 

 

5

1

3

1

3

6

2

4

5

3

5

5

2

3

3

1

5

3

-1

-1

-3

-2

0

 

 

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

 

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

Если дана вырожденная  транспортная таблица (её можно узнать   по     имеющемуся 0, то заменив am на am + ne  и  все  bj  на bj + e , где e >  0 подразумевается очень малым, исправим значения базисных переменных так, что бы для новых ai и bj получилось базисное решение. Это всегда можно сделать единственным способом (как и при отыскании симплекс – множителей).

 

15

       

5

5

   

5

   

10

10

0


 

 

20 + e

5 + e

10 + e

10 + e

5 + e

15

         

15

         

20 + e

         

 

15 + 2e

       

5 - e

5 + e

   

5 - 2e

   

10 + e

10 + e

3e

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