Составим двойственную задачу к прямой задаче.
Z(y)=-14y1-300y2 → max15y1-150y2≤15,4y1-200y2≤20,y1 ≤ 0,y2 > 0.
Из 1-го склада необходимо весь груз направить к 2-у потребителю.
Из 2-го склада необходимо груз направить к 1-у потребителю (20 ед.), к 2-у потребителю (10 ед.), к 4-у потребителю (10 ед.)
Из 3-го склада необходимо весь груз направить к 3-у потребителю.
Из 4-го склада необходимо весь груз направить к 3-у потребителю.
Из 5-го склада необходимо весь груз направить к 4-у потребителю.
Минимальные затраты составят:
F(x) = 1∙30 + 1∙20 + 5∙10 + 1∙10 + 3∙10 + 1∙18 + 1∙10 + 0∙2 = 168.
Решение
Для устранения дисбаланса добавляем дополнительные строки.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
800 620 410 0 500 200
350 0 650 550 80 250
200 600 0 680 400 100
690 760 0 80 220 220
0 0 0 0 0
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент.
800 620 410 0 500
350 0 650 550 80
200 600 0 680 400
690 760 0 80 220
0 0 0 0 0
0 0 0 0 0
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 4). Другие нули в строке 1 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (5; 4)
Фиксируем нулевое значение в клетке (2, 2). Другие нули в строке 2 и столбце 2 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (5; 2)
Фиксируем нулевое значение в клетке (3, 3). Другие нули в строке 3 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 3), (5; 3)
В итоге получаем следующую матрицу:
800 620 410 [0] 500
350 [0] 650 550 80
200 600 [0] 680 400
690 760 [-0-] 80 220
0 [-0-] [-0-] [-0-] 0
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 3), то решение недопустимое.
3. Проводим модификацию матрицы
. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
строку 5, столбец 3, строку 1, столбец 2
Получаем сокращенную матрицу (элементы выделены):
800 620 410 0 500
350 0 650 550 80
200 600 0 680 400
690 760 0 80 220
0 0 0 0 0
Минимальный элемент сокращенной матрицы (min(350, 550, 80, 200, 680, 400, 690, 80, 220) = 80) вычитаем из всех ее элементов:
800 620 410 0 500
270 0 650 470 0
120 600 0 600 320
610 760 0 0 140
0 0 0 0 0
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
800 700 490 0 500
270 0 650 470 0
120 600 0 600 320
610 760 0 0 140
0 80 80 0 0
4. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент.
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
5. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 4). Другие нули в строке 1 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 4), (5; 4)
Фиксируем нулевое значение в клетке (2, 5). Другие нули в строке 2 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (5; 5), (2; 2).
Фиксируем нулевое значение в клетке (3, 3)
Задать вопрос
на новый заказ в Автор24.
