Основная (каноническая) задача линейного программирования (ОЗЛП)

Геометрический метод решения ОЗЛП.
В практических задачах, как правило .
Предполагаем что , .
Выразим m базисных переменных через две свободных (например, и ). Система уравнений (2) примет вид:
(3)

С учетом условия неотрицательности переменных множество G можно представить в виде системы неравенств:
(4)
Отложим по осям ОХ1 и ОХ2 значения свободных переменных, а также построим полуплоскости, соответствующие неравенствам (4):

Утверждение. ОДР, если она существует, всегда является выпуклым множеством, имеющим форму многоугольника.
Поиск оптимального решения.
Подставим соотношение (3) в (1).
Получим: . (5)
Будем рассматривать целевую функцию в виде:
, (6)
т.к. параметр a не влияет на оптимальное решение .

Линии уровня целевой функции - параллельные прямые:
,
Изменение параметра C равносильно мысленному перемещению прямой параллельно самой себе.
В каком направлении необходимо перемещать прямую , чтобы значение убывало?

Замечание: ОДР может быть неограниченным (незамкнутым) множеством. В этом случае возможна ситуация, когда ОЗЛП не имеет конечного решения, т.е.

Задача 3.
Определить
при ограничениях:
Решение.
.
основные переменные;
свободные переменные .

Выразим основные переменные через свободные:
; .