Модифицированный симплекс-метод решения задач линейного программирования. Модифицированный симплексный метод
Основная идея модифицированного
симплекс-метода заключается в использовании
текущей обратной матрицы
(и исходных данных задачи) при выполнении
вычислений, необходимых для определения
включаемой и исключаемой переменных.
Представление обратной матрицы в
мультипликативной форме позволяет
вычислять последовательность обратных
матриц непосредственно по исходным
данным без использования многократных
операций обращения каждого базиса. Как
и в обычном симплекс-методе, в данном
случае исходный базис всегда представляет
собой единичную матрицуI,
обратной к которой является сама эта
матрица. Поэтому, если-
последовательность обратных матриц,
соответствующих итерациям 1, 2,…,i,
а
- последовательность соответствующих
им матриц, то
Последовательность подстановок приводит к следующей формуле:
(2.23)
Следует подчеркнуть, что мультипликативное представление обратной матрицы не является необходимой процедурой для реализации вычислительной схемы модифицированного симплекс-метода, и на каждой итерации можно применять любой из способов обращения текущего базиса. При использовании модифицированного симплекс-метода важно то, что обратные матрицы вычисляются способом, позволяющим уменьшить влияние машинных ошибок округления.
Шаги алгоритма модифицированного
симплекс-метода, по существу, такие же,
как и в алгоритме обычного симплекс-метода.
После нахождения начального базиса Iопределяется соответствующий ему вектор
коэффициентов целевой функции,
элементы которого формируются в
зависимости от того, являются ли начальные
базисные переменные остаточными
(избыточными) или искусственными.
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.
Задачей оптимизации в математике называется задача о нахождении экстремума вещественной функции в некоторой области. Как правило, рассматриваются области, принадлежащие и заданные набором равенств и неравенств.
3.1. Описание
Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.
Каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным конусом.
Уравнение W(x) = c, где W(x) – максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. При этом экстремальная задача приобретает следующую формулировку: требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причем их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.
Сущность симплекс-метода состоит в том, что если число неизвестных больше числа уравнений, то данная система неопределенная с бесчисленным множеством решений. Для решения системы все неизвестные произвольно подразделяются на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придаются произвольные значения и затем подставляются в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.
В теории линейного программирования существует теорема, которая утверждает, что среди базисных решений системы можно найти оптимальное, а в некоторых случаях – несколько оптимальных решений, причем все они обеспечат экстремум целевой функции. Таким образом, если найти какой-то базисный план и затем улучшить его, то получится оптимальное решение. На этом принципе построен симплекс-метод.
Последовательность вычислений симплекс-методом можно разделить на две основные фазы:
1. нахождение исходной вершины множества допустимых решений;
2. последовательный переход от вершины к вершине, ведущий к оптимизации значения целевой функции.
В некоторых случаях исходное решение очевидно или его определение не требует сложных вычислений, – например, когда все ограничения представлены неравенствами вида «меньше или равно» (тогда нулевой вектор совершенно точно есть допустимое решение, хотя, скорее всего, далеко не оптимальное). В таких задачах первую фазу симплекс-метода можно вообще не проводить. Симплекс-метод соответственно делится на однофазный и
двухфазный .
3.2. Алгоритм симплекс-метода
Усиленная постановка задачи
Рассмотрим следующую задачу линейного программирования:
Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:
Здесь x – переменные из исходного линейного функционала; x s – новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство; c – коэффициенты исходного линейного функционала; Z – переменная, которую необходимо максимизировать. Полупространства и в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт число степеней свободы. Проще говоря, если рассматривать вершину многогранника, это есть число рёбер, по которым можно продолжать движение.
Тогда можно присвоить такому числу переменных значение 0 и назвать
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Предупреждение
Очистить все ячейки?
Закрыть Очистить
Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.
Симплекс метод
Примеры решения ЗЛП симплекс методом
Пример 1. Решить следующую задачу линейного программирования:
![]() |
Правая часть ограничений системы уравнений имеет вид:
Запишем текущий опорный план:
![]() |
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x
при
. min
(40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x
3 . Сделаем исключение Гаусса для столбца x
2 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x
1 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при
. min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x
4 . Сделаем исключение Гаусса для столбца x
1 , учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Текущий опорный план является оптимальным, так как в строках 4 под переменными нет отрицательных элементов.
Решение можно записать так: .
Значение целевой функции в данной точке: F
(X
)=.
Пример 2. Найти максимум функции
Р е ш е н и е.
Базисные векторы x 4 , x 3 , следовательно, все элементы в столбцах x 4 , x 3 , ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x 3 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.
Симплекс таблица примет вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x
2 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при
. Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.
Примеры решения ЗЛП методом искусственного базиса
Пример 1. Найти максимум функции
Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:
![]() |
Матрица коэффициентов системы уравнений имеет вид:
Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.
Симплекс таблица примет вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-5), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при
соответствует строке 3. Из базиса выходит вектор Сделаем исключение Гаусса для столбца учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при
соответствует строке 1. Из базиса выходит вектор x
2 . Сделаем исключение Гаусса для столбца x
1 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x
3 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при
соответствует строке 3. Из базиса выходит вектор x
5 . Сделаем исключение Гаусса для столбца x
3 , учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.
Решение исходной задачи можно записать так:
Пример 2. Найти оптимальный план задачи линейного программирования:
Матрица коэффициентов системы уравнений имеет вид:
Базисные векторы x 4 , x 5 , x 6 , следовательно, все элементы в столбцах x 4 , x 5 , x 6 , ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x 5 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x 6 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.
Симплекс таблица примет вид:
В строке 5 элементы, соответствующие переменным x 1 , x 2 , x 3 , x 4 , x 5 , x 6 неотрицательны, а число находящийся в пересечении данной строки и столбца x 0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.
Поясним вычисления a i , j ¢ с использованием “правила прямоугольника“. Необходимо взять разрешающий элемент a k , s и мысленно соединить его с тем коэффициентом, новое значение которого требуется найти. Эту прямую следует считать главной диагональю, на ней строится прямоугольник, сторонами которого являются строки и столбцы. В прямоугольнике нужно провести побочную диагональ, тогда значение нового коэффициента будет равно его исходному значению, из которого вычитается произведение элементов, стоящих на побочной диагонали, поделенному на разрешающий элемент. Поясним эти действия на схеме (рис. 1.9). Прежде чем заполнить симплекс-таблицу исходные уравнения следует представить в виде (1.21).![]() |
|||||
|
|||||
|
|||||
Суть преобразований симплекс-метода рассмотрим на примере 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 - равным единице.
Важно заметить, что для симплекс-метода в матричной форме итерация симплекс-метода эквивалентна умножению матричного уравнения слева на следующую квадратную матрицу:
|
![](https://i2.wp.com/referatwork.ru/image.php?way=oplibru/baza3/43581743899.files/image454.png)
В случае если все столбцы матрицы 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