Разработка сайтов и программного обеспечения, системное администрирование, обучение программированию и работе с СУБД MySQL

in english

zoonman·ruПроектыСтатьи и заметки

Образец машинного решения симлекс задачи

Главная → Проекты → Реализация метода искусственного базиса (М-метода) → Пример

Реализация симплекс-метода в случае произвольных свободных членов методом искусственного базиса (M-методом)

Исходные данные:
1.0*x1+ 1.0*x2 >= 4.0
1.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.0
1.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
F(x)=10 X=(2; 2; 0; 0; 10; 8)

Шаг №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
F(x)=16 X=(0; 4; 0; 2; 4; 8)

Шаг №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
F(x)=24 X=(0; 6; 2; 6; 0; 6)

Шаг №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
F(x)=36 X=(4; 8; 8; 14; 0; 0)

Оптимальное решение найдено!

Другие материалы:

Метки: симплекс метод.

Комментарии:

Вы можете оставить первый комментарий.

имя:

e-mail (не публикуется):

комментарий:

© 2005—2012, Ткачев Филипп
Программист, веб-разработка и прикладное ПО.
Все права защищены.