|
Текст подпрограммы и версий ( Фортран ) ml08r.zip |
Тексты тестовых примеров ( Фортран ) tml08r.zip |
|
Текст подпрограммы и версий ( Си ) ml08r_c.zip |
Тексты тестовых примеров ( Си ) tml08r_c.zip |
|
Текст подпрограммы и версий ( Паскаль ) ml08r_p.zip |
Тексты тестовых примеров ( Паскаль ) tml08r_p.zip |
Решение задачи линейного программирования с двухсторонними ограничениями на переменные симплекс - методом с использованием метода отражений. Матрица условий хранится компактно.
Решается задача линейного программирования:
min (c, x) ( или max (c, x) )
A x = b ,
0 ≤ x ≤ α ,
где A - матрица размерности m на n, x, c и α - векторы длины n, b - вектоp длины m.
Hа каждой итерации симплекс - метода базисная матрица B представляется в виде произведения матриц отражения и правой треугольной матрицы.
Ненулевые элементы матрицы условий A задаются в виде одномерного массива, каждый элемент которого содержит очередной (по столбцам) ненулевой элемент ai j матрицы A, индексы i в том же порядке задаются в целочисленном массиве NS.
Вектоp T длины n содержит коэффициенты линейной формы, а таблица ненулевых элементов матрицы A по столбцам задается в целом массиве NT, т.е. NT(J) содержит число ненулевых элементов в J - ом столбце матрицы A.
Введен вспомогательный вектоp SUM длины n с компонентами SUМ j = - (a1 j +... + am j), где ai j - элементы матрицы А. Вектоp b дополняется компонентой bm + 1 = 0.
Компоненты вектоpа α верхних ограничений на переменные задаются в одномерном массиве ALFA. Номера компонент вектоpа α, отличных от + ∞, задаются вектоpом NALFA.
Точность вычислений характеризуется величиной невязки r = ( - b1 - ... - bm) - (SUM, x).
Дж.Данциг, Линейное программирование. Его применения и обобщения. Изд - во "Прогресс", M., 1966.
В.В.Воеводин, Вычислительные основы линейной алгебры. Изд - во "Наука", M., 1977.
SUBROUTINE ML08R (A, NS, DA, B, M, T, NT, N, SUM, X, P, EPS,
XK, Z, ALFA, KV, NALFA, NX)
Параметры
| A - | вещественный вектоp длины DA, содержащий ненулевые элементы матрицы условий; |
| NS - | целый вектоp, в котором перечислены номера строк ненулевых элементов матрицы A; |
| DA - | число ненулевых элементов в матрице условий (тип: целый); |
| B - | вещественный рабочий массив размерности M на M, где M = m + 1; |
| M - | число стpок в расширенной матрице, pавное m + 1 (тип: целый); |
| T - | вещественный вектоp длины n, содержащий коэффициенты линейной формы; |
| NT - | целый вектоp длины N, содержащий количества ненулевых элементов матрицы по столбцам; |
| N - | число столбцов матрицы условий (тип: целый); |
| SUM - | вещественный вектоp длины n, содержащий сумму элементов матрицы по столбцам с обратным знаком; |
| X - | вещественный вектоp длины M; на входе X (I) = bI, I = 1,..., M; на выходе X (I) - ненулевые компоненты решения для I = 1, 2,..., M - 1, X (M) - минимальное (максимальное) значение линейной формы; |
| P - | целая переменная; при обращении к подпрограмме задается равной 1, если требуется найти максимум линейной формы, и не равной 1 в противном случае; на выходе: |
| P= 1 - | если найдено решение, |
| P= 2 - | если задача несовместна, |
| P= 3 - | если значение линейной формы неограничено, |
| P= 4 - | если базисная матрица плохо обусловлена; |
| EPS - | заданная абсолютная погрешность вычислений (тип: вещественный); |
| XK - | вещественный рабочий вектоp длины M; |
| Z - | вещественный рабочий вектоp длины M; |
| ALFA - | вещественный вектоp длины KV, содержащий отличные от + ∞ компоненты вектоpа верхних ограничений α; |
| KV - | длина вектоpа ALFA, равная числу отличных от + ∞ компонент вектоpа α (тип: целый). |
| NALFA - | целый двухбайтовый вектоp длины KV, содержащий номера компонент вектоpа верхних ограничений α; отличных от + ∞; |
| NX - | целый двухбайтовый вектоp длины M, содержащий на выходе из подпрограммы номера ненулевых компонент решения. |
Версии: нет
Вызываемые подпрограммы: нет
Замечания по использованию
|
Задача должна быть приведена к виду, в котоpом компоненты вектоpа b неотрицательны. На выходе из подпрограммы в массиве NX (I = 1, 2,..., M - 1) стоит номеp J (I) компоненты решения, для которой 0 < xJ (I) = X (I) < αJ (I). Если при выходе из подпрограммы элемент NALFA (J) массива NALFA содержит число (k + 1600), то в оптимальном плане xk = αk. Остальные компоненты решения равны нулю. Вектоp α не должен содержать нулевых компонент, и хотя бы одна его компонента должна быть отлична от + ∞. Используются служебные подпрограммы: ML0801, ML0802, ML0803, ML0804, ML0805, ML0806, ML0807, ML0808, ML0809, ML0810, ML0811, ML0812, ML0813, ML0814, ML0815, ML0816, ML0817, ML0818, ML0819, ML0820, ML0821, ML0822, MLU33, MLU34. Программа рекомендуется для решения задач, требующих высокую точность вычислений.Значение P = 4 на выходе из подпрограммы чаще всего означает, что следует увеличить значение EPS, т.е. снизить требуемую точность. |
REAL A(10), B(4, 4), T(4), SUM(4), X(4), XK(4), Z(4), ALFA(2), EPS
INTEGER*2 NX(4), NALFA(2), NS(10), NT(4)
INTEGER M, N, KV, P, DA
DATA A /1., 2., 1., 2., 1., 2., 3., 5., 1., 1./
DATA NS /1, 2, 3, 1, 2, 3, 1, 2, 3, 3/
DATA SUM /-4., -5., -9., -1./, X /15., 20., 10., 0./
DATA T /1., 2., 3., -1./
DATA ALFA /2., 3./
DATA NT /3, 3, 3, 1/
DATA NALFA /1, 3/
DATA KV /2/, P/1/, M/4/, N/4/, EPS/0.01/, DA/10/
CALL ML08R (A, NS, DA, B, M, T, NT, N, SUM, X, P, EPS, XK, Z,
* ALFA, KV, NALFA, NX)
Результаты:
X = (2.43, 2.71, 0.43, 14.57)
NX = (2, 3, 4)
NALFA = (163852, 3)
Таким образом:
x = (2., 2.43, 2.71, 0.43)
(c, x) = 14.57