Логотип

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

Подробное решение типовых задач по высшей математике
Главная   >>   Пример №1. Симплекс метод. Нахождение наибольшего значения функции

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

Задача:

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

Знак системы x1 + x2 550
2 x1 + 3 x2 1200
12 x1 + 30 x2 9600

x1 ≥ 0    x2 ≥ 0    

Решение:

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

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

Знак системы x1 + x2 550
2 x1 + 3 x2 1200
12 x1 + 30 x2 9600


Знак системы x1 + x2 + S1 = 550
2 x1 + 3 x2 + S2 = 1200
12 x1 + 30 x2 + S3 = 9600

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

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

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

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

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

Знак системы x1 + x2 + S1 = 550
2 x1 + 3 x2 + S2 = 1200
12 x1 + 30 x2 + S3 = 9600

F = 3 x1 + 4 x2

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

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

Шаг №1
x1 x2 S1 S2 S3 св. член Θ
1 1 1 0 0 550 550 : 1 = 550
2 3 0 1 0 1200 1200 : 3 = 400
12 30 0 0 1 9600 9600 : 30 = 320
3 4 0 0 0 F - 0
1 1 1 0 0 550
2 3 0 1 0 1200
2/5 1 0 0 1/30 320
3 4 0 0 0 F - 0
3/5 0 1 0 -1/30 230
4/5 0 0 1 -1/10 240
2/5 1 0 0 1/30 320
7/5 0 0 0 -2/15 F - 1280

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

Шаг №2
x1 x2 S1 S2 S3 св. член Θ
3/5 0 1 0 -1/30 230 230 : 3/5 ≈ 383,33
4/5 0 0 1 -1/10 240 240 : 4/5 = 300
2/5 1 0 0 1/30 320 320 : 2/5 = 800
7/5 0 0 0 -2/15 F - 1280
3/5 0 1 0 -1/30 230
1 0 0 5/4 -1/8 300
2/5 1 0 0 1/30 320
7/5 0 0 0 -2/15 F - 1280
0 0 1 -3/4 1/24 50
1 0 0 5/4 -1/8 300
0 1 0 -1/2 1/12 200
0 0 0 -7/4 1/24 F - 1700

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

Шаг №3
x1 x2 S1 S2 S3 св. член Θ
0 0 1 -3/4 1/24 50 50 : 1/24 = 1200
1 0 0 5/4 -1/8 300
0 1 0 -1/2 1/12 200 200 : 1/12 = 2400
0 0 0 -7/4 1/24 F - 1700
0 0 24 -18 1 1200
1 0 0 5/4 -1/8 300
0 1 0 -1/2 1/12 200
0 0 0 -7/4 1/24 F - 1700
0 0 24 -18 1 1200
1 0 3 -1 0 450
0 1 -2 1 0 100
0 0 -1 -1 0 F - 1750

Приравниваем свободные переменные нулю, устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные, следовательно, ее значение для данного решения можно найти мгновенно. (см. таблицу)
S1 = 0   S2 = 0  
x1 = 450   x2 = 100   S3 = 1200  
=> F - 1750 = 0   => F = 1750
Среди коэффициентов выделенной строки нет положительных. Следовательно, найдено наибольшее значение функции F.

Ответ:

x1 = 450   x2 = 100  

Fmax = 1750










© 2010-2018, по всем вопросам пишите по адресу matematika1974@yandex.ru



Ссылки