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

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

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

Симплекс метод является универсальным, т.е. позволяет решить произвольную задачу линейного программирования.
Конечно, симплекс метод не является самым наглядным, как и все аналитические методы решения.
Но на самом деле не так все сложно, как может показаться на первый взгляд.
Этот калькулятор находит общее решение только для случая, когда решением является отрезок прямой.
Вы можете решить свою задачу или посмотреть примеры решений.
Введите целые числа или обыкновенные дроби.
Например: 12, -3/4.
Найти значение функции
F   =   x1 +   x2 +   x3 +   x4 +   x5 +   x6
при следующих ограничениях:
Знак системы x1 + x2 + x3 + x4 + x5 + x6
x1 + x2 + x3 + x4 + x5 + x6
x1 + x2 + x3 + x4 + x5 + x6
x1 + x2 + x3 + x4 + x5 + x6
x1 + x2 + x3 + x4 + x5 + x6

Задача:

Найти наибольшее значение функции
F = 30 x1 + 50 x2 + 80 x3
при следующих ограничениях:
Знак системы 20 x1 + 20 x2 + 30 x3 ≤ 9500
10 x1 + 10 x2 + 10 x3 ≤ 5500
10 x2 + 10 x3 ≤ 2000
x1 ≥ 0    x2 ≥ 0    x3 ≥ 0    

Решение:

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

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

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

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

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

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

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

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

Шаг №1
x1 x2 x3 S1 S2 S3 св. член Θ
20 20 30 1 0 0 9500 9500 : 30 ≈ 316,667
10 10 10 0 1 0 5500 5500 : 10 = 550
0 10 10 0 0 1 2000 2000 : 10 = 200
30 50 80 0 0 0 F - 0
20 20 30 1 0 0 9500
10 10 10 0 1 0 5500
0 1 1 0 0 1/10 200
30 50 80 0 0 0 F - 0
20 -10 0 1 0 -3 3500
10 0 0 0 1 -1 3500
0 1 1 0 0 1/10 200
30 -30 0 0 0 -8 F - 16000
Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно. (см. выделенную строку таблицы)
x1 = 0   x2 = 0   S3 = 0  
x3 = 200   S1 = 3500   S2 = 3500   		=> F - 16000 = 0   => F = 16000

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

x1 = 175   x2 = 0   x3 = 200  

Fmax = 21250


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

Ссылки