Реферат: Графический метод и симплекс-метод решения задач линейного программирования
После ввода в базис переменной x2 новый план будет иметь вид
x' = (0, x 2, x 3 , x 4 ).
Этот план не является базисным, так как он содержит только одну нулевую координату, значит надо сделать нулевой (исключить из базиса) одну из переменных x 3 или x 4 . Подставим координаты плана x' = (0, x 2, x 3 , x 4 ) в ограничения задачи. Получим
2x 2 + x 3 = 4,
2x 2 + x 4 = 12.
Выразим отсюда базисные переменные x 3 и x 4 через переменную x 2 , вводимую в базис.
| x 3 = 4 – 2x 2, | (2.6) |
| x 4 = 12 – 2x 2 . | (2.7) |
Так переменные x 3 и x 4 должны быть неотрицательны, получим систему неравенств
| 4 – 2x 2 ≥0, | (2.8) |
| 12 – 2x 2 ≥ 0. | (2.9) |
Чем больше значение x 2 , тем больше возрастает целевая функция. Найдем максимальное значение новой базисной переменной, не нарушающее ограничения задачи, то есть удовлетворяющее условиям (2.8), (2.9).
Перепишем последние неравенства в виде
2x 2 ≤ 4,
2x 2 ≤ 12,
откуда максимальное значение x 2 = min { 4/2, 12/2 } = 2. Подставляя это значение в выражения (2.6), (2.7) для x 3 и x 4 ,получаем x 3 = 0.Следовательно x3 выводится из базиса.
Шаг 4. Определение координат нового базисного плана.
Новый базисный план (смежная угловая точка) имеет вид
x' = (0, x 2, 0, x 4 )
Базис этой точки состоит из столбцов A 2 и A 4 , так что 
= (A 2, A 4 ). Этот базис не является единичным, так как вектор A 2 = (2,2),и следовательно задача (2.2)–(2.5) не имеет предпочтительного вида относительно нового базиса. Преобразуем условия задачи (2.3), (2.4) таким образом, чтобы она приняла предпочтительный вид относительно новых базисных переменных x 2, x 4, то есть чтобы переменная x 2 входила в первое уравнение с коэффициентом, равным единице, и не присутствовала во втором уравнении. Перепишем уравнения задачи
– x 1 + 2 x 2 + x 3 = 4, (p 1)
3x 1 +2 x 2 + x 4 = 12. (p 2)
Поделим первое уравнение на коэффициент при x 2 .Получим новое уравнение 
= p 1 / 2, эквивалентное исходному
– 1/2 x 1 + x 2 + 1/2 x 3 = 2. ( )
Используем это уравнение, которое назовем разрешающим, для исключения переменной x 2 из второго уравнения. Для этого надо уравнение умножить на 2 и вычесть из p 2 . Получим 
= p 2 – 2 = p 2 – p 1 :
4 x 1 – x 3 + x 4 = 8. ( )
В итоге получили новое "предпочтительное" представление исходной задачи относительно новых базисных переменных x 2 , x 4 :
f (x ) = x 1 + 2 x 2 + 0 x 3 + 0 x 4 max
– 1/2 x 1 + x2 + 1/2 x 3 = 2 ( )
4 x 1 – x 3 + x 4 = 8 ( )
xj 0, j = 1,2,3,4
Подставляя сюда представление нового базисного плана x 1 = (0, x 2, 0, x 4 ), сразу найдем его координаты, так как значения базисных переменных равны правым частям уравнений
x' = (0, 2, 0, 8); f (x 1 )=4.