ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовомупроекту по “Системному анализу”
Тема: “Решение задач линейного программированиябольшой размерности”
Выполнил студент гр. Э-282:
Богдановский А. А.
Проверил преподаватель:
Тихненко Е.В.
________________________
Дата:
“___”__________ 1996 г.
СОДЕРЖАНИЕ
TOC o «1-3» f GOTOBUTTON _Toc347013713 PAGEREF _Toc347013713 3
2. Конкретизация задачи GOTOBUTTON _Toc347013714 PAGEREF _Toc347013714 3
3. Математическая модель симплекс-методас мультипликативным представлением обратной матрицы GOTOBUTTON _Toc347013715 PAGEREF _Toc347013715 3
3.1. Модифицированныйсимплекс-метод GOTOBUTTON _Toc347013716 PAGEREF _Toc347013716 4
3.2. Мультипликативная формаобратной матрицы GOTOBUTTON _Toc347013717 PAGEREF _Toc347013717 5
3.3. Преимущества метода GOTOBUTTON _Toc347013718 PAGEREF _Toc347013718 8
4. Алгоритм метода, реализованногов программе GOTOBUTTON _Toc347013719 PAGEREF _Toc347013719 9
5. Текст программы SASIMPL GOTOBUTTON _Toc347013720 PAGEREF _Toc347013720 11
6. Интерфейс пользователя GOTOBUTTON _Toc347013721 PAGEREF _Toc347013721 11
6.1. Работа с программой GOTOBUTTON _Toc347013722 PAGEREF _Toc347013722 12
6.2. Формат файлов, содержащихпостановку задач линейного программирования GOTOBUTTON _Toc347013723 PAGEREF _Toc347013723 13
7. Результаты работы программы GOTOBUTTON _Toc347013724 PAGEREF _Toc347013724 14
СПИСОК ЛИТЕРАТУРЫ GOTOBUTTON _Toc347013725 PAGEREF _Toc347013725 17
Приложение I. Текст программыSASIMPL GOTOBUTTON _Toc347013726 PAGEREF _Toc347013726 18
1.
Реализоватьна произвольной вычислительной технике с помощью любого программного средстваодин из методов решения задач линейногопрограммирования большой размерности.2.
[А. А.1] В соответствии с общей постановкойзадачи, возможностями студента, доступной литературой и другими факторами,студентом была конкретизирована и сформулирована следующая задача:
· “модифицированныйсимплекс-метод с мультипликативным представлением обратной матрицы”;
·
·
· 3.
[А. А.2] Решаемая задача линейного программированияпредставлена в канонической форме и имеет следующий вид:
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. В начале первого цикла нам известны обратнаяматрица EQ Asup(-1;sdo(x)) (единичная матрица), базисное решение xb= EQ Asup(-1;sdo(x))
2. Образуем для каждой небазисной переменнойхарактеристическую разность Dj,используя уравнение:
Dj= cj — EQ isu(i=1;n;pi* Aij) j — pPj,
где p - двойственныепеременные, которые можно найти следующим образом:
p = cx* EQ Asup(-1;sdo(x))
где cx - векторкоэффициентов целевой функции при базисных переменных.
3. Предполагая, что используется стандартноеправило выбора вводимого столбца, находим:
EQ mindba10()j Dj= Ds .
4. Если Ds ³0 — процедура останавливается. Текущее базисное решение является оптимальным.
5. Если Ds £0, вычисляем преобразованный столбец:
EQ o(P;—)s = EQ Asup(-1;sdo(x)) s
6. Пусть
EQ o(P;—)s EQ o(a;-)1s EQ o(a;-)2s EQ o(a;-)ms
Если все EQ o(a;-)is £ 0 — процедура останавливается: оптимумнеограничен.
7. В противном случае находим выводимую избазиса переменную:
EQ f(xb r; o(a;-)r s)= mindba20()o(a;-)rs ³ 0 = q.
8. Строим увеличенную матрицу:
EQ bbc[( Asup(-1;sdo(x)) oac(:;:;:) o(P;—)s) -1;sdo(x:;:;:
и трансформируем ее с ведущим элементом EQ o(a;-)r s
xbi Üxb i — q * EQ o(a;-)is ¹ r,
xbr Üq
и переходим к этапу 2.3.2.
Назовемэлементарной матрицей матрицу, отличающуюся от единичной только одной строкойили столбцом. При мультипликативном представлении матрица EQ Asup(-1;sdo(x)) не дается явно, а представляется в видепроизведения накапливаемых элементарных матриц. Для того, чтобы показать, какэто делается, примем, что EQ Asup(-1;sdo(x с)) — матрица, обратная текущей базисной, ипредположим, что новая обратная вычисляется с помощью ведущей операции,опирающейся на ведущий элемент EQ o(a;-)r s EQ Asup(-1;sdo(x с)) следует произвести следующие операции:
1. Для i=1,...,m, i¹r заменить строку i на
(строкаi) — EQ f(o(a;-)i s; o(a;-)r s) * (строка r) .
2. Заменить строку r на EQ f(1; o(a;-)r s) * (строка r).
Легкодоказать непосредственным перемножением матриц, что эти операции соответствуютумножению EQ Asup(-1;sdo(x с)) слева на элементарную матрицу:
E = EQ bbc[(1 ... oac(h1;h2;: ;:;hm) ... 1) , (1)
где
EQ hi= blc{(aal(—f(o(a;-)i s;o(a;—)r s);i=1;...;m; i¹r;f(1; o(a,—)r s), i=r)) (2)
т. е.
EQ Asup(-1;sdo(x n)) E * EQ Asup(-1;sdo(x с)) ,
где EQ Asup(-1;sdo(x n)) - новая обратнаяматрица.
Еслиначальный базис был единичным и если осуществлены k ведущих операций, то нацикле k обратная матрица EQ Asup(-1;sdo(x k)) дается формулой:
EQ Asup(-1;sdo(x n)) Ek * Ek-1*… * E1,
где каждая из матриц Eiявляется элементарной матрицей типа (1).
Полученноепредставление EQ Asup(-1;sdo(x n)) в виде произведения элементарных матриц называетсямультипликативной формой обратной матрицы.
Важнымсвойством элементарных матриц является то, что они могут сохраняться в памятипутем записи только элементов неединичного столбца и его положения в матрице(практически необходимо запоминать только ненулевые элементы и их положение).Поскольку обратная матрица теперь в явной форме недоступна, все вычисления,требующие ее использования, сводятся к последовательности умножений наэлементарные матрицы. Рассмотрим эти вычисления в том порядке, в котором онипроизводятся в симплекс-методе:
Оценка двойственныхпеременных:
Двойственныепеременные даются формулой:
p = cx* EQ Asup(-1;sdo(x)) (3)
так что, если EQ Asup(-1;sdo(x)) дана вмультипликативной форме, то приходится оценить следующее матричноепроизведение:
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 = EQ isu(i=1;m; ui* hi) ,
то есть вектор uE есть строка. отличающаяся от uтолько одним элементом d,который равен скалярному произведению u на неединичный столбец h. Таким образом, вычисление p призадании обратной матрицы в виде произведения k элементарных матриц требуетвычисления k скалярных произведений.
Вычисление ведущегостолбца EQ o(P;—)s :
Вектор EQ o(P;—)s
EQ o(P;—)s Ek * (… * (E2 * (E1* Ps))...) . (6)
Здесь произведения вычисляются в прямой последовательности:сначала E1 * Ps, затем E2 * (E1 * Ps)и т. д. Каждая операция требует вычисления произведения вида Eu. Если E и uтаковы, как в (4), (5), но uтеперь вектор-столбец, то
Eu = (a1,..., am),
где
EQ ai= blc{(aal(ui+ hi* ur; i=1;...;m; i¹r;;hr* ur; i=r .))
Таким образом, оценкаEu требует m умножений и m сложений.
Изменение обратнойматрицы:
Здесьтребуется только добавление к списку, сохраняемому в памяти, нового вектора h вида(1), (2), элементы которого вычисляются по текущему EQ o(P;—)s .3.3.
Модифицированныйсимплекс-метод, в особенности в мультипликативной форме, обладаетзначительными преимуществами по сравнению со стандартной формой. Это относитсяк точности, скорости и требованиям к памяти. Большая часть этих преимуществопределяется тем фактором, что, как правило, матрицы больших линейных задач (тоесть с n>m>100) являются слабозаполненными, содержат малый процентненулевых элементов. Обычной является плотность 5% или менее. Модифицированнаяформа симплекс-метода в большей степени способна использовать преимущества,вытекающие из этого факта. В этой форме характеристические разности и ведущийвектор вычисляются непосредственно по исходным данным. Поскольку исходнаяматрица слабозаполнена, а перемножение следует производить только тогда, когдаоба сомножителя отличны от нуля, то время вычислений значительно сокращается. Вдополнение к этому использование только исходных данных приводит к тому, чтоуменьшается возможность накопления ошибок округления. Наоборот, стандартныесимплексные таблицы, даже если они первоначально являются слабозаполненными, входе итеративного процесса быстро заполняются ненулевыми элементами. Такимобразом, время вычислений увеличивается,и, поскольку каждая таблица вычисляется из предшествующей, накопление ошибокможет начать играть более серьезную роль.4.
Исходныеданные:
Количество переменных: n
Количество ограничений: m
Вектор коэффициентов целевойфункции: c
Матрица ограничений: A
Правая часть ограничений: b
Предполагается,что задача линейного программирования задана в канонической форме для задачиминимизации.
Алгоритм:
1. Нахождение начального опорного плана:a) b) c) d)
В результате получаем:
·
·
2. Счетчик итераций iteration приравниваем 1:iteration := 1.
3. Расчет двойственных переменных Pi (p) :a) x)и записываем его в массивдвойственных переменных Pi: Pi := Cx;b) Ek) в соответствии с(3), где i изменяется от iteration до 1 (если iteration = 1, то данный пунктпропускается).
4. Поиск ведущего столбца (вводимойпеременной):a) Û Ds, s_min Ûs ) ;b) ³ 0, то алгоритм заканчивает работу и текущиебазисные значения переменных являются оптимальным решением задачи.c)
5. Вычисление ведущего столбца AA (EQ o(P;—)s a) A;b) Ek) на AA в соответствии с(6), где i изменяется от 1 до iteration 1 (если iteration = 1, то данный пунктпропускается).c)
6. Поиск выводимой переменной из базиса:a) b) q Ûth_min, r Ûr_min) будет соответствовать переменной с индексом в базисе r, выводимой избазиса;
7. Добавляем в список элементарных матриц ещеодну:a) iterationв соответствии с (1), (2) и добавляем ее в список элементарных матриц;
8. Делаем замену переменных в базисе:a) NXBasis[r_min] = s_minb)
X[i] = X[i] — th_min *AA[i], i ¹r_min
X[r_min] = th_min .
9. Увеличиваем счетчик итераций на единицу:iteration := iteration + 1.
10. Переходим к пункту 3.5.
Программабыла написана на языке программирования Borland C++ 3.1 с использованиембиблиотеки работы с матрицами MATRIX и библиотеки интерфейса пользователя TSWM.
ПрограммаSASIMPL состоит из 6 модулей:1. главныймодуль программы (интерфейс)2. реализацияметода3. библиотекаработы с матрицами4. обработкаошибок5. библиотекаинтерфейса пользователя6. то же
В приложении I представлены тексты модулей MSIMPLEX.CPP,SA.CPP, MATRIX.CPP и GERROR.CPP.6. [А. А.3] Интерфейспользователя
ПрограммаSASIMPL имеет примитивный пользовательский интерфейс, который позволяетзагружать данные о задачах из внешних файлов, решать их и просматриватьрезультаты. Кроме того, программа предоставляет скромную справочную систему дляудобства работы.6.1.
Главный экран программы, который появляется при ее запускеизображен на рисунке 1:
Рисунок SEQ Рисунок * ARABIC
Здесь программа предоставляет пользователю выбратьнеобходимый режим работы:
1. «Решить задачу линейного программирования»
в этом разделе программы можно задать данные по задаче линейного программирования и решить ее; данные нужно будет загрузить из внешнего файла; формат файлов, содержащих постановку задачи линейного программирования, можно узнать, если выбратьрежим «Узнать о программе» главного меню данной программы; после решения задачи программа выведет на экран результаты вычисления, кроме того, эти результаты будут сохранены в текущей директории в файле SASIMPL.RES.
2. «Почитать краткую теорию метода»
в этом разделе описывается краткая теориямодифицированного симплекс-метода смультипликативным представлением обратной матрицы;
3. «Узнать о программе»
здесь можно узнать о программе (назначение,автор, дата, ...) и, кроме того, формат файлов с постановками задач линейного программирования.
4. «Выйти из программы»
выход из данной программы.
Еслипользователь выбрал первый пункт меню, на экране появится изображение похожеена рисунок 2:
Здесь пользователю предлагается выбрать файл, содержащийданные о задаче, которую ему необходимо решить (формат таких файлов см. в REF _Ref347010598 n
После того,как пользователь укажет программе необходимый файл, программа произведетвычисления по заданному алгоритму метода решения задач линейногопрограммирования и на экране появятся результаты вычислений в виде типа рис. 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). Кроме того, в ограниченияхдолжны стоять только (!) равенства, то есть должны уже быть введены свободные и искусственные переменные.
Если в целевой функции или в ограничениях заданы коэффициенты не для всех переменных, то этикоэффициенты принимаются за нулевые, нов целях проверки, в этом случае, программа выведет предупреждающее сообщение обэтом.
При вводе искусственных переменных используйтебольшие коэффициенты в целевой функции, чтобы они были на два-три порядка больше, чем для обычных переменных. 7.
В качествеконтрольных примеров бралось множество примеров из задачника /2/.
Рассмотримследующий пример:
Fmax = 3x1+ x2
x1 + 2x2 ³ 5,
2x1 + 4x2 £16,
3x1 + x2 ³6,
x1 + 3x2 £9,
x1, x2 ³0.
Так как программе SASIMPL требуется постановка задачи вканонической форме, то приведем ее к канонической форме:
Fmax = 3x1 + x2+ 0x3 + Mx4 + 0x5 + 0x6 + Mx7+ 0x8
x1 + 2x2 — x3 + x4 = 5,
2x1 + 4x2 + x5 =16,
3x1 + x2 — x6 + x7 = 6,
x1 + 3x2 +x8 = 9,
x1, x2 ³0.
Таким образом, мыввели две свободные переменные x3, x6, и двеискусственные — x4 и x7 .
Составимвходной файл для программы, содержащий данную задачу:
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
Как можноувидеть, функция Fmax преобразована к Fmin путемумножения на -1. В качестве больших коэффициентов M взято число 1000, котороево много раз превосходит соседние коэффициенты в целевой функции.
Врезультате вычислений программы SASIMPL при подаче на вход указанного файла,получили следующие результаты:
Входные данные:
Количество переменных n = 9
Количество ограничений m = 5
Вектор коэффициентов целевой функции C:
-1.000 -1.000 -2.000 -1.000 0.000 0.000 0.000 0.000 0.000
Матрица коэффициентов в ограничениях A:
1.000 2.000 1.000 -1.000 1.000 0.000 0.000 0.000 0.000
2.000 1.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000
1.000 2.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000
0.000 0.000 1.000 1.000 0.000 0.000 0.000 1.000 0.000
0.000 0.000 -2.000 3.000 0.000 0.000 0.000 0.000 1.000
Вектор правой части ограничений B:
10.000 4.000 6.000 5.000 6.000
********************************************************
Итерация N0
Значения базисных переменных:
X5 = 10
X6 = 4
X7 = 6
X8 = 5
X9 = 6
Значение целевой функции: 0.000
Итерация N1
Значения базисных переменных:
X5 = 5
X6 = 4
X7 = 6
X3 = 5
X9 = 16
Значение целевой функции: -10.000
Итерация N2
Значения базисных переменных:
X5 = 3
X1 = 2
X7 = 4
X3 = 5
X9 = 16
Значение целевой функции: -12.000
Итерация N3
Значения базисных переменных:
X2 = 2
X1 = 1
X7 = 1
X3 = 5
X9 = 16
Значение целевой функции: -13.000
Данное решение является оптимальным!
TC " СПИСОКЛИТЕРАТУРЫ " 1. 2. 3. 4. 5. 6. 7.
TC "
PAGE #"'Стр: '#'
'" [А. А.1]Тихненко считает, что обращение к себе как к третьему лицу — плохой тон...
PAGE #"'Стр: '#'
'" [А. А.2]Оказывается каноническая форма постановки линейной задачи не обуславливаетналичие начального опорного плана (единичного базиса) — это в принципе самаяглавная ошибка курсовика (то есть у меня требовалась постановка задачи нетолько в каноническом виде, но и чтобы присутствовал единичный базис...)
PAGE #"'Стр: '#'
'" [А. А.3]Тихненко не понравилось в интерфейсе слишком!!! много разных цветов (я это тожеосознал — цветов в программе, как на попугае...). Ещ