Транспортная задача

Автор работы: Пользователь скрыл имя, 12 Ноября 2012 в 12:22, лабораторная работа

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

У поставщиков A1 , A2 , A3 , A4 , находится соответственно 100 , 170 , 140 , 180 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4 , B5 в количестве 50 , 160 , 130 , 10 , 210 единиц соответственно.

Скачать полностью (192.18 Кб) Сколько стоит заказать работу?
Прикрепленные файлы: 1 файл

задача.doc

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

У поставщиков A1 , A2 , A3 , A4 , находится соответственно 100 , 170 , 140 , 180 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4 , B5 в количестве 50 , 160 , 130 , 10 , 210 единиц соответственно.


Стоимость доставки единицы продукции от поставщика A1 к указанным потребителям равна 13 , 5 , 13 , 1 , 5 ден.ед.


Стоимость доставки единицы продукции от поставщика A2 к указанным потребителям равна 1 , 15 , 1 , 6 , 7 ден.ед.


Стоимость доставки единицы продукции от поставщика A3 к указанным потребителям равна 15 , 6 , 4 , 10 , 5 ден.ед.


Стоимость доставки единицы продукции от поставщика A4 к указанным потребителям равна 2 , 6 , 13 , 3 , 11 ден.ед.


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


Решение :

    

Что мы будем  делать? 
Найдем начальное решение методом Фогеля. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется не оптимальным, используя метод потенциалов, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение.


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


В нашем случае, запасы поставщиков - 590 единиц продукции  больше, чем потребность потребителей - 560 на 30 единиц. Введем в рассмотрение фиктивного потребителя B6, с потребностью в продукции равной 30. Стоимость доставки единицы продукции от всех поставщиков к данному потребителю примем равной нулю.


Маршруты доставки продукции от поставщиков к фиктивному потребителю B6 мы будем рассматривать в последнюю очередь. Не факт, но, скорее всего, это позволит получить более рентабельное начальное решение.


1)

    

Согласно условию  задачи составим таблицу. (тарифы cij располагаются в нижнем правом углу ячейки)


Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

 

13  

-

 

5  

-

 

13  

-

 

1  

-

 

5  

-

 

0  

100

A 2

-

 

1  

-

 

15  

-

 

1  

-

 

6  

-

 

7  

-

 

0  

170

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

-

 

5  

-

 

0  

140

A 4

-

 

2  

-

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

180

Потребность

50

160

130

10

210

30

  

 

2)

    

 

В каждой строке, найдем разность i между двумя ячейками (доступными для выбора) с наименьшими тарифами.

  

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

Поставщик

Потребитель

i

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

 

13  

-

 

5  

-

 

13  

-

 

1  

-

 

5  

-

 

0  

4

A 2

-

 

1  

-

 

15  

-

 

1  

-

 

6  

-

 

7  

-

 

0  

0

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

-

 

5  

-

 

0  

1

A 4

-

 

2  

-

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

1


  

Поставщик

Потребитель

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

 

13  

-

 

5  

-

 

13  

-

 

1  

-

 

5  

-

 

0  


A 2

-

 

1  

-

 

15  

-

 

1  

-

 

6  

-

 

7  

-

 

0  


A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

-

 

5  

-

 

0  


A 4

-

 

2  

-

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  


j

1

1

3

2

0

-



Из полученных разностей выберем наибольшую.


Наибольшей разностью обладает строка 1. В данной строке выберем ячейку A1B4, как обладающую наименьшим тарифом.


Почему? 
Стоимость доставки единицы продукции от поставщика A1 к потребителю B4, как минимум, на 4 ден.ед. меньше чем к другим потребителям (см. левую таблицу).


Запасы поставщика A1 составляют 100 единиц продукции. Потребность потребителя B4 составляет 10 единиц продукции. (см. таблицу пункта 1)


От поставщика A1 к потребителю B4 будем доставлять min = { 100 , 10 } = 10 единиц продукции.


Разместим в  ячейку A1B4 значение равное 10


Мы полностью  удовлетворили потребность потребителя B4. Вычеркиваем столбец 4 таблицы, т.е исключаем его из дальнейшего рассмотрения.


Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

 

13  

-

 

5  

-

 

13  

10

 

1  

-

 

5  

-

 

0  

100

A 2

-

 

1  

-

 

15  

-

 

1  

-

 

6  

-

 

7  

-

 

0  

170

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

-

 

5  

-

 

0  

140

A 4

-

 

2  

-

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

180

Потребность

50

160

130

10

210

30

  

 

3)

    

 

В каждой строке, найдем разность i между двумя ячейками (доступными для выбора) с наименьшими тарифами.

  

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

Поставщик

Потребитель

i

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

 

13  

-

 

5  

-

 

13  

10

 

1  

-

 

5  

-

 

0  

0

A 2

-

 

1  

-

 

15  

-

 

1  

-

 

6  

-

 

7  

-

 

0  

0

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

-

 

5  

-

 

0  

1

A 4

-

 

2  

-

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

4


  

Поставщик

Потребитель

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

 

13  

-

 

5  

-

 

13  

10

 

1  

-

 

5  

-

 

0  


A 2

-

 

1  

-

 

15  

-

 

1  

-

 

6  

-

 

7  

-

 

0  


A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

-

 

5  

-

 

0  


A 4

-

 

2  

-

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  


j

1

1

3

-

0

-


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