 | Сервис для решения задач по линейному программированиюи другие интересные типовые задачи |
English |
Пример №5. Решение задачи линейного программирования симплекс методом.
Решение не единственное
Данное решение сделано калькулятором, представленным на сайте.
Пример №1. Симплекс метод. Нахождение наибольшего значения функции
Пример №2. Симплекс метод. Нахождение наименьшего значения функции
Пример №3. Симплекс метод. Нахождение наибольшего значения функции (искусственный базис)
Пример №4. Симплекс метод. Нахождение наименьшего значения функции (искусственный базис)
Пример №6. Симплекс метод. Функция неограниченно возрастает
Пример №7. Симплекс метод. Функция неограниченно убывает
Пример №8. Симплекс метод. Область допустимых решений - пустое множество
Пример №2. Симплекс метод. Нахождение наименьшего значения функции
Пример №3. Симплекс метод. Нахождение наибольшего значения функции (искусственный базис)
Пример №4. Симплекс метод. Нахождение наименьшего значения функции (искусственный базис)
Пример №6. Симплекс метод. Функция неограниченно возрастает
Пример №7. Симплекс метод. Функция неограниченно убывает
Пример №8. Симплекс метод. Область допустимых решений - пустое множество
Задача:
Найти наибольшее значение функции
| F | = | x1 | + | 2 | x2 |
при следующих ограничениях:
 | x1 | + | 2 | x2 | ≤ | 6 | ||
| 2 | x1 | + | x2 | ≤ | 8 | |||
| x2 | ≤ | 2 |
Решение:
1. Свободные члены системы должны быть неотрицательными.
Данное условие выполнено.
2. Каждое ограничение системы должно представлять собой уравнение.
| | x1 | + | 2 | x2 | ≤ | 6 | ||
| 2 | x1 | + | x2 | ≤ | 8 | |||
| x2 | ≤ | 2 |
| | x1 | + | 2 | x2 | + | S1 | = | 6 | |||||||||
| 2 | x1 | + | x2 | + | S2 | = | 8 | ||||||||||
| x2 | + | S3 | = | 2 |
S1 ≥ 0, S2 ≥ 0, S3 ≥ 0. Введенные переменные S1, S2, S3, называются балансовыми переменными.
3. Нахождение начального базиса и значения функции F, которое соответствует найденному начальному базису.
Что такое базис?
Переменная называется базисной для данного уравнения, если она входит в данное уравнение с коэффициентом один и не входит в оставшиеся уравнения системы (при условии, что в правой части уравнения стоит неотрицательное число).
Если в каждом уравнении присутствует базисная переменная, тогда говорят, что в системе присутствует базис.
Переменные, которые не являются базисными, называются свободными.
В чем заключается идея симплекс метода?
Каждому базису соответствует единственное значение функции. Одно из них является наибольшим значением функции F.
Мы будем переходить от одного базиса к другому.
Следующий базис будем выбирать таким образом, чтобы получить значение функции F не меньше имеющегося.
Очевидно, количество возможных базисов для любой задачи число не очень большое.
Следовательно, рано или поздно, ответ будет получен.
Как осуществляется переход от одного базиса к другому?
Запись решения удобнее вести в виде таблиц. Каждая строка таблицы эквивалентна уравнению системы. Выделенная строка состоит из коэффициентов функции (см. таблицу ниже). Это позволяет не переписывать переменные каждый раз, что существенно экономит время.
B выделенной строке выбираем наибольший положительный коэффициент (можно выбрать любой положительный).
Это необходимо для того, чтобы получить значение функции F не меньше имеющегося.
Выбран столбец.
Для положительных коэффициентов выбранного столбца считаем отношение Θ и выбираем наименьшее значение.
Это необходимо для того, чтобы после преобразования столбец свободных членов остался неотрицательным.
Выбрана строка.
Определен элемент, который будет базисным. Далее считаем.
В нашей системе есть базис?
Переменная называется базисной для данного уравнения, если она входит в данное уравнение с коэффициентом один и не входит в оставшиеся уравнения системы (при условии, что в правой части уравнения стоит неотрицательное число).
Если в каждом уравнении присутствует базисная переменная, тогда говорят, что в системе присутствует базис.
Переменные, которые не являются базисными, называются свободными.
В чем заключается идея симплекс метода?
Каждому базису соответствует единственное значение функции. Одно из них является наибольшим значением функции F.
Мы будем переходить от одного базиса к другому.
Следующий базис будем выбирать таким образом, чтобы получить значение функции F не меньше имеющегося.
Очевидно, количество возможных базисов для любой задачи число не очень большое.
Следовательно, рано или поздно, ответ будет получен.
Как осуществляется переход от одного базиса к другому?
Запись решения удобнее вести в виде таблиц. Каждая строка таблицы эквивалентна уравнению системы. Выделенная строка состоит из коэффициентов функции (см. таблицу ниже). Это позволяет не переписывать переменные каждый раз, что существенно экономит время.
B выделенной строке выбираем наибольший положительный коэффициент (можно выбрать любой положительный).
Это необходимо для того, чтобы получить значение функции F не меньше имеющегося.
Выбран столбец.
Для положительных коэффициентов выбранного столбца считаем отношение Θ и выбираем наименьшее значение.
Это необходимо для того, чтобы после преобразования столбец свободных членов остался неотрицательным.
Выбрана строка.
Определен элемент, который будет базисным. Далее считаем.
В нашей системе есть базис?
| | x1 | + | 2 | x2 | + | S1 | = | 6 | |||||||||
| 2 | x1 | + | x2 | + | S2 | = | 8 | ||||||||||
| x2 | + | S3 | = | 2 |
Базис есть, т.е. мы можем начать решение.
| F | = | x1 | + | 2 | x2 |
Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. систему)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно.
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно.
| x1 = 0 x2 = 0 S1 = 6 S2 = 8 S3 = 2 |
=> F = 0 |
Начальный базис найден и получено значение функции F, соответствующее найденному базису.
4. Нахождение наибольшего значения функции F.
Шаг №1
| x1 | x2 | S1 | S2 | S3 | св. член | Θ |
| 1 | 2 | 1 | 0 | 0 | 6 | 6 : 2 = 3 |
| 2 | 1 | 0 | 1 | 0 | 8 | 8 : 1 = 8 |
| 0 | 1 | 0 | 0 | 1 | 2 | 2 : 1 = 2 |
| 1 | 2 | 0 | 0 | 0 | F - 0 | |
| 1 | 0 | 1 | 0 | -2 | 2 | |
| 2 | 0 | 0 | 1 | -1 | 6 | |
| 0 | 1 | 0 | 0 | 1 | 2 | |
| 1 | 0 | 0 | 0 | -2 | F - 4 |
Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно. (см. выделенную строку таблицы)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно. (см. выделенную строку таблицы)
| x1 = 0 S3 = 0 x2 = 2 S1 = 2 S2 = 6 |
=> F - 4 = 0 => F = 4 |
Шаг №2
| x1 | x2 | S1 | S2 | S3 | св. член | Θ |
| 1 | 0 | 1 | 0 | -2 | 2 | 2 : 1 = 2 |
| 2 | 0 | 0 | 1 | -1 | 6 | 6 : 2 = 3 |
| 0 | 1 | 0 | 0 | 1 | 2 | |
| 1 | 0 | 0 | 0 | -2 | F - 4 | |
| 1 | 0 | 1 | 0 | -2 | 2 | |
| 0 | 0 | -2 | 1 | 3 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 2 | |
| 0 | 0 | -1 | 0 | 0 | F - 6 |
Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно. (см. выделенную строку таблицы)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно. (см. выделенную строку таблицы)
| S1 = 0 S3 = 0 x1 = 2 x2 = 2 S2 = 2 |
=> F - 6 = 0 => F = 6 |
Среди коэффициентов выделенной строки нет положительных. Следовательно, найдено наибольшее значение функции F.
В столбце 5 коэффициент в выделенной строке равен нулю, а базисной переменной нет.
Это позволяет сделать вывод о том, что можно найти еще одно решение при котором F = 6.
Это позволяет сделать вывод о том, что можно найти еще одно решение при котором F = 6.
Шаг №3
| x1 | x2 | S1 | S2 | S3 | св. член | Θ |
| 1 | 0 | 1 | 0 | -2 | 2 | |
| 0 | 0 | -2 | 1 | 3 | 2 | 2 : 3 ≈ 0,67 |
| 0 | 1 | 0 | 0 | 1 | 2 | 2 : 1 = 2 |
| 0 | 0 | -1 | 0 | 0 | F - 6 | |
| 1 | 0 | 1 | 0 | -2 | 2 | |
| 0 | 0 | -2/3 | 1/3 | 1 | 2/3 | |
| 0 | 1 | 0 | 0 | 1 | 2 | |
| 0 | 0 | -1 | 0 | 0 | F - 6 | |
| 1 | 0 | -1/3 | 2/3 | 0 | 10/3 | |
| 0 | 0 | -2/3 | 1/3 | 1 | 2/3 | |
| 0 | 1 | 2/3 | -1/3 | 0 | 4/3 | |
| 0 | 0 | -1 | 0 | 0 | F - 6 |
Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно. (см. выделенную строку таблицы)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно. (см. выделенную строку таблицы)
| S1 = 0 S2 = 0 x1 = 10/3 x2 = 4/3 S3 = 2/3 |
=> F - 6 = 0 => F = 6 |
С геометрической точки зрения, оба полученных решения являются точками пространства, т.е. образуют отрезок.
Любая точка (любое решение), принадлежащая данному отрезку, также будет являться решением.
Ответ: