ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по “Системному анализу”

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

Выполнил студент гр. Э-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          -           вектор коэффициентов целевой функции (c₁,c₂,...,c_n);

            A         -           матрица ограничений размера m´n ранга m, может быть представлена также как вектора [P₁, P₂, ..., P_n];

            b          -           m-вектор правой части ограничений (b₁,b₂,...,b_m).         

            Таким образом, поставленная задача имеет n - переменных и m - ограничений.

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

3.1.           

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

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

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

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

1.    В начале первого цикла нам известны обратная матрица  EQ Asup(-1;sdo(x))  (единичная матрица), базисное решение x_b =  EQ Asup(-1;sdo(x))

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

D_j = c_j —  EQ isu(i=1;n; p_{i *} A_ij) _j — pP_j ,

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

p = c_{x *}  EQ Asup(-1;sdo(x))

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

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

 EQ mindba10()j   D_j = D_s  .

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

5.    Если D_s £ 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(x_{b 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}

x_{b i} Ü x_{b i} — q _*  EQ o(a;-)_is ¹ r,

x_{b r} Ü 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(h₁;h_2;: ;:;h_m) ... 1)  ,                                                              (1)

где

 EQ h_i = 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)) E_{k *} E_{k-1 *} ... _* E₁ ,

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

            Полученное представление  EQ Asup(-1;sdo(x n))  в виде произведения элементарных матриц называется мультипликативной формой обратной матрицы.

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

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

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

p = c_{x *}  EQ Asup(-1;sdo(x))                                                                                  (3)

так что, если  EQ Asup(-1;sdo(x))  дана в мультипликативной форме, то приходится оценить следующее матричное произведение:

p = (...((c_{x *} E_k­) _* E_k-1) _* ...) _* E₁ .

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

E = [u₁, u₂, ..., u_r-1, h, u_r+1, ..., u_m ],                                               (4)

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

u = (u₁, ..., u_m)                                                              (5)

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

uE = (u₁, ..., u_r-1, d, u_r+1, ..., u_m),

где

d = u _* h =  EQ isu(i=1;m; u_{i *} h_i)  ,

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

Вычисление ведущего столбца  EQ o(P;—)_s :

            Вектор  EQ o(P;—)_s

 EQ o(P;—)_s E_{k *} (... _* (E_{2 *} (E_{1 *} P_s))...) .                                                 (6)

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

Eu = (a₁, ..., a_m),

где

 EQ a_i = blc{(aal(u_i + h_{i *} u_r ; i=1;...;m; i¹r;; h_{r *} u_r ; 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)   E_k) в соответствии с (3), где i изменяется от iteration до 1 (если iteration = 1, то данный пункт пропускается).

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

a)    Û D_s, s_min Û s ) ;

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

c)   

5.    Вычисление ведущего столбца AA ( EQ o(P;—)_s

a)    A;

b)   E_k) на 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_min

b)  

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/.

            Рассмотрим следующий пример:

F_max = 3x₁ + x₂

x₁   + 2x₂ ³ 5,

2x₁ + 4x₂ £ 16,

3x₁ + x₂ ³ 6,

x₁ + 3x₂ £ 9,

x₁, x₂ ³ 0.

Так как программе SASIMPL требуется постановка задачи в канонической форме, то приведем ее к канонической форме:

F_max = 3x₁ + x₂ + 0x₃ + Mx₄ + 0x₅ + 0x₆ + Mx₇ + 0x₈

x₁   + 2x₂ - x₃ + x₄ = 5,

2x₁ + 4x₂ + x₅ = 16,

3x₁ + x₂  - x₆ + x₇ = 6,

x₁ + 3x₂ + x₈ = 9,

x₁, x₂ ³ 0.

Таким образом,  мы ввели две свободные переменные x₃, x₆, и две искусственные - x₄ и x₇ .

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

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_max преобразована к F_min путем умножения на -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] Тихненко не понравилось в интерфейсе слишком!! много разных цветов (я это тоже осознал - цветов в программе, как на попугае...). Еще, естественно, не понравилось то, что задаваь задачу надо вне программы и то, что надо вручную делать единичный базис...

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовому проекту по “Системному анализу” Тема: “Решение задач линейного программирования большой размерности” Выполнил студент гр. Э-282:      Богдановский А. А. Проверил преподаватель: Тихненко Е. В. ____

 

• 14:21 05 Июля 2016
  Российско-китайский медуниверситет откроет магистерскую программу по TCM
• 01:21 05 Июля 2016
  На форуме МГУ Россия и Китай обсудят научно-образовательное сотрудничество
• 11:00 04 Июля 2016
  Реморенко: "ЕГЭ-туризм" в России сходит на нет
• 10:52 04 Июля 2016
  Летняя российско-австрийская школа откроется в Москве
• 15:31 01 Июля 2016
  В СПбГУ могут воссоздать географический факультет

Заказать уникальную работу