- •Глава III
- •3.1. Метод жесткого многогранника
- •3.2. Метод случайного поиска
- •Рубежный тестовый контроль
- •2. Метод жесткого многогранника
- •Глава IV. Линейное программирование
- •4.1. Необходимые сведения
- •4.2. Примеры задач линейного программирования
- •4.3. Основная задача линейного программирования (озлп)
- •4.4. Эквивалентная задача линейного программирования
- •4.5. Симплекс-метод
- •4.6. Геометрическая интерпретация задачи линейного программирования
- •Рубежный тестовый контроль
4.3. Основная задача линейного программирования (озлп)
Рассмотрим систему уравнений
, (4.21)
где
, , , (4.22)
т.е. рассматривается система из m уравнений, которая содержит n неизвестных. Вопрос о том, как соотносятся между собой m и n, будет обсуждаться ниже. Рассмотрим также целевую функцию
, (4.23)
где – заданный вектор, – заданная константа.
Требуется найти такой вектор x, чтобы при выполнении ограничений
; (4.24)
, (4.25)
целевая функция
(4.26)
достигала минимума.
Замечание 1. Соотношения (4.24) содержат только равенства. Но вот, например, в задаче об использовании сырья ограничения-равенства вообще отсутствуют, зато фигурируют ограничения-неравенства вида
. (4.27)
Неравенство (4.27) преобразуем в эквивалентные ему соотношения, которые вписываются в рамки задачи (4.24) – (4.26). Неравенство (4.27) запишем в виде
.
Вводим далее новую переменную , потребовав, чтобы
; (4.28)
. (4.29)
Ограничение (4.27) эквивалентно ограничениям (4.28), (4.29). Таким образом, каждое ограничение в виде неравенства может быть превращено в ограничение-равенство, при этом, однако, появляется новая неизвестная величина. Эта новая переменная включается в целевую функцию (4.26) с нулевым коэффициентом .
Из сказанного вытекает, что сколько неравенств превращаются в равенства, столько новых (дополнительных) переменных должно быть введено.
Замечание 2. В том случае, когда требуется найти максимум целевой функции F(x), вводится новая целевая функция . Она и минимизируется.
Замечание 3. Как следует из (4.25), все переменные должны быть не отрицательными. Для переменных , которые по своей физической сущности не могут быть таковыми, вводится замена
. (4.30)
Если в ходе решения задачи линейного программирования будет найдена переменная , то это будет означать, что .
Замечание 4. Если некоторая координата такова, что она может принимать как положительные, так и отрицательные значения, то в этом случае вводятся такие две новые переменные и , что
; (4.31)
(4.32)
Замечание 5. В соотношения (4.24) – (4.26) входят только одноиндексные переменные , а, например, в задаче использования оборудования применяются двухиндексные переменные.
С помощью замены
, , (4.33)
все двухиндексные переменные превращаются в новые, но уже одноиндексные. Например, имеются переменные , , , , , , т.е. имеются двухиндексные переменные , ; Вводим новые переменные
,
т.е.
.
Другими словами
, , , , , .
Если ; , то
. (4.34)
Пример. Рассмотрим пример из задачи использования оборудования, т.е. задачу (4.15)
, (4.35)
;
; (4.36)
;
. (4.37)
В данном случае вводим новые переменные
, , ,
т.е.
.
Соотношения (4.35) – (4.37) приобретают следующий вид:
(4.38)
(4.39)
;
, .
Неравенства (4.38) преобразуются в равенства:
;
,
т.е. имеем
(4.40)
Вводим матрицу
x1 x2 x3 x4 x5 x6
и векторы (см. (4.40), (4.39))
, , .
Задача в форме ОЗЛП запишется как
;
;
.