Для решения задач линейного программирования существует множество методов. Рассмотрим один из них улучшенный (модифицированный) симплекс-метод
Для начала расскажем, что такое симплекс-метод. Слово SIMPLEX в обычном смысле означает простой, несоставной, в противоположность слову COMPLEX.
Данный метод получил несколько различных форм (модификаций) и был разработан в 1947 году Г. Данцигом.
Сущность симплекс-метода заключается в том, что если число неизвестных больше числа уравнений, то данная система неопределенная с бесчисленным множеством решений. Для решения системы все неизвестные произвольно подразделяют на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придают произвольные значения и подставляют в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.
В теории линейного программирования существует теорема, которая утверждает, что среди базисных решений системы можно найти оптимальное, а в некоторых случаях и несколько оптимальных решений, но все они обеспечат экстремум целевой функции. Таким образом, если найти какой-либо базисный план, а затем улучшить его, то получится оптимальное решение. На этом принципе и построен симплекс-метод.
Одним из модификаций симплекс-метода является улучшенный симплекс-метод. В литературе этот метод встречается также под названием метода обратной матрицы или модифицированного симплекс-метода.
При решении задач линейного программирования, в которых n (количество переменных) существенно больше m (количество ограничений), улучшенный симплекс-метод требует по сравнению с другими значительно меньшего количества вычислительных операций и объема памяти ЭВМ.
В улучшенном симплекс-методе реализуется та же основная идея, что и в обычном симплекс-методе, но здесь на каждой итерации пересчитывается не вся матрица A -1 , обратная матрице ограничений A, а лишь та часть, которая относится к текущему базису A x .
Рассмотрим поэтапно шаги решения задачи линейного программирования улучшенным симплекс-методом:
j = c j -- = c j -- P j , (2)
где - двойственные переменные, которые можно найти следующим образом:
где c x - вектор коэффициентов целевой функции при базисных переменных.
3. Предполагая, что используется стандартное правило выбора вводимого столбца, находим:
= (, ...,) . (2.4)
Если все 0 - процедура останавливается: оптимум неограничен.
7. В противном случае находим выводимую из базиса переменную:
8. Строим увеличенную матрицу:
и трансформируем ее с ведущим элементом. Первые m столбцов дают матрицу, обратную новому базису.
9. Преобразуем базисное решение:
x b i x b i -- * , i r, (2.7)
и переходим к этапу 2.
Этот вариант называют также модифицированным симплекс-методом, поскольку он уменьшает объем вычислений на каждом шаге. Идея заключается в том, что на каждом шаге каноническую форму задачи для текущего базиса можно получить независимо от других таких форм непосредственно из исходной записи стандартной задачи ЛП.
Для этого нужно:
Улучшенный симплекс-метод, обладает значительными преимуществами по сравнению со стандартной формой. Это относится к точности, скорости и требованиям к памяти. Большая часть этих преимуществ определяется тем фактором, что, как правило, матрицы больших линейных задач (то есть с n>m>100) являются слабо заполненными, содержат малый процент ненулевых элементов.
Обычной является плотность 5% или менее. Улучшенная форма симплекс-метода в большей степени способна использовать преимущества, вытекающие из этого факта. В этой форме характеристические разности и ведущий вектор вычисляются непосредственно по исходным данным. Поскольку исходная матрица слабо заполнена, а перемножение следует производить только тогда, когда оба сомножителя отличны от нуля, то время вычислений значительно сокращается.
В дополнение к этому использование только исходных данных приводит к тому, что уменьшается возможность накопления ошибок округления. Наоборот, стандартные симплексные таблицы, даже если они первоначально являются слабо заполненными, в ходе итеративного процесса быстро заполняются ненулевыми элементами. Таким образом, время вычислений увеличивается, и, поскольку каждая таблица вычисляется из предшествующей, накопление ошибок может начать играть более серьезную роль.
Поясним вычисления 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 - равным единице.
Важно заметить, что для симплекс-метода в матричной форме итерация симплекс-метода эквивалентна умножению матричного уравнения слева на следующую квадратную матрицу:
|
В случае если все столбцы матрицы 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
МОДИФИЦИРОВАННЫЙ СИМПЛЕКС МЕТОДСимплекс-метод – не самая эффективная
компьютерная процедура, так как она вычисляет и
хранит информацию, которая не нужна для текущей
итерации и может вообще не использоваться для
принятия решений при последующих итерациях. Для
коэффициентов неосновных переменных в уравнении
(0), коэффициентов введенных основных переменных
в других уравнениях и правых частях уравнений при
каждой итерации используется только релевантная
информация. Поэтому нужна процедура, которая
может получать эту информацию эффективно, без
вычислений и хранения всех других коэффициентов
(это и есть модифицированный симплекс-метод).
С учетом возможностей современных ППП, использующих модифицированный симплекс-метод с мультипликативным представлением матрицы, отнесение очередного вектора к классу векторов, обеспечивающих совместность или несовместность, требует проведения всего нескольких итераций после модификации обобщенной матрицы
МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД
Вычислительная схема, основанная на преобразовании обратных матриц. Анализируя вычислительную процедуру симплекс-метода с позиций оценки трудоемкости, нетрудно заметить, что наиболее критичным в этом плане является э ап пересчета значений А и b при переходе от одного базисного плана к другому (п. 3 алгоритма). Однако в том случае, когда число ограничений задачи m явно меньше количества переменных я, можно добиться существенной экономии, выполняя на очередной итерации q преобразование Жордана-Гаусса не над матрицей Л(р() по Д Чр(ведущий столбец аЧр О. Данные соображения положены в основу вычислительной схемы симплекс-метода , основанной на преобразовании обратных матриц, которую также называют модифицированным симплекс-методом. Впервые данный алгоритм был предложен в 1951 г. в работах Л. В. Канторовича.
Вычислительной схеме модифицированного симплекс-метода соответствует система таблиц 7] и T q). Таблица 7J (рис. 1.7) является общей для всех итераций и служит для получения
По аналогии с п. 1.4.1 опишем формальную схему алгоритма модифицированного симплекс-метода.
В завершение подчеркнем, что в силу приведенных выше преимуществ именно модифицированный симплекс-метод реально применяется в программном обеспечении , предназначенном для решения канонических задач линейного программирования.
Пример решения ЗЛП модифицированным симплекс-методом. Приведем решение рассмотренной ранее задачи (1.34)-(1.35), основанное на использовании процедуры модифицированного симплекс-метода. По аналогии с п. 1.4.3
Еще раз вернемся к таблице Т (рис. 1.8), получаемой на финальной итерации процедуры модифицированного симплекс--метода. Более подробно рассмотрим нулевую строку матрицы A 4p(
Таким образом, существенным преимуществом модифицированного симплекс-метода является то, что он позволяет одновременно найти оптимальные планы как прямой, так и двойственной задачи.
В заключение отметим, что в настоящем параграфе был рассмотрен вариант двойственного алгоритма, соответствующий стандартному симплекс-методу . Нетрудно догадаться, что существует и вариант, построенный на базе модифицированного симплекса (схемы, связанной с преобразованием обратных матриц), но, поскольку этот вопрос представляет интерес в основном с точки зрения техники организации вычислений, мы на нем останавливаться не будем. При желании с глубоким и детальным описанием данной версии алгоритма можно ознакомиться в . Отметим лишь, что она обладает теми же принципиальными преимуществами, что и модифицированный симплекс-метод.
Модифицированный симплекс-метод - вычислительная схема, связанная с преобразованием обратных матриц.
Сформулируйте основные отличия модифицированного симплекс-метода по отношению к стандартному.
Перечислите преимущества модифицированного симплекс-метода.
Будет ли отличаться количество итераций при решении одной и той же задачи при решении ее стандартным и модифицированным симплекс-методом
Метод разложения (декомпозиции) был разработан для решения задач линейного программирования большой размерности, имеющих блочную структуру. Его вычислительная процедура главным образом основана на идеях модифицированного симплекс-метода. Однако значение метода Данцига-Вулфа состоит не только и (не столько) в его вычислительных преимуществах, сколько в возможности дать содержательную экономическую интерпретацию . Метод предусматривает разложение исходной задачи (5.6)-(5.9) на локальные задачи, соответствующие обособленным частям объединения (в данном случае предприятиям), и главную задачу (соответствует объединению в целом и связывает эти локальные задачи).
Р. Б. Д у б и н а, К. Е. Ч е р н и н. Программа образования и записи на М. Б. матрицы для модифицированного симплекс-метода.- Сборник программ для ЭВМ Урал. Л., Аркт. и антаркт. ин-т, 1966.
Среди методов нахождения оптимального решения наибольшее распространение приобрёл метод последо -ват. улучшения допустимого решения (МНУ), к-рый имеет большое число вычислит, реализаций (
В модифицированном методе матрица
не пересчитывается, хранится и пересчитывается только матрица. В остальном алгоритм похож на вышеописанный.
1. Вычисляем двойственные переменные
2. Проверка оптимальности. преобразуется в.
Проверка заключается в вычислении для всех столбцов. Столбец со значением < 0 можно вводить в базис.
Часто выбирают минимальное значение, но для этого нужно перебрать все столбцы.
Чаще выбирают значение, меньшее некоторого заданного значения
Если такого столбца не обнаружится, за принимается максимальное найденное абсолютное значение и соответствующий столбец вводится в базис.
3. Определение выводимого.
Пусть - вводимый столбец, соответствующий переменной Базиный план - это решение системы Увеличиваем.
Умножим слева на, т.е.
Здесь - базисный план, - разложение вводимого столбца по базису.
Находим максимальное значение, при котором все значения не отрицательны. Если может быть взято как угодно велико, решение не ограничено. В противном случае один из элементов выйдет на нулевое значение. Выводим соответствующий столбец из базиса.
4. Пересчет опорного(базисного) плана.
Вычисляем новый опорный план по уже приведенной формуле с найденным значением.
5. Пересчитываем обратную к базисной.
Пусть - выводимый столбец.
Матрица B представима в виде
где - базисная матрица без выводимого столбца.
После замены столбца базисная матрица будет иметь вид
Нам нужно найти матрицу, такую что
Замечание.
При пересчете матрицы накапливаются ошибки округления. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется «повторением».
Мультипликативный вариант симплекс-метода
В мультипликативном варианте матрица не хранится, хранятся лишь множители
При решении экономических задач часто матрица ограничений разреженная, в таком случае мультипликативный вариант получает дополнительные преимущества - можно хранить мультипликаторы в сжатом виде (не хранить нули).
Во избежание накопления ошибок округления может использоваться LU-разложение матрицы.
При подавляющем числе ограничений типа «неравенство» может быть использован метод переменного базиса .
Метод основан на том, что базисная матрица может быть представлена в виде
Обратная к ней имеет вид
При относительно небольших размерах матрицы остальная часть матрицы может не храниться.
Таким подходом удается решить задачи с десятками миллионов строк ограничений (например, из теории игр).
Двойственный симплекс-метод
Для реализации двойственного метода необходимо перейти от задачи на минимум к задаче на максимум (или наоборот) путем транспонирования матрицы коэффициентов. При переходе от задачи на минимум целевая функция примет вид:
при ограничениях
Теорема двойственности . Если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем экстремальные значения линейных функций этих задач равны.
Если линейная функция одной из задач не ограничена, то другая не имеет решения.