Пример №3. Решение задачи линейного программирования симплекс методом. Нахождение наибольшего значения функции (искусственный базис)Данное решение сделано калькулятором, представленным на сайте.
Задача:
Найти наибольшее значение функции при следующих ограничениях: | | | 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 выражена через свободные переменные. Поэтому значение функции 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 выражена через свободные переменные. Поэтому значение функции 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
Ссылки
|