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

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

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

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

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

Решение:

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

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

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

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

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

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

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

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

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

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

x1 = 2   x2 = 1  

Fmax = 1


Перейти к решению своей задачи
Наверх







© 2010-2023

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


Ссылки