Задачи по "Математике"

Автор работы: Пользователь скрыл имя, 23 Марта 2012 в 07:33, задача

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

У поставщиков A1 , A2 , A3 , находится соответственно 9 , 16 , 5 единиц однотипной продукции, которая должна быть
доставлена потребителям B1 , B2 , B3 , B4 в количествах 11 , 7 , 8 , 4 единиц соответственно.

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

Стоимость доставки единицы продукции от поставщика A2 к указанным потребителям равна 8 , 3 , 9 , 2 ден.ед.

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

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

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

транспортная.docx

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

4) Задача :

   

У поставщиков A1 , A2 , A3 , находится соответственно 9 , 16 , 5 единиц однотипной продукции, которая должна быть

доставлена потребителям B1 , B2 , B3 , B4 в количествах 11 , 7 , 8 , 4 единиц соответственно.


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


Стоимость доставки единицы продукции от поставщика A2 к указанным потребителям равна 8 , 3 , 9 , 2 ден.ед.


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


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

стоимость доставки.


Решение :

   

 

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

суммарной потребности  потребителей. Проверим это условие.


В нашем случае, потребность всех потребителей - 30 единиц продукции равна запасам всех поставщиков .


Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

5

 

2


-

 

5


-

 

8


4

 

1


9

A 2

6

 

8


7

 

3


3

 

9


-

 

2


16

A 3

-

 

7


-

 

4


5

 

6


-

 

3


5

Потребность

11

7

8

4

 

 

Заполненные нами ячейки будем называть базисными, остальные - свободными.


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

равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.


Количество базисных ячеек (задействованных маршрутов) равно 6, что и требовалось.


Мы нашли начальное  решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.


S0 = 2 * 5 + 1 * 4 + 8 * 6 + 3 * 7 + 9 * 3 + 6 * 5 = 140 ден. ед.


Общие затраты на доставку всей продукции, для начального решения , составляют 140 ден. ед. .


Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем:


·  Находим потенциалы поставщиков и потребителей для имеющегося решения.


·  Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.


·  Выбираем свободную ячейку (с отрицательной оценкой), выбор которой, позволяет максимально снизить общую

стоимость доставки всей продукции на данном шаге решения.


·  Находим новое решение, как минимум, не хуже предыдущего.


·  Вычисляем общую стоимость доставки всей продукции для нового решения.


Шаг 1

ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.


Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика. 
Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя. 
Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна

тарифу данного  маршрута.  
(ui + vj = cij, где cij - тариф клетки AiBj)  
Поскольку, число базисных клеток - 6, а общее количество потенциалов равно 7, то для однозначного определения

потенциалов, значение одного из них можно выбрать произвольно.

 

 

 

 


Примем u2 = 0.


v1 + u2 = c21

v1 + u2 = 8

v1 = 8 - 0 = 8


v2 + u2 = c22

v2 + u2 = 3

v2 = 3 - 0 = 3


v3 + u2 = c23

v3 + u2 = 9

v3 = 9 - 0 = 9


v3 + u3 = c33

v3 + u3 = 6

u3 = 6 - 9 = -3


v1 + u1 = c11

v1 + u1 = 2

u1 = 2 - 8 = -6


v4 + u1 = c14

v4 + u1 = 1

v4 = 1 - ( -6 ) = 7

Поставщик

Потребитель

U j

B 1

B 2

B 3

B 4

A 1

5

 

2


-

 

5


-

 

8


4

 

1


u 1 = -6

A 2

6

 

8


7

 

3


3

 

9


-

 

2


u 2 = 0

A 3

-

 

7


-

 

4


5

 

6


-

 

3


u 3 = -3

V i

v 1 = 8

v 2 = 3

v 3 = 9

v 4 = 7

 

Найдем оценки свободных  ячеек следующим образом (в таблице  они располагаются в нижнем левом  углу ячейки):


12 = c12 - ( u1 + v2 ) = 5 - ( -6 + 3 ) = 8


13 = c13 - ( u1 + v3 ) = 8 - ( -6 + 9 ) = 5


24 = c24 - ( u2 + v4 ) = 2 - ( 0 + 7 ) = -5


31 = c31 - ( u3 + v1 ) = 7 - ( -3 + 8 ) = 2


32 = c32 - ( u3 + v2 ) = 4 - ( -3 + 3 ) = 4


34 = c34 - ( u3 + v4 ) = 3 - ( -3 + 7 ) = -1

Поставщик

Потребитель

U j

B 1

B 2

B 3

B 4

A 1

5

 

2


-

8

5


-

5

8


4

 

1


u 1 = -6

A 2

6

 

8


7

 

3


3

 

9


-

-5

2


u 2 = 0

A 3

-

2

7


-

4

4


5

 

6


-

-1

3


u 3 = -3

V i

v 1 = 8

v 2 = 3

v 3 = 9

v 4 = 7

 


 

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


Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

9

 

2


-

 

5


-

 

8


-

 

1


9

A 2

2

 

8


7

 

3


3

 

9


4

 

2


16

A 3

-

 

7


-

 

4


5

 

6


-

 

3


5

Потребность

11

7

8

4

 

Шаг 2

ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.


Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика. 
Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя. 
Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна

тарифу данного  маршрута.  
(ui + vj = cij, где cij - тариф клетки AiBj)  
Поскольку, число базисных клеток - 6, а общее количество потенциалов равно 7, то для однозначного определения

потенциалов, значение одного из них можно выбрать произвольно.

 

 

 

 

 

 

 

 

 

 


Примем u2 = 0.


v1 + u2 = c21

v1 + u2 = 8

v1 = 8 - 0 = 8


v2 + u2 = c22

v2 + u2 = 3

v2 = 3 - 0 = 3


v3 + u2 = c23

v3 + u2 = 9

v3 = 9 - 0 = 9


v4 + u2 = c24

v4 + u2 = 2

v4 = 2 - 0 = 2


v3 + u3 = c33

v3 + u3 = 6

u3 = 6 - 9 = -3


v1 + u1 = c11

v1 + u1 = 2

u1 = 2 - 8 = -6

Поставщик

Потребитель

U j

B 1

B 2

B 3

B 4

A 1

9

 

2


-

 

5


-

 

8


-

 

1


u 1 = -6

A 2

2

 

8


7

 

3


3

 

9


4

 

2


u 2 = 0

A 3

-

 

7


-

 

4


5

 

6


-

 

3


u 3 = -3

V i

v 1 = 8

v 2 = 3

v 3 = 9

v 4 = 2

 

Найдем оценки свободных  ячеек следующим образом (в таблице  они располагаются в нижнем левом  углу ячейки):


12 = c12 - ( u1 + v2 ) = 5 - ( -6 + 3 ) = 8


13 = c13 - ( u1 + v3 ) = 8 - ( -6 + 9 ) = 5


14 = c14 - ( u1 + v4 ) = 1 - ( -6 + 2 ) = 5


31 = c31 - ( u3 + v1 ) = 7 - ( -3 + 8 ) = 2


32 = c32 - ( u3 + v2 ) = 4 - ( -3 + 3 ) = 4


34 = c34 - ( u3 + v4 ) = 3 - ( -3 + 2 ) = 4

Поставщик

Потребитель

U j

B 1

B 2

B 3

B 4

A 1

9

 

2


-

8

5


-

5

8


-

5

1


u 1 = -6

A 2

2

 

8


7

 

3


3

 

9


4

 

2


u 2 = 0

A 3

-

2

7


-

4

4


5

 

6


-

4

3


u 3 = -3

V i

v 1 = 8

v 2 = 3

v 3 = 9

v 4 = 2

 


 

Все оценки свободных  ячеек положительные, следовательно, найдено оптимальное решение.


Ответ:


X опт =

9

0

0

0

2

7

3

4

0

0

5

0


 

Smin = 2 * 9 + 8 * 2 + 3 * 7 + 9 * 3 + 2 * 4 + 6 * 5 = 120


 


Информация о работе Задачи по "Математике"