Решение задачи линейного программирования модифицированным симплекс

Интеллектуальная среда дистанционного обучения и дизайна
http: econom.misis.ru, fdisto.misis.ru; e-mail: vaosadchy@yandex.ru

Решение задачи линейного программирования модифицированным симплекс-методом

Математическое описание

Решается задача линейного программирования:

min (c, x) ( или max (c, x) ) ,

A x = b ,

x ≥ 0 ,

где A - матрица размерности m на n, x

и c - векторы длины n, b - вектоp длины m.

Используется модифицированный симплекс - метод. Исходная информация задается в виде расширенной матрицы

| a₁₁ a₁₂ . . . a_1n

| . . . . . . . . . . . . . . . . . . . . . .

A1 = | a_m1 a_m2 . . . a_mn

| c₁ c₂ . . . c_n

| a_m+2,1 a_m+2,2 . . . a_m+2,N

где a_{i j} ( i = 1, ... , m ; j = 1, ... , n ) - элементы матрицы A ,

a_{m+2, j} = - ( a_{1 j} + a_{2 j} + ... + a_{m j} ) для j = 1, ... , n

Вектоp b дополняется двумя компонентами

b_{m + 1} = 0,

b_{m + 2} = - (b₁ + ... + b_m).

Точность вычислений характеризуется величиной невязки

r = b_m+2 - Σ a_{m+2, j} x_j

С.Гасс, Линейное программирование, Физматгиз, 1961.

Использование

ML01R (A, M1, U, N, X1, NB, P, EPS, XK)

Параметры

A -	вещественный двумерный массив размерности m + 2 на n, содержащий элементы расширенной матрицы A1;
M -	число стpок матрицы A1 (тип: целый);
U -	рабочий массив размерности M на M (тип: вещественный);
N -	число столбцов матрицы A1 (тип: целый);
X -	вещественный вектоp длины M, при этом на входе X (I) = b_I, I = 1, ..., M, на выходе для I = 1, ... , M - 2 ; X (I) - ненулевые компоненты решения, X (M - 1) - минимальное (или максимальное) значение линейной формы, X (M) - величина невязки r;
NB -	вектоp длины M, содержащий номеpа ненулевых компонент решения т.е. x_{NB (I)} = X (I) для I = 1, ... , M - 2 (тип: целый);
P -	целая переменная, при обращении к подпрограмме задается равной 1, если требуется найти максимум линейной формы, и не равной 1, в противном случае; на выходе:

P = 1 -	если найдено решение,
P = 2 -	если задача несовместна,
P = 3 -	если значение линейной формы неограничено;

EPS -	заданная абсолютная погрешность вычислений (тип: вещественный);
XK -	вещественный рабочий вектоp длины M.

Задача должна быть приведена к виду, в котоpом компоненты вектоpа b неотрицательны.

Подпрограмма рекомендуется для использования, если матрица A содержит много ненулевых элементов.