"Чистая"
и прикладная математика

СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ: ТИПИЧНЫЙ ПРИМЕР И АЛГОРИТМ

Идея симплекс-метода

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

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

Алгоритм для алгебраических преобразований в симплекс-методе

Идея симплекс-метода

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

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

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

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

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

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

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

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

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

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

Таким образом, применение симплекс-метода распадается на два этапа:

1) нахождение допустимого базисного решения системы ограничений;

2) нахождение оптимального решения.

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

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

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

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

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

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

Решение.

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

.

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

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

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

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

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

Таблица 1
Базисные неизвестныеСвободные членыСвободные неизвестныеВспомогательные коэффициенты
X1X2
X3-21-2
X4-4-1-1
X521-1
X6601
F0-1-2

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

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

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

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

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

Итак,

.

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

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

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

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

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

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

Таблица 2
Базисные неизвестныеСвободные членыСвободные неизвестныеВспомогательные коэффициенты
X1X3
X21-1/2-1/2
X4-3-3/2-1/21
X531/2-1/21
X651/21/2-1
F2-2-12

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

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

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

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

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

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

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

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

.

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

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

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

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

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

Таблица 3
Базисные неизвестныеСвободные членыСвободные неизвестныеВспомогательные коэффициенты
X4X3
X12-2/31/3
X22-1/3-1/31/2
X521/3-2/3-1/2
X641/31/3-1/2
F6-4/3-1/32

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

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

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

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

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

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

.

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

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

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

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

.

Таблица 4
Базисные неизвестныеСвободные членыСвободные неизвестныеВспомогательные коэффициенты
X5X3
X463-2
X162-12/3
X241-11/3
X62-11-1/3
F144-34/3

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

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

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

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

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

.

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

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

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

.

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

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

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

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

.

Таблица 5
Базисные неизвестныеСвободные членыСвободные неизвестныеВспомогательные коэффициенты
X5X6
X32-11
X4102
X181
X261
F20133

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

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

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

- в третьей строке ;

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

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

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

Ответ:

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

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

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

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

Решение.

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

.

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

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

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

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

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

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

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

Шаг II (соответствует пункту 4 алгоритма симплекс-метода).

Основные переменные , неосновные переменные .

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

Следовательно, имеем новое базисное решение , которое также является недопустимым, а поэтому не оптимальным. Но в нём, как мы и предвидели, только одна переменная отрицательна (а именно ).

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

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

Шаг III (соответствует пунктам 5-6 алгоритма симплекс-метода).

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

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

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

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

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

Шаг IV (соответствует пунктам 7-8 алгоритма симплекс-метода).

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

Линейная форма, выраженная через те же неосновные переменные, примет вид . Продолжим перебор для поиска максимума.

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

Шаг V (соответствует пунктам 9-11 алгоритма симплекс-метода).

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

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

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

Алгоритм для алгебраических преобразований в симплекс-методе

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


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


3. В данной или полученной после выполнения п. 2 этого алгоритма системе m уравнений с n переменными (m < n) m переменных принимают за основные. Основными могут быть любые m переменных, коэффициенты при которых образуют отличный от нуля определитель. Проще всего в качестве основных взять добавочные переменные (в этом случае отпадает необходимость вычислять определитель, который заведомо отличен от нуля, так как каждая добавочная переменная входит только в одно из уравнений системы ограничений).

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

Если найденное базисное решение окажется допустимым, то переходят к п. 5 этого алгоритма, если же оно окажется недопустимым, то предварительно выполняют п. 4 этого алгоритма.


4. От полученного недопустимого базисного решения переходят к допустимому базисному решению или устанавливают, что система ограничений данной задачи противоречива. В отдельной статье разобран случай, когда система не имеет ни одного решения.


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


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

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


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


8. Выражают новые основные переменные и линейную форму через неосновные переменные (это начинают делать с выделенного уравнения).


9. Повторяют пункты 6-8 этого алгоритма до тех пор, пока не будет достигунт критерий оптимальности (см. п. 5 этого алгоритма). После этого выписывают компоненты оптимального решения и находят оптимум (максимум или минимум) линейной формы.


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


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

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

Нет времени вникать в решение? Можно заказать работу!

Начало темы "Линейное программирование"

Задача и теоремы линейного программирования, примеры формулировки задач

Графический метод решения задач линейного программирования

Пример задачи линейного программирования: задача использования ресурсов, её графическое решение

Продолжение темы "Линейное программирование"

Симплекс-метод: случай, когда максимум целевой функции - бесконечность

Симплекс-метод: случай, когда система не имеет ни одного решения

Симплекс-метод: случай, когда оптимальное решение - не единственное

Поделиться с друзьями