Здесь приведено ручное (не апплетом) решение двух задач симплекс-методом (аналогичным решению апплетом) с подробными объяснениями для того, чтобы понять алгоритм решения задач симплекс-методом. Первая задача содержит знаки неравенства только " ≤ " (задача с начальным базисом), вторая может содержить знаки " ≥ ", " ≤ " или " = " (задача с искусственным базисом), они решаются по разному.
Симплекс-метод, решение задачи с начальным базисом
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.
Если вы уже разобрались с графическим методом решения задач линейного программирования, самое время переходить к симплекс-методу . В отличие от первого, он практически не имеет ограничений на задачу (любое количество переменных, разные знаки и т.п.) и модифицируется в зависимости от типа задачи (например, М-метод или метод искусственного базиса).
При решении задачи симплекс методом вычисления обычно ведутся (для компактности и наглядности) в таблицах (табличный симплекс-метод), причем последняя таблица с оптимальным решением содержит важную дополнительную информацию: решение двойственной задачи, остатки ресурсов, сведения о дефицитных ресурсах и т.п., которая позволяет провести экономический анализ задачи линейного программирования (см. ниже пример 3).
Примеры решений задач симплекс-методом выложены бесплатно для вашего удобства — изучайте, ищите похожие, решайте. Если вам нужна помощь в выполнении подобных заданий, перейдите в раздел: решение линейного программирования на заказ.
Решение задач симплекс-методом: примеры онлайн
Задача 1. Компания производит полки для ванных комнат двух размеров — А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В — 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В — 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В — 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?
Составление математической модели и решение ЗЛП симплекс-методом (pdf, 33 Кб)
Задача 2.
Решить задачу линейного программирования симплекс-методом. 
Решение симплекс-методом с искусственным базисом (pdf, 45 Кб)
Задача 3. Предприятие производит 3 вида продукции: А1, А2, А3, используя сырьё двух типов. Известны затраты сырья каждого типа на единицу продукции, запасы сырья на планируемый период, а также прибыль от единицы продукции каждого вида.
- Сколько изделий каждого вида необходимо произвести, чтобы получить максимум прибыли?
- Определить статус каждого вида сырья и его удельную ценность.
- Определить максимальный интервал изменения запасов каждого вида сырья, в пределах которого структура оптимального плана, т.е. номенклатура выпуска, не изменится.
- Определить количество выпускаемой продукции и прибыль от выпуска при увеличении запаса одного из дефицитных видов сырья до максимально возможной (в пределах данной номенклатуры выпуска) величины.
- Определить интервалы изменения прибыли от единицы продукции каждого вида, при которых полученный оптимальный план не изменится.
Решение задачи линейного программирования с экономическим анализом (pdf, 163 Кб)
Задача 4.
Решить задачу линейного программирования симплексным методом: 
Решение табличным симплекс-методом с поиском опорного плана (pdf, 44 Кб)
Задача 5.
Решить задачу линейного программирования симплекс-методом: 
Решение табличным симплекс-методом (pdf, 47 Кб)
Задача 6.
Решить задачу симплекс-методом, рассматривая в качестве начального опорного плана, план, приведенный в условии:
Решение ручным симплекс-методом (pdf, 60 Кб)
Задача 7.
Решить задачу модифицированным симплекс-методом.
Для производства двух видов изделий А и Б используется три типа технологического оборудования. На производство единицы изделия А оборудование первого типа используется а1=4 часов, оборудование второго типа а2=8 часов, а оборудование третьего типа а3=9 часов. На производство единицы изделия Б оборудование первого типа используется б1=7 часов, оборудование второго типа б2=3 часов, а оборудование третьего типа б3=5 часов.
На изготовление этих изделий оборудование первого типа может работать не более чем t1=49 часов, оборудование второго типа не более чем t2=51 часов, оборудование третьего типа не более чем t3=45 часов.
Прибыль от реализации единицы готового изделия А составляет АЛЬФА=6 рублей, а изделия Б – БЕТТА=5 рублей.
Составить план производства изделий А и Б, обеспечивающий максимальную прибыль от их реализации.
Решение модифицированным симплекс-методом (pdf, 67 Кб)
Задача 8.
Найти оптимальное решение двойственным симплекс-методом
Решение двойственным симплекс-методом (pdf, 43 Кб)
Примеры решений задач по линейному программированию
Методы решения задачи линейного программирования
Опорные решения задачи линейного программирования
Пусть дана задача линейного программирования в канонической форме записи
при условиях
Будем обозначать через множество решений системы (2) – (3). Предположим, что , где – ранг матрицы , – количество уравнений в системе (2).
Из системы векторов-столбцов матрицы выберем некоторую линейно независимую подсистему из векторов . Она существует, так как . Эта система образует базис в . Обозначим через , . Назовем множеством базисных значений индекса , – базиснойподматрицей матрицы . Координаты вектора будем называть базисными , если , и небазисными в противном случае.
Запишем систему (2) в виде . Разобьем слагаемые левой части на базисные и небазисные, то есть
Определим частное решение этой системы следующим образом. Положим в (4) все небазисные переменные равными нулю . Тогда система (4) примет вид
Назовем (5) базисной подсистемой системы уравнений (2). Обозначим через вектор, составленный из базисных координат вектора . Тогда систему (2) можно переписать в векторно-матричном виде
Так как подматрица является базисной, она
невырождена. Поэтому система (6) имеет единственное решение . Полученное таким образом частное решение системы (2) назовем опорным решением прямой задачи линейного программирования, соответствующим базису . (Иногда опорное решение также называют базисным ). Как видим, базису соответствует единственное опорное решение. Очевидно, что число опорных решений конечно.
Для данного базиса определим также и опорное решение двойственной задачи линейного программирования. Напомним, что задача двойственная к канонической имеет вид
при условиях
Запишем систему (8) в виде
Напомним, что множество решений системы (8) обозначается через .
Определим вектор двойственных переменных из условия выполнения базисных ограничений в системе (9) как равенств. Получим следующую систему линейных уравнений:
Обозначим через вектор, составленный из ба-
зисных координат вектора . Тогда систему (10) можно переписать в векторно-матричном виде
Система (11) также имеет единственное решение .
Назовем его опорным (базисным ) решением двойственной задачи линейного программирования, соответствующим базису . Это опорное решение также определяется однозначно.
Итак, любому базису соответствуют два вектора – два опорных решения и прямой и двойственной задач линейного программирования, соответственно.
Определим далее следующие разновидности базисов и опорных решений. Если все координаты опорного решения неотрицательны, то базис, которому соответствует это опорное решение, называется допустимым опорным планом прямой задачи линейного программирования, а соответствующее тому же базису опорное решение называется псевдопланом двойственной задачи. Фактически для допустимости базиса достаточно неотрицательности базисных координат . Заметим, что опорный план является допустимым вектором прямой задачи линейного программирования ().
Если опорное решение удовлетворяет всем ограничениям (9) двойственной задачи, то базис, которому соответствует это опорное решение, называется двойственно допустимым . В этом случае вектор называется опорным планом двойственной задачи линейного программирования, а соответствующее тому же базису опорное реше-
ние называется псевдопланом прямой задачи.
Для двойственной допустимости базиса достаточно выполнения только небазисных неравенств . Заметим, что опорный план является допустимым вектором двойственной задачи линейного программирования ().
Разности левых и правых частей неравенств (9) обозначим через , . Тогда двойственную допустимость базиса можно устанавливать, проверяя неотрицательность всех . Заметим, что, как следует непосредственно из определения, все базисные невязки равны нулю ().
Пример решения прямой и двойственной задачи симплекс методом
Поэтому достаточно убедиться в выполнении неравенств для всех .
Теорема 1. Пусть и – опорные решения задачи линейного программирования, соответствующие некоторому базису , тогда имеет место равенство .
Доказательство . Из определений опорных решений легко получить равенства
откуда и следует справедливость теоремы.
Теорема 2. (Критерий оптимальности опор-ных решений) Если базис одновременно допустим и двойственно допустим, то соответствующие ему опорные решения и являются решениями, соответственно, прямой и двойственной задач линейного программирования.
Доказательство. Справедливость этого утверждения следует из теории двойственности в линейном программировании и теоремы 1.
Теорема 3. Допустимое решение задачи (1) – (3) является опорным планом задачи тогда и только тогда, когда оно является вершиной выпуклого многогранного множества .
Доказательство. Пусть – опорный план задачи (1) – (3). Докажем, что – вершина множества . По определению опорный план – допустимое опорное решение, соответствующее некоторому базису , то есть – решениесистемы линейных уравнений относительно переменных
Легко увидеть, что эта система имеет единственное решение. Значит, несущая плоскость грани, содержащей точку , имеет размерность 0. Следовательно, – вершина множества .
Обратно. Пусть – вершина множества . Докажем, что – опорный план задачи (1) – (3). Так как – вершина, то она является гранью множества , размерность которой равна нулю. Следовательно, у вектора найдется не менее нулевых компонент, множество номеров которых обозначим . Таким образом, – единственное решение системы
где . Поэтому осталось доказать, что система векторов линейно независима. Предположим противное. Тогда существуют числа не все равные нулю, такие что . Поэтому
Это означает, что система (12) имеет решение, отличное от , что противоречит единственности ее решения. Таким образом, – базис, а вектор – соответствующий ему опорный план задачи (1) – (3). Что и требовалось.
Заметим, что допустимое решение задачи (7), (8) (двойственной задаче (1) – (3)) также является опорным планом тогда и только тогда, когда оно является вершиной допустимого множества .
Дата публикования: 2015-01-10; Прочитано: 695 | Нарушение авторского права страницы
Studopedia.org — Студопедия.Орг — 2014-2018 год.(0.005 с)…
Для определенности считаем, что решается задача на отыскание минимума.
1. Задачу линейного программирования привести к каноническому виду.
После введения добавочных переменных систему уравнений и линейную функцию записываем в виде, который называется расширенной системой:
Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены; в противном случае используем так называемый М – метод, который будет рассмотрен ниже.
2. Определить базисные и свободные переменные.
3. Исходную расширенную систему заносим в первую симплекс – таблицу. Последняя строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной . В ней указываются коэффициенты функции цели . В левом столбце таблицы записываем основные переменные (базис), в последующих – коэффициенты при свободных переменных. В предпоследнем столбце – свободные члены расширенной системы . Последний столбец подготовлен для оценочных отношений, необходимых для определения базисной переменной на основании соотношения (6.29).
4. Определить возможность решения задачи по значениям согласно теоремам 6.7,…, 6.9.
5. Выбрать разрешающий (опорный) элемент .
Решение производственной задачи табличным симплекс-методом
Если критерий оптимальности не выполнен (не выполнены условия теоремы 6.7 или 6.8), то наибольший по модулю отрицательный коэффициент в последней строке определяет разрешающий (опорный) столбец 
.
Составляем оценочные отношения каждой строки по следующим правилам:
1 0) , если все и имеют разные знаки;
2 0) , если все и ;
3 0) , если ;
4 0) 0, если и ;
5 0) , если и имеют одинаковые знаки.
Определим . Если конечного минимума нет, то задача не имеет конечного оптимума (). Если минимум конечен, то выбираем строку q , на которой он достигается (любую, если их несколько), и называем ее разрешающей (опорной) строкой. На пересечении разрешающих строки и столбца находится разрешающий (опорный) элемент .
6 0) Переход к следующей таблице по правилам:
а) в левом столбце записываем новый базис: вместо основной переменной – переменную , т.е. поменяем местами переменные и ;
б) на место опорного элемента поставить 1;
в) на остальных местах опорной строки в новой таблице оставить элементы исходной таблицы;
г) на остальные места в опорном столбце поставить соответствующие элементы исходной таблицы, умноженные на –1;
д) на оставшиеся свободные места элементов , , в новой таблице записать числа , , , которые находятся следующим образом:
Для упрощения вычислений по этим формулам их можно сформулировать в виде «правила прямоугольника» (рис. 6.8): элементы на диагоналях прямоугольника с вершинами (или , , , , или , , , ) перемножаются (произведение, не содержащее опорного элемента , берется со знаком минус) и полученные произведения складываются;
е) все полученные элементы новой таблицы разделить на опорный элемент .
7 0) По значению элемента определить, найдено ли оптимальное значение целевой функции. В случае отрицательного ответа продолжить решение (возврат к пункту 6).
Рис. 6.8. Правило прямоугольника для определения чисел:
а − , б − , в − .
Рассмотрен алгоритм преобразования симплекс – таблиц для невырожденных допустимых базисных решений, т.е. выполнялась ситуация, описанная теоремой 6.9. Если исходная задача линейного программирования является вырожденной, то в ходе ее решения симплекс – методом могут появиться и вырожденные базисные решения. При этом возможны холостые шаги симплекс – метода, т.е. итерации, на которых f (x) не изменяется. Возможно так же и зацикливание, т.е. бесконечная последовательность холостых шагов. Для его предотвращения разработаны специальные алгоритмы – антициклины. Однако в подавляющем большинстве случаев холостые шаги сменяются шагами с убыванием целевой функции и процесс решения завершается в результате конечного числа итераций.
Пример 6.8. Решить задачу, приведенную в примере 6.7, симплекс методом.
⇐ Предыдущая45678910111213Следующая ⇒
Дата публикования: 2015-01-23; Прочитано: 174 | Нарушение авторского права страницы
Studopedia.org — Студопедия.Орг — 2014-2018 год.(0.002 с)…
Главная >> Пример №3. Симплекс метод. Нахождение наибольшего значения функции (искусственный базис)
Симплекс метод
| — | x 1 | + | x 2 | ≥ | 1 | |
| x 1 | + | 3 | x 2 | ≤ | 15 | |
| — | 2 | x 1 | + | x 2 | ≤ | 4 |
| Переменная называется базисной для данного уравнения, если она входит в данное уравнение с коэффициентом один и не входит в оставшиеся уравнения (при условии, что в правой части уравнения стоит положительное число).
Если в каждом уравнении присутствует базисная переменная, тогда говорят, что в системе присутствует базис. Идея симплекс метода заключается в том, чтобы переходить от одного базиса к другому, получая значение функции, как минимум, не меньше имеющегося (каждому базису соответствует единственное значение функции). Как осуществляется переход от одного базиса к другому? |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | св. член | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W — 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W — 0 |
| x 1 | x 2 | S 1 | S 2 | S 3 | св. член | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F — 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F — 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F — 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F — 13 = 0 => F = 13 |
Среди коэффициентов выделенной строки нет положительных. Следовательно, найдено наибольшее значение функции F.
Ответ:
x 1 = 3 x 2 = 4
F max = 13
Перейти к решению своей задачи
© 2010-2018, по всем вопросам пишите по адресу [email protected]
Условие задачи
Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве 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 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.
К прямой задаче планирования товарооборота, решаемой симплекс методом
, составить двойственную задачу
линейного программирования.
Установить сопряженные пары переменных
прямой и двойственной задачи.
Согласно сопряженным парам переменных из решения прямой задачи получить решение двойственной задачи
, в которой производится оценка ресурсов
, затраченных на продажу товаров.
Решение задачи симплекс методом
Пусть x 1 , x 2 , x 3 — количество реализованных товаров, в тыс. руб., 1, 2, 3 — ей групп, соответственно. Тогда математическая модель задачи имеет вид:
F = 4·x 1 + 5·x 2 + 4·x 3 ->max
Решаем симплекс методом.
Вводим дополнительные переменные 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
Поскольку отрицательных оценок нет, то план оптимален.
Решение задачи:
Ответ
x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160
То есть необходимо реализовать товар первого вида в объеме 40 тыс.
руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F max = 160 тыс. руб.
Решение двойственной задачи
Двойственная задача имеет вид:
Z = 240·y 1 + 200·y 2 + 160·y 3 ->min
Вводим дополнительные переменные 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;
Ответ
y 1 = 0; y 2 = 0; y 3 = 1; Z min = 160;
Симплексный метод – это вычислительная процедура, основанная на принципе последовательного улучшения решений при переходе от одной базисной точки (базисного решения) к другой. При этом значение целевой функции улучшается.
Базисным решением является одно из допустимых решений, находящихся в вершинах области допустимых значений. Проверяя на оптимальность вершину за вершиной симплекса, приходят к искомому оптимуму. На этом принципе основан симплекс-метод.
Симплекс – это выпуклый многоугольник в n-мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости (гиперплоскость делит пространство на два полупространства).
Например, линия бюджетных ограничений делит блага на доступные и недоступные.
Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число итераций (шагов), кроме случаев «зацикливания».
Алгоритм симплексного метода состоит из ряда этапов.
Первый этап. Строится исходная оптимизационная модель. Далее исходная матрица условий преобразуется в приведенную каноническую форму, которая среди всех других канонических форм выделяется тем, что:
а) правые части условий (свободные члены bi) являются величинами неотрицательными;
б) сами условия являются равенствами;
в) матрица условий содержит полную единичную подматрицу.
Если свободные члены отрицательные, то обе части неравенства умножаются на — 1, а знак неравенства меняется на противоположный. Для преобразования неравенств в равенства вводятся дополнительные переменные, которые, обычно, обозначают объем недоиспользованных ресурсов. В этом их экономический смысл.
Наконец, если после добавления дополнительных переменных, матрица условий не содержит полную единичную подматрицу, то вводятся искусственные переменные, которые не имеют никакого экономического смысла. Они вводятся исключительно для того, чтобы получить единичную подматрицу и начать процесс решения задачи при помощи симплексного метода.
В оптимальном решении задачи все искусственные переменные (ИП) должны быть равными нулю. Для этого вводят искусственные переменные в целевую функцию задачи с большими отрицательными коэффициентами (-М) при решении задачи на max, и с большими положительными коэффициентами (+М), когда задача решается на min. В этом случае даже незначительное ненулевое значение искусственной переменной будет резко уменьшать (увеличивать) значение целевой функции. Обычно М в 1000 раз должно быть больше, чем значения коэффициентов при основных переменных.
Второй этап. Строится исходная симплекс-таблица и отыскивается некоторое начальное базисное решение. Множество переменных, образующих единичную подматрицу, принимается за начальное базисное решение. Значения этих переменных равны свободным членам. Все остальные внебазисные переменные равны нулю.
Третий этап. Проверка базисного решения на оптимальность осуществляется при помощи специальных оценок коэффициентов целевой функции. Если все оценки коэффициентов целевой функции отрицательны или равны нулю, то имеющееся базисное решение – оптимальное. Если хотя бы одна оценка коэффициента целевой функции больше нуля, то имеющееся базисное решение не является оптимальным и должно быть улучшено.
Четвертый этап. Переход к новому базисному решению. Очевидно, что в оптимальный план должна быть введена такая переменная, которая в наибольшей степени увеличивает целевую функцию. При решении задач на максимум прибыли в оптимальный план вводится продукция, производство которой наиболее выгодно. Это определяется по максимальному положительному значению оценки коэффициента целевой функции.
Столбец симплексной таблицы с этим номером на данной итерации называется генеральным столбцом.
Для отыскания генеральной строки все свободные члены (ресурсы) делятся на соответствующие элементы генерального столбца (норма расхода ресурса на единицу изделия). Из полученных результатов выбирается наименьший. Соответствующая ему строка на данной итерации называется генеральной. Она соответствует ресурсу, который лимитирует производство на данной итерации.
Элемент симплексной таблицы, находящийся на пересечении генеральных столбца и строки, называется генеральным элементом.
Затем все элементы генеральной строки (включая свободный член), делятся на генеральный элемент. В результате этой операции генеральный элемент становится равным единице. Далее необходимо, чтобы все другие элементы генерального столбца стали бы равны нулю, т.е. генеральный столбец должен стать единичным. Все строки (кроме генеральной) преобразуются следующим образом. Полученные элементы новой строки умножаются на соответствующий элемент генерального столбца и полученное произведение вычитается из элементов старой строки.
Значения новых базисных переменных получим в соответствующих ячейках столбца свободных членов.
Пятый этап. Полученное базисное решение проверяется на оптимальность (см. третий этап). Если оно оптимально, то вычисления прекращаются. В противном случае необходимо найти новое базисное решение (четвертый этап) и т.
Симплекс метод
Пример решения оптимизационных задач линейного программирования симплексным методом
Пусть необходимо найти оптимальный план производства двух видов продукции (х1 и х2).
Исходные данные:
Построим оптимизационную модель
– ограничение по ресурсу А;
– ограничение по ресурсу В.
Приведем задачу к приведенной канонической форме. Для этого достаточно ввести дополнительные переменные Х3 и Х4. В результате неравенства преобразуются в строгие равенства.
Построим исходную симплексную таблицу и найдем начальное базисное решение. Им будут дополнительные переменные, т. к. им соответствует единичная подматрица.
1-я итерация. Находим генеральный столбец и генеральную строку:
Генеральный элемент равняется 5.
2-я итерация. Найденное базисное решение не является оптимальным, т.к. cтрока оценок (Fj-Cj) содержит один положительный элемент. Находим генеральный столбец и генеральную строку:
max (0,0.3,-1.4,0) = 0.2
Найденное решение оптимально, так как все специальные оценки целевой функции Fj – Cj равны нулю или отрицательны. F(x)=29 x1=2; x2=5.
Для производства двух видов изделий А и В используются три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется в течении 1 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 3 часа.
Для производства единицы изделия В оборудование первого типа используется в течении 2 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 1 час.
На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 32 часа, оборудование второго типа – 60 часов, оборудование третьего типа – 50 часов.
Прибыль от реализации единицы готового изделия А составляет 4 денежные единицы, а изделия В – 2 денежные единицы.
Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.
1) Составить математическую модель задачи
2) Решить графическим методом
3)Решить симплекс-методом путем преобразования симплекс-таблиц
Решение
Перед нами – классическая задача линейного программирования. Под планом производства понимается ответ на простой вопрос: сколько изделий А и сколько изделий В надо выпустить, чтобы прибыль была максимальна.
Прибыль рассчитывается по формуле: .
Запишем математическую модель задачи:
Чтобы проиллюстрировать применение симплекс-метода решения этой задачи, решим ее графически.
Для этого построим на плоскости области, описываемые ограничениями-неравенствами, и прямую , которая называется целевой функцией.
Три записанных выше неравенства ограничивают на плоскости многоугольник (построен красным цветом), ограниченный слева и снизу координатными осями (т.к. искомое количество изделий положительно).
График целевой функции (построен синим цветом) передвигается в направлении, обозначенном стрелкой (по-научному – в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (15 ; 5). В этой точке целевая функция будет достигать максимума.
А теперь решим эту задачу симплекс-методом. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам, введя дополнительные переменные .
Симплекс-таблица составляется так:
В графе Базис записываются вектора переменных, принимаемые за базисные. На первом этапе это – A3, A4, A5. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.
В следующий столбец записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В –
столбец свободных членов. Далее идут столбцы коэффициентов Аi при i –й переменной.
Следует отметить, что оценки для базисных векторов всегда равны нулю.
Преобразование симплекс-таблицы ведется следующим образом:
Шаг 1: Проверяется критерий оптимальности, суть которого состоит в том, что все оценки должны быть неотрицательны. В нашем случае этот критерий не выполнен, поэтому переходим ко второму шагу.
Шаг 2: Для отрицательных оценок вычисляются величины:
Из этих элементов выбирается тот, для которого вычисленное произведение минимально, в нашем случае минимально, поэтому в качестве так называемого разрешающего элемента выбирается третий элемент первого столбца – 3 (выделен в таблице).
Шаг 3: Третья строка таблицы делится на 3 и вычитается из первой и второй строк. В сущности, применяется метод исключения неизвестных, известный как метод Жордана – Гаусса.
Таким образом, новыми базисными переменными становятся A3, A4, A1.
Возвращаемся к шагу 1 и повторяем весь процесс.
Под столбцом свободных членов записывается начальная оценка
Остальные оценки записываются под столбцами соответствующих векторов .
Следует отметить, что оценки для базисных векторов всегда равны нулю.
Ответы, полученные различными методами, совпадают.
Задач линейного программирования. Он в последовательном построении , характеризующей рассматриваемый процесс. Решение разбивается на три основных этапа: выбор переменных, построение системы ограничений и поиск целевой функции.
Исходя из этого разделения, условие задачи можно перефразировать следующим образом: экстремум целевой функции 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).
Симплекс-метод - это итеративный процесс направленного решения системы уравнений по шагам, который начинается с опорного решения и в поисках лучшего варианта движется по угловым точкам области допустимого решения, улучшающих значение целевой функции до тех пор, пока целевая функция не достигнет оптимального значения.Назначение сервиса . Сервис предназначен для онлайн решения задач линейного программирования (ЗЛП) симплекс-методом в следующих формах записи:
- в виде симплексной таблицы (метод жордановых преобразований); базовой форме записи;
- модифицированным симплекс-методом ; в столбцовой форме; в строчечной форме.
Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word и Excel .
При этом ограничения типа x i ≥ 0 не учитывайте. Если в задании для некоторых x i отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом . При решении автоматически определяется использование М-метода (симплекс-метод с искусственным базисом) и двухэтапного симплекс-метода .Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП
Решение транспортной задачи
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных
Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.
| Объем товара Х (в партиях) | Доход G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Алгоритм симплекс-метода включает следующие этапы:
- Составление первого опорного плана . Переход к канонической форме задачи линейного программирования путем введения неотрицательных дополнительных балансовых переменных.
- Проверка плана на оптимальность . Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить.
- Определение ведущих столбца и строки . Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца.
- Построение нового опорного плана . Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана-Гаусса .
Если необходимо найти экстремум целевой функции, то речь идет о поиске минимального значения (F(x) → min , см. пример решения минимизации функции) и максимального значения ((F(x) → max , см. пример решения максимизации функции)
Экстремальное решение достигается на границе области допустимых решений в одной из вершин угловых точек многоугольника, либо на отрезке между двумя соседними угловыми точками.
Основная теорема линейного программирования . Если целевая функция ЗЛП достигает экстремального значения в некоторой точке области допустимых решений, то она принимает это значение в угловой точке. Если целевая функция ЗЛП достигает экстремального значения более чем в одной угловой точке, то она принимает это же значение в любой из выпуклой линейной комбинации этих точек.
Суть симплекс-метода
. Движение к точке оптимума осуществляется путем перехода от одной угловой точки к соседней, которая ближе и быстрее приближает к X опт. Такую схему перебора точек, называемую симплекс-метод
, предложил Р. Данцигом.
Угловые точки характеризуются m базисными переменными, поэтому переход от одной угловой точки к соседней возможно осуществить сменой в базисе только одной базисной переменной на переменную из небазиса.
Реализация симплекс-метода в силу различных особенностей и постановок задач ЛП имеет различные модификации .
Построение симплекс-таблиц продолжается до тех пор, пока не будет получено оптимальное решение.
Как с помощью симплекс-таблицы определить, что решение задачи линейного программирования является оптимальным?
Если последняя строка (значения целевой функции) не содержит отрицательных элементов, следовательно, найдет оптимальный план.
Замечание 1. Если одна из базисных переменных равна нулю, то крайняя точка, соответствующая такому базисному решению - вырожденная. Вырожденность возникает, когда имеется неоднозначность в выборе направляющей строки. Можно вообще не заметить вырожденности задачи, если выбрать другую строку в качестве направляющей. В случае неоднозначности нужно выбирать строку с наименьшим индексом, чтобы избежать зацикливания.
Замечание 2. Пусть в некоторой крайней точке все симплексные разности неотрицательные D k ³ 0 (k = 1..n+m),т.е. получено оптимальное решение и существует такой А k - небазисный вектор, у которого D k = 0. Тогда максимум достигается по крайней мере в двух точках, т.е. имеет место альтернативный оптимум. Если ввести в базис эту переменную x k , значение целевой функции не изменится.
Замечание 3. Решение двойственной задачи находится в последней симплексной таблице. Последние m компонент вектора симплексных разностей(в столбцах балансовых переменных) - оптимальное решение двойственной задачи. Значение целевых функций прямой и двойственной задачи в оптимальных точках совпадают.
Замечание 4. При решении задачи минимизации в базис вводится вектор с наибольшей положительной симплексной разностью. Далее применяется тот же алгоритм, что и для задачи максимизации.
Если задано условие «Необходимо, чтобы сырье III вида было израсходовано полностью», то соответствующее условие представляет собой равенство.