Цикл приведен в таблице (4,3 → 4,5 → 3,5 → 3,4 → 2,4 → 2,1 → 1,1 → 1,3).
Оценка свободной клетки равна Δ43 = (0) - (0) + (22) - (19) + (15) - (15) + (12) - (6) = 9.
(4;4): В свободную клетку (4;4)
поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки
«-», «+», «-».
|
|
1 |
2 |
3 |
4 |
5 |
Запасы |
|
1 |
12[170] |
10 |
6[240] |
12 |
18 |
410 |
|
2 |
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 |
|
Цикл приведен в таблице (4,4 → 4,5 → 3,5 → 3,4).
Оценка свободной клетки равна Δ44 = (0) - (0) + (22) - (19) = 3.
Из приведенного расчета видно, что ни одна свободная клетка не имеет отрицательной оценки, следовательно, дальнейшее снижение целевой функции Fx невозможно, поскольку она достигла минимального значения.
Таким образом, последний опорный план является оптимальным.
Минимальные затраты составят:
*170 + 6*240 + 15*40 + 6*180 + 15*90
+ 19*135 + 22*95 + 0*80 = 11165
Если в оптимальном решении задачи имеется несколько оценок равных нулю, то это является свидетельством того, что среди бесчисленного множества решений этой задачи существуют еще решения, являющиеся также оптимальными, поскольку значение целевой функции остается одинаковым - минимальным. Их принято называть альтернативными.
Примечание. Основной алгоритм распределительного метода является не лучшим методом решения транспортных задач, так как на каждой итерации для проверки опорного плана на оптимальность приходилось строить [mп-(m+n-1)] циклов пересчета, что при больших размерах матрицы оказывается очень громоздким и трудоемким делом. Так, для расчетов по матрице 10х10 на каждой итерации надо строить 81 цикл, а по матрице 20x20 - 361 цикл.
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 1-й магазин (170), в 3-й магазин (240)
Из 2-го склада необходимо груз направить в 1-й магазин (40), в 2-й магазин (180), в 4-й магазин (90)
Из 3-го склада необходимо груз направить в 4-й магазин (135), в 5-й магазин (95)
Потребность 5-го магазина остается неудовлетворенной на 80 ед.
Оптимальный план является
вырожденным, так как базисная переменная x45=0.
. Задача о назначениях
Исходные данные
|
Бригада |
Виды работ |
||||
|
|
1 |
2 |
3 |
4 |
5 |
|
1 |
2 |
5 |
16 |
2 |
2 |
|
2 |
0 |
7 |
8 |
5 |
10 |
|
3 |
4 |
17 |
6 |
3 |
3 |
|
4 |
6 |
11 |
11 |
7 |
8 |
|
5 |
6 |
12 |
2 |
13 |
12 |
Исходная матрица имеет вид:
|
2 |
5 |
16 |
2 |
2 |
|
0 |
7 |
8 |
5 |
10 |
|
4 |
17 |
6 |
3 |
3 |
|
6 |
11 |
11 |
7 |
8 |
|
6 |
12 |
2 |
13 |
12 |
Шаг №1.
. Проводим редукцию матрицы по
строкам. В связи с этим во вновь полученной матрице в каждой строке будет как
минимум один ноль.
|
0 |
3 |
14 |
0 |
0 |
2 |
|
0 |
7 |
8 |
5 |
10 |
0 |
|
1 |
14 |
3 |
0 |
0 |
3 |
|
0 |
5 |
5 |
1 |
2 |
6 |
|
4 |
10 |
0 |
11 |
10 |
2 |
Затем такую же операцию редукции
проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
|
0 |
0 |
14 |
0 |
0 |
|
0 |
4 |
8 |
5 |
10 |
|
1 |
11 |
3 |
0 |
0 |
|
0 |
2 |
5 |
1 |
2 |
|
4 |
7 |
0 |
11 |
10 |
|
0 |
3 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 5).
Другие нули в строке 1 и столбце 5 вычеркиваем.
Фиксируем нулевое значение в клетке (2, 1).
Другие нули в строке 2 и столбце 1 вычеркиваем.
Фиксируем нулевое значение в клетке (3, 4).
Другие нули в строке 3 и столбце 4 вычеркиваем.
В итоге получаем следующую матрицу:
|
[-0-] |
[-0-] |
14 |
[-0-] |
[0] |
|
[0] |
4 |
8 |
5 |
10 |
|
1 |
11 |
3 |
[0] |
[-0-] |
|
[-0-] |
2 |
5 |
1 |
2 |
|
4 |
7 |
0 |
11 |
10 |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 3), то решение недопустимое.
. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
строку 1,
столбец 1,
строку 3,
столбец 3,
Получаем сокращенную матрицу
(элементы выделены):
|
0 |
0 |
14 |
0 |
0 |
|
0 |
4 |
8 |
5 |
10 |
|
1 |
11 |
3 |
0 |
0 |
|
0 |
2 |
5 |
1 |
2 |
|
4 |
7 |
0 |
11 |
10 |
Минимальный элемент сокращенной
матрицы (min(4, 5, 10, 2, 1, 2, 7, 11, 10) = 1) вычитаем из всех ее элементов:
|
0 |
0 |
14 |
0 |
0 |
|
0 |
3 |
8 |
4 |
9 |
|
1 |
11 |
3 |
0 |
0 |
|
0 |
1 |
5 |
0 |
1 |
|
4 |
6 |
0 |
10 |
9 |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
|
1 |
0 |
15 |
0 |
0 |
|
0 |
3 |
8 |
4 |
9 |
|
2 |
11 |
4 |
0 |
0 |
|
0 |
1 |
5 |
0 |
1 |
|
4 |
6 |
0 |
10 |
9 |
Шаг №2.
. Проводим редукцию матрицы по
строкам. В связи с этим во вновь полученной матрице в каждой строке будет как
минимум один ноль.
|
1 |
0 |
15 |
0 |
0 |
0 |
|
0 |
3 |
8 |
4 |
9 |
0 |
|
2 |
11 |
4 |
0 |
0 |
0 |
|
0 |
1 |
5 |
0 |
1 |
0 |
|
4 |
6 |
0 |
10 |
9 |
0 |
Затем такую же операцию редукции
проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
|
1 |
0 |
15 |
0 |
0 |
|
0 |
3 |
8 |
4 |
9 |
|
2 |
11 |
4 |
0 |
0 |
|
0 |
1 |
5 |
0 |
1 |
|
4 |
6 |
0 |
10 |
9 |
|
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 2). Другие нули в строке 1 и столбце 2 вычеркиваем.
Фиксируем нулевое значение в клетке (2, 1). Другие нули в строке 2 и столбце 1 вычеркиваем.
Фиксируем нулевое значение в клетке (3, 5). Другие нули в строке 3 и столбце 5 вычеркиваем.
Фиксируем нулевое значение в клетке (4, 4). Другие нули в строке 4 и столбце 4 вычеркиваем.
Фиксируем нулевое значение в клетке (5, 3). Другие нули в строке 5 и столбце 3 вычеркиваем.
В итоге получаем следующую матрицу:
|
1 |
[0] |
15 |
[-0-] |
[-0-] |
|
[0] |
3 |
8 |
4 |
9 |
|
2 |
11 |
4 |
[-0-] |
[0] |
|
[-0-] |
1 |
5 |
[0] |
1 |
|
4 |
6 |
[0] |
10 |
9 |
Количество найденных нулей равно k =
5. В результате получаем эквивалентную матрицу Сэ:
|
1 |
0 |
15 |
0 |
0 |
|
0 |
3 |
8 |
4 |
9 |
|
2 |
11 |
4 |
0 |
0 |
|
0 |
1 |
5 |
0 |
1 |
|
4 |
6 |
0 |
10 |
9 |
. Методом проб и ошибок определяем
матрицу назначения Х, которая позволяет по аналогично расположенным элементам
исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
|
1 |
[0] |
15 |
[-0-] |
[-0-] |
|
[0] |
3 |
8 |
4 |
9 |
|
2 |
11 |
4 |
[-0-] |
[0] |
|
[-0-] |
1 |
5 |
[0] |
1 |
|
4 |
6 |
[0] |
10 |
9 |
= 3 + 5 + 0 + 7 + 2 = 17
. Задача о ранце
|
Направление |
Планируемая прибыль |
Стоимость проекта |
|
I |
200 |
300 |
|
II |
150 |
200 |
|
III |
400 |
145 |
|
IV |
160 |
120 |
|
V |
840 |
650 |
|
VI |
750 |
650 |