Optimization-and-Control-Methods

Problem 1. Формула Шермана-Моррисона

Input file name: standard input

Output file name: standard output

Time limit: 5 s

Memory limit: 256 MB

Вам дана квадратная матрица A и ее обратная матрица B.
Вам необходимо заменить в матрице A i-й столбец на вектор x и найти обратную матрицу к новой матрице.
Гарантируется что матрица B является обратной матрицей к матрице A.

Input

В первой строке входных данных находится два целых числа n, i (1<=n<=500, 1<=i<=n) — размер квадратной матрицы, а также номер столбца который необходимо заменить пронумерованный с единицы.
В следующих n строках задано по n дробных чисел a[i][j] (−500<=a[i][j]<=500) — значения элементов матрицы A.
В следующих n строках задано по n дробных чисел b[i][j] (−500<=b[i][j]<=500) — значения элементов матрицы B.
В следующей строке задано по n чисел x[i]​ (−500<=x[i]<=500) — значения элементов вектора x.

Output

В первой строке выведите YES, если новая матрица является невырожденной, NO — в противном случае. Если новая матрица является невырожденной выведите n строк по n чисел в каждой — новую обратную матрицу.
Абсолютная или относительная погрешность не должны превышать 10^-6.

Problem 2. Основная фаза симплекс-метода

Input file name: standard input

Output file name: standard output

Time limit: 3 s

Memory limit: 256 MB

В данной задаче необходимо реализовать алгоритм основной фазы симплекс метода.
В задаче дана матрица A, вектор b, а также вектор c.
А также вам известен начальный базисный план и базис Jб​.
Необходимо вывести оптимальный план для заданных соотношений:
Ax=b
cx→max⁡

Input

В первой строке входных данных находится два целых числа m, n (1<=m<=n<=500 ) — размер матрицы A, mстрок по n столбцов.
В следующих m строках задано по n целых чисел a[i][j] (−500<=a[i][j]<=500) — значения элементов матрицы A.
В следующей строке задано m целых чисел b[i] (−500<=b[i]<=500) — значения элементов вектора b.
В следующей строке задано n целых чисел c[i]​ (−500<=c[i]<=500) — значения элементов вектора c.
В следующей строке задано n дробных чисел x[i] (−500<=x[i]<=500) — значения элементов начального плана x.
В следующей строке задано m целых чисел j[i] ​(−500<=j[i]<=500) — значения индексов базиса.

Output

В первой строке выходных данных необходимо вывести следующее:
Если задача не ограничена выведите Unbounded
Иначе выведите Bounded
На второй строке выходных данных, в случае если ответ существует, необходимо вывести n дробных чисел через пробел — значения вектора x.
Абсолютная или относительная погрешность не должны превышать 10^(-6).

Problem 3. Первая фаза симплекс метода

Input file name: standard input

Output file name: standard output

Time limit: 3 s

Memory limit: 256 MB

В данной задаче необходимо реализовать алгоритм первой фазы симплекс метода.
В задаче дана матрица A, вектор b, а также вектор c.
Необходимо вывести любой план для заданных соотношений
Ax=b
cx→max⁡

Input

В первой строке входных данных находится два целых числа m, n (1<=m<=n<=500) — размер матрицы A, m строк по n столбцов.
В следующих m строках задано по n целых чисел a[i][j] (−500<=a[i][j]≤500) — значения элементов матрицы A.
В следующей строке задано m целых чисел b[i]​ (−500<=b[i]<=500) — значения элементов вектора b.
В следующей строке задано n целых чисел c[i] (−500<=c[i]<=500) — значения элементов вектора c.

Output

В первой строке выходных данных необходимо вывести следующее:
Если данная задача не имеет решений необходимо вывести No solution.
Если задача не ограничена выведите Unbounded
Иначе выведите Bounded
На второй строке выходных данных, в случае если ответ существует, необходимо вывести n дробных чисел через пробел  — значения вектора x.
Абсолютная или относительная погрешность не должны превышать 10^(-16).

Problem 4. Симплекс метод

Input file name: standard input

Output file name: standard output

Time limit: 3 s

Memory limit: 256 MB

В данной задаче необходимо реализовать алгоритм симплекс метода.
В задаче дана матрица A, вектор b, а также вектор c.
Необходимо вывести оптимальный план для заданных соотношений
Ax=b
cx→max⁡

Input

В первой строке входных данных находится два целых числа m, n (1<=m<=n<=500) — размер матрицы A, m строк по n столбцов.
В следующих m строках задано по n целых чисел a[i][j] (−500<=a[i][j]≤500) — значения элементов матрицы A.
В следующей строке задано m целых чисел b[i]​ (−500<=b[i]<=500) — значения элементов вектора b.
В следующей строке задано n целых чисел c[i] (−500<=c[i]<=500) — значения элементов вектора c.

Output

В первой строке выходных данных необходимо вывести следующее:
Если данная задача не имеет решений необходимо вывести No solution.
Если задача не ограничена выведите Unbounded
Иначе выведите Bounded
На второй строке выходных данных, в случае если ответ существует, необходимо вывести n дробных чисел через пробел  — значения вектора x.
Абсолютная или относительная погрешность не должны превышать 10^(-16).

Problem 5. Матричная транспортная задача

Input file name: standard input

Output file name: standard output

Time limit: 3 s

Memory limit: 256 MB

Пусть имеется mmm пунктов производства некоторого однородного продукта и nnn пунктов его потребления. Для каждого пункта производства i=1,2,…,m и для каждого пункта потребления j=1,2,…,n заданы следующие величины: объём производства a[i] пункте производства i, объём потребления b[j]​ в пункте потребления j, затраты на перевозку единицы продукта c[i][j]​ от пункта производства i до пункта потребления j.
Требуется составить план перевозок, позволяющий вывезти продукты производителей, обеспечивающий потребности потребителей и дающий минимум суммарных затрат на перевозку.
Обозначим как x[i][j] объёмы перевозок от поставщика i до потребителя j.

Input

В первой строке входных данных находится два целых числа m, n (1<=m<=n<=200) — количество пунктов производства и пунктов потребления соответственно.
В следующих m строках задано по n целых чисел c[i][j]​ (−500<=c[i][j]<=500) — значения элементов стоимости перевозок.
В следующей строке задано m целых чисел a[i] (0<=a[i]<=500) — значения элементов вектора a.
В следующей строке задано n целых чисел b[i] (0<=b[i]<=500) — значения элементов вектора b.

Output

Выведите m строк по n целых чисел  — объемы перевозок.

Problem 6. Квадратичное программирование

Input file name: standard input

Output file name: standard output

Time limit: 3 s

Memory limit: 256 MB

В данной задаче необходимо реализовать итерационный алгоритм для решения задачи квадратичного программирования.
В задаче дана матрица A, вектор b, вектор c и симметричная положительно полуопределенная матрица D. Также вам известен опорный план {x, J[опт], J*}.


Необходимо вывести оптимальный план для заданных соотношений:
Ax = b, x >= 0
c'x + (1/2)x'Dx -> min

Input

В первой строке входных данных находится два целых числа m, n, k (1<=m<=k<=n<=100) — размер матрицы A, m строк по n столбцов, а также k - количество индексов расширенного базиса.
В следующих m строках задано по n целых чисел a[i][j] (−500<=a[i][j]<=500) — значения элементов матрицы A.
В следующей строке задано m целых чисел b[i]​ (−500<=b[i]<=500) — значения элементов вектора b.
В следующей строке задано n целых чисел c[i]​ (−500<=c[i]<=500) — значения элементов вектора c.
В следующих n строках задано по n целых чисел d[i][j]​ (−500<=d[i][j]<=500) — значения элементов матрицы D.
В следующей строке задано n дробных чисел x[i] (0<=x[i]<=500) — значения элементов плана x.
В следующей строке задано m целых чисел j[опт][i]​​ (1<=j[опт][i]<=n) — значения индексов опорного базиса.
В следующей строке задано k целых чисел j*[i] (1<=j*[i]<=n) — значения индексов расширенного базиса.

Output

В первой строке выходных данных необходимо вывести следующее:
Если задача не ограничена выведите Unbounded
Иначе выведите Bounded
На второй строке выходных данных, в случае если ответ существует, необходимо вывести n дробных чисел через пробел  — значения вектора x.
Абсолютная или относительная погрешность не должны превышать 10^(-6).