|
Текст подпрограммы и версий mlc4r_c.zip |
Тексты тестовых примеров tmlc4r_c.zip |
Решение задачи целочисленного линейного программирования модифицированным методом Юнга.
Постановка задачи: найти мakcимyм (a, x) при условиях:
Ax ≤ b
n
∑ x j ≤ L ,
j =1
где x ≥ 0 - целый вектор длины n,
a - заданный целый вектор длины n,
A - заданная целая матрица размеров m*n,
b ≥ 0 - заданный целый вектор длины m,
L > 0 - заданное целое число.
Для решения задачи используется оригинальная модификация метода Юнга. Эта модификация удобна, когда матрица A слабо заполнена. Ненулевые элементы матрицы хранятся компактно в одномерном массиве в виде ai j*1000 + j. В отдельном целочисленном массиве длины m хранятся количества ненулевых элементов в строках матрицы A. В процессе вычислений преобразуется только небазисная матрица размеров n * n
Т.Ху. Целочисленное программирование и потоки в сетях. Изд - во "Мир", М., 1974.
int mlc4r_c (integer *na, integer *ns, integer *nai,
integer *naj, integer *l, integer *nb, integer *nr, integer *m,
integer *n, integer *n1, integer *mn, integer *it, real *tmax,
integer *ierr)
Параметры
| na - | заданный целый массив длины mn, в котором упакованы ненулевые элементы матрицы A (по строкам) по формуле ai j * 1000 + j; |
| ns - | заданный целый вектор длины m, содержащий количество ненулевых элементов в строках матрицы A; |
| nai - | заданный вектор правых частей длины m (тип: целый); |
| naj - | заданный вектор коэффициентов линейной формы длины n (тип: целый); |
| l - | заданная целая переменная (верхняя граница на сумму компонент вектора x); |
| nb - | целый рабочий массив размеров (n + 1) * (n + 1); |
| nr - | целый рабочий вектор длины 4 * (m + n + 2), на выходе в первых (m + n + 2) элементах вектора nr находится решение; |
| m - | m = m, целая переменная, число строк в матрице A; |
| n - | n = n, целая переменная, число столбцов в матрице A; |
| n1 - | n1 = n + 1, размер рабочей матрицы; |
| mn - | число ненулевых элементов в матрице A, тип целый; |
| it - | заданное максимальное число итераций, на выходе - выполненное число итераций, тип целый; |
| tmax - | заданное максимальное время работы программы (в секундах), тип вещественный; |
| ierr - | целая переменная, указывающая причину окончания счета; |
| ierr= 1 - | найдено оптимальное решение; |
| ierr= 2 - | выполнено заданное число итераций; |
| ierr= 3 - | истекло время; |
| ierr=65 - |
выполнилось ограничение
n
∑ x j = l
j =1
|
Версии: нет
Вызываемые подпрограммы: utmn05_c
Замечания по использованию
|
Для упаковки ненулевых элементов матрицы A удобно воспользоваться вспомогательной подпрограммой int utmlc_c(int *iv, int *n, int *iw), которая из целого вектора iv длины n строит целый вектор длины n/2, упаковывая каждую пару компонент вектора iv в одну компоненту вектора iw по формуле: iw(( i - 1)/2 + 1) = iv( i ) + iv( i + 1)*1000. Таким образом, если в векторе iv перечислить номера столбцов и значения ненулевых элементов матрицы A (по строкам) в виде: номер столбца, значение элемента матрицы, номер столбца, значение ... и т.д., то обратившись к подпрограмме utmlc_c мы получим требуемое представление исходной информации. Вектор - решение хранится в первых m + n + 1 элементах вектора nr, причем nr (1) - значение линейной формы, nr (2) ÷ nr (m + 1) - невязки в ограничениях, равные b - ax, nr (m + 2) ÷ nr (m + n + 1) - компоненты вектора x. Счет можно закончить по заданному числу итераций или по времени. При этом вектор x может не быть оптимальным, но обязательно будет допустимым. Если ограничения в задаче имеют вид ax ≥ b, b ≥ 0, x ≥ 0, целые, то иногда может помочь замена переменных yj = k - xj, где k ≥ xj для всех j = 1, ..., n. Подставим xj = k - yj в функционал и систему ограничений: найти max (- a, y) при условиях - ay + ak ≥ b или ay ≤ ak - b, где k - вектор - столбец, все элементы которого равны k. n n
∑ yj = nk - ∑ x j
j =1 j =1
n
∑ yj ≤ nk
j =1
Если вектор ak - b ≥ 0, то задача имеет требуемый вид. Если задача поставлена на минимум, переходим к поиску максимума, изменив знаки у вектора коэффициентов линейной формы. Количество итераций не всегда связано с размерами задачи и оценке не поддается. При ierr = 1 и ierr = 2 допустимое решение может оказаться оптимальным. Используются служебные подпрограммы: mlc4b_c, mlc4c_c, mlc4d_c, mlc4o_c, mlc4p_c, mlc4w_c, utmn05_c, utmn06_c. |
Найти максимум x0 = x1 + x2 + x3 при условиях:
- 4x1 + 5x2 + 2x3 ≤ 4
- 2x1 + 5x2 ≤ 5
3x1 - 2x2 + 2x3 ≤ 6
2x1 - 5x2 ≤ 1
x1 + x2 + x3 ≤ 10
x1, x2, x3 ≥ 0, целые
Решение: x0 = 5 , x1 = 3 , x2 = 2 , x3 = 0
int main(void)
{
/* Initialized data */
static int iv[20] = { 1,-4,2,5,3,2,1,-2,2,5,1,3,2,-2,3,2,1,2,2,-5 };
static int it = 20;
static float tmax = 60.f;
static int ns[4] = { 3,2,3,2 };
static int nai[4] = { 4,5,6,1 };
static int naj[3] = { 1,1,1 };
static int m = 4;
static int n = 3;
static int n1 = 4;
static int mn = 10;
static int l = 10;
/* Local variables */
static int ierr;
extern int mlc4r_c(int *, int *, int *, int *, int *, int *, int *,
int *, int *, int *, int *, int *, float *, int *);
extern int utmlc_c(int *, int *, int *);
static int m1, na[10], nb[16] /* was [4][4] */, nr[36];
utmlc_c(iv, &c__20, na);
mlc4r_c(na, ns, nai, naj, &l, nb, nr, &m, &n, &n1, &mn, &it, &tmax,
&ierr);
m1 = m + n + 2;
/* l10: */
printf("\n %5i \n", ierr);
printf("\n %8i %8i %8i %8i %8i \n %8i %8i %8i %8i \n",
nr[0], nr[1], nr[2], nr[3], nr[4], nr[5], nr[6], nr[7], nr[8]);
return 0;
} /* main */
Результаты решения:
ierr = 1
nr(1) ÷ nr(8) : 5 6 1 1 5 3 2 0
таким oбpaзoм, (a, x) = 5, невязки
по строкам матрицы условий равны, соответственно,
(6, 1, 1, 5),
вектор - решение x = (3, 2, 0).