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

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

Последовательность подстановок приводит к следующей формуле:

(2.23)

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

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

1. 2.7.2. Мультипликативное представление обратной матрицы

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

Определим единичную матрицу следующим образом:

(2.24)

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

(2.25)

при условии, что
. Если
, матрицы
не существует. Заметим, что матрицаполучается из матрицыпутём замены еёr-го вектор-столбцастолбцом.

1.5.1. Вычислительная схема, основанная на преобра­зовании обратных матриц. Анализируя вычислительную процедуру симплекс-метода с позиций оценки трудоемкости, не­трудно заметить, что наиболее критичным в этом плане являет­ся этап пересчета значений А и b при переходе от одного базис­ного плана к другому (п. 3 алгоритма). Однако в том случае, когда число ограничений задачи m явно меньше количества переменных n , можно добиться существенной «экономии», вы­полняя на очередной итерации q преобразование Жордана-Га­усса не над матрицей А (β ( q )), а над матрицей Δ -1 (β ( q )). При этом учитывается и то, что при необходимости, применяя формулу (1.26), всегда можно получить А (β ( q )) по Δ -1 (β ( q )). Более того, для выполнения описанных выше действий симплекс-процедуры нам в действительности не требовалась матрица А (β ( q )) целиком. Реаль­но в ней использовались только строка оценок a 0 (β ( q )) и ведущий столбец a l (β ( q )). Данные соображения положены в основу вы­числительной схемы симплекс-метода, основанной на преобра­зовании обратных матриц, которую также называют модифици­рованным симплекс-методом . Впервые данный алгоритм был предложен в 1951 г. в работах Л. В. Канторовича.

Вычислительной схеме модифицированного симплекс-мето­да соответствует система таблиц T 1 и Т 2 ( q ) . Таблица T 1 (рис. 1.7 ) является общей для всех итераций и служит для получения строки оценок текущего базисного плана a 0 (β ( q )). Если обозна­чить через δ i (β ( q )) (i Î 0: m ) строки матрицы Δ -1 (β ( q )), то из (1.26), в частности, следует, что

Как видно из рис. 1.7 , T 1 состоит из трех блоков:

Ø Ø в центре содержится матрица А ;

Ø Ø в левом блоке таблицы на каждой итерации дописывают­ся нулевые строки матрицы Δ -1 (β ( q ))для текущего ба­зиса ;

Ø Ø нижний блок, расположенный под матрицей А , на каж­дой итерации дополняется строкой оценок текущего плана, вычисленной по формуле (1.42).

Симплекс-таблица Т 2 ( q ) , изображенная на рис. 1.8 , соответ­ствует допустимому базису КЗЛП β ( q ) , получаемому на q -й ите­рации. Столбец N (β ( q )) содержит номера базисных столбцов (в последовательности вхождения в базис); столбец b (β ( q )) - компоненты вектора ограничений относительно текущего ба­зиса β ( q ) ; Δ -1 (β ( q )) - матрица, обратная по отношению к матри­це расширенных столбцов текущего базиса β ( q ) ; графа а l со­держит расширенный вектор условий, вводимый в базис на текущей итерации, а следующая графа - координаты а l (β ( q )) этого же столбца в текущем базисе β ( q ) .

По аналогии с п. 1.4.1 опишем формальную схему алгоритма модифицированного симплекс-метода.

0-этап. Нахождение допустимого базисного плана.

1. Для поиска допустимого базиса может быть применен ме­тод минимизации невязок, рассмотренный в п. 1.4.5. При этом для решения вспомогательной задачи используется процедура модифицированного симплекс-метода. В результате 0-этапа мы получаем допустимый базисный план x (β (1)) и соответствую­щие ему матрицу Δ -1 (β (1)) и вектор b (β (1)).

2. Заполняем центральную часть таблицы T 1 , содержащую матрицу А .

3. Содержимое матрицы Δ -1 (β (1)) и вектора b (β (1)), получен­ных на этапе поиска допустимого базисного плана, переносит­ся в таблицу T 2 (1) .

4. Полагаем номер текущей итерации q равным 1 и перехо­дим к I-этапу.

1-этап. Стандартная итерация алгоритма - выполня­ется для очередного базисного плана x (β ( q )).

1°. Проверка оптимальности текущего базисного плана . Содержимое нулевой строки таблицы T 2 ( q ) - δ 0 (β ( q )) переписы­вается в соответствующую графу таблицы T 1 . По формуле (1.42) рассчитываем и заполняем строку a 0 (β ( q )). Осуществля­ем просмотр строки оценок a 0 (β ( q )). Возможны два варианта:

1΄. a 0 (β ( q ))≥0 -план, соответствующий текущему базису задачи, оптимален. Вычислительный процесс закончен. Со­гласно формулам (1.33) и (1.32) выписываются оптимальный план задачи х * = x (β ( q )) и оптимальное значение целевой функ­ции f (х *) = f (x (β ( q ))).

1". В строке оценок a 0 (β ( q )) существует по меньшей мере один элемент a 0, j (β ( q ))<0, т. е. имеющий отрицательную оцен­ку. Следовательно, план x (β ( q )) - неоптимален . Выбирает­ся номер l , соответствующий элементу, имеющему минималь­ную (максимальную по абсолютной величине) отрицательную оценку:

l -й столбец матрицы A становится ведущим и должен быть вве­ден в очередной базис. Переходим к пункту 2° алгоритма.

2°. Определение столбца, выводимого из базиса . Перепи­сываем ведущий столбец а l из таблицы T 1 в текущую таблицу Т 2 ( q ) . По формуле а l (β ( q )) = Δ -1 (β ( q ))а l заполняем соответствую­щий столбец в таблице Т 2 ( q ) . Возможны два варианта:

2". Для всех i Î 1: m а i , l (β ( q ))≤0. Делается вывод о неограни­ченности целевой функции и завершается вычислительный процесс.

2". Существует по крайней мере один индекс i Î 1: m , для ко­торого а i , l (β ( q ))>0. Согласно правилу (1.27) определяются мес­то r и номер N r (β ( q )) для столбца, выводимого из базиса. Пере­ходим к пункту 3° алгоритма.

3°. Пересчет относительно нового базиса элементов столбца b и матрицы Δ -1 . Переход к новому базису β ( q +1) , кото­рый получается введением в базис β ( q ) столбца а l и выводом из него столбца а r , осуществляется по формулам, аналогичным формулам (1.28)-(1.31). Они имеют вид:

Полагаем номер текущей итерации q : =q +l и переходим к первому пункту алгоритма.

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

1.5.2. Пример решения ЗЛП модифицированным сим­плекс-методом. Приведем решение рассмотренной ранее за­дачи (1.34)-(1.35), основанное на использовании процедуры модифицированного симплекс-метода. По аналогии с п. 1.4.3 оно начинается с выбора очевидного исходного базиса, обра­зуемого столбцами {5,2,3}. Для него уже были вычислены Δ -1 (β ( q )) и b (β ( q )), поэтому заполнение начальных таблиц T 1 и Т 2 (1) не представляет труда.

На первой итерации мы переписываем нулевую строку

из Т 2 (1) в T 1 и, умножив ее на матрицу A , получаем строку оце­нок

Так как a 0 (β (1)) содержит отрицательные элементы, то делаем вывод о неоптимальности плана, соответствующего базису β (1) , и, выбрав наименьшую отрицательную оценку (-88), получаем номер столбца, вводимого в базис, l = 4.

Переписываем столбец

из таблицы T 1 в Т 2 (1) и пересчитываем его координаты относи­тельно текущего базиса, т. е. умножаем матрицу Δ -1 (β ( q )), рас­положенную в таблице Т 2 (1) слева, на а 4 .

После заполнения таблицы Т 2 (1) данными по вводимому в но­вый базис столбцу можно перейти к определению номера выво­димого столбца. Эта процедура осуществляется в полной ана­логии с обычным симплекс-методом. Рассмотрев отношения элементов b i (β (1)) и a i , l (β (1)) для {i Î1:m| a i , l (β (1))>0} и определив минимальное из них, находим, что r = 2. Следовательно, стол­бец с номером N 2 (β ( q )) = 2 должен быть выведен из базиса. Та­ким образом, получаем очередной допустимый базис задачи с N (β (2)) = {5, 4, 3}. Элемент a 2,3 (β (1)) является ведущим (обведен кружком). Применив формулы (1.43)-(1.46), переходим к сим­плекс-таблице, соответствующей второй итерации Т 2 (2) , и пола­гаем индекс текущей итерации q = 2.

Повторяя те же самые действия (их легко проследить по при­водимым здесь таблицам Т 2 (2) и Т 2 (3) , на третьей итерации мы получим оптимальный план задачи и оптимальное значение целевой функции, которые извлекаются из второго столбца таблицы Т 2 (3) . Легко заметить, что в процессе решения мы «про­шли» по той же самой последовательности допустимых базис­ных планов, которая встречалась в п. 1.4.3.

Поясним вычисления a i , j ¢ с использованием “правила прямоугольника“. Необходимо взять разрешающий элемент a k , s и мысленно соединить его с тем коэффициентом, новое значение которого требуется найти. Эту прямую следует считать главной диагональю, на ней строится прямоугольник, сторонами которого являются строки и столбцы. В прямоугольнике нужно провести побочную диагональ, тогда значение нового коэффициента будет равно его исходному значению, из которого вычитается произведение элементов, стоящих на побочной диагонали, поделœенному на разрешающий элемент. Поясним эти действия на схеме (рис. 1.9). Прежде чем заполнить симплекс-таблицу исходные уравнения следует представить в виде (1.21).

	a k,j
			a i,j

Суть преобразований симплекс-метода рассмотрим на примере 1.4. Давайте вспомним ограничивающие неравенства и целœевую функцию из этого примера и найдем max целœевой функции, пользуясь вышеизложенным методом:

F = 908X 1 + 676X 2 ® max.

X 1 + X 2 14,

X 2 10,

10 X 1 + 8 X 2 120,

7X 1 + 5 X 2 70,

4X 1 + 2X 2 28,

.

Преобразуем ее в каноническую форму, вводя дополнительные переменные X j 0, и превратив неравенства в равенства. Следует обратить внимание, что если в неравенстве стоит знак "", то при свободной переменной пишут " - ", в противном случае - " + ":

X 1 + X 2 = 14 - X 3 ,

X 2 = 10 - X 4 ,

10 X 1 + 8 X 2 = 120 - X 5 ,

7X 1 + 5 X 2 = 70 - X 6 ,

4X 1 + 2X 2 = 28 - X 7 .

Чтобы приступить к процедуре симплекс-метода, нужно из множества базисных решений полученной системы уравнений сначала найти опорное. С учетом этого в решении задач симплекс-методом различают три этапа:

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

Определœение допустимого решения;

Определœение оптимального решения.

1-й этап

Первоначальное базисное решение систем находим, полагая свободными переменные X 1 и X 2 .

Тогда X 3 = 14 - X 1 - X 2 ,

X 4 = 10 - X 2 ,

X 5 =120 - 10X 1 - 8X 2 ,

X 6 = 70 - 10X 1 - 5X 2 ,

X 7 = 28 - 4X 1 - 2X 2 ,

F = 908X 1 + 676X 2 = 0 .

Преобразуем эти уравнения к нормальному виду:

X 3 = 14 - (X 1 + X 2),

X 4 = 10 - (0X 1 + X 2),

X 5 =120 - (10X 1 + 8X 2),

X 6 = 70 - (7X 1 + 5X 2),

X 7 = 10 - (4X 1 + 2X 2),

F = 0 + 908 X 1 + 676 X 2 .

Полученную систему уравнений запишем в виде исходной симплекс-таблицы (табл. 1.9). В табл. 1.9 нет отрицательных свободных членов. Следовательно, нами получено опорное (допустимое) решение, так как допустимым решением является любое неотрицательное решение (при котором > 0 ), но оно не является оптимальным.

Очевидно, что если бы при всœех неизвестных в целœевой функции F стояли положительные коэффициенты, то было бы достигнуто максимальное значение F . Отсюда вытекает признак оптимальности допустимого решения: в F - строке симплекс-таблицы не должно быть отрицательных коэффициентов.

Таблица 1.9

Базисные переменные X б	Свободный член	Свободные переменные
X 1	X 2
X 3
X 4
X 5
X 6
X 7
F		- 908	- 676

2-й этап

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

Значение целœевой функции F в новом опорном (допустимом) решении должно быть больше, чем в предыдущем;

Новое решение системы должно быть также опорным (допустимым).

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

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

По выше изложенному правилу для нахождения допустимого решения меняют местами базисные и свободные переменные. Для этого находят разрешающий элемент (в табл. 1.9 он взят в рамку). В нашем случае разрешающим должна быть как столбец X 1 , так и X 2 . Деля свободные переменные на соответствующие значения X 1 иX 2 (кроме строки F ), находим наименьшее положительное значение. Важно заметить, что для столбца X 1 :

Важно заметить, что для столбца X 2 :

Наименьшее отношение 28/4 определяет разрешающую строку и разрешающий столбец, а пересечение разрешающего столбца и разрешающей строки - разрешающий элемент a ks = 4. В табл. 1.9 разрешающий столбец и разрешающую строку отмечаем стрелками (®). Определивa ks , строят следующую таблицу, в которой меняют местами переменные, входящие в строку и столбец разрешающего элемента͵ ᴛ.ᴇ. переводят базисные переменные в свободные, а свободные - в базисные.

В нашем примере меняем местами переменные Х 7 и Х 1 , отмеченные в табл. 1.9 стрелками. Коэффициенты новой табл. 1.10 находят по коэффициентам старой табл. 1.9, используя выражения, приведенные в табл. 1.8 и “правило прямоугольника”. В табл. 1.10 снова не имеем оптимального решения.

Таблица 1.10

Базисные переменные Х б

Свободный член В

Свободные переменные

X 7

X 2

Х 3

- 1/4

1/2

Х 4

Х 5

-5/2

Х 6

-7/4

3/2

Х 1

1/4

1/2

F

-222

По вышеописанным правилам в табл. 1.10 находим разрешающий элемент 1 и строим новую табл. 1.11 сделав замещение базиса (Х 4 и Х 2 ). Особо подчеркнем, что для нахождения разрешающего элемента мы должны выбирать наименьшее положительное значение, ᴛ.ᴇ. отрицательные отношения свободных членов к коэффициентам разрешающего столбца мы не рассматриваем.

3-й этап

Проверим, является ли найденное решение оптимальным, а для нашего примера - максимальным. Для этого сделаем анализ целœевой функции F : F = 8576 + 227 X 7 + 222 X 4 .

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

X 3 = 2; X 2 = 10; X 5 = 20; X 6 = 6; X 1 = 2; X 7 = X 4 = 0;

F max = 8576.

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

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

1. Нахождения первоначального базисного (опорного) решения и формирование исходной таблицы.

2. Отыскание разрешающего элемента a ks (нахождение отрицательного свободного члена - b i < 0 и минимального отношенияb i / a ij ; если в строке отрицательного свободного члена нет отрицательных коэффициентов, то задача неразрешима).

3. Перерасчет новой таблицы по формулам табл. 1.8.

4. Проверка наличия отрицательного свободного члена. В случае если он есть, то переходим к п. 2. Отсутствие отрицательного свободного члена означает, что получено опорное (допустимое) решение.

5. Аналогично п. 2 - 4 выполняется перерасчет таблицы при поиске оптимального решения.

Решение задачи ЛП симплекс-методом в матричной форме

Требуется минимизировать ,

при ограничениях

при "x ³ 0.

Введем векторы:

C = (C 1 , ... , C n) - вектор оценок,

X = (X 1 , ... , X n) - вектор переменных,

b = (B 1 , ... , B m) - вектор ограничений

и матрицу

A =

размером (mn) - матрицу коэффициентов ограничений.

Тогда задача ЛП будет иметь следующую трактовку:

минимизировать F=CX

при условиях AX = b, X 0.

Эту задачу можно записать в матричной форме:

Введем обозначение:

А * = - здесь матрица A * размером (m+1)(n+1).

Согласно выше приведенной методике находят разрешающий элемент a ks .

Следующий шаг симплекс-метода - процедура исключения Гаусса, которая позволяет сделать всœе коэффициенты в s - м столбце, кроме a ks , нулевыми, a ks - равным единице.

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

(1.23)

, гдеk 0; s 0.

В случае если всœе столбцы матрицы A разделить на базисные B и небазисные N, то задачу ЛП можно записать так:

,

где C b и C N - соответствующие компоненты вектора C, X b , X N - базисные и небазисные переменные.

Для выбора начальных базисных переменных x b следует умножить уравнение слева на матрицу:

где R= C b B -1 .

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

,

гдеI - единичная матрица.

Отсюда следует, что относительные оценки при небазисных переменных

c j = c j - C b B -1 a j = c j - Ra j .

Базис будет допустимым, в случае если свободные члены при базисных переменных будут неотрицательными, ᴛ.ᴇ. B -1 b ³ 0.

В случае если c j ³ 0 для , то базис является оптимальным решением задачи. Вектор называют вектором текущих цен. Каждая строка умножается на вектор R и вычитается из строки коэффициентов стоимости, для того чтобы исключить коэффициенты стоимости при базисных переменных.

В случае если задача ЛП задана не в канонической форме, ᴛ.ᴇ.

минимизировать F=CX

при условиях AX b , X 0,

то, вводя слабые переменные, их можно записать в виде

Метод исключения по строкам для матрицы эквивалентен умножению этой матрицы слева на B -1 , где B - базис подматрицы A , тогда

,

ᴛ.ᴇ. матрица, получаемая на месте единичной I , будет матрицей, обратной для текущего базиса. Относительные оценки, расположенные над единичной матрицей, будут

,

поскольку - единичные векторы.

Так как F= C b B -1 b = Rb, текущее значение целœевой функции равно произведению вектора текущих цен матрицы A на исходный вектор b .

Пример.
Размещено на реф.рф
F= 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5 ® min

при ограничениях

2X 1 + 3X 3 + 4X 4 + 2X 5 = 10,

3X 2 + 3X 4 + 6X 5 = 9,

.

Для данного примера матрицаA * будет иметь вид

.

Пусть X 1 и X 2 - базисные переменные.

Матрица B имеет вид

.

Тогда обратная матрица B -1 имеет следующий вид

.

Напомним, что , где присоединœенная матрица, составленная из алгебраических дополнений элементов b ik определителя матрицы B .

Определитель равен:

= .

Следовательно, матрица B неособенная.

Алгебраические дополнения элементов определителя имеют следующие значения:

b 11 = 3, b 12 = 0, b 12 = 0, b 22 = 2 ; т.е. .

Умножив на , находим обратную матрицу:

.

Вектор текущих цен будет

R = C b B -1 = = .

Напомним, что C b - базисные компоненты вектора C :

Тогда = .

Для выбора начального базиса нужно матрицу A * умножить слева на матрицу

=

.

Разрешающий элемент находится в квадрате.

Итерация симплекс-метода эквивалентна полученной таблице, умноженной слева на следующую матрицу:

.

Эта матрица получена из матрицы (1.23)

Здесь a ks = 2 ;

a 11 = 1; a 12 = - a 0s / a ks = - 12/2 = - 6;

a 13 = 0 ; a 21 = 0 ; a 22 = 1/ a ks = 1/2 ; a 23 = 0;

a 31 = 0 ; a 32 = - a ms / a ks = -1/2 ; a 33 = 1.

Тогда имеем

=

(1.24)

Разрешающий элемент помещен в квадрат.

Следующая итерация симплекс-метода равносильна умножению слева на матрицу

.

=

.

Следовательно, F min =11; X 4 =7/3; X 5 =1/3; X 1 =X 2 =X 3 =0.

Модифицированный симплекс-метод(МСМ ) отличается от обычного симплекс-метода(СМ ) тем, что в СМ всœе элементы симплекс-таблиц пересчитываются на каждой итерации и при получении очередной таблицы, всœе предыдущие таблицы, включая исходную, не сохраняются. В МСМ сохраняется исходная таблица, а на каждой итерации определяются: строка относительных оценок C , вводимых в базис , и текущее значение вектора правых частей ограничений . Для того чтобы определить всœе элементы таблицы после j- й итерации СМ , достаточно знать матрицу B -1 , соответствующую этой таблице, исходную матрицу и индексы текущих базисных переменных. Тогда текущий вектор R = C b B -1 (индексы текущих базисных переменных определяют, какие элементы вектора оценок из исходной таблицы входят в вектор С b ); =B -1 b , где b берется из исходной таблицы, а любой столбец новой таблицы=B -1 a j , гдеa j - столбец исходной таблицы.

Пусть задана теперь исходная таблица B -1 , соответствующая таблице i -й итерации. Для того чтобы получить матрицуB -1 , соответствующую (i+1)- й итерации, нужно определить небазисный столбец i -й таблицы , который должен быть введен в базис. ИзСМ следует, что должна быть введен в базис, в случае если C j <0. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, крайне важно вычислить С j для i -ой таблицы, выбрать среди них <0, а затем вычислить

a S = B -1 и =B -1 b (= C j - Ra j ).

Найдя разрешающий элемент и используя элементы векторов и , находим матрицу B -1 для следующей таблицы.

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

F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5 ® min

при ограничениях:

2X 1 + 3X 3 + 4X 4 + 2X 5 = 10,

3X 2 + 3X 4 + 6X 5 = 9,

Выбрав в качестве базисных переменных X 1 и Х 2 , получили следующую задачу: F = 43 - 9/2X 3 - 12X 4 - 12X 5

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Пермский государственный технический университет

Лысьвенский филиал

Кафедра ЕН

Курсовая работа

по дисциплине «Системный анализ и исследование операций»

по теме: «Симплекс метод в форме презентации»

Выполнил студент группы ВИВТ-06-1:

Старцева Н. С.

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

Мухаметьянов И.Т.

Лысьва 2010г.

Введение. 3

Математическое программирование. 5

Графический метод. 6

Табличный симплекс – метод. 6

Метод искусственного базиса. 7

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

Двойственный симплекс – метод. 7

Общий вид задачи линейного программирования. 9

Решение задачи линейного программирования симплекс-методом. 11

Вычислительные процедуры симплекс – метода. 11

Теорема 1: 13

Теорема 2: 14

Теорема 3: 15

Теорема 4: 15

Теорема 5: 15

Переход к новому опорному плану. 15

Двойственная задача. 17

Теорема 1 (первая теорема двойственности) 18

Теорема 2(вторая теорема двойственности) 18

Заключение. 20

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

7x 1 +5x 2 →max

x 3 =19-2x 1 -3x 2 (0;0;19;13;15;18)

x 4 =13-2x 1 -x 2 первоначальный опорный план

x 6 =18-3x 1 F(x 1 , x 2)=7*0+5*0=0

x i ≥0, (i=1,…n)

На интуитивном уровне понятно, что естественным будет увеличение x 1 , так как коэффициент при нем больше чем при x 2 . Оставляя x 2 =0, мы можем увеличивать до тех пор, пока x 3 , x 4 , x 5 , x 6 будут оставаться неотрицательными.

x 1 =min{19/2;13/2;∞;18/3}=6

Это означает что при x 1 =6, x 6 =0, то есть x 1 -переходит в число базисных, а x 6 -в число свободных.

x 3 =19-2(6-1/3 x 6)-3 x 2 =19-12+2/3 x 6 -3 x 2 =7+2/3 x 6 -3 x 2

x 4 =13-2(6-1/3 x 6)- x 2 =1+2/3 x 6 - x 2

F(x 2 ; x 6) =42-7/3 x 6 +5 x 2

При данном опорном плане (6;0;7;1;15;0) x 2 переводиться из свободных в базисные переменные:

x 2 =min{∞;7/3;1/11;15/3}=1

Выражаем x 2 через x 4

x 2 =1+2/3 x 6 - x 4

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

x 3 =7+2/3 x 6 -3(1+2/3x 6 –x 4)= 7+2/3 x 6 -3-2x 6 +3x 4 =4-4/3x 6 +3 x 4

x 5 = 12-2x 6 +3x 4 -

F=42-7/3 x 6 +5(1+2/3x 2 - x 4) =47-7/3x 6 +10/3x 6 -5x 4 =47+x 6 -5x 4

x 6 положительное, следовательно можно увеличивать

x 6 =min{18;∞;3;6}=1

x 4 =4/3-4/9 x 6 - 1/3x 3

F=47+x 6 -5(4/3-4/9-1/3x 3)

В целевой функции все коэффициенты при переменных отрицательны, значение функции увеличивать нельзя, аналогично преобразовываем остальные переменные, находим опорный план, из которого определяем x 1 ,x 2 .

1. Пересечение замкнутых множеств, множество нетривиальных ограничений.

2. Множество решений системы линейных нестрогих неравенств и уравнений является замкнутым.

αX=(αx 1 ,x 2 ,…, αx n)

X+Y=(x 1 +y 1 , x 2 +y 2 ,… x n +y n)

Линейные координаты X 1 ,X 2 ,…X n называется точка P=λ 1 x 1 + λ 2 x 2 +…+ λ k x k

Множество P={λ 1 x 1 + λ 2 x 2 +…+ λ k x k } 0≤ h i ≤1 для i= 1,…k n åR i =1, 1≤ i ≤k выпуклая линейная комбинация точек x 1 ,x 2 ,…x n . Если k=2, то это множество называется отрезком. X 1 ,X 2 – концы отрезка. Угловой точкой замкнутого множества называется точка, которая не является нетривиальной линейной комбинацией точек множества (угловая точка).

Нетривиальность означает, что хотя бы одна из λ отлична от 0 или 1.

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

Если задача линейного программирования имеет единственное решение, то оно лежит среди угловых точек ОДР. А если решение не одно, то среди решений имеется несколько угловых, таких что множество всех решений является их выпуклой линейной комбинацией.

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

Переход к новому опорному плану

F 1 =F(x 1); F 2 =F(x 2) F 2 -F 1 =-υ k Δ k =F 2 можно доказать, где υ k рассмотренный выше минимум, который определяется при введении k-ой переменной в базис, а Δ k =åс j x j (1) -С k , где n ≤ j ≤1, X 1 =(x 1 (1) ;x 2 (1) ;…x n (1))- оценка k-ой переменной, поэтому если решается задача на максимум, то величина ΔF 2 положительной должна быть, Δk – отрицательная. При решении задач на минимум ΔF 2 -отрицательная, Δ k - положительная. Эти величины вычисляются и если среди ΔF 2 все значения не положительны, то при решении задач на минимум наоборот. Если при решении на максимум среди ΔF 2 несколько положительных, то вводим в базис тот вектор, при котором эта величина достигает максимум, а если задача решается на минимум и среди ΔF 2 несколько отрицательных, то в число базисных включается вектор с наименьшим значением ΔF 2 , то есть с наибольшим по абсолютной величине. При выполнении этих условий гарантируется наибольшее возможное изменении значения функции.

Решение задачи будет единственным, если для любых векторов x k не входящих в базис, оценки Δ k ≠0, если хотя бы одно из таких Δ k =0, то решение не является единственным, для нахождения другого решения переходим к другому опорному плану, включая в базис x k , где Δ k =0. Перебор все такие опорные решений составляют их в линейную комбинацию, которая и будет решением задачи.

Если для любого некоторого Δ k противоречащих условию оптимальности коэффициенты при переменной x k ≤ 0, то система ограничений не ограничена, то есть оптимального плана не существует.

Двойственная задача

Двойственная задача (ДЗ) – это вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными, чем при прямой задачи (ПЗ). Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных. Для перехода к ДЗ необходимо, чтобы ПЗ была записана в стандартной канонической форме. При представлении ПЗ в стандартной форме в состав переменных x j включаются также избыточные и остаточные переменные.

Двойственная задача имеет:

1. m переменных, соответствующих числу ограничений прямой задачи;

2. n ограничений, соответствующих числу переменных прямой задачи.

Двойственная задача получается путём симметричного структурного преобразования условий прямой задачи по следующим правилам:

· Каждому ограничению b i ПЗ соответствует переменная y i ДЗ;

· Каждой переменной x j ПЗ соответствует ограничение C j ДЗ;

· Коэффициенты при x j в ограничениях ПЗ становятся коэффициентами левой части соответствующего ограничения ДЗ;

· Коэффициенты C j при x j в целевой функции ПЗ становятся постоянными правой части ограничения ДЗ;

· Постоянные ограничений b i ПЗ становятся коэффициентами целевой функции ДЗ.

Рассмотрим следующие две задачи:

F = С 1 х 1 +С 2 х 2 +... +С n x n →max

(5)

a 11 x 1 + a 22 x 2 + ... + a 1m x n ≤ b 1

a 21 x 1 + a 22 x 2 + ... + a 2m x n ≤b 2

a m1 x 1 + a m2 x 2 + ... + a mn x n ≤b m

x j ≥0 j=1,…,n

Z = b 1 х 1 +b 2 х 2 +... +b n x n →min

(6)

a 11 y 1 + a 21 y 2 + ... + a m1 y 1 ≤ C 1

a 12 y 1 + a 22 y 2 + ... + a m 2 y 2 ≤C 2

. . . . . . . . . . . . . . . . . . . . . . .

a 1 n y n + a 2 m y n + ... + a nm y n ≤C n

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

1. Основы математических методов и их применение;

2. Решение задач с помощью симплекс – метода.

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

В основу данной разновидности симплекс-метода положены такие особенности линейной алгебры, которые позволяют в ходе решения задачи работать с частью матрицы ограничений. Иногда метод называют методом обратной матрицы.

В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Способность хороша для ситуаций, когда число переменных n значительно превышает число ограничений m.

В целом, метод отражает традиционные черты общего подхода к решению задач линейного программирования, включающего в себя канонизацию условий задачи, расчёт симплекс – разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана – Гаусса. Особенности заключаются в наличии двух таблиц – основной и вспомогательной, порядке их заполнения и некоторой специфичности расчётных формул.

Зная оптимальный план этой задачи, на основе соотношений получаем оптимальный план исходной задачи.

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

1. Первоначальную задачу сводят к задаче линейного программирования.

2. Находят решение линейной задачи

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

Первый этап: Получение задания к курсовой работе

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

Под каждую цифру записываются буквы a, b, c, d, e, f в следующем виде:

из последней строки таблицы индивидуальных заданий находим столбцы соответствующие буквам a, b, c, d, e, f. Тогда числовыми данными, необходимыми для выполнения данной курсовой работы, будут данные находящиеся в а – том столбце в строке 9, b – том столбце в строке 5, c – том столбце в строке 5, d – том столбце в строке 8, e – том столбце в строке 7и f – том столбце в строке 2.

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

На некотором заводе производится три вида продукта и при этом расходуется два вида ресурсов. Производственная функция каждого вида продукта на предприятии опишется равенствами:

где С i и - постоянные величины, i = 1, 2, 3;

X 1 – трудовые ресурсы в человеко-днях;

Х 2 – денежно-материальные средства, в тенге;

У i – получаемый продукт

Х 1 = а 1 х 1 + b 1 x 2 + c 1 x 3

Х 2 = а 2 х 1 + b 2 x 2 + c 2 x 3

Найти все неотрицательные базисные решения и определить оптимальный план F = y 1 + y 2 + y 3 .

Известно, что продукт для производства j – того вида затрачивается a ij единиц i – того ресурса. Эти затраты даются в таблицах 3.9.1. – 3.9.10

Последующие числовые данные берутся только из таблицы исходных данных выбранного варианта задания т.е. из таблицы №3.9.11.

2. По столбцу таблицы №3.9.11 для строки 8 исходной таблицей затрат единиц ресурса, будет таблица №3.9.4 т.е. следующая таблица:

Продукты ресурсы
I	8	4	6
II	160	240	200

3. По столбцу c – на 3 строке находим с 1 =6, α 1 =0,6

4. По столбцу d – на 5 строке определяем с 2 =5, α 2 =0,5

5. По столбцу e – по 4 строке установим, что с 3 =8, α 3 =0,4.

6. И наконец по столбцу f – в 1 строке найдем Т чел.дней =1000, П тенге = 280000

Для производства имеются трудовые ресурсы Т чел.дней и денежно-материальные средства П тенге.

Требуется найти оптимальный план выпуска продукции, при котором выпускаемый продукт будет наибольшим.

Второй этап – составление математической модели задачи

1. На основании полученных в первом этапе исходных данных и описания заданного производственного процесса составляется следующая таблица:

Продукты ресурсы
I	8	4	6	1000
II	160	240	200	280000

Через Х 1 обозначим ресурсы I вида.

Через Х 2 обозначим ресурсы II вида.

2. Обращаясь к условиям задачи, определяем все возможные ограничения, объединяя их в систему ограничений.

8Х 1 + 4Х 2 + 6Х 3 ≤ 1000

240Х 1 + 200Х 2 + 160Х 3 ≤ 280000

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

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

Для решения задачи линейного программирования применяется симплекс – метод.

Третий этап – выбор метода решения полученной математической задачи

1. Для решения задач линейного программирования симплекс – методом задача приводиться к каноническому виду:

8Х 1 + 4Х 2 + 6Х 3 + Х 4 = 1000

240Х 1 + 200Х 2 + 160Х 3 + Х 5 = 280000

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

Нахождение точки Куна-Таккера обеспечивает получение оптимального решения задачи нелинейного программирования. Теорему 2 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример: Минимизировать при ограничениях С помощью теоремы 2 докажем, что решение является оптимальным. Имеем Так...

Лучей, исходящих из одной точки, называется многогранным выпуклым конусом с вершиной в данной точке. 1.4 Математические основы решения задачи линейного программирования графическим способом 1.4.1 Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n = 2 и n = ...

Положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение. Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой...