2xl + 3x2-2x3 + 3xi<3, -х1 + х3 + 2х4 < О,
1» "2 *3 "4 -
a) С помощью программы TORA найдите оптимальное решение данной задачи.
b) Имея оптимальное решение, выберите любую небазисную переменную и попробуйте ввести ее в базис, щелкнув на кнопке Next Iteration. Сравните полученное значение целевой функции с оптимальным. (Идея этого упражнения заключается в том, чтобы показать, что в оптимальном решении любая небазисная переменная, введенная в базис, не может улучшить значения целевой функции.)
3.4. ИСКУССТВЕННОЕ НАЧАЛЬНОЕ РЕШЕНИЕ
В примере 3.3.1 при начальном допустимом базисном решении гарантировалось, что все последующие базисные решения, получаемые при выполнении симплекс-метода, также будут допустимыми. В задачах линейного программирования, где все ограничения являются неравенствами типа "<" (с неотрицательной правой частью), дополнительные (остаточные) переменные позволяют сформировать начальное допустимое базисное решение. Естественно, возникает вопрос: как найти начальное допустимое базисное решение в задачах ЛП, где есть ограничения в виде равенств или неравенств типа ">"?
Наиболее общим способом построения начального допустимого базисного решения задачи ЛП является использование искусственных переменных. Эти переменные в первой итерации играют роль дополнительных остаточных переменных, но на последующих итерациях от них освобождаются. Разработано два тесно связанных между собой метода нахождения начального решения, которые используют искусственные переменные: М-метод5 и двухэтапный метод.
3.4.1. М-метод
Пусть задача ЛП записана в стандартной форме (см. раздел 3.1). Для любого равенства i, в котором не содержится дополнительная остаточная переменная, введем искусственную переменную Д, которая далее войдет в начальное базисное решение. Но, поскольку эта переменная искусственна (другими словами, не имеет никакого "физического смысла" в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф.
Переменная i?, с помощью достаточно большого положительного числа М штрафуется путем ввода в целевую функцию выражения -MRt в случае максимизации целевой функции и выражения +MRt - в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведет к нулевому значению переменной Rt. Следующий пример проясняет детали этого метода.
5 М-метод также называют методом больших штрафов. - Прим. ред.
Пример 3.4.1
Минимизировать z = 4х, + х,
при выполнении условий
Зх, -¥ х2 = 3, 4а-, + Зл-2 > 6, х, + 2х2 < 4, х„х2>0.
Стандартная форма этой задачи получается в результате добавления дополнительной (избыточной) переменной х3 во второе неравенство и дополнительной (остаточной) переменной xt в третье неравенство. Эта задача в стандартной форме будет записана следующим образом.
Минимизировать z = 4х, + х2
при выполнении условий
Зх, + х2 = 3, 4л-, + Зх2 - х3 = 6, х, + 2х2 + xt = 4, л",, х2, х3, х4 0.
В полученной задаче первое и второе уравнения не имеют дополнительных (остаточных) переменных, которые можно ввести в базисное решение. Поэтому введем в эти уравнения искусственные переменные Л, и R2, а в целевую функцию добавим штраф MRX + MR2. В результате получим следующую задачу ЛП.
Минимизировать z = 4х, + х2 + МЛ, + MR2
при выполнении условий
Зх, + х2 + Л, = 3,
4а-, + Зх2 -х3 + Л2 = 6,
х, + 2х2 + х4 = 4,
" -К,, Л, "Kg, -
В этой модифицированной задаче переменные Л,, Л2 и х4 можно использовать в качестве начального допустимого базисного решения. В результате получим следующую симплекс-таблицу.
Прежде чем применять симплекс-метод, надо согласовать значения в z-строке с остальной частью таблицы. В частности, значение функции z, соответствующее начальному базисному решению Л, = 3, Л2 = 6 и х4 = 4, должно равняться ЗМ+ 6М + 0 = 9М, а не 0, как показано в таблице. Это противоречие связано с тем,
что переменным Л, и R2 соответствуют ненулевые коэффициенты (-М, -М) в строке г (сравните с начальным решением в примере 3.3.1, где дополнительным переменным соответствуют нулевые коэффициенты в z-строке). Чтобы сделать эти коэффициенты нулевыми, следует умножить элементы строк Л, и R2 на величину М, и затем сложить эти строки с z-строкой. (Обратите внимание на "подсвеченные" единицы в этих строках - если бы эти коэффициенты были отличны от единиц, то необходимо было бы сначала разделить все элементы этих строк на данные коэффициенты.) Кратко это действие можно записать следующим образом.
Новая z-строка = старая z-строка + М х /?,-строка + М х /?2-строка
Измененная симплекс-таблица примет следующий вид (проверьте!).
Базис | | | | | | | Решение |
| -4 + 7м | -1 + AM | | | | | |
Я | | | | | | | |
| | | | | | | |
| | | | | | | |
Отметим, что теперь z = 9М, что соответствует базисному решению Л, = 3, R2 = 6 и х4-4.
Последняя таблица готова к применению симплекс-метода с использованием условий оптимальности и допустимости, описанных в разделе 3.3.2. Поскольку мы минимизируем целевую функцию, находим наибольший положительный коэффициент в z-строке. Наибольший коэффициент -4 + 7М соответствует переменной д-,, которая и будет вводимой. Условие допустимости указывает на переменную Л, в качестве исключаемой.
Поскольку вводимая и исключаемая переменные определены, новую симплекс-таблицу можно вычислить с помощью метода Гаусса-Жордана. Заметим, что вычисления в z-строке, где присутствует М, следует проводить алгебраически. Так, для получения новой г-строки надо новую ведущую строку умножить на -(-4 + 7М) и сложить с текущей z-строкой. В результате получим следующую таблицу.
Базис | | | | | | | Решение |
| | (1 + 5А*)/3 | | (4 - 7М)/3 | | | 4 +2м |
| | | | | | | |
| | | | -4/3 | | | |
| | | | -1/3 | | | |
Отметим, что уже первая итерация исключила из базисного решения искусственную переменную Rlt что является результатом включения штрафа в целевую функцию.
Последняя таблица показывает, что следующими (вводимой и исключаемой) переменными будут д:2 и R2 соответственно. Конечно, для получения оптимального решения может потребоваться больше двух итераций. В данной задаче оптимальным решением будет хх = 2/5, л\, = 9/5, х3 = 1 и z = 17/5.