Ферма занимается разведением крупного рогатого скота

Обозначим через х1 кг количество овса, через x2 кг количество ячменя, через x3 кг количество сои. Согласно условию задачи составим систему ограничений на переменные х1, x2, x3:
0,5х1 + 0,8x2 + 0,9x3 ≥ 2
100х1 + 80x2 + 150x3 ≥ 300
10х1 + 15x2 + 20x3 ≥ 20
х1, x2, x3 >0
F(X0)= 20х1 + 30x2 +40x3 → min
Умножив обе части неравенств на -1, получим систему с другим направлением знака неравенств:
-0,5х1 + -0,8x2 + -0,9x3 ≥ -2
-100х1 + -80x2 + -150x3≥ -300
-10х1 + -15x2 + -20x3 ≥ -20
F(X0) = 20х1 + 30x2 +40x3 = min
Преобразуем неравенства в эквивалентные равенства с помощью дополнительных неизвестных. Симплексные уравнения будут следующими:
-2 = -0,5х1-0,8x2-0,9x3+1x4+0x 5+ 0x6
-300 = -100х1-80x2-150x3+0x4 + 1x 5+ 0x6
-20 = -10х1-15x2-20x3+0x4+0x 5+1x6
F(X0) = 20х1 + 30x2 +40x3+0x4+0x 5+ 0x6 = min
Система симплексных уравнений записывается в таблице.
Cj
P0
X0
х1
x2
x3
x4
x 5
x6
0 x4
-2 -0,5 -0,8 -0,9 1 0 0
0 x 5
-300 -100 -80 -150 0 1 0
0 x6
-20 -10 -15 -20 0 0 1
F(X0) 0 -20 -30 -40 0 0 0
Элементы целевой строки рассчитывают по обычным правилам и получают отрицательные знаки.
В итоговом столбце свободные числа имеют отрицательные знаки. Это является свидетельством того, что данный план нельзя считать допустимым, так как он противоречит экономическому смыслу. План можно считать допустимым только тогда, когда в итоговом столбце не будет отрицательных чисел.
Ликвидация отрицательных чисел в итоговом столбце начинается с наибольшего по абсолютной величине. В нашем примере таким числом является (-300). Строка x 5 в которой находится это число, принимается за ключевую и соответственно выделяется.
Определив ключевую строку, находим ключевой столбец. Для этого нужно элементы целевой строки разделить на элементы ключевой строки и из полученных отношений выбрать наименьшее. Столбец, имеющий наименьшее отношение, принимается за ключевой и так же как ключевая строка, выделяется.
Столбцы х1, х2, х3 будут иметь следующие отношения:
-20/-100 = 0,2
-30/-80= 0,375
-40/-150= 0,26
Наименьшее отношение имеет столбец х1, он и будет являться ключевым.
P0
X0
x1 x2 x3 x4 x5 x6
x4 -0,2 0.1 -0,32 0 1 -0.006 0
x3 2 0,6 0,53 1 0 0,006 0
x6 20 3,33 -4,33 0 0 -0,13 1
F(X0) -80 -6,66 8,66 0 0 0,26 0
В итоговом столбце имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x4 следует ввести переменную x5.
P0
X0
x1 x2 x3 x4 x5 x6
x5 33.33 -16.67 53.33 0 -166.67 1 0
x3 2.22 0.56 0.89 1 -1.11 0 0
x6 24.44 1.11 2.78 0 -22.22 0 1
F(x1) -88.89 -2.22 -5.56 0 44.44 0 0
Выразим базисные переменные через остальные:
x5 = 16.67 x1-53.33 x2+166.67 x4+33.333
x3 = -0.56 x1-0.89 x2+1.11 x4+2.222
x6 = -1.11 x1-2.78 x2+22.22 x4+24.444
Подставим их в целевую функцию:
F(X) = 20 x1+30 x2+40(-0.56 x1-0.89 x2+1.11 x4+2.222)
или
F(X) = -2.22 x1-5.56 x2+44.44 x4+88.889
-16.67 x1+53.33 x2-166.67x4+ x5=33.333
0.56 x1+0.89 x2+ x3-1.11 x4=2.222
1.11 x1+2.78 x2-22.22x4+x6=24.444
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.Решим систему уравнений относительно базисных переменных: x5, x3, x6Полагая, что свободные переменные равны 0, получим первый опорный план:X0 = (0,0,2.222,0,33.333,24.444)Базисное решение называется допустимым, если оно неотрицательно.
P0
X0
x1 x2 x3 x4 x5 x6
x5 33.33 -16.67 53.33 0 -166.67 1 0
x3 2.22 0.56 0.89 1 -1.11 0 0
x6 24.44 1.11 2.78 0 -22.22 0 1
F(X0) 0 2.22 5.56 0 -44.44 0 0
Переходим к основному алгоритму симплекс-метода.Итерация №0.1 . Проверка критерия оптимальности.Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.2. Определение новой базисной переменной.В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент.3. Определение новой свободной переменной.Вычислим значения Di по строкам как частное от деления: bi / ai2и из них выберем наименьшее:min (33.333 : 53.333 , 2.222 : 0.889 , 24.444 : 2.778 ) = 0.625Следовательно, 1-ая строка является ведущей.Разрешающий элемент равен (53.333) и находится на пересечении ведущего столбца и ведущей строки.
P0
X0
x1 x2 x3 x4 x5 x6 min
x5 33.33 -16.67 53.33 0 -166.67 1 0 0.625
x3 2.22 0.56 0.89 1 -1.11 0 0 2.5
x6 24.44 1.11 2.78 0 -22.22 0 1 8.8
F(X1) 0 2.22 5.56 0 -44.44 0 0 0
4