МОДИФИЦИРОВАННЫЙ СИМПЛЕКС МЕТОДСимплекс-метод – не самая эффективная
компьютерная процедура, так как она вычисляет и
хранит информацию, которая не нужна для текущей
итерации и может вообще не использоваться для
принятия решений при последующих итерациях. Для
коэффициентов неосновных переменных в уравнении
(0), коэффициентов введенных основных переменных
в других уравнениях и правых частях уравнений при
каждой итерации используется только релевантная
информация. Поэтому нужна процедура, которая
может получать эту информацию эффективно, без
вычислений и хранения всех других коэффициентов
(это и есть модифицированный симплекс-метод).
Основная идея модифицированного
симплекс-метода заключается в использовании
текущей обратной матрицы
(и исходных данных задачи) при выполнении
вычислений, необходимых для определения
включаемой и исключаемой переменных.
Представление обратной матрицы в
мультипликативной форме позволяет
вычислять последовательность обратных
матриц непосредственно по исходным
данным без использования многократных
операций обращения каждого базиса. Как
и в обычном симплекс-методе, в данном
случае исходный базис всегда представляет
собой единичную матрицуI,
обратной к которой является сама эта
матрица. Поэтому, если
-
последовательность обратных матриц,
соответствующих итерациям 1, 2,…,i,
а
- последовательность соответствующих
им матриц, то
Последовательность подстановок приводит к следующей формуле:
(2.23)
Следует подчеркнуть, что мультипликативное представление обратной матрицы не является необходимой процедурой для реализации вычислительной схемы модифицированного симплекс-метода, и на каждой итерации можно применять любой из способов обращения текущего базиса. При использовании модифицированного симплекс-метода важно то, что обратные матрицы вычисляются способом, позволяющим уменьшить влияние машинных ошибок округления.
Шаги алгоритма модифицированного симплекс-метода, по существу, такие же, как и в алгоритме обычного симплекс-метода. После нахождения начального базиса Iопределяется соответствующий ему вектор коэффициентов целевой функции, элементы которого формируются в зависимости от того, являются ли начальные базисные переменные остаточными (избыточными) или искусственными.
При мультипликативном представлении
обратной матрицы используется операция
алгебры матриц, позволяющая вычислять
элементы матрицы, обратной к новой
матрице базисных векторов, по известной
обратной матрице предыдущего базиса
при условии, что два рассматриваемых
базиса отличаются только одним
вектор-столбцом. Такой способ представления
обратной матрицы удобно использовать
именно в вычислительной схеме
симплекс-метода, так как базисы,
соответствующие каждым двум последовательным
итерациям, отличаются лишь одним столбцом
(в результате замены исключаемого
вектор-столбца текущего базиса новым
вектор-столбцом). Другими словами,
текущая базисная матрица
и новая базисная матрица
,
соответствующая следующей итерации,
отличаются только одним столбцом. При
мультипликативном представлении
обратной матрицы
,
соответствующей новому базису, она
вычисляется путём умножения слева
обратной текущей матрицы
на формируемую по определённым правилам
матрицу.
Определим единичную матрицу следующим образом:
(2.24)
где
- единичный вектор-столбец сi-м
элементом, равным единице, и остальными
элементами, равными нулю. Допустим, что
известны матрицыи
,
и векторматрицызаменяется новым вектором;
как принято при описании симплекс-метода,
векторопределяется как включаемый в базис, а
вектор- как исключаемый из базиса. Для упрощения
записи математических соотношений
используем следующее определение
,при
этомбудет представлять собойk-й
элемент
.
Тогда новую обратную матрицу
можно вычислить по следующей формуле:
(2.25)
при условии, что
.
Если
,
матрицы
не существует. Заметим, что матрицаполучается из матрицыпутём замены еёr-го
вектор-столбцастолбцом.
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
Пермский государственный технический университет
Лысьвенский филиал
Кафедра ЕН
Курсовая работа
по дисциплине «Системный анализ и исследование операций»
по теме: «Симплекс метод в форме презентации»
Выполнил студент группы ВИВТ-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
|
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
|
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. Решение задач с помощью симплекс – метода.
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.