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

Здесь приведено ручное (не апплетом) решение двух задач симплекс-методом (аналогичным решению апплетом) с подробными объяснениями для того, чтобы понять алгоритм решения задач симплекс-методом. Первая задача содержит знаки неравенства только " ≤ " (задача с начальным базисом), вторая может содержить знаки " ≥ ", " ≤ " или " = " (задача с искусственным базисом), они решаются по разному.

Симплекс-метод, решение задачи с начальным базисом

1)Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений " ≤ ").

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

Эта система является системой с базисом (базис s 1 , s 2 , s 3 , каждая из них входит только в одно уравнение системы с коэффициентом 1), x 1 и x 2 - свободные переменные. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами: -система ограничений должна быть системой уравнений с базисом; -свободные члены всех уравнений в системе должны быть неотрицательны.

Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод . Составим первую симплекс-таблицу (Итерация 0) для решения задачи на симплекс-метод , т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь "БП" означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты.

симплекс-метод итерация 0

Отношение

Для улучшения решения перейдем к следующей итерации симплекс-метода , получим следующую симплекс-таблицу. Для этого надо выбрать разрешающий столбец , т.е. переменную, которая войдет в базис на следующей итерации симплекс-метода. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке (в задаче на максимум) – в начальной итерации симплекс-метода это столбец x 2 (коэффициент -6).

Затем выбирается разрешающая строка , т.е. переменная, которая выйдет из базиса на следующей итерации симплекс-метода. Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s 3 (коэффициент 20).

Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации симплекс-метода переменная x 2 заменит в базисе s 1 . Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.

Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х 2 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).

1)Вычисление строки х 2 таблицы "Итерация 1". Сначала делим все члены разрешающей строки s 3 таблицы "Итерация 0" на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x 2 в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s 3 таблицы "Итерация 0" будет совпадать со строкой х 2 таблицы "Итерация 1". Строку x 2 таблицы "Итерации 1" мы получили 0 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом:

2) Вычисление z-строки таблицы "Итерация 1". На месте -6 в первой строке (z-строке) в столбце х 2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим эту строку с первой строкой (z - строкой) таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x 2 появился ноль 0, цель достигнута. Элементы разрешающего столбца х 2 выделены красным цветом.

3) Вычисление строки s 1 таблицы "Итерация 1". На месте 1 в s 1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х 2 получен необходимый 0.

4) Вычисление строки s 2 таблицы "Итерация 1". На месте 3 в s 2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х 2 получен нужный 0. Столбец х 2 в таблице "Итерация 1" стал единичным, он содержит одну 1 и остальные 0.

Строки таблицы «Итерация 1» получаем по следующему правилу:

Новая строка = Старая строка – (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).

Например для z-строки имеем:

Старая z-строка (-4 -6 0 0 0 0) -(-6)*Новая разрешающая строка -(0 -6 0 0 -6 -120) =Новая z-строка (-4 0 0 0 6 120).

Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем.

симплекс-метод итерация 1

Отношение

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

симплекс-метод итерация 2

Отношение

Разрешающий столбец s 3 , разрешающая строка s 1 , s 1 выходит из базиса, s 3 входит в базис.

симплекс-метод итерация 3

Отношение

В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x 1 = 24, x 2 = 16, z max = 192.

Если в условии задачи есть ограничения со знаком ≥, то их можно привести к виду ∑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. Графическое решение задачи

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

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

Исходные данные задачи на симплекс-метод

Предприятие выпускает 4 вида изделий, обрабатывая их на 3-х станках.

Нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:

Фонд времени работы станков (мин.) задан в матрице B:

Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:

Цель производственной задачи

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

Решение задачи табличным симплекс-методом

(1) Обозначим X1, X2, X3, X4 планируемое количество изделий каждого вида. Тогда искомый план: (X1, X2, X3, X4 )

(2) Запишем ограничения плана в виде системы уравнений:

(3) Тогда целевая прибыль:

То есть прибыль от выполнения производственного плана должна быть максимальной.

(4) Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X5, X6, X7 ).

(5) Примем следующий опорный план :

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Занесем данные в симплекс-таблицу :

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

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

Вычислим b = Н / Элементы_выбранного_столбца

Среди вычисленных значений b выбираем наименьшее .

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

  • Сам разрешающий элемент обращается в 1.
  • Для элементов разрешающей строки – a ij (*) = a ij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные ).
  • Для элементов разрешающего столбца – они просто обнуляются.
  • Остальные элементы таблицы пересчитываем по правилу прямоугольника.

a ij (*) = a ij – (A * B / РЭ)

Как видите, мы берем текущую пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A * B ) делим на разрешающий элемент (РЭ ). И вычитаем из текущей пересчитываемой ячейки (a ij ) то, что получилось. Получаем новое значение - a ij (*) .

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

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

(10) Так как в последней строке нет отрицательных элементов, это означает, что нами найден оптимальный план производства! А именно: выпускать мы будем те изделия, которые перешли в колонку «Базис» - X1 и X2. Прибыль от производства каждой единицы продукции нам известна (матрица C ). Осталось перемножить найденные объемы выпуска изделий 1 и 2 с прибылью на 1 шт., получим итоговую (максимальную! ) прибыль при данном плане производства.

ОТВЕТ:

X1 = 32 шт., X2 = 20 шт., X3 = 0 шт., X4 = 0 шт.

P = 48 * 32 + 33 * 20 = 2 196 руб.

Галяутдинов Р.Р.


© Копирование материала допустимо только при указании прямой гиперссылки на

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

рубашка 1 рубашка 2 рубашка 3 Запасы нитки (м.) 1 9 3 96 пуговицы (шт.) 20 10 30 640 ткань ( 1 2 2 44 Прибыль (р.) 2 5 4

Решение задачи

Построение модели

Через и количество рубашек 1-го, 2-го и 3-го вида, предназначенных к выпуску.

Тогда ограничения на ресурсы будут иметь следующий вид:

Кроме того, по смыслу задачи

Целевая функция, выражающая получаемую прибыль:

Получаем следующую задачу линейного программирования:

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

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

Решение задачи симплекс-методом

Заполняем симплексную таблицу:

Так как мы решаем задачу на максимум – наличие в индексной строке отрицательных чисел при решении задачи на максимум свидетельствует о том, что нами оптимальное решение не получено и что от таблицы 0-й итерации необходимо перейти к следующей.

Переход к следующей итерации осуществляем следующим образом:

ведущий столбец соответствует

Ключевая строка определяется по минимуму соотношений свободных членов и членов ведущего столбца (симплексных отношений):

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 9.

Теперь приступаем к составлению 1-й итерации: Вместо единичного вектора вводим вектор .

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

Ключевой столбец для 1-й итерации соответствует

Разрешающим элементов является число 4/3. Вектор выводим из базиса и вводим вместо него вектор . Получаем таблицу 2-й итерации.

Ключевой столбец для 2-й итерации соответствует

Находим ключевую строку, для этого определяем:

Разрешающим элементов является число 10/3. Вектор выводим из базиса и вводим вместо него вектор . Получаем таблицу 3-й итерации.

№ БП c Б A o x 1 x 2 x 3 x 4 x 5 x 6 Симплексные 2 5 4 0 0 0 отношения 0 x 4 0 96 1 9 3 1 0 0 32/3 x 5 0 640 20 10 30 0 1 0 64 x 6 0 44 1 2 2 0 0 1 22 F j - c j 0 -2 -5 -4 0 0 0 1 x 2 5 32/3 1/9 1 1/3 1/9 0 0 32 x 5 0 1600/3 170/9 0 80/3 -10/9 1 0 20 x 6 0 68/3 7/9 0 4/3 -2/9 0 1 17 F j - c j 160/3 -13/9 0 -7/3 5/9 0 0 2 x 2 5 5 -1/12 1 0 1/6 0 -1/4 -- x 5 0 80 10/3 0 0 10/3 1 -20 24 x 3 4 17 7/12 0 1 -1/6 0 3/4 204/7 F j - c j 93 -1/12 0 0 1/6 0 7/4 3 x 2 5 7 0 1 0 1/4 1/40 -3/4 x 1 2 24 1 0 0 1 3/10 -6 x 3 4 3 0 0 1 -3/4 -7/40 17/4 F j - c j 95 0 0 0 1/4 1/40 5/4

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

Необходимо шить 24 рубашки 1-го вида, 7 рубашек 2-го вида и 3 рубашки 3-го вида. При этом получаемая прибыль будет максимальна и составит 95 руб.

Помощь в решении ваших задач по этому предмету вы можете найти, отправив сообщение в ВКонтакте , на Viber или заполнив форму . Стоимость решения домашней работы начинается от 7 бел.руб. за задачу (200 рос.руб.), но не менее 10 бел.руб. (300 рос.руб.) за весь заказ. Подробное оформление. Стоимость помощи на экзамене онлайн (в этом случае необходима 100% предоплата) - от 30 бел.руб. (1000 рос.руб.) за решение билета.

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

Исходя из этого разделения, условие задачи можно перефразировать следующим образом: экстремум целевой функции Z(X) = f(x1, x2, … ,xn) → max (min) и соответствующие переменные, если известно, что они удовлетворяют системе ограничений: Φ_i (x1, x2, … ,xn) = 0 при i = 1, 2, …, k;Φ_i (x1, x2, … ,xn)) 0 при i = k+1, k+2, …, m.

Систему ограничений нужно привести к каноническому виду, т.е. к системе линейных уравнений, где число переменных больше числа уравнений (m > k). В этой системе обязательно найдутся переменные, которые можно выразить через другие переменные, а если это не так, то их можно ввести искусственно. В этом случае первые называются базисом или искусственным базисом, а вторые – свободными.

Удобнее рассмотреть симплекс-метод на конкретном примере. Пусть дана линейная функция f(x) = 6x1 + 5x2 + 9x3 и система ограничений:5x1 + 2x2 + 3x3 ≤ 25;x1 + 6x2 + 2x3 ≤ 20;4x1 + 3x3 ≤ 18.Требуется найти максимальное значение функции f(x).

РешениеНа первом этапе задайте начальное (опорное) решение системы уравнений абсолютно произвольным образом, которое при этом должно удовлетворять данной системе ограничений. В данном случае требуется введение искусственного , т.е. базисных переменных x4, x5 и x6 следующим образом:5x1 + 2x2 + 3x3 + x4 = 25;x1 + 6x2 + 2x3 + x5 = 20;4x1 + 3x3 + x6 = 18.

Как видите, неравенства преобразовались в равенства благодаря добавленным переменные x4, x5, x6, которые являются неотрицательными величинами. Таким образом, вы привели систему к каноническому виду. Переменная x4 входит в первое уравнение с коэффициентом 1, а в два – с коэффициентом 0, то же справедливо для переменных x5, x6 и соответствующих уравнений, что соответствует определению базиса.

Вы подготовили систему и нашли начальное опорное решение – X0 = (0, 0, 0, 25, 20, 18). Теперь представьте коэффициенты переменных и свободные члены уравнений (цифры справа от знака «=») в виде таблицы для оптимизации дальнейших вычислений (см. рис).

Суть симплекс-метода состоит в том, чтобы привести эту таблицу к такому виду, в котором все цифры в строке L будут неотрицательными величинами. Если же выяснится, что это невозможно, то система вообще не имеет оптимального решения. Для начала выберите самый минимальный элемент этой строки, это -9. Цифра стоит в третьем столбце. Преобразуйте соответствующую переменную x3 в базисную. Для этого разделите строку на 3, чтобы в ячейке получилась 1.

Теперь нужно, чтобы ячейки и обратились в 0. Для этого отнимите от соответствующие цифры третьей строки, на 3. От элементов второй строки - элементы третьей, умноженные на 2. И, наконец, от элементов строки L - умноженные на (-9). Вы получили второе опорное решение: f(x) = L = 54 при x1 = (0, 0, 6, 7, 8, 0).