При ограничениях

.

Решение. Вводим дополнительные неотрицательные переменные х ₃, х ₄, х ₅ с соответствующими знаками:

В соответствии с правилом, сформулированным в § 5.2, на I шаге в качестве основных возьмем дополнительные переменные.

I шаг. Основные переменные: х ₃, х ₄, х ₅. Неосновные переменные: х ₁, х ₂.

Выражаем основные переменные через неосновные:

- первое базисное решение недопустимое (отрицательная компонента выделена), поэтому не может быть оптимальным. Линейную функцию на недопустимом решении не рассматриваем! В системе (5.6) выберем то уравнение, которое содержит отрицательный свободный член, т.е. первое уравнение (если таких уравнений несколько, выбираем любое из них).

Поскольку переменная х ₃ принимает отрицательное значение при первом базисном решении, то ее необходимо увеличить. Это возможно сделать за счет увеличения любой из неосновных переменных, входящих в первое уравнение с положительным коэффициентом, в данном случае — переменной х ₂..Если перевести эту переменную в основные, то она, став положительной, увеличит переменную х ₃ Как только х ₂ достигает значения 1, то х ₃ обратится в 0, т.е. исчезнет отрицательная компонента в решении. Можно считать, что переменная х ₃ станет неосновной. Однако рост переменной х ₂ ограничен условиями неотрицательности остальных переменных, которые определяют х ₂ = min{l;3; } = 1, т.е. первое уравнение — разрешающее. При х ₂ = 1 переменная х ₃ = 0 и переходит в неосновные переменные.

II шаг. Основные переменные: х ₂, х ₄, х ₅. Неосновные переменные: х ₁, х ₃.

Выражая новые основные переменные через новые неоcновные, начиная с разрешающего уравнения, получаем

и базисное решение Х ₂ = (0; 1; 0; 2; 3), которое является допустимым. Поэтому выражаем через неосновные переменные линейную функцию F = х ₁ + х ₂ = 1 + 2 x ₁ + x ₃ и необходимо продолжать решение в соответствии с алгоритмом, изложенным в § 5.2.

Однако не всегда первый же шаг избавляет от недопустимого решения.

Пример 5.4. Решить симплексным методом задачу:

при ограничениях:

.

Решение. После введения дополнительных неотрицательных переменных с соответствующими знаками получим систему уравнений:

На I шаге дополнительные переменные возьмем в качестве основных, так как они удовлетворяют правилу, изложенному § 5.2: входят во все уравнения и только по одному разу.

I шаг. Основные переменные: х ₃, х ₄, х ₅, х ₆. Неосновные переменные: х ₁, х ₂.

Выразим основные переменные через неосновные:

— первое базисное решение недопустимое, с двумя отрицательными компонентами.

Для получения допустимого базисного решения поступаем так, как в примере 5.3: выбираем любое уравнение, содержащее отрицательный свободный член — первое или например первое, и в нем любую неосновную переменную с положительным коэффициентом: x ₁ или х ₂, например х ₁. Наибольшее возможное значение х ₁ = min {12/2; ; 10/2; } достигается в третьем уравнении, оно разрешающее, и переменная х ₅ переходит в неосновные переменные. Однако при этом ни одна из отрицательных компонент базисного решения не пропадает! Поэтому невыгодно переводить переменную х ₁ основные переменные. Переведем в основные х ₂, тогда большее возможное значение х ₂ = min {12/3; 7; 10; 2} = 2 достигается в четвертом уравнении; при этом переменная х ₆ перейдет в неосновные, и исчезает одна отрицательная компонента в базисном решении.

II шаг. Основные переменные: х ₂, х ₃, х ₄, х ₅. Неосновные переменные: х ₁, х ₆.

Выразим новые основные переменные через новые неосновные, начиная с четвертого уравнения:

=(0; 2; -6; 5; 8; 0) — недопустимое базисное решение с одной отрицательной компонентой. Рассмотрим второе уравнение (с отрицательным свободным членом) и переведем в основные одну из неосновных переменных, х ₁ или x ₂, входящих в уравнение с положительными коэффициентами.

Получим из уравнений их наибольшие возможные значения: х ₁ = min { ; 3; ;8/2} = 3 достигается во втором уравнении; х ₆= { ;2;5;8} = 2 тоже определяет второе уравнение как разрешающее. Любой выбор устранит недопустимость решения, этому безразлично, какую переменную х ₁ или х ₆ выбрать. Переведем х ₆ в основные.

III шаг. Основные переменные: х ₂, х ₄, х ₅, х ₆. Неосновные переменные: х ₁, х ₃.

Выразим новые основные переменные через новые неосновные, начиная со второго уравнения:

Х ₃ = (0;4;0;3;4;2) — допустимое базисное решение. Выражаем функцию цели через неосновные переменные: F = -2 x ₁ + 3 х ₂ = 12 - 4 x ₁ + х ₃. Дальнейшее решение предоставляем читателю в соответствии с алгоритмом, изложенным в § 5.2.

Замечание 1. Если базисное решение недопустимое и для его улучшения есть возможность выбора переменной, переводимой из неосновных в основные, то рекомендуется выбрать такую неосновную переменную, которая определит в качестве разрешающего то уравнение системы, где содержится отрицательный свободный член. Только в этом случае новое базисное решение будет содержать, по крайней мере, на одну отрицательную компоненту меньше. Если в качестве разрешающего будет получено уравнение, не содержащее отрицательного свободного члена, то в новом базисном решении число отрицательных компонент не уменьшится.

Замечание 2. Из примера 5.4 не следует делать вывод о том, что чем больше отрицательных компонент в первоначальном базисном решении, тем больше потребуется шагов, чтобы получить допустимое базисное решение. Оказывается, что в некоторых случаях невозможно получить допустимое базисное решение даже при одной отрицательной компоненте, а иногда его можно получить за один шаг, хотя все компоненты первоначального базисного решения отрицательны. Дальнейшие примеры пояснят это замечание.

Рассмотрим задачу о составлении оптимального рациона, приведенную в § 1.2 и решенную геометрически в примере 4.2.

Пример 5.5. Решить симплексным методом задачу:

при ограничениях:

Решение. Введем дополнительные переменные х ₃, х ₄, x ₅, x ₆ (каждую со знаком "минус"). Их экономический смысл – разность между содержанием и необходимым минимумом каждого из питательных веществ. На I шаге берем дополнительные переменные в качестве основных.

I шаг. Основные переменные: х ₃, х ₄, х ₅. Неосновные переменные: х ₁, х ₂.

После преобразований получим:

Х ₁=(0;0;-9;-8;-12) – первое базисное решение недопустимое, содержащее три отрицательные компоненты. Неосновная переменная х ₂ входит в каждое уравнение с положительным коэффициентом, поэтому имеет смысл перевести ее в основные. В случае, когда все основные переменные принимают отрицательные значения, для ускорения решения можно в качестве значения для переменной х ₂ взять максимальное оценочное отношение из полученных во всех уравнениях: х ₂=max{9/3;8;12}=12. Третье уравнение является разрешающим, при этом х ₅ = 0 и переходит в основные, а остальные основные переменные принимают положительные значения.

II шаг. Основные переменные: х ₂, х ₄, х ₅. Неосновные переменные: х ₁, х ₃.

После преобразований получим:

X ₂=(0;9;0;10;42) — допустимое базисное решение. Если действовать, как в предыдущих примерах, то для получения допустимого решения потребуется три шага!

Заканчивая решение примера 5.5 симплексным методом, на следующем шаге получаем оптимальное базисное решение X ₃ = (2;3;0;0;5), при котором минимальные затраты на рацион составляют F _min = 26. Учитывая экономический смысл исходных и дополнительных переменных, получаем, что в оптимальном рационе используется 2 единицы корма I и 3 единицы корма II, при этом вещества S ₁ и S ₂ потребляются в необходимых минимальных количествах (х ₃ = x ₄ = 0), а питательное вещество S ₃ оказывается в избытке на 5 единиц (х ₅ = 5).

Итак, для ускорения отыскания допустимого базисного решения, когда все основные переменные отрицательны, рекомендуется выбрать, если возможно, неосновную переменную, входящую во все уравнения со знаком "плюс", и в качестве ее значения брать не min, a max оценочных отношений, получаемых из каждого уравнения.

Пример 5.6. Решить симплексным методом задачу:

при ограничениях:

Решение. Введем дополнительные переменные:

Рис. 5.3

I шаг. Основные переменные: х ₃, х ₄. Неосновные переменные: х ₁, х ₂.

Х ₁ = (0; 0; 2; -1) -- недопустимое базисное решение. Во втором уравнении выбираем любую переменную - х ₁ или х ₂ так как обе имеют знак "плюс", и переводим в основные. Для х ₁: min{2;6/2} = 2, разрешающее первое уравнение; для х ₂: min{2;6} = 2, разрешающее тоже первое уравнение, поэтому в любом случае не удается сразу избавиться от отрицательной компоненты базисного решения.

II шаг. Основные переменные: х ₁, х ₄. Неосновные переменные: х ₂, х ₃.

Получим после преобразований:

Х ₂=(2;0;0;-2) - недопустимое базисное решение. Однако второе уравнение не содержит неосновной переменной с положительным коэффициентом, поэтому невозможно увеличить переменную x ₄ и получить допустимое базисное решение. Задача противоречива (см. рис. 5.3).

После анализа результатов, полученных при решении примеров 5.1 - 5.6, сформулируем алгоритм получения первоначального допустимого базисного решения:

Если каждая дополнительная переменная входит в уравнение с тем же знаком, что и свободный член, стоящий в правой части уравнения, то дополнительные переменные можно брать в качестве основных на I шаге. При этом получится допустимое базисное решение.

Если первое базисное решение получилось недопустимым (например, в качестве основных взяты дополнительные переменные, но хотя бы одна из них входила в уравнение со знаком, противоположным знаку свободного члена), то рассматриваем уравнение, содержащее отрицательный свободный член (любое, если их несколько) и переводим в основные ту неосновную переменную, которая в это уравнение входит с положительным коэффициентом (любую, если их несколько). Такие шаги повторяем до тех пор, пока достигается допустимое базисное решение.

Если базисное решение недопустимое, а в уравнении, содержащем отрицательный свободный член, отсутствует неосновная переменная с положительным коэффициентом, то в этом случае допустимое базисное решение получить невозможно, т.е. условия задачи противоречивы.