Постановка задачи линейного программирования

Общая постановка задачи: найти наибольшее (наименьшее) значение

при ограничениях

Ограничения задаются линейными формами.

Основные фигуры, встречающиеся в линейном программировании:

1. Прямая линия

M₁, M₂ – точки в n-мерном пространстве

, t - параметр

2. Плоскость

Задаётся скалярным произведением:

3. Полупространство

Из этих фигур составляются различные другие фигуры.

Область дополнительных значений – многогранник.

Задача: определить существует ли решение или нет, если существует – найти его (единственное решение или много решений, поиск наименьшего или наибольшего значения).

Определение моментов переключения.

смотрим вопрос № 21