Определите сложность алгоритма решения задачи. Умножение матриц размерности n
(Отметьте один правильный вариант ответа.)
Варианты ответа
О(n3)(Верный ответ)
О(n2)
О(n4)
Z = c11 x11 + c12 x12 + c21 x21 + c22 x22→ minпри ограничениях
x11+x12=a1x21+x22=a2x11+x21=b1x12+x22=b2при условии неотрицательности решения, xij≥ 0, и баланса: a1+a2=b1+b2. Введем сквозную нумерацию переменных и исключим из рассмотрения последнее условие (устраним линейную зависимость уравнений на основе баланса). Система уравнений всех граней (действительных и возможных) многогранника допустимых решений имеет вид:
y1 | +y2 | =a1 | |
y3+y4 | =a2 | ||
y1 | +y3 | =b1 | |
y1 | =0 | ||
y2 | =0 | ||
y3 | =0 | ||
y4 | =0 |
Z = c11 x11 + c12 x12 + c21 x21 + c22 x22→ minпри ограничениях
x11+x12=a1x21+x22=a2x11+x21=b1x12+x22=b2при условии неотрицательности решения, xij≥ 0, и баланса: a1+a2=b1+b2. Введем сквозную нумерацию переменных и исключим из рассмотрения последнее условие (устраним линейную зависимость уравнений на основе баланса). Система уравнений всех граней (действительных и возможных) многогранника допустимых решений имеет вид:
y1 | +y2 | =a1 | |
y3+y4 | =a2 | ||
y1 | +y3 | =b1 | |
y1 | =0 | ||
y2 | =0 | ||
y3 | =0 | ||
y4 | =0 |
Z = c11 x11 + c12 x12 + c21 x21 + c22 x22→ minпри ограничениях
x11+x12=a1x21+x22=a2x11+x21=b1x12+x22=b2при условии неотрицательности решения, xij≥ 0, и баланса: a1+a2=b1+b2. Введем сквозную нумерацию переменных и исключим из рассмотрения последнее условие (устраним линейную зависимость уравнений на основе баланса). Система уравнений всех граней (действительных и возможных) многогранника допустимых решений имеет вид:
y1 | +y2 | =a1 | |
y3+y4 | =a2 | ||
y1 | +y3 | =b1 | |
y1 | =0 | ||
y2 | =0 | ||
y3 | =0 | ||
y4 | =0 |