Разработка математической модели и ПО для задач составления расписания
Пусть задача линейного программирования записана в канонической форме:
минимизировать

при условиях

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