Симплекс метод онлайн
Данный онлайн калькулятор решает задачу линейного программирования симплекс методом. Дается подробное решение с пояснениями. Для решения задачи линейного программирования задайте количество ограничений и количество переменных. Затем введите данные в ячейки и нажимайте на кнопку «Вычислить». Теоретическую часть смотрите в статье: Решение задачи линейного программирования. Симплекс метод.
| Количество ограничений: m= | 1234567891011121314151617181920 |
| Количество переменных : n= | 1234567891011121314151617181920 |
Очистить все ячейки?
Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.
Симплекс метод
Симплекс метод − это метод решения задачи линейного программирования (ЗЛП). Суть метода заключается в нахождении начального допустимого плана, и в последующем улучшении плана до достижения максимального (или минимального) значения целевой функции в данном выпуклом многогранном множестве или выяснения неразрешимости задачи. Подробнее в статье: Решение задачи линейного программирования. Симплекс метод.
Примеры решения ЗЛП симплекс методом
Пример 1. Решить следующую задачу линейного программирования:
Р е ш е н и е. Матрица коэффициентов системы уравнений имеет вид:
Правая часть ограничений системы уравнений имеет вид:
Составляем симплексную таблицу. В столбец x0 записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка — это целевая функция, умноженная на −1. Последние три векторы столбцы обазуют базис в трехмерном пространствое. Следовательно базисные переменные , а свободные переменные :
Запишем текущий опорный план:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x2. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x3. Сделаем исключение Гаусса для столбца x2, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Запишем текущий опорный план:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x1. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x4. Сделаем исключение Гаусса для столбца x1, учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Запишем текущий опорный план:
Текущий опорный план является оптимальным, так как в строках 4 под переменными нет отрицательных элементов.
Решение можно записать так: .
Значение целевой функции в данной точке: F(X)=.
Пример 2. Найти максимум функции
при условиях
Р е ш е н и е. Матрица коэффициентов системы уравнений имеет вид:
Правая часть ограничений системы уравнений имеет вид:
Составляем симплексную таблицу. В столбец x0 записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка — это целевая функция, умноженная на −1:
Базисные векторы x4, x3, следовательно, все элементы в столбцах x4, x3, ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x
Симплекс таблица примет вид:
Запишем текущий опорный план:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x2. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.
Примеры решения ЗЛП методом искусственного базиса
Пример 1. Найти максимум функции
при условиях
Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:
Матрица коэффициентов системы уравнений имеет вид:Правая часть ограничений системы уравнений имеет вид:
Составляем симплексную таблицу. В столбец x0 записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последние две строки − это целевая функция, умноженная на −1 и разделенная на две части. Последняя строка − строка с исскуственными переменными:
Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.
Симплекс таблица примет вид:
Запишем текущий опорный план:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-5), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор Сделаем исключение Гаусса для столбца учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Запишем текущий опорный план:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 1. Из базиса выходит вектор x2. Сделаем исключение Гаусса для столбца x1, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Запишем текущий опорный план:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x3. Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор x5. Сделаем исключение Гаусса для столбца x3, учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Запишем текущий опорный план:
Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.
Решение исходной задачи можно записать так:
| . |
Значение целевой функции в данной точке:
| . |
Пример 2. Найти оптимальный план задачи линейного программирования:
Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственные переменные, а в целевую функцию добавляем эти переменные, умноженные на −M, где M, очень большое число:
Матрица коэффициентов системы уравнений имеет вид:
Правая часть ограничений системы уравнений имеет вид:
Составляем симплексную таблицу. В столбец x0 записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последние две строки − это целевая функция, умноженная на −1 и разделенная на две части. Последняя строка − строка с исскуственными переменными:
Базисные векторы x4, x5, x6, следовательно, все элементы в столбцах x4, x5, x6, ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x4, кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x5, кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x6, кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.
Симплекс таблица примет вид:
Запишем текущий опорный план:
В строке 5 элементы, соответствующие переменным
matworld.ru
Линейное программирование. Симплекс-метод | Решатель
Рассмотрим симплекс-метод для решения задач линейного программирования (ЛП). Он основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает.
Алгоритм симплекс-метода следующий:
- Исходную задачу переводим в канонический вид путем введения дополнительных переменных. Для неравенства вида ≤ дополнительные переменные вводят со знаком (+), если же вида ≥ то со знаком (—). В целевую функцию дополнительные переменные вводят с соответствующими знаками с коэффициентом, равным 0, т.к. целевая функция не должна при этом менять свой экономический смысл.
- Выписываются вектора Pi из коэффициентов при переменных и столбца свободных членов. Этим действием определяется количество единичных векторов. Правило – единичных векторов должно быть столько, сколько неравенств в системе ограничений.
- После этого исходные данные вводятся в симплекс-таблицу. В базис вносятся единичные вектора, и исключая их из базиса, находят оптимальное решение. Коэффициенты целевой функции записывают с противоположным знаком.
- Признак оптимальности для задачи ЛП – решение оптимально, если в f – строке все коэффициенты положительны. Правило нахождения разрешающего столбца – просматривается f – строка и среди ее отрицательных элементов выбирается наименьшее. Вектор Pi его содержащий становится разрешающим. Правило выбора разрешающего элемента – составляются отношения положительных элементов разрешающего столбца к элементам вектора Р0 и то число, которое дает наименьшее отношение становится разрешающим элементом, относительно которого будет произведен пересчет симплекс-таблицы. Строка, содержащая этот элемент называется разрешающей строкой. Если в разрешающем столбце нет положительных элементов, то задача не имеет решения. После определения разрешающего элемента переходят к пересчету новой симплекс – таблицы.
- Правила заполнения новой симплекс – таблицы. На месте разрешающего элемента проставляют единицу, а другие элементы полагают равными 0. Разрешающий вектор вносят в базис, из которого исключают соответствующий нулевой вектор, а остальные базисные вектора записывают без изменений. Элементы разрешающей строки делят на разрешающий элемент, а остальные элементы пересчитывают по правилу прямоугольников.
- Так поступают до тех пор, пока в f – строке все элементы не станут положительными.
Рассмотрим решение задачи с использованием рассмотренного выше алгоритма.
Дано:
Приводим задачу к каноническому виду:
Составляем вектора:
Заполняем симплекс – таблицу:
Правило прямоугольников:
Пересчитаем первый элемент вектора Р0, для чего составляем прямоугольник из чисел: и получаем: .
Аналогичные расчеты выполним для всех остальных элементов симплекс – таблицы:
В полученном плане f – строка содержит один отрицательный элемент – (-5/3), вектора P1. Он содержит в своем столбце единственный положительный элемент, который и будет разрешающим элементом. Сделаем пересчет таблицы относительно этого элемента:
Отсутствие отрицательных элементов в f – строке означает, что найден оптимальный план:
F* = 36/5, Х = (12/5, 14/5, 8, 0, 0).
Рекомендуемая литература
- Ашманов С. А. Линейное программирование, М: Наука, 1998г.,
- Вентцель Е.С. Исследование операций, М: Советское радио, 2001г.,
- Кузнецов Ю.Н., Кузубов В.И., Волошенко А.Б. Математическое программирование, М: Высшая школа, 1986г.
Решение линейного программирования на заказ
Заказать любые задания по этой дисциплине можно у нас на сайте. Прикрепить файлы и указать сроки можно на странице заказа.
reshatel.org
Пример решения задачи симплекс М-методом
Условие задачи
Найти оптимальные величины производства продукции видов А, Б и В. Затраты сырья на единицу продукции: А – 5, Б – 2, В – 4. Объем сырья – 2000 единиц. Затраты оборудования на единицу продукции: А – 4, Б – 5, В – 4. Объем оборудования – 1000 единиц. Прибыль от реализации единицы продукции: А – 10, Б – 8, В – 12. Критерий – максимум прибыли предприятия. Производство продукции А должно быть не менее 100 ед. Производство продукции Б должно быть не менее 50 ед.
Решение задачи симплекс методом
1) Определение оптимального плана производства
Пусть x1, x2, x3 — количество произведенной продукции вида А, Б, В, соответственно. Тогда математическая модель задачи имеет вид:
F = 10·x1 + 8·x2 + 12·x3 –>max
Решаем симплекс методом.
Вводим дополнительные переменные x4 ≥ 0, x5 ≥ 0, x6 ≥ 0, x7 ≥ 0, чтобы неравенства преобразовать в равенства.
Чтобы выбрать начальный базис, вводим искусственные переменные x8 ≥ 0, x9 ≥ 0 и очень большое число M (M –> ∞). Решаем М методом.
F = 10·x1 + 8·x2 + 12·x3 + 0·x4 + 0·x5 + 0·x6 + 0·x7– M·x8– M·x9 –>max
В качестве базиса возьмем x4 = 2000; x5 = 1000; x8 = 100; x9 = 50.
Данные заносим в симплекс таблицу
Симплекс таблица № 1
Целевая функция:
0 · 2000 + 0 · 1000 + (– M) · 100 + (– M) · 50 = – 150M
Вычисляем оценки по формуле:
Δ1 = 0 · 5 + 0 · 4 + (– M) · 1 + (– M) · 0 – 10 = – M – 10
Δ2 = 0 · 2 + 0 · 5 + (– M) · 0 + (– M) · 1 – 8 = – M – 8
Δ3 = 0 · 4 + 0 · 4 + (– M) · 0 + (– M) · 0 – 12 = – 12
Δ4 = 0 · 1 + 0 · 0 + (– M) · 0 + (– M) · 0 – 0 = 0
Δ5 = 0 · 0 + 0 · 1 + (– M) · 0 + (– M) · 0 – 0 = 0
Δ6 = 0 · 0 + 0 · 0 + (– M) · (–1) + (– M) · 0 – 0 = M
Δ7 = 0 · 0 + 0 · 0 + (– M) · 0 + (– M) · (–1) – 0 = M
Δ8 = 0 · 0 + 0 · 0 + (– M) · 1 + (– M) · 0 – (– M) = 0
Δ9 = 0 · 0 + 0 · 0 + (– M) · 0 + (– M) · 1 – (– M) = 0
Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:
Δ1 = – M – 10
Вводим переменную x1 в базис.
Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x1.
Наименьшее неотрицательное: Q3 = 100. Выводим переменную x8 из базиса. Для этого над строками таблицы выполняем линейные преобразования.
Из 1-й строки вычитаем 3-ю строку, умноженную на 5
Из 2-й строки вычитаем 3-ю строку, умноженную на 4
Получаем новую таблицу:
Симплекс таблица № 2
Целевая функция:
0 · 1500 + 0 · 600 + 10 · 100 + (– M) · 50 = – 50M + 1000
Вычисляем оценки по формуле:
Δ1 = 0 · 0 + 0 · 0 + 10 · 1 + (– M) · 0 – 10 = 0
Δ2 = 0 · 2 + 0 · 5 + 10 · 0 + (– M) · 1 – 8 = – M – 8
Δ3 = 0 · 4 + 0 · 4 + 10 · 0 + (– M) · 0 – 12 = – 12
Δ4 = 0 · 1 + 0 · 0 + 10 · 0 + (– M) · 0 – 0 = 0
Δ5 = 0 · 0 + 0 · 1 + 10 · 0 + (– M) · 0 – 0 = 0
Δ6 = 0 · 5 + 0 · 4 + 10 · (–1) + (– M) · 0 – 0 = – 10
Δ7 = 0 · 0 + 0 · 0 + 10 · 0 + (– M) · (–1) – 0 = M
Δ8 = 0 · (–5) + 0 · (–4) + 10 · 1 + (– M) · 0 – (– M) = M + 10
Δ9 = 0 · 0 + 0 · 0 + 10 · 0 + (– M) · 1 – (– M) = 0
Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:
Δ2 = – M – 8
Вводим переменную x2 в базис.
Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x2.
Наименьшее неотрицательное: Q4 = 50. Выводим переменную x9 из базиса и удаляем искусственные переменные. Выполняем линейные преобразования.
Из 1-й строки вычитаем 4-ю строку, умноженную на 2
Из 2-й строки вычитаем 4-ю строку, умноженную на 5
Получаем новую таблицу:
Симплекс таблица № 3
Целевая функция:
0 · 1400 + 0 · 350 + 10 · 100 + 8 · 50 = 1400
Вычисляем оценки по формуле:
Δ1 = 0 · 0 + 0 · 0 + 10 · 1 + 8 · 0 – 10 = 0
Δ2 = 0 · 0 + 0 · 0 + 10 · 0 + 8 · 1 – 8 = 0
Δ3 = 0 · 4 + 0 · 4 + 10 · 0 + 8 · 0 – 12 = – 12
Δ4 = 0 · 1 + 0 · 0 + 10 · 0 + 8 · 0 – 0 = 0
Δ5 = 0 · 0 + 0 · 1 + 10 · 0 + 8 · 0 – 0 = 0
Δ6 = 0 · 5 + 0 · 4 + 10 · (–1) + 8 · 0 – 0 = – 10
Δ7 = 0 · 2 + 0 · 5 + 10 · 0 + 8 · (–1) – 0 = – 8
Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:
Δ3 = – 12
Вводим переменную x3 в базис.
Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x3.
= 87.5
Наименьшее неотрицательное: Q2 = 87.5. Выводим переменную x5 из базиса
2-ю строку делим на 4.
Из 1-й строки вычитаем 2-ю строку, умноженную на 4
Вычисляем:
Получаем новую таблицу:
Симплекс таблица № 4
Целевая функция:
0 · 1050 + 12 · 175/2 + 10 · 100 + 8 · 50 = 2450
Вычисляем оценки по формуле:
Δ1 = 0 · 0 + 12 · 0 + 10 · 1 + 8 · 0 – 10 = 0
Δ2 = 0 · 0 + 12 · 0 + 10 · 0 + 8 · 1 – 8 = 0
Δ3 = 0 · 0 + 12 · 1 + 10 · 0 + 8 · 0 – 12 = 0
Δ4 = 0 · 1 + 12 · 0 + 10 · 0 + 8 · 0 – 0 = 0
Δ5 = 0 · (–1) + 12 · 1/4 + 10 · 0 + 8 · 0 – 0 = 3
Δ6 = 0 · 1 + 12 · 1 + 10 · (–1) + 8 · 0 – 0 = 2
Δ7 = 0 · (–3) + 12 · 5/4 + 10 · 0 + 8 · (–1) – 0 = 7
Поскольку отрицательных оценок нет, то план оптимален.
Решение задачи: x1 = 100; x2 = 50; x3 = 175/2 = 87.5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450
Ответ: x1 = 100; x2 = 50; x3 = 175/2 = 87.5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450То есть необходимо произвести x1 = 100 единиц продукции вида А, x2 = 50 единиц продукции вида Б и x3 = 87,5 единиц продукции вида В. Максимальная прибыль при этом составит Fmax = 2450 единиц.
Автор: Олег Одинцов. Опубликовано:
1cov-edu.ru