Логотип

Решение задач по математике онлайн

Главная >> Пример №5. Симплекс метод. Решение не единственное.

Симплекс метод

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

Задача:

Найти наибольшее значение функции
F = 2 x1 + 4 x2 + x3
при следующих ограничениях:

Знак системы - 2 x1 + 3 x2 + x3 36
x1 + 2 x2 + 2 x3 45
2 x1 - x2 - 3 x3 30

x1 ≥ 0    x2 ≥ 0    x3 ≥ 0    

Решение:

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

2. Каждое ограничение системы должно представлять собой уравнение.

Знак системы - 2 x1 + 3 x2 + x3 36
x1 + 2 x2 + 2 x3 45
2 x1 - x2 - 3 x3 30


Знак системы - 2 x1 + 3 x2 + x3 + S1 = 36
x1 + 2 x2 + 2 x3 + S2 = 45
2 x1 - x2 - 3 x3 + S3 = 30

S1 ≥ 0, S2 ≥ 0, S3 ≥ 0.   Введенные переменные S1, S2, S3, называются балансовыми переменными.

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

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

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

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

Знак системы - 2 x1 + 3 x2 + x3 + S1 = 36
x1 + 2 x2 + 2 x3 + S2 = 45
2 x1 - x2 - 3 x3 + S3 = 30

F = 2 x1 + 4 x2 + x3

Приравниваем свободные переменные нулю, устно находим значения базисных переменных.
Функция F выражена через свободные переменные, следовательно, ее значение для данного решения можно найти мгновенно.
x1 = 0   x2 = 0   x3 = 0  
S1 = 36   S2 = 45   S3 = 30  
=> F = 0
Начальный базис найден и получено значение функции F соответствующее найденному базису.

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

Шаг №1
x1 x2 x3 S1 S2 S3 св. член Θ
-2 3 1 1 0 0 36 36 : 3 = 12
1 2 2 0 1 0 45 45 : 2 ≈ 22,50
2 -1 -3 0 0 1 30
2 4 1 0 0 0 F - 0
-2/3 1 1/3 1/3 0 0 12
1 2 2 0 1 0 45
2 -1 -3 0 0 1 30
2 4 1 0 0 0 F - 0
-2/3 1 1/3 1/3 0 0 12
7/3 0 4/3 -2/3 1 0 21
4/3 0 -8/3 1/3 0 1 42
14/3 0 -1/3 -4/3 0 0 F - 48

Приравниваем свободные переменные нулю, устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные, следовательно, ее значение для данного решения можно найти мгновенно. (см. таблицу)
x1 = 0   x3 = 0   S1 = 0  
x2 = 12   S2 = 21   S3 = 42  
=> F - 48 = 0   => F = 48

Шаг №2
x1 x2 x3 S1 S2 S3 св. член Θ
-2/3 1 1/3 1/3 0 0 12
7/3 0 4/3 -2/3 1 0 21 21 : 7/3 = 9
4/3 0 -8/3 1/3 0 1 42 42 : 4/3 ≈ 31,50
14/3 0 -1/3 -4/3 0 0 F - 48
-2/3 1 1/3 1/3 0 0 12
1 0 4/7 -2/7 3/7 0 9
4/3 0 -8/3 1/3 0 1 42
14/3 0 -1/3 -4/3 0 0 F - 48
0 1 5/7 1/7 2/7 0 18
1 0 4/7 -2/7 3/7 0 9
0 0 -24/7 5/7 -4/7 1 30
0 0 -3 0 -2 0 F - 90

Приравниваем свободные переменные нулю, устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные, следовательно, ее значение для данного решения можно найти мгновенно. (см. таблицу)
x3 = 0   S1 = 0   S2 = 0  
x1 = 9   x2 = 18   S3 = 30  
=> F - 90 = 0   => F = 90
Среди коэффициентов выделенной строки нет положительных. Следовательно, найдено наибольшее значение функции F.
В столбце 4 коэффициент в выделенной строке равен нулю, а базисной переменной нет.
Это позволяет сделать вывод о том, что можно найти еще одно решение, при котором F = 90

Шаг №3
x1 x2 x3 S1 S2 S3 св. член Θ
0 1 5/7 1/7 2/7 0 18 18 : 1/7 = 126
1 0 4/7 -2/7 3/7 0 9
0 0 -24/7 5/7 -4/7 1 30 30 : 5/7 = 42
0 0 -3 0 -2 0 F - 90
0 1 5/7 1/7 2/7 0 18
1 0 4/7 -2/7 3/7 0 9
0 0 -24/5 1 -4/5 7/5 42
0 0 -3 0 -2 0 F - 90
0 1 7/5 0 2/5 -1/5 12
1 0 -4/5 0 1/5 2/5 21
0 0 -24/5 1 -4/5 7/5 42
0 0 -3 0 -2 0 F - 90

Приравниваем свободные переменные нулю, устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные, следовательно, ее значение для данного решения можно найти мгновенно. (см. таблицу)
x3 = 0   S2 = 0   S3 = 0  
x1 = 21   x2 = 12   S1 = 42  
=> F - 90 = 0   => F = 90
С геометрической точки зрения, оба полученных решения являются точками пространства, т.е. образуют отрезок.
Любая точка (любое решение), принадлежащая данному отрезку, также будет являться решением.

Ответ:

X1 = 9 * t + 21 * (1 - t)

X2 = 18 * t + 12 * (1 - t)

X3 = 0 * t + 0 * (1 - t)

где   0 ≤ t ≤ 1

Fmax = 90











© 2010–2016
По всем вопросам пишите по адресу matematika1974@yandex.ru


Ссылки