ВУЗ:
Составители:
Рубрика:
11
определим методом северо-западного угла (таблица 2).
8 5 7 10
10 2 3 5 7
8 2
8 4 1 3 2
3 − 5 +
12 6 3 2 5 −
+2 10
Таблица 2
8 5 7 10
10 2 3 5 7
8 2
8 4 1 3 2+
− 3 5
12 6 3 2 5 −
+ 7 5
Таблица 3
Для проверки плана на оптимальность определим потенциалы строк и столбцов. Для этого для
каждой базисной клеточки выпишем уравнение v
j
− u
i
= c
ij
.
v
1
− u
1
=2,v
3
− u
2
=3
v
2
− u
1
=3,v
3
− u
3
=2
v
2
− u
2
=1,v
4
− u
3
=5
Положив u
1
=0, находим последовательно v
1
=2,v
2
=3,u
2
=2,v
3
=5,u
3
=3,v
4
=8. Полученные
u
i
,v
j
используем для проверки условий оптимальности других клеток таблицы. Для внебазисных
клеток находим величины
c
13
− v
3
+ u
1
=5+0− 3=2,c
24
− v
4
+ u
2
=2+2− 8=−4
c
14
− v
4
+ u
1
=7+0− 8=−1,c
31
− v
1
+ u
3
=6+3− 2=7
c
21
− v
1
+ u
2
=4+2− 2=4,c
32
− v
2
+ u
3
=3+3− 3=3
Для оптимальности опорного плана согласно алгоритму достаточно выполнения условия c
ij
− v
j
+
u
i
≥ 0. Однако это условия нарушается и наибольшее нарушение имеет место в клеточке (2.4).
Поэтому перевозку x
24
следует ввести согласно алгоритму в опорный план. Для этого строим цикл,
начинающийся в клеточке (2.4). Этот цикл приведен в таблицу 2, он содержит клеточки (2.4),
(3.4), (3.3), (2,3). Сравнивая перевозки в клеточках с
−
, находим величину коррекции плана
Θ = min{5, 10} =5. Проведя коррекцию плана, получаем новый опорный план, приведенный в
таблице 3. Транспортные затраты, отвечающие новому опорному плану, равны 74 единицы, то есть
уменьшились на 20 единиц относительно предыдущего.
Повторяем процедуру проверки очередного опорного плана на оптимальность. Находим потен-
циалы строк и столбцов из системы уравнений
v
1
− u
1
=2,v
4
− u
2
=2,u
1
=0,u
2
=2,v
3
=1
v
2
− u
1
=3,v
3
− u
3
=2,v
1
=2,v
4
=4
v
2
− u
2
=1,v
4
− u
3
=5,v
2
=3,u
3
= −1
Проверяем условие v
j
− u
i
≤ c
ij
для внебазисных клеточек.
c
13
− v
3
+ u
1
=5+0+1=6,c
23
− v
3
+ u
2
=3+3− 1=5
c
14
− v
4
+ u
1
=7+0− 4=3,c
31
− v
1
+ u
3
=6− 1 − 2=3
c
21
− v
1
+ u
2
=4+2− 2=4,c
32
− v
2
+ u
3
=3− 1 − 3=−1
Условие оптимальности нарушено, в единственной клеточке (3.2). Строим цикл, начинающийся в
этой клеточке (см. таблицу 2). Величина коррекции Θ = min{3, 5}. Проводя коррекцию плана,
получаем новый опорный план (таблица 3). Анализ полученного плана показывает, что опорный
план оптимален. Минимальные затраты на транспортировку составляют 71 единицу.
Мы рассматривали ранее Т.З., для которых выполнялось условие баланса. В практических
случаях это условие может не выполняться. Пусть имеется m пунктов производства с объемами
a
1
,a
2
,...,a
m
и n пунктов с объемами b
1
,b
2
,...,b
n
. Допустим, что
m
i=1
a
i
>
n
j=1
b
j
. Математиче-
11
определим методом северо-западного угла (таблица 2).
8 5 7 10 8 5 7 10
10 2 3 5 7 10 2 3 5 7
8 2 8 2
8 4 1 3 2 8 4 1 3 2 +
3 − 5 + − 3 5
12 6 3 2 5 − 12 6 3 2 5 −
+ 2 10 + 7 5
Таблица 2 Таблица 3
Для проверки плана на оптимальность определим потенциалы строк и столбцов. Для этого для
каждой базисной клеточки выпишем уравнение vj − ui = cij .
v1 − u1 = 2, v3 − u2 = 3
v2 − u1 = 3, v3 − u3 = 2
v2 − u2 = 1, v4 − u3 = 5
Положив u1 = 0, находим последовательно v1 = 2, v2 = 3, u2 = 2, v3 = 5, u3 = 3, v4 = 8. Полученные
ui , vj используем для проверки условий оптимальности других клеток таблицы. Для внебазисных
клеток находим величины
c13 − v3 + u1 = 5 + 0 − 3 = 2, c24 − v4 + u2 = 2 + 2 − 8 = −4
c14 − v4 + u1 = 7 + 0 − 8 = −1, c31 − v1 + u3 = 6 + 3 − 2 = 7
c21 − v1 + u2 = 4 + 2 − 2 = 4, c32 − v2 + u3 = 3 + 3 − 3 = 3
Для оптимальности опорного плана согласно алгоритму достаточно выполнения условия cij − vj +
ui ≥ 0. Однако это условия нарушается и наибольшее нарушение имеет место в клеточке (2.4).
Поэтому перевозку x24 следует ввести согласно алгоритму в опорный план. Для этого строим цикл,
начинающийся в клеточке (2.4). Этот цикл приведен в таблицу 2, он содержит клеточки (2.4),
(3.4), (3.3), (2,3). Сравнивая перевозки в клеточках с − , находим величину коррекции плана
Θ = min{5, 10} = 5. Проведя коррекцию плана, получаем новый опорный план, приведенный в
таблице 3. Транспортные затраты, отвечающие новому опорному плану, равны 74 единицы, то есть
уменьшились на 20 единиц относительно предыдущего.
Повторяем процедуру проверки очередного опорного плана на оптимальность. Находим потен-
циалы строк и столбцов из системы уравнений
v1 − u1 = 2, v4 − u2 = 2, u1 = 0, u2 = 2, v3 = 1
v2 − u1 = 3, v3 − u3 = 2, v1 = 2, v4 = 4
v2 − u2 = 1, v4 − u3 = 5, v2 = 3, u3 = −1
Проверяем условие vj − ui ≤ cij для внебазисных клеточек.
c13 − v3 + u1 = 5 + 0 + 1 = 6, c23 − v3 + u2 = 3 + 3 − 1 = 5
c14 − v4 + u1 = 7 + 0 − 4 = 3, c31 − v1 + u3 = 6 − 1 − 2 = 3
c21 − v1 + u2 = 4 + 2 − 2 = 4, c32 − v2 + u3 = 3 − 1 − 3 = −1
Условие оптимальности нарушено, в единственной клеточке (3.2). Строим цикл, начинающийся в
этой клеточке (см. таблицу 2). Величина коррекции Θ = min{3, 5}. Проводя коррекцию плана,
получаем новый опорный план (таблица 3). Анализ полученного плана показывает, что опорный
план оптимален. Минимальные затраты на транспортировку составляют 71 единицу.
Мы рассматривали ранее Т.З., для которых выполнялось условие баланса. В практических
случаях это условие может не выполняться. Пусть имеется m пунктов m производства
n с объемами
a1 , a2 , . . . , am и n пунктов с объемами b1 , b2 , . . . , bn . Допустим, что i=1 ai > j=1 bj . Математиче-
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
