Решение симплекс таблиц онлайн подробно. Пример решения задачи

11.4. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

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

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

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

Рассматривая это условие с учетом двойственности, можно записать

.

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

Это позволило разработать новый метод решения задач линейного программирования, при использовании которого сначала получается недопустимое, но «лучшее, чем оптимальное» решение (в обычном симплекс-методе сначала находится допустимое , но неоптимальное решение). Новый метод, получивший название двойственного симплекс-метода , обеспечивает выполнение условия оптимальности решения и систематическое «приближение» его к области допустимых решений. Когда полученное решение оказывается допустимым, итерационный процесс вычислений заканчивается, так как это решение является и оптимальным.

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

Пример . Найти минимум функции

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

.

Перейдем к канонической форме:

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

Начальная симплекс-таблица имеет вид

Базисные переменные	x 1	x 2	x 3	x 4	x 5	Решение
x 3 x 4 x 5	–3 –4	–1 –3				–3 –6
	–2	–1

Начальное базисное решение оптимальное, но не допустимое.

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

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

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

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

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

Переменные	x 1	x 2	x 3	x 4	x 5
Уравнение x 4 -уравнение	–2 –4	–1 –3
Отношение

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

Базисные переменные	x 1	x 2	x 3	x 4	x 5	Решение
x 3 x 2 x 5						–1 –1

Новое решение также оптимальное, но все еще недопустимое. В качестве новой исключаемой переменной выберем (произвольно) x 3 . Определим включаемую переменную.

Переменные	x 1	x 2	x 3	x 4	x 5
Уравнение x 4 -уравнение
отношение

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

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

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

Перед тем, как перейти к алгоритму симплекс метода, несколько определений .

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

Пусть имеется система m ограничений с n переменными (m n).

Допустимым базисным решением является решение, содержащее m неотрицательных основных (базисных ) переменных и n - m неосновных . (небазисных, или свободных ) переменных. Неосновные переменные в базисном решении равны нулю, основные же переменные, как правило, отличны от нуля, то есть являются положительными числами.

Любые m переменных системы m линейных уравнений с n переменными называются основными , если определитель из коэффициентов при них отличен от нуля. Тогда остальные n - m переменных называются неосновными (или свободными ).

Алгоритм симплекс метода

• Шаг 1 . Привести задачу линейного программирования к канонической форме. Для этого перенести свободные члены в правые части (если среди этих свободных членов окажутся отрицательные, то соответствующее уравнение или неравенство умножить на - 1) и в каждое ограничение ввести дополнительные переменные (со знаком "плюс", если в исходном неравенстве знак "меньше или равно", и со знаком "минус", если "больше или равно").
• Шаг 2 . Если в полученной системе m уравнений, то m переменных принять за основные, выразить основные переменные через неосновные и найти соответствующее базисное решение. Если найденное базисное решение окажется допустимым, перейти к допустимому базисному решению.
• Шаг 3 . Выразить функцию цели через неосновные переменные допустимого базисного решения. Если отыскивается максимум (минимум) линейной формы и в её выражении нет неосновных переменных с отрицательными (положительными) коэффициентами, то критерий оптимальности выполнен и полученное базисное решение является оптимальным - решение окончено. Если при нахождении максимума (минимума) линейной формы в её выражении имеется одна или несколько неосновных переменных с отрицательными (положительными) коэффициентами, перейти к новому базисному решению.
• Шаг 4 . Из неосновных переменных, входящих в линейную форму с отрицательными (положительными) коэффициентами, выбирают ту, которой соответствует наибольший (по модулю) коэффициент, и переводят её в основные. Переход к шагу 2.

Важные условия

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

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

Симплекс метод с симплексными таблицами

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

Будет нелишним открыть в новом окне пособие Действия с дробями : их, дробей в задачах на симплекс-метод, мягко говоря, хватает.

Пример.

Вводим добавочные неотрицательные переменные и сводим данную систему неравенств к эквивалентной ей системе уравнений

.

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

Введённые добавочные переменные принимаем за основные (базисные). Тогда и - неосновные (свободные) переменные.

Выразив основные (базисные) переменные через неосновные (свободные), получим

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

Из коэффициентов при переменных (неизвестных) построим первую симплексную таблицу.

Таблица 1
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X1	X2
X3	-2	1	-2
X4	-4	-1	-1
X5	2	1	-1
X6	6	0	1
F	0	-1	-2

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

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

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

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

.

Поэтому ведущая строка - та, в которой записано

Ведущим элементом, таким образом, является -2.

Составляем вторую симплексную таблицу.

Новый базисный элемент вписываем первой строкой, а столбец, в котором стояло , вписываем новую свободную переменную

Заполняем первую строку. Для этого все числа, стоящие в ведущей строке таблицы 1, делим на ведущий элемент и записываем в соответствующий столбец первой строки таблицы 2, кроме числа, стоящего в ведущем столбце, куда записывается величина, обратная ведущему элементу (то есть, единица, делённая на ведущий элемент).

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

Таблица 2
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X1	X3
X2	1	-1/2	-1/2
X4	-3	-3/2	-1/2	1
X5	3	1/2	-1/2	1
X6	5	1/2	1/2	-1
F	2	-2	-1	2

Кто ещё не открыл в новом окне пособие Действия с дробями , может сделать это сейчас, поскольку самое время.

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

Например, для получения свободного члена второй строки число 1 умножаем на 1 и прибавляем из таблицы 1 число -4. Получаем -3. Коэффициент при во второй строке находим так же: . Так как в предыдущей таблице отсутствует столбец с новой свободной переменной , то коэффициент второй строки в столбце новой свободной переменной будет (то есть из таблицы 1 прибавляем 0, так как в таблице 1 столбец с отсутствует).

Так же заполняется и индексная строка:

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

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

Для поиска ведущей строки найдём минимум отношений свободных членов к элементам ведущей строки. Получаем:

.

Следовательно, ведущая строка - та, в которой записано , а ведущим элементом является -3/2.

Составляем третью симплексную таблицу

Новую базисную переменную записываем первой строкой. В столбец, в котором было , вписываем новую свободную переменную .

Первая строка:

Вспомогательные коэффициенты:

Таблица 3
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X4	X3
X1	2	-2/3	1/3
X2	2	-1/3	-1/3	1/2
X5	2	1/3	-2/3	-1/2
X6	4	1/3	1/3	-1/2
F	6	-4/3	-1/3	2

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

Для перехода к четвёртой симплексной таблице найдём наибольшее из чисел и . Это число .

Следовательно, ведущий столбец - тот, в котором записано .

Минимум модулей отношений свободных членов к элементам ведущего столбца:

.

Поэтому ведущая строка - та, в которой записано , а ведущий элемент 1/3.

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

Первая строка:

Вспомогательные коэффициенты:

Таблица 4
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X5	X3
X4	6	3	-2
X1	6	2	-1	2/3
X2	4	1	-1	1/3
X6	2	-1	1	-1/3
F	14	4	-3	4/3

Вычисление остальных строк на примере второй строки:

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

Для улучшения плана перейдём к следующей симплексной таблице.

Найдём наибольшее из чисел 4 и . Это число 4. Следовательно, ведущий столбец .

Для нахождения ведущей строки найдём

.

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

Для нахождения ведущей строки найдём

.

Следовательно, ключевая строка - та, в которой записано , а ведущий элемент 1.

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

Первая строка:

Вспомогательные коэффициенты:

Таблица 5
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X5	X6
X3	2	-1	1
X4	10			2
X1	8			1
X2	6			1
F	20	1	3	3

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

Свободные члены:

Во второй строке ;

В третьей строке ;

В четвёртой строке .

Индексная строка:

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

Симплекс метод с алгебраическими преобразованиями

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

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

Пример. Найти максимум функции при ограничениях

Шаг I. Вводим добавочные неотрицательные переменные и сводим данную систему неравенств к эквивалентной ей системе уравнений

.

Введённые добавочные переменные принимаем за основные, так как в этом случае базисное решение системы легко находится. Тогда и - неосновные переменные.

Выразив основные переменные через неосновные, получим

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

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

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

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

Для решения ЗЛП симплекс-методом ее приводят к каноническому виду, т.е. из ограничений – неравенств надо сделать ограничения – равенства. Для этого в каждое ограничение вводится дополнительная неотрицательная балансовая переменная со знаком «+», если знак неравенства «£», и со знаком «–», ели знак неравенства «³».

В целевой функции эти дополнительные переменные входят с нулевыми коэффициентами, т.е. запись целевой функции не изменится. Каждую переменную, на которую не наложено условие неотрицательности, можно представить в виде разности двух неотрицательных переменных: .

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

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

1. Составляем первый опорный план

Задача остается прежней. Приведем стандартную форму системы неравенств (1) в каноническую форму системы уравнений путем введения дополнительных балансовых переменных x 3 , x 4 , x 5 , x 6 .

В экономическом смысле значения дополнительных переменных x 3 , x 4 , x 5 определяют остатки сырья после реализации продукции.

Матрица полученной системы уравнений имеет вид:

Видно, что в матрице A базисным минором 4-го порядка является определитель, составленный из единичных коэффициентов при дополнительных переменных x 3 , x 4 , x 5 , x 6 , так как он отличен от нуля и равен 1. Это означает, что векторы-столбцы при этих переменных является линейно независимыми, т.е. образуют базис , а соответствующие им переменные x 3 , x 4 , x 5 , x 6 являются базисными (основными). Переменные x 1 , x 2 будут называться свободными (неосновными).

Если свободным переменным x 1 и x 2 задавать различные значения, то, решая систему относительно базисных переменных, получим бесконечное множество частных решений. Если свободным переменным задавать только нулевые значения, то из бесконечного множества частных решений выделяют базисные решения – опорные планы.

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

Количество базисных решений и соответствующее ему число групп базисных переменных может быть не более, чем , где n –общее число переменных, r – число базисных переменных, r ≤ m ≤ n .

Для нашей задачи r = 4; n = 6. Тогда , т.е. возможны 15 групп из 4-х базисных переменных (или 15 базисных решений).

Разрешим систему уравнений относительно базисных переменных x 3 , x 4 , x 5 , x 6:

Полагая, что свободные переменные x 1 = 0, x 2 = 0, получим значения базисных переменных: x 3 = 312; x 4 = 15; x 5 = 24; x 6 = –10, т.е. базисное решение будет = (0; 0; 312; 15; 24; –10).

Данное базисное решение является недопустимым , т.к. x 6 = –10 ≤ 0, а по условию ограничений x 6 ≥ 0. Поэтому вместо переменной x 6 в качестве базисной надо взять другую переменную из числа свободных x 1 или x 2 .

Дальнейшее решение будем выполнять, используя укороченные симплексные таблицы, заполнив строки первой таблицы коэффициентами системы следующим образом (табл. 1):

Таблица 1

F –строка называется индексной . Она заполняется коэффициентами целевой функции, взятыми с противоположными знаками, так как уравнение функции можно представить в виде F = 0 – (– 4x 1 – 3x 2).

В столбце свободных членов b i есть отрицательный элемент b 4 = –10, т.е. решение системы является недопустимым. Чтобы получить допустимое решение (опорный план), элемент b 4 надо сделать неотрицательным.

Выбираем x 6 -строку с отрицательным свободным членом. В этой строке есть отрицательные элементы. Выбираем любой из них, например, «–1» в x 1 -столбце, и x 1 -столбец принимаем в качестве разрешающего столбца (он определит, что переменная x 1 перейдет из свободных в базисные).

Делим свободные члены b i на соответствующие элементы a is разрешающего столбца, получаем оценочные отношения Θ i = = {24, 15, 12, 10}. Из них выбираем наименьшее положительное (minΘ i =10), которое будет соответствовать разрешающей строке . Разрешающая строка определяет переменную x j , которая на следующем шаге выступает из базиса и станет свободной. Поэтому x 6 -строка является разрешающей строкой, а элемент «–1» – разрешающим элементом . Обводим его кружком. Переменные x 1 и x 6 меняются местами.

Оценочные отношения Θ i в каждой строке определяются по правилам:

1) Θ i = , если b i и a is имеют разные знаки;

2) Θ i = ∞, если b i = 0 и a is < 0;

3) Θ i = ∞, если a is = 0;

4) Θ i = 0, если b i = 0 и a is > 0;

5) Θ i = , если b i и a is имеют одинаковые знаки.

Совершаем шаг модифицированного жорданова исключения (ШМЖИ) с разрешающим элементом и составляем новую таблицу (табл. 2) по следующему правилу:

1) на месте разрешающего элемента (РЭ) устанавливается величина, ему обратная, т.е. ;

2) элементы разрешающей строки делятся на РЭ;

3) элементы разрешающего столбца делятся на РЭ и знак меняется;

4) остальные элементы находятся по правилу прямоугольника:

Из табл. 2 видно, что свободные члены в b i -столбце являются неотрицательными, следовательно, получено первоначальное допустимое решение – первый опорный план = (10; 0; 182; 5; 4; 0). При этом значение функции F () = 40. Геометрически это соответствует вершине F (10; 0) многоугольника решений (рис. 1).

Таблица 2

2. Проверяем план на оптимальность. Опорный план не оптимальный, так как в F -строке имеется отрицательный коэффициент «–4». Улучшаем план.

3. Нахождение нового опорного плана

Выбираем разрешающий элемент по правилу:

Выбираем наименьший отрицательный коэффициент в F -строке «–4», который и определяет разрешающий столбец – x 6 ; переменную x 6 переводим в базисные;

Находим отношения Θ i , среди них выбираем наименьшее положительное, которое соответствует разрешающей строке:

min Θ i = min {14, 5, 2, ∞} = 2, следовательно, x 5 -строка – разрешающая, переменную x 5 переводим в свободные (переменные x 5 и x 6 меняются местами).

На пересечении разрешающих строки и столбца стоит разрешающий элемент «2»;

Выполняем шаг ШМЖИ, строим табл. 3 по вышеприведенному правилу и получаем новый опорный план = (12; 0; 156; 3; 0; 2).

Таблица 3

4. Проверка нового опорного плана на оптимальность

Опорный план также не является оптимальным, так как в F -строке имеется отрицательный коэффициент «–1». Значение функции F () = 48, что геометрически соответствует вершине E (12; 0) многоугольника решений (рис. 1). Улучшаем план.

5. Нахождение нового опорного плана

x 2 -столбец – разрешающий, так как в F -строке наименьший отрицательный коэффициент «–1» находится в x 2 -столбце (Δ 2 = –1). Находим наименьшее Θ i : min Θ i = min {≈ 9, 6, ∞, 24} = 6, следовательно, x 4 -строка – разрешающая. Разрешающий элемент «1/2». Меняем местами переменные x 2 и x 4 . Выполняем шаг ШМЖИ, строим табл. 4, получаем новый опорный план = (9; 6; 51; 0; 0; 5).

6. Проверка опорного плана на оптимальность

В F -строке все коэффициенты неотрицательны, следовательно, опорный план является оптимальным. Геометрически соответствует точке D (9;6) (см. рис. 1). Оптимальный план дает максимальное значение целевой функции у.е.

Основная идея симплексного метода решения ЗЛП состоит в последовательном улучшении опорных решений ЗЛП.

Существуют несколько форм записи симплексного метода.

1. Базовая форма записи симплекс-метода;
2. Симплекс-метод в виде симплексной таблицы;
3. Модифицированный симплекс-метод;
4. Симплекс-метод в столбцовой форме;
5. Симплексный метод в строчечной форме.

Определим максимальное значение целевой функции F(X) = 3x 1 +5x 2 +4x 3 при следующих условиях-ограничений.
0.1x 1 +0.2x 2 +0.4x 3 ≤1100
0.05x 1 +0.02x 2 +0.02x 3 ≤120
3x 1 +x 2 +2x 3 ≤8000

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
0.1x 1 + 0.2x 2 + 0.4x 3 + 1x 4 + 0x 5 + 0x 6 = 1100
0.05x 1 + 0.02x 2 + 0.02x 3 + 0x 4 + 1x 5 + 0x 6 = 120
3x 1 + 1x 2 + 2x 3 + 0x 4 + 0x 5 + 1x 6 = 8000

Базовая форма записи симплекс-метода

Решение ведется путем выражения базисных переменных через небазисные: x 0 = 3x 1 +5x 2 +4x 3 x 4 = 1100-0.1x 1 -0.2x 2 -0.4x 3 x 5 = 120-0.05x 1 -0.02x 2 -0.02x 3 x 6 = 8000-3x 1 -x 2 -2x 3

Симплекс-метод в виде симплексной таблицы

Решение ведется в виде симплексной таблицы. Форма разработана для вычислений на ЭВМ. При использовании искусственного базиса используется специальное число М (обычно 10000).

План	Базис	В	x 1	x 2	x 3	x 4	x 5	x 6	min
1	x4	1100	0.1	0.2	0.4	1	0	0	5500
	x5	120	0.05	0.02	0.02	0	1	0	6000
	x6	8000	3	1	2	0	0	1	8000
Индексная строка	F(X1)	0	-3	-5	-4	0	0	0	0
2	x2	5500	0.5	1	2	5	0	0	11000
	x5	10	0.04	0	-0.02	-0.1	1	0	250
	x6	2500	2.5	0	0	-5	0	1	1000
Индексная строка	F(X2)	27500	-0.5	0	6	25	0	0	0
3	x2	5375	0	1	2.25	6.25	-12.5	0	11000
	x1	250	1	0	-0.5	-2.5	25	0	250
	x6	1875	0	0	1.25	1.25	-62.5	1	1000
Индексная строка	F(X3)	27625	0	0	5.75	23.75	12.5	0	0

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

Матрица коэффициентов A = a ij Матрица b. Итерация №1 . = (4, 5, 6) Матрица c. c = (-3, -5, -4, 0, 0, 0) c B = (0, 0, 0) c N = (-3, -5, -4) Вычисляем: Матрицу B -1 вычисляем через алгебраические дополнения. u = c B B -1 = (0, 0, 0)

Симплекс-метод в столбцовой форме

Переходим к столбцовой форме симплекс-метода. Выразим каждую переменную через небазисные. x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0.1(-x 1)+0.2(-x 2)+0.4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0.05(-x 1)+0.02(-x 2)+0.02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) Данной системе соответствует таблица T 0 . 0 -1 0 0 0 0 -1 0 0 0 0 -1 1100 0.1 0.2 0.4 120 0.05 0.02 0.02 8000 3 1 2 0 -3 -5 -4

Симплексный метод в строчечной форме

В качестве начальной допустимой базы можно взять B 0 = <4, 5, 6>. Ей будет соответствовать следующая таблица. 1100 0.1 0.2 0.4 1 0 0 120 0.05 0.02 0.02 0 1 0 8000 3 1 2 0 0 1 0 -3 -5 -4 0 0 0

Матрица Q, составленная из коэффициентов системы, называется симплекс-таблицей , соответствующей базе В. Симплекс-таблица называется допустимой , или прямо допустимой , если q i0 ≥ 0. Элементы q i0 последней строки симплекс-таблицы Q называются относительными оценками .

Формы решения методом искусственного базиса

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

Формы решения методом искусственного базиса:

1. M-метод (симплекс-таблица);
2. двухэтапный или двухфазный симплекс-метод (Базовая форма записи, Модифицированный симплекс-метод, Симплекс-метод в столбцовой форме, Симплексный метод в строчечной форме).

Если в условии задачи есть ограничения со знаком ≥, то их можно привести к виду ∑a ji b j , умножив обе части неравенства на -1. Введем m дополнительных переменных x n+j ≥0(j =1,m ) и преобразуем ограничения к виду равенств

(2)

Предположим, что все исходные переменные задачи x 1 , x 2 ,..., x n – небазисные. Тогда дополнительные переменные будут базисными, и частное решение системы ограничений имеет вид

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)

Так как при этом значение функции цели F 0 = 0 , можно представить F(x) следующим образом:

F(x)=∑c i x i +F 0 =0 (4)

Начальная симплекс-таблица (симплекс-табл. 1) составляется на основании уравнений (2) и (4). Если перед дополнительными переменными x n+j стоит знак «+», как в (2), то все коэффициенты перед переменными x i и свободный член b j заносятся в симплекс-таблицу без изменения. Коэффициенты функции цели при ее максимизации заносятся в нижнюю строку симплекс-таблицы с противоположными знаками. Свободные члены в симплекс-таблице определяют решение задачи.

Алгоритм решения задачи следующий:

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

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

Таблица 1.

x n

базисные переменные	Свободные члены в ограничениях	Небазисные переменные
		x 1	x 2	...	x l	...
x n+1	b 1	a 11	a 12	...	a 1l	...	a 1n
x n+2	b 2	a 21	a 22	...	a 2l	...	a 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+r	b2	a r1	a r2	...	a rl	...	a rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+m	b m	a m1	a m2	...	a ml	...	a mn
F(x) max	F 0	-c 1	-c 2	...	-c 1	...	-c n

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

Одновременно из БП исключается та переменная, которая первой изменит знак при увеличении выбранной НП x l . Это будет x n+r , индекс r которой определяется из условия

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

Строка, соответствующая переменной x n+r , называется ведущей, или разрешающей. Элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим, или разрешающим элементом. Нахождением ведущего элемента заканчивается работа с каждой очередной симплекс-таблицей.

3-й шаг. Рассчитывается новая симплекс-таблица, элементы которой пересчитываются из элементов симплекс-таблицы предыдущего шага и помечаются штрихом, т.е. b" j , a" ji , c" i , F" 0 . Пересчет элементов производится по следующим формулам:

Сначала в новой симплекс-таблице заполнятся строка и столбец, которые в предыдущей симплекс-таблице были ведущими. Выражение (5) означает, что элемент a" rl на месте ведущего равен обратной величине элемента предыдущей симплекс-таблицы. Элементы строки a ri делятся на ведущий элемент, а элементы столбца a jl также делятся на ведущий элемент, но берутся с противоположным знаком. Элементы b" r и c" l рассчитываются по тому же принципу.

Остальные формулы легко записать с помощью .

Прямоугольник строится по старой симплекс-таблице таким образом, что одну из его диагоналей образует пересчитываемый (a ji) и ведущий (a rl) элементы (рис. 1). Вторая диагональ определяется однозначно. Для нахождения нового элемента a" ji из элемента a ji вычитается (на это указывает знак « – » у клетки) произведение элементов противоположной диагонали, деленное на ведущий элемент. Аналогично пересчитываются элементы b" j , (j≠r) и c" i , (i≠l).

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

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

Рис. 1. Правило прямоугольника

Если среди коэффициентов F-строки имеются отрицательные (за исключением свободного члена), то нужно переходить к другому базисному решению. При максимизации функции цели в базис включается та из небазисных переменных (например x l), столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента c l в нижней строке симплекс-таблицы. Это позволяет выбрать ту переменную, увеличение которой приводит к улучшению функции цели. Столбец, соответствующий переменной x l , называется ведущим. Одновременно из базиса исключается та переменная x n+r , индекс r которой определяется минимальным симплексным отношением:

Строка, соответствующая x n+r , называется ведущей , а элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим элементом.

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

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

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

Пример 1. Решить задачу

max{F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0}

Симплексным методом и дать геометрическую интерпретацию процесса решения.

Графическая интерпретация решения задачи представлена на рис. 2. Максимальное значение функции цели достигается в вершине ОДЗП с координатами . Решим задачу с помощью симплекс-таблиц. Умножим второе ограничение на (-1) и введём дополнительные переменные, чтобы неравенства привести к виду равенств, тогда

Исходные переменные x 1 и x 2 принимаем в качестве небазисных, а дополнительные x 3 , x 4 и x 5 считаем базисными и составляем симплекс-таблицу(симплекс-табл. 2). Решение, соответствующее симплекс-табл. 2, не является допустимым; ведущий элемент обведен контуром и выбран в соответствии с шагом 2 приведенного ранее алгоритма. Следующая симплекс-табл. 3 определяет допустимое базисное решение, ему соответствует вершина ОДЗП на рис. 2 Ведущий элемент обведен контуром и выбран в соответствии с 5-м шагом алгоритма решения задачи. Табл. 4 соответствует оптимальному решению задачи, следовательно: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.

Рис. 2. Графическое решение задачи