Данный онлайн калькулятор решает задачу линейного программирования в основной форме. Дается подробное решение с пояснениями. Для решения задачи линейного программирования задайте количество ограничений и количество переменных. Затем введите данные в ячейки. Введите номера строк (в количесте равной количеству переменных задачи) через запятую, которые входят в базис и нажимайте на кнопку "Вычислить". Теоретическую часть смотрите ниже.
Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.
Данная статья предназначена для тех, кто хочет более углубленно изучить симплекс-метод, понять как он работает. Онлайн калькулятор на данной странице позволяет экспентировать при решении задачи линейного программирования (ЛП) и понять, как этот метод позволяет перейти от одного допустимого плана к другому и при этом увеличить значение целевой функции при задаче на максимум, или уменьшить значение целевой функции, при задаче на минимум.
Рассмотрим следующую задачу линейного программирования в основной форме:
![]() |
![]() |
Запишем данную задачу ЛП в матричном виде:
![]() |
(1a) |
![]() |
(1b) |
где C−1×n− вектор-строка, X−n×1− вектор-столбец, A−m×n− матрица ранга n, B−m×1− вектор столбец.
Пусть X0− допустимый план задачи ЛП (1a)-(1b) и пусть первые n неравенства в (1b) удовлетворяются как равенства и соответствующим этим неравенствам векторы строки матрицы A линейно независимы. Это означает, что X0 является вершиной выпуклого многогранного множества (1b). Тогда
![]() |
(2) |
![]() |
(3) |
где , AБ−n×n− матрица ранга n, составленная из базисных векторов-строк матрицы A, AН−m−n×n− матрица, составленная из небазисных векторов-строк матрицы A,
, BБ−n×1− вектор-столбец, соответствующий базисным векторам матрицы A, BН−m−n×1− вектор-столбец, соответствующий небазисным векторам матрицы A.
Наша цель переместиться из вершины X0 до другой вершины выпуклого многогранного множества (1b) так, чтобы значение целевой функции в новой точке был не меньше, чем в вершине X0.
Вычислим обратную A−1Б к матрице AБ. Заметим, что
![]() ![]() |
(4) |
Из (4) следует
![]() |
(5) |
Запишем уравнение прямой, по которому нужно двигаться от точки X0 по одному из ребер выпуклого многогранного множества (1b):
![]() |
(6) |
При движении от точки X0 по ребру выпуклого многогранного множества, новая точка (вершина) должна удовлетворять системе линейных неравенств (1b). Тогда, подставляя (6 ) в (1b), получим:
![]() |
![]() |
Далее, учитывая, что ,
получим:
![]() |
(7) |
![]() |
(8) |
А исходя из (2) и (5) неравенство (7) можно записать так:
![]() |
(9) |
Запишем систему линейных неравенств (ЛН)(8) в развернутом виде:
![]() ![]() |
(10) |
Поскольку правая часть системы ЛН (10) неотрицательна (см неравенство (3)), то при aНia−1Бp>0t получится больше нуля. Но из условия (9) следует неположительность параметра t. Следовательно будем учитывать те неравенства (10), при которых aНia−1Бp<0. Найдем t из (10):
![]() ![]() |
(11) |
Мы не учли один момент. В (6) мы выбрали некоторый столбец a−1Бp из матрицы A−1Б. Но нужно выбрать такой столбец из матрицы A−1Б, при котором целевая функция не уменьшалась. Подставим (6) в (1a):
![]() |
(12) |
Как видно из (12), для того, чтобы значение целевой функции CX увеличилось максимально, t⋅Ca−1Бp должен быть максимально большим. Но так следует из (8) t неположительное число. Поэтому мы должны выбрать t⋅Ca−1Бp<0. Следовательно вычисляем:
![]() |
(13) |
Далее выбираем один из столбцов p матрицы t⋅A−1Б, при котором Ca−1Бp<0. Чтобы максимально увеличить целевую функцию, выбираем самый большой по модулю отрицательный элемент вектора (13) и соответствующую к нему вектор столбец a−1Бp.
Далее, возвращаяясь к выражению (12), находим t и подставляя в (6) находим новый план задачи (1a)-(1b). Отмечаем буквой q строку A, при которой t принял максимальное значение. Таким образом, в базис входит вектор-строка q, а из базиса выходит вектор-строка p матрицы A. Далее, взьяв в качестве исходного новый план, продолжаем процедуру.
Если на каком-то этапе решения задачи t⋅Ca−1Бp≥0, то текущий план является решением задачи ЛП (1a)-(1b).
Можно с легкостью найти также оптимальный план двойственной задачи. Из условия дополняющей нежесткости для задачи ЛП (1a)-(1b) имеем:
Y∗(B−AX∗)=0, | (14) |
где Y∗−1×m− вектор-строка − оптимальный план задачи ЛП двойственной к (1a)-(1b), X∗−n×1− вектор-столбец − оптимальный план задачи ЛП (1a)-(1b).
Запишем (14) так:
![]() |
(15) |
или
![]() ![]() |
Из (2) и (3) следует, что для того, чтобы левая часть выражения (15) была равна нулю достаточно, чтобы Y∗Н=0.
Чтобы Y∗ была допустимой точкой задачи ЛП двойственной к (1a)-(1b), Y∗ должна удовлетворять условиям
Y∗A=C,Y∗≥0 |
или
(Y∗Б,Y∗Н)A=C,(Y∗Б,Y∗Н)≥0 |
Тогда имеем:
![]() |
или
![]() |
Учитывая, что Y∗Н=0, получим:
![]() |
Откуда:
![]() |
Следовательно, оптимальный план двойственной к задаче ЛП(1a)-(1b) будет вектор:
Y∗=(Y∗Б,Y∗Н)=(CA−1Б,0) |
0 − вектор-строка порядка 1×m−n.
В заключении отметим, что на каждом шаге решения задачи можно найти псевдоплан Y0 :
Y0=(CA−1Б,0) |
Заметим, что хотя и псевдоплан удовлетворяет условию дополняющей нежесткости (14), но в его компонентах есть отрицательные элементы. А когда все элементы псевдоплана оказываются неотрицательными, то псевдоплан становится планом и одновременно оптимальным планом задачи двойственной к (1a)-(1b).
Таким образом алгоритм решения задачи ЛП в основной форме содержит следующие шаги:
1. Выбираем базисные векторы из числа строка матрицы A в количестве, равной количеству переменных исходной задачи.
2. Из базисных векторов составляем матрицу AБ и вычисляем обратное к нему матрицу A−1Б.
3. Вычисляем текущий опорный план из выражения X0=A−1БBБ.
4. Вычисляем произведение CA−1Б.
5. Если среди координат вектора CA−1Б нет отрицательных, то переходим к пункту 10.
6. Находим самый большой по модулю отрицательный элемент из вектора СA−1Б и соответствующий столбец p матрицы A−1Б и обозначим через a−1Бp.
7. Находим t из
![]() ![]() |
и фиксируем номер q того неравенства, при котором достигается максимальное значение t.
7. Находим новый опорный план из равенства:
![]() |
8. Строим новый базис AБ. Для этого из базиса выводим строку p и вводим в базис строку q.
9. Переходим к пункту 2.
10. Текущий план X∗=X0 является оптимальным. Вычисляем значение целевой функции в оптимальной точке: F=CX∗.
Для просмотра примеров решения, введите данные на онлайн калькулятор выше, задайте начальный базис в виде номеров строк матрицы A через запятую и нажмите на кнопку "Вычислить". Калькулятор представит решение задачи ЛП подробно, по шагам. Для решения задачи линейного программирования обычным симплекс методом используйте калькулятор Симплекс метод онлайн.
Представленный в данной статье метод решения задачи ЛП является аналогом двойственного симплекс метода. В этой статье мы разобрали этот метод для задачи, записанной в основной форме, в то время как двойственный симплекс метод рассматривает решение задачи двойственной к основной форме, т.е. в канонической форме.