Задачи линейного программирования
Задачи линейного программирования
9. Симплекс-метод. Компания производит полки для ванных комнат двух размеров – А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В – 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В – 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В – 4 денежных единицы, то сколько полок каждого типа следует выпускать в неделю, чтобы получить максимальную прибыль?
Составим математическую модель задачи.
Пусть x1 – количество полок вида А, x2- количество полок вида В, которые производятся в неделю. Прибыль от продажи такого количества полок составит 3x1+4x2, прибыль требуется максимизировать. Выпишем ограничения задачи x1+x2≤550 - в неделю на рынке может быть реализовано до 550 полок.
Затраты материала: 2x1+3x2≤1200
Затраты машинного времени:12x1+30x2≤9600
Таким образом, приходим к задаче линейного программирования.
F=3x1+4x2→max,
X1+x2≤550,
2x1+3x2≤1200,
12x1+30x2≤9600,
X1≥0,x2≥0.
Решим ее симплекс-методом. Приведем задачу к каноническому виду путем добавления искусственных переменных
F=3x1+4x2→max,
X1+x2+x3=550,
2x1+3x2+x4=1200,
12x1+30x2+x5=9600,
Xi≥0,i=1,2,3,4,5
Составим симплекс-таблицу
|
Базисные переменные |
Коэф. переменных |
Свободные члены |
Отношения | ||||
|
X1 |
X2 |
X3 |
X4 |
X5 | |||
|
0 |
1 |
1 |
1 |
0 |
0 |
550 |
550 |
|
0 |
2 |
3 |
0 |
1 |
0 |
1200 |
400 |
|
0 |
12 |
30 |
0 |
0 |
1 |
9600 |
320 |
|
F |
-3 |
-4 |
0 |
0 |
0 |
0 |
0 |
В последней оценочной строке есть отрицательные оценки, поэтому нужно делать шаг симплекс метода. Выбираем столбец с наименьшей оценкой, а затем разрешающий элемент по наименьшему отношению свободных членов. Результат шага запишем в таблицу. Аналогично будем повторять шаги, пока не придем к таблице с неотрицательными оценками.
|
Базисные переменные |
Коэф. переменных |
Свободные члены |
Отношения | ||||
|
X1 |
X2 |
X3 |
X4 |
X5 | |||
|
0 |
0,6 |
0 |
1 |
0 |
-0,033 |
230 |
383,3 |
|
0 |
0,8 |
0 |
0 |
1 |
-0,1 |
240 |
300 |
|
X2 |
0,4 |
1 |
0 |
0 |
0,033 |
320 |
800 |
|
F |
-1,4 |
0 |
0 |
0 |
0,13 |
1280 |
|
Базисные переменные |
Коэф. переменных |
Свободные члены |
Отношения | ||||
|
X1 |
X2 |
X3 |
X4 |
X5 | |||
|
0 |
0 |
0 |
1 |
-0,75 |
0,042 |
50 |
1190 |
|
X1 |
1 |
0 |
0 |
1,25 |
-0,125 |
300 |
2400 |
|
X2 |
0 |
1 |
0 |
-0,5 |
0,083 |
200 |
2409 |
|
F |
0 |
0 |
0 |
1,75 |
-0,042 |
1700 |
|
Базисные переменные |
Коэф. переменных |
Свободные члены |
Отношения | ||||
|
X1 |
X2 |
X3 |
X4 |
X5 | |||
|
X5 |
0 |
0 |
24 |
-18 |
1 |
1200 | |
|
X1 |
1 |
0 |
3 |
-1 |
0 |
450 | |
|
X2 |
0 |
1 |
-2 |
1 |
0 |
100 | |
|
F |
0 |
0 |
1 |
1 |
0 |
1750 |
В последнем плане строка F не содержит отрицательных значений, план x1=450,x2=100 оптимален, целевая функция принимает значение 1750.
Таким образом, чтобы получить максимальную прибыль предприятию необходимо производить 450 полок вида A и 100 полок вида В, при этом прибыль составит 1750 ден. ед., а останется неиспользованными 1200 минут машинного времени.
Ответ: Чтобы получить максимальную прибыль предприятию необходимо производить 450 полок вида A и 100 полок вида В, при этом прибыль составит 1750 ден. ед., а останется неиспользованными 1200 минут машинного времени.
10. Задача коммивояжера. Коммивояжер должен объездить 6 городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей:
|
A |
B |
C |
D |
E |
F | |
|
A |
∞ |
26 |
42 |
15 |
29 |
25 |
|
B |
7 |
∞ |
16 |
1 |
30 |
25 |
|
C |
20 |
13 |
∞ |
35 |
5 |
0 |
|
D |
21 |
16 |
25 |
∞ |
18 |
18 |
|
E |
12 |
46 |
27 |
48 |
∞ |
5 |
|
F |
23 |
5 |
5 |
9 |
5 |
∞ |
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 26 + 16 + 35 + 18 + 5 + 23 = 123
Для определения нижней границы множества воспользуемся Операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент. di = min(j) dij
|
I J |
A |
B |
C |
D |
E |
F |
Di |
|
A |
M |
26 |
42 |
15 |
29 |
25 |
15 |
|
B |
7 |
M |
16 |
1 |
30 |
25 |
1 |
|
C |
20 |
13 |
M |
35 |
5 |
0 |
0 |
|
D |
21 |
16 |
25 |
M |
18 |
18 |
16 |
|
E |
12 |
46 |
27 |
48 |
M |
5 |
5 |
|
F |
23 |
5 |
5 |
9 |
5 |
M |
5 |
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: dj = min(i) dij
|
I j |
A |
B |
C |
D |
E |
F |
|
A |
M |
11 |
27 |
0 |
14 |
10 |
|
B |
6 |
M |
15 |
0 |
29 |
24 |
|
C |
20 |
13 |
M |
35 |
5 |
0 |
|
D |
5 |
0 |
9 |
M |
2 |
2 |
|
E |
7 |
41 |
22 |
43 |
M |
0 |
|
F |
18 |
0 |
0 |
4 |
0 |
M |
|
Dj |
5 |
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются Константами приведения.
|
I j |
A |
B |
C |
D |
E |
F |
|
A |
M |
11 |
27 |
0 |
14 |
10 |
|
B |
1 |
M |
15 |
0 |
29 |
24 |
|
C |
15 |
13 |
M |
35 |
5 |
0 |
|
D |
0 |
0 |
9 |
M |
2 |
2 |
|
E |
2 |
41 |
22 |
43 |
M |
0 |
|
F |
13 |
0 |
0 |
4 |
0 |
M |
Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*,j*).
|
I j |
A |
B |
C |
D |
E |
F |
Di |
|
A |
M |
11 |
27 |
0(10) |
14 |
10 |
10 |
|
B |
1 |
M |
15 |
0(1) |
29 |
24 |
1 |
|
C |
15 |
13 |
M |
35 |
5 |
0(5) |
5 |
|
D |
0(1) |
0(0) |
9 |
M |
2 |
2 |
0 |
|
E |
2 |
41 |
22 |
43 |
M |
0(2) |
2 |
|
F |
13 |
0(0) |
0(9) |
4 |
0(2) |
M |
0 |
|
Dj |
1 |
0 |
9 |
0 |
2 |
0 |
0 |
Наибольшая сумма констант приведения равна (10 + 0) = 10 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
|
I j |
A |
B |
C |
D |
E |
F |
Di |
|
A |
M |
11 |
27 |
M |
14 |
10 |
10 |
|
B |
1 |
M |
15 |
0 |
29 |
24 |
0 |
|
C |
15 |
13 |
M |
35 |
5 |
0 |
0 |
|
D |
0 |
0 |
9 |
M |
2 |
2 |
0 |
|
E |
2 |
41 |
22 |
43 |
M |
0 |
0 |
|
F |
13 |
0 |
0 |
4 |
0 |
M |
0 |
|
Dj |
0 |
0 |
0 |
0 |
0 |
0 |
10 |
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
I j |
A |
B |
C |
E |
F |
Di |
|
B |
1 |
M |
15 |
29 |
24 |
1 |
|
C |
15 |
13 |
M |
5 |
0 |
0 |
|
D |
M |
0 |
9 |
2 |
2 |
0 |
|
E |
2 |
41 |
22 |
M |
0 |
0 |
|
F |
13 |
0 |
0 |
0 |
M |
0 |
|
Dj |
1 |
0 |
0 |
0 |
0 |
2 |
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 49
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*,j*).
|
I j |
A |
B |
C |
E |
F |
Di |
|
B |
0(16) |
M |
15 |
29 |
24 |
15 |
|
C |
14 |
13 |
M |
5 |
0(5) |
5 |
|
D |
M |
0(2) |
9 |
2 |
2 |
2 |
|
E |
1 |
41 |
22 |
M |
0(1) |
1 |
|
F |
12 |
0(0) |
0(9) |
0(2) |
M |
0 |
|
Dj |
1 |
0 |
9 |
2 |
0 |
0 |
Наибольшая сумма констант приведения равна (15 + 1) = 16 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:
|
I j |
A |
B |
C |
E |
F |
Di |
|
B |
M |
M |
15 |
29 |
24 |
15 |
|
C |
14 |
13 |
M |
5 |
0 |
0 |
|
D |
M |
0 |
9 |
2 |
2 |
0 |
|
E |
1 |
41 |
22 |
M |
0 |
0 |
|
F |
12 |
0 |
0 |
0 |
M |
0 |
|
Dj |
1 |
0 |
0 |
0 |
0 |
16 |
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
I j |
B |
C |
E |
F |
Di |
|
C |
13 |
M |
5 |
0 |
0 |
|
D |
0 |
9 |
2 |
2 |
0 |
|
E |
41 |
22 |
M |
0 |
0 |
|
F |
0 |
0 |
0 |
M |
0 |
|
Dj |
0 |
0 |
0 |
0 |
0 |
Чтобы исключить подциклы, запретим следующие переходы: (4,2),
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 49
Шаг №3.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*,j*).
|
I j |
B |
C |
E |
F |
Di |
|
C |
13 |
M |
5 |
0(5) |
5 |
|
D |
M |
7 |
0(0) |
0(0) |
0 |
|
E |
41 |
22 |
M |
0(22) |
22 |
|
F |
0(13) |
0(7) |
0(0) |
M |
0 |
|
Dj |
13 |
7 |
0 |
0 |
0 |
Наибольшая сумма констант приведения равна (22 + 0) = 22 для ребра (5,6), следовательно, множество разбивается на два подмножества (5,6) и (5*,6*).
Нижняя граница гамильтоновых циклов этого подмножества:
|
I j |
B |
C |
E |
F |
Di |
|
C |
13 |
M |
5 |
0 |
0 |
|
D |
M |
7 |
0 |
0 |
0 |
|
E |
41 |
22 |
M |
M |
22 |
|
F |
0 |
0 |
0 |
M |
0 |
|
Dj |
0 |
0 |
0 |
0 |
22 |
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
I j |
B |
C |
E |
Di |
|
C |
13 |
M |
5 |
5 |
|
D |
M |
7 |
0 |
0 |
|
F |
0 |
0 |
M |
0 |
|
Dj |
0 |
0 |
0 |
5 |
Чтобы исключить подциклы, запретим следующие переходы: (4,2),
Поскольку нижняя граница этого подмножества (5,6) меньше, чем подмножества (5*,6*), то ребро (5,6) включаем в маршрут с новой границей H = 54
Шаг №4.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*,j*).
|
I j |
B |
C |
E |
Di |
|
C |
8 |
M |
0(8) |
8 |
|
D |
M |
7 |
0(7) |
7 |
|
F |
0(8) |
0(7) |
M |
0 |
|
Dj |
8 |
7 |
0 |
0 |
Наибольшая сумма констант приведения равна (8 + 0) = 8 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
|
I j |
B |
C |
E |
Di |
|
C |
8 |
M |
M |
8 |
|
D |
M |
7 |
0 |
0 |
|
F |
0 |
0 |
M |
0 |
|
Dj |
0 |
0 |
0 |
8 |
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
I j |
B |
C |
Di |
|
D |
M |
7 |
7 |
|
F |
0 |
0 |
0 |
|
Dj |
0 |
0 |
7 |
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 61
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,3) и (6,2).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,4), (4,3), (3,5), (5,6), (6,2), (2,1),
Длина маршрута равна F(Mk) = 62
11. Транспортная задача. Из трех холодильников Ai (i =1,3), вмещающих мороженную рыбу в количествах ai (тонн), необходимо последнюю доставить в пять магазинов Bj (j =1,5) в количествах bj (тонн). Стоимости перевозки 1 тонны рыбы из холодильника Ai в магазин Bj заданы в виде матрицы C=((cij)) (3x5). Написать математическую модель задачи и спланировать перевозки так, чтобы их общая стоимость была минимальной.
А1 = 320, а2 = 280, а3 = 250,
B1 = 150, b2 = 140, b3 = 110, b4 = 230, b5 = 220,
Решение
Примем некоторые обозначения: I - индекс строки, J - индекс столбца, M - количество поставщиков, N - количество потребителей, Xi, j - перевозка между поставщиком Ai и потребителем Bj.
|
Поставщик |
Потребитель |
Запасы | |||||||||||||||||||
|
B1 |
B2 |
B3 |
B4 |
B5 | |||||||||||||||||
|
A1 |
|
|
|
|
|
320 | |||||||||||||||
|
A2 |
|
|
|
|
|
280 | |||||||||||||||
|
A3 |
|
|
|
|
|
250 | |||||||||||||||
|
Потребность |
150 |
140 |
110 |
230 |
220 |
Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям.
Находим опорный план по правилу северо-западного угла:
Введем некоторые обозначения:
Ai* - излишек нераспределенного груза от поставщика Ai
Bj* - недостача в поставке груза потребителю Bj
Помещаем в клетку (1,1) меньшее из чисел A1*=320 и B1*=150
Так как спрос потребителя B1 удовлетворен, то столбец 1 в дальнейшем в расчет не принимается
Помещаем в клетку (1,2) меньшее из чисел A1*=170 и B2*=140
Так как спрос потребителя B2 удовлетворен, то столбец 2 в дальнейшем в расчет не принимается
Помещаем в клетку (1,3) меньшее из чисел A1*=30 и B3*=110
Так как запасы поставщика A1 исчерпаны, то строка 1 в дальнейшем в расчет не принимается
Помещаем в клетку (2,3) меньшее из чисел A2*=280 и B3*=80
Так как спрос потребителя B3 удовлетворен, то столбец 3 в дальнейшем в расчет не принимается
Помещаем в клетку (2,4) меньшее из чисел A2*=200 и B4*=230
Так как запасы поставщика A2 исчерпаны, то строка 2 в дальнейшем в расчет не принимается
Помещаем в клетку (3,4) меньшее из чисел A3*=250 и B4*=30
Так как спрос потребителя B4 удовлетворен, то столбец 4 в дальнейшем в расчет не принимается
Помещаем в клетку (3,5) меньшее из чисел A3*=220 и B5*=220
|
Поставщик |
Потребитель |
Запасы | |||||||||||||||||||
|
B1 |
B2 |
B3 |
B4 |
B5 | |||||||||||||||||
|
A1 |
|
|
|
|
|
320 | |||||||||||||||
|
A2 |
|
|
|
|
|
280 | |||||||||||||||
|
A3 |
|
|
|
|
|
250 | |||||||||||||||
|
Потребность |
150 |
140 |
110 |
230 |
220 |
Целевая функция F=13930
Решаем задачу методом потенциалов:
Этап 1
Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci, j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj:
U1=0
V1=C1,1-U1= 20
V2=C1,2-U1= 23
V3=C1,3-U1= 20
U2=C3,2-V3= -4
V4=C2,4-U2= 23
U3=C4,3-V4= -14
V5=C3,5-U3= 22
Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток (Неоптимальные выделены красным цветом)
S1,4 = c1,4 - (u1 + v4) = -8.
S1,5 = c1,5 - (u1 + v5) = 2.
S2,1 = c2,1 - (u2 + v1) = 13.
S2,2 = c2,2 - (u2 + v2) = -4.
S2,5 = c2,5 - (u2 + v5) = 11.
S3,1 = c3,1 - (u3 + v1) = 0.
S3,2 = c3,2 - (u3 + v2) = 2.
S3,3 = c3,3 - (u3 + v3) = 4.
Так как имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,4). Для нее оценка равна -8.
Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".
|
Поставщик |
Потребитель |
Запасы | |||||||||||||||||||
|
B1 |
B2 |
B3 |
B4 |
B5 | |||||||||||||||||
|
A1 |
|
|
|
|
|
320 | |||||||||||||||
|
A2 |
|
|
|
|
|
280 | |||||||||||||||
|
A3 |
|
|
|
|
|
250 | |||||||||||||||
|
Потребность |
150 |
140 |
110 |
230 |
220 |
Перемещаем по циклу груз величиной в 30 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:
|
Поставщик |
Потребитель |
Запасы | |||||||||||||||||||
|
B1 |
B2 |
B3 |
B4 |
B5 | |||||||||||||||||
|
A1 |
|
|
|
|
|
320 | |||||||||||||||
|
A2 |
|
|
|
|
|
280 | |||||||||||||||
|
A3 |
|
|
|
|
|
250 | |||||||||||||||
|
Потребность |
150 |
140 |
110 |
230 |
220 |
Целевая функция F= 13690
Значение целевой функции изменилось на 240 единиц по сравнению с предыдущим этапом.
Этап 2
Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci, j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj:
U1=0
V1=C1,1-U1= 20
V2=C1,2-U1= 23
V4=C1,4-U1= 15
U2=C4,2-V4= 4
U3=C4,3-V4= -6
V3=C2,3-U2= 12
V5=C3,5-U3= 14
Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток (Неоптимальные выделены красным цветом)
S1,3 = c1,3 - (u1 + v3) = 8.
S1,5 = c1,5 - (u1 + v5) = 10.
S2,1 = c2,1 - (u2 + v1) = 5.
S2,2 = c2,2 - (u2 + v2) = -12.
S2,5 = c2,5 - (u2 + v5) = 11.
S3,1 = c3,1 - (u3 + v1) = -8.
S3,2 = c3,2 - (u3 + v2) = -6.
S3,3 = c3,3 - (u3 + v3) = 4.
Наиболее потенциальной является клетка (2,2). Для нее оценка равна -12.
Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".
|
Поставщик |
Потребитель |
Запасы | |||||||||||||||||||
|
B1 |
B2 |
B3 |
B4 |
B5 | |||||||||||||||||
|
A1 |
|
|
|
|
|
320 | |||||||||||||||
|
A2 |
|
|
|
|
|
280 | |||||||||||||||
|
A3 |
|
|
|
|
|
250 | |||||||||||||||
|
Потребность |
150 |
140 |
110 |
230 |
220 |
Перемещаем по циклу груз величиной в 140 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:
|
Поставщик |
Потребитель |
Запасы | |||||||||||||||||||
|
B1 |
B2 |
B3 |
B4 |
B5 | |||||||||||||||||
|
A1 |
|
|
|
|
|
320 | |||||||||||||||
|
A2 |
|
|
|
|
|
280 | |||||||||||||||
|
A3 |
|
|
|
|
|
250 | |||||||||||||||
|
Потребность |
150 |
140 |
110 |
230 |
220 |
Целевая функция F= 12010
Значение целевой функции изменилось на 1680 единиц по сравнению с предыдущим этапом.
Этап 3
Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci, j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj:
U1=0
V1=C1,1-U1= 20
V4=C1,4-U1= 15
U2=C4,2-V4= 4
U3=C4,3-V4= -6
V2=C2,2-U2= 11
V3=C2,3-U2= 12
V5=C3,5-U3= 14
Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток (Неоптимальные выделены красным цветом)
S1,2 = c1,2 - (u1 + v2) = 12.
S1,3 = c1,3 - (u1 + v3) = 8.
S1,5 = c1,5 - (u1 + v5) = 10.
S2,1 = c2,1 - (u2 + v1) = 5.
S2,5 = c2,5 - (u2 + v5) = 11.
S3,1 = c3,1 - (u3 + v1) = -8.
S3,2 = c3,2 - (u3 + v2) = 6.
S3,3 = c3,3 - (u3 + v3) = 4.
Наиболее потенциальной является клетка (3,1). Для нее оценка равна -8.
Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".
|
Поставщик |
Потребитель |
Запасы | |||||||||||||||||||
|
B1 |
B2 |
B3 |
B4 |
B5 | |||||||||||||||||
|
A1 |
|
|
|
|
|
320 | |||||||||||||||
|
A2 |
|
|
|
|
|
280 | |||||||||||||||
|
A3 |
|
|
|
|
|
250 | |||||||||||||||
|
Потребность |
150 |
140 |
110 |
230 |
220 |
Перемещаем по циклу груз величиной в 30 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:
|
Поставщик |
Потребитель |
Запасы | |||||||||||||||||||
|
B1 |
B2 |
B3 |
B4 |
B5 | |||||||||||||||||
|
A1 |
|
|
|
|
|
320 | |||||||||||||||
|
A2 |
|
|
|
|
|
280 | |||||||||||||||
|
A3 |
|
|
|
|
|
250 | |||||||||||||||
|
Потребность |
150 |
140 |
110 |
230 |
220 |
Целевая функция F= 11770
Значение целевой функции изменилось на 240 единиц по сравнению с предыдущим этапом.
Этап 4
Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci, j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj:
U1=0
V1=C1,1-U1= 20
V4=C1,4-U1= 15
U3=C1,3-V1= -14
U2=C4,2-V4= 4
V2=C2,2-U2= 11
V3=C2,3-U2= 12
V5=C3,5-U3= 22
Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток.
S1,2 = c1,2 - (u1 + v2) = 12.
S1,3 = c1,3 - (u1 + v3) = 8.
S1,5 = c1,5 - (u1 + v5) = 2.
S2,1 = c2,1 - (u2 + v1) = 5.
S2,5 = c2,5 - (u2 + v5) = 3.
S3,2 = c3,2 - (u3 + v2) = 14.
S3,3 = c3,3 - (u3 + v3) = 12.
S3,4 = c3,4 - (u3 + v4) = 8.
Так как все оценки Si, j>=0, то полученный план является оптимальным.
Транспортная задача решена.
|
Поставщик |
Потребитель |
Запасы | |||||||||||||||||||
|
B1 |
B2 |
B3 |
B4 |
B5 | |||||||||||||||||
|
A1 |
|
|
|
|
|
320 | |||||||||||||||
|
A2 |
|
|
|
|
|
280 | |||||||||||||||
|
A3 |
|
|
|
|
|
250 | |||||||||||||||
|
Потребность |
150 |
140 |
110 |
230 |
220 |
Целевая функция F= 11770
Ответ: F= 11770
| < Предыдущая | Следующая > |
|---|