Курсовая работа: Симплекс метод в форме презентации
В нашем случае базисными переменными являются x3 , x4 ,x5 ,x6 . Остальные переменные являются свободными (x1 ,x2 ). Придавая произвольные значения свободным переменным мы будем получать различные значения базисных. Любое решение системы ограничений задачи называется допустимым. Опорным называется решение задачи, записанное в каноническом виде в котором свободные переменные равны 0.
Теорема 1:
Оптимальное решение задачи линейного программирования находиться среди опорных решений. Идея симплекс метода состоит в том, что определенному правилу перебираются опорные решения до нахождения оптимального среди них, перебирая опорные решения, по существу, мы перебираем различные базисные переменные, то есть на очередном шаге некоторая переменная переводится из числа базисных, а вместо нее некоторая переменная из числа свободных в число базисных.
7x1 +5x2 →max
x3 =19-2x1 -3x2 (0;0;19;13;15;18)
x4 =13-2x1 -x2 первоначальный опорный план
x5 =15-3x2
x6 =18-3x1 F(x1 , x2 )=7*0+5*0=0
xi ≥0, (i=1,…n)
На интуитивном уровне понятно, что естественным будет увеличение x1 , так как коэффициент при нем больше чем при x2 . Оставляя x2 =0, мы можем увеличивать до тех пор, пока x3 , x4 , x5 , x6 будут оставаться неотрицательными.
x1 =min{19/2;13/2;∞;18/3}=6
Это означает что при x1 =6, x6 =0, то есть x1 -переходит в число базисных, а x6 -в число свободных.
x1 =6-1/3 x6
Выражаем неизвестные переменные и целевую функцию через свободные переменные:
x3 =19-2(6-1/3 x6 )-3 x2 =19-12+2/3 x6 -3 x2 =7+2/3 x6 -3 x2
x4 =13-2(6-1/3 x6 )- x2 =1+2/3 x6 - x2
x5 = x5 =15
F(x2 ; x6 ) =42-7/3 x6 +5 x2
При данном опорном плане (6;0;7;1;15;0) x2 переводиться из свободных в базисные переменные:
x2 =min{∞;7/3;1/11;15/3}=1
Выражаем x2 через x4
x2 =1+2/3 x6 - x4
Выражаем неизвестные переменные и целевую функцию через свободные переменные:
x3 =7+2/3 x6 -3(1+2/3x6 –x4 )= 7+2/3 x6 -3-2x6 +3x4 =4-4/3x6 +3 x4
x5 = 12-2x6 +3x4 -
F=42-7/3 x6 +5(1+2/3x2 - x4 ) =47-7/3x6 +10/3x6 -5x4 =47+x6 -5x4
x6 положительное, следовательно можно увеличивать
x6 =min{18;∞;3;6}=1
x4 =4/3-4/9 x6 - 1/3x3