переменной х. Если перевести эту переменную в основные, то она, став положительной, увеличит переменную х. Как только х достигнет уровня 1, то х обратиться в нуль, т.е. переменная х станет неосновной. В то же время рост переменной х ограничен условиями неотрицательности остальных переменных, которые определяют х = min {1,3,00} =1.
То есть первое уравнение разрешающее. При х = 1, переменная х = О и переходит в неосновные переменные.
Шаг 2. Основные переменные хх, х Неосновные переменные л:,х Выражая новые основные переменные через неосновные, получим
х=1+х+Хз
х = 2-Хз х = 3-х.
Базисное решение соответственно равно = (0; 1; 0; 2; 3) и является
допустимым. Целевая линейная функция F, выраженная через неосновные переменные, имеет вид
F = Xj+ 2x=1 +2х+Хз
В дальнейшем процедура получения оптимального решения соответствует описанному выше симплекс-методу.
Не во всех случаях получение допустимого базисного решения возможно уже после первого шага.
Рассмотрим следующий пример.
Определить максимум линейной функции
F = -2х + Зх -> max
при ограничениях: 2х + Зх > 12; -х + х < 7; 2х + х < 10; х > 2; х > О, введем дополнительные переменные и перейдем к системе уравнений.
2Xj + Зх2-Хз= 12 -x-fx-fx = 7
2Xj+X2 + X5= 10
На первом шаге дополнительные переменные возьмем в качестве основных, учитывая, что они входят во все уравнения по одному разу.
Шаг 1. Основные переменные х, Х, х, х Неосновные переменные
соотношения х = min
l*2.
Выразим основные переменные через неосновные: 3 =-12 +2л:,+ 32
Xj= 10-2x, -х
Х = (0; 0; - 12; 7; 10; -2) первое базисное решение недопустимо, так как
в него входят две отрицательные компоненты. Для получения допустимого базисного решения выбираем уравнение, содержащее отрицательную постоянную. В рассматриваемом примере это первое и четвертое уравнения. Выберем, например, первое и в нем неосновную переменную или
х. Пусть это будет х наибольшее возможное значение х выбирается из оо,оо,5,оо} = 3 достигается в третьем уравнении, оно разрешающее, и переменная х переходит в неосновные переменные.
Нетрудно проверить, что в этом случае количество отрицательных переменных в базисном решении сохраняется и, следовательно, переводить х в основные переменные нецелесообразно. Переведем в основные
переменные х. Наибольшее значение х определяется из соотношения Х2 = min( 00,7,5,00} = 5, достигается в четвертом уравнении. При этом переменная х переходит в неосновные, и в базисном решении становится на одну отрицательную компоненту меньше.
Шаг 2. Основные переменные х, х, х, х Неосновные переменные х, х
Выразим новые основные переменные через новые неосновные, начиная с четвертого уравнения:
2 = 2 + , х=-6 + 2х, +3х
31 о
4 = 5+,-Х,
Хз = 8-2х,-х,.
= (0; 2; -6; 5; 8; 0) - недопустимое базисное решение с одной отрицательной компонентой. Рассмотрим второе уравнение, в которое вхо-74
значения = mm
х = mm
дит отрицательная постоянная «-6», и переведем в основные одну из неосновные переменных х или х, входящих в уравнение с положительными коэффициентами. Получим из уравнений их набольшие возможные 00,00,00,4} =4 достигается на четвертом уравнении
00,00,5,00} =5. Выберем х, например, в качестве основной.
ШагЗ. Основные переменные х, х, х, х Неосновные переменные х, х
Выразим основные переменные через неосновные, начиная с третьего уравнения.
х = 7 + х-х х = 9 + 5х-3х х = 3-3х+х
= (0; 7; 9; 0; 3; 5) - допустимое базисное решение. Выражая функцию цели через неосновные переменные, получим:
F = -2х + Зх = -2Xj + 3(7 + х - хр = 21 + Xj - Зх
В дальнейшем задача решается согласно алгоритму симплекс-метода.
Пользуясь предлагаемой схемой определения допустимого базисного решения, необходимо учитывать следующее. Если базисное решение недопустимо и для его улучшения есть возможность выбора переменной, переводимой из неосновных переменных в основные, то рекомендуется выбрать такую неосновную переменную, которая должна определить в качестве разрешающего то уравнение системы, где содержится отрицательная постоянная. Только в этом случае новое базисное решение будет содержать по крайней мере на одну отрицательную компоненту меньше. Если в качестве разрешающего будет получено уравнение, не содержащее отрицательной постоянной, то в новом базисе количество отрицательных компонент сохранится.
Как будет показано ниже, количество шагов, необходимых для получения допустимого базисного решения, не зависит от числа отрицательных компонент в исходном базисном решении.
В качестве примера рассмотрим задачу следующего вида.