Симплексный метод пример. Решение злп симплекс-методом

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

Как осуществляется переход от одного базиса к другому?
Запись решения удобнее вести в виде таблиц. Каждая строка эквивалентна уравнению системы. Выделенная строка состоит из коэффициентов функции (сравните сами). Это позволяет не переписывать переменные каждый раз, что существенно экономит время.
B выделенной строке выбираем наибольший положительный коэффициент. Это необходимо для того, чтобы получить значение функции, как минимум, не меньше имеющегося.
Выбран столбец.
Для положительных коэффициентов выбранного столбца считаем отношение Θ и выбираем наименьшее значение. Это необходимо для того, чтобы после преобразования столбец свободных членов остался положительным.
Выбрана строка.
Следовательно, определен элемент, который будет базисным. Далее считаем.

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

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

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.

Шаг 0. Подготовительный этап.

Приводим задачу ЛП к специальной форме (15).

Шаг 1. Составляем симплекс-таблицу , соответствующую специальной форме:

Заметим, что этой таблице соответствует допустимое базисное решение
задачи (15). Значение целевой функции на этом решении

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

Если среди элементов индексной строки симплекс – таблицы
нет ни одного положительного элемента то
, оптимальное решение задачи ЛП найдено:. Алгоритм завершает работу.

Шаг 3. Проверка на неразрешимость

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

Шаг 4. Выбор ведущего столбца q

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

Шаг 5. Выбор ведущей строки p

Среди положительных элементов столбца
находим элемент
, для которого выполняется равенство

.

Строку p объявляем ведущей (разрешающей). Элемент
объявляем ведущим (разрешающим).

Шаг 6. Преобразование симплексной таблицы

Составляем новую симплекс-таблицу, в которой:

а) вместо базисной переменной записываем, вместо небазисной пере меннойзаписываем;

б) ведущий элемент заменяем обратной величиной
;

в) все элементы ведущего столбца (кроме
) умножаем на
;

г) все элементы ведущей строки (кроме
) умножаем на;

д) оставшиеся элементы симплексной таблицы преобразуются по следующей схеме «прямоугольника».

Из элемента вычитается произведение трех сомножителей:

первый – соответствующий элемент ведущего столбца;

второй – соответствующий элемент ведущей строки;

третий – обратная величина ведущего элемента
.

Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».

Шаг 7. Переход к следующей итерации осуществляется возвратом к шагу 2.

2.3. Алгоритм симплекс-метода для задачи на максимум

Алгоритм симплекс-метода для задачи на максимум отличается от алгоритма для задачи на минимум только знаками индексной строки коэффициентов в целевой функции
, а именно:

На шаге 2:
:

На шаге 3
. Целевая функция является неограниченной сверху на допустимом множестве.

На шаге 4 :
.

2.4. Пример решения задачи симплекс-методом

Решить задачу, записанную в виде (15).

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

Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение не является оптимальным. Значение целевой функции для этого базисаL=0.

Выбираем ведущий столбец – это столбец, соответствующий переменной .

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

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

Одна итерация метода завершена. Переходим к новой итерации. Полученная таблица неоптимальная. Базисное решение, соответствующее таблице, имеет вид . Значение целевой функции на этом базисеL= -2 .

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

Еще одна итерация завершена. Переходим к новой итерации.

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

Необходимо решить задачу линейного программирования.

Целевая функция:

2x 1 +5x 2 +3x 3 +8x 4 →min

Ограничивающие условия:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1

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

Так как наша задача - задача минимизации, то нам необходимо преобразовать ее к задаче на поиск максимума. Для этого изменим знаки коэффициентов целевой функции на противоположные. Элементы первого неравенства записываем без изменений, добавив в него дополнительную переменную x 5 и изменив знак "≤" на "=". Т. к. второе и третье неравенства имеют знаки "≥" необходимо поменять знаки их коэффициентов на противоположные и внести в них дополнительные переменные x 6 и x 7 соответственно. В результате получем эквивалентную задачу:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

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

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение.В строке F имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -1.988 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X2, а ведущий элемент: 0.313.

Так как в строке F нет отрицательных элементов, то найдено оптимальное решение. Так как исходной задачей был поиск минимума, то оптимальным решением будет свободный член строки F, взятый с противоположным знаком. F=1.924
при значениях переменных равных: x 3 =0.539, x 1 =0.153. Переменные x 2 и x 4 не входят в базис, поэтому x 2 =0 x 4 =0.

Рассмотрен пример решения задачи симплекс методом, а также пример решения двойственной задачи.

Условие задачи

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b 1 = 240, b 2 = 200, b 3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a 11 = 2 единицы, ресурса второго вида в количестве a 21 = 4 единицы, ресурса третьего вида в количестве a 31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a 12 = 3, a 13 = 6 единицы, ресурса второго вида в количестве a 22 = 2, a 23 = 4 единицы, ресурса третьего вида в количестве a 32 = 6, a 33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c 1 = 4, c 2 = 5, c 3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

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

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

F = 4·x 1 + 5·x 2 + 4·x 3 ->max

0}}}{~}" title="delim{lbrace}{matrix{4}{1}{{2x_1 + 3x_2 + 6x_3= 0}}}{~}">

Решаем симплекс методом.

Вводим дополнительные переменные x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, чтобы неравенства преобразовать в равенства.

В качестве базиса возьмем x 4 = 240; x 5 = 200; x 6 = 160.

Данные заносим в симплекс таблицу

Симплекс таблица № 1

Целевая функция:

0 · 240 + 0 · 200 + 0 · 160 = 0

Вычисляем оценки по формуле:

Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 - 4 = - 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Вводим переменную x 2 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 2 .

= 26.667

Наименьшее неотрицательное: Q 3 = 26.667. Выводим переменную x 6 из базиса

3-ю строку делим на 6.
Из 1-й строки вычитаем 3-ю строку, умноженную на 3
Из 2-й строки вычитаем 3-ю строку, умноженную на 2

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 2

Целевая функция:

0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6

Поскольку есть отрицательная оценка Δ 1 = - 2/3, то план не оптимален.

Вводим переменную x 1 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 1 .

Наименьшее неотрицательное: Q 3 = 40. Выводим переменную x 2 из базиса

3-ю строку делим на 2/3.
Из 2-й строки вычитаем 3-ю строку, умноженную на 8/3

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 3

Целевая функция:

0 · 160 + 0 · 40 + 4 · 40 = 160

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 - 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 - 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1

Поскольку отрицательных оценок нет, то план оптимален.

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

Ответ

То есть необходимо реализовать товар первого вида в объеме 40 тыс. руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F max = 160 тыс. руб.

Решение двойственной задачи

Двойственная задача имеет вид:

Z = 240·y 1 + 200·y 2 + 160·y 3 ->min

Title="delim{lbrace}{matrix{4}{1}{{2y_1 + 4y_2 + 4y_3>=4} {3y_1 + 2y_2 + 6y_3>=5} {6y_1 + 4y_2 + 8y_3>=4} {y_1, y_2, y_3>= 0}}}{~}">

Вводим дополнительные переменные y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, чтобы неравенства преобразовать в равенства.

Сопряженные пары переменных прямой и двойственной задач имеют вид:

Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;