|
Текст подпрограммы и версий mlc2r_c.zip |
Тексты тестовых примеров tmlc2r_c.zip |
Решение задачи линейного целочисленного программирования методом Гомори (полностью целочисленный алгоритм).
Для решения задачи
n
max ( z0 + ∑ cj (-xj) ) , A x ≤ b , xj ≥ 0 ,
x j=1
где c и x - целочисленные векторы из En, A - целочисленная матрица порядка m на n, b - целочисленный вектоp из Em, z0 - заданное число, используется полностью целочисленный алгоритм Гомори.
Исходная информация задается в виде расширенной матрицы А порядка (2 + m + n) на (1 + n):
| z0 cT |
| 0 - E |
А =
| b A |
| o 0 T |
где E - единичная матрица порядка n на n, 0 - нулевой вектор.
Hа каждой итерации метода на месте последней строки матрицы А строится дополнительное целочисленное ограничение, котоpое используется в качестве ведущей строки.
Если решение существует, то оно определяется за конечное число итераций.
Xу T., Целочисленное программирование и потоки в сетях, М., Мир, 1974.
int mlc2r_c (integer *a, integer *m, integer *n, integer *mr,
integer *max, real *eps, integer *ierr)
Параметры
| a - | заданная целая матрица A порядка (2 + m + n) на (n + 1); |
| m - | число стpок в матрице A, pавное 2 + m + n (тип: целый); |
| n - | число столбцов в матрице A, pавное n + 1 (тип: целый); |
| mr - | целый вектоp длины 2m + 2n, используемый в подпрограмме как рабочий; |
| max - | заданное целое число (см. замечания по использованию); |
| eps - | заданная абсолютная погрешность округления вещественного числа до целого (тип: вещественный); |
| ierr - | целая переменная, указывающая причину окончания процесса вычислений: |
| ierr= 0 - | если найдено оптимальное решение; |
| ierr=65 - | если такое решение не существует. |
Версии: нет
Вызываемые подпрограммы: нет
Замечания по использованию
| 1. |
Используются служебные подпрограммы: mlc21_c, mlc22_c, mlc23_c, mlc24_c, mlc25_c, mlc26_c, mlc27_c. | |
| 2. |
Задаваемое значение параметра max должно быть оценкой свеpху для суммы компонент вектоpа x, т.е. n
∑ xj ≤ max
j=1
| |
| 3. |
B процессе вычислений производится округление некоторых вещественных чисел с использованием параметра eps, 0 < eps < 0.5. b частности, вещественное число y заменяется целым k, если abs (y - k) ≤ eps. Выбор конкретного значения параметра eps во многом определяется коэффициентами условий задачи, однако, обычно eps берется из интервала (10 - 7, 10 - 4). | |
| 4. | По окончании работы программы элемент a (1, 1) содержит оптимальное значение линейной формы, n следующих элементов первого столбца - компоненты оптимального вектоpа x, m следующих - значения компонент вектоpа (b - a x) дополнительных переменных. |
Максимизировать 4 x1 + 5 x2 + x3
при условиях
3 x1 + 2 x2 ≤ 10
x1 + 4 x2 ≤ 11
3 x1 + 3 x2 + x3 ≤ 13 ,
x1, x2, x3 ≥ 0 , целые
| 0 -4 -5 -1 |
| 0 -1 0 0 |
| 0 0 -1 0 |
| 0 0 0 -1 |
a = | 10 3 2 0 |
| 11 1 4 0 |
| 13 3 3 1 |
| 0 0 0 0 |
int main(void)
{
/* Initialized data */
static int a[32] /* was [8][4] */ = { 0,0,0,0,10,11,13,0,-4,-1,
0,0,3,1,3,0,-5,0,-1,0,2,4,3,0,-1,0,0,-1,0,0,1,0 };
static int m = 8;
static int n = 4;
static int max__ = 10;
static float eps = .001f;
/* Local variables */
static int ierr;
extern int mlc2r_c(int *, int *, int *, int *, int *, float *, int *);
static int mr[24];
#define a_ref(a_1,a_2) a[(a_2)*8 + a_1 - 9]
mlc2r_c(a, &m, &n, mr, &max__, &eps, &ierr);
printf("\n %5i %5i %5i %5i \n",
a_ref(1, 1), a_ref(2, 1), a_ref(3, 1), a_ref(4, 1));
return 0;
} /* main */
Результаты:
max z = a(1, 1) = 19
x1 = a(2, 1) = 2
x2 = a(3, 1) = 2
x3 = a(4, 1) = 1