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

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

Содержание реферата

1. Общая постановка задачи
2. Конкретизация задачи
3. Математическая модель симплекс-метода с мультипликативным представлением обратной матрицы
   3.1. Модифицированный симплекс-метод
   3.2. Мультипликативная форма обратной матрицы
   3.3. Преимущества метода
4. Алгоритм метода, реализованного в программе
5. Текст программы SASIMPL
6. Интерфейс пользователя
   6.1. Работа с программой
   6.2. Формат файлов, содержащих постановку задач линейного программирования

1. Общая постановка задачи

Реализовать на произвольной вычислительной технике с помощью любого программного средства один из методов решения задач линейного программирования большой размерности.

2. Конкретизация задачи

В соответствии с общей постановкой задачи, возможностями студента, доступной литературой и другими факторами, студентом была конкретизирована и сформулирована следующая задача:

для решения задач линейного программирования большой размерности принять “модифицированный симплекс-метод с мультипликативным представлением обратной матрицы”;

разработать алгоритм для этого метода;

описать этот алгоритм на языке программирования Borland C++ 3.1;

написать программу-оболочку на языке Borland C++ 3.1, реализующую примитивный пользовательский интерфейс.

3. Математическая модель симплекс-метода с мультипликативным представлением обратной матрицы

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

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 - ограничений.

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

3.1. Модифицированный симплекс-метод

В  литературе  этот  метод встречается также под названием метода обратной матрицы.

При  решении задач линейного программирования, в которых n (количество  переменных)  существенно  больше  m (количество ограничений),  модифицированный  симплекс-метод  требует  по сравнению   с   другими   значительно   меньшего  количества вычислительных операций и объема памяти ЭВМ.

В   модифицированном  симплекс-методе  реализуется  та  же основная  идея, что и в обычном симплекс-методе, но здесь на каждой  итерации  пересчитывается  не  вся матрица A-1, обратная матрице  ограничений A, а лишь та часть, которая относится к текущему базису Ax.

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

1.         В начале первого цикла нам известны обратная матрица  (единичная матрица), базисное решение xb = b.

2.         Образуем для каждой небазисной переменной характеристическую разность Dj, используя уравнение:

Dj = cj — = cj — pPj ,

где      p         -           двойственные переменные, которые можно найти следующим образом:

p = cx * ,

где      cx        -           вектор коэффициентов целевой функции при базисных переменных.

3.         Предполагая, что используется стандартное правило выбора вводимого столбца, находим:

4.         Если Ds ³ 0 - процедура останавливается. Текущее базисное решение является оптимальным.

5.         Если Ds £ 0, вычисляем преобразованный столбец: = Ps

6.         Пусть = (, , ..., ) .

Если все £ 0 - процедура останавливается: оптимум неограничен.

7.         В противном случае находим выводимую из базиса переменную: = q .

8.         Строим увеличенную матрицу:

\s\do(x-1,\s\do(x:,:,:

и трансформируем ее с ведущим элементом . Первые m столбцов результат дают матрицу, обратную новому базису. Преобразуем базисное решение:

xb i Ü xb i — q * , i ¹ r,

xb r Ü q

и переходим к этапу 2.

3.2. Мультипликативная форма обратной матрицы

Назовем элементарной матрицей матрицу, отличающуюся от единичной только одной строкой или столбцом. При мультипликативном представлении матрица  не дается явно, а представляется в виде произведения накапливаемых элементарных матриц. Для того, чтобы показать, как это делается, примем, что  - матрица, обратная текущей базисной, и предположим, что новая обратная вычисляется с помощью ведущей операции, опирающейся на ведущий элемент . Тогда над   следует произвести следующие операции:

1.         Для i=1,...,m, i¹r заменить строку i на

(строка i) —  * (строка r) .

2.         Заменить строку r на  * (строка r).

Легко доказать непосредственным перемножением матриц, что эти операции соответствуют умножению  слева на элементарную матрицу:

E = (2,: ,:,(m ,         (1)

Если начальный базис был единичным и если осуществлены k ведущих операций, то на цикле k обратная матрица  дается формулой:

= Ek * Ek-1 * ... * E1 ,

где каждая из матриц Ei является элементарной матрицей типа (1).

Полученное представление  в виде произведения элементарных матриц называется мультипликативной формой обратной матрицы.

Важным свойством элементарных матриц является то, что они могут сохраняться в памяти путем записи только элементов неединичного столбца и его положения в матрице (практически необходимо запоминать только ненулевые элементы и их положение). Поскольку обратная матрица теперь в явной форме недоступна, все вычисления, требующие ее использования, сводятся к последовательности умножений на элементарные матрицы. Рассмотрим эти вычисления в том порядке, в котором они производятся в симплекс-методе:

Оценка двойственных переменных:

Двойственные переменные даются формулой:

p = cx * ,          (3)

так что, если  дана в мультипликативной форме, то приходится оценить следующее матричное произведение:

p = (...((cx * Ek) * Ek-1) * ...) * E1 .

Операции производятся в том же порядке, как указано скобками, то есть сначала вычисляется строка cx * Ek . Затем (cx * Ek) * Ek-1 и т. д. Каждая из этих операций требует умножения элементарной матрицы слева на вектор-строку. Пусть

E = [u1, u2, ..., ur-1, h, ur+1, ..., um ],         (4)

где ui есть i-ый единичный вектор, и пусть

u = (u1, ..., um)         (5)

- произвольный вектор-строка. Тогда

uE = (u1, ..., ur-1, d, ur+1, ..., um),

где

d = u * h =  ,

то есть вектор uE есть строка. отличающаяся от u только одним элементом d, который равен скалярному произведению u на неединичный столбец h. Таким образом,  вычисление p при задании обратной матрицы в виде произведения k элементарных матриц требует вычисления k скалярных произведений.

Вычисление ведущего столбца :

Вектор дается формулой

= Ek * (... * (E2 * (E1 * Ps))...) .        (6)

Здесь произведения вычисляются в прямой последовательности: сначала E1 * Ps , затем E2 * (E1 * Ps) и т. д. Каждая операция требует вычисления произведения вида Eu. Если E и u таковы, как в (4), (5), но u теперь вектор-столбец, то

Eu = (a1, ..., am),

где

Таким образом,  оценка Eu требует m умножений и m сложений.

Изменение обратной матрицы:

Здесь требуется только добавление к списку, сохраняемому в памяти, нового вектора h вида (1), (2), элементы которого вычисляются по текущему .

3.3. Преимущества метода

Модифицированный симплекс-метод, в особенности в мультипликативной форме, обладает значительными преимуществами по сравнению со стандартной формой. Это относится к точности, скорости и требованиям к памяти. Большая часть этих преимуществ определяется тем фактором, что, как правило, матрицы больших линейных задач (то есть с n>m>100) являются слабозаполненными, содержат малый процент ненулевых элементов. Обычной является плотность 5% или менее. Модифицированная форма симплекс-метода в большей степени способна использовать преимущества, вытекающие из этого факта. В этой форме характеристические разности и ведущий вектор вычисляются непосредственно по исходным данным. Поскольку исходная матрица слабозаполнена, а перемножение следует производить только тогда, когда оба сомножителя отличны от нуля, то время вычислений значительно сокращается. В дополнение к этому использование только исходных данных приводит к тому, что уменьшается возможность накопления ошибок округления. Наоборот, стандартные симплексные таблицы, даже если они первоначально являются слабозаполненными, в ходе итеративного процесса быстро заполняются ненулевыми элементами. Таким образом,  время вычислений увеличивается, и, поскольку каждая таблица вычисляется из предшествующей, накопление ошибок может начать играть более серьезную роль.

4. Алгоритм метода, реализованного в программе

Исходные данные:

Количество переменных:  n

Количество ограничений:  m

Вектор коэффициентов целевой функции:      c

Матрица ограничений:       A

Правая часть ограничений:         b

Предполагается, что задача линейного программирования задана в канонической форме для задачи минимизации.

Алгоритм:

1.         Нахождение начального опорного плана:

перебираются все строки ограничений и ищется переменная с коэффициентом 1;

проверяется, чтобы в остальных ограничениях у этой переменной был коэффициент 0;

если условие выполняется, то эта переменная заносится в базис;

так ищем переменные до тех пор, пока не найдем m базисных переменных.

В результате получаем:

массив NXBasis[m], в котором хранятся индексы базисных переменных;

массив X[m], с самими значениями базисных переменных, которые на начальном этапе должны равняться правой части ограничений b;

2.         Счетчик итераций iteration приравниваем 1: iteration := 1.

3.         Расчет двойственных переменных Pi (p) :

создаем массив коэффициентов целевой функции при базисных переменных Cx (cx) и записываем его в массив двойственных переменных Pi: Pi := Cx;

организуем последовательное умножение Pi на E[i] (Ek) в соответствии с (3), где i изменяется от iteration до 1 (если iteration = 1, то данный пункт пропускается).

4.         Поиск ведущего столбца (вводимой переменной):

расчет характеристических оценок всех небазисных переменных и поиск минимальной среди них c_min (c_min Û Ds, s_min Û s ) ;

если c_min ³ 0, то алгоритм заканчивает работу и текущие базисные значения переменных являются оптимальным решением задачи.

иначе, определяем, что в базис будем вводить переменную с индексом s_min.

5.         Вычисление ведущего столбца AA ():

Заносим в массив AA[m] столбец s_min из матрицы A;

организуем последовательное умножение E[i] (Ek) на AA в соответствии с (6), где i изменяется от 1 до iteration 1 (если iteration = 1, то данный пункт пропускается).

проверяем, если все элементы AA положительны или равны нулю, то текущее решение является оптимальным, но не единственным, и алгоритм заканчивает работу.

6.         Поиск выводимой переменной из базиса: ищем минимальное значение th = X[i]/AA[i], где i от 1 до m найденное th_min (q Û th_min, r Û r_min) будет соответствовать переменной с индексом в базисе r, выводимой из базиса;

7.         Добавляем в список элементарных матриц еще одну: вычисляем новую элементарную матрицу Eiteration в соответствии с (1), (2) и добавляем ее в список элементарных матриц;

8.         Делаем замену переменных в базисе: присваиваем NXBasis[r_min] = s_min

перевычисляем значения базисных переменных:

X[i] = X[i] - th_min * AA[i], i ¹ r_min

X[r_min] = th_min .

9.         Увеличиваем счетчик итераций на единицу: iteration := iteration + 1.

10.      Переходим к пункту 3.

5. Текст программы SASIMPL

Программа была написана на языке программирования Borland C++ 3.1 с использованием библиотеки работы с матрицами MATRIX и библиотеки интерфейса пользователя TSWM.

Программа SASIMPL состоит из 6 модулей:

SA.CPP         главный модуль программы (интерфейс)

MSIMPLEX.CPP     реализация метода

MATRIX.CPP           библиотека работы с матрицами

GERROR.CPP         обработка ошибок

TSWM.LIB     библиотека интерфейса пользователя

GETFILE.LIB то же

В приложении I представлены тексты модулей MSIMPLEX.CPP, SA.CPP, MATRIX.CPP и GERROR.CPP.

6. Интерфейс пользователя

Программа SASIMPL имеет примитивный пользовательский интерфейс, который позволяет загружать данные о задачах из внешних файлов, решать их и просматривать результаты. Кроме того, программа предоставляет скромную справочную систему для удобства работы.

6.1. Работа с программой

Главный экран программы, который появляется при ее запуске изображен на рисунке 1:

Рисунок 1

Здесь программа предоставляет пользователю выбрать необходимый режим работы:

1. "Решить задачу линейного программирования"

в  этом  разделе  программы можно  задать данные по задаче   линейного  программирования  и  решить  ее; данные нужно  будет  загрузить  из  внешнего  файла; формат файлов, содержащих  постановку  задачи  линейного  программирования, можно узнать, если выбрать режим "Узнать о программе" главного   меню   данной  программы;  после  решения  задачи программа  выведет  на  экран  результаты  вычисления, кроме того,   эти  результаты  будут сохранены  в  текущей  директории в файле SASIMPL.RES.

2. "Почитать краткую теорию метода"

в  этом  разделе  описывается  краткая  теория модифицированного      симплекс-метода с мультипликативным представлением  обратной  матрицы;

3. "Узнать о программе"

здесь можно узнать о программе (назначение, автор, дата, ...)  и,  кроме того,  формат файлов с постановками задач линейного программирования.

4. "Выйти из программы"

выход из данной программы.

Если пользователь выбрал первый пункт меню, на экране появится изображение похожее на рисунок 2:

Здесь пользователю предлагается выбрать файл, содержащий данные о задаче, которую ему необходимо решить (формат таких файлов см. в 6.2 ).

После того, как пользователь укажет программе необходимый файл, программа произведет вычисления по заданному алгоритму метода решения задач линейного программирования и на экране появятся результаты вычислений в виде типа рис. 3:

6.2. Формат файлов, содержащих постановку задач линейного программирования

Программа SASIMPL понимает только определенные файлы с постановкой задач. Рассмотрим один из них:

; *** Начало файла с данными о задаче ***

; Пример  из  Ю.  П. Зайченко, С. А. Шумилова

; "Исследование операций" N1.46

n = 8                        ; количество переменных

m = 4                        ; количество ограничений

F = -3 -1 0 1000 0 0 1000    ; целевая функция минимизации

LIMITS:                      ; задание ограничений

1 2 -1 1 = 5

2 4 0 0 1 = 16

3 1 0 0 0 -1 1 = 6

1 3 0 0 0 0 0 1 = 9

;*** Конец файла ***

Символ ';' является символом-коментария.

Создавая  файлы  такого  формата, обратите внимание на то, что  целевая  функция  F  должна  задаваться для минимизации (преобразование  максимизирующей  к  минимизирующей  функции производится  путем умножения ее коэффициентов на -1). Кроме того,  в ограничениях должны стоять только (!) равенства, то есть  должны  уже  быть  введены  свободные  и искусственные переменные.

Если   в   целевой   функции  или  в  ограничениях  заданы коэффициенты  не  для  всех  переменных, то эти коэффициенты принимаются  за нулевые, но в целях проверки, в этом случае, программа выведет предупреждающее сообщение об этом.

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