Разработка математической модели и ПО для задач составления расписания (стр. 7 из 12)
Искусственные переменные можно получить из слабыхпеременных, используемых для превращения неравенств в уравнения. Действительно,если исходные ограничения задачи линейного программирования заданы в виденеравенств:
то, добавив слабую переменную в каждое неравенство, получим:
Если bi
0, то si можноиспользовать в качестве начальных базисных переменных. Различие между искусственными переменными
и слабыми переменными siсостоит в следующем. В оптимальном решении задачи все искусственные переменныедолжны быть равными нулю, поскольку в исходной задаче таких переменных нет. Сдругой стороны, вполне возможно, что в оптимальном решении слабые переменныебудут иметь положительные значения. Для того, чтобыискусственные переменные стали равными нулю, можно представить целевую функциюследующим образом:
где Mi – достаточно большие положительные числа. Идея метода соответствуеттому, что искусственным переменным придаются заведомо большие цены. Такойспособ приводит к нулевым значениям искусственных переменных в оптимальномрешении.
Существует и другой способ получения начального допустимогобазиса. В этом способе, как и в первом, в качестве начальных базисныхпеременных используются искусственные переменные. Рассматривается новая целеваяфункция
, представляющая собой сумму искусственных переменных.Требуется минимизировать , используя z – уравнение как одно из ограничений. Еслиисходная система уравнений имеет допустимое решение, то все искусственныепеременные должны стать равными нулю. Следовательно, минимальное значение 
должно стать равным нулю. Если 
, то исходная система уравнений не имеет допустимых решений.Если 
, то можно опустить целевую функцию и использовать оптимальный базис -формы в качестве начального допустимого базиса дляминимизации z. В литературе такой способ называется двухфазовым симплекс-методом. Напервой фазе метода находится допустимый базис путем минимизации , на второй – минимизируется z и получается оптимальныйбазис. Рассмотри в качестве примера следующую задачу линейногопрограммирования:
минимизировать
при условиях
где все bi неотрицательны.
Если ввести искусственные переменные
и новую целевуюфункцию 
, то получим задачу: минимизировать
, при условиях
-z
Если вычесть все уравнения, содержащие bi,из
-формы, получим:
