Главная страница
Навигация по странице:

  • Шаг №1 . 1. Проводим редукцию матрицы по строкам

  • 2. Методом проб и ошибок

  • 4. Методом проб и ошибок определяем матрицу назначения Х

    		•

    на всякий пожарный завтра. Исходная матрица имеет вид


    Скачать 15.42 Kb.
    НазваниеИсходная матрица имеет вид
    Дата16.06.2022
    Размер15.42 Kb.
    Формат файлаdocx
    Имя файлана всякий пожарный завтра.docx
    ТипДокументы
    #596356


    Исходная матрица имеет вид:


    1
    4
    6
    3

    9
    7
    10
    9

    4
    5
    11
    7

    8
    7
    8
    5


    Шаг №1.

    1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.


    0
    3
    5
    2
    1

    2
    0
    3
    2
    7

    0
    1
    7
    3
    4

    3
    2
    3
    0
    5

    Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент.



    0
    3
    2
    2

    2
    0
    0
    2

    0
    1
    4
    3

    3
    2
    0
    0

    0
    0
    3
    0

    После вычитания минимальных элементов получаем полностью редуцированную матрицу.
    2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

    Фиксируем нулевое значение в клетке (1, 1). Другие нули в строке 1 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 3), (2; 2).

    Фиксируем нулевое значение в клетке (2, 3). Другие нули в строке 2 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 3), (2; 2).

    В итоге получаем следующую матрицу:


    [0]
    3
    2
    2

    2
    [-0-]
    [0]
    2

    [-0-]
    1
    4
    3

    3
    2
    [-0-]
    0

    Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 4-х независимых нулей (в матрице их только 2), то решение недопустимое.
    3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:

    строку 2, столбец 1, строку 4

    Получаем сокращенную матрицу (элементы выделены):


    0
    3
    2
    2

    2
    0
    0
    2

    0
    1
    4
    3

    3
    2
    0
    0

    Минимальный элемент сокращенной матрицы (min(3, 2, 2, 1, 4, 3) = 1) вычитаем из всех ее элементов:



    0
    2
    1
    1

    2
    0
    0
    2

    0
    0
    3
    2

    3
    2
    0
    0

    Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:



    0
    2
    1
    1

    3
    0
    0
    2

    0
    0
    3
    2

    4
    2
    0
    0


    Шаг №2.

    1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

    Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент.

    После вычитания минимальных элементов получаем полностью редуцированную матрицу.

    2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

    Фиксируем нулевое значение в клетке (1, 1). Другие нули в строке 1 и столбце 1 вычеркиваем.

    Фиксируем нулевое значение в клетке (2, 3). Другие нули в строке 2 и столбце 3 вычеркиваем.

    Фиксируем нулевое значение в клетке (3, 2). Другие нули в строке 3 и столбце 2 вычеркиваем.

    Фиксируем нулевое значение в клетке (4, 4). Другие нули в строке 4 и столбце 4 вычеркиваем.

    В итоге получаем следующую матрицу:


    [0]
    2
    1
    1

    3
    [-0-]
    [0]
    2

    [-0-]
    [0]
    3
    2

    4
    2
    [-0-]
    [0]

    Количество найденных нулей равно k = 4. В результате получаем эквивалентную матрицу Сэ:



    0
    2
    1
    1

    3
    0
    0
    2

    0
    0
    3
    2

    4
    2
    0
    0

    4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.



    [0]
    2
    1
    1

    3
    [-0-]
    [0]
    2

    [-0-]
    [0]
    3
    2

    4
    2
    [-0-]
    [0]

    Cmin = 10 + 1 + 5 + 5 = 21

    написать администратору сайта