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

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

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

Раздел: Бесплатные рефераты по методам оптимальных решений

Вуз: не указан

Задача № 2

Задачи 2.5.

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

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

Требуется:

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

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

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

Участок работ Карьер	В₁	В₂	В₃	В₄	В₅	Предложение
А₁	3	4	5	15	24	15
А₂	19	2	22	4	13	15
А₃	20	27	1	17	19	15
Потребности	11	11	11	16	11

Решение

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

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

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	3

-
	4

-
	5

-
	15

-
	24

A ₂

-
	19

-
	2

-
	22

-
	4

-
	13

A ₃

-
	20

-
	27

-
	1

-
	17

-
	19

A ₄

-
	0

-
	0

-
	0

-
	0

-
	0

Потребность

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

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

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

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

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	3

-
	4

-
	5

-
	15

-
	24

A ₂

-
	19

-
	2

-
	22

-
	4

-
	13

A ₃

-
	20

-
	27

11
	1

-
	17

-
	19

A ₄

-
	0

-
	0

-
	0

-
	0

-
	0

Потребность

И т.д.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

11
	3

-
	4

-
	5

4
	15

-
	24

A ₂

-
	19

11
	2

-
	22

4
	4

-
	13

A ₃

-
	20

-
	27

11
	1

4
	17

-
	19

A ₄

-
	0

-
	0

-
	0

4
	0

11
	0

Потребность

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

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

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

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

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

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

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

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

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

(u_i + v_j = c_ij, где c_ij - тариф клетки A_iB_j)

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

Примем v₄ = 0.
v₄ + u₁ = c₁₄		v₄ + u₁ = 15				u₁ = 15 - 0 = 15
v₄ + u₂ = c₂₄	v₄ + u₂ = 4				u₂ = 4 - 0 = 4
v₄ + u₃ = c₃₄	v₄ + u₃ = 17				u₃ = 17 - 0 = 17
v₄ + u₄ = c₄₄	v₄ + u₄ = 0				u₄ = 0 - 0 = 0
v₅ + u₄ = c₄₅	v₅ + u₄ = 0		v₅ = 0 - 0 = 0
v₁ + u₁ = c₁₁	v₁ + u₁ = 3		v₁ = 3 - 15 = -12
v₂ + u₂ = c₂₂	v₂ + u₂ = 2		v₂ = 2 - 4 = -2
v₃ + u₃ = c₃₃	v₃ + u₃ = 1			v₃ = 1 - 17 = -16

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

₁₂ = c₁₂ - ( u₁ + v₂ ) = 4 - ( 15 + ( -2 ) ) = -9

₁₃ = c₁₃ - ( u₁ + v₃ ) = 5 - ( 15 + ( -16 ) ) = 6

₁₅ = c₁₅ - ( u₁ + v₅ ) = 24 - ( 15 + 0 ) = 9

₂₁ = c₂₁ - ( u₂ + v₁ ) = 19 - ( 4 + ( -12 ) ) = 27

₂₃ = c₂₃ - ( u₂ + v₃ ) = 22 - ( 4 + ( -16 ) ) = 34

₂₅ = c₂₅ - ( u₂ + v₅ ) = 13 - ( 4 + 0 ) = 9

₃₁ = c₃₁ - ( u₃ + v₁ ) = 20 - ( 17 + ( -12 ) ) = 15

₃₂ = c₃₂ - ( u₃ + v₂ ) = 27 - ( 17 + ( -2 ) ) = 12

₃₅ = c₃₅ - ( u₃ + v₅ ) = 19 - ( 17 + 0 ) = 2

₄₁ = c₄₁ - ( u₄ + v₁ ) = 0 - ( 0 + ( -12 ) ) = 12

₄₂ = c₄₂ - ( u₄ + v₂ ) = 0 - ( 0 + ( -2 ) ) = 2

₄₃ = c₄₃ - ( u₄ + v₃ ) = 0 - ( 0 + ( -16 ) ) = 16

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

11
	3

-
-9	4

-
6	5

4
	15

-
9	24

u ₁ = 15

A ₂

-
27	19

11
	2

-
34	22

4
	4

-
9	13

u ₂ = 4

A ₃

-
15	20

-
12	27

11
	1

4
	17

-
2	19

u ₃ = 17

A ₄

-
12	0

-
2	0

-
16	0

4
	0

11
	0

u ₄ = 0

V _i

v ₁ = -12

v ₂ = -2

v ₃ = -16

v ₄ = 0

v ₅ = 0

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

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

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

A₁B₂ , A₁B₄ , A₂B₄ , A₂B₂

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

11
	3

4
	4

-
	5

-
	15

-
	24

A ₂

-
	19

7
	2

-
	22

8
	4

-
	13

A ₃

-
	20

-
	27

11
	1

4
	17

-
	19

A ₄

-
	0

-
	0

-
	0

4
	0

11
	0

Потребность

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

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

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

Примем v₄ = 0.
v₄ + u₂ = c₂₄		v₄ + u₂ = 4	u₂ = 4 - 0 = 4
v₄ + u₃ = c₃₄	v₄ + u₃ = 17	u₃ = 17 - 0 = 17
v₄ + u₄ = c₄₄	v₄ + u₄ = 0	u₄ = 0 - 0 = 0
v₅ + u₄ = c₄₅	v₅ + u₄ = 0	v₅ = 0 - 0 = 0
v₂ + u₂ = c₂₂	v₂ + u₂ = 2	v₂ = 2 - 4 = -2
v₃ + u₃ = c₃₃	v₃ + u₃ = 1	v₃ = 1 - 17 = -16
v₂ + u₁ = c₁₂	v₂ + u₁ = 4	u₁ = 4 - ( -2 ) = 6
v₁ + u₁ = c₁₁	v₁ + u₁ = 3	v₁ = 3 - 6 = -3
₁₃ = c₁₃ - ( u₁ + v₃ ) = 5 - ( 6 + ( -16 ) ) = 15
₁₄ = c₁₄ - ( u₁ + v₄ ) = 15 - ( 6 + 0 ) = 9
₁₅ = c₁₅ - ( u₁ + v₅ ) = 24 - ( 6 + 0 ) = 18
₂₁ = c₂₁ - ( u₂ + v₁ ) = 19 - ( 4 + ( -3 ) ) = 18
₂₃ = c₂₃ - ( u₂ + v₃ ) = 22 - ( 4 + ( -16 ) ) = 34
₂₅ = c₂₅ - ( u₂ + v₅ ) = 13 - ( 4 + 0 ) = 9
₃₁ = c₃₁ - ( u₃ + v₁ ) = 20 - ( 17 + ( -3 ) ) = 6
₃₂ = c₃₂ - ( u₃ + v₂ ) = 27 - ( 17 + ( -2 ) ) = 12
₃₅ = c₃₅ - ( u₃ + v₅ ) = 19 - ( 17 + 0 ) = 2
₄₁ = c₄₁ - ( u₄ + v₁ ) = 0 - ( 0 + ( -3 ) ) = 3
₄₂ = c₄₂ - ( u₄ + v₂ ) = 0 - ( 0 + ( -2 ) ) = 2
₄₃ = c₄₃ - ( u₄ + v₃ ) = 0 - ( 0 + ( -16 ) ) = 16

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

11
	3

4
	4

-
15	5

-
9	15

-
18	24

u ₁ = 6

A ₂

-
18	19

7
	2

-
34	22

8
	4

-
9	13

u ₂ = 4

A ₃

-
6	20

-
12	27

11
	1

4
	17

-
2	19

u ₃ = 17

A ₄

-
3	0

-
2	0

-
16	0

4
	0

11
	0

u ₄ = 0

V _i

v ₁ = -3

v ₂ = -2

v ₃ = -16

v ₄ = 0

v ₅ = 0

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

решение.

Ответ:

X _опт =	11	4	0	0	0
	0	7	0	8	0
	0	0	11	4	0
	0	0	0	4	11

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

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

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

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

Внимание!

Если вам нужна помощь в написании работы, то рекомендуем обратиться к профессионалам. Более 70 000 авторов готовы помочь вам прямо сейчас. Бесплатные корректировки и доработки. Узнайте стоимость своей работы

Бесплатная оценка

Размер: 31.92K

Скачано: 319

Скачать бесплатно

14.05.13 в 15:30 Автор:

Понравилось? Нажмите на кнопочку ниже. Вам не сложно, а нам приятно).

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

Важно! Все представленные Задачи для бесплатного скачивания предназначены для составления плана или основы собственных научных трудов.

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

Добавить работу

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

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

Добавить отзыв могут только зарегистрированные пользователи.