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

и другие интересные типовые задачи		 En

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

Данное решение сделано калькулятором, представленным на сайте.
Перейти к решению своей задачи
Задача:

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

Решение:

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

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

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

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

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

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

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

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

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

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

x1 = 30   x2 = 20  

Fmin = -50


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

Ссылки