Логотип

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

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

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

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

Задача:

Найти наименьшее значение функции
F = 10 x1 -7 x2 -5 x3
при следующих ограничениях:

Знак системы 6 x1 + 15 x2 + 6 x3 9
14 x1 + 42 x2 + 16 x3 21
2 x1 + 8 x2 + 2 x3 4

x1 ≥ 0    x2 ≥ 0    x3 ≥ 0    

Решение:

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

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

Знак системы 6 x1 + 15 x2 + 6 x3 9
14 x1 + 42 x2 + 16 x3 21
2 x1 + 8 x2 + 2 x3 4


Знак системы 6 x1 + 15 x2 + 6 x3 + S1 = 9
14 x1 + 42 x2 + 16 x3 + S2 = 21
2 x1 + 8 x2 + 2 x3 + S3 = 4

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

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

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

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

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

Знак системы 6 x1 + 15 x2 + 6 x3 + S1 = 9
14 x1 + 42 x2 + 16 x3 + S2 = 21
2 x1 + 8 x2 + 2 x3 + S3 = 4

F = 10 x1 -7 x2 -5 x3

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

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

Шаг №1
x1 x2 x3 S1 S2 S3 св. член Θ
6 15 6 1 0 0 9 9 : 15 ≈ 0,60
14 42 16 0 1 0 21 21 : 42 ≈ 0,50
2 8 2 0 0 1 4 4 : 8 ≈ 0,50
10 -7 -5 0 0 0 F - 0
6 15 6 1 0 0 9
1/3 1 8/21 0 1/42 0 1/2
2 8 2 0 0 1 4
10 -7 -5 0 0 0 F - 0
1 0 2/7 1 -5/14 0 3/2
1/3 1 8/21 0 1/42 0 1/2
-2/3 0 -22/21 0 -4/21 1 0
37/3 0 -7/3 0 1/6 0 F + 7/2

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

Шаг №2
x1 x2 x3 S1 S2 S3 св. член Θ
1 0 2/7 1 -5/14 0 3/2 3/2 : 2/7 ≈ 5,25
1/3 1 8/21 0 1/42 0 1/2 1/2 : 8/21 ≈ 1,31
-2/3 0 -22/21 0 -4/21 1 0
37/3 0 -7/3 0 1/6 0 F + 7/2
1 0 2/7 1 -5/14 0 3/2
7/8 21/8 1 0 1/16 0 21/16
-2/3 0 -22/21 0 -4/21 1 0
37/3 0 -7/3 0 1/6 0 F + 7/2
3/4 -3/4 0 1 -3/8 0 9/8
7/8 21/8 1 0 1/16 0 21/16
1/4 11/4 0 0 -1/8 1 11/8
115/8 49/8 0 0 5/16 0 F + 105/16

Приравниваем свободные переменные нулю, устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные, следовательно, ее значение для данного решения можно найти мгновенно. (см. таблицу)
x1 = 0   x2 = 0   S2 = 0  
x3 = 21/16   S1 = 9/8   S3 = 11/8  
=> F + 105/16 = 0   => F = -105/16
Среди коэффициентов выделенной строки нет отрицательных. Следовательно, найдено наименьшее значение функции F.

Ответ:

x1 = 0   x2 = 0   x3 = 21/16  

Fmin = -105/16











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


Ссылки