Контрольная работа по "Методам оптимальных решений"

 

Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.

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

 

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

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

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

Разместим в ячейку A₁B₄ значение равное 16

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

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1	-     10	-     11	-     9	16     6	-     8	126
A 2	-     15	-     16	-     13	-     11	-     14	10
A 3	-     14	-     12	-     11	-     11	-     12	98
A 4	-     0	-     0	-     0	-     0	-     0	110
Потребность	68	68	82	16	110

 

И т.д. В результате получим

 

 

 

 

 

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1	-     10	-     11	-     9	16     6	110     8	126
A 2	10     15	-     16	-     13	-     11	-     14	10
A 3	-     14	16     12	82     11	-     11	-     12	98
A 4	58     0	52     0	-     0	-     0	-     0	110
Потребность	68	68	82	16	110

 

Количество базисных ячеек равно 7. Требуется, чтобы было 8.

В свободную ячейку A₁B₃ запишем ноль, как в ячейку не образующую цикл (понятие цикл см. ниже) с базисными ячейками и имеющую наименьший тариф. Будем считать, что от поставщика A₁ к потребителю B₃ доставляем 0 единиц продукции.

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1	-     10	-     11	0     9	16     6	110     8	126
A 2	10     15	-     16	-     13	-     11	-     14	10
A 3	-     14	16     12	82     11	-     11	-     12	98
A 4	58     0	52     0	-     0	-     0	-     0	110
Потребность	68	68	82	16	110

 

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

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

S₀ = 6 * 16 + 8 * 110 + 15 * 10 + 12 * 16 + 11 * 82 + 0 * 58 + 0 * 52 = 2220 ден. ед.

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

 

3. Решаем  задачу методом потенциалов.

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

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

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

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

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

Примем u₁ = 0.

v₃ + u₁ = c₁₃ v₃ + u₁ = 9 v₃ = 9 - 0 = 9

v₄ + u₁ = c₁₄ v₄ + u₁ = 6 v₄ = 6 - 0 = 6

v₅ + u₁ = c₁₅ v₅ + u₁ = 8 v₅ = 8 - 0 = 8

v₃ + u₃ = c₃₃ v₃ + u₃ = 11 u₃ = 11 - 9 = 2

v₂ + u₃ = c₃₂ v₂ + u₃ = 12 v₂ = 12 - 2 = 10

v₂ + u₄ = c₄₂ v₂ + u₄ = 0 u₄ = 0 - 10 = -10

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

v₁ + u₂ = c₂₁ v₁ + u₂ = 15 u₂ = 15 - 10 = 5

 

Поставщик	Потребитель					U j
	B 1	B 2	B 3	B 4	B 5
A 1	-     10	-     11	0     9	16     6	110     8	u 1 = 0
A 2	10     15	-     16	-     13	-     11	-     14	u 2 = 5
A 3	-     14	16     12	82     11	-     11	-     12	u 3 = 2
A 4	58     0	52     0	-     0	-     0	-     0	u 4 = -10
V i	v 1 = 10	v 2 = 10	v 3 = 9	v 4 = 6	v 5 = 8

 

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

₁₁ = c₁₁ - ( u₁ + v₁ ) = 10 - ( 0 + 10 ) = 0

₁₂ = c₁₂ - ( u₁ + v₂ ) = 11 - ( 0 + 10 ) = 1

₂₂ = c₂₂ - ( u₂ + v₂ ) = 16 - ( 5 + 10 ) = 1

₂₃ = c₂₃ - ( u₂ + v₃ ) = 13 - ( 5 + 9 ) = -1

₂₄ = c₂₄ - ( u₂ + v₄ ) = 11 - ( 5 + 6 ) = 0

₂₅ = c₂₅ - ( u₂ + v₅ ) = 14 - ( 5 + 8 ) = 1

₃₁ = c₃₁ - ( u₃ + v₁ ) = 14 - ( 2 + 10 ) = 2

₃₄ = c₃₄ - ( u₃ + v₄ ) = 11 - ( 2 + 6 ) = 3

₃₅ = c₃₅ - ( u₃ + v₅ ) = 12 - ( 2 + 8 ) = 2

₄₃ = c₄₃ - ( u₄ + v₃ ) = 0 - ( -10 + 9 ) = 1

₄₄ = c₄₄ - ( u₄ + v₄ ) = 0 - ( -10 + 6 ) = 4

₄₅ = c₄₅ - ( u₄ + v₅ ) = 0 - ( -10 + 8 ) = 2

 

 

 

Поставщик	Потребитель					U j
	B 1	B 2	B 3	B 4	B 5
A 1	- 0 10	- 1 11	0     9	16     6	110     8	u 1 = 0
A 2	10     15	- 1 16	- -1 13	- 0 11	- 1 14	u 2 = 5
A 3	- 2 14	16     12	82     11	- 3 11	- 2 12	u 3 = 2
A 4	58     0	52     0	- 1 0	- 4 0	- 2 0	u 4 = -10
V i	v 1 = 10	v 2 = 10	v 3 = 9	v 4 = 6	v 5 = 8