Симплекс метод графическим способом

Высшая математика и экономика

Образовательные онлайн сервисы: теория и практика

Примеры — Математическое программирование

Графический и симплекс метод

Для производства двух видов изделий А и В используются три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется в течении 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 и повторяем весь процесс.
Под столбцом свободных членов записывается начальная оценка

Остальные оценки записываются под столбцами соответствующих векторов .


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

Опять проверяется критерий оптимальности. Отрицательная оценка только одна – в столбце А2.

Вычисляем:

Разрешающим элементом будет второй элемент второго столбца – 2/3.

Новыми базисными переменными становятся A3, A2, A1
Делим вторую строку на 2 и вычитаем из третьей.
Умножаем вторую строку на 5/2 и вычитаем из первой.

На этот раз отрицательных оценок нет, т.е. критерий оптимальности выполнен.

Таким образом, получается искомое значение целевой функции F(15; 5; 7; 0; 0) = 70, т.е. возвращаясь к системе неравенств, получаем:

Ответы, полученные различными методами, совпадают.

Источник

Симплекс метод онлайн

Данный онлайн калькулятор решает задачу линейного программирования симплекс методом. Дается подробное решение с пояснениями. Для решения задачи линейного программирования задайте количество ограничений и количество переменных. Затем введите данные в ячейки и нажимайте на кнопку «Вычислить». Теоретическую часть смотрите в статье: Решение задачи линейного программирования. Симплекс метод.

Предупреждение

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Симплекс метод

Симплекс метод − это метод решения задачи линейного программирования (ЗЛП). Суть метода заключается в нахождении начального допустимого плана, и в последующем улучшении плана до достижения максимального (или минимального) значения целевой функции в данном выпуклом многогранном множестве или выяснения неразрешимости задачи. Подробнее в статье: Решение задачи линейного программирования. Симплекс метод.

Примеры решения ЗЛП симплекс методом

Пример 1. Решить следующую задачу линейного программирования:

Р е ш е н и е. Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка — это целевая функция, умноженная на −1. Последние три векторы столбцы обазуют базис в трехмерном пространствое. Следовательно базисные переменные , а свободные переменные :

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x₂. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x₃. Сделаем исключение Гаусса для столбца x₂, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x₁. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x₄. Сделаем исключение Гаусса для столбца x₁, учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Текущий опорный план является оптимальным, так как в строках 4 под переменными нет отрицательных элементов.

Решение можно записать так: .

Значение целевой функции в данной точке: F(X)=.

Пример 2. Найти максимум функции

Р е ш е н и е. Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка — это целевая функция, умноженная на −1:

Базисные векторы x₄, x₃, следовательно, все элементы в столбцах x₄, x₃, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x₄, кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x₃, кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.

Симплекс таблица примет вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x₂. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.

Примеры решения ЗЛП методом искусственного базиса

Пример 1. Найти максимум функции

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:

Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последние две строки − это целевая функция, умноженная на −1 и разделенная на две части. Последняя строка − строка с исскуственными переменными:

Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

Запишем текущий опорный план:

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

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 1. Из базиса выходит вектор x₂. Сделаем исключение Гаусса для столбца x₁, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x₃. Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор x₅. Сделаем исключение Гаусса для столбца x₃, учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.

Решение исходной задачи можно записать так:

.

Значение целевой функции в данной точке:

.

Пример 2. Найти оптимальный план задачи линейного программирования:

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственные переменные, а в целевую функцию добавляем эти переменные, умноженные на −M, где M, очень большое число:

Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последние две строки − это целевая функция, умноженная на −1 и разделенная на две части. Последняя строка − строка с исскуственными переменными:

Базисные векторы x₄, x₅, x₆, следовательно, все элементы в столбцах x₄, x₅, x₆, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x₄, кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x₅, кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x₆, кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

Запишем текущий опорный план:

В строке 5 элементы, соответствующие переменным x₁, x₂, x₃, x₄, x₅, x₆ неотрицательны, а число находящийся в пересечении данной строки и столбца x₀ отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.

Источник