Образец машинного решения симлекс задачи
Главная → Проекты → Реализация метода искусственного базиса (М-метода) → Пример
Реализация симплекс-метода в случае произвольных свободных членов методом искусственного базиса (M-методом)
Исходные данные:
1.0*x1+ 1.0*x2 >= 4.01.0*x1+ 2.0*x2 >= 6.0
-1.0*x1+ 2.0*x2 <= 12.0
1.0*x1+ 1.0*x2 <= 12.0
F(x)= 1.0*x1+ 4.0*x2
Введем выравнивающие и искусственные переменные:
1.0*x1+ 1.0*x2 -1.0*x3 +1.0*y1 = 4.01.0*x1+ 2.0*x2 -1.0*x4 +1.0*y2 = 6.0
-1.0*x1+ 2.0*x2 +1.0*x5 = 12.0
1.0*x1+ 1.0*x2 +1.0*x6 = 12.0
F(x)= 1.0*x1+ 4.0*x2 - M*(y1 +y2) → max
Начнем решение задачи:
Шаг №1
Базис | Св.члены | x1 | x2 | x3 | x4 | x5 | x6 | y1 | y2 | Оценка |
y 1 | 4.0 | 1.0 | 1.0 | -1.0 | 0.0 | 0.0 | 0.0 | 1.0 | 0.0 | 4.0 |
y 2 | 6.0 | 1.0 | 2.0 | 0.0 | -1.0 | 0.0 | 0.0 | 0.0 | 1.0 | 3.0 |
x 5 | 12.0 | -1.0 | 2.0 | 0.0 | 0.0 | 1.0 | 0.0 | 0.0 | 0.0 | 6.0 |
x 6 | 12.0 | 1.0 | 1.0 | 0.0 | 0.0 | 0.0 | 1.0 | 0.0 | 0.0 | 12.0 |
F (x) | 0.0 | -1.0 | -4.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | max |
M func | -10.0 | -2.0 | -3.0 | 1.0 | 1.0 | 0.0 | 0.0 | -1.0 | -1.0 | max |
Базис | Св.члены | x1 | x2 | x3 | x4 | x5 | x6 | y1 | y2 |
y 1 | 1.0 | 0.5 | 0.0 | -1.0 | 0.5 | 0.0 | 0.0 | 1.0 | -0.5 |
x 2 | 3.0 | 0.5 | 1.0 | 0.0 | -0.5 | 0.0 | 0.0 | 0.0 | 0.5 |
x 5 | 6.0 | -2.0 | 0.0 | 0.0 | 1.0 | 1.0 | 0.0 | 0.0 | -1.0 |
x 6 | 9.0 | 0.5 | 0.0 | 0.0 | 0.5 | 0.0 | 1.0 | 0.0 | -0.5 |
F (x) | 12.0 | 1.0 | 0.0 | 0.0 | -2.0 | 0.0 | 0.0 | 0.0 | 2.0 |
M func | -1.0 | -0.5 | 0.0 | 1.0 | -0.5 | 0.0 | 0.0 | -1.0 | 0.5 |
Шаг №2
Базис | Св.члены | x1 | x2 | x3 | x4 | x5 | x6 | y1 | y2 | Оценка |
y 1 | 1.0 | 0.5 | 0.0 | -1.0 | 0.5 | 0.0 | 0.0 | 1.0 | -0.5 | 2.0 |
x 2 | 3.0 | 0.5 | 1.0 | 0.0 | -0.5 | 0.0 | 0.0 | 0.0 | 0.5 | 6.0 |
x 5 | 6.0 | -2.0 | 0.0 | 0.0 | 1.0 | 1.0 | 0.0 | 0.0 | -1.0 | беск |
x 6 | 9.0 | 0.5 | 0.0 | 0.0 | 0.5 | 0.0 | 1.0 | 0.0 | -0.5 | 18.0 |
F (x) | 12.0 | 1.0 | 0.0 | 0.0 | -2.0 | 0.0 | 0.0 | 0.0 | 2.0 | max |
M func | -1.0 | -0.5 | 0.0 | 1.0 | -0.5 | 0.0 | 0.0 | -1.0 | 0.5 | max |
Базис | Св.члены | x1 | x2 | x3 | x4 | x5 | x6 | y1 | y2 |
x 1 | 2.0 | 1.0 | 0.0 | -2.0 | 1.0 | 0.0 | 0.0 | 2.0 | -1.0 |
x 2 | 2.0 | 0.0 | 1.0 | 1.0 | -1.0 | 0.0 | 0.0 | -1.0 | 1.0 |
x 5 | 10.0 | 0.0 | 0.0 | -4.0 | 3.0 | 1.0 | 0.0 | 4.0 | -3.0 |
x 6 | 8.0 | 0.0 | 0.0 | 1.0 | 0.0 | 0.0 | 1.0 | -1.0 | 0.0 |
F (x) | 10.0 | 0.0 | 0.0 | 2.0 | -3.0 | 0.0 | 0.0 | -2.0 | 3.0 |
M func | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 |
Шаг №3
Базис | Св.члены | x1 | x2 | x3 | x4 | x5 | x6 | Оценка |
x 1 | 2.0 | 1.0 | 0.0 | -2.0 | 1.0 | 0.0 | 0.0 | 2.0 |
x 2 | 2.0 | 0.0 | 1.0 | 1.0 | -1.0 | 0.0 | 0.0 | беск |
x 5 | 10.0 | 0.0 | 0.0 | -4.0 | 3.0 | 1.0 | 0.0 | 3.3 |
x 6 | 8.0 | 0.0 | 0.0 | 1.0 | 0.0 | 0.0 | 1.0 | беск |
F (x) | 10.0 | 0.0 | 0.0 | 2.0 | -3.0 | 0.0 | 0.0 | max |
Базис | Св.члены | x1 | x2 | x3 | x4 | x5 | x6 |
x 4 | 2.0 | 1.0 | 0.0 | -2.0 | 1.0 | 0.0 | 0.0 |
x 2 | 4.0 | 1.0 | 1.0 | -1.0 | 0.0 | 0.0 | 0.0 |
x 5 | 4.0 | -3.0 | 0.0 | 2.0 | 0.0 | 1.0 | 0.0 |
x 6 | 8.0 | 0.0 | 0.0 | 1.0 | 0.0 | 0.0 | 1.0 |
F (x) | 16.0 | 3.0 | 0.0 | -4.0 | 0.0 | 0.0 | 0.0 |
Шаг №4
Базис | Св.члены | x1 | x2 | x3 | x4 | x5 | x6 | Оценка |
x 4 | 2.0 | 1.0 | 0.0 | -2.0 | 1.0 | 0.0 | 0.0 | беск |
x 2 | 4.0 | 1.0 | 1.0 | -1.0 | 0.0 | 0.0 | 0.0 | беск |
x 5 | 4.0 | -3.0 | 0.0 | 2.0 | 0.0 | 1.0 | 0.0 | 2.0 |
x 6 | 8.0 | 0.0 | 0.0 | 1.0 | 0.0 | 0.0 | 1.0 | 8.0 |
F (x) | 16.0 | 3.0 | 0.0 | -4.0 | 0.0 | 0.0 | 0.0 | max |
Базис | Св.члены | x1 | x2 | x3 | x4 | x5 | x6 |
x 4 | 6.0 | -2.0 | 0.0 | 0.0 | 1.0 | 1.0 | 0.0 |
x 2 | 6.0 | -0.5 | 1.0 | 0.0 | 0.0 | 0.5 | 0.0 |
x 3 | 2.0 | -1.5 | 0.0 | 1.0 | 0.0 | 0.5 | 0.0 |
x 6 | 6.0 | 1.5 | 0.0 | 0.0 | 0.0 | -0.5 | 1.0 |
F (x) | 24.0 | -3.0 | 0.0 | 0.0 | 0.0 | 2.0 | 0.0 |
Шаг №5
Базис | Св.члены | x1 | x2 | x3 | x4 | x5 | x6 | Оценка |
x 4 | 6.0 | -2.0 | 0.0 | 0.0 | 1.0 | 1.0 | 0.0 | беск |
x 2 | 6.0 | -0.5 | 1.0 | 0.0 | 0.0 | 0.5 | 0.0 | беск |
x 3 | 2.0 | -1.5 | 0.0 | 1.0 | 0.0 | 0.5 | 0.0 | беск |
x 6 | 6.0 | 1.5 | 0.0 | 0.0 | 0.0 | -0.5 | 1.0 | 4.0 |
F (x) | 24.0 | -3.0 | 0.0 | 0.0 | 0.0 | 2.0 | 0.0 | max |
Базис | Св.члены | x1 | x2 | x3 | x4 | x5 | x6 |
x 4 | 14.0 | 0.0 | 0.0 | 0.0 | 1.0 | 0.3 | 1.3 |
x 2 | 8.0 | 0.0 | 1.0 | 0.0 | 0.0 | 0.3 | 0.3 |
x 3 | 8.0 | 0.0 | 0.0 | 1.0 | 0.0 | 0.0 | 1.0 |
x 1 | 4.0 | 1.0 | 0.0 | 0.0 | 0.0 | -0.3 | 0.7 |
F (x) | 36.0 | 0.0 | 0.0 | 0.0 | 0.0 | 1.0 | 2.0 |
Оптимальное решение найдено!
Реклама:
Комментарии:
имя:
e-mail (не публикуется):
комментарий:
e-mail (не публикуется):
комментарий:
Вы можете оставить первый комментарий.