Сервис для решения задач по линейному программированию

Пусть хорошие люди смотрят хорошие решения
English

Пример №5. Решение задачи линейного программирования симплекс методом.
Решение не единственное

Данное решение является образцом работы программы, представленной на сайте.
Задача:

Найти наибольшее значение функции
F = x1 + 2 x2
при следующих ограничениях:
Знак системы x1 + 2 x2 6
2 x1 + x2 8
x2 2
x1 ≥ 0    x2 ≥ 0    

Решение:

1. Свободные члены системы должны быть неотрицательными.
Данное условие выполнено.

2. Каждое ограничение системы должно представлять собой уравнение.
Знак системы x1 + 2 x2 6
2 x1 + x2 8
x2 2
Знак системы x1 + 2 x2 + S1 = 6
2 x1 + x2 + S2 = 8
x2 + S3 = 2
S1 ≥ 0, S2 ≥ 0, S3 ≥ 0.   Введенные переменные S1, S2, S3, называются балансовыми переменными.

3. Нахождение начального базиса и значения функции F, которое соответствует найденному начальному базису.

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

В чем заключается идея симплекс метода?
Каждому базису соответствует единственное значение функции. Одно из них является наибольшим значением функции F.
Мы будем переходить от одного базиса к другому.
Следующий базис будем выбирать таким образом, чтобы получить значение функции F не меньше имеющегося.
Очевидно, количество возможных базисов для любой задачи число не очень большое.
Следовательно, рано или поздно, ответ будет получен.

Как осуществляется переход от одного базиса к другому?
Запись решения удобнее вести в виде таблиц. Каждая строка таблицы эквивалентна уравнению системы. Выделенная строка состоит из коэффициентов функции (см. таблицу ниже). Это позволяет не переписывать переменные каждый раз, что существенно экономит время.
B выделенной строке выбираем наибольший положительный коэффициент (можно выбрать любой положительный).
Это необходимо для того, чтобы получить значение функции F не меньше имеющегося.
Выбран столбец.
Для положительных коэффициентов выбранного столбца считаем отношение Θ и выбираем наименьшее значение.
Это необходимо для того, чтобы после преобразования столбец свободных членов остался неотрицательным.
Выбрана строка.
Определен элемент, который будет базисным. Далее считаем.

В нашей системе есть базис?
Знак системы x1 + 2 x2 + S1 = 6
2 x1 + x2 + S2 = 8
x2 + S3 = 2
Базис есть, т.е. мы можем начать решение.
F = x1 + 2 x2
Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. систему)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно.
x1 = 0   x2 = 0  
S1 = 6   S2 = 8   S3 = 2  
=> F = 0
Начальный базис найден и получено значение функции F, соответствующее найденному базису.

4. Нахождение наибольшего значения функции F.

Шаг №1
x1 x2 S1 S2 S3 св. член Θ
1 2 1 0 0 6 6 : 2 = 3
2 1 0 1 0 8 8 : 1 = 8
0 1 0 0 1 2 2 : 1 = 2
1 2 0 0 0 F - 0
1 0 1 0 -2 2
2 0 0 1 -1 6
0 1 0 0 1 2
1 0 0 0 -2 F - 4
Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно. (см. выделенную строку таблицы)
x1 = 0   S3 = 0  
x2 = 2   S1 = 2   S2 = 6  
=> F - 4 = 0   => F = 4

Шаг №2
x1 x2 S1 S2 S3 св. член Θ
1 0 1 0 -2 2 2 : 1 = 2
2 0 0 1 -1 6 6 : 2 = 3
0 1 0 0 1 2
1 0 0 0 -2 F - 4
1 0 1 0 -2 2
0 0 -2 1 3 2
0 1 0 0 1 2
0 0 -1 0 0 F - 6
Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно. (см. выделенную строку таблицы)
S1 = 0   S3 = 0  
x1 = 2   x2 = 2   S2 = 2  
=> F - 6 = 0   => F = 6
Среди коэффициентов выделенной строки нет положительных. Следовательно, найдено наибольшее значение функции F.
В столбце 5 коэффициент в выделенной строке равен нулю, а базисной переменной нет.
Это позволяет сделать вывод о том, что можно найти еще одно решение при котором F = 6.

Шаг №3
x1 x2 S1 S2 S3 св. член Θ
1 0 1 0 -2 2
0 0 -2 1 3 2 2 : 3 ≈ 0,67
0 1 0 0 1 2 2 : 1 = 2
0 0 -1 0 0 F - 6
1 0 1 0 -2 2
0 0 -2/3 1/3 1 2/3
0 1 0 0 1 2
0 0 -1 0 0 F - 6
1 0 -1/3 2/3 0 10/3
0 0 -2/3 1/3 1 2/3
0 1 2/3 -1/3 0 4/3
0 0 -1 0 0 F - 6
Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно. (см. выделенную строку таблицы)
S1 = 0   S2 = 0  
x1 = 10/3   x2 = 4/3   S3 = 2/3  
=> F - 6 = 0   => F = 6
С геометрической точки зрения, оба полученных решения являются точками пространства, т.е. образуют отрезок.
Любая точка (любое решение), принадлежащая данному отрезку, также будет являться решением.
Ответ:

X1 = 2 * t + 10/3 * (1 - t)

X2 = 2 * t + 4/3 * (1 - t)

где   0 ≤ t ≤ 1

Fmax = 6


Это интересно:
На каждом шаге значение функции изменяется на величину равную произведению выбранного коэффициента выделенной строки на Θmin. Если числа позволяют, можете в этом убедиться самостоятельно.








© 2010-2020 Если у Вас есть замечания, пожалуйста, пишите matematika1974@yandex.ru


Ссылки