Симплекс метод онлайн
Данный онлайн калькулятор решает задачу линейного программирования симплекс методом. Дается подробное решение с пояснениями. Для решения задачи линейного программирования задайте количество ограничений и количество переменных. Затем введите данные в ячейки и нажимайте на кнопку “Вычислить”. Теоретическую часть смотрите в статье: Решение задачи линейного программирования. Симплекс метод.
| Количество ограничений: 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
Симплекс таблица примет следующий вид:
Запишем текущий опорный план:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор
Симплекс таблица примет следующий вид:
Текущий опорный план является оптимальным, так как в строках 4 под переменными нет отрицательных элементов.
Решение можно записать так: .
Значение целевой функции в данной точке: F(X)=.
Пример 2. Найти максимум функции
при условиях
Р е ш е н и е. Матрица коэффициентов системы уравнений имеет вид:
Правая часть ограничений системы уравнений имеет вид:
Составляем симплексную таблицу. В столбец x0 записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов
Базисные векторы x4, x3, следовательно, все элементы в столбцах x4, x3, ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x4, кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x3, кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.
Симплекс таблица примет вид:
Запишем текущий опорный план:
Примеры решения ЗЛП методом искусственного базиса
Пример 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 элементы, соответствующие переменным x1, x2, x3, x4, x5, x6 неотрицательны, а число находящийся в пересечении данной строки и столбца x0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.
matworld.ru
Решить графически задачу – 8 Февраля 2015 – Примеры решений задач
Задача. Решить графически задачу линейного программирования, определив экстремальное значение целевой функции:
при ограничениях
Решение.
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Построим уравнение 3x1+x2 = 9 по двум точкам.
Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 9. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 3. Соединяем точку (0;9) с (3;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 3 • 0 + 1 • 0 – 9 ≤ 0, т.е. 3x1+x2 – 9≥ 0 в полуплоскости выше прямой.
Построим уравнение x1+2x2 = 8 по двум точкам.
Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 4. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 8. Соединяем точку (0;4) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 • 0 + 2 • 0 – 8 ≤ 0, т.е. x1+2x2 – 8≥ 0 в полуплоскости выше прямой.
Построим уравнение x1+x2 = 8 по двум точкам.
Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 8. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 8. Соединяем точку (0;8) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 • 0 + 1 • 0 – 8 ≤ 0, т.е. x1+x2 – 8≤ 0 в полуплоскости ниже прямой.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Проверить правильность построения графиков функций можно с помощью калькулятора
Рассмотрим целевую функцию задачи F = 4x1+6x2 → min.
Построим прямую, отвечающую значению функции F = 0: F = 4x1+6x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора – точка (0; 0), конец – точка (4; 6). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Прямая F(x) = 4x1+6x2 пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
3x1+x2=9
x1+2x2=8
Решив систему уравнений, получим: x1 = 2, x2 = 3
Откуда найдем минимальное значение целевой функции:
F(X) = 4*2 + 6*3 = 26
www.reshim.su
Графический метод решения задач линейного программирования
На этом уроке будем знакомиться с графическим методом решения задач линейного программирования, то есть, таких задач, в которых требуется найти такое решения системы линейных уравнений и (или) неравенств (системы ограничений), при котором функция цели – линейная функция – принимает оптимальное значение.
Ввиду того, что наглядность графического решения достигается лишь на плоскости, мы можем познакомиться с графическим представлением задачи только в двумерном пространстве. Это представление пригодно для системы ограничений-неравенств с двумя переменными или для систем уравнений, в которых число переменных на 2 превышает число уравнений, то есть число свободных переменных равно двум.
Поэтому графический метод имеет такие узкие рамки применения, что о нём как об особом методе решения задач линейного программирования говорить нельзя.
Однако для выработки наглядных представлений о решениях задач линейного программирования графический метод представляет определённый интерес. Кроме того, он позволяет геометрически подтвердить справедливость теорем линейного программирования.
Итак, задача линейного программирования. Требуется найти неотрицательные значения переменных и , удовлетворяющих системе неравенств
при которых линейная форма принимает оптимальное значение.
Из теории и практики решения систем линейных неравенств известно, что множество всех решений данной системы, то есть множество пар чисел и , удовлетворяющих системе, составляет многоугольник этой системы. Допустим, что это пятиугольник ABCDE (рисунок внизу).
Линейная форма графически означает семейство параллельных между собой прямых. При конкретном числовом значении F линейная форма изобразится в виде некоторой прямой. Каждую из прямых этого семейства принято называть линией уровня. На рисунке построена линия уровня (чёрного цвета, проходит через начало координат), соответствующая значению F =0.
Если исходную линию уровня передвигать вправо, то значение F при этом возрастает. Нужное направление движения исходной линии уровня можно установить следующим образом. Коэффициенты при переменных в уравнении прямой служат координатами вектора, перпендикулярного этой прямой. Таким образом, получаем градиент – вектор (на рисунке бордового цвета). Значения функции F возрастают при перемещении исходной линии уровня в направлении вектора .
Среди прямых упомянутого семейства параллельных прямых прямые mn (зелёного цвета) и MN (красного цвета), которые назовём опорными. Опорными обычно называют такие прямые, которые имеют с многоугольником ABCDE хотя бы одну общую точку, и многоугольник ABCDE целиком лежит по одну сторону от этой прямой. Как видно из чертежа, прямая mn является опорной, так как она касается многоугольника в точке A и многоугольник целиком лежит правее (или выше) этой прямой. Прямая MN также является опорной, так как имеет с многоугольником общую точку С и многоугольник целиком лежит левее этой прямой.
Из основных теорем линейного программирования известно, что линейная форма достигает максимального и минимального значений в крайних точках многогранника решений. Это значит, что опорные прямые mn и MN характеризуют экстремальные значения линейной формы (функции цели), то есть в точках А и С линейная форма достигает оптимальных значений. В точке А, находящейся ближе к началу координат, функция цели достигает минимального значения, а в точке С, находящейся дальше от начала координат, – максимального значения.
1. Построить многоугольник решений системы неравенств.
3. Двигать прямую (или линейку) вдоль градиента – вектора параллельно линии равных значений в сторону многоугольника решений до соприкосновения с многоугольником решений. Если первая встреча с многоугольником решений произойдёт в крайней точке с координатами , то в этой точке функция цели достигает минимального значения. Если первая встреча произойдёт со стороной многоугольника, то данная функция цели достигает минимума во всех точках этой стороны.
4. Двигаясь дальше, придём к некоторому опорному положению, когда прямая будет иметь одну общую точку с многоугольником решений. В этой точке функция цели достигает своего максимума.
5. Если первоначально построенная линия равных значений пересекает многоугольник решений, то функция цели достигает минимального значения в вершине многоугольника, расположенной ближе к началу координат, а максимального значения – в вершине, более удалённой от начала координат.
Пример 1. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях
Построим многоугольник решений. Для этого начертим граничные прямые. Из первого неравенства запишем уравнение . Это уравнение первой граничной прямой. Найдём точки пересечения этой прямой с осями координат. При из уравнения получим , при получим . Это значит, что первая прямая отсекает от осей координат отрезки и .
Аналогично строим остальные граничные прямые. Вторая прямая от осей координат отсекает отрезки, равные 6. Третья прямая проходит параллельно оси , отсекая на оси отрезок, равный 2. Четвёртая прямая имеет уравнение . Она совпадает с осью .
Из рисунка ниже видно, что множество точек четырёхугольника ABDE удовлетворяет всем четырём неравенствам системы.
Следовательно, четырёхугольник ABDE является многоугольником решений системы (заштрихован вовнутрь).
Начертим линию равных значений функции цели. Приняв в равенстве F =1, получим, что эта линия отсекает отрезки 1 и 1/3 соответственно на оси и на оси . Проведём прямую через эти точки (на чертеже она чёрного цвета).
Двигая эту прямую параллельно самой себе в направлении градиента – вектора (бордового цвета), получим опорные прямые. Первая прямая (зелёного цвета) имеет с многоугольником общую точку A. Здесь функция цели достигает минимума. Двигаясь дальше, придём к точке В. Здесь максимум. Координаты точки В: (2, 4). Подставляя в функцию цели координаты точки В, т. е. , , получим максимальное значение функции цели: .
На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.
Пример 3. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях
где .
Правильное решение и ответ.
Пример 4. Решить графическим методом задачу линейного программирования, в которой требуется найти минимум функции при ограничениях
где .
Правильное решение и ответ.
До сих пор полученные выводы были основаны на том, что множество решений задачи линейного программирования сконфигурировано так, что оптимальное решение конечно и единственно. Теперь рассмотрим примеры, когда это условие нарушается. В этих примерах многоугольник решений строится так, как показано в предыдущих примерах, остановимся же на признаках, которые отличают эти исключительные примеры.
Пример 5. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях
Решение. На рисунке изображены: неограниченная многогранная область решений данной системы ограничений, исходная линия уровня (чёрного цвета), вектор (бордового цвета), указывающий направление движения исходной линии уровня для нахождения максимума целевой функции.
Легко заметить, что функция F может неограниченно возрастать при заданной системе ограничений, поэтому можно условно записать, что .
На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.
Пример 6. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях
Решение. Изображённая на рисунке ниже область не содержит ни одной общей точки, которая бы удовлетворяла всем неравенствам системы ограничений. То есть система ограничений противоречива и не может содержать ни одного решения, в том числе и оптимального.
На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.
На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.
Пример 8. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях
Решение. На рисунке ниже изображены область решений системы ограничений и линия уровня (чёрного цвета). Если передвигать линию уровня параллельно исходной в направлении вектора , то она выйдет из области решений не в одной точке, как это было в предыдущих примерах, а сольётся с прямой CD, которая является граничной линией области решений.
Все точки отрезка CD дают одно и то же значение функции цели, которое и служит её оптимальным значением: . Следовательно, имеется не одно, а бесчисленное множество оптимальных решений, совпадающих с точками отрезка CD, в частности, с двумя угловыми точками C и D. Этот пример показывает, что в некоторых случаях единственность оптимального решения нарушается.
На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.
Напоследок следует заметить, что строить многогранник решений можно и другим способом, отличающимся о того, который мы рассматривали. А именно: можно не искать точки пересечения прямых с осями координат, а искать точки пересечения прямых. Для этого последовательно решаются системы из двух уравнений, так, чтобы решениями были точки пересечения всех прямых. Полученные точки и будут вершинами многогранника решений. Этот способ иногда бывает удобным в случаях, когда точки пересечения прямых с осями координат – дробные числа и, неправильно отложив точку пересечения, можно получить ошибку и в поиске точек пересечения самих прямых.
Начало темы “Линейное программирование”
Поделиться с друзьями
function-x.ru
Онлайн-калькулятор:Графический метод решения ЗЛП
Решение задач линейного программирования графическим методом
Необходимо найти максимальное значение целевой функции F = 10x1+20x2 → max, при системе ограничений:
|
x1+3.5x2≤350 |
(1) |
|
2x1+0.5x2≤240 |
(2) |
|
x1+x2≤150 |
(3) |
|
x2≥60 |
(4) |
|
x1≥0 |
(5) |
|
x2≥0 |
(6) |
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Построим уравнение x1+3.5x2 = 350 по двум
точкам. Для нахождения первой точки приравниваем x1 = 0.
Находим x2 = 100. Для нахождения второй точки
приравниваем x2 = 0. Находим x1 = 350.
Соединяем точку (0;100) с (350;0) прямой линией.
Построим уравнение 2x1+0.5x2 = 240 по двум
точкам. Для нахождения первой точки приравниваем x1 = 0.
Находим x2 = 480. Для нахождения второй точки
приравниваем x2 = 0. Находим x1 = 120.
Соединяем точку (0;480) с (120;0) прямой линией.
Построим уравнение x1+x2 = 150 по двум
точкам. Для нахождения первой точки приравниваем x1 = 0.
Находим x2 = 150. Для нахождения второй точки
приравниваем x2 = 0. Находим x1 = 150.
Соединяем точку (0;150) с (150;0) прямой линией.
Построим уравнение x2 = 60. Эта прямая проходит через
точку x2 = 60 параллельно оси OX1.
или
Границы области допустимых решений
Пересечением полуплоскостей будет являться
область, координаты точек которого удовлетворяют условию
неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи F =
10x1+20x2 → max.
Построим прямую, отвечающую значению функции F = 0: F =
10x1+20x2 = 0. Вектор-градиент, составленный
из коэффициентов целевой функции, указывает направление
максимизации F(X). Начало вектора – точка (0; 0), конец – точка
(10; 20). Будем двигать эту прямую параллельным образом. Поскольку
нас интересует максимальное решение, поэтому двигаем прямую до
последнего касания обозначенной области. На графике эта прямая
обозначена пунктирной линией.
Равный масштаб
Область допустимых решений представляет собой многоугольник
Прямая F(x) = const пересекает область в
точке C. Так как точка C получена в результате пересечения прямых
(1) и (3), то ее координаты удовлетворяют уравнениям
этих прямых:
x1+3.5x2≤350
x1+x2≤150
Решив систему уравнений, получим: x1 = 70, x2
= 80
Откуда найдем максимальное значение целевой функции:
F(X) = 10*70 + 20*80 = 2300
Подробнее о том, как находить область допустимого решения
Для данного решения имеются ряд замечаний (см. ниже).
Для исходных данных также доступны следующие действия:
Начало формы
Конец формы
xreff.ru