Данный онлайн калькулятор решает задачу линейного программирования в основной форме. Дается подробное решение с пояснениями. Для решения задачи линейного программирования задайте количество ограничений и количество переменных. Затем введите данные в ячейки. Введите номера строк (в количесте равной количеству переменных задачи) через запятую, которые входят в базис и нажимайте на кнопку "Вычислить". Теоретическую часть смотрите ниже.
Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.
Данная статья предназначена для тех, кто хочет более углубленно изучить симплекс-метод, понять как он работает. Онлайн калькулятор на данной странице позволяет экспентировать при решении задачи линейного программирования (ЛП) и понять, как этот метод позволяет перейти от одного допустимого плана к другому и при этом увеличить значение целевой функции при задаче на максимум, или уменьшить значение целевой функции, при задаче на минимум.
Рассмотрим следующую задачу линейного программирования в основной форме:
 |
 |
Запишем данную задачу ЛП в матричном виде:
 |
(1a) |
 |
(1b) |
где \( \small C-1×n- \) вектор-строка, \( \small X-n×1- \) вектор-столбец, \( \small A-m×n- \) матрица ранга n, \( \small B-m×1- \) вектор столбец.
Пусть \( \small X_0- \) допустимый план задачи ЛП (1a)-(1b) и пусть первые n неравенства в (1b) удовлетворяются как равенства и соответствующим этим неравенствам векторы строки матрицы \( \small A\) линейно независимы. Это означает, что \( \small X_0 \) является вершиной выпуклого многогранного множества (1b). Тогда
 |
(2) |
 |
(3) |
где 
, \( \small A_Б-n×n- \) матрица ранга n, составленная из базисных векторов-строк матрицы A, \( \small A_Н-m-n×n- \) матрица, составленная из небазисных векторов-строк матрицы A,
, \( \small B_Б-n×1- \) вектор-столбец, соответствующий базисным векторам матрицы A, \( \small B_Н-m-n×1- \) вектор-столбец, соответствующий небазисным векторам матрицы A.
Наша цель переместиться из вершины \( \small X_0 \) до другой вершины выпуклого многогранного множества (1b) так, чтобы значение целевой функции в новой точке был не меньше, чем в вершине \( \small X_0 \).
Вычислим обратную \( \small A_Б^{-1}\) к матрице \( \small A_Б \). Заметим, что
  |
(4) |
Из (4) следует
 |
(5) |
Запишем уравнение прямой, по которому нужно двигаться от точки \( \small X_0 \) по одному из ребер выпуклого многогранного множества (1b):
 |
(6) |
При движении от точки \( \small X_0 \) по ребру выпуклого многогранного множества, новая точка (вершина) должна удовлетворять системе линейных неравенств (1b). Тогда, подставляя (6 ) в (1b), получим:
 , |
 . |
Далее, учитывая, что , получим:
 , |
(7) |
 . |
(8) |
А исходя из (2) и (5) неравенство (7) можно записать так:
 |
(9) |
Запишем систему линейных неравенств (ЛН)(8) в развернутом виде:
  |
(10) |
Поскольку правая часть системы ЛН (10) неотрицательна (см неравенство (3)), то при \( \small a_{Нi}a_{Бp}^{-1} \gt 0 \;\;t \) получится больше нуля. Но из условия (9) следует неположительность параметра t. Следовательно будем учитывать те неравенства (10), при которых \( \small a_{Нi}a_{Бp}^{-1} \lt 0 \). Найдем t из (10):
  |
(11) |
Мы не учли один момент. В (6) мы выбрали некоторый столбец \( \small a_{Бp}^{-1} \) из матрицы \( \small A_Б^{-1} \). Но нужно выбрать такой столбец из матрицы \( \small A_Б^{-1} , \) при котором целевая функция не уменьшалась. Подставим (6) в (1a):
 |
(12) |
Как видно из (12), для того, чтобы значение целевой функции \( \small CX \) увеличилось максимально, \( \small t \cdot Ca_{Бp}^{-1} \) должен быть максимально большим. Но так следует из (8) t неположительное число. Поэтому мы должны выбрать \( \small t \cdot Ca_{Бp}^{-1} \lt 0 \). Следовательно вычисляем:
 . |
(13) |
Далее выбираем один из столбцов p матрицы \( \small t \cdot A_{Б}^{-1} \), при котором \( \small Ca_{Бp}^{-1} \lt 0.\) Чтобы максимально увеличить целевую функцию, выбираем самый большой по модулю отрицательный элемент вектора (13) и соответствующую к нему вектор столбец \( \small a_{Бp}^{-1} .\)
Далее, возвращаяясь к выражению (12), находим t и подставляя в (6) находим новый план задачи (1a)-(1b). Отмечаем буквой q строку A, при которой t принял максимальное значение. Таким образом, в базис входит вектор-строка q, а из базиса выходит вектор-строка p матрицы A. Далее, взьяв в качестве исходного новый план, продолжаем процедуру.
Если на каком-то этапе решения задачи \( \small t \cdot Ca_{Бp}^{-1} \ge 0 ,\) то текущий план является решением задачи ЛП (1a)-(1b).
Можно с легкостью найти также оптимальный план двойственной задачи. Из условия дополняющей нежесткости для задачи ЛП (1a)-(1b) имеем:
| \(\small Y^*(B-AX^*)=0, \) | (14) |
где \(\small Y^*-1×m - \) вектор-строка − оптимальный план задачи ЛП двойственной к (1a)-(1b), \(\small X^*-n×1 - \) вектор-столбец − оптимальный план задачи ЛП (1a)-(1b).
Запишем (14) так:
 |
(15) |
или
  |
Из (2) и (3) следует, что для того, чтобы левая часть выражения (15) была равна нулю достаточно, чтобы \( \small Y_Н^*=0. \)
Чтобы \( \small Y^* \) была допустимой точкой задачи ЛП двойственной к (1a)-(1b), \( \small Y^* \) должна удовлетворять условиям
| \(\small Y^*A=C,\;\; Y^* \ge 0\) |
или
| \(\small (Y_Б^*,Y_Н^*)A=C,\;\; (Y_Б^*,Y_Н^*) \ge 0\) |
Тогда имеем:
 |
или
 |
Учитывая, что \(\small Y_Н^*=0, \) получим:
 |
Откуда:
 |
Следовательно, оптимальный план двойственной к задаче ЛП(1a)-(1b) будет вектор:
| \(\small Y^*=(Y_Б^*,Y_Н^*)=(CA_Б^{-1},0 ) \) |
0 − вектор-строка порядка \( \small 1×m-n \).
В заключении отметим, что на каждом шаге решения задачи можно найти псевдоплан \(\small Y_0 \) :
| \(\small Y_0=(CA_Б^{-1},0 ) \) |
Заметим, что хотя и псевдоплан удовлетворяет условию дополняющей нежесткости (14), но в его компонентах есть отрицательные элементы. А когда все элементы псевдоплана оказываются неотрицательными, то псевдоплан становится планом и одновременно оптимальным планом задачи двойственной к (1a)-(1b).
Таким образом алгоритм решения задачи ЛП в основной форме содержит следующие шаги:
1. Выбираем базисные векторы из числа строка матрицы A в количестве, равной количеству переменных исходной задачи.
2. Из базисных векторов составляем матрицу \( \small A_Б \) и вычисляем обратное к нему матрицу \( \small A_Б^{-1} \).
3. Вычисляем текущий опорный план из выражения \( \small X_0=A_Б^{-1} B_Б \).
4. Вычисляем произведение \( \small CA_Б^{-1} \).
5. Если среди координат вектора \( \small CA_Б^{-1} \) нет отрицательных, то переходим к пункту 10.
6. Находим самый большой по модулю отрицательный элемент из вектора \( \small СA_Б^{-1} \) и соответствующий столбец p матрицы \( \small A_Б^{-1} \) и обозначим через \( \small a_{Бp}^{-1}. \)
7. Находим t из
| |
и фиксируем номер q того неравенства, при котором достигается максимальное значение t.
7. Находим новый опорный план из равенства:
|
8. Строим новый базис \( \small A_Б \). Для этого из базиса выводим строку p и вводим в базис строку q.
9. Переходим к пункту 2.
10. Текущий план \( \small X^*=X_0 \) является оптимальным. Вычисляем значение целевой функции в оптимальной точке: \( \small F=CX^*. \)
Для просмотра примеров решения, введите данные на онлайн калькулятор выше, задайте начальный базис в виде номеров строк матрицы A через запятую и нажмите на кнопку "Вычислить". Калькулятор представит решение задачи ЛП подробно, по шагам. Для решения задачи линейного программирования обычным симплекс методом используйте калькулятор Симплекс метод онлайн.
Представленный в данной статье метод решения задачи ЛП является аналогом двойственного симплекс метода. В этой статье мы разобрали этот метод для задачи, записанной в основной форме, в то время как двойственный симплекс метод рассматривает решение задачи двойственной к основной форме, т.е. в канонической форме.