Реферат: Модифицированный симплекс-метод с мультипликативным представлением матриц

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

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

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

Выполнил студент гр. Э-282:

     Богдановский А. А.

Проверил преподаватель:

Тихненко Е.В.

________________________

Дата:

“___”__________ <st1:metricconverter ProductID=«1996 г» w:st=«on»>1996 г</st1:metricconverter>.

<span Times New Roman";mso-bidi-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:KO;mso-bidi-language: AR-SA">

СОДЕРЖАНИЕ

 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

<span Times New Roman"; mso-bidi-font-family:«Times New Roman»;mso-font-kerning:14.0pt;mso-ansi-language: RU;mso-fareast-language:KO;mso-bidi-language:AR-SA">
<h1 %1:1:0:." Kolesnikov 20081025T2321">1.<span Times New Roman"">               

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

<h1 %1:2:0:." Kolesnikov 20081025T2321">2.<span Times New Roman"">               

<a А. А._1";mso-comment-date:20081025T0728">[А. А.1] 

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

·<span Times New Roman"">     

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

·<span Times New Roman"">     

·<span Times New Roman"">     

·<span Times New Roman"">     

<h1 %1:3:0:." Kolesnikov 20081025T2321">3.<span Times New Roman"">               

<a А. А._2";mso-comment-date:20081025T0728">[А. А.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 — ограничений.

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

<h2 %1:3:0:.%2:1:0:." Kolesnikov 20081025T2321">3.1.<span Times New Roman"">           

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

            При  решении задач линейного программирования, вкоторых 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.

<h2 %1:3:0:.%2:2:0:." Kolesnikov 20081025T2321">3.2.<span Times New Roman"">           

            Назовемэлементарной матрицей матрицу, отличающуюся от единичной только одной строкойили столбцом. При мультипликативном представлении матрица  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 .

<h2 %1:3:0:.%2:3:0:." Kolesnikov 20081025T2321">3.3.<span Times New Roman"">           

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

<h1 %1:4:0:." Kolesnikov 20081025T2321">4.<span Times New Roman"">               

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

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

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

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

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

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

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

Алгоритм:

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

<p %1:1:4:)" Kolesnikov 20081025T2321">a)<span Times New Roman"">   <p %1:2:4:)" Kolesnikov 20081025T2321">b)<span Times New Roman"">  <p %1:3:4:)" Kolesnikov 20081025T2321">c)<span Times New Roman"">   <p %1:4:4:)" Kolesnikov 20081025T2321">d)<span Times New Roman"">  

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

·<span Times New Roman"">     

·<span Times New Roman"">     

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

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

<p %1:1:4:)" Kolesnikov 20081025T2321">a)<span Times New Roman"">   x)и записываем его в массивдвойственных переменных Pi: Pi := Cx;<p %1:2:4:)" Kolesnikov 20081025T2321">b)<span Times New Roman"">  Ek) в соответствии с(3), где i изменяется от iteration до 1 (если iteration = 1, то данный пунктпропускается).

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

<p %1:1:4:)" Kolesnikov 20081025T2321">a)<span Times New Roman"">   Û Ds, s_min Ûs ) ;<p %1:2:4:)" Kolesnikov 20081025T2321">b)<span Times New Roman"">  ³ 0, то алгоритм заканчивает работу и текущиебазисные значения переменных являются оптимальным решением задачи.<p %1:3:4:)" Kolesnikov 20081025T2321">c)<span Times New Roman"">   

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

<p %1:1:4:)" Kolesnikov 20081025T2321">a)<span Times New Roman"">   A;<p %1:2:4:)" Kolesnikov 20081025T2321">b)<span Times New Roman"">  Ek) на AA в соответствии с(6), где i изменяется от 1 до iteration 1 (если iteration = 1, то данный пунктпропускается).<p %1:3:4:)" Kolesnikov 20081025T2321">c)<span Times New Roman"">   

6.    Поиск выводимой переменной из базиса:

<p %1:1:4:)" Kolesnikov 20081025T2321">a)<span Times New Roman"">   <p %1:2:4:)" Kolesnikov 20081025T2321">b)<span Times New Roman"">  q Ûth_min, r Ûr_min) будет соответствовать переменной с индексом в базисе r, выводимой избазиса;

7.    Добавляем в список элементарных матриц ещеодну:

<p %1:1:4:)" Kolesnikov 20081025T2321">a)<span Times New Roman"">   iterationв соответствии с (1), (2) и добавляем ее в список элементарных матриц;

8.    Делаем замену переменных в базисе:

<p %1:1:4:)" Kolesnikov 20081025T2321">a)<span Times New Roman"">    NXBasis[r_min] = s_min<p %1:2:4:)" Kolesnikov 20081025T2321">b)<span Times New Roman"">  

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

X[r_min] = th_min .

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

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

<h1 %1:5:0:." Kolesnikov 20081025T2321">5.<span Times New Roman"">               

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

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

<p %1:1:0:." Kolesnikov 20081025T2321; tab-stops:7.0cm">1.<span Times New Roman"">                                                    главныймодуль программы (интерфейс)<p %1:2:0:." Kolesnikov 20081025T2321; tab-stops:7.0cm">2.<span Times New Roman"">                                    реализацияметода<p %1:3:0:." Kolesnikov 20081025T2321; tab-stops:7.0cm">3.<span Times New Roman"">                                         библиотекаработы с матрицами<p %1:4:0:." Kolesnikov 20081025T2321; tab-stops:7.0cm">4.<span Times New Roman"">                                         обработкаошибок<p %1:5:0:." Kolesnikov 20081025T2321; tab-stops:7.0cm">5.<span Times New Roman"">                                              библиотекаинтерфейса пользователя<p %1:6:0:." Kolesnikov 20081025T2321; tab-stops:7.0cm">6.<span Times New Roman"">                                         то же

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

<h1 %1:6:0:." Kolesnikov 20081025T2321">6.<span Times New Roman"">               <a А. А._3"; mso-comment-date:20081025T0728">[А. А.3] Интерфейспользователя

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

<h2 %1:6:0:.%2:1:0:." Kolesnikov 20081025T2321">6.1.<span Times New Roman"">           

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

<img src="/cache/referats/2565/image002.gif" v:shapes="_x0000_i1025">

Рисунок  SEQ Рисунок * ARABIC

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

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

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

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

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

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

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

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

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

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

<img src="/cache/referats/2565/image003.gif" v:shapes="_x0000_i1026">

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

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

<img src="/cache/referats/2565/image004.gif" v:shapes="_x0000_i1027">

<h2 %1:6:0:.%2:2:0:." Kolesnikov 20081025T2321">6.2.<span Times New Roman"">           

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

<span Courier New";mso-bidi-font-family: «Times New Roman»">; *** Начало файла с данными о задаче ***

<span Courier New";mso-bidi-font-family: «Times New Roman»">; Пример  из  Ю.  П.Зайченко, С. А. Шумилова

<span Courier New";mso-bidi-font-family: «Times New Roman»">; «Исследование операций» N1.46

<span Courier New";mso-bidi-font-family: «Times New Roman»">n = 8                       ; количество переменных

<span Courier New";mso-bidi-font-family: «Times New Roman»">m = 4                       ; количество ограничений

<span Courier New";mso-bidi-font-family: «Times New Roman»">F = -3 -1 0 1000 0 0 1000   ; целевая функция минимизации

<span Courier New";mso-bidi-font-family: «Times New Roman»">LIMITS:                     ; задание ограничений

<span Courier New";mso-bidi-font-family: «Times New Roman»">1 2 -1 1 = 5

<span Courier New";mso-bidi-font-family: «Times New Roman»">2 4 0 0 1 = 16

<span Courier New";mso-bidi-font-family: «Times New Roman»">3 1 0 0 0 -1 1 = 6

<span Courier New";mso-bidi-font-family: «Times New Roman»">1 3 0 0 0 0 0 1 = 9

<span Courier New";mso-bidi-font-family: «Times New Roman»">;*** Конец файла ***

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

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

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

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

<h1 %1:7:0:." Kolesnikov 20081025T2321">7.<span Times New Roman"">               

            В качествеконтрольных примеров бралось множество примеров из задачника /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 .

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

<span Courier New";mso-bidi-font-family: «Times New Roman»">n = 8                       ; количество переменных

<span Courier New";mso-bidi-font-family: «Times New Roman»">m = 4                        ; количество ограничений

<span Courier New";mso-bidi-font-family: «Times New Roman»">F = -3 -1 0 1000 0 0 1000   ; целевая функция минимизации

<span Courier New";mso-bidi-font-family: «Times New Roman»">LIMITS:                     ; задание ограничений

<span Courier New";mso-bidi-font-family: «Times New Roman»">1 2 -1 1 = 5

<span Courier New";mso-bidi-font-family: «Times New Roman»">2 4 0 0 1 = 16

<span Courier New";mso-bidi-font-family: «Times New Roman»">3 1 0 0 0 -1 1 = 6

<span Courier New";mso-bidi-font-family: «Times New Roman»">1 3 0 0 0 0 0 1 = 9

            Как можноувидеть, функция Fmax преобразована к Fmin путемумножения на -1. В качестве больших коэффициентов M взято число 1000, котороево много раз превосходит соседние коэффициенты в целевой функции.

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

<span Courier New";mso-bidi-font-family: «Times New Roman»">Входные данные:

<span Courier New";mso-bidi-font-family: «Times New Roman»">Количество переменных n = 9

<span Courier New";mso-bidi-font-family: «Times New Roman»">Количество ограничений m = 5

<span Courier New";mso-bidi-font-family: «Times New Roman»">Вектор коэффициентов целевой функции C:

<span Courier New";mso-bidi-font-family: «Times New Roman»">-1.000 -1.000 -2.000 -1.000 0.000  0.000  0.000 0.000  0.000

<span Courier New";mso-bidi-font-family: «Times New Roman»">

<span Courier New";mso-bidi-font-family: «Times New Roman»">Матрица коэффициентов в ограничениях A:

<span Courier New";mso-bidi-font-family: «Times New Roman»"> 1.000  2.000 1.000 -1.000  1.000  0.000 0.000  0.000  0.000

<span Courier New";mso-bidi-font-family: «Times New Roman»"> 2.000  1.000 0.000  0.000  0.000 1.000  0.000  0.000 0.000

<span Courier New";mso-bidi-font-family: «Times New Roman»"> 1.000  2.000 0.000  0.000  0.000 0.000  1.000  0.000 0.000

<span Courier New";mso-bidi-font-family: «Times New Roman»"> 0.000  0.000 1.000  1.000  0.000 0.000  0.000  1.000 0.000

<span Courier New";mso-bidi-font-family: «Times New Roman»"> 0.000  0.000 -2.000 3.000  0.000  0.000 0.000  0.000  1.000

<span Courier New";mso-bidi-font-family: «Times New Roman»">

<span Courier New";mso-bidi-font-family: «Times New Roman»">Вектор правой части ограничений B:

<span Courier New";mso-bidi-font-family: «Times New Roman»">10.000  4.000  6.000 5.000  6.000

<span Courier New";mso-bidi-font-family: «Times New Roman»">

<span Courier New";mso-bidi-font-family: «Times New Roman»">********************************************************

<span Courier New";mso-bidi-font-family: «Times New Roman»">Итерация N0

<span Courier New";mso-bidi-font-family: «Times New Roman»">Значения базисных переменных:

<span Courier New";mso-bidi-font-family: «Times New Roman»">X5 = 10

<span Courier New";mso-bidi-font-family: «Times New Roman»">X6 = 4

<span Courier New";mso-bidi-font-family: «Times New Roman»">X7 = 6

<span Courier New";mso-bidi-font-family: «Times New Roman»">X8 = 5

<span Courier New";mso-bidi-font-family: «Times New Roman»">X9 = 6

<span Courier New";mso-bidi-font-family: «Times New Roman»">Значение целевой функции: 0.000

<span Courier New";mso-bidi-font-family: «Times New Roman»">

<span Courier New";mso-bidi-font-family: «Times New Roman»">Итерация N1

<span Courier New";mso-bidi-font-family: «Times New Roman»">Значения базисных переменных:

<span Courier New";mso-bidi-font-family: «Times New Roman»">X5 = 5

<span Courier New";mso-bidi-font-family: «Times New Roman»">X6 = 4

<span Courier New";mso-bidi-font-family: «Times New Roman»">X7 = 6

<span Courier New";mso-bidi-font-family: «Times New Roman»">X3 = 5

<span Courier New";mso-bidi-font-family: «Times New Roman»">X9 = 16

<span Courier New";mso-bidi-font-family: «Times New Roman»">Значение целевой функции: -10.000

<span Courier New";mso-bidi-font-family: «Times New Roman»">

<span Courier New";mso-bidi-font-family: «Times New Roman»">Итерация N2

<span Courier New";mso-bidi-font-family: «Times New Roman»">Значения базисных переменных:

<span Courier New";mso-bidi-font-family: «Times New Roman»">X5 = 3

<span Courier New";mso-bidi-font-family: «Times New Roman»">X1 = 2

<span Courier New";mso-bidi-font-family: «Times New Roman»">X7 = 4

<span Courier New";mso-bidi-font-family: «Times New Roman»">X3 = 5

<span Courier New";mso-bidi-font-family: «Times New Roman»">X9 = 16

<span Courier New";mso-bidi-font-family: «Times New Roman»">Значение целевой функции: -12.000

<span Courier New";mso-bidi-font-family: «Times New Roman»">

<span Courier New";mso-bidi-font-family: «Times New Roman»">Итерация N3

<span Courier New";mso-bidi-font-family: «Times New Roman»">Значения базисных переменных:

<span Courier New";mso-bidi-font-family: «Times New Roman»">X2 = 2

<span Courier New";mso-bidi-font-family: «Times New Roman»">X1 = 1

<span Courier New";mso-bidi-font-family: «Times New Roman»">X7 = 1

<span Courier New";mso-bidi-font-family: «Times New Roman»">X3 = 5

<span Courier New";mso-bidi-font-family: «Times New Roman»">X9 = 16

<span Courier New";mso-bidi-font-family: «Times New Roman»">Значение целевой функции: -13.000

<span Courier New";mso-bidi-font-family: «Times New Roman»">

<span Courier New";mso-bidi-font-family: «Times New Roman»">

<span Courier New";mso-bidi-font-family: «Times New Roman»">Данное решение является оптимальным!

 TC " СПИСОКЛИТЕРАТУРЫ "

<p %1:1:0:." Kolesnikov 20081025T2321">1.<span Times New Roman"">   <p %1:2:0:." Kolesnikov 20081025T2321">2.<span Times New Roman"">   <p %1:3:0:." Kolesnikov 20081025T2321">3.<span Times New Roman"">   <p %1:4:0:." Kolesnikov 20081025T2321">4.<span Times New Roman"">   <p %1:5:0:." Kolesnikov 20081025T2321">5.<span Times New Roman"">   <p %1:6:0:." Kolesnikov 20081025T2321">6.<span Times New Roman"">   <p %1:7:0:." Kolesnikov 20081025T2321">7.<span Times New Roman"">   

 TC "

<span Александр Богдановский"">

PAGE #"'Стр: '#'
'"   [А. А.1]Тихненко считает, что обращение к себе как к третьему лицу — плохой тон...

<span Александр Богдановский"">

PAGE #"'Стр: '#'
'"   [А. А.2]Оказывается каноническая форма постановки линейной задачи не обуславливаетналичие начального опорного плана (единичного базиса) — это в принципе самаяглавная ошибка курсовика (то есть у меня требовалась постановка задачи нетолько в каноническом виде, но и чтобы присутствовал единичный базис...)

<span Александр Богдановский"">

PAGE #"'Стр: '#'
'"   [А. А.3]Тихненко не понравилось в интерфейсе слишком!!! много разных цветов (я это тожеосознал — цветов в программе, как на попугае...). Ещ

еще рефераты
Еще работы по программированию, базе данных