ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту по “Системному анализу”
Тема: “Решение задач линейного программирования большой размерности”
Выполнил студент гр. Э-282:
Богдановский А. А.
Проверил преподаватель:
Тихненко Е. В.
________________________
Дата:
“___” __________ 1996 г.
СОДЕРЖАНИЕ
1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ
2. КОНКРЕТИЗАЦИЯ ЗАДАЧИ
3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ СИМПЛЕКС-МЕТОДА С МУЛЬТИПЛИКАТИВНЫМ ПРЕДСТАВЛЕНИЕМ ОБРАТНОЙ МАТРИЦЫ
3.1. Модифицированный симплекс-метод
3.2. Мультипликативная форма обратной матрицы
3.3. Преимущества метода
4. АЛГОРИТМ МЕТОДА, РЕАЛИЗОВАННОГО В ПРОГРАММЕ
5. ТЕКСТ ПРОГРАММЫ SASIMPL
6. ИНТЕРФЕЙС ПОЛЬЗОВАТЕЛЯ
6.1. Работа с программой
6.2. Формат файлов, содержащих постановку задач линейного программирования
7. РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ I. ТЕКСТ ПРОГРАММЫ SASIMPL
Общая постановка задачи
Реализовать на произвольной вычислительной технике с помощью любого программного средства один из методов решения задач линейного программирования большой размерности.
Конкретизация задачи
В соответствии с общей постановкой задачи, возможностями студента, доступной литературой и другими факторами, студентом была конкретизирована и сформулирована следующая задача:
для решения задач линейного программирования большой размерности принять “модифицированный симплекс-метод с мультипликативным представлением обратной матрицы”;
разработать алгоритм для этого метода;
описать этот алгоритм на языке программирования Borland C++ 3.1;
написать программу-оболочку на языке Borland C++ 3.1, реализующую примитивный пользовательский интерфейс.
Математическая модель симплекс-метода с мультипликативным представлением обратной матрицы
Решаемая задача линейного программирования представлена в канонической форме и имеет следующий вид:
min F = cx, при Ax = b, x ( 0 ,
где c - вектор коэффициентов целевой функции (c1,c2,...,cn);
A - матрица ограничений размера m(n ранга m, может быть представлена также как вектора [P1, P2, ..., Pn];
b - m-вектор правой части ограничений (b1,b2,...,bm).
Таким образом, поставленная задача имеет n - переменных и m - ограничений.
До рассмотрения мультипликативной формы кратко опишем этапы модифицированного симплекс-метода с хранением обратной матрицы в явной форме.
Модифицированный симплекс-метод
В литературе этот метод встречается также под названием метода обратной матрицы.
При решении задач линейного программирования, в которых n (количество переменных) существенно больше m (количество ограничений), модифицированный симплекс-метод требует по сравнению с другими значительно меньшего количества вычислительных операций и объема памяти ЭВМ.
В модифицированном симплекс-методе реализуется та же основная идея, что и в обычном симплекс-методе, но здесь на каждой итерации пересчитывается не вся матрица A-1, обратная матрице ограничений A, а лишь та часть, которая относится к текущему базису Ax.
Рассмотрим поэтапно шаги решения задачи линейного программирования модифицированным симплекс-методом:
1. В начале первого цикла нам известны обратная матрица (единичная матрица), базисное решение xb = b.
2. Образуем для каждой небазисной переменной характеристическую разность (j, используя уравнение:
(j = cj — = cj — (Pj ,
где ( - двойственные переменные, которые можно найти следующим образом:
( = cx * ,
где cx - вектор коэффициентов целевой функции при базисных переменных.
3. Предполагая, что используется стандартное правило выбора вводимого столбца, находим:
.
4. Если (s ( 0 - процедура останавливается. Текущее базисное решение является оптимальным.
5. Если (s ( 0, вычисляем преобразованный столбец:
= Ps
6. Пусть
= (, , ..., ) .
Если все ( 0 - процедура останавливается: оптимум неограничен.
7. В противном случае находим выводимую из базиса переменную:
= ( .
8. Строим увеличенную матрицу:

и трансформируем ее с ведущим элементом . Первые m столбцов результат дают матрицу, обратную новому базису. Преобразуем базисное решение:
xb i ( xb i — ( * , i ( r,
xb r ( (
и переходим к этапу 2.
Мультипликативная форма обратной матрицы
Назовем элементарной матрицей матрицу, отличающуюся от единичной только одной строкой или столбцом. При мультипликативном представлении матрица не дается явно, а представляется в виде произведения накапливаемых элементарных матриц. Для того, чтобы показать, как это делается, примем, что - матрица, обратная текущей базисной, и предположим, что новая обратная вычисляется с помощью ведущей операции, опирающейся на ведущий элемент . Тогда над следует произвести следующие операции:
1. Для i=1,...,m, i(r заменить строку i на
(строка i) — * (строка r) .
2. Заменить строку r на * (строка r).
Легко доказать непосредственным перемножением матриц, что эти операции соответствуют умножению слева на элементарную матрицу:
E = , (1)
где
(2)
т. е.
= E * ,
где - новая обратная матрица.
Если начальный базис был единичным и если осуществлены k ведущих операций, то на цикле k обратная матрица дается формулой:
= Ek * Ek-1 * ... * E1 ,
где каждая из матриц Ei является элементарной матрицей типа (1).
Полученное представление в виде произведения элементарных матриц называется мультипликативной формой обратной матрицы.
Важным свойством элементарных матриц является то, что они могут сохраняться в памяти путем записи только элементов неединичного столбца и его положения в матрице (практически необходимо запоминать только ненулевые элементы и их положение). Поскольку обратная матрица теперь в явной форме недоступна, все вычисления, требующие ее использования, сводятся к последовательности умножений на элементарные матрицы. Рассмотрим эти вычисления в том порядке, в котором они производятся в симплекс-методе:
Оценка двойственных переменных:
Двойственные переменные даются формулой:
( = cx * , (3)
так что, если дана в мультипликативной форме, то приходится оценить следующее матричное произведение:
( = (...((cx * Ek) * Ek-1) * ...) * E1 .
Операции производятся в том же порядке, как указано скобками, то есть сначала вычисляется строка cx * Ek . Затем (cx * Ek) * Ek-1 и т. д. Каждая из этих операций требует умножения элементарной матрицы слева на вектор-строку. Пусть
E = [u1, u2, ..., ur-1, (, ur+1, ..., um ], (4)
где ui есть i-ый единичный вектор, и пусть
( = ((1, ..., (m) (5)
- произвольный вектор-строка. Тогда
(E = ((1, ..., (r-1, (, (r+1, ..., (m),
где
( = ( * ( = ,
то есть вектор (E есть строка. отличающаяся от ( только одним элементом (, который равен скалярному произведению ( на неединичный столбец (. Таким образом, вычисление ( при задании обратной матрицы в виде произведения k элементарных матриц требует вычисления k скалярных произведений.
Вычисление ведущего столбца :
Вектор дается формулой
= Ek * (... * (E2 * (E1 * Ps))...) . (6)
Здесь произведения вычисляются в прямой последовательности: сначала E1 * Ps , затем E2 * (E1 * Ps) и т. д. Каждая операция требует вычисления произведения вида E(. Если E и ( таковы, как в (4), (5), но ( теперь вектор-столбец, то
E( = ((1, ..., (m),
где

Таким образом, оценка E