Методические указания по изучению дисциплины и выполнению контрольной работы (стр. 8 из 14)

а) б)

+ - 20 20

40

- + 80

20 60

Рис.3.1

Может случится, что найденное наименьшее число (

одинаково для нескольких клеток цепи, помеченных знаком «-» (рис.3.2а). В этом случае во всех таких клетках (с минимальными стоимостями), кроме одной, нужно оставить нулевые (фиктивные) поставки (рис.3.2б).

а) б)

+ 4 - 3 33

20 20

- + 10 30

30 10

- 2 + 0 60

20 40

Рис.3.2

Составляется новый план, рассчитывается значение целевой функции. Переходим к шагу 2.

3.5. Пример решения транспортной задачи

На четырех строительных площадках В₁, В₂, В₃, В₄ монтируется в день соответственно 20,120,20 60 м³ сборных плит перекрытий. Производство этих плит налажено на трех заводах А_1, А₂, А₃ в размере соответственно 100,70 и 50 м³. Известны стоимости перевозки (табл.2) 1м³ сборных плит из каждого пункта производства в каждый пункт потребления (ден. ед./ м³).

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

РЕШЕНИЕ.

Исходное опорное решение получим по методу «северо-западного угла» (табл.3) и по методу min элемента (табл.4).

Здесь

,т.е имеем закрытую модель ТЗ (табл.2 ).

табл.2

Bj Ai	20	120	20	60
100	6	4	2	4
70	1	2	7	2
50	2	4	1	4

табл.3

Bj Ai	20	120	20	60
100	6 20	4 80	2	4
70	1	2 40	7 20	2 10
50	2	4	1	4 50

Транспортные расходы f=

табл.4

Bj Ai	20	120	20	60
100	6	4 100	2	4
70	1 20	2	7	2 50
50	2	4 20	1 20	4 10

f=

Транспортные расходы для опорного плана, построенного по методу min элемента, меньше. Поэтому за исходное решение возьмем то, которое получено по методу min элемента (табл.4).

Количество заполненных клеток в табл.4 равно 6: m+n-1=3+4-1=6.

Следовательно, полученный план невырожденный.

Для определения потенциалов (см. формула 3.8) составляем уравнения:

u₁+v₂=4, u₂+v₁=1, u₂+v₄=2, u₃ +v₂=4, u₃+v₃=1, u₃+v₄=4. Положим u₁=0, тогда v₂=4, u₃=0, v₃=1, v₄=4, u₂=-2, v₁=3.

Потенциалы проставлены в табл.5 (последняя строка и последний столбец). Их можно вычислять и непосредственно в таблице не выписывая систему уравнений. Т.к. если известны потенциал и тариф (стоимость перевозки) занятой клетки, то из соотношения u_i+v_j=c_ij легко определить неизвестный потенциал (из суммы вычесть известное слагаемое, получим неизвестное слагаемое. Роль суммы в данном равенстве играет тариф c_ij)

Определим по формуле (3.9) оценки свободных клеток:

s₁₁=6-(0+3)=3>0, s₁₃=2-(0+1)=1>0, s₁₄=4-(0+4)=0

s₂₂=2-(-2+4)=0, s₂₃=7-(-2+1)=8>0, s₃₁=2-(0+3)= -1<0

табл.5 табл.6

Bj Ai	20	120	20	60	ui	Bj Ai	20	120	20	60	ui
100	6	4 100	2	4	0	100	6	4 100	2	4	0
70	- 1 20	2	7	+ 2 50	-2	70	- 1 10	+ 2	7	2 60	-1
50	2 +	4 20	1 20	-- 4 10	0	50	+ 2 10	- 4 20	1 20	4	0
vi	3	4	1	4	vj	2	4	1	3

План неоптимальный, т.к. s₃₁<0. Строим для клетки (3;1) цикл непосредственно в табл.5. В цикл войдут клетки (3;1), (3;4), (2;4), (2;1). Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком,

В результате смещения по циклу получим новый план (табл.6). Транспортные расходы ( а были равны 660).

Будет ли полученный план оптимальным? План невырожденный.

Определим для него новые потенциалы:

u₁+v₂=4, u₂+v₁=1, u₂+v₄= 2, u₃+v₁=2, u₃+v₂=4, u₃+v₃=1. Положим u₁=0, тогда v₂=4, u₃=0, v₁=2, v₃=1, u₂= -1, v₄=3. Проставим значения найденных потенциалов в табл.6.

Определим оценки свободных клеток:

s₁₁=6-(0+2)=4>0, s₁₃=2-(0+1)=1>0, s₁₄=4-(0+3)=1>0

s₂₂=2-(-1+4)=-1<0, s₂₃=7-(-1+1)=7>0, s₄₄=4-(0+3)=1>0.

План (табл.6) неоптимальный, т.к. s₂₂<0. Строим для клетки (2;2) цикл непосредственно в табл.6. В цикл войдут клетки (2;2), (2;1), (3;1), (3;2). Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком,

В результате смещения по циклу получим новый план (табл.7). План невырожденный. Транспортные расходы