Решение задач симплекс методом – онлайн калькулятор

Форма ввода исходных данных для решения задачи симплекс методом с помощью онлайн калькулятора

Онлайн калькулятор для решения задачи симплекс методом. Первый опорный план можно рассчитать тремя способами: методом искусственного базиса (М-метод), двухшаговым или базовым методами. Ввод данных расчета возможен в виде обыкновенных или десятичных дробей.

Содержание

См. также:

Онлайн калькулятор

Исходные данные задачи

Открыть в новой вкладке с параметрами по умолчанию

Руководство по использованию калькулятора

Задачи, решаемые с помощью данного калькулятора

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

Общая задача линейного программирования формулируется следующим образом.
Найти максимум (минимум) линейной функции n переменных :
(1)
при ограничениях вида
(2) $\left\{\begin{aligned}a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n&=b_1\\............................&....\\a_{p1}x_1+a_{p2}x_2+\cdots+a_{pn}x_n&=b_p\\a_{p+1,1}x_1+a_{p+1,2}x_2+\cdots+a_{p+1,n}x_n&\leqslant b_{p+1}\\.....................................&.......\\a_{p+q,1}x_1+a_{p+q,2}x_2+\cdots+a_{p+q,n}x_n&\leqslant b_{p+q}\\a_{p+q+1,1}x_1+a_{p+q+1,2}x_2+\cdots+a_{p+q+1,n}x_n&\geqslant b_{p+q+1}\\..........................................&.........\\a_{p+q+s,1}x_1+a_{p+q+s,2}x_2+\cdots+a_{p+q+s,n}x_n&\geqslant b_{p+q+s}\end{aligned}\right.$
(3) .

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

Краткое описание симплексного метода

Суть симплекс метода заключается в том, что мы все неравенства сводим к простейшему виду:
(4) .
Это достигается введением дополнительных неотрицательных переменных . Тогда неравенства преобразуются в равенства, и вместо (2) получается система уравнений:
(5) $\left\{\begin{aligned}a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n&=b_1\\............................&....\\a_{p1}x_1+a_{p2}x_2+\cdots+a_{pn}x_n&=b_p\\a_{p+1,1}x_1+a_{p+1,2}x_2+\cdots+a_{p+1,n}x_n-x_{n+1}&=b_{p+1}\\.....................................&.......\\a_{p+q,1}x_1+a_{p+q,2}x_2+\cdots+a_{p+q,n}x_n-x_{n+q}&= b_{p+q}\\a_{p+q+1,1}x_1+a_{p+q+1,2}x_2+\cdots+a_{p+q+1,n}x_n+x_{n+q+1}&= b_{p+q+1}\\..........................................&.........\\a_{p+q+s,1}x_1+a_{p+q+s,2}x_2+\cdots+a_{p+q+s,n}x_n+x_{n+q+s}&=b_{p+q+s}\end{aligned}\right.$

Если приравнять часть переменных к нулю, то можно найти значения остальных, решая систему линейных уравнений (5) (если уравнения линейно независимы). Такое решение является опорным планом. Нулевые переменные называются свободными. Переменные, значения которых определяются из системы уравнений, называются базисными, а их совокупность – базисом. Таким образом задача сводится к тому, чтобы найти такой базис, в котором целевая функция (1) имеет экстремальное значение.

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

1. Определяется первый опорный план, не обязательно оптимальный. Если это невозможно, то решения не существует – ограничения (2), (3) не выполняются ни при каких значениях переменных.
2. Выбирается переменная, входящая в базис из условия наибольшего увеличения (уменьшения) целевой функции. Если такой переменной нет, то задача решена – целевая функция достигла максимума (минимума).
3. Определяется переменная, выходящая из базиса из условия, чтобы неотрицательные переменные оставались неотрицательными. Если этого сделать нельзя, то решения не существует, поскольку целевая функция может иметь сколь угодно большое (малое) значение.

Методы построения первого опорного плана

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

1. Метод искусственного базиса или М-метод. В нем вводятся искусственные переменные , и добавляются по одной в каждое уравнение системы:
.
Поскольку выражаются через остальные переменные:
,
то из них можно составить базис. Также искусственные переменные вводят в целевую функцию, но так, чтобы в экстремуме они обратились в нуль:
, или
,
где – очень большое положительное число. Далее, стандартным симплекс-методом, решается видоизмененная задача. Если первый опорный план исходной задачи существует, то искусственные переменные выходят из базиса. Если нет, то исходная задача решения не имеет.

2. Двухшаговый метод.
В двухшаговом методе также вводятся искусственные переменные , как и в М-методе. Только вначале решается вспомогательная задача с целевой функцией
.
Если ее решением является решение с нулевыми значениями искусственных переменных, то получаем базис, который используем в качестве первого опорного плана для решения основной задачи. В противном случае исходная система ограничений несовместна, задача не имеет решения.

3. Базовый симплекс-метод.
В базовом симплекс-методе вначале получают частное решение системы уравнений, игнорируя условия неотрицательности переменных. Если система совместна, то получают решение, в котором одни переменные выражены через другие. Из первых переменных составляют базис. При этом может оказаться, что для некоторых базисных переменных условия неотрицательности не выполняются. Тогда производят преобразования Жордана-Гаусса, с целью уменьшения числа переменных, нарушающих условия . Если удалось построить базис, в котором неотрицательные переменные принимают неотрицательные значения, то этот базис будет первым опорным планом. Если нет, то система ограничений несовместна, задача решения не имеет.

Ввод исходных данных

Исходными данными являются:
число переменных ;
число уравнений системы ограничений (2);
коэффициенты линейной формы целевой функции (1);
тип экстремума целевой функции (максимум или минимум);
коэффициенты и свободные члены системы ограничений (2);
тип ограничения (≤, ≥ или =);
наличие ограничений неотрицательности переменных (x_j ≥ 0 или x_j любое);
метод расчета начального опорного плана (искусственного базиса, двухшаговый или базовый);
дроби – обыкновенные или десятичные.

Существует два способа ввода данных:
1. В виде единой таблицы.
2. Ввод каждого значения по отдельности.

Ввод данных единой таблицей

В этом способе все данные вводятся в одно текстовое поле. Разделителем строк служит перевод новой строки; разделителем столбцов – любая последовательность символов, отличных от перевода новой строки, цифры, буквы, точки, запятой, знаков '+', '-', '=', '<', '>'.
Первая строка таблицы содержит значения коэффициентов целевой функции и тип экстремума: 'min' или 'max'.
В последующих n строках вводят коэффициенты системы ограничений, вид ограничения ('≤=', '≥=' или '=') и значения свободных членов .
В последней строке вводят условия неотрицательности переменных:
'+' – если переменная неотрицательная;
'+-' – если переменная может иметь любое значение.

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

Ввод данных по отдельности

Каждое значение можно вводить по отдельности. Для этого нужно ввести число переменных и число ограничений, и нажать кнопку Применить.
Далее можно изменить любое значение в последующих полях ввода.
При нажатии на кнопку Рассчитать производится проверка правильности заполнения ячеек и расчет решения задачи.

Погрешность вычислений

Чтобы получить точный результат без округлений, нужно выполнить следующие условия.
1. В строке Дроби выбрать 'Обыкновенные'.
2. Все числовые значения должны вводится либо целыми без десятичной запятой (или точки), либо в виде обыкновенных дробей. Например: '3', '0', '-12', '5/6'.
Если при вводе данных, хотя бы в одном поле, встретится запятая или точка, то все числовые величины будут округляться, и отображаться в виде десятичных дробей.

Чтобы получить приближенный результат в виде десятичных дробей, нужно в строке Дроби выбрать 'Десятичные', и указать число значащих цифр. Оно используется только для отображения данных расчета, и не оказывает влияния на точность. При расчете используются числа с 15-ю знаками не зависимо от выбранного значения числа значащих цифр.

Ввод числовых данных

Ввод натуральных чисел выполняется, как обычно, в виде последовательности цифр 0 – 9.
Перед отрицательными числами ставится знак минус без пробела.
Обыкновенные дроби вводят с использованием косой черты без пробелов, которая отделяет числитель от знаменателя. Например: 5/2.
Десятичные дроби, для расчетов с округлением, вводят, используя в качестве разделителя запятую или точку. Например: 0,1254.

Сохранение данных расчета

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

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

Чтобы очистить все данные, нужно нажать на ссылку Открыть в новой вкладке с параметрами по умолчанию. Она расположена в начале страницы.

Автор: Олег Одинцов. Опубликовано: 19-02-2024

См. также:

Число переменных
Число ограничений