![]() |
![]() ![]() |
![]() |
trminator |
![]()
Сообщение
#1
|
Четыре квадратика ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: ![]() ![]() ![]() |
Задача:
Требуется найти максимум функции: Код c[1]*x[1] + c[2]*x[2] + ... + c[n]*x[n] -> max при ограничениях: Код a[1,1]*x[1] + a[1,2]*x[2] + ... + a[1,n]*x[n] <= b[1] ... a[m,1]*x[1] + a[m,2]*x[2] + ... + a[m,n]*x[n] <= b[m] x[i] >= 0, x = 1, ..., n Другой вариант записи задачи: Код C*X -> max A[M,N]*X[N] <= B[M] X >= 0 Решение задачи можно искать с помощью простого симплексного метода, например, как в такой программе (программа написана для компилятора Дельфи или FPC, но должна пойти и на TP, если изменить пару строк):
Пояснения: Симплекс-метод решает ЗЛП в стандартной форме: Код C*X -> max A*X = B X >= 0 А дана задача в канонической форме. Чтобы привести задачу из исходной (канонической) формы, вводим дополнительные переменные: Код C*X + 0*Y -> max A*X + E*Y = B X, Y >= 0 где Е - единичная матрица. Все структуры данных, нужные для работы метода, хранятся в одной симплексной таблице, которая перед вызовом самого метода должна выглядеть так: Код ┌─────────────────┬──────────┬───┐ │ │ 1 │ │ │ │ 1 │ │ │ A[M,N] │ 1 │ B │ │ │ 1 │ │ │ │ 1│ │ ├─────────────────┼──────────┼───┤ │ -С │ 0 │ 0 │ └─────────────────┴──────────┴───┘ На каждом шаге алгоритма: 1) Выбираем первый "слева" столбец j0, в котором в последней строке - отрицательное число. Если такого столбца нет, то заканчиваем работу алгоритма 2) Выбираем строку, для которой отношение <элемент последнего столбца> / A[i, j0] минимально. 3) Выполняем со всей таблицей преобразование Жордана-Гаусса с ведущим столбцом j0 и ведущей строкой i0, то есть добиваемся, чтобы в столбце j0 все элементы стали равными 0, кроме i0-го элемента, который будет равен 1 После окончания работы алгоритма в последнем столбце будут храниться значения переменных, на которых достигается максимум функции, а само значение функции будет лежать в правом нижнем углу таблицы. Замечание: в найденном решении будет m (а то и меньше) неотрицательных элементов, а не n. Такое решение называется базисным. Как вариант, можно выбирать столбец j0 как столбец с максимальным по модулю отрицательным нижним элементом. Так алгоритм потребует меньше итераций, но может зациклиться (а то правило выбора пары i0, j0, которое используется в этом алгоритме, гарантирует, что зацикливаться программа не будет. Правило называется правилом Бленда). P.S. Пример входного файла, которым питается программа: Код 3 2 3 4 5 1 5 3 4 1 2 200 160 Формат входных данных: n m - размерность матрицы fun - коэффициенты целевой функции A - сама матрица b - правые части ограничений Правильный ответ для этого примера: Код x[1] = 8.000 x[2] = 0.000 x[3] = 64.000 min f(x) = 344.000 |
![]() ![]() |
![]() |
Текстовая версия | 10.09.2024 14:47 |