Главная » Банк рефератов » Методы оптимальных решений » Задачи »

Задача по методам оптимальных решений (Задачи 2.5.)

Задача по методам оптимальных решений (Задачи 2.5.)
Дисциплина: Методы оптимальных решений
Вид работы: Задача
Тема: Задача по методам оптимальных решений (Задачи 2.5.)
Вуз: не указан

Задача № 2

Задачи 2.5.

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

Числовые данные для решения содержатся ниже в матрице планирования (повариантно).

Требуется:

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

Определить, что произойдет с оптимальным планом, если изменятся условия перевозок: а) появится запрет на перевозки от первого карьера до второго участка работ; б) по этой коммуникации будет ограничен объем перевозок 3 тоннами.

Матрица планирования:

Участок работ

Карьер

В1

В2

В3

В4

В5

Предложение

А1

3

4

5

15

24

15

А2

19

2

22

4

13

15

А3

20

27

1

17

19

15

Потребности

11

11

11

16

11

 

Решение

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

В нашем случае, запасы поставщиков - 45 единиц продукции меньше, чем потребность потребителей - 60 на 15 единиц. Введем в рассмотрение фиктивного поставщика A4, с запасом продукции равным 15. Стоимость доставки единицы продукции от данного поставщика ко всем потребителям примем равной нулю.

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

 

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

A 1

-

  

3  

 

 

-

  

4  

 

 

-

  

5  

 

 

-

  

15  

 

 

-

  

24  

 

 

15

A 2

-

  

19  

 

 

-

  

2  

 

 

-

  

22  

 

 

-

  

4  

 

 

-

  

13  

 

 

15

A 3

-

  

20  

 

 

-

  

27  

 

 

-

  

1  

 

 

-

  

17  

 

 

-

  

19  

 

 

15

A 4

-

  

0  

 

 

-

  

0  

 

 

-

  

0  

 

 

-

  

0  

 

 

-

  

0  

 

 

15

Потребность

11

11

11

16

11

 

Минимальный элемент матрицы тарифов находится в ячейке A3B3 и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B3 наиболее рентабельный.

Запасы поставщика A3 составляют 15 единиц продукции. Потребность потребителя B3 составляет 11 единиц продукции. (см. таблицу пункта 1)

От поставщика A3 к потребителю B3 будем доставлять min = { 15 , 11 } = 11 единиц продукции.

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

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

A 1

-

  

3  

 

 

-

  

4  

 

 

-

  

5  

 

 

-

  

15  

 

 

-

  

24  

 

 

15

A 2

-

  

19  

 

 

-

  

2  

 

 

-

  

22  

 

 

-

  

4  

 

 

-

  

13  

 

 

15

A 3

-

  

20  

 

 

-

  

27  

 

 

11

  

1  

 

 

-

  

17  

 

 

-

  

19  

 

 

15

A 4

-

  

0  

 

 

-

  

0  

 

 

-

  

0  

 

 

-

  

0  

 

 

-

  

0  

 

 

15

Потребность

11

11

11

16

11

 

И т.д.

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

A 1

11

  

3  

 

 

-

  

4  

 

 

-

  

5  

 

 

4

  

15  

 

 

-

  

24  

 

 

15

A 2

-

  

19  

 

 

11

  

2  

 

 

-

  

22  

 

 

4

  

4  

 

 

-

  

13  

 

 

15

A 3

-

  

20  

 

 

-

  

27  

 

 

11

  

1  

 

 

4

  

17  

 

 

-

  

19  

 

 

15

A 4

-

  

0  

 

 

-

  

0  

 

 

-

  

0  

 

 

4

  

0  

 

 

11

  

0  

 

 

15

Потребность

11

11

11

16

11

 

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

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

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

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

S0 = 3 * 11 + 15 * 4 + 2 * 11 + 4 * 4 + 1 * 11 + 17 * 4 + 0 * 4 + 0 * 11 = 210 ден. ед.

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

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij - тариф клетки AiBj)

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

Примем v4 = 0.

 

v4 + u1 = c14

v4 + u1 = 15

u1 = 15 - 0 = 15

v4 + u2 = c24

v4 + u2 = 4

u2 = 4 - 0 = 4

v4 + u3 = c34

v4 + u3 = 17

u3 = 17 - 0 = 17

v4 + u4 = c44

v4 + u4 = 0

u4 = 0 - 0 = 0

v5 + u4 = c45

v5 + u4 = 0

v5 = 0 - 0 = 0

 

v1 + u1 = c11

v1 + u1 = 3

v1 = 3 - 15 = -12

v2 + u2 = c22

v2 + u2 = 2

v2 = 2 - 4 = -2

 

v3 + u3 = c33

v3 + u3 = 1

v3 = 1 - 17 = -16

 

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

 

12 = c12 - ( u1 + v2 ) = 4 - ( 15 + ( -2 ) ) = -9

 

 

13 = c13 - ( u1 + v3 ) = 5 - ( 15 + ( -16 ) ) = 6

 

 

15 = c15 - ( u1 + v5 ) = 24 - ( 15 + 0 ) = 9

 

 

21 = c21 - ( u2 + v1 ) = 19 - ( 4 + ( -12 ) ) = 27

 

 

23 = c23 - ( u2 + v3 ) = 22 - ( 4 + ( -16 ) ) = 34

 

 

25 = c25 - ( u2 + v5 ) = 13 - ( 4 + 0 ) = 9

 

 

31 = c31 - ( u3 + v1 ) = 20 - ( 17 + ( -12 ) ) = 15

 

 

32 = c32 - ( u3 + v2 ) = 27 - ( 17 + ( -2 ) ) = 12

 

 

35 = c35 - ( u3 + v5 ) = 19 - ( 17 + 0 ) = 2

 

 

41 = c41 - ( u4 + v1 ) = 0 - ( 0 + ( -12 ) ) = 12

 

 

42 = c42 - ( u4 + v2 ) = 0 - ( 0 + ( -2 ) ) = 2

 

 

43 = c43 - ( u4 + v3 ) = 0 - ( 0 + ( -16 ) ) = 16

 

Поставщик

Потребитель

U j

B 1

B 2

B 3

B 4

B 5

A 1

11

  

3  

 

 

-

  -9

4  

 

 

-

  6

5  

 

 

4

  

15  

 

 

-

  9

24  

 

 

u 1 = 15

A 2

-

  27

19  

 

 

11

  

2  

 

 

-

  34

22  

 

 

4

  

4  

 

 

-

  9

13  

 

 

u 2 = 4

A 3

-

  15

20  

 

 

-

  12

27  

 

 

11

  

1  

 

 

4

  

17  

 

 

-

  2

19  

 

 

u 3 = 17

A 4

-

  12

0  

 

 

-

  2

0  

 

 

-

  16

0  

 

 

4

  

0  

 

 

11

  

0  

 

 

u 4 = 0

V i

v 1 = -12

v 2 = -2

v 3 = -16

v 4 = 0

v 5 = 0

 

Оценка свободной ячейки A1B2 (незадействованного маршрута) отрицательная (12 =-9) , следовательно решение не является оптимальным.

Построим цикл для выбранной ячейки A1B2:

Ячейки образующие цикл для свободной ячейки A1B2 :

A1B2 , A1B4 , A2B4 , A2B2

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

A 1

11

  

3  

 

 

4

  

4  

 

 

-

  

5  

 

 

-

  

15  

 

 

-

  

24  

 

 

15

A 2

-

  

19  

 

 

7

  

2  

 

 

-

  

22  

 

 

8

  

4  

 

 

-

  

13  

 

 

15

A 3

-

  

20  

 

 

-

  

27  

 

 

11

  

1  

 

 

4

  

17  

 

 

-

  

19  

 

 

15

A 4

-

  

0  

 

 

-

  

0  

 

 

-

  

0  

 

 

4

  

0  

 

 

11

  

0  

 

 

15

Потребность

11

11

11

16

11

 

Общие расходы на доставку продукции от поставщиков к потребителям изменятся на

4 * 4 - 15 * 4 + 4 * 4 - 2 * 4 = ( 4 - 15 + 4 - 2 ) * 4 = -9 * 4   ден. ед.

Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 210 + ( - 36 ) = 174 ден. ед. .

Примем v4 = 0.

 

v4 + u2 = c24

v4 + u2 = 4

u2 = 4 - 0 = 4

v4 + u3 = c34

v4 + u3 = 17

u3 = 17 - 0 = 17

v4 + u4 = c44

v4 + u4 = 0

u4 = 0 - 0 = 0

v5 + u4 = c45

v5 + u4 = 0

v5 = 0 - 0 = 0

v2 + u2 = c22

v2 + u2 = 2

v2 = 2 - 4 = -2

v3 + u3 = c33

v3 + u3 = 1

v3 = 1 - 17 = -16

v2 + u1 = c12

v2 + u1 = 4

u1 = 4 - ( -2 ) = 6

v1 + u1 = c11

v1 + u1 = 3

v1 = 3 - 6 = -3

13 = c13 - ( u1 + v3 ) = 5 - ( 6 + ( -16 ) ) = 15

 

14 = c14 - ( u1 + v4 ) = 15 - ( 6 + 0 ) = 9

 

15 = c15 - ( u1 + v5 ) = 24 - ( 6 + 0 ) = 18

 

21 = c21 - ( u2 + v1 ) = 19 - ( 4 + ( -3 ) ) = 18

 

23 = c23 - ( u2 + v3 ) = 22 - ( 4 + ( -16 ) ) = 34

 

25 = c25 - ( u2 + v5 ) = 13 - ( 4 + 0 ) = 9

 

31 = c31 - ( u3 + v1 ) = 20 - ( 17 + ( -3 ) ) = 6

 

32 = c32 - ( u3 + v2 ) = 27 - ( 17 + ( -2 ) ) = 12

 

35 = c35 - ( u3 + v5 ) = 19 - ( 17 + 0 ) = 2

 

41 = c41 - ( u4 + v1 ) = 0 - ( 0 + ( -3 ) ) = 3

 

42 = c42 - ( u4 + v2 ) = 0 - ( 0 + ( -2 ) ) = 2

 

43 = c43 - ( u4 + v3 ) = 0 - ( 0 + ( -16 ) ) = 16

 

Поставщик

Потребитель

U j

B 1

B 2

B 3

B 4

B 5

A 1

11

  

3  

 

 

4

  

4  

 

 

-

  15

5  

 

 

-

  9

15  

 

 

-

  18

24  

 

 

u 1 = 6

A 2

-

  18

19  

 

 

7

  

2  

 

 

-

  34

22  

 

 

8

  

4  

 

 

-

  9

13  

 

 

u 2 = 4

A 3

-

  6

20  

 

 

-

  12

27  

 

 

11

  

1  

 

 

4

  

17  

 

 

-

  2

19  

 

 

u 3 = 17

A 4

-

  3

0  

 

 

-

  2

0  

 

 

-

  16

0  

 

 

4

  

0  

 

 

11

  

0  

 

 

u 4 = 0

V i

v 1 = -3

v 2 = -2

v 3 = -16

v 4 = 0

v 5 = 0

 

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

 решение.

Ответ:

X опт =

 

11

4

0

0

0

 

0

7

0

8

0

0

0

11

4

0

0

0

0

4

11

Smin = 3 * 11 + 4 * 4 + 2 * 7 + 4 * 8 + 1 * 11 + 17 * 4 + 0 * 4 + 0 * 11 = 174

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

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

Чтобы полностью ознакомиться с контрольной, скачайте файл!

Скачать работу можно на сайте для ознакомления по теме: Задача по методам оптимальных решений (Задачи 2.5.)!

0

Размер: 31.92K
Скачано: 79
Скачать


Для скачивания данной работы требуется 1 балл (получить баллы). Этот балл будет зачислен автору в качестве вознаграждения.


Расскажите другим о работе:

Если работа, по Вашему мнению, плохого качества, или она Вам уже встречалась, сообщите об этом нам.


Добавление отзыва к работе

Добавить отзыв Вы сможете после скачивания работы.