ШАГ 1.Выписываем исходное допустимое базисное решение и соответствующее ему значение целевой функции Z.
На первой итерации в качестве базисных выбираем дополнительныепеременные (в нашем примере это Х3, Х4, Х5). Небазисные переменные Х1 и Х2 приравниваем к нулю. Тогда из задачи (2) получим:
Х3 = 2000, Х4 = 28000, Х5 = 9000.
Выписываем полностью исходное допустимое базисное решение:
Примечание 1. Исходя из смысла задачи об оптимальном использовании ресурсов, ситуация, отвечающая исходному плану Х1, означает бездеятельность предприятия. Ресурсы (пашня, труд, удобрения) не используются, поэтому прибыль, отраженная в целевой функции, равна нулю.
Шаг 2 сводится к тому, что даем первой из небазисных переменных единичное приращение и вычисляем, к каким это приведет изменениям для значений базисных переменных. Затем вычисляем изменение значения функции Z. Если оно положительное, то делаем вывод о целесообразности ввода данной небазисной переменной в базис. На этом шаг 2 можно закончить и другие небазисные переменные не исследовать.
Итак, пусть : Δ Х1 = 1
Тогда изменения для базисных переменных Х3, Х4, Х5 запишутся так:
Δ Х3 = -1
Δ Х4 = -4
Δ Х5 = -2
Подставляя эти изменения значений переменных в целевую функцию, получим:
Вывод:Решение Х1 неоптимальное. Переменную Х1 целесообразно ввести в базис, поскольку от этого значение целевой функции Z увеличится
Примечание 2. Т.е., один гектар пашни засевается пшеницей (Х1). Тогда недоиспользованная площадь пашни (Х3) уменьшится на 1 га. А так как каждый гектар пшеницы требует 4 чел.-дн. труда, то недоиспользованный труд (Х4) уменьшится на 4 чел.-дн. Соответственно количество недоиспользованного удобрения (Х5) уменьшится на 2 кг д.в. Целевая функция увеличится на 1500.
Примечание 3. Если мы сделали вывод о целесообразности ввода в базис какой-либо небазисной переменной (в нашем примере это переменная Х1), то другие небазисные переменные (в нашем примере это Х2) испытывать на данном шаге на предмет целесообразности ввода в базис не обязательно.
Примечание 4. Если на какой-либо из итераций на шаге 2 мы убедимся, что ни одну из небазисных переменных нецелесообразно вводить в базис, это будет означать, что получено оптимальное решение.
ШАГ 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.
Переменную Х1 нельзя увеличивать до бесконечности, а только до той величины, которая будет удовлетворять условиям неотрицательности переменных:
Х3> 0, Х4 > 0, Х5> 0 (3)
Переменная Х2 пока остается равной нулю (т.е. под сахарную свеклу площадь пашни пока не выделяется).
Выразим из системы ограничений задачи (2) базисные переменные Х3, Х4, Х5 через вновь вводимую в базис переменную Х1:
Х3 = 2000 - Х1
Х4 = 28000 - 4Х1 (4)
Х5 = 9000 - 2Х1
Так как переменные Х3, Х4, Х5 должны удовлетворять условиям неотрицательности, то соотношения (4) можно записать так:
2000 - Х1 > 0 Х1< 2000 : 1 < 2000 (*)
28000 - 4Х1 > 0 откуда Х1 < 28000 : 4 < 7000
9000 - 2Х1 > 0 Х1< 9000 : 2 < 4500
Для одновременного выполнения условий (3) необходимо, чтобы значение переменной Х1 не превышало 2000, потому что когда Х1 увеличится до значения, равного 2000 обратится в нуль Х3 (см. первое ограничение задачи (2)). При дальнейшем увеличении Х1 до значения 4500, обратится в нуль Х5 (см. третье ограничение задачи (2)). При этом значение Х3 станет меньше нуля и нарушится условие неотрицательности (см первое ограничение задачи (2)). Увеличение Х1 до 7000 приведет к тому, что Х3 и Х5 станут меньше нуля (см. первое и третье ограничения задачи (2)), т.е. нарушится условие неотрицательности переменных.
Таким образом, на данном шаге мы выяснили, какая из базисных переменных первой обратится в нуль при вводе небазисной переменной в базис, и то уравнение, в которое она входит. Это означает, что замена базисной переменной должна произойти именно в этом уравнении. В нашем примере замена прежней базисной переменной произойдет в первом уравнении, где получено наименьшее значение Х1. Пометим это уравнение символом (*).
Окончательно делаем вывод: в новом базисе будут находиться переменные Х1, Х4, Х5, а переменная Х3 становится небазисной (обращается в ноль).
Примечание 4. Если некоторая базисная переменная не уменьшается при переходе к новому базису, а увеличивается или остается прежней, то уравнение, которое ее содержит, на шаге 3 не рассматривается.
ШАГ 4. Пересчет системы линейных уравнений задачи (2) с учетом нового состава базисных переменных.
На предыдущем шаге мы выяснили, что базисной переменной в первом уравнении становится Х1, во втором и третьем уравнениях остаются прежние переменные (соответственно Х4 и Х5).
Преобразуем систему уравнений задачи (2) так, чтобы переменная Х1 осталась только в первом уравнении с коэффициентом, равным +1, и отсутствовала бы в двух других.
Для этого выполним ряд действий:
1. Перепишем в новую систему уравнений (4) первое уравнение из системы (2) в том же виде.
Примечание 5. Если коэффициент при вновь вводимой в базис переменной отличен от единицы, то нужно сделать соответствующие преобразования, т.е. разделить почленно все уравнение на этот коэффициент.
2. Исключим переменную Х1 из второго уравнения системы (2).
Для этого из второго уравнения системы (2) вычтем первое уравнение новой системы (4), умноженное на 4:
4Х1 + 40Х2 + Х4 = 28000
4Х1 + 4Х2 + 4Х3 = 8000
36Х2 - 4Х3 + Х4 = 20000
Это будет второе уравнение новой системы (4).
3. Исключим Х1 из третьего уравнения системы (2).
Для этого из третьего уравнения системы (2) вычтем первое уравнение новой системы (4), умноженное на 2:
2Х1 + 9Х2 + Х5 = 9000
2Х1 + 2Х2 + 2Х3 = 4000
7Х2 - 2Х3 + Х5 = 5000
Это будет третье уравнение новой системы (4).
После таких преобразований новая система уравнений будет иметь вид:
Х3 = 2000 - Х1 
