|
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
x 7 |
|
0: 1 |
1: 1 |
1: 1 |
1: 1 |
1: 1 |
1: 1 |
0: 1 |
0: 1 |
|
0-(0 • 3):1 |
7-(1 • 3):1 |
5-(1 • 3):1 |
3-(1 • 3):1 |
2-(1 • 3):1 |
0-(1 • 3):1 |
1-(0 • 3):1 |
0-(0 • 3):1 |
|
0-(0 • 10):1 |
3-(1 • 10):1 |
5-(1 • 10):1 |
10-(1 • 10):1 |
15-(1 • 10):1 |
0-(1 • 10):1 |
0-(0 • 10):1 |
1-(0 • 10):1 |
|
0-(0 • -11):1 |
-5-(1 • -11):1 |
-5-(1 • -11):1 |
-11-(1 • -11):1 |
0-(1 • -11):1 |
0-(1 • -11):1 |
0-(0 • -11):1 |
0-(0 • -11):1 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x3 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
x6 |
0 |
4 |
2 |
0 |
-1 |
-3 |
1 |
0 |
|
x7 |
0 |
-7 |
-5 |
0 |
5 |
-10 |
0 |
1 |
|
F(X1) |
0 |
6 |
6 |
0 |
11 |
11 |
0 |
0 |
. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант
симплекс-таблицы:
|
БазисBx1x2x3x4x5x6x7 |
|
|
|
|
|
|
|
|
|
x3 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
x6 |
0 |
4 |
2 |
0 |
-1 |
-3 |
1 |
0 |
|
x7 |
0 |
-7 |
-5 |
0 |
5 |
-10 |
0 |
1 |
|
F(X2) |
0 |
6 |
6 |
0 |
11 |
11 |
0 |
0 |
Оптимальный план можно записать так:
3 = 0(X) = 11•0 + 9 = 9
3. Транспортная задача
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
Распределительный метод является одним из вариантов базового симплексного метода. Поэтому идея распределительного метода (как и симплексного) содержит такие же три существенных момента.
Прежде всего отыскивается какое-то решение
задачи - исходный опорный план. Затем посредством специальных показателей
опорный план проверяется на оптимальность. Если план оказывается не
оптимальным, переходят к другому плану. При этом второй и последующие планы
должны быть лучше предыдущего. Так за несколько последовательных переходов от
не оптимального плана приходят к оптимальному.
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
12 |
10 |
6 |
12 |
18 |
410 |
|
2 |
15 |
6 |
13 |
15 |
23 |
310 |
||||||
|
3 |
21 |
18 |
14 |
19 |
22 |
230 |
||||||
|
Потребности |
210 |
180 |
240 |
225 |
175 |
|
Проверим необходимое и достаточное
условие разрешимости задачи.
∑ a = 410 + 310 + 230 = 950
∑ b = 210 + 180 + 240 + 225 +
175 = 1030
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равным 80 (1030-950). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
|
12345Запасы |
|
|
|
|
|
|
|
1 |
12 |
10 |
6 |
12 |
18 |
410 |
|
2 |
15 |
6 |
13 |
15 |
23 |
310 |
|
3 |
21 |
18 |
14 |
19 |
22 |
230 |
|
4 |
0 |
0 |
0 |
0 |
0 |
80 |
|
Потребности |
210 |
180 |
240 |
225 |
175 |
|
Первая итерация заключается в определении исходного опорного плана и проверке его на оптимальность.
Определение исходного опорного плана. Первый опорный план может быть найден посредством различных способов: по правилу северо-западного угла, приоритету ближайших пунктов, способу минимального элемента С=(cij), способу Фогеля и по способу Лебедева-Тихомирова.
Этап I. Поиск первого опорного плана.
. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 6
Для этого элемента запасы равны 410, потребности 240. Поскольку минимальным является 240, то вычитаем его.
13 = min(410,240) = 240.
|
12 |
10 |
6 |
12 |
18 |
410 - 240 = 170 |
|
15 |
6 |
x |
15 |
23 |
310 |
|
21 |
18 |
x |
19 |
22 |
230 |
|
0 |
0 |
x |
0 |
0 |
80 |
|
210 |
180 |
240 - 240 = 0 |
225 |
175 |
0 |
Искомый элемент равен 6
Для этого элемента запасы равны 310, потребности 180. Поскольку минимальным является 180, то вычитаем его.
22 = min(310,180) = 180.
|
12 |
x |
6 |
12 |
18 |
170 |
|
15 |
6 |
x |
15 |
23 |
310 - 180 = 130 |
|
21 |
x |
x |
19 |
22 |
230 |
|
0 |
x |
x |
0 |
0 |
80 |
|
210 |
180 - 180 = 0 |
0 |
225 |
175 |
0 |
Искомый элемент равен 12
Для этого элемента запасы равны 170, потребности 210. Поскольку минимальным является 170, то вычитаем его.
11 = min(170,210) = 170.
|
12 |
x |
6 |
x |
x |
170 - 170 = 0 |
|
15 |
6 |
x |
15 |
23 |
130 |
|
21 |
x |
x |
19 |
22 |
230 |
|
0 |
x |
x |
0 |
0 |
80 |
|
210 - 170 = 40 |
0 |
0 |
225 |
175 |
0 |
Искомый элемент равен 15
Для этого элемента запасы равны 130,
потребности 40. Поскольку минимальным является 40, то вычитаем его.
x21 = min(130,40) = 40.
|
12 |
x |
6 |
x |
x |
0 |
|
15 |
6 |
x |
15 |
23 |
130 - 40 = 90 |
|
x |
x |
x |
19 |
22 |
230 |
|
x |
x |
x |
0 |
0 |
80 |
|
40 - 40 = 0 |
0 |
0 |
225 |
175 |
0 |
Искомый элемент равен 15
Для этого элемента запасы равны 90, потребности 225. Поскольку минимальным является 90, то вычитаем его.
24 = min(90,225) = 90.
|
12 |
x |
6 |
x |
x |
0 |
|
15 |
6 |
x |
15 |
x |
90 - 90 = 0 |
|
x |
x |
x |
19 |
22 |
230 |
|
x |
x |
x |
0 |
0 |
80 |
|
0 |
0 |
0 |
225 - 90 = 135 |
175 |
0 |
Искомый элемент равен 19
Для этого элемента запасы равны 230, потребности 135. Поскольку минимальным является 135, то вычитаем его.
34 = min(230,135) = 135.
|
12 |
x |
6 |
x |
x |
0 |
|
15 |
6 |
x |
15 |
x |
0 |
|
x |
x |
x |
19 |
22 |
230 - 135 = 95 |
|
x |
x |
x |
x |
0 |
80 |
|
0 |
0 |
0 |
135 - 135 = 0 |
175 |
0 |
Искомый элемент равен 22
Для этого элемента запасы равны 95, потребности 175. Поскольку минимальным является 95, то вычитаем его.
35 = min(95,175) = 95.
|
12 |
x |
6 |
x |
x |
0 |
|
15 |
6 |
x |
15 |
x |
0 |
|
x |
x |
x |
19 |
22 |
95 - 95 = 0 |
|
x |
x |
x |
x |
0 |
80 |
|
0 |
0 |
0 |
0 |
175 - 95 = 80 |
0 |
Искомый элемент равен 0
Для этого элемента запасы равны 80, потребности 80. Поскольку минимальным является 80, то вычитаем его.
45 = min(80,80) = 80.
|
12 |
x |
6 |
x |
x |
0 |
|
15 |
6 |
x |
15 |
x |
0 |
|
x |
x |
x |
19 |
22 |
0 |
|
x |
x |
x |
x |
0 |
80 - 80 = 0 |
|
0 |
0 |
0 |
0 |
80 - 80 = 0 |
0 |
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
||||||
|
1 |
12[170] |
10 |
6[240] |
12 |
18 |
410 |
15[40] |
6[180] |
13 |
15[90] |
23 |
310 |
|
3 |
21 |
18 |
14 |
19[135] |
22[95] |
230 |
||||||
|
4 |
0 |
0 |
0 |
0 |
0[80] |
80 |
||||||
|
Потребности |
210 |
180 |
240 |
225 |
175 |
|