ГЛАВА 4. НЕКОТОРЫЕ ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ

В этой главе сообщаются в весьма сжатой форме необходимые сведения из теории выпуклых множеств и линейного программирования. Введены основные понятия, сформулированы некоторые теоремы. Изложение в максимальной степени согласовано с книгой Д. Б. Юдина и Е. Г. Гольштейна [45] (вышедшей ранее в серии «Экономико-математическая библиотека»), к которой читателю и следует обратиться при необходимости за более подробными сведениями.

В этой же главе дана формальная постановка задачи целочисленного линейного программирования.

§ 1. Основные понятия линейного программирования

1.1. Задача линейного программирования формулируется следующим образом.

Максимизировать

при условиях

или, в более лаконичной записи: Максимизировать

при условиях

Множество наборов удовлетворяющих условиям называется областью определения задачи линейного программирования Вектор удовлетворяющий условиям называется планом (или допустимым решением) задачи (1.1) — (1.4). Расширенным планом задачи называют набор где план задачи

План обращающий в максимум ли» нейную форму (1.1), называется оптимальным планом (или решением) задачи (1.1) — (1.4). Расширенный план X называется оптимальным расширенным планом, если план X оптимальный.

Иногда бывает удобно ввести следующие обозначения: область определения задачи (1.1) — (1.4); задача оптимальный

план задачи (1.1) — (1.4), — оптимальный расширенный план. Через обозначим множество оптимальных планов задачи

Матрично-векторная запись задачи линейного программирования: Максимизировать

при условиях

Ясно, что задача минимизации линейной формы при условиях (1.6) — (1.8) сводится к задаче максимизации линейной формы при тех же условиях.

Задача линейного программирования называется разрешимой, если существует оптимальный планер

1.2. Часто оказывается удобной каноническая форма задачи линейного программирования. Максимизировать

при условиях

Задача легко сводится к задаче (1.9) — (1.11) введением новых неотрицательных переменных и заменой неравенств уравнениями

Вектор-столбец называется вектором условий задачи (1.9) — (1.11). Вектор-столбец называется вектором ограничений задачи (1.9)-(1.11).

Рис. 4.1.1.

1.3. Геометрическая интерпретация задачи линейного программирования иллюстрирует исходные понятия (и методы решения). Приведем пример. Максимизировать

при условиях

Геометрическая интерпретация приведена на рис. 4.1.1.

Область определения задачи заштрихована. Точке соответствует оптимальный план Направляющий вектор С прямой определяет направление, в котором растет линейная форма