Решение симплекс методом задачи ЛП: пример и алгоритм

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

Понятие и алгоритм симплекс метода

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

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

Симплекс метод был предложен американским математиком Р.Данцигом в 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. Вводим добавочные неотрицательные переменные
и сводим
данную систему неравенств к эквивалентной ей системе уравнений

.

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

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

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

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

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

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

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

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

Шаг II.

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

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

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

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

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

Шаг III.

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

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

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

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

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

Шаг IV.

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

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

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

Шаг V.

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

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

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

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

Ссылка на основную публикацию